多處理器系統(tǒng)實時調度EDZL算法的研究.pdf

1、實時系統(tǒng)不僅要保證任務運行邏輯上的正確性，而且還要保證在限定的時間內能夠完成指定任務。否則，錯過了截止期的實時任務會造成像任務運行出錯時一樣嚴重的后果。
　　 實時調度算法是實時系統(tǒng)研究的核心課題之一。隨著計算機技術的飛速發(fā)展，多處理器實時系統(tǒng)的應用已越來越廣泛。多處理器系統(tǒng)上的實時調度也越來越引起人們的關注。最早截止期優(yōu)先（Earliest Deadline First，簡稱EDF）調度算法和最小松弛時間優(yōu)先（Least La

2、xity First，簡稱LLF）調度算法已被證明是單處理器系統(tǒng)上的最優(yōu)調度算法。然而，在多處理器系統(tǒng)上，這種最優(yōu)性失敗了，最早截止時間零松弛（Earliest Deadline Zero Laxity，簡稱EDZL）調度算法明顯優(yōu)于這兩種算法。
　　 本文從EDF實時調度模型出發(fā)，分析了EDF模型在單處理器實時系統(tǒng)上的最優(yōu)性，以及EDF模型在多處理器實時系統(tǒng)上的非最優(yōu)性。引入了EDF模型的改進算法——多處理器實時系統(tǒng)EDZL調

3、度算法。本文對EDZL調度算法進行了較為深入的研究。研究了EDZL算法的性質，并對EDF調度算法和EDZL調度算法進行了比較。證明了EDZL調度算法支配EDF調度算法。
　　 實時調度算法的可調度性是衡量實時系統(tǒng)可靠性的重要指標。EDZL算法是作業(yè)級動態(tài)優(yōu)先級算法，用常規(guī)的利用率分析方法進行可調度性判定比較困難。本文從實時作業(yè)在執(zhí)行時受到的干涉出發(fā)，分析了實時作業(yè)能夠容忍干涉的下界，以及其它任務對作業(yè)可能產(chǎn)生干涉的上界，通過比較