Safety Verification of Rate-Monotonic Least-Splitting Real-Time Scheduler on Multiprocessor System

In real-time task scheduling on multiprocessorsystems, partitioning approach has received the attention ofmany researchers because of its higher least upper boundutilization of safe systems. Semi-partitioning allows sometasks to be split into subtasks and each subtask to beassigned to a different processor. Though task splittingimproves the performance of systems, by counting eachsubtask as a separate task, it increases the effective numberof tasks to be scheduled, which in turn, raises the executionoverhead. This research is on semi-partitioning of tasks andassigning each partition to a separate processor to bescheduled by the well-known scheduler Rate-Monotonic(RM). Using our algorithm, we do not need to definerelease time for subtasks of a task to assure their nonconcurrentexecution and the number of effective tasks, inturn, is reduced. It is theoretically proven that with theproposed semi-partitioning and RM scheduling algorithm,all processors may safely run their tasks according to theirdeadlines. Further, experimental results on 3000 randomlygenerated task-sets indicates that not only is utilizationfactor boosted, but the number of broken tasks also isdecreased.

کلیدواژه ها:

Rate-Monotonic Least Splitting ، Semi- Partitioning ، Hard real-time ، Multiprocessor Scheduling