Research On Multiprocessor Real-time Scheduling Algorithms And Locking Protocols

Early in this century,the concerns of energy consumption promoted the development of multiprocessors.Although the optimal real-time scheduling algorithm has been determined,the conclusion is not compatible with multiprocessor environments.Therefore,the study of multiprocessor real-time scheduling has become one of the essential theories in real-time systems.On the other hand,the growing demand for computing capacity and gradually promising parallel processing techniques make parallel tasks more and more important to real-time systems.However,tasks may access shared resources at runtime that need mutual exclusion to avoid race conditions,and mutually exclusive accesses to shared resources can significantly affect the schedulability.Parallel tasks can further increase shared resource contentions despite the benefit to multiprocessor systems,which brings more challenges to the literature.As a result,this dissertation achieves the following progress in the field of multiprocessor real-time scheduling and locking protocols.Global scheduling can theoretically achieve better utilization on multiprocessors despite higher scheduling overheads,and hence has been an important scheduling paradigm for parallel tasks.However,existing studies have not considered the synchronization of parallel real-time tasks under global scheduling.Hence,this dissertation studies the synchronization of parallel tasks under global scheduling in Chapter 3.Two priority-inheritance-based locking protocols with FIFO-ordered and priority-ordered queues are proposed,respectively.Besides,a blocking and schedulability analysis based on linear programming(LP)technique is also achieved for the proposed protocols.Empirical evaluation reveals that the priority inheritance protocol with priorityordered queues outperforms that with FIFO-ordered queues under intense shared resource contentions.Non-preemptive real-time systems have been widely used to reduce the influences of system overheads and improve time predictability.Nevertheless,existing analyses for parallel tasks with non-preemptive spin-locks are still pessimistic.This dissertation studies the blocking analysis for parallel real-time tasks with non-preemptive spin-locks under federated scheduling in Chapter 4.An LP-based analysis applicable to a finergrained shared resource model is proposed.Empirical evaluation shows that the priorityordered non-preemptive spin-locks outperform the FIFO-ordered non-preemptive spinlocks,and the proposed analysis improves the analytical accuracy prominently.However,non-preemptive spin-locks can perform poorly in large systems with heavy contentions for shared resources due to the utilization waste by spinning.With scalability concerns,this dissertation proposes a hierarchical hybrid locking protocol in Chapter 5.The proposed locking protocol can reduce global contention and utilization waste by applying a token mechanism.Furthermore,to mitigate the utilization waste by exclusive clustering,the proposed approach further distinguishes heavy and light tasks scheduled under federated and partitioned scheduling,respectively.Empirical evaluation shows that the proposed protocol can significantly improve the schedulability of parallel real-time tasks in large systems.Under partitioned scheduling,resource-oriented partitioning(ROP)is a coordinated approach for the classical distributed priority ceiling protocol.Although the coordination of the allocations for both tasks and resources can reduce resource contentions,existing studies on the ROP mainly assign tasks and resources to processors individually via heuristic methods,and hence fail to consider the mutual effects between them.This dissertation proposes an improved ROP's task and resource partitioning approach with the integer linear programming technique.The proposed approach formulates the task and resource partitioning to a feasibility analysis under schedulable conditions,which simultaneously considers task and resource partitioning.Furthermore,the formulation describes the task and resource partitioning as a combination instead of a permutation,which reduces the feasible domain for the problem.Empirical evaluation shows that the proposed approach improves the schedulability and reduces average solving time prominently.