PRTM (Periodic Real-Time Task Model)
中譯：週期性即時工作模型
週期性即時工作模型(Periodic Real-Time Task Model)又常被稱作週期性工作模型(Periodic Task Model)，它是由Liu與Layland於1973年所提出的週期性即時工作模型(Periodic Real-Time Task Model)[Liu1973]1)。此模型假設一個工作自其初次到達系統後，就會依據其週期時間(Period)反覆到達系統；且每次工作都必須在其截限時間(Deadline)內在處理器上執行不超過其在最差情況下的運算時間(Worst-Case Execution Time，WCET)。若是能順利在截限時間內完成的工作，就被稱為滿足截限時間(Meet Deadline)；相反地，若是無法在時限內完成則被稱為錯失截限時間(Miss Deadline)或是截限時間違反(Deadline Violation)。
此模型將工作定義為在系統中定期反複執行的工作，使用$\mathcal{T}=\{ \tau_1, \tau_2, \cdots, \tau_n \}$來表示一組$n$個週期性的任務(Task)，並使用$A_i$、$T_i$、$C_i$與$D_i$分別代表每個任務$\tau_i$的：
- $A_i$:到達時間(Arrival Time)
- $T_i$:週期(Period)
- $C_i$:最差情況下的執行時間(Worst-Case Execution Time，WCET)
- $D_i$:截限時間(Relative Deadline)
任務可以被視為是用以產生工作(Job)的樣板(Template)，當任務$\tau_i$在時間$A_i$到達系統後，就會立刻產生一個工作(Job，又常被稱為工作實例(Task Instance))，後續每間隔$T_i$時間就會再產生一個新的工作。我們將任務$\tau_i$所產生的第$j$個工作定義為$\tau_{i,j}$，並將其到達系統(也就是被產生的時間)定義為$A_{i,j}$，且可計算為$A_i + (j-1) T_i$；每個工作$\tau_{i,j}$被產生後，被要求在其截限時間前(也就是$A_{i,j} + D_i$)在處理器上執行不超過$C_i$的時間。舉例來說，一個週期性的即時任務$\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$前完成執行(對$\tau_{i,j}$來說，$A_{i,j}+ D_i$也可稱為該工作的絕對截止時間(Absolute Deadline))。依定義，若是一個工作$\tau_{i,j}$順利地在$A_{i,j}+D_i$前完成$C_i$的運算，就被稱為滿足截限時間；相反地，若是無法在時限內完成則被稱為錯失截限時間或是截限時間違反。
應用實例
- 以車用電腦為例，胎壓偵測工作即屬週期性工作任務，假設該任務為$\tau_i$且其可能的參數為$A_i=0$、$T_i=D_i=10s$以及$C_i=2$，那麼就表示自系統啟動起，每間隔10秒就產生一個工作實例，且$\tau_i$的每個工作實例都必須在接下來的10秒內完成不超過2秒的運算處理。
分類
週期性工作模型還可以依據任務的特性分為不同的類別，以下列舉幾個常見的類別：
- 型式良好的任務(Well-Formed Task):絕大多數論文都是考慮此類的任務，其執行時間、截限時間與週期間符合$0\leq C_i \leq D_i \leq T_i$, $\forall \tau_i \in \mathcal{T}$。
- 截限時間受限任務(Constrained-Deadline Task):此類任務的截限時間不大於其週期時間，意即$D_i \leq T_i$, $\forall \tau_i \in \mathcal{T}$。
- 完全截限時間任務(Implicit-Deadline Task):此類任務的截限時間等於其週期時間，意即$D_i = T_i$, $\forall \tau_i \in \mathcal{T}$。
- 長於週期的截限時間(Post-Period Deadline):此類任務的截限時間較其週期時間長，意即$D_i > T_i$, $\forall \tau_i \in \mathcal{T}$。
- 短於週期的截限時間(Pre-Period Deadline):此類任務的截限時間較其週期時間短，意即$D_i < T_i$, $\forall \tau_i \in \mathcal{T}$。