即時系統

在即時系統(Real-Time Systems)裡執行的工作除必須在邏輯上正確外，還必須滿足特定的時間限制(Timing Constraint)，否則將有可能帶來不可彌補的後果，例如一個使用雷達偵測前車距離，並控制車速以保持安全間距的車距調節工作，它被設定為每秒必須執行5次，且每次都必須在200ms 內完成其執行，否則將可能造成車禍事故的發生。

最為相關且最常被使用的工作模型，是由Liu與Layland於1973年所提出的週期性即時工作模型(Periodic Real-Time Task Model)[Liu1973]¹⁾。此模型假設一個工作自其初次到達系統後，就會依據其週期時間(Period)反覆到達系統；且每次工作都必須在其截限時間(Deadline)內在處理器上執行不超過其在最差情況下的運算時間(Worst-Case Execution Time，WCET)。若是能順利在截限時間內完成的工作，就被稱為滿足截限時間(Meet Deadline)；相反地，若是無法在時限內完成則被稱為錯失截限時間(Miss Deadline)或是截限時間違反(Deadline Violation)。

與時效性相關的工作模型還有偶發性工作模型(Sporadic Task Model)[Mok1983]，同樣是用以表達在系統中會反覆執行的工作，但其到達系統的時間並不固定，常用以表示在系統中以特定事件(Event)驅動的工作，例如負責煞車控制的工作並不會固定的執行，而是會等待駕駛踩下煞車的事件發生時，才會執行煞車控制的工作。偶發性工作與週期性工作相同，都必須在其到達系統後，於其截限時間內完成運算；但不同的是，偶發性工作並不會於固定的週期時間到達系統，取而代之的是它使用一個最短間隔時間(Minimum Separation Time)，來規範一個偶發性工作連續到達系統的時間間隔。例如前述的煞車控制工作，可以透過煞車裝置的硬體或是煞車控制軟體設計上的限制，規範出其進行連續兩次煞車動作所必須間隔的時間 – 也就是煞車控制工作的最短間隔時間。由於在最差情況下，一個偶發性工作任務的任意兩個連續的工作，其到達時間的間隔都等於其最短間隔時間，因此本計書後續除特別說明以外，相關內容皆針對週期性工作加以討論，但同時也適用於偶發性工作。除了週期性與偶發性的即時工作模型之外，若是在系統中存在非重複執行的工作，則可以使用非週期性工作模型加以表達[Liu2000]，它同樣必須要在截限時間內完成，但只會到達系統一次，並不會反覆地執行。

不論工作模型為何，即時系統依據是否允許工作錯失截限時間，可區分為硬式(Hard)、軟式(Soft)與嚴格(Firm)即時系統。

• 硬式即時系統(Hard Real-Time Systems): 完全不允許工作錯失截限時間，否則可能會帶來嚴重的後果(例如一個煞車控制工作的執行超出了其截限時間，則可能會造成車禍意外的發生)。
• 軟式即時系統(Soft Real-Time Systems):允許工作在其截限時間後完成，但超過其截限時間後其價值會隨著逾時的時間遞減(例如愈晚傳回的胎壓偵測數據，其參考價值愈低)。大部份軟式即時系統在設計上追求的是儘可能地讓所有工作都能在截限時間內完成，但若有逾時的工作仍會儘可能地將它們完成(因為逾時後仍有價值)。
• 嚴格即時系統(Firm Real-Time System)：與軟式即時系統一樣允許工作的執行超過其截限時間，但超過截限時間後的價值為0。若有逾時的工作，通常會直接將其加以捨棄(反正再繼續執行也沒有任何價值)。

常見的即時系統研究領域的相關工作模型包含以下數個：

1. 週期性工作模型(Periodic Real-Time Task Model)：此模型將工作定義為在系統中定期反複執行的工作，使用$\mathcal{T}=\{ \tau_1, \tau_2, \cdots, \tau_n \}$來表示一組$n$個週期性的任務(Task)，並使用$A_i$、$T_i$、$C_i$與$D_i$分別代表每個任務$\tau_i$的：到達時間(Arrival Time)、週期(Period)、最差情況下的執行時間(Worst-Case Execution Time，WCET)與截限時間(Relative Deadline)。每個任務$\tau_i$可以被視為是用以產生工作(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$的時間。
2. 偶發性工作模型(Sporadic Real-Time Task Model)：此工作模型與週期性即時工作模型同樣是用以表達在系統中會反複執行的工作，使用$A_i$、$T^s_i$、$C_i$與$D_i$分別代表每個任務$\tau_i$的到達時間(Arrival Time)、最短間隔時間(Minimum Separation Time)、最差情況下的執行時間(Worst-Case Execution Time，WCET)與截限時間(Relative Deadline)。偶發性工作與週期性工作相同，都必須在其到達系統後，於其截限時間內完成運算；但不同的是，偶發性工作並不會於固定的週期時間到達系統，取而代之的是它使用一個最短間隔時間(Minimum Separation Time)$T^s_i$，來規範一個偶發性工作$\tau_i$其連續兩次工作實例到達時間的間隔必須大於$T^s_i$。由於在最差情況下，一個偶發性工作任務的任意兩個連續的工作，其到達時間的間隔都等於其最短間隔時間，因此對週期性工作的討論或排程方法，也適用於偶發性工作。
3. 非週期工作模型(Aperiodic Real-Time Task Model)：此工作模型同樣具有必須在截限時間內完成工作執行的要求，但不會重複地產生工作實例。我們可以使用$A_i$、$C_i$與$D_i$來定義一個非週期性工作$\tau_i$，它會於時間$A_i$到達系統，並要求在時間 $D_i$內在處理器上執行不超過$C_i$的運算時間。

不論一個工作$\tau_i$屬於上述的哪一種工作模型，其執行若無法在所要求的截限時間$D_i$內完成$C_i$的運算時，就被稱為是「錯失截限時間(Miss Deadline)」或「截限時間違反(Deadline Violation)」；相反地，如果可以在截限時間內完成工作，則稱為「滿足截限時間(Meet Deadline)」或是「滿足時間限制(Meet Timing Constraints)」。

綜關相關文獻，即時系統的工作排程方法都是可搶先(Preemptive)的優先權驅動(Priority-Driven)的方法為之 — 工作排程方法還可依據工作在執行時是否可被其它工作搶先，區分為可搶先(Preemptive)與不可搶先(Non-Preemptible)兩類。綜觀相關文獻，大部份論文所提出的方法皆為可搶先的排程方法。

除此之外，我們可以還可以再進一步將工作排程方法區分為固定優先權(Fixed Priority)與動態優先權(Dynamic Priority)兩類。固定優先權的排程方法是在系統運行前，事先給定每個任務$\tau_i$一個固定的優先權$P_i$，所有$\tau_i$依週期所產生的工作實例$\tau_{i,j}$都會使用此優先權$P_i$；至於動態優先權的方法，則是在系統開始運行後，依據工作實例$\tau_{i,j}$產生時系統當時的況狀來決定其優先權，同一任務的不同工作實例將可能以不同的優先權運作。本節後續將分別針對採用固定優先權(Fixed Priority)與動態優先權(Dynamic Priority)的即時工作排程方法彙整其相關研究成果。

• Rate Monotonic (RM)[Liu1973]：以工作的週期做為優先權給定的基礎，週期較短的工作將擁有較高的優先權，為最佳的固定優先權排程方法²⁾。

• Earliest Deadline First (EDF)[Liu1973]：在系統運行時，依據工作距其截限時間的遠近，動態地給定優先權(距截限時間較急迫的工作實例，其優先權較高)。為最佳的動態優先權排程方法。

前述的工作排程方法，所考慮的都是獨立性的工作(Independent Task)，也就是工作的執行除了處理器之外不需要任何其它的資源；然而在真實應用中的工作大部分都是相依性工作(Dependent Task)，意即工作除了必須競爭處理器之外，還需要存取系統中的共享資源(Shared Resource)。為了確保共享資源被多個工作使用時，仍能保持其資料的一致性(Data Consistency)，通常會使用鎖(Lock)³⁾做為同步機制，讓工作以互斥的方式使用共享資源。具體來說，為了確保資料的一致性，當一個工作$\tau_i$要存取一個共享資源$R_j$時，它必須先將$R_j$加以鎖定(若$R_j$沒有被其它工作鎖定使用中)才能夠開始使用該資源；待其使用完後，$R_j$的鎖也才會被加以釋放。與此同時，若是其它工作也想要使用正在被鎖定使用中的共享資源的話，就必須等待$\tau_i$完成其使用並將它釋放才行。因此多個工作如若需要存取同一個共享資源時，則會是以互斥的方式進行存取。然而互斥存取也帶來了優先權倒置(Priority Inversion)、連鎖式阻擋(Chained Blocking)與遞移阻擋(Transitive Blcoking)，甚至是死結(Deadlock)等異常現象。學者們先後提出了許多設計良好的即時工作同步方法來避免或降低這些異常現象發生的次數或是其所帶來的影響，其中以應用在單處理器系統的Priority Ceiling Protocol (PCP)[Sha1990]以及Stack Resource Policy (SRP)[Baker1990]最為著名。

當考慮多處理器或多核心系統時，其相關的即時同步方法較單處理器更為複雜與困難。舉例來說，在單處理器的情況下，高優先權的工作不可能被較晚到達系統的低優先權工作所阻擋，其原因在於較晚到達系統的低優先權工作不可能搶先高優先權的工作；但在使用多核心處理器的情況下，較晚抵達系統的低優先權工作，卻有可能在其它處理器核心上執行，若是它比高優先權的工作更早開始鎖定資源，則高優先權的工作就有可能被它加以阻擋，此情況為多核心處理器的同步方法設計帶來更多的挑戰。此方面的研究成果在Partitioned Scheduling方面，以英國約克大學的即時系統研究群所提出的MrsP[BurnsWellings2013]以及美國UNC的研究團隊所提出的FMLP[Block2007]最受到重視。另外還有MPCP[Rajkumar1990]、MSRP[Gai2001]等方法。

至於配合Global Scheduling方法的FMLP[Block2007]、P-PCP[Easwaran2009]、OMLP[Easwaran2011]與LB-PCP[Macariu2011]等同步方法。另外亦有學者針對Semi-Partitioned Scheduling方法提出MLPS[Afshar2012]與NMLPS方法[Afshar2012]等方法，以及Brandenburg等學者針對Clustered Scheduling的排程方法，將FMLP方法修改為可應用至C-EDF方法[Calandrino2007]的FMLP$^+$[Brandenburg2014]方法。

這裡要查一下FMLP到底是partitioned還是global?

bibtex file