- 學位論文
On-line Scheduling in Real-Time Multiprocessor Systems
多核心即時系統上的線上排程問題研究
摘要
近年來，隨著許多著重於計算能力的應用程式紛紛朝向多核心平台架構發展，使得多核心即時系統上的線上排程(on-line scheduling)問題研究成為主要探討的議題之一。然而，在多核心即時系統上分析線上排程問題相較於在單核心即時系統上來得困難的多，因為一個執行程序(process)在多核心系統的行為模式較於單核心系統上的行為模式來得更為複雜。因此，在此篇論文中，我們著重於研究與分析在多核心即時系統上的線上排程問題，以發掘線上排程演算法的一些良好的特性與找出更合適於多核心系統的線上排程演算法。 對即時系統而言，排程演算法(scheduling algorithm)可以分為兩大類，分別是非優先權導向演算法(non-priority-driven algorithm)與優先權導向演算法(priority-driven algorithm)，我們主要針對這兩種類演算法進行可排程性的討論與分析。在論文的第一個部份，我們首先探討一種非優先權導向演算法，EDZL (Earliest Deadline until Zero Laxity)演算法。EDZL 是一種混合性的演算法，它結合了EDF演算法與LLF演算法的特性，EDZL演算法一開始排程時會按照EDF的排程策略進行一直到有一個工作(job)進入zero laxity的狀態。為了避免這個進入zero laxity狀態的工作無法在期限之內完成，這個工作相對於目前可以執行的工作而言，其優先權會被提高到最高層級。基於EDZL這樣有彈性的排程策略，我們在雙核心的系統上導出其可排程率界限(schedulability bound)為3/2+|umax−1/2|，其中umax代表的是一個作業(task)的利用率(utilization)，而它的值大於所有給定的作業的利用率。為了能夠完整的瞭解EDZL演算法，我們更進一步探索EDZL在排程具有某些限制條件與特殊案例的作業時的一些良好特性。同時我們也對於EDZL的可排程率上限(upper bound)與可排程率下限(lower bound)進行探討，最後，我們探討一種變形的EDZL演算法，稱為EDZL_GCD演算法，並且證明其為最佳的演算法。 在此篇論文的第二個部份，我們研究一種優先權導向的演算法，RM (Rate Monotonic) 演算法，我們著重於全域(global) RM演算法於m 個相同等級核心上的可排程率探討。我們提出一種可以估算一組作業利用RM演算法排程時所需要配置的核心資源。根據分析配置給作業的核心資源，我們可以找出更好的可排程率下限。而我們所提出的可排程率下限相較於之前的結果更為接近可排程率上限。
並列摘要
With the trend toward using multiprocessor systems to handle computing intensive applications, the analysis of on-line scheduling algorithms becomes the main interesting issue for real-time multiprocessor systems in recent decades. However, it is difficult to analyze on-line scheduling algorithms in real-time multiprocessor systems because the behavior of a process in a multiprocessor system is more complicated than that in a single processor system. Therefore, in the dissertation, we study on-line scheduling algorithms to explore some nice properties of on-line scheduling algorithms in real-time multiprocessor systems. The scheduling algorithms for real-time systems can be categorized into two classes: non-priority-driven scheduling algorithm and priority driven scheduling algorithms. We focus on the schedulability issue of a non-priority-driven scheduling algorithm and a priority-driven scheduling algorithm for multiprocessor systems. In the first part of the dissertation, we study a non-priority-driven scheduler: Earliest Deadline until Zero Laxity (EDZL) scheduling algorithm. EDZL algorithm is a hybrid algorithm of Earliest Deadline First (EDF) algorithm and Least Laxity First (LLF) algorithm. A set of tasks scheduled by EDZL algorithm is initially scheduled using EDF algorithm until any job has a zero laxity. To avoid a job from missing its deadline, the priority of the job is immediately promoted to the highest priority among all active jobs. Based on the flexible scheduling policy of EDZL, we derive the schedulability bound of 3/2+|umax–1/2| for two-processor systems, where umax is the maximum utilization of an individual task in the given task set. For a comprehensive analysis of EDZL, we further explore some nice properties of EDZL for task sets with some restricted conditions and provide some special cases for EDZL scheduling algorithm. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions. A variation of EDZL algorithm, called EDZL_GCD algorithm, is also discussed and is proved to be an optimal scheduling algorithm. In the second part of the dissertation, we study a priority-driven scheduler: Rate Monotonic (RM) algorithm. We aims to find the schedulable utilization bound of global RM scheduling algorithm for periodic real-time tasks on m identical processors. A method to estimate the allocation of a set of tasks scheduled by RM algorithm in multiprocessor systems is proposed. Based on the analysis of allocation of the tasks, we present a better utilization lower bound of RM in m processor systems for m >1. Compared with earlier results, the proposed schedulability bound is closer to the upper bound on the achievable schedulability condition of RM.