基于容錯技術的優先級反轉研究
2008-12-31 00:00:00趙奇索曉冉方琦軍
計算機應用研究 2008年9期
摘 要：優先級反轉是實時系統中出現最多的問題。為了防止這種現象的發生，目前經常采用的方法是優先級繼承和優先級置頂。但是，它們在特定情況下也存在缺陷。容錯技術是提高系統可靠性的重要保障，利用容錯技術對優先級繼承進行擴展，可以更好地解決優先級的反轉問題，保障了系統的實時性能。
關鍵詞：實時系統；優先級反轉；優先級繼承；容錯優先級
中圖分類號：TP16.2 文獻標志碼：A
文章編號：1001-3695(2008)09-2634-03
Research on priority inversion based on faulttolerant
ZHAO Qi，SUO Xiaoran，FANG Qijun
(College of Information Electric Engineering， Hebei University of Engineering， Handan Hebei 056038， China)
Abstract:Priority inversion is the most problem in the realtime system. At present， priority inheritance and priority ceiling are often adopted to prevent the phenomenon of priority inversion. However， the two ways have some disadvantages in a given situation. So faulttolerant is adopted to improve the reliability of the system. This paper expanded priority inheritance based on faulttolerant to allow a better solution to the problem of priority inversion and ensured the realtime performance of the realtime system.
Key words:realtime system; priority inversion; priority inheritance; faulttolerant priority
0 引言
目前實時系統在軍事、經濟、科學等多個領域中起著重要的作用。而絕大多數實時系統都是多任務實時微內核的結構，采用的是基于優先級的可搶占式調度策略。系統為每一個任務分配一個優先權，調度程序保證當前運行的進程是優先權最高的進程。但是，由于多進程共享資源，有時具有最高優先權的進程會被低優先權進程阻塞，反而使具有中等優先權的進程先于高優先權的進程執行，導致系統崩潰。這就是所謂的優先級反轉。目前，普遍采用優先級置頂協議和優先級繼承協議來解決優先級的反轉問題。但是，它們在某種特定條件下也存在不足，這樣會降低系統整體的實時性能。
在實時系統的運行過程中，容錯是最重要的可靠性保障手段。容錯就是系統在出現錯誤的情況下，仍能在規定的時間范圍內提供指定的服務[1]。利用容錯技術來解決優先級的反轉問題，能更有效地提高系統的容錯能力，使系統的性能得到保障。
1 優先級反轉及解決方法
1.1 優先級反轉問題分析
在并發和同步時，避免優先級反轉是實時系統區別于非實時系統的一個主要特征。所謂優先級反轉是指由于資源競爭或同步等原因導致低優先級的任務或者活動先于高優先級任務執行的現象。典型的優先級反轉如圖1所示。
的任務B阻塞了高優先級任務C的執行。優先級反轉會導致系統的可預測性降低。因為在嚴格優先級實時調度中，一個任務只需要等待資源和等待比本身優先級高的任務的執行，即任務等待的時間是可以計算的。但在發生優先級反轉時，任務還需要等待比自己優先級低的活動，這導致等待時間難以預測。所以從實時系統的可預測性要求來講，必須避免優先級反轉的發生。
1.2 優先級反轉的解決方法[2]
目前普遍使用以下兩種方法來解決優先級反轉：
a)優先級繼承協議。優先級繼承的基本思想是當一個任務阻塞了一個或多個高優先級任務時，它便忽略自己的原始優先級分配而以其阻塞的所有任務的最高優先級執行臨界區，使得該任務能盡快釋放出優先級較高的任務所需資源；在退出臨界區后，該任務再返回到其最初的優先級水平。
b）優先級置頂協議。優先級置頂是指系統把每一個臨界資源與一個優先級頂相聯系。當一個任務進入臨界區時，系統便將這個優先級頂傳遞給這個任務，使其優先級最高；當這個任務退出臨界區后系統立即將其優先級恢復正常，從而保證系統不會出現優先級反轉的情況。比較以上兩種方法，對于優先級置頂協議，程序設計者必須靜態地將每個任務以及每個資源都仔細進行考慮，然后選擇適合的優先級頂來對優先級加以保護；如果設計得不好，那么有可能系統存在隱患。而對于優先級繼承協議，實時系統的優先級是惟一的，每個任務只可以有一個優先級，而實時系統任務調度方式是選擇最高優先級任務執行，且只能選擇一個任務。因此，優先級繼承方法需要改寫內核os_task_info數據結構等，并且要將其改寫為支持時間片輪轉的算法，這樣就與實時系統的設計初衷不一樣了，而且其修改將實時系統變成兩個任務可以擁有同一個優先級的方式，會改變整個設計思路。這是該方法的缺點。
2 利用容錯技術擴展優先級繼承協議
2.1 容錯模型定義
定義一個實時任務集合表示任務，是在沒有出現故障時系統調度的主要對象，它可以是周期任務，也可以是軟非周期任務。任務τ義為一個三元組，。任務的執行時間；Di表示任務的最后期限；周期任務的周期，對于軟非周期任務而言，它是任務到來的時間間隔最小值。每個任多個替代任務，而每個替代任務只能對應一個特定容錯處理，所以其計算時間各不相同。本文主要研究任務的最壞響應時間，為了方便分析，假設替代任務中執行時間最長的，其執行時間用均被分配在同一個優先級上執行，因此只需考現故障時，其對應的替期限相等。體響應時間等響應時間和響應時間之和。
對于任務，可以根據某種靜態優先級調度算法 FP(Γ)來分配優先級，如RMS(rate monotonic scheduling)[3]或 DMS(deadline monotonic scheduling)[4]。根據F個任務被分配到各不相同的優先級。下面給出任務優先級定義：
態，執行。
b)只考慮單處理器系統的暫時性軟件故障，所采取的容錯技術可以是恢復塊技術、異常處理或任務的重復執行。一旦任務出現故障，系統將立即調度相應的替代任務進行容錯處理。當替代任務故障時，所采取的容錯技術是重復執行統在任務與之間的調度切換無損耗，而且故障出現時只會影響當前正在執行的任務，對其他任務不會產生任何影響。
c)這里假設容錯模型為故障出現的頻率有上界，即兩個相繼出現的故障之間有最小間隔限制，的一個標準，其值越小，系統的容錯能力就越強。
2.2 優先級繼承協議的擴展
當采取繼承策略時，系統無須額外的容錯調度處理機制，完全按照無容錯需求時所采取的FP(Γ)調度機制來處理容錯，這樣實現起來較為簡單。但是，當系統考慮容錯需求時，任務的響應時間肯定大于或等于無容錯情況下的響應時間，若只是簡單地按照無容錯情況下的處理機制，可能會導致任務無法在截止期限內完成，結果整個系統不可調度，造成嚴重的損害。現在對表 1 中的容錯實時任務集合采取容錯優先級繼承的分配策略。當時，根據式(2)計算所得到的每個任務的最壞響應時間對應的截止期限，則是可調度的；但是當縮小為9
從上面的分析可以得出，在系統采取容錯優先級繼承的分配策略時，當碰到下面的情況時，采取允許容錯優先級提高的分配策略是無法提高系統容錯能力的：最低優先級任務可調度，而處于中間優先級任務不可調度，并且對于不可調度的任務τi來說，在優先級高于pi的任務中，至少存在一個這樣的任務，其替代任務的執行時間比優先級低于pi的所有任務的替代任務執行時間要長。系統容錯能力無法提高的主要原因是由于高優先級任務的容錯優先級高于不可調度任務的優先級造成的，要提高這種情況下系統的容錯能力，可以從降低高優先級任務的容錯優先級的角度來考慮。筆者將從允許容錯優先級降低的分配策略(≤p)來分析如何提高系統的容錯能力。這種分配策略的目的是通過挪用高優先級任務的空閑時間來處理低優先級任務的容錯，以保證出錯的任務滿足截止期限的要求，提高系統的容錯能力。
2.3 可調度性分析
首先分析允許容錯優先級降低對任務響應時間的影響；然后根據這種影響得出任務最壞響應時間的計算公式；最后根據計算公式舉實例說明允許容錯優先級降低的分配策略可以在容錯優先級繼承和提高兩種分配策略無法提高系統容錯能力的情況下，有效地提高系統容錯能力，從而可以更好地解決優先級反轉的問題。
3 結束語
在實時系統中，由于目前經常采用的兩種解決優先級反轉問題的方法都有其缺陷，使系統的可靠性能降低。而容錯技術的特點就是保證系統的可靠性。本文通過利用容錯技術的這個特點來擴展優先級繼承協議，使系統的容錯能力得到提高，從而更好地解決優先級的反轉問題，提高系統的實時性能。
參考文獻：
［1］JAHANIAN F.State restoration in realtime faulttolerant system[C]//Proc of Complex System Engineering Synthesis and Assessment Technology Workshop.1992：21-29.
[2]SHA L，RAJKUMAR R，LEHOCZKY J P.Priority inheritance protocols:an approach to realtime synchronization[J].IEEE Trans on Computers，1990，39(9):11751185.
[3]LIU C L，LAYLAND J W.Scheduling algorithms for multiprogramming in a hard realtime environment[J].Journal of the ACM，1973，20(1): 46-61.
[4]AUDSLEY N C，BURNS A，RICHARDSON M，et al.Hard realtime scheduling: the deadline monotonic approach[C]//Proc of the 8th IEEE Workshop on Realtime Operating Systems and Software.Atlanta: IEEE Computer Society Press，1991:133137.
[5]LIMA G M de A，BURNS A.An optimal fixedpriority assignment algorithm for supporting faulttolerant hard realtime systems[J].IEEE Trans on Computers，2003，52(10):13321346.[6]BURNS A，DAVIS R，PUNNEKKAT S.Feasibility analysis of faulttolerant realtime task sets[C]//Proc of the 8th Euromicro Workshop on Realtime Systems.L’Aquila: IEEE Computer Society Press，1996:29-33.
