Semi-partitioned scheduling for fixed-priority real-time tasks based on intelligent rate monotonic algorithm

摘要

In this paper, a new semi-partitioned scheduling algorithm on multiprocessor platforms, based on intelligent rate monotonic algorithm is proposed. Intelligent rate monotonic algorithm is an extended version of the famous rate monotonic algorithm. By splitting some tasks between processors, semi-partitioning is used to enhance overall utilisation. Each semi-partitioned approach has two phases, partitioning and scheduling. The main challenge of semi-partitioned scheduling algorithms is how to partition and split tasks by which they are safely scheduled under the identified scheduling policy, with high utilisation. The partitioning phase of our proposed approach called Semi-Partitioned Intelligent Rate Monotonic-First-Fit (SIRM-FF) includes three sub-phases. Task splitting is done only in the third sub-phase. In the second sub-phase, processors are selected by a first-fit method. The use of first-fit method makes SIRM-FF create a lower number of sub-tasks in comparison to previous works, hence the number of context switches of sub-tasks and overhead due to task splitting is reduced. The feasibility of tasks and sub-tasks which are partitioned by SIRM-FF is formally proved and overall utilisation is compared with competitors.