• RTS領域的第一篇論文
• FP工作最佳排程方法 — RM
• DP工作最佳排程方法 — EDF

即時系統領域自1970年代初期開始發展，其相關學理與技術可為具有嚴格時間限制(timing constraint)的各式系統開發，提供效能保證與可預測性的分析工具。

依據系統設計與建置需求，我們可以選擇適合的工作模型來進行相關的分析與系統設計，常見的即時工作模型如下：

週期性即時工作模型(Periodic Real-Time Task Model)發表於Liu與Layland於1973年所合著的論文 [Liu1973]，是目前最通用且被廣為使用的模型，截至2023年12月為止，該論文已被引用超過14,193次。該模型使用$\mathcal{T}=\{ \tau_1, \tau_2, \cdots, \tau_n \}$來表示一組$n$個週期性的任務(Task)，每個任務$\tau_i$在時間$A_i$到達系統後，就會產生一個該任務的實例(Instance)，稱之為工作(Job)；任務$\tau_i$後續每間隔一段固定的時間就會再產生一個新工作，我們將這段固定的時間稱為週期(period)並將其定義為$T_i$，同時也將$\tau_i$的第$j$個工作(也就是任務實例)定義為$\tau_{i,j}$。¹⁾。每個$\tau_{i,j}$的到達時間可以定義為$A_{i,j}=A_i+(j-1)\times T_i$，並且在到達系統後，必須在其relative deadline(相對截限時間)$D_i$內在處理器上完成$C_i$的運算量(Computation Amount)。舉例來說，一個週期性的即時任務$\tau_i$可以定義為$A_i=2$ms、$T_i=10$ms、$C_i=5$ms以及$D_i=8$ms，也就是說$\tau_i$會自時間$2$ms到達系統，然後每間隔$10$ms就會產生一個必須在$8$ms內完成$5$ms運算量的工作$\tau_{i,j}$；當然，我們也可以說$\tau_{i,j}$必須在時間$A_{i,j}+ D_i$前完成執行\footnote{對$\tau_{i,j}$來說，$A_{i,j}+ D_i$也可稱為該工作的絕對截止時間(Absolute Deadline)。}。

[dijk-cacm-15-859]