在即時多處理器系統上之有效的動態排程演算法

Abstract

在即時系統中的工作，不但要求計算結果正確，而且必須在一定的時限內完成。由於在一個多處理器的即時系統中的工作，如果無法在時限內被正確的被執行並傳回計算結果會導致嚴重的後果，所以具有容錯能力的工作排程演算法是非常重要的。主從模型（Primary Backup model）是一種常用的容錯排程方式。這類的排程法會為工作安排額外的備份，因此系統資源的需求會較大。本論文即是提出了一個動態排程演算法，並使之能夠動態調整備份工作的數量。其目的是為了讓更多的工作在時限內被正確執行並降低系統資源的要求，為此，我們提出了負載回饋的調整機制，依據當前系統的負載程度來決定是不是要安排額外的備份工作。此方法採取的是折衷原則，藉由減少備份工作的安排以達到節省系統資源的目的，並將其用來執行更多的工作，有效提高工作完成比。為了回收並有效利用配置給備份工作的系統資源，我們也提出了一個等候機制，讓工作在佇列中等待系統資源被釋放，直到工作本身的完成時限無法被滿足為止。我們以模擬的方式來評估演算法的效能，結果顯示，在大部分的情況下，我們的方法比其他現有的演算法具有更好的工作完成比，但是容錯的能力會稍微下降。

Real-time systems are defined as those systems in which the correctness of the system depends not only on the logical result of computation, but also on the time at which the results are produced. Task scheduling on real-time multiprocessor systems with fault-tolerant requirements is an important problem due to the catastrophic consequences of not tolerating faults. Primary Backup model is commonly used to schedule real-time tasks with fault-tolerant requirements. In such scheme, redundant copies of tasks are scheduled and more computing resources are required. In this thesis, we propose an effective dynamic scheduling algorithm, named Loading-driven Adaptive Scheduling Algorithm (LASA), which has an adaptive fault-tolerant mechanism to control when redundant (backup) copies of tasks will be scheduled or not. For the purpose of conserving computing resources and achieving higher Guarantee Ratio, the proposed loading-driven adaptation strategy takes the system loading into consideration and makes a trade-off between rejecting tasks and accepting them without backup copies. In order to improve the utilization of reclaimed computing resources from redundant copies, we also propose the task deferment mechanism by adding a waiting queue to the scheduling scheme. A task can be left in the waiting queue until some processors become available or its deadline becomes unable to be met. To evaluate the performance of our proposed algorithm, we have constructed a simulation environment to study it and found that our algorithm outperforms other previous work.