具點對點截限時間之即時資源管理

Real-Time Resource Management for End-to-End Deadlines

郭錦福(Chin-Fu Kuo)

指導教授 ： 郭大維

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2005年)

https://doi.org/10.6342/NTU.2005.00211

摘要

近幾年來，隨著軟硬體的進步，有許多現代化的元件導向分散系統，例如相位雷達，已利用商用元件來建構而成，除此之外，許多硬體元件的功能逐漸可以利用軟體模組來實作。這些系統中的工作可以被當成分散式的即時工作，這些工作有點對點截限時間保證需求，以及有執行先後關係限制。在這論文中，我們提出一個有機率效能保證的兩階段排程演算法，另外當考慮到如果沒有工作的完整優先權關係或是執行工作後所獲得的利益值時，我們提出一個階層資源分配架。

我們以元件導向雷達系統當作一個例子來展示我們所提出方法的可行性，我們所提出的方法與以往和資源使用效率有關的演算法或是沒有可排程保證分析方法不同，因為我們對前後端的工作提出了一個聯合的即時排程演算法，這個方法可以作為離線式的機率分析與執行時的許可控制機制。除此之外，我們也發展了一套階層式的資源分配架構，這個方法包含了兩個階段：在離線階段中，這個演算法利用動態程式規劃方法來計算出一些狀態的次佳資源分配方式；而在執行階段，這個演算法利用貪婪方法來找到一個由離線階段所計算出的次佳資源分配方式。除了元件導向雷達系統可以使用我們所提出的想法外，這些想法也適用於許多元件導向分散式系統的設計上。

關鍵字

相位雷達 ； 即時工作排程 ； 機率效能保證 ； 分散式系統 ； 即時資源分配

並列摘要

In recent years, many modern component-oriented distributed
systems, such as phased array radars, are built with commercial-off-the-shelf components, and the functions of many hardware components are also re-implemented by software modules. In such systems, tasks could be modelled as distributed real-time tasks which require end-to-end deadline guarantees and have precedence constraints. In this thesis, we propose a two stage scheduling algorithm with emph{probabilistic timing guarantees}
and a hierarchical emph{resource allocation} framework with no totally ordered importance or numeric utility value for every task.

We take component-oriented radar systems as a case study to
demonstrate the feasibility of our work. Different from most previous work on either algorithms with restrictions in resource utilization or heuristics without analytical ways for schedulability guarantees, we propose a joint real-time scheduling algorithm for both front-end and back-end processor workloads with an analytical framework for off-line probabilistic analysis and on-line admission
control. We also develop a hierarchical resource allocation
framework. This approach consists of two phases: In the off-line phase, the algorithm computes the sub-optimal resource configuration assignments for few workload states by a dynamic programming approach; in the on-line phase, the algorithm computes resource reconfiguration assignments by a greedy approach, provided that sub-optimal resource reconfiguration assignments for several
selected workload states are computed in the off-line phase. Beside component-oriented radar systems, the ideas presented in this thesis could be applied to the designs of many component-oriented distributed systems.

並列關鍵字

Phased-Array Radar ； Real-Time Task Scheduling ； Probabilistic Performance Guarantee ； Distributed Systems ； Real-Time Resource Allocation

參考文獻

[1] L. Abeni and G. Butazzo. QoS guarantee using probabilistic deadlines. In Multiprocessor

EDF and Deadline Monotonic Schedulability Analysisthe IEEE Euromicro Conference

[2] L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems.

In the Proceedings of the 18th IEEE Real Time Systems Symposium, pages 4–13,

December 1998.