JCSE, vol. 14, no. 3, pp.121-130, 2020

DOI: http://dx.doi.org/10.5626/JCSE.2020.14.3.121

Real-Time Scheduling for Periodic Tasks on Uniform Multiprocessors

Sang-Gil Lee and Cheol-Hoon Lee
System Software Lab., Department of Computer Science and Engineering, Chungnam National University, Daejeon, Korea

Abstract: The problem of scheduling a set of periodic tasks on a uniform multiprocessor system is considered in the present study. Each processor in a uniform multiprocessor system is characterized by its speed or computation capacity, i.e., execution of a job on a processor with speed s for t time units completes s x t units of execution. In the commonly-known partitioned scheduling, each task is assigned to a processor and all of its jobs are required to be executed on that processor. However, partitioning of periodic tasks requires solving the bin-packing problem, which is known to be intractable (NPhard in the strong sense). This paper presents a global scheduling algorithm that transforms a given periodic task system into another using a "task-splitting" (as opposed to the "set-splitting" technique. Each transformed periodic task system is guaranteed to be scheduled successfully on any uniform multiprocessor using a partitioned scheduling algorithm. The earliest deadline first (EDF) algorithm is chosen for scheduling tasks on each processor. It is proven that the proposed algorithm results in the theoretical-maximum utilization bound on any uniform multiprocessor platform if the platform is "reasonably powerful". Therefore, the proposed algorithm is optimal in the sense of maximizing achievable utilization. Since the task-splitting technique will incur context switches during runtime, we have also considered the ways of reducing the number of context switches, and suggest a method which can significantly reduce the number of context switches in the schedules generated by the proposed algorithm.

Keyword: Real-time scheduling; Real-time tasks; Task-splitting

Full Paper:   188 Downloads, 1191 View