ハードリアルタイムタスクへの最適な整数調和周期の割り当て
Assigning Optimal Integer Harmonic Periods to Hard Real Time Tasks
リアルタイムシステムにおいて、各タスクにアプリケーション上限以下の整数の調和周期を割り当てる問題を離散区分最適化として定式化し、最適解を求めるDPHSアルゴリズムを提案した。
著者: Anand Bhat, Ragunathan Rajkumar
分類: eess.SY, cs.PF, cs.RO, cs.SY
原文アブストラクト
Selecting period values for tasks is a very important step in the design process of a real-time system, especially due to the significance of its impact on system schedulability. It is well known that, under RMS, the utilization bound for a harmonic task set is 100%. Also, polynomial-time algorithms have been developed for response-time analysis of harmonic task sets. In practice, the largest acceptable value for the period of a task is determined by the performance and safety requirements of the application. In this paper, we address the problem of assigning harmonic periods to a task set such that every task gets assigned an integer period less than or equal to its application specified upper bound and the task utilization of every task is less than 1. We focus on integer solutions given the discrete nature of time in real-time computer systems. We first express this problem of assigning harmonic periods to a task set as a discrete piecewise optimization problem. We then present the 'Discrete Piecewise Harmonic Search' (DPHS) algorithm that outputs an optimal harmonic task assignment. We then define conditions for a metric to be rational for harmonization. We show that commonly used metrics like, the total percentage error (TPE), total system utilization (TSU), first order error (FOE), and maximum percentage error (MPE), are rational. We next prove that the DPHS algorithm finds the optimal feasible assignment, if one exists, for these rational metrics. We apply the DPHS algorithm to harmonize task sets used in real-world applications to highlight its benefits. We compare the performance of the DPHS algorithm against a brute-force search and find that the DPHS searches up to 94\% fewer task sets than the brute-force search that obtains the optimal solution.
関連論文
- Raspberry Pi 5上のPREEMPT_RT LinuxにおけるUAV飛行制御ワークロードのスケジューリング解析リアルタイムシステム
- 確率的応答時間解析の高速化:修正クリティカルインスタントと最適化畳み込みリアルタイムシステム
- 市販部品ベースのリアルタイムシステムにおけるミドルウェア透過的なコールバック実行リアルタイムシステム
- ROS 2マルチスレッド実行器のタイミング解析と優先度駆動型拡張リアルタイムシステム
- ROS 2と古典的リアルタイムスケジューリングの橋渡し:周期タスクへの適用リアルタイムシステム
- PAAM: ROS 2における協調的かつ優先度駆動型アクセラレータ管理フレームワークリアルタイムシステム
