實時系統模型

一個實時系統模型由三個部分組成，調度與資源訪問控制、處理器和資源等，實時系統與通用作業系統不同，實時系統是套用在某個具體的場合中，且實時系統的任務必須在時限內完成。實時系統的設計就是要採用合適的任務調度算法，保證任務在時限內完成，而不論是否發生其他事情。實時系統注重的是個體表現，更準確地講是個體最壞情況表現，即在最壞情況下也要保證個體的處理在其時限內完成。

基本介紹

• 中文名：實時系統模型
• 外文名：real-time system modeling
• 所屬問題：數位訊號處理器
• 相關概念：實時系統、調度、定時約束等

基本介紹

一個實時系統模型由三個部分組成，如圖1所示。任務圖位於圖的上面部分，它給出了任務的執行時間、資源需求、定時約束和任務之間的依賴關係。下面部分是資源圖，描述資源的數量和屬性，以及使用資源的規則。在中間是作業系統使用的調度和資源訪問控制算法。注意，圖中給出的是簡化了的模型，有些參數和關係沒有詳細表示出。

圖1 實時系統模型

實時系統的可預測性

實時系統的可預測性包含兩個方面：第一個方面是指任務處理在沒有被打斷的情況下的執行時間可預測，主要指任務的最長處理時間是可預測的；第二個方面是指實時系統在多任務調度、資源分配和需要中斷服務的情況下，各任務保證在時限內完成處理。實時系統採用各種算法和策略，始終保證系統行為的可預測性(predictability)。可預測的系統可靠性更高。

通用作業系統的設計注重多個任務的平均表現性能，儘量縮短系統的平均回響時間和提高系統的吞吐率，在單位時間內為儘可能多的用戶請求提供服務。

實時系統與通用作業系統不同，實時系統是套用在某個具體的場合中，且實時系統的任務必須在時限內完成。實時系統的設計就是要採用合適的任務調度算法，保證任務在時限內完成，而不論是否發生其他事情。實時系統注重的是個體表現，更準確地講是個體最壞情況表現，即在最壞情況下也要保證個體的處理在其時限內完成。

一切導致系統不可預測的因素都是實時系統設計者所不期望的，比如Cache的使用。Cache在通用計算機中的使用很普遍，它能有效地減少存儲器存取的時間，以增加系統的平均吞吐率。Cache分配算法之一就是當前執行的任務完全占有整個Cache，這種方法使Cache的命中率很高，從而減少了存取數據的時間。在通用計算機系統中，這是一種常用的方法。但是，對於實時系統的設計者來說，這種方法導致了任務執行時間不可預測。下面舉一個例子說明。

已知任務A在未被其他任務打斷時的執行時間為 。當A在執行過程中，一個高優先權的任務B就緒了，系統就會中斷A，然後轉為執行B，這時A已經執行的時間有 。B執行完後，系統轉回A被打斷處繼續執行，直到完成A，這時任務A又被執行了 長的時間。 一定等於 嗎?不一定!因為當任務B執行時，Cache中A的一些存儲塊會被B所替換。當A繼續執行並存取被替換的Cache塊時，就會發生Cache失效(miss)，所以就會用更長的時間存取數據。如果沒有B任務，就不會有這種Cache失效發生。因此 一般會大於 。在有Cache的系統中，A任務的執行時間就與A被搶占的次數有關和每次搶占後Cache被替換的狀態有關。實時系統在計算所有任務是否滿足各自的時限時，事先知道任務的確切執行時間是很重要的。Cache使任務的執行時間不可預測，所以對於實時系統來講，要合理管理Cache，使用Cache凍結、旁路等模式。

實時系統任務的分類

實時系統的任務有兩種分類方法：第一種是根據任務到達時間是否可預測來分類；第二種是根據任務沒有在時限內處理完而所造成後果的嚴重程度來分類。

根據第一種分類方法，可以把實時系統的任務分為周期任務和非周期任務。

●實時系統中有很多任務被重複地執行。例如，在飛機上，感測器要每隔100ms對飛機的速度、高度和姿態等參數進行採集。這些感測器採集的信息送到實時控制計算機中，作為周期任務的輸入參數。這些周期任務調整飛機的副翼、方向舵等控制面，以保持飛機的穩定。周期任務是設計者已知的，所以這類任務的調度方法可以預先設定。

●除周期任務外的其他任務是偶爾出現的，兩次任務的釋放時間間隔服從某種機率分布。例如，飛行員需要飛機轉彎，一系列相關任務會被執行。非周期任務是不可預測的，系統必須保留足夠的時間來執行這些任務。非周期任務中，必須在嚴格的時限內完成的任務又稱為偶發(sporadic)任務。

根據第二種分類方法，可以把實時系統的任務分為關鍵(critical)任務和非關鍵任務。

●關鍵任務需要在時限內完成，否則後果會很嚴重，例如，飛機的穩定控制系統。但是，關鍵任務的發生頻率可能過高，並不需要每次發生都需要成功地執行。比如，一個關鍵的周期任務每發生n次，只需要執行完一次就可以保證系統的正常。

●非關鍵實時(或稱為軟實時)任務對系統的重要程度較低。非關鍵任務處理的數據常常是隨時間變化的，所以如果沒有在時限內完成非關鍵任務，它們就沒有價值。調度非關鍵任務的目標就是儘量提高非關鍵任務完成的百分比。

實時系統的模型

系統資源、處理器和資源

系統資源分為兩大類：處理器和資源。

這裡所指的“處理器”是抽象的，包括CPU、磁碟、網路鏈路和資料庫伺服器等具有計算、檢索和傳輸功能的部件。處理器執行機器指令、搬移數據、檢索檔案和處理查詢。每個任務的執行必須擁有一個或多個處理器。處理器又常被稱作伺服器和主動資源。如果兩個處理器功能是一樣的並且可以交換使用，就可以認為它們是同一類型。

“資源”一詞專指被動資源，如記憶體、互斥量和資源鎖。任務執行除了需要處理器外，還需要一些資源。資源在使用的過程中不會被消耗掉，所以資源是可重用的。如果某種資源是豐富的，總是能被任務得到，它就不會在實時系統模型中出現，這樣做的目的是為了簡化模型。

實時系統任務的參數

一個任務可以由其時間參數、功能參數、資源參數和互聯參數來表征。時間參數說明了任務的定時約束和行為，如時限和釋放時間。功能參數說明任務的內在屬性，如價值函式和可搶占性(可搶占性指任務執行時可以被其他任務搶占)。資源參數說明任務的資源需求。互聯參數描述任務如何依賴於其他任務以及其他操作如何依賴於它。

定時約束

定時約束：執行時間、釋放時間、回響時間、絕對時限、相對時限

任務的執行時間是指任務單獨執行並擁有所有它需要的資源時，完成任務的執行所需要的時間量。任務執行時間可能在 之間變化，一般我們所指的任務執行時間是 。

任務的釋放時間又稱為到達時間，它是一個時刻，在這個時刻上，任務能夠執行。從釋放時間開始，只要任務所需的數據或其他條件得到滿足，就可以被調度和執行。

任務的回響時間是指任務的釋放時間到完成時間的時間長度。

任務的相對時限是指任務的最大允許回響時問。

任務的時限是一個時刻，要求任務在此時刻之間完成它的執行。任務的時限也稱為絕對時限。任務的絕對時限等於釋放時間加上其相對時限。

下面舉一個例子說明。一個實時系統中有一個中斷，其發生的周期是100ms，這箇中斷在(20+100×k)ms等時刻發生，其中k為自然數。中斷服務程式(即任務)的執行時間為60ms。

①任務的釋放時間(時刻)：20ms，120ms，220ms…

②任務的執行時間(一段時間)：60ms

③任務的絕對時限(時刻)：120ms，220ms，320ms…

④任務的相對時限(一段時間)：100ms

⑤任務的回響時間(一段時間)：[60ms，100ms]，任務的回響時間可以是變化的。

周期任務的模型

周期任務指釋放時間間隔是一個常數的任務。任務的釋放時間和執行時間的抖動會影響周期任務模型的準確程度。

假設系統中有n個任務： ，各個任務的周期對應為 。H為所有任務周期的最低公倍數，稱H為系統的超周期(hyperperiod)。每個超周期中執行的

H任務個數為 。任務的利用率 定義為任務的執行時間和周期的比值，即 。系統各任務利用率的總合稱為總利用率，用U表示。

舉一個例子：某實時系統中有3個周期任務，其周期分別為3、4和10，對應的執行時間分別為1、1和3，則系統的超周期為60，每個超周期中執行的任務數為41，各任務的利用率為0．33、0．25和0．3，系統總利用率為0.88。這個系統的處理器在88%的時間內處理任務。

執行次序圖(precedence graph)

任務間的數據的相關性和控制的相關性可能限制任務的執行次序。如果要按照某種次序執行任務，則稱任務具有“優先約束(precedence constraints)”。否則，如果任務可以按照任意次序執行，則稱它們是獨立的。

這裡採用符號“<”來說明任務之間的先後約束關係。如果任務 必須在任務 完成之後才能執行，則稱 為 的“先趨”， 是 的“後繼”，並可用符號 表示。如果 ，並且沒有其他任務 使得 ，則稱 為 的“直接先趨”， 是 的“直接後繼”。

可以用執行次序圖表示任務集合T中任務之間的優先約束。圖中的頂點表示一個任務，如果任務 為 的直接先趨，從頂點 到 就有一條有向的邊。圖2為一個有5個任務的實時系統的執行次序圖。

圖2 一個實時系統任務的執行次序圖

從圖中可以得到：

⊄(⊄表示空集)；

如果在執行次序圖的結點標上任務的釋放時間和絕對時限，該圖就被稱為任務圖。表示任務之間的數據依賴關係可用有向的數據相關連線連線任務，以表示任務之間的數據相關關係。數據相關連線的起點是生成數據的任務，數據相關連線的終點是使用數據任務，數據量的大小可標示在數據相關連線上。

功能參數

任務的功能參數會影響調度和資源訪問控制算法，這些功能參數主要有任務的可搶占性、任務的重要程度(criticality)和任務價值函式。

系統中任務常常是交替執行的。調度程式可能掛起一個不是特別緊急的任務，把處理器讓給更緊急的任務執行。如果一個任務的執行在任何時候都可以被掛起，以便讓其他任務執行，隨後又可以在掛起點被恢復執行，就稱此任務是可搶占的(preemptable)。如果一個任務必須從頭執行到尾，中途不能中斷，則稱任務是不可搶占的。之所以有這種限制是因為，如果任務在執行中被掛起並把處理器讓給其他任務，那這個被掛起的任務就必須重新從頭開始執行。有時，一個任務可能在一小段是不可搶占的，比如中斷服務任務，它在開始執行時要保存處理器的狀態，這一段是不可搶占的。

任何系統中，任務都不是同等重要的。某個任務的重要性指明了相對於其他任務來講這個任務有多重要。當系統負荷過重以至於調度不能滿足所有任務的時限要求時，犧牲重要性低的任務是有實際意義的，這樣能使重要性高的任務滿足時限要求。這種系統中，任務的重要性信息就要送給調度程式使用。

資源參數

實時系統資源包括處理器和資源，處理器也可看作是資源的一種。任務的資源參數從套用的角度給出了處理器和資源的部分描述。任務的資源參數包括執行任務的處理器類型、任務需要的每種類型的資源的數量和任務執行時需要某種資源的時間間隔。

如果一種資源的每個單元必須連續使用，則此資源是不可搶占的。換句話說，一旦不可搶占資源的單元被分配給了一個任務，其他需要此資源的任務必須等到這個任務用完以後才能使用該資源。如果任務可以同時使用一種資源中的不同單元，則此資源是可搶占的。

可用資源圖描述資源的配置和資源間的連線關係。資源圖中的一個頂點表示一種資源，頂點的屬性是資源的參數，包括資源的類型和資源的單元數。資源圖中連線資源的邊有兩種：第一種， ，表示 是 的一部分，如計算機資源包含CPU資源和記憶體資源；第二種連線表示資源是可訪問的，如兩台計算機的CPU之間有連線，表示每個CPU都可以被另外的一台計算機訪問。

調度程式和性能

調度程式根據所選擇的一組調度算法和資源訪問控制協定，來對任務進行調度和資源分配。調度程式把處理器分配給任務，也可以反過來說，調度程式把任務分配給處理器。調度程式產生的調度為有效時，需要滿足的條件為：

●任何時候，每個處理器最多只分配給一個任務；

●任何時候，每個任務最多只分配到一個處理器；

●所有任務在釋放之前都沒有被調度；

●根據所使用的調度算法，給每個任務分配的處理器時間之和等於其最大執行時間或實際執行時間；

●所有的優先約束和資源使用約束滿足。

如果所有的任務按照其時限完成，就稱相應的調度程式是可行調度。如果調度程式對某個任務集合總是能產生可行調度，則稱這個任務集合是可調度的。除了可行性準則外，調度程式的其他性能參數包括最大與平均延緩時間(tardiness)、最大與平均延遲時間(lateness)、逾時率(miss rate)、丟失率(loss rate)和無效率(invalid rate)。

①延緩時間是任務的回響時間與其執行時間的差。如果任務在釋放後立即執行，並沒有被其他任務打斷，則延緩時間為0，達到最小延緩時間。

②延遲時間是任務的回響時間與其相對時限的差。和延緩時間不同，延遲時間有負值。當任務的回響時間小於相對時限時，即任務及時完成，延遲時間就是負值。

③逾時率是指已經執行但完成得太晚的任務的百分比。

④丟失率是指被放棄的任務的百分比，也就是根本沒有執行的任務的百分比。

⑤無效率是逾時率和丟失率之和，它給出了任務中沒有產生有效結果的百分比。實時系統希望無效率儘可能小。