1、要解決的問(wèn)題WHAT：按什么原則分配CPU 進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī)HOW： 如何分配CPU CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）第1頁(yè)，共56頁(yè)。 一批作業(yè)從進(jìn)入系統(tǒng)到作業(yè)運(yùn)行完畢可能經(jīng)歷三級(jí)調(diào)度高級(jí)、低級(jí)和中級(jí)調(diào)度。一. 高級(jí)調(diào)度(High Scheduling) 又稱(chēng)為作業(yè)調(diào)度接納調(diào)度或長(zhǎng)程調(diào)度, 用于批處理系統(tǒng), 確定將外存后備隊(duì)列中哪些作業(yè)調(diào)入內(nèi)存, 并為它們創(chuàng)建進(jìn)程。實(shí)時(shí)系統(tǒng)和分時(shí)系統(tǒng)的前臺(tái)作業(yè)不需要作業(yè)調(diào)度。每次作業(yè)調(diào)度時(shí), 都必須做出兩個(gè)決定: 1) 接納多少個(gè)作業(yè): 取決于多道程序度。 2) 接納哪些作業(yè)(用什么調(diào)度算法): 先來(lái)先服務(wù)、短作業(yè)優(yōu)先、

2、優(yōu)先權(quán)、響應(yīng)比優(yōu)先。3.1 處理機(jī)調(diào)度的基本概念 3.1.1 高級(jí)、低級(jí)和中級(jí)調(diào)度響應(yīng)/運(yùn)行第2頁(yè)，共56頁(yè)。二. 低級(jí)調(diào)度(進(jìn)程調(diào)度,短程調(diào)度) 進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng), 即按照一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程。它是最基本的一種調(diào)度, 批處理系統(tǒng), 實(shí)時(shí)系統(tǒng)和分時(shí)系統(tǒng)都必須有進(jìn)程調(diào)度。它通過(guò)進(jìn)程調(diào)度程序來(lái)完成。1. 進(jìn)程調(diào)度程序的主要功能可描述如下：(1) 記錄系統(tǒng)中各進(jìn)程的狀況 為了很好地實(shí)現(xiàn)進(jìn)程調(diào)度, 進(jìn)程調(diào)度程序首先必須管理系統(tǒng)中各進(jìn)程的PCB，將進(jìn)程的狀態(tài)變化及資源需求情況及時(shí)地記錄到PCB中。通過(guò)PCB變化來(lái)準(zhǔn)確地掌握系統(tǒng)

3、中所有進(jìn)程的狀態(tài)特征和執(zhí)行情況。第3頁(yè)，共56頁(yè)。(2) 選擇進(jìn)程真正占有CPU 這是進(jìn)程調(diào)度的實(shí)質(zhì), 即按照系統(tǒng)規(guī)定的調(diào)度策略從就緒隊(duì)列中選擇一個(gè)進(jìn)程占有CPU執(zhí)行。進(jìn)程調(diào)度依據(jù)的算法與系統(tǒng)的設(shè)計(jì)目標(biāo)相一致。對(duì)于不同的系統(tǒng), 通常采用不同的調(diào)度策略。對(duì)于批處理系統(tǒng)常采用短進(jìn)程的進(jìn)程優(yōu)先, 以減少各進(jìn)程的周轉(zhuǎn)時(shí)間。對(duì)于分時(shí)系統(tǒng), 更多地采用時(shí)間片輪轉(zhuǎn)。(3) 進(jìn)行進(jìn)程上下文的切換 當(dāng)進(jìn)程調(diào)度選中一個(gè)進(jìn)程占有CPU時(shí), 進(jìn)程調(diào)度程序要做的主要工作則是進(jìn)行進(jìn)程上下文切換: 將正在執(zhí)行進(jìn)程的運(yùn)行現(xiàn)場(chǎng)保留在該進(jìn)程的PCB中, 以便以后該進(jìn)程恢復(fù)執(zhí)行。將剛選中進(jìn)程的運(yùn)行現(xiàn)場(chǎng)恢復(fù)起來(lái), 并將CPU的控制權(quán)

4、交給被選中進(jìn)程, 使其執(zhí)行。第4頁(yè)，共56頁(yè)。2. 進(jìn)程調(diào)度方式 (1)非搶占方式(Non preemptive mode) 在非搶占方式下, 調(diào)度程序一旦把 CPU分配給某一進(jìn)程后便讓它一直運(yùn)行下去, 直到進(jìn)程完成或發(fā)生某事件而不能運(yùn)行時(shí)，才將CPU分給其它進(jìn)程。 這種調(diào)度方式通常用在批處理系統(tǒng)中。它的主要優(yōu)點(diǎn)是簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小。 (2)搶占方式(Preemptive mode) 當(dāng)一個(gè)進(jìn)程正在執(zhí)行時(shí)，系統(tǒng)可以基于某種策略剝奪CPU給其它進(jìn)程。剝奪的原則有： 優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時(shí)間片原則。 顯然這種調(diào)度方式多用在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，以便及時(shí)響應(yīng)各進(jìn)程的請(qǐng)求。第5頁(yè)，共56頁(yè)。3.

5、 進(jìn)程調(diào)度的時(shí)機(jī) 所謂進(jìn)程調(diào)度的時(shí)機(jī)，是指什么情況下引起進(jìn)程調(diào)度程序工作。進(jìn)程調(diào)度的時(shí)機(jī)是與進(jìn)程調(diào)度的方式有關(guān)的。進(jìn)程調(diào)度的時(shí)機(jī)如下：正在執(zhí)行的進(jìn)程正確完成, 或由于某種錯(cuò)誤而終止運(yùn)行(陷阱或中斷) ；執(zhí)行中的進(jìn)程提出I/O請(qǐng)求, 等待I/O完成時(shí);在分時(shí)系統(tǒng)中, 按照時(shí)間片輪轉(zhuǎn), 分給進(jìn)程的時(shí)間片用完時(shí)；按照優(yōu)先級(jí)調(diào)度時(shí), 有更高優(yōu)先級(jí)進(jìn)程變?yōu)榫途w時(shí)(搶占方式)；在進(jìn)程通訊中, 執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作, 如wait操作、阻塞原語(yǔ)和喚醒原語(yǔ)時(shí), 都可能引起進(jìn)程調(diào)度。第6頁(yè)，共56頁(yè)。三. 中級(jí)調(diào)度(中程調(diào)度) 中級(jí)調(diào)度使暫時(shí)停止的進(jìn)程不再占用寶貴的內(nèi)存資源, 將它們調(diào)到外存上去成為掛起

6、狀態(tài)。當(dāng)處于掛起就緒的進(jìn)程重新具備運(yùn)行條件且內(nèi)存稍有空閑時(shí), 中級(jí)調(diào)度將它重新調(diào)入內(nèi)存, 掛在活動(dòng)就緒隊(duì)列上等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)質(zhì)上就是存儲(chǔ)管理中的對(duì)換功能。 進(jìn)程調(diào)度頻率最高(10100ms/次)調(diào)度算法簡(jiǎn)單快速; 作業(yè)調(diào)度頻率最低約幾分鐘一次,調(diào)度算法允許花費(fèi)較多的時(shí)間; 中級(jí)調(diào)度介于兩者之間。第7頁(yè)，共56頁(yè)。3.1.2. 調(diào)度隊(duì)列模型1. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 在分時(shí)系統(tǒng)中, 通常僅有進(jìn)程調(diào)度, 采用FIFO算法。CPU就 緒 隊(duì) 列阻 塞 隊(duì) 列時(shí)間片完進(jìn)程調(diào)度等待事件事件出現(xiàn)交互用戶完成第8頁(yè)，共56頁(yè)。2. 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 在批處理系統(tǒng)中,不僅需要進(jìn)程

7、調(diào)度而且需要作業(yè)調(diào)度。CPU就 緒 隊(duì) 列阻 塞 隊(duì) 列時(shí)間片完進(jìn)程調(diào)度事件1出現(xiàn) 后備隊(duì)列完成阻 塞 隊(duì) 列事件2出現(xiàn) 阻 塞 隊(duì) 列事件n出現(xiàn) .等待事件1等待事件2等待事件n作業(yè)調(diào)度第9頁(yè)，共56頁(yè)。3. 具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 在具有三級(jí)調(diào)度系統(tǒng)中, 增加了在外存的掛起狀態(tài)CPU就 緒 隊(duì) 列就 緒 掛 起 時(shí)間片完進(jìn)程調(diào)度事件出現(xiàn)后備隊(duì)列完成阻 塞 掛 起阻 塞 隊(duì) 列 掛起等待事件作業(yè)調(diào)度事件出現(xiàn)中級(jí)調(diào)度交互作業(yè)調(diào)出第10頁(yè)，共56頁(yè)。 對(duì)于不同的系統(tǒng), 有不同的設(shè)計(jì)目標(biāo), 采用不同的調(diào)度算法。調(diào)度算法實(shí)質(zhì)上是個(gè)策略問(wèn)題面向用戶的準(zhǔn)則： 周轉(zhuǎn)時(shí)間短 交互式系統(tǒng)的響應(yīng)時(shí)間快 截止

8、時(shí)間保證 優(yōu)先權(quán)準(zhǔn)則(公平合理)面向系統(tǒng)的準(zhǔn)則： 單位時(shí)間內(nèi)運(yùn)行盡可能多的進(jìn)程, 吞吐量高 使處理機(jī)盡可能保持“忙碌”利用率高 使內(nèi)外存、I/O設(shè)備得以均衡、充分利用3.1.3. 調(diào)度算法的評(píng)價(jià)準(zhǔn)則第11頁(yè)，共56頁(yè)。進(jìn)程(作業(yè))平均周轉(zhuǎn)時(shí)間（周轉(zhuǎn)時(shí)間、吞吐量） 設(shè)某進(jìn)程創(chuàng)建時(shí)間為Si, 結(jié)束的時(shí)間為Ei 它的周轉(zhuǎn)時(shí)間(全過(guò)程所用時(shí)間)為 Ti =Ei Si 系統(tǒng)為它提供的實(shí)際服務(wù)時(shí)間為T(mén)si 則進(jìn)程平均周轉(zhuǎn)時(shí)間T,帶權(quán)平均周轉(zhuǎn)時(shí)間W為： T W= 其中，n為被測(cè)定進(jìn)程流中的進(jìn)程數(shù)ni=1Tin1ni=1Tin1Tsi 要設(shè)計(jì)一個(gè)理想的調(diào)度算法是一件十分困難的事,在實(shí)際系統(tǒng)中, 調(diào)度算法往往折

9、衷考慮。 大多數(shù)操作系統(tǒng)都采用比較簡(jiǎn)單的調(diào)度算法第12頁(yè)，共56頁(yè)。3.2 調(diào)度算法1.先進(jìn)先出調(diào)度算法(FIFO) (先來(lái)先服務(wù)FCFS) 作業(yè)調(diào)度按照進(jìn)入后備隊(duì)列的先后次序調(diào)度, 進(jìn)程調(diào)度按照進(jìn)入進(jìn)程就緒隊(duì)列的先后次序來(lái)調(diào)度 優(yōu)點(diǎn):實(shí)現(xiàn)簡(jiǎn)單 缺點(diǎn):不利于短作業(yè)(進(jìn)程),緊迫性作業(yè)(進(jìn)程)得不到及時(shí)處理2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(SJF,SPF) 選擇就緒隊(duì)列中估計(jì)運(yùn)行時(shí)間最短的進(jìn)程投入運(yùn)行 優(yōu)點(diǎn): 平均周轉(zhuǎn)時(shí)間,帶權(quán)平均周轉(zhuǎn)時(shí)間都改善 缺點(diǎn): 對(duì)長(zhǎng)作業(yè)(進(jìn)程)非常不利 不能保證緊迫性作業(yè)(進(jìn)程)得到及時(shí)處理 估計(jì)運(yùn)行時(shí)間不準(zhǔn)確第13頁(yè)，共56頁(yè)。3. 優(yōu)先權(quán)調(diào)度算法(HPFHighes

10、t Priority First)優(yōu)先選擇就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程投入運(yùn)行非搶占式優(yōu)先權(quán)算法:僅在事件發(fā)生放棄處理機(jī)時(shí)搶占式優(yōu)先權(quán)算法: 可將正在運(yùn)行的運(yùn)行權(quán)剝奪 優(yōu)先權(quán)的類(lèi)型靜態(tài)優(yōu)先權(quán): 在進(jìn)程創(chuàng)建時(shí)指定優(yōu)先權(quán), 在進(jìn)程運(yùn)行時(shí)優(yōu)先數(shù)不變動(dòng)態(tài)優(yōu)先權(quán): 在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先權(quán)，但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化。如等待時(shí)間長(zhǎng)優(yōu)先數(shù)可改變 確定優(yōu)先權(quán)的依據(jù)進(jìn)程類(lèi)型、對(duì)資源的需求、根據(jù)用戶要求第14頁(yè)，共56頁(yè)。4. 高響應(yīng)比優(yōu)先調(diào)度算法： 改進(jìn)短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法,優(yōu)先權(quán)用下式動(dòng)態(tài)計(jì)算出來(lái) 優(yōu)先權(quán)= =上式可看出 等待時(shí)間相同要求服務(wù)的時(shí)間越短優(yōu)先權(quán)越高, 有利于短作業(yè) 要求服務(wù)時(shí)間相

11、同,等待時(shí)間越長(zhǎng)優(yōu)先權(quán)越高,近似于先來(lái)先服務(wù) 長(zhǎng)作業(yè)的優(yōu)先權(quán)會(huì)隨等待時(shí)間加長(zhǎng)而升高,長(zhǎng)作業(yè)也會(huì)得到執(zhí)行等待時(shí)間+要求服務(wù)時(shí)間 響應(yīng)時(shí)間 要求服務(wù)時(shí)間 要求服務(wù)時(shí)間第15頁(yè)，共56頁(yè)。 把CPU劃分成若干時(shí)間片,并且按順序賦給就緒隊(duì)列中的每一個(gè)進(jìn)程，進(jìn)程輪流占有CPU，當(dāng)時(shí)間片用完時(shí)，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的CPU，將該進(jìn)程排在就緒隊(duì)列末尾。同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程運(yùn)行 分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇問(wèn)題： 固定時(shí)間片、可變時(shí)間片確定時(shí)間片大小的因素： 系統(tǒng)響應(yīng)時(shí)間、就緒進(jìn)程個(gè)數(shù)、CPU能力 5.時(shí)間片輪轉(zhuǎn)調(diào)度算法第16頁(yè)，共56頁(yè)。6.多隊(duì)列反饋調(diào)度算法： 系統(tǒng)按優(yōu)先級(jí)設(shè)置多

12、級(jí)就緒隊(duì)列第一級(jí)優(yōu)先級(jí)最高 各就緒隊(duì)列分配不同的時(shí)間片,優(yōu)先級(jí)高的第一級(jí)隊(duì)列時(shí)間片最小, 隨著隊(duì)列優(yōu)先級(jí)的降低, 時(shí)間片加大 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法 一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)就緒隊(duì)列 進(jìn)程由于等待事件而放棄CPU后, 進(jìn)入等待隊(duì)列, 一旦等待的事件發(fā)生, 則回到原來(lái)的就緒隊(duì)列 當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí), 可以搶占CPU,被搶占進(jìn)程回到原來(lái)一級(jí)就緒隊(duì)列末尾 當(dāng)?shù)谝患?jí)隊(duì)列空時(shí), 就去調(diào)度第二級(jí)隊(duì)列, 如此類(lèi)推 時(shí)間片用完后進(jìn)程放棄CPU, 進(jìn)入下一級(jí)就緒隊(duì)列第17頁(yè)，共56頁(yè)。 實(shí)時(shí)系統(tǒng)中, 對(duì)實(shí)時(shí)進(jìn)程的調(diào)度有截止時(shí)間的要求1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 1) 提供必要的信息 就緒時(shí)間、

13、開(kāi)始截止時(shí)間或完成截止時(shí)間、處理時(shí)間、資源要求、優(yōu)先級(jí)( 硬實(shí)時(shí)任務(wù)賦絕對(duì)優(yōu)先級(jí))。 2) 系統(tǒng)處理速度快 若系統(tǒng)中有m 個(gè)周期性硬實(shí)時(shí)任務(wù), 處理時(shí)間為Ci周期時(shí)間為Pi , 則處理機(jī)處理速度應(yīng)達(dá)到可調(diào)度條件: 1 (單處理機(jī)) n (多處理機(jī)) 3) 采用搶占式調(diào)度機(jī)制以滿足對(duì)截止時(shí)間的要求 4) 具有快速切換機(jī)制: 快速中斷響應(yīng)、快速任務(wù)分派3.3 實(shí)時(shí)調(diào)度CiPii=1nCiPii=1n第18頁(yè)，共56頁(yè)。2. 實(shí)時(shí)調(diào)度算法的分類(lèi) 1) 非搶占式調(diào)度算法 非搶占式輪轉(zhuǎn)調(diào)度算法(響應(yīng)時(shí)間數(shù)秒到數(shù)十秒) 輪轉(zhuǎn)一圈后調(diào)度 非搶占式優(yōu)先權(quán)調(diào)度算法(響應(yīng)時(shí)間數(shù)百毫秒) 當(dāng)前進(jìn)程完成(或被阻塞)后

14、調(diào)度 2) 搶占式調(diào)度算法 嚴(yán)格要求的實(shí)時(shí)系統(tǒng), 響應(yīng)時(shí)間在數(shù)十毫秒以內(nèi) 基于時(shí)鐘中斷的搶占式調(diào)度算法 時(shí)鐘中斷到來(lái)時(shí)調(diào)度 立即搶占的優(yōu)先權(quán)調(diào)度算法 立即剝奪當(dāng)前進(jìn)程 調(diào)度時(shí)間見(jiàn)P 83 圖3-6第19頁(yè)，共56頁(yè)。3.幾種常見(jiàn)的實(shí)時(shí)調(diào)度算法 1) 最早截止時(shí)間優(yōu)先算法(Earliest Deadline First) 根據(jù)任務(wù)的開(kāi)始截止時(shí)間確定優(yōu)先級(jí)。 2) 最低松弛度優(yōu)先算法(Least Laxity First) 根據(jù)任務(wù)的松弛度(緊急程度)確定優(yōu)先級(jí) 根據(jù)任務(wù)完成截止時(shí)間和本身運(yùn)行時(shí)間確定松弛度 松弛度= 必須完成時(shí)間-本身運(yùn)行時(shí)間-當(dāng)前時(shí)間 P 85 圖 3-9第20頁(yè)，共56頁(yè)。

15、保存現(xiàn)場(chǎng):順序保存進(jìn)程的上下文, 包括程序計(jì)數(shù)器和其它寄存器 用新?tīng)顟B(tài)和相關(guān)信息更新正在運(yùn)行進(jìn)程的PCB 把該進(jìn)程移至合適的隊(duì)列-就緒、阻塞 選擇另一個(gè)要執(zhí)行的進(jìn)程,更新該進(jìn)程的PCB 從被選中進(jìn)程中重裝入 CPU 上下文,恢復(fù)現(xiàn)場(chǎng) 若無(wú)就緒進(jìn)程,系統(tǒng)會(huì)安排一個(gè)閑逛進(jìn)程(idle), 一直運(yùn)行, 在執(zhí)行過(guò)程中可接收中斷。3.4 CPU調(diào)度的實(shí)現(xiàn)第21頁(yè)，共56頁(yè)。操作系統(tǒng)的核心 向上提供無(wú)中斷的虛擬機(jī)器, 在核心內(nèi)不允許中斷特點(diǎn): 核心常駐內(nèi)存, 短小精焊, 為進(jìn)程運(yùn)行提供舞臺(tái) 核心的組成中斷處理: 時(shí)鐘、I/O、虛擬存儲(chǔ)器進(jìn)程管理: 調(diào)度 控制 通訊 互斥 同步等原語(yǔ)管理: 提供一系列原語(yǔ),

16、 同步, 通信, 創(chuàng)建, 撤消等隊(duì)列管理:中斷之后調(diào)度之前(運(yùn)行-就緒-等待隊(duì)列)現(xiàn)場(chǎng)管理: 保存現(xiàn)場(chǎng)、恢復(fù)現(xiàn)場(chǎng)時(shí)鐘管理: 絕對(duì)時(shí)鐘、間隔時(shí)鐘、虛時(shí)鐘第22頁(yè)，共56頁(yè)。 保存現(xiàn)場(chǎng)、分析中斷源 處理中斷原語(yǔ)管理、隊(duì)列管理、時(shí)鐘管理、進(jìn)程調(diào)度 恢復(fù)現(xiàn)場(chǎng)中斷核心入口核心處理流程 唯一入口:中斷,由硬件完成 作業(yè): P101 2, 3, 5第23頁(yè)，共56頁(yè)。3.5死鎖死鎖的基本概念死鎖的解決方案 （預(yù)防，避免，檢測(cè)及解除）資源分配圖第24頁(yè)，共56頁(yè)。3.5.1 死鎖的基本概念死鎖(Deadlock)的定義： 一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到的資源，

17、這種現(xiàn)象稱(chēng)為進(jìn)程死鎖，這一組進(jìn)程就稱(chēng)為死鎖進(jìn)程說(shuō)明: 參與死鎖的進(jìn)程最少是兩個(gè)參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源注意：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。第25頁(yè)，共56頁(yè)。死鎖產(chǎn)生的原因1.競(jìng)爭(zhēng)資源引起永久性資源:可被多個(gè)進(jìn)程多次使用(可再用資源) 剝奪性資源(CPU、內(nèi)存） 非剝奪性資源(磁帶機(jī)、打印機(jī)) 競(jìng)爭(zhēng)非剝奪性資源會(huì)引起死鎖臨時(shí)性資源:只可使用一次的資源； 如信號(hào)量,中斷信號(hào),同步信號(hào)等(可消耗性資源) 競(jìng)爭(zhēng)臨時(shí)性資源也會(huì)引起死鎖2. 進(jìn)程推進(jìn)順序不當(dāng)引起 對(duì)資源采用“申請(qǐng)-分配-使用-釋放”模式, 由于推進(jìn)順序不當(dāng)兩進(jìn)程都要申請(qǐng)對(duì)方

18、已占有的資源第26頁(yè)，共56頁(yè)。P1： 申請(qǐng)打印機(jī)申請(qǐng)掃描儀使用釋放打印機(jī)釋放掃描儀P2： 申請(qǐng)掃描儀申請(qǐng)打印機(jī)使用釋放打印機(jī)釋放掃描儀死鎖的例子:競(jìng)爭(zhēng)非剝奪性資源進(jìn)程推進(jìn)順序不當(dāng)引起死鎖第27頁(yè)，共56頁(yè)。Req(R1) Req(R2) Rel(R1) Rel(R2)Rel(R1)Rel(R2)Req(R1)Req(R2)P2P1不安全區(qū)競(jìng)爭(zhēng)非剝奪性資源推進(jìn)順序不當(dāng)進(jìn)入不安全區(qū)第28頁(yè)，共56頁(yè)。3.5.2產(chǎn)生死鎖的四個(gè)必要條件1) 互斥條件（資源獨(dú)占）： 一個(gè)資源每次只能給一個(gè)進(jìn)程使用2) 請(qǐng)求和保持條件: (部分分配,占有申請(qǐng)) 在申請(qǐng)新資源的同時(shí)保持對(duì)原有資源的占有3) 不可剝奪條件（

19、不可強(qiáng)占）： 資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中奪取資源, 資源只能由占有者自愿釋放4) 循環(huán)等待條件： 存在進(jìn)程-等待資源環(huán)形鏈 P1 , P2 , , Pn, 其中P1等待P2占有的資源, P2等待P3占有的資源, , Pn等待P1占有的資源。第29頁(yè)，共56頁(yè)。3.6 死鎖的預(yù)防 3.6.1 強(qiáng)限制預(yù)防 確定資源分配算法,保證不發(fā)生死鎖。做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。1. 破壞“請(qǐng)求和保持(部分分配)”條件 每個(gè)進(jìn)程運(yùn)行前必須一次性申請(qǐng)運(yùn)行期所需全部資源, 若所需資源均可滿足則全部分配。該進(jìn)程運(yùn)行中不再請(qǐng)求資源, 屏棄請(qǐng)求條件。 簡(jiǎn)單、安全; 但資源利用率低,要長(zhǎng)期等待。2.

20、破壞“不可剝奪”條件 在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下, 規(guī)定: 某進(jìn)程在申請(qǐng)新的資源不能立即滿足而被阻塞之前, 必須釋放已占有的資源(可能造成前一段工作失效), 若需要再重新申請(qǐng)(增加開(kāi)銷(xiāo))。第30頁(yè)，共56頁(yè)。3.破壞“循環(huán)等待”條件 采用資源有序分配法:允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源, 對(duì)系統(tǒng)中所有資源編號(hào), 進(jìn)程申請(qǐng)資源時(shí)應(yīng)嚴(yán)格按資源編號(hào)遞增次序進(jìn)行,否則不予分配。P1：申請(qǐng)1申請(qǐng)3申請(qǐng)4P2：申請(qǐng)2申請(qǐng)4申請(qǐng)8Pn：申請(qǐng)1申請(qǐng)2申請(qǐng)8缺點(diǎn): 資源利用仍不充分第31頁(yè)，共56頁(yè)。3.6.2 避免死鎖的銀行家算法 前面的三種方法由于限制太強(qiáng), 資源利用率都不太高。能否放寬限制條件？ E.W.Dijks

21、tra于1968年提出銀行家算法, 此算法要事先知道每個(gè)進(jìn)程對(duì)資源的最大需求量; 算法的基本思路:允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源,但在每次分配資源前先對(duì)本次分配的安全性進(jìn)行檢查, 以判斷這種分配是否可能導(dǎo)致死鎖, 若分配可能導(dǎo)致系統(tǒng)死鎖, 則不予分配, 否則分配該資源。(檢查每次分配后是否仍存在安全分配序列) 顯然, 此法避免了死鎖且資源利用率高。第32頁(yè)，共56頁(yè)。1. 安全序列： 如果進(jìn)程序列P1，Pn對(duì)每個(gè)Pi(1in)進(jìn)程, 它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有Pj (j Available(2,3,0),讓P4等待4) 若P0請(qǐng)求資源,發(fā)出請(qǐng)求向量Request(0,2,0)假定

22、分配,資源為: 檢查此刻的安全性：Available(2,1,0)已不滿足任何進(jìn)程的需要, 不安全; 不予分配Available 仍為(2,3,0) 。 Max Allocation Need Available 進(jìn)程 A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1第40頁(yè)，共56頁(yè)。檢查此刻的安全性 Max Allocation Need Available 進(jìn)程 A B

23、C A B C A B C A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1安全, 可將(0,1,0)分配給P0若將P0請(qǐng)求改為Request(0,1,0)假定分配, 資源變?yōu)? 進(jìn) Work Allocation Need W+ A Finish 程 A B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 trueP3 5 2 2 2 1 1 0 1 1 7 3 3

24、 trueP4 7 3 3 0 0 2 4 3 1 7 3 5 trueP0 7 3 5 0 2 0 7 3 3 7 5 5 trueP2 7 5 5 3 0 2 6 0 0 10 5 7 true第41頁(yè)，共56頁(yè)。3.7 死鎖的檢測(cè)與解除 允許死鎖發(fā)生，系統(tǒng)必須提供檢測(cè)和解除死鎖的手段, 操作系統(tǒng)應(yīng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生。第42頁(yè)，共56頁(yè)。3.7.1死鎖的檢測(cè)1. 資源分配圖用有向圖描述進(jìn)程的死鎖: 準(zhǔn)確、形象 系統(tǒng)由若干類(lèi)資源構(gòu)成，一類(lèi)資源稱(chēng)為一個(gè)資源類(lèi)；每個(gè)資源類(lèi)中包含若干個(gè)同種資源，稱(chēng)為資源實(shí)例。二元組G=（V，E） V：結(jié)點(diǎn)集，分為P，R兩部分 P=p1,p2,p

25、n R=r1,r2,rm E：邊的集合, 其元素為有序二元組 分配邊(rj,pi): 資源實(shí)例進(jìn)程的一條有向邊申請(qǐng)邊(pi,rj): 進(jìn)程資源類(lèi)的一條有向邊第43頁(yè)，共56頁(yè)。有環(huán)有死鎖第44頁(yè)，共56頁(yè)。有環(huán)無(wú)死鎖第45頁(yè)，共56頁(yè)。2. 死鎖定理 如果資源分配圖中沒(méi)有環(huán)路, 則系統(tǒng)中沒(méi)有死鎖, 如果圖中存在環(huán)路則系統(tǒng)中可能存在死鎖。 如果每個(gè)資源類(lèi)中只包含一個(gè)資源實(shí)例, 則資源分配圖環(huán)路是死鎖存在的充分必要條件。資源分配圖化簡(jiǎn)方法：1）找一個(gè)非孤立點(diǎn)進(jìn)程結(jié)點(diǎn)且只有分配邊，去掉分配邊，將其變?yōu)楣铝⒔Y(jié)點(diǎn)。2）再把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，即將某進(jìn)程的申請(qǐng)邊變?yōu)榉峙溥叀?）重復(fù)(1)

26、 (2)操作直到無(wú)法再化簡(jiǎn), 若所有結(jié)點(diǎn)都為孤立結(jié)點(diǎn)則無(wú)死鎖, 否則死鎖發(fā)生第46頁(yè)，共56頁(yè)。3.7.2死鎖的解除 一旦死鎖發(fā)生則采取專(zhuān)門(mén)的措施，解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行。死鎖的解除(關(guān)鍵是代價(jià)最小)：1）重新啟動(dòng)2）撤消進(jìn)程3）剝奪資源4）進(jìn)程回退第47頁(yè)，共56頁(yè)。處理機(jī)調(diào)度 (1) 高級(jí)調(diào)度(作業(yè)調(diào)度接納調(diào)度或長(zhǎng)程調(diào)度) 將后備隊(duì)列中作業(yè)調(diào)入內(nèi)存,并創(chuàng)建進(jìn)程。 (2)低級(jí)調(diào)度(進(jìn)程調(diào)度,短程調(diào)度) 從就緒隊(duì)列中選中一進(jìn)程,把CPU使用權(quán)交給它。 (3)中級(jí)調(diào)度: 內(nèi)存緊張時(shí)將內(nèi)存的進(jìn)程掛起調(diào)到外存 或內(nèi)存稍有空閑時(shí)將它激活重新調(diào)入內(nèi)存 2. 進(jìn)程調(diào)度方式 (1)非搶占方式

27、(Non preemptive mode) (2)搶占方式(Preemptive mode)3. 進(jìn)程調(diào)度的時(shí)機(jī) (1) 執(zhí)行進(jìn)程正確完成 或錯(cuò)誤終止 (2) 執(zhí)行進(jìn)程提出I/O請(qǐng)求, 等待I/O完成時(shí); (3) 分時(shí)系統(tǒng)時(shí)間片輪轉(zhuǎn), 分給進(jìn)程的時(shí)間片用完時(shí) (4) 優(yōu)先級(jí)調(diào)度, 搶占方式中有更高優(yōu)先級(jí)進(jìn)程就緒 (5) 執(zhí)行進(jìn)程執(zhí)行wait、阻塞原語(yǔ)和喚醒原語(yǔ)等操作第48頁(yè)，共56頁(yè)。4. 調(diào)度算法(1)先進(jìn)先出調(diào)度算法(FIFO) (先來(lái)先服務(wù)FCFS)(2)短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法(SJF,SPF)(3)優(yōu)先權(quán)調(diào)度算法(HPFHighest Priority First)(4)高響應(yīng)比優(yōu)

28、先調(diào)度算法(5)時(shí)間片輪轉(zhuǎn)調(diào)度算法(6)多隊(duì)列反饋調(diào)度算法5. 常見(jiàn)的實(shí)時(shí)調(diào)度算法(1) 最早截止時(shí)間優(yōu)先算法(Earliest Deadline First)(2) 最低松弛度優(yōu)先算法(Least Laxity First)6. 調(diào)度的實(shí)現(xiàn)過(guò)程 保存現(xiàn)進(jìn)程現(xiàn)場(chǎng)、更新它的PCB、把它移至合適隊(duì)列 選擇要執(zhí)行的進(jìn)程、更新它的PCB、恢復(fù)新進(jìn)程現(xiàn)場(chǎng)第49頁(yè)，共56頁(yè)。7. 死鎖(Deadlock)的定義：進(jìn)程組中各進(jìn)程都無(wú)限等待被該組另一進(jìn)程所占的資源注意：參與死鎖的進(jìn)程最少是兩個(gè)、至少有兩個(gè) 已占有資源、該組所有進(jìn)程都在等待資源8.產(chǎn)生死鎖的四個(gè)必要條件 (1) 互斥條件(資源獨(dú)占): 一個(gè)資源

29、只能給一個(gè)進(jìn)程使用 (2) 請(qǐng)求和保持條件: 部分分配, 保持原資源申請(qǐng)新資源 (3) 不可剝奪條件: (不可強(qiáng)占, 只能由占有者自愿釋放) (4) 循環(huán)等待條件: 形成等待環(huán)9. 死鎖的預(yù)防(強(qiáng)限制) 破壞產(chǎn)生死鎖的四個(gè)必要條件之一(后3條)10. 避免死鎖的銀行家算法(寬限制) 檢查每次分配后是否仍存在安全分配序列 避免了死鎖且資源利用率高第50頁(yè)，共56頁(yè)。11. 死鎖的檢測(cè) 允許死鎖發(fā)生,OS應(yīng)不斷檢測(cè)死鎖是否發(fā)生12. 資源分配圖結(jié)點(diǎn)集: 各進(jìn)程結(jié)點(diǎn)P, 各資源類(lèi)結(jié)點(diǎn)R邊集: 元素為有序二元組, 分配邊(rj,pi) 申請(qǐng)邊(pi,rj) 13. 死鎖定理資源分配圖無(wú)環(huán)路, 則沒(méi)有死鎖, 有環(huán)路則可能存在死鎖 若各資源類(lèi)只含一個(gè)資源, 環(huán)路是死鎖的充分必要條件14. 資源分配圖化簡(jiǎn)方法() (1)找只有分配邊的進(jìn)程結(jié)點(diǎn),去掉分配邊變?yōu)楣铝⒔Y(jié)點(diǎn) (2)把相應(yīng)的資源分配給等待進(jìn)程, 申請(qǐng)邊變?yōu)榉峙溥?重復(fù)(1) (2) 直到無(wú)法再化簡(jiǎn), 若仍有環(huán)路則死鎖發(fā)生15. 死鎖的解除(關(guān)鍵是代價(jià)