Research And Implementation Of Semi-partitioned Multiprocessor Real-time Scheduling

Since multicore architecture is gaining dominance in micro-processor design, real-time scheduling for multicores has become the hot topic in real-time research community and industry. In fixed priority scheduling, the utilization bounds for global scheduling and partitioned scheduling are only50%, so scheduling policies that has higher utilization bound and less preemptions is highly desirable. For the purpose of improving schedulability without sacraficing the advantage of partitioned scheduling, in semi-partitioned scheduling, most tasks are fixed to particular processors to reduce runtime overhead, while a few tasks are splitted into sub-tasks and allocated to different processors.In soft real-time systems, occasional deadline misses of jobs are allowed. In such situations, if the tardiness of the tasks are proved to be bounded and the bound can be calculated, then we can guarantee that no task will delay unboundedly, which is a very important concern of soft real-time systems. But research on tardiness of semi-partitioned scheduling is not yet mature. We study the tardiness of fixed-priority-semi-partitioned scheduling, and present an algorithm to calculate the tardiness bound, given Rate Monotonic (RM) scheduling as an example.Semi-partitioned scheduling policies can greatly improve the utilization of the CPU. But there lacks implementation of semi-partitioned scheduling in real-life operating systems. We have developed a multicore semi-partitioned real-time scheduler. The key issues in designing a semi-partitioned scheduler, such as task splitting and task migration, are analyzed. Then we present the detailed implementation of the scheduler in Linux2.6.20kernel. A user library is developed as well, which exposes interfaces to users allowing extending the scheduler with different semi-partitioned scheduling algorithms. Extensive experiments are conducted to verify the correctness of our implementation. This work will play an important role in research on semi-partitioned real-time scheduling, and help to push the use of semi-partitioned scheduling in real-life systems.