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 non-concurrent 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.