即時多處理器系統上EDkL演算法可排程條件之分析

Abstract

近幾年來，針對多重處理器即時排程的需求變得越來越多；隨著硬體成本的降低，使用多重處理器架構的即時系統已經變得非常普遍。也就因為如此，在這樣的系統當中，工作排程是一個有挑戰性的問題，如果排程方式不佳，雖然使用較多的處理器，卻反而沒有得到該有的加乘效率。本論文主要研究一些有效率的多重處理器即時排程方法，首先是 EDZL ( Earliest Deadline first until Zero Laxity)，為了改善效率，我們從Zero laxity再推廣到 k 個laxities的情況來分析，並且嘗試以其它的經驗法則來取代EDZL當中的EDF成為主要的排程模組。在本篇論文當中，經由實驗發現EDZL仍是一個很有效率的排程演算法；EDkL並沒辦法增加多少處理器使用率；以其它經驗法則取代EDF的方式表現並不如意；先前已有研究者猜測EDZL的可排程使用率為 ，我們分析一類特殊工作集合的無法排程的特性，以反證法證明 這個猜測是錯誤的；並由分析的過程證明EDZL的可排程使用率無法超過m(1-1/e)；雖然這個可排程使用率的邊界條件不甚理想，不過這種低處理器使用率僅出現在特殊的工作集合，針對一般工作集合來說，EDZL仍是一個實用且有效率的排程演算法。

There has been an increasing demand for real-time scheduling on multiprocessor systems. With the decreasing cost of hardware, multiprocessor architecture becomes more popular nowadays. However, a multiprocessor real-time system may not provide a performance speedup proportional to the number of processors. Choosing a suitable scheduling algorithm is very important in order to get good performance. In this paper, we study some efficient real-time scheduling algorithms for multiprocessor systems. The first is EDZL (Earliest Deadline first until Zero Laxity). Then we extend the cases to the condition of k laxities. We also try to replace the EDF module with other heuristics in EDZL algorithm. We find that EDkL could not improve processor utilization and other heuristics are not good enough as EDF in EDZL. Using a special task set we got from experiments, we disprove the conjecture that the utilization bound of EDZL is 3m/4. Finally, we also get a property that the utilization bound of EDZL is not greater than m(1-1/e) where e is the natural logarithm. Although the bound of EDZL is not ideal enough, EDZL is still an efficient and practical scheduling algorithm for real-time multiprocessor systems.