在異質多處理器上針對即時系統具有容錯能力之動態排程演算法

Abstract

即時系統已經廣泛地被應用在許多需要嚴格地符合時間要求的環境中。在即時系統中的工作必須在時間限制內完成，否則可能造成嚴重的後果。由於對穩定性的高度要求，容錯能力也是即時系統所必須具備的。由於工作在進入系統後才能開始被排程，因此需要的是動態的排程演算法。本論文即是提出一個在異質多處理器上針對即時系統具有容錯能力的動態排程演算法。我們將會提出一個以工作可排程的時間與所需要的執行時間作為考量的heuristic函式，來決定工作排程的優先順序。針對為達到容錯目的所用的backup，我們也提出新的排程策略，稱為MNO。經由動態地模擬一個即時系統，結果顯示我們提出的方法能夠決定出更恰當的排程順序，而且挪出更多的可排程時間給後來的工作，使得較多的工作能夠在時間限制前完成執行。並且在不同的環境中，不需要搭配任何參數也能得到較好的結果。

Real-time systems are being increasingly used in several applications which are time critical. Tasks corresponding to these applications have deadlines to be met. Fault-tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. In this thesis, we propose an algorithm do dynamically schedule arriving real-time tasks with PB fault-tolerant requirement on to a set of heterogeneous multiprocessor. Our algorithm, named density first with minimum non-overlap scheduling algorithm (DNA), proposes two performance improving techniques. First, a new heuristic function, called density, takes account of the needed computation time and schedulable time of a task. The task with the maximum density value will be given the highest priority. Second, the MNO strategy for backup scheduling will minimize the time reserved for backups. In the result of dynamic simulation, we can find that our algorithm has fewer rejected tasks and more general and suitable for any kind of environment.