實(shí)時(shí)事務(wù)調(diào)度(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-11 22:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-11 22:30:01 來(lái)源：信息時(shí)代

    實(shí)時(shí)事務(wù)調(diào)度 : 對(duì)于任一給定事務(wù)集各事務(wù)活動(dòng)的執(zhí)行排序。關(guān)于RTDB事務(wù)有兩級(jí)調(diào)度: 事務(wù)級(jí)(CPU使用)和操作級(jí)(數(shù)據(jù)使用),后者就是通常的并發(fā)控制,這里指的是前者。
1.決定調(diào)度策略的基本因素
決定調(diào)度策略設(shè)計(jì)或選擇的基本因素有:
(1)脫機(jī)與聯(lián)機(jī): 脫機(jī)調(diào)度基于事務(wù)的預(yù)分析,在系統(tǒng)未運(yùn)行前產(chǎn)生一個(gè)事務(wù)執(zhí)行的調(diào)度表或調(diào)度計(jì)劃。聯(lián)機(jī)調(diào)度則在系統(tǒng)運(yùn)行時(shí)才執(zhí)行調(diào)度算法來(lái)實(shí)現(xiàn)對(duì)事務(wù)執(zhí)行的指派。
(2)靜態(tài)與動(dòng)態(tài):靜態(tài)調(diào)度乃指調(diào)度策略與算法(包括優(yōu)先分派)不考慮動(dòng)態(tài)變化情況,故一旦確定,不會(huì)根據(jù)當(dāng)時(shí)的情況而動(dòng)態(tài)地變更。動(dòng)態(tài)調(diào)度在運(yùn)行時(shí)動(dòng)態(tài)地進(jìn)行事務(wù)的“可行性”和“可調(diào)度性”分析,然后產(chǎn)生一個(gè)事務(wù)能否及何時(shí)執(zhí)行的調(diào)度決策。注意,脫機(jī)調(diào)度當(dāng)然是靜態(tài)的,但靜態(tài)調(diào)度不一定是脫機(jī)的,所以它們屬于調(diào)度描述的兩個(gè)不同維。
(3)可調(diào)度性分析: 即事務(wù)滿足其定時(shí)限制(特別是截止期)的可能性或概率分析,對(duì)當(dāng)前事務(wù)進(jìn)行“可行性”檢驗(yàn)和預(yù)測(cè)。一般,實(shí)時(shí)調(diào)度應(yīng)有一定的可調(diào)度性分析能力。
(4)沖突避免與沖突解決:系統(tǒng)中存在著事務(wù)間潛在的資源使用沖突。調(diào)度這種沖突的方法可以分成兩類: 一類是事務(wù)被放行以前進(jìn)行潛在沖突的探測(cè)與解決,不讓有潛在沖突的事務(wù)同時(shí)運(yùn)行,故稱為避免沖突的調(diào)度。另一類是允許有潛在沖突的事務(wù)同時(shí)執(zhí)行,動(dòng)態(tài)地進(jìn)行沖突的探測(cè)與解決。當(dāng)要發(fā)生沖突時(shí),采用一定的協(xié)議來(lái)解決,典型的就是封鎖(等待)或剝奪兩個(gè)沖突事務(wù)之一的執(zhí)行,這種封鎖與剝奪都以其優(yōu)先級(jí)的高低為依據(jù)。
(5)搶占與不搶占:所謂搶占就是高優(yōu)先級(jí)事務(wù)搶占低優(yōu)先級(jí)事務(wù)的CPU,而低優(yōu)先級(jí)的事務(wù)則被掛起(不被夭折),當(dāng)該高優(yōu)先級(jí)事務(wù)結(jié)束時(shí),它恢復(fù)執(zhí)行。不搶占調(diào)度,則一個(gè)事務(wù)一旦開(kāi)始執(zhí)行,就直至結(jié)束而不讓出它已獲得且仍然需要的任何資源。搶占調(diào)度可避免“優(yōu)先級(jí)顛倒”,但也可能帶來(lái)負(fù)面作用。因?yàn)楸粧炱鸬氖聞?wù)若不讓出它已占有的數(shù)據(jù),則數(shù)據(jù)的占有時(shí)間延長(zhǎng),就會(huì)形成等待事務(wù)的“護(hù)航隊(duì)”(convoy),這種“護(hù)航隊(duì)”一旦形成,可能會(huì)持續(xù)很長(zhǎng)的時(shí)間,進(jìn)而導(dǎo)致事務(wù)延長(zhǎng)時(shí)間的不確定性,不利于其定時(shí)限制的滿足。
(6)超載與非超載:非超載調(diào)度假定系統(tǒng)的事務(wù)集始終備有足夠的資源,每一可能的事務(wù)集都是可調(diào)度的。它不能處理“不可調(diào)度”(即不能滿足定時(shí)限制)的事務(wù),而是簡(jiǎn)單地將其拋棄。超載調(diào)度進(jìn)行超載情況(即存在定時(shí)限制不滿足的可能性)的探測(cè),當(dāng)探測(cè)到這種情況時(shí),則使用各種策略來(lái)解決。
2.優(yōu)先級(jí)分派策略
作為實(shí)時(shí)事務(wù)調(diào)度基礎(chǔ)的優(yōu)先級(jí)分派策略是一個(gè)函數(shù),可用于兩類不同對(duì)象: 單個(gè)事務(wù)或一個(gè)事務(wù)組。當(dāng)用于單個(gè)事務(wù)時(shí),函數(shù)結(jié)果是該事務(wù)的優(yōu)先級(jí); 當(dāng)用于事務(wù)組時(shí),結(jié)果是這些事務(wù)的一個(gè)排序表。
以下為典型的實(shí)時(shí)事務(wù)優(yōu)先級(jí)分派策略:
(1)最早放行優(yōu)先(earliest release first,ERF):將最高優(yōu)先級(jí)給具有最早“放行”時(shí)間的事務(wù)。所謂放行時(shí)間就是事務(wù)可以開(kāi)始執(zhí)行的最早時(shí)間(不一定是事務(wù)的到達(dá)時(shí)間)。
(2) 最早截止期優(yōu)先(earliest deadline first,EDF): 即具有最早截止期者優(yōu)先級(jí)最高。其主要缺點(diǎn)是已過(guò)或幾乎要過(guò)截止期者將獲得最高優(yōu)先級(jí),這顯然不合適。
(3) 最早可達(dá)截止期優(yōu)先(earliest feasible deadline first,EFDF): 具有最早的“可達(dá)”截止期者優(yōu)先級(jí)最高。一個(gè)事務(wù)T的截止期相對(duì)于當(dāng)前時(shí)間是“可達(dá)到”的,乃指t+(E-P)≤d。這里t為當(dāng)前時(shí)間,E、P分別為T(mén)的執(zhí)行時(shí)間估算和已執(zhí)行時(shí)間,d為其截止期。這樣,具有不可達(dá)截止期的事務(wù)可不必立即夭折,因?yàn)樗€有機(jī)會(huì)(當(dāng)系統(tǒng)沒(méi)有可達(dá)截止期的事務(wù)時(shí))獲得服務(wù),這對(duì)軟實(shí)時(shí)事務(wù)很有用。該策略顯然是EDF的改進(jìn)版本。
(4)最短空余時(shí)間優(yōu)先(least slack first,LSF):事務(wù)T的空余時(shí)間S=d-(t+E-P),即推遲T的執(zhí)行而仍然滿足其截止期的可推遲時(shí)間量估算。LSF考慮了當(dāng)前時(shí)間與剩余執(zhí)行時(shí)間估算E—F,若事務(wù)在執(zhí)行,則當(dāng)前時(shí)間t與已執(zhí)行時(shí)間P同步增加而使S不變,因而優(yōu)先級(jí)也不變。但隨事務(wù)的停止執(zhí)行,其優(yōu)先級(jí)動(dòng)態(tài)上升。所以,它是一種動(dòng)態(tài)策。
(5)最高價(jià)值優(yōu)先(highest value first,HVF):每一事務(wù)有一價(jià)值函數(shù),其值最大者最優(yōu)先。問(wèn)題是如何合理地構(gòu)造價(jià)值函數(shù),例如: V(T)=k(w₁(t-t_s)-w₂d+w₃P-w₄S),其中,t、d、P、S的意義同上,k、t_s分別為事務(wù)T的危急度、開(kāi)始時(shí)間,w_i為加權(quán)因子。
(6) 最大價(jià)值密度優(yōu)先(greatest value density first,GVDF): 下列價(jià)值密度函數(shù)最大者最優(yōu)先為:

(v為價(jià)值函數(shù))
3. 典型的調(diào)度方法
(1)靜態(tài)表驅(qū)動(dòng)調(diào)度: 它執(zhí)行靜態(tài)可調(diào)度性分析,產(chǎn)生一種調(diào)度表,在運(yùn)行時(shí)按調(diào)度表決定一個(gè)事務(wù)何時(shí)執(zhí)行。這種方法較適用于周期性事務(wù)。
(2)優(yōu)先級(jí)驅(qū)動(dòng)可搶占調(diào)度:它強(qiáng)調(diào)“最高優(yōu)先者”。每一事務(wù)被指派一優(yōu)先級(jí),按優(yōu)先級(jí)高低執(zhí)行;在執(zhí)行過(guò)程中,若有更高優(yōu)先級(jí)的事務(wù)到達(dá),則讓位給它執(zhí)行。
(3)動(dòng)態(tài)計(jì)劃式調(diào)度:它對(duì)到達(dá)的事務(wù)進(jìn)行動(dòng)態(tài)可調(diào)度性分析或可行性檢驗(yàn),僅當(dāng)斷定它是可行的,才放行,并產(chǎn)生一個(gè)各事務(wù)執(zhí)行的計(jì)劃或調(diào)度。它提供了事務(wù)可行性預(yù)報(bào),凡放行的事務(wù)都保險(xiǎn)會(huì)滿足其時(shí)間限制。但問(wèn)題是,如何使事務(wù)的執(zhí)行時(shí)間估算、資源需求、定時(shí)限制、截止期或周期、執(zhí)行次序約束等諸多因素的假定成立,從而使這“保險(xiǎn)算法”有效,這很難實(shí)現(xiàn)。
(4)動(dòng)態(tài)盡力式調(diào)度:基于事務(wù)的特征為每一指派一優(yōu)先級(jí),然后就按其優(yōu)先級(jí)來(lái)調(diào)度。其可靠度通過(guò)優(yōu)先級(jí)動(dòng)態(tài)調(diào)整的深入模擬仿真來(lái)獲得。它不進(jìn)行可行性檢驗(yàn),盡最大努力去滿足多個(gè)事務(wù)的截止時(shí)間,但不保險(xiǎn),事務(wù)在執(zhí)行期間可能被夭折。