An Improved Static-Priority Scheduling Algorithm for Multi-Processor Real-Time Systems

Abstract

This thesis deals with the problem of designing a new real-time scheduling algorithm for independent periodic tasks with static priority on multi-processor platforms called IBSP-TS (Interval Based Semi-Partitioned Task Splitting). The widely implemented priority policy Rate-Monotonic is applied in the algorithm. IBSP-TS combines interval-based semi-partition technique and another multi-processor scheduling algorithm SPA2 to achieve the highest possible worst-case utilization bound to ln2 while meeting the deadlines. The assignment of IBSP is divided into two parts. In the first part, tasks are categorized into several interval groups. Each group has its own assignment policy except for the last interval. In most cases, there are some tasks residual after applying all the policies. All the residual tasks are handled along with the tasks from last interval in the second part of the algorithm. The schedulability can be ensured by feasibility tests. The simulation experiment shows IBSP-TS has some good properties compared to the best static-priority multi-processor scheduling algorithm at this moment. It generally has higher success ratio, less sorted tasks and also less task migrations. In the best case, it can achieve the break-down utilization point to 76% in simulation. Additionally, this algorithm can let system designer to choose the number of intervals in the algorithm. The more intervals, the less number of sorted tasks there are.