處理機調(diào)度與死鎖

處理機調(diào)度：多道程序環(huán)境下横腿，動態(tài)的把處理機分配給就緒隊列中的一個進程使之
執(zhí)行开缎。提高處理機的利用率、改善系統(tǒng)性能仗岸，很大程度上取決于處理機調(diào)度的性能允耿。
處理機調(diào)度便成為OS設計的中心問題之一。分配的任務由處理機調(diào)度程序完成

處理機調(diào)度的基本概念

作業(yè)進入系統(tǒng)駐留在外存的后備隊列上扒怖，再至調(diào)入內(nèi)存運行完畢较锡，可能要經(jīng)歷下述三級調(diào)度

高級調(diào)度

又稱作業(yè)調(diào)度或長程調(diào)度(Long-Term Scheduling),接納調(diào)度(Admission Scheduling) 主要在早期批處理階段，處理在外存上的作業(yè)
決定外存后備隊列中的哪些作業(yè)調(diào)入內(nèi)存; ?為它們創(chuàng)建進程盗痒、分配必要的資源; ?將新創(chuàng)建的進程排在就緒隊列上蚂蕴，準備執(zhí)行。 * 管理的方面比較多

系統(tǒng)運行并不一定存在高級調(diào)度

批處理系統(tǒng) ：作業(yè)進入系統(tǒng)后先駐留外存俯邓， 故需要有作業(yè)調(diào)度骡楼。
分時系統(tǒng) ：為及時響應，作業(yè)由終端直接送 入內(nèi)存稽鞭，故不需作業(yè)調(diào)度鸟整。
實時系統(tǒng) 中，通常也不需作業(yè)調(diào)度朦蕴。

低級調(diào)度

也稱為進程調(diào)度篮条、微觀調(diào)度或短程調(diào)度 （Short-Term Scheduling） 決定內(nèi)存就緒隊列中的哪個進程獲得處理 機，進行分配工作吩抓。是最基本的一種調(diào)度涉茧， 在三種基本OS中都有

進程調(diào)度方式

非搶占方式（Non-preemptive Mode） 一旦處理機分配給某進程，該進程一直執(zhí)行疹娶。 決不允許其他進程搶占已分配運行進程的處理機降瞳。 2）搶占方式（Preemptive Mode） 允許調(diào)度程序根據(jù)某種原則，暫停某個正在執(zhí) 行的進程，將處理機重新分配給另一進程挣饥。

中級調(diào)度

又稱交換調(diào)度或中程調(diào)度（Medium-Term Scheduling） 引入目的：提高內(nèi)存利用率和系統(tǒng)吞吐量除师。 根據(jù)條件將一些進程調(diào)出或再調(diào)入內(nèi)存

調(diào)度隊列模型

不論高級、中級或者低級調(diào)度扔枫，都涉及到進程隊 列汛聚，由此形成了三類調(diào)度隊列模型。從這三種方式中 體驗調(diào)度的過程短荐。
① 僅有進程調(diào)度的調(diào)度隊列模型
② 具有高級和低級調(diào)度的調(diào)度隊列模型
③ 同時具有三級調(diào)度的調(diào)度隊列模型

進程調(diào)度發(fā)生時間

正在執(zhí)行的進程結(jié)束 ?
正在執(zhí)行的進程阻塞 ?
正在執(zhí)行的進程未完成轉(zhuǎn)就緒（時間片到） ?
新就緒了更高優(yōu)先級的進程（搶占式）
具有高級和低級調(diào)度的調(diào)度隊列模型 ? 批處理系統(tǒng)中倚舀，還需要作業(yè)調(diào)度

同時具有三級調(diào)度的調(diào)度隊列模型

引入中級調(diào)度后，進程的狀態(tài)變化：
? 就緒狀態(tài)：分為內(nèi)存就緒和外存就緒忍宋。
? 阻塞狀態(tài)：分為內(nèi)存阻塞和外存阻塞痕貌。 中級調(diào)度使進程在上述狀態(tài)間變化，并使 數(shù)據(jù)在內(nèi)外存間互換糠排。

image.png

選擇調(diào)度方式和調(diào)度算法的若干準則

面向用戶的準則

周轉(zhuǎn)時間短： 針對批處理系統(tǒng)的性能指標舵稠。作業(yè)從提交到完成所經(jīng)歷 的時間。 ?
CPU執(zhí)行用時Ts ?
總的等待時間Tw = 在后備隊列中等待 + 就緒隊列上等待 + 阻塞隊列中等待（等待I/O操作用時） ?
周轉(zhuǎn)時間T=Ts+Tw ?
帶權周轉(zhuǎn)時間W= T/Ts ?
平均周轉(zhuǎn)時間入宦、平均帶權周轉(zhuǎn)時間（n個作業(yè)求平均）

響應時間快：針對分時系統(tǒng)哺徊。用戶輸入一個請 求（如擊鍵）到系統(tǒng)給出首次響應（如屏幕顯示） 的時間
?均衡性：系統(tǒng)響應時間的快慢與用戶所請求的 復雜性相適應。
?截止時間的保證：針對實時系統(tǒng)的性能指標乾闰。 開始截止時間和完成截止時間落追。任務必須按規(guī)定 的時間開始或完成，調(diào)度方式和算法必須能保證 該要求涯肩。 
?優(yōu)先權準則：三大基本OS在調(diào)度算法的選擇 時都可遵循轿钠。可以使關鍵任務達到更好的指標

面向系統(tǒng)的準則

系統(tǒng)吞吐量高： 批處理系統(tǒng)的重要指標病苗。 ?單位時間內(nèi)所完成的作業(yè)數(shù)谣膳，跟作業(yè)本身 （與作業(yè)平均長度密切相關）和調(diào)度算法 都有關系； 

處理機調(diào)度與死鎖

調(diào)度算法

先來先服務調(diào)度算法FCFS

一種最簡單的調(diào)度算法铅乡，按先后順序進行調(diào)度继谚。既 可用于作業(yè)調(diào)度，也可用于進程調(diào)度阵幸。
 ? 按照作業(yè)提交花履，或進程變?yōu)榫途w狀態(tài)的先后次 序分派CPU； 
? 新作業(yè)只有當當前作業(yè)或進程執(zhí)行完或阻塞才 獲得CPU運行
 ? 被喚醒的作業(yè)或進程不立即恢復執(zhí)行挚赊，通常等 到當前作業(yè)或進程出讓CPU诡壁。 （所以，默認即 是非搶占方式）
 不利于短作業(yè)（進程） 

短作業(yè)（進程）優(yōu)先調(diào)度算法SJF/SPF

優(yōu)點：
 ? 通過上表可見采用SJF/SPF算法荠割，平均周轉(zhuǎn) 時間妹卿、平均帶權周轉(zhuǎn)時間都有明顯改善旺矾。 SJF/SPF調(diào)度算法能有效的降低作業(yè)的平均 等待時間，提高系統(tǒng)吞吐量夺克。 方式： 
? 分搶占和非搶占兩種方式箕宙，上例為簡單的非 搶占式。
 SJF/SPF的不足： 1. 對短作業(yè)有利铺纽，但同時造成了對長作 業(yè)的不利柬帕。 2.由于作業(yè)（進程）的長短含主觀因素， 不一定能真正做到短作業(yè)優(yōu)先狡门。 3.未考慮作業(yè)的緊迫程度陷寝，因而不能保證 緊迫性作業(yè)（進程）的及時處理。

高優(yōu)先權優(yōu)先調(diào)度算法HPF

照顧緊迫性作業(yè)其馏，使其獲得優(yōu)先處理而引入 調(diào)度算法凤跑。常用于批處理系統(tǒng)中的作業(yè)調(diào)度算法， 以及多種操作系統(tǒng)中的進程調(diào)度算法 1) 分兩種方式：
 ?非搶占式優(yōu)先權算法 
?搶占式優(yōu)先權算法 關鍵點：新作業(yè)產(chǎn)生時
優(yōu)先權的類型
 ? 靜態(tài)優(yōu)先權：創(chuàng)建進程時確定叛复，整個運行 期間保持不變仔引。一般利用某一范圍的一個 整數(shù)來表示，又稱為優(yōu)先數(shù)致扯。
 ? 動態(tài)優(yōu)先權：創(chuàng)建進程時賦予的優(yōu)先權可 隨進程的推進或隨其等待時間的增加而改 變肤寝。

高響應比優(yōu)先調(diào)度算法HRRN

 短作業(yè)優(yōu)先算法是一種比較好的算法（相當于根據(jù) 作業(yè)長度設定的靜態(tài)優(yōu)先權算法）当辐，適用于短作業(yè) 較多的批處理系統(tǒng)中抖僵，其主要不足是長作業(yè)的運行 得不到保證。
 ? HRRN為每個作業(yè)引入動態(tài)優(yōu)先權缘揪，使作業(yè)的優(yōu) 先級隨著等待時間的增加而以速率a提高： 優(yōu)先權 =（等待時間+要求服務時間)/要求服務時間 = 響應時間 / 要求服務時間

基于時間片的輪轉(zhuǎn)調(diào)度算法RR

? 分時系統(tǒng)新需求：及時響應用戶的請求耍群； 采用基于 時間片 的輪轉(zhuǎn)式進程調(diào)度算法。
 ? 早期分時系統(tǒng)采用的是 簡單的時間片輪轉(zhuǎn)法
找筝， 進入90年代后廣泛采用 多級反饋隊列調(diào)度算 法 蹈垢。 
時間片輪轉(zhuǎn)算法
1. 將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一 個隊列袖裕。 2. 每次調(diào)度時將CPU分派給隊首進程曹抬，讓其執(zhí)行一 個時間片。時間片的長度從幾個ms到幾百ms急鳄。 3. 在一個時間片結(jié)束時谤民，發(fā)生時鐘中斷。 4. 調(diào)度程序據(jù)此暫停當前進程的執(zhí)行疾宏，將其送到就 緒隊列的末尾张足，并通過上下文切換執(zhí)行當前就緒 的隊首進程。 

多級反饋隊列算法FB

1）設置多個就緒隊列坎藐，各隊列有不同的優(yōu)先 級,優(yōu)先級從第一個隊列依次降低为牍。
 2） 賦予各隊列進程執(zhí)行時間片大小不同, 優(yōu) 先權越高，時間片越短 。

image.png

實時調(diào)度

實時系統(tǒng)

1.指系統(tǒng)能夠在限定的響應時間內(nèi)提供所需水平 的服務碉咆。
2.指計算的正確性不僅取決于程序的邏輯正確性抖韩， 也取決于結(jié)果產(chǎn)生的時間，如果系統(tǒng)的時間約 束條件得不到滿足吟逝，將會發(fā)生系統(tǒng)出錯帽蝶。
實時任務：具有明確時間約束的計算任務， 有軟/硬块攒，隨機/周期性之分励稳。

實現(xiàn)實時調(diào)度的基本條件

1）提供必要的信息 為了實現(xiàn)實時調(diào)度，系統(tǒng)應向調(diào)度程序提供 有關任務的下述信息：
就緒時間 囱井。該任務成為就緒狀態(tài)的時間驹尼。
開始截止時間、完成截止時間 庞呕。
處理時間 新翎。從開始執(zhí)行到完成所需時間。
資源要求 住练。任務執(zhí)行時所需的一組資源地啰。
優(yōu)先級 。根據(jù)任務性質(zhì)賦予不同優(yōu)先級讲逛。
2）系統(tǒng)處理能力足夠強
處理能力不足可能會出現(xiàn)某些實時任務不能 得到及時處理亏吝，導致難以預料的后果。 如： 系統(tǒng)中有M個周期性的硬實時任務盏混，處理 時間為Ci蔚鸥，周期時間表示為Pi, 單機系統(tǒng)中必須滿足條件
3）采用搶占式調(diào)度機制
? 硬實時任務：廣泛采用搶占機制。
? 小的實時系統(tǒng)：如能預知任務的開始 截止時間许赃，為簡化調(diào)度程序和對任務調(diào) 度時所花費的系統(tǒng)開銷止喷，可采用非搶占 調(diào)度機制，
4）具有快速切換機制
1. 對外部中斷的快速響應能力混聊。 ? 利用快速硬件中斷機構弹谁，可在緊迫的 外部事件請求中及時響應。 2. 快速的任務分派能力句喜。 ? 使系統(tǒng)中的運行功能單位適當?shù)男≡し撸岣咔?換速度。類如線程的思想

實時調(diào)度算法的分類

非搶占調(diào)度算法

該算法較簡單藤滥，用于一些小型實時系統(tǒng)或要 求不太嚴格的實時系統(tǒng)中鳖粟，又可分為：
 1. 非搶占式輪轉(zhuǎn)調(diào)度算法。常用于工業(yè)生產(chǎn) 的群控系統(tǒng)中拙绊，要求不太嚴格向图。
 2. 非搶占式優(yōu)先調(diào)度算法泳秀。要求相對嚴格， 根據(jù)任務的優(yōu)先級安排等待位置榄攀∈雀担可用于 有一定要求的實時控制系統(tǒng)中。（精心設 置可獲得百ms級的響應時間）

搶占式調(diào)度算法

較嚴格的實時系統(tǒng)中（t約為數(shù)十ms）檩赢， 選擇采用搶占式優(yōu)先權調(diào)度算法吕嘀。根據(jù) 搶占發(fā)生時間可分為：
 1. 基于時鐘：某高優(yōu)先級任務到達后并不 立即搶占，而等下一個時鐘中斷時搶占贞瞒。 
2. 立即搶占：一旦出現(xiàn)外部中斷偶房，只要當 前任務未處于臨界區(qū)，就立即搶占處理 機军浆。

最早截止時間優(yōu)先EDF

根據(jù)任務的開始截止時間來確定任務的優(yōu)先級棕洋。 截止時間越早，其優(yōu)先級越高乒融。 ?系統(tǒng)保持一個實時任務就緒隊列 ?隊列按各任務截止時間的早晚排序 ?調(diào)度程序總是選擇就緒隊列中的第一個任務掰盘，分配處 理機使之投入運行。
 ? 新任務產(chǎn)生時赞季，是否等當前程序執(zhí)行完： ?搶占式/非搶占式 
? 可能會使作業(yè)錯過愧捕，但可適用于軟實時系統(tǒng)

最低松弛度優(yōu)先LLF

根據(jù)任務緊急（或松弛）的程度，來確定任務的優(yōu)先 級申钩。任務的緊急程度越高（松弛度值越写位妗），優(yōu)先級就越 高典蜕。
 ? 松弛度= 截止完成時間 – 還需執(zhí)行時間 - 當前時間 可理解為當前時刻到開始截止時刻間的差距断盛，隨著時間的 推進罗洗，這個差值逐漸變小愉舔，任務越來越緊迫

處理機調(diào)度與死鎖

死鎖

多道程序系統(tǒng)借助并發(fā)執(zhí)行改善資源利用率， 提高系統(tǒng)吞吐量伙菜，但可能發(fā)生一種危險——死 鎖轩缤。 死鎖（Deadlock）：指多個進程在運行過 程中，因爭奪資源而造成的一種僵局贩绕。當進程 處于這種狀態(tài)時火的，若無外力作用，它們都將無 法再向前推進淑倾。

產(chǎn)生死鎖的原因

1. 競爭資源馏鹤。系統(tǒng)中供多個進程共享的資源 如打印機、公用隊列等的數(shù)目不滿足需要 時娇哆，會引起資源競爭而產(chǎn)生死鎖湃累。
2. 進程間推進順序非法勃救。進程在運行過程中， 請求和釋放資源的順序不當治力，同樣會導致 死鎖蒙秒。

產(chǎn)生死鎖的必要條件

① 互斥條件：進程對所分配到的資源進行排他性 使用
② 請求和保持條件：進程已經(jīng)保持了至少一個資 源，又提出新的資源請求宵统，而新請求資源被其 他進程占有只能造成自身進程阻塞晕讲，但對自己 已獲得的其他資源保持不放，必然影響其他進 程马澈。
③ 不剝奪條件：進程已獲得的資源未使用完之前 不能被剝奪瓢省，只能在使用完時由自己釋放。
④ 環(huán)路等待條件

處理死鎖的基本方法

① 預防死鎖 
? 設置限制條件痊班，破壞四個必要條件的一個或幾個净捅， 預防發(fā)生死鎖。
 ? 較易實現(xiàn)辩块。限制條件的嚴格也會導致系統(tǒng)資源利用 率和系統(tǒng)吞吐量降低蛔六。
 ② 避免死鎖 
? 不須事先限制，破壞四個必要條件废亭，而是在資源的 動態(tài)分配過程中国章，用某種方法去防止系統(tǒng)進入不安 全狀態(tài)，從而避免發(fā)生死鎖豆村。
 ? 這種事先加以較弱限制的方法液兽，實現(xiàn)上有一定難度， 但可獲較高的資源利用率及系統(tǒng)吞吐量掌动，目前在較 完善的系統(tǒng)中四啰，常用此方法來避免發(fā)生死鎖。
③ 檢測死鎖粗恢。
 ? 允許系統(tǒng)運行過程中發(fā)生死鎖柑晒，但通過系統(tǒng)檢測機 構可及時的檢測出，能精確確定與死鎖有關的進程 和資源眷射；然后采取適當?shù)拇胧┏自蓿瑥南到y(tǒng)中將已發(fā) 生的死鎖清除掉。
 ④ 解除死鎖妖碉。 
? 與死鎖檢測配套的一種措施涌庭。
 ? 常用的實施方法：撤銷或掛起一些進程，以便回收 一些資源并將他們分配給已阻塞進程欧宜，使之轉(zhuǎn)為就 緒以繼續(xù)運行坐榆。 
? 死鎖的檢測與解除措施，有可能使系統(tǒng)獲得較好的 資源利用率和吞吐量（死鎖幾率不一定很高）冗茸，但 在實現(xiàn)上難度也最大席镀。

預防死鎖的方法

預防死鎖
摒棄“環(huán)路等待”條件
避免死鎖

銀行家算法避免死鎖

image.png

image.png

image.png

（1）T0時刻的初始狀態(tài)是安全的羹铅； 
（2）下面出現(xiàn)P1請求資源的操作，具體請求 向量為Request1(1,0,2)愉昆，利用銀行家算法 進行檢查該操作是否是安全可行的： 
1）兩個基本判斷 
Request1(1,0,2)<=Need1(1,2,2) 
Request1(1,0,2)<=Available1(3,3,2) 
2）先假設為P1分配資源职员，并修改 Available,Allocation1和Need1向量。
3） Request1(1,0,2)后新的資源狀態(tài)表下再判斷新資源狀態(tài)是否是 安全的跛溉。 找到一個安全序列{P1,P3,P4,P0,P2}焊切，因此系統(tǒng)是安全的，該請求是 安全的芳室，可將假設真正實施专肪，將P1所申請的資源分配給它。

死鎖的檢測與解除

當系統(tǒng)為進程分配資源時堪侯，若未采取任何 限制性措施嚎尤，則系統(tǒng)必須提供檢測和解除 死鎖的手段，為此系統(tǒng)必須：

1. 保存有關資源的請求和分配信息伍宦；

2. 提供一種算法芽死，以利用這些信息來檢測系 統(tǒng)是否已進入死鎖狀態(tài)

   
   
   image.png

死鎖的檢測

檢測時機：
當進程等待時檢測死鎖
定時檢測
系統(tǒng)資源利用率下降時檢測死鎖

死鎖定理

簡化方法如下：
1.在資源分配圖中找出一個既不阻塞又非獨立 的進程結(jié)點Pi，在順利的情況下運行完畢次洼，釋 放其占有的全部資源关贵。
2.由于釋放了資源，這樣能使其它被阻塞的進 程獲得資源繼續(xù)運行卖毁。消去了Pi的邊揖曾。
3.經(jīng)過一系列簡化后，若能消去圖中所有邊亥啦， 使結(jié)點都孤立炭剪，稱該圖是可完全簡化的。

死鎖的解除

當發(fā)現(xiàn)進程死鎖時翔脱，便應立即把它們從 死鎖狀態(tài)中解脫出來奴拦。常采用的方法是：

1. 剝奪資源。從其他進程剝奪足夠數(shù)量的 資源給死鎖進程以解除死鎖狀態(tài)碍侦。
2. 撤銷進程粱坤。最簡單的是讓全部進程都死 掉隶糕；溫和一點的是按照某種順序逐個撤 銷進程瓷产，直至有足夠的資源可用，使死 鎖狀態(tài)消除為止枚驻。

2.jpg

3.jpg

1.jpg