即時系統中多處理器優先權排程演算法

近年來，多處理器系統已經廣泛的被使用。然而，許多即時系統的排程演算法都是基於單一處理器系統而發展的，例如RM 和EDF 排程演算法。但單一處理器和多處理器有著一些本質上的差異，直接在多處理器上使用這些演算法並不合適。在硬即時系統上，最重要的責任就是保持所有的工作在期限內完成，當處理器的使用率高的時候，要達成這個目標變得相當困難。在本論文中，我們提出多優先權處理器排程演算法，它賦予所有的工作和處理器不同的優先權。此演算法可避免處理器時間變得破碎，同時,它為有需要比較長處理器時間的工作保留較長的處理器時間，這樣的排程策略可以增加可排程比率，當處理器的負載較重時，模擬結果顯示此演算法即使在系統有重的負載時仍是相當有效率的。

關鍵字

即時系統；演算法；排程；優先權；多處理器

並列摘要

In recent years, multiprocessor systems are used widespread. However, in real-time systems many scheduling algorithms are developed based on single processor systems, such as rate-monotonic (RM) scheduling algorithm and earliest deadline first (EDF) scheduling algorithm. There are some different properties between single processor systems and multiprocessor systems. Those scheduling algorithms designed for single processor systems are not suitable for applying to multiprocessor systems. For the hard real-time system, it is most important to keep all tasks to meet their deadlines. If the system’s utilization is high, it is hard to approach this goal. In this thesis, we propose a scheduling algorithm, Multiprocessor Priority (MPP) scheduling algorithm, for multiprocessor real-time systems. The scheduler assigns all tasks and processors different priorities to prevent the processor time’s fragmentation. Moreover, it reserves longer available processor time for the task that requires longer execution time. This kind of scheduling strategy could increase system’s schedulable rate when the processor’s load is heavy. The simulation results show that the proposed algorithm is efficient even when the system load is heavy.

並列關鍵字

real time system ； algorithm ； scheduling ； priority ； multiprocessor

參考文獻

[1] B. Anderson, S. Baruah, and J. Jonsson, "Static-Priority Scheduling

Systems," Parallel and Distributed Processing Techniques and

Languages, 3rd Ed,

[4] A. Burns, "Scheduling Hard Real-Time Systems," Software

Engineering, Volume 6, Issue 3, pp 116-128, Journal, 1991

國際替代計量

即時系統中多處理器優先權排程演算法

未授權

主題瀏覽