实时系统-调度算法和可调度分析
第二章 Scheduler
調度:在有限的一組處理單元上決定具有某些已知特征(周期性、持續時間/執行時間/計算時間)的一組任務的順序和/或執行時間。這些單元具有給定的能力(容量、處理速度),并且在每個任務的完成時間和處理單元的使用上受到一組約束。
Work-conserving scheduling:在每一時刻,優先級與每個活動作業相關聯,并且可以執行的最高優先級作業被選擇在可用處理器上執行。當活動作業存在時,處理器永遠不會處于空閑狀態(除非遷移約束阻止任務在空閑處理器上執行,分區調度/自掛起?)
在過去:每個任務有專用的處理器,只需要保證任務在deadline之前執行完成即刻,不是實時系統RTOS
而現在 :一個處理器上有多個任務,需要調度保證每個任務滿足deadline
如果所有任務都可以根據一組指定的約束完成,則稱該調度(schedule)是**可行(feasible)**的。
如果存在至少一個算法可以產生一個可行的調度,則這一組任務被稱為**可調度(schedulable)**的,
一些非實時調度算法(可以用做實時調度算法的一部分):
- FIFO,先進先出
- LIFO,后進先出
- SETF,最短執行時間優先
- LETF,最長執行時間優先
一些定義:
Arrival time/release time :一個任務到達,可以被執行的時間點.
Computation time cic_ici? :處理器在沒有被打斷的情況下,執行一個任務所必需的時間
Deadline did_idi?:一個任務需要被完成的時間點
Start time: 任務開始被執行的時間點
Finishing time fif_ifi?: 任務執行完成的時間點
Lateness(Li):Li=fi?diLateness (L_i): L_i=f_i- d_iLateness(Li?):Li?=fi??di?, 代表一個任務被完成時相對于deadline的時間長度,如果是在deadline前完成,他的延遲是負數。
Tardinessorexceedingtime(Ei):Ei=max(0,Li)Tardiness\ or \ exceeding\ time (E_i): E_i=max(0,Li)Tardiness?or?exceeding?time(Ei?):Ei?=max(0,Li), 一個任務在結束時間之后仍然活躍的時間長度
LaxityorSlacktime(Xi):Xi=(di)fi?ai?CiLaxity\ or\ Slack time (X_i): X_i=(d_i)\ f_i-a_i-C_iLaxity?or?Slacktime(Xi?):Xi?=(di?)?fi??ai??Ci? 是任務在激活時可以延遲(或被其他任務搶占)以在截止日期內完成的最長時間。
Response time 完成一個任務所需要的時間.$ R_i=F_i-r_i.$ 也可以是被高優先級任務搶占的時間和計算時間Ri=Ii+CiR_i=I_i+C_iRi?=Ii?+Ci?相加
Average response time平均響應時間:1n∑i=1n(Ri)\frac{1}{n}\sum^n_{i=1}(R_i)n1?∑i=1n?(Ri?) ,其實就是n個任務的響應時間求個平均值。
全部完成時間 total completion time : max?fi?min?ri\max{f_i}-\min{r_i}maxfi??minri? ,最后被完成的任務的結束時間減去最早到的任務的開始時間。
Maximum Lateness 最大延遲時間 :Lmax=max?ifi?diL_{max}=\max_i{f_i-d_i}Lmax?=maxi?fi??di? 所有任務中延遲時間最大的任務的延遲時間。
Maximum Number of Late tasks :Nlate=∑inmiss(fi)miss(fi)=0iffi≤dielse1N_{late}=\sum^n_imiss(f_i)\\miss(f_i)=0 \ if\ f_i \ \le d_i\ else\ 1Nlate?=∑in?miss(fi?)miss(fi?)=0?if?fi??≤di??else?1說白了就是這個調度會讓多少任務的結束時間超過截止期限。
圖之間的優先關系可以通過非循環有向圖(對于WCET最壞執行時間,控制流圖,CFG)來描述,其中任務由節點表示,優先關系由箭頭表示。CFG在任務集上誘導一個偏序。
這個圖可以有不同的解釋,激活當前任務的所有后續任務(并發任務執行)。激活任務的一個后續任務(非確定性選擇)。
實時系統可以分為硬實時和軟實時系統,都是盡力在ddl之前完成任務,但是根據沒按時完成的后果,嚴重的是硬實時,沒有嚴重后果的是軟實時。
調度算法可以按幾種標準分成如下三類
1.Time-Triggered (TT) scheduling 時間觸發調度
- 也稱為:時鐘驅動調度
- 所有任務調用時間都是離線計算的,并存儲在表中
- 運行時分派是一種簡單的表查找。示例:靜態循環調度Static cyclic scheduling
? Event-Triggered scheduling 事件觸發調度,這也是這門課關注的部分
- 進程的時間表由外部中斷的發生決定
- 固定優先級調度
- 動態優先級調度
2.Fixed/Static priority scheduling 固定/靜態優先級調度
Dynamic priority scheduling 動態優先級調度
3.Preemptive scheduling 可搶占式調度
non-preemptive scheduling 不可搶占式調度
接下來介紹非搶占式調度
對于每個事件,都有一個將要執行的相應流程。事件由(a)外部中斷和(b)進程本身發出。在隊列中收集事件;根據排隊規則,選擇一個事件來運行。
進程不能被中斷。
如果事件隊列為空(例如空閑任務),后臺進程可以運行(并被搶占!)。定時事件僅在經過一段時間間隔后才進入隊列。
上圖這個進程是是CPU的運行簡單版本,當事務隊列是空的時候,CPU進入低電休眠;否則從事務隊列抓取事務,并且執行事務對應的進程。
非搶占式調度的屬性
進程之間的通信是簡單的(共享資源不會產生問題),但是中斷可能引發問題。
如果環境或進程生成太多事務,會造成緩存溢出,當很長的進程阻止了其他的進程運行也會造成緩存溢出(事務隊列放不下了)。解決方法也很簡單,把長進程劃分的更小,局部上下文保存(?)。
Co-operative Multitasking 協作多任務
每個進程允許上下文切換當 cswitch() 函數被調用. 單獨的調度程序來選擇下一個運行的進程。
優點
- 知道哪里發生了上下文切換
- 共享資源更少出錯
缺點
- 編程錯誤可以阻止其他線程,線程永遠不會放棄CPU。(很簡單的一點大概就是沒寫cswitch?)
- 如果在允許上下文切換之前花費太長時間,則實時行為將面臨風險。(就是從線程執行的時候開始到cswitch很久?)
Preemptive Scheduling – Stack Policy 可搶占式任務,棧策略
和非搶占式的情況很像,但是進程可以被其他進程搶占,這解決了長任務的部分問題。
如果搶占順序受到限制,我們可以使用通常的基于堆棧的函數調用上下文機制(進程=函數)。
進程必須按照其實例的后進先出順序LIFO完成。
- 限制靈活性
- 如果多個進程等待外部事件的時間未知,則不實用
共享資源(進程之間的通信!)必須加以保護,例如:禁用中斷、使用信號量。
箭頭所指向的地方就發生了搶占,T2搶占T1, T3搶占T2。
Preemptive Multitasking
由操作系統決定何時進行上下文切換,以及下一個進程是誰。使用timer去調用操作系統和切換上下文。使用硬件或者軟件中斷,或者直接調用操作系統去切換上下文。
控制流圖 像下圖
Static cyclic scheduling
- 所有任務調用時間都是離線計算的,并存儲在表中
- 運行時分派是一種簡單的表查找
Round-Robin scheduling
- 每個作業準備好執行時都會加入一個先進先出(隊列)
- 隊列頭部的作業最多執行一個時間片。無論作業是否完成,它都將被搶占并放置在隊列的末尾
- 用于調度分時應用程序
- 常用于臺式計算機系統
- 也稱為處理器共享算法
- 常用于服務器集群的負載平衡
Weighted Round-Robin scheduling
- 不同的作業可能有不同的權重,而不是給每個作業相同的時間片。作業的權重是指分配給作業的處理器時間的分數
- 具體地說,一個作業的權重為每輪wtw_twt?時間片,一輪的長度等于所有就緒作業的權重之和
- 已被用于高速交換網絡中的實時流量調度。
Static/Fixed priority scheduling
- 每個任務都有一個固定的優先級
- 運行時間分配是基于優先級的
- 可以是搶占式,也可以是非搶占式
Dynamic priority scheduling
- 任務優先級在運行時動態分配
- 總是使用復雜的算法來確定每個任務/作業的優先級
例如,最早截止日期優先(EDF)
Cyclic Executive Scheduling 循環執行調度
- 執行時間線是一個無限長的超周期序列。
- 同一調度在每個超時段執行一次。
- 計劃是脫機設計的,并存儲在表中。
- 運行時任務分派是簡單的表查找。
屬性:
- 可預測
- 低運行時開銷
缺陷:
如果任務周期相對較短,任務表可能會變得非常大。維護噩夢?Maintenance nightmare
未廣泛使用除了某些安全關鍵系統。
簡單的周期性時間觸發調度
每隔一個周期P,從時間t(0)開始,timer都會到期,然后從頭開始執行進程表。
時間觸發的循環執行調度
P被劃分成了很多個幀f,每個幀的開頭都有一個任務被釋放。
通用時間觸發調度器
這個圖 就是 0時刻執行T1,3時刻執行T2,7時刻執行T1。。。12時刻執行T2
Event Triggered Scheduling
-
Aperiodic Task Sets 非周期任務集
-
Periodic Task Sets 定期任務集
-
**Mixed Aperiodic and Periodic Task Sets **混合非周期和周期任務集
具有實時約束的非周期任務調度
| 獨立任務集 | EDD(Jackson) | EDF(Horn) |
| 非獨立任務集 | LDF(Lawler) | EDF*(Chetto) |
EDD Earliest Deadline Due最早期限到期
給定一組n個任務。在最小化最大延遲方面(min?(maximumlateness)\min({maximum\ lateness)}min(maximum?lateness)),誰的截止期在前面就先調度誰,這么做是最優的。
證明:
圖畫的不太好,不妨假設f2′?f1=2≤d2?d1=1f_2'-f_1 =2\ \le d_2-d_1=1f2′??f1?=2?≤d2??d1?=1
第一個調度序列中$f_1-d_1\ \le \ f_2-\ d_2 $ Lmax1=f2?d2L^1_{max}=f_2-d_2Lmax1?=f2??d2?
第二個調度序列中 f2′?d2≤f1′?d1f_2'-d_2 \le f1'-d_1f2′??d2?≤f1′?d1? Lmax2=f1′?d1L_{max}^2=f_1'-d_1Lmax2?=f1′??d1?
所以Lmax1?Lmax2=f2?f1′?(d2?d1)≤0L^1_{max}-L^2_{max}=f_2-f_1'-(d_2-d_1)\le0Lmax1??Lmax2?=f2??f1′??(d2??d1?)≤0
所以確實是先調度截止期在前頭的。
例子:
d1?>d5?>d3?>d4?>d2d_1->d_5->d_3->d_4->d_2d1??>d5??>d3??>d4??>d2?
**EDF Earliest Deadline First **
執行已經arrive了的任務中,截止期最前的就行。
證明:對于每個時間間隔[t,t+1),驗證實際運行的任務是否是具有最早絕對截止日期的任務。如果不是這樣,則在該時間間隔內執行具有最早絕對截止日期的任務。此操作不能增加最大延遲。
引入一些變量和術語
σ(t)\sigma(t)σ(t)表示這個任務在片段[t,t+1)中執行
E(t)E(t)E(t)表明這個準備了的任務,在時間t是有最早截止時間的。
tE(t)tE(t)tE(t)是在當前調度中,任務E(t)E(t)E(t)什么時候開始執行的時間片。
這是相同的兩個任務集,上面不知道用了什么算法,下面是EDF,看黑色的方塊,上下兩圖中t=4的時候,到達的任務有T1,T2,T3,T4T_1,T_2,T_3,T_4T1?,T2?,T3?,T4?,他們的截止時間分別是d2≤d3≤d1≤d4d2\le d3\le d1\le d4d2≤d3≤d1≤d4,所以在t=4的時候應該執行T2T_2T2? ,這個例子不太好,看下面的例子。
EDF:當每個任務進入系統時,會為其分配一個優先級,其優先級由其絕對截止日期決定,截止日期較早的任務被分配更高的優先級
好處是CPU利用率達到百分百
壞處是高運行時開銷,過載期間的時間隔離不良。
所以這個算法沒有被廣泛運用。
比如下面是一個缺點,上面的調度中,T2的ddl比較前,但是T2來的太晚了,所以就算馬上讓給T2,T2也會超時,但還好T1執行完了,如果再提前一點,讓T2在t=4時刻到,兩個任務都執行不完。
事務觸發調度
周期性任務的搶奪調度算法
| 靜態優先級 | RM(rate-monotonic)速率單調 | DM(deadline-monotonic)時限單調 |
| 動態優先級 | EDF | EDF* |
混合周期性任務和非周期性任務的任務集
周期性任務:時間驅動,執行具有硬時間約束的關鍵控制活動,旨在保證正常的激活率。
非周期任務:事件驅動,可能有硬、軟、非實時要求,具體取決于具體應用。
零星任務:只有對環境做出適當的假設,才能離線保證具有關鍵時間約束的事件驅動非周期任務;也就是說,假設每個關鍵事件的最大到達率。以最短到達間隔時間為特征的非周期性任務稱為零星任務。
后臺調度
- 周期性任務的RM和EDF調度的簡單解決方案:
- 在后臺處理非周期性任務,即如果沒有定期請求。
- 定期任務不受影響。
- 非周期性任務的響應可能太長,不可能為其分配更高的優先級。
說白了就是有兩個不同優先級的隊列,周期性任務用RM算法排隊,非周期任務用FCFS排隊,周期任務優先級更高,非周期任務只有周期任務空閑時才能用上cpu。
例子:
每個周期性任務的豎線,都是他此刻要進行調度的時候,RM算法的特點是,周期越短的任務優先級越高,所以T1優先級大于T2,在12時刻的時候,T2沒執行完,被T1搶占了,再繼續執行。然后最下面的非周期任務就插周期任務的空運行。
RM - Polling Server rm-輪詢服務器
想法:人為的創建一個周期性任務,這個任務專門用來處理非周期性任務,所以也被稱為server。
和所有的周期性任務一樣,server也有他的周期和計算時間,所以運行其上的周期性任務也會受限于他的周期
他的優先級(也就是周期的倒數)可以選取為能匹配非周期任務的需求。
如果沒有提交的非周期性請求,PS將掛起自己,直到下一個周期開始,并且最初分配給非周期性服務的時間不會為非周期性執行保留。
缺點:如果一個非周期性請求剛好在服務器掛起之后到達,它必須等到下一個輪詢周期開始。
周期性任務的可調度性分析
一組定期任務和一個服務器任務可以在其截止日期內執行,如果
這是充分非必要條件。
可調度性算法
Utilization Bound Test
$U=10/30+10/40+12/52=81% \ge 3(2^{1/3}-1)=78% $ 但是還是可以調度,所以說明這個利用率上界是充分條件。
精確分析:計算WCRT的方程
hp(i)是比Taski更高優先級的Task集合,[]是向上取整,整個式子采用迭代方式求直到收斂hp(i)是比Task_i更高優先級的Task集合,[]是向上取整,整個式子采用迭代方式求直到收斂hp(i)是比Taski?更高優先級的Task集合,[]是向上取整,整個式子采用迭代方式求直到收斂
| 1 | 30 | 30 | 10 | H |
| 2 | 40 | 40 | 10 | M |
| 3 | 52 | 52 | 12 | L |
R1=C1+0=10≤D1=30,所以可以調度R_1=C_1+0=10\le D_1=30 ,所以可以調度R1?=C1?+0=10≤D1?=30,所以可以調度。 R2=C2+[R2T1]C1\displaystyle R_2=C_2+[\frac{R2}{T1}]C_1R2?=C2?+[T1R2?]C1?,從R2=C2R_2=C_2R2?=C2?的最好情況開始迭代,直到收斂。第一次是R2=10+[1030]×10=10+1×10=20;接著迭代R2=10+[2030]×10=10+1×10=20。發現收斂了,所以R2就是20≤D2=40\displaystyle R_2=10+[\frac{10}{30}]\times10=10+1\times10=20;接著迭代R_2=10+[\frac{20}{30}]\times10=10+1\times10=20。發現收斂了,所以R_2就是20\le D_2=40R2?=10+[3010?]×10=10+1×10=20;接著迭代R2?=10+[3020?]×10=10+1×10=20。發現收斂了,所以R2?就是20≤D2?=40,可以調度。R3算數過程如下圖:
總結
以上是生活随笔為你收集整理的实时系统-调度算法和可调度分析的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 编程开发中的起名规范
- 下一篇: [Sdoi2008] Sue的小球