HSM：應用於動態負載平衡之基於工作竊取演算法的分層排程機制

Abstract

有鑑於單一電腦系統的處理器數目日益增加，作業系統需要調整原有的排程器，抑 或是開發一個新的排程演算法，方能有效率地發揮多處理器系統的效能。在這篇論文 裡，我們提出一個分層排程機制，使用全域排程器及本地排程器，其中，全域排程器 用來維持每個週期性工作的狀態，並將可執行的工作平均分給多個處理器；本地排程 器則是用來分配處理器的資源，以及將執行的結果回饋給全域排程器。在我們所提的 分層排程器中，全域排程器以最差符合法為基礎，逐步地將全部的工作分給每一個處 理器。雖然總負載不盡相同，但每個處理器會分配到幾乎等數量的工作。當系統瀕臨 滿載甚至是過載的情況，全域排程器會改變分配的分法，藉由放棄負載較高的工作來 使得每個處理器的總負載不會超過其負荷。至於本地排程器則隸屬於每個處理器，依 據處理器的計算資源，確認工作的適宜性。當本地排程器發現其處理器負載過高而無 法勝任工作時，會將負載過重的資訊回饋於 f_Byte，要求全域排程器重新規劃工作。 在下個週期性工作到來的時候，全域排程器會重新將該工作分配給更適合的處理器來 執行。藉由 f_Byte 的回饋，本論文所提出的分層排程機制，可以有效地減少啟動全域 排程器的頻率，只有在動態負載不平衡的時後，才會啟動全域排程器重新規劃工作的 分配。在本論文中，我們設計三個實驗，分別探討分層排程器在不同負載（週期性工 作、非週期性工作）、不同臨界參數下的表現。實驗結果證明處理週期性工作時，分層 排程器在中低負載皆有較好的表現，改善率保持在 20% 到 64% 之間，而在高負載情況 下，分層排程器能讓更多的工作在時間內完成。相較於週期性工作，處理非週期性工 作時，分層排程器雖然在低負載的表現較不突出，但在中高負載的表現皆優於在處理 週期性工作時的結果。最後，我們的實驗也證明，分層排程機制能依據處理器計算資 源的多寡，導出適當的臨界參數，以減少該系統因啟動分層排程機制而產生的不必要 的資源耗費。

Along with the growing number of processors in personal computers, operating systems need to modify original schedulers to effectively schedule tasks in a multi-processor system. In this thesis, we design a hierarchical scheduling mechanism which is composed of a global scheduler and several local schedulers. The global scheduler is used for maintaining the state of tasks and assigning ready tasks to processors in balance. The local scheduler is responsible for evaluating processor’s resource and updating f_Byte to feedback the local status to the global scheduler. A global assigning algorithm based on the worst-fit algorithm is used to assign tasks in phases. In each phase, the global scheduler assigns a task to every processor. The global assigning algo- rithm changes the sorting principle when the system is overloaded and abandons the tasks with heavy loads. Therefore, each task set assigned to a processor is schedulable. Each processor has a local scheduler to verify whether the assigned tasks are proper for the processor based on pro- cessor’s computing resource. The local scheduler updates f_Byte to feedback the local status to the global scheduler, and requests for reassigning tasks in the next scheduling period. In this thesis, we design three experiments to explore the performance of the hierarchical scheduling mechanism in different loadings (periodic tasks, aperiodic tasks) and different thresholds. The experimental results show that the hierarchical scheduling mechanism has a good performance in light and normal loadings, and the improvement rate is between 20% and 64%, while in the high-loading case, the hierarchical scheduling mechanism makes more tasks completed in time. Comparatively, the performance of the hierarchical scheduling mechanism is better for aperi- odic tasks than for periodic tasks, if system loads are high or normal. Finally, our experiments also show that the hierarchical scheduling mechanism can derive appropriate thresholds based on the processor’s computing resources to reduce the unnecessary overhead producing by the hierarchical scheduling mechanism.