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

In real-time task scheduling on multiprocessor systems, partitioning approach has received the attention of many researchers because of its higher least upper bound utilization of safe systems. Semi-partitioning allows some tasks to be split into subtasks and each subtask to be assigned to a different processor. Though task splitting improves the performance of systems, by counting each subtask as a separate task, it increases the effective number of tasks to be scheduled, which in turn, raises the execution overhead. This research is on semi-partitioning of tasks and assigning each partition to a separate processor to be scheduled by the well-known scheduler Rate-Monotonic (RM). Using our algorithm, we do not need to define release time for subtasks of a task to assure their nonconcurrent execution and the number of effective tasks, in turn, is reduced. It is theoretically proven that with the proposed semi-partitioning and RM scheduling algorithm, all processors may safely run their tasks according to their deadlines. Further, experimental results on 3000 randomly generated task-sets indicates that not only is utilization factor boosted, but the number of broken tasks also is decreased.