On-line Scheduling in Real-Time Multiprocessor Systems

淡江大學機構典藏 > 商管學院 > 資訊管理學系暨研究所 > 學位論文 > Item 987654321/75639

Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/75639

Title:	On-line Scheduling in Real-Time Multiprocessor Systems
Other Titles:	多核心即時系統上的線上排程問題研究
Authors:	衛信文;Wei, Hsin-wen
Contributors:	淡江大學資訊管理學系
Keywords:	線上排程演算法;可排程率分析;即時系統;多核心系統;on-line scheduling algorithm;schedulability analysis;real-time system;multiprocessor system
Date:	2008
Issue Date:	2012-04-05 13:09:10 (UTC+8)
Publisher:	新竹市：清華大學資訊工程學系
Abstract:	近年來，隨著許多著重於計算能力的應用程式紛紛朝向多核心平台架構發展，使得多核心即時系統上的線上排程(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演算法排程時所需要配置的核心資源。根據分析配置給作業的核心資源，我們可以找出更好的可排程率下限。而我們所提出的可排程率下限相較於之前的結果更為接近可排程率上限。
Appears in Collections:	[資訊管理學系暨研究所] 學位論文

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	197	View/Open
摘要.pdf	95Kb	Adobe PDF	51	View/Open
目錄.pdf	70Kb	Adobe PDF	31	View/Open

Loading...