太原理工大學(xué)操作系統(tǒng)-第三章處理機(jī)調(diào)度與死鎖

1、 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1 1第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的基本概念3.2 作業(yè)調(diào)度3.3 進(jìn)程調(diào)度3.4 死鎖 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2 23.1 處理機(jī)調(diào)度的基本概念 處理機(jī)資源是計(jì)算機(jī)系統(tǒng)中最重要的資源，它的調(diào)度處理機(jī)資源是計(jì)算機(jī)系統(tǒng)中最重要的資源，它的調(diào)度策略，常常表示操作系統(tǒng)的某種特征，其算法的優(yōu)劣直接策略，常常表示操作系統(tǒng)的某種特征，其算法的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。影響整個(gè)系統(tǒng)的性能。 處理機(jī)調(diào)度需要解決三個(gè)問(wèn)題：處理機(jī)調(diào)度需要解決三個(gè)問(wèn)題：(1) (1) 處理機(jī)分配的策略，即需要確定處理機(jī)的調(diào)度算法；處理機(jī)分配的策略，即需要確定處理機(jī)的調(diào)

2、度算法；(2) (2) 什么時(shí)候分配處理機(jī)，即需要確定處理機(jī)的調(diào)度時(shí)機(jī)；什么時(shí)候分配處理機(jī)，即需要確定處理機(jī)的調(diào)度時(shí)機(jī)；(3) (3) 如何分配處理機(jī)，即需要給出處理機(jī)的調(diào)度過(guò)程。如何分配處理機(jī)，即需要給出處理機(jī)的調(diào)度過(guò)程。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3 3一、處理機(jī)的分級(jí)調(diào)度：一、處理機(jī)的分級(jí)調(diào)度：1 1、作業(yè)調(diào)度（高級(jí)調(diào)度）：、作業(yè)調(diào)度（高級(jí)調(diào)度）： 按一定原則選擇按一定原則選擇若干個(gè)后備作業(yè)若干個(gè)后備作業(yè)調(diào)入主存調(diào)入主存，分配資，分配資源，并建立相應(yīng)的進(jìn)程，投入運(yùn)行。當(dāng)該作業(yè)執(zhí)行完畢源，并建立相應(yīng)的進(jìn)程，投入運(yùn)行。當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收資源。時(shí)，還負(fù)責(zé)回收資源。 在每次執(zhí)

3、行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。 1) 1) 接納多少個(gè)作業(yè)接納多少個(gè)作業(yè) 2) 2) 接納哪些作業(yè)接納哪些作業(yè) 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4 42 2、進(jìn)程調(diào)度（低級(jí)調(diào)度）：、進(jìn)程調(diào)度（低級(jí)調(diào)度）： （線程調(diào)度）（線程調(diào)度） 按照某種策略從進(jìn)程就緒隊(duì)列中選擇按照某種策略從進(jìn)程就緒隊(duì)列中選擇一個(gè)就緒進(jìn)程一個(gè)就緒進(jìn)程，使，使其其占有處理機(jī)占有處理機(jī)運(yùn)行。運(yùn)行。進(jìn)程調(diào)度方式：進(jìn)程調(diào)度方式： 1 1）非搶占式調(diào)度方式非搶占式調(diào)度方式 當(dāng)有重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，仍然讓正在執(zhí)當(dāng)有重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，仍然讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行

4、，直到該進(jìn)程完成任務(wù)終止運(yùn)行或發(fā)生某行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成任務(wù)終止運(yùn)行或發(fā)生某種等待事件而進(jìn)入阻塞狀態(tài)時(shí)，才主動(dòng)放棄占有的處理機(jī)，種等待事件而進(jìn)入阻塞狀態(tài)時(shí)，才主動(dòng)放棄占有的處理機(jī)，把處理機(jī)分配給重要或緊迫的就緒進(jìn)程，以使其運(yùn)行。把處理機(jī)分配給重要或緊迫的就緒進(jìn)程，以使其運(yùn)行。優(yōu)點(diǎn)：優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小。實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小。 適用于大多數(shù)的批處理系統(tǒng)環(huán)境。適用于大多數(shù)的批處理系統(tǒng)環(huán)境。 缺點(diǎn)：缺點(diǎn)：難以滿足緊急任務(wù)的要求難以滿足緊急任務(wù)的要求立即執(zhí)行，因而可能造立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)

5、系統(tǒng)中，不宜采用這種調(diào)度方式。不宜采用這種調(diào)度方式。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖5 5 2 2）搶占式調(diào)度方式搶占式調(diào)度方式 當(dāng)重要或緊迫的進(jìn)程一到，便把正在執(zhí)行的進(jìn)程占當(dāng)重要或緊迫的進(jìn)程一到，便把正在執(zhí)行的進(jìn)程占有的處理機(jī)強(qiáng)行剝奪下來(lái)，并轉(zhuǎn)給這個(gè)優(yōu)先級(jí)比它更高有的處理機(jī)強(qiáng)行剝奪下來(lái)，并轉(zhuǎn)給這個(gè)優(yōu)先級(jí)比它更高的重要或緊迫的就緒進(jìn)程，使其運(yùn)行。的重要或緊迫的就緒進(jìn)程，使其運(yùn)行。 搶占的原則：搶占的原則： (1) (1) 優(yōu)先權(quán)原則優(yōu)先權(quán)原則 (2) (2) 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先原則優(yōu)先原則 (3) (3) 時(shí)間片原則時(shí)間片原則 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖6 63

6、3）交換調(diào)度（中級(jí)調(diào)度）（均衡調(diào)度）：）交換調(diào)度（中級(jí)調(diào)度）（均衡調(diào)度）： 按照給定的原則實(shí)現(xiàn)按照給定的原則實(shí)現(xiàn)進(jìn)程進(jìn)程在主存和外存交換區(qū)之間的在主存和外存交換區(qū)之間的換進(jìn)換出換進(jìn)換出，以解決內(nèi)存緊張問(wèn)題，特別是具有虛擬存儲(chǔ)器，以解決內(nèi)存緊張問(wèn)題，特別是具有虛擬存儲(chǔ)器的系統(tǒng)中。的系統(tǒng)中。 引入中級(jí)調(diào)度的主要目的引入中級(jí)調(diào)度的主要目的: : 是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 為此，應(yīng)使那為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待。們調(diào)至外存上去等待。 操作系統(tǒng) 第三章 處理

7、機(jī)調(diào)度與死鎖7 7二、調(diào)度隊(duì)列模型二、調(diào)度隊(duì)列模型 1. 1. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 就 緒 隊(duì) 列阻 塞 隊(duì) 列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖8 82. 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型 就 緒 隊(duì) 列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件 1作業(yè)調(diào)度事件1出現(xiàn)時(shí)間片完等待事件 2事件2出現(xiàn)等待事件 n事件n出現(xiàn)后 備 隊(duì) 列 操作系統(tǒng) 第三章 處理機(jī)調(diào)度

8、與死鎖9 93. 3. 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型 就緒隊(duì)列進(jìn)程調(diào)度CPU就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn) 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1010三、三、 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 (1) (1) 作業(yè)周轉(zhuǎn)時(shí)間短。作業(yè)周轉(zhuǎn)時(shí)間短。 (2) (2) 響應(yīng)時(shí)間快。響應(yīng)時(shí)間快。 (3) (3) 截止時(shí)間的保證。截止時(shí)間的保證。 (4) (4) 優(yōu)先

9、權(quán)準(zhǔn)則。優(yōu)先權(quán)準(zhǔn)則。2.2.面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 (1) (1) 系統(tǒng)吞吐量高。系統(tǒng)吞吐量高。 (2) (2) 處理機(jī)利用率好。處理機(jī)利用率好。 (3) (3) 各類資源的平衡利用。各類資源的平衡利用。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖11113.2 作業(yè)調(diào)度一、作業(yè)的組織 程序程序 作業(yè)由三部分組成作業(yè)由三部分組成 數(shù)據(jù)數(shù)據(jù) 作業(yè)說(shuō)明書(shū)作業(yè)說(shuō)明書(shū) （說(shuō)明用戶的控制意圖）（說(shuō)明用戶的控制意圖） 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1212作業(yè)控制塊作業(yè)控制塊（JCBJCB）：為了管理和調(diào)度已進(jìn)入系統(tǒng)的各個(gè)作為了管理和調(diào)度已進(jìn)入系統(tǒng)的各個(gè)作業(yè)業(yè)，系統(tǒng)設(shè)置的用于記錄作業(yè)的基本情況的數(shù)據(jù)結(jié)構(gòu)

10、系統(tǒng)設(shè)置的用于記錄作業(yè)的基本情況的數(shù)據(jù)結(jié)構(gòu)。作業(yè)控制塊作業(yè)控制塊（JCBJCB）的主要內(nèi)容的主要內(nèi)容：(1)(1)作業(yè)的基本情況作業(yè)的基本情況 用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語(yǔ)言等。用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語(yǔ)言等。(2)(2)作業(yè)的控制要求作業(yè)的控制要求 控制方式、類型、優(yōu)先數(shù)、操作順序和出錯(cuò)處理等?？刂品绞健㈩愋?、優(yōu)先數(shù)、操作順序和出錯(cuò)處理等。(3)(3)作業(yè)的資源要求作業(yè)的資源要求 作業(yè)建立的時(shí)間、要求運(yùn)行的時(shí)間、最遲完成的時(shí)間、作業(yè)建立的時(shí)間、要求運(yùn)行的時(shí)間、最遲完成的時(shí)間、需要的主存容量、外設(shè)的種類及數(shù)量和資源使用情況。需要的主存容量、外設(shè)的種類及數(shù)量和資源使用情況。二、

11、作業(yè)控制塊二、作業(yè)控制塊 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1313作業(yè)名作業(yè)名資源要求資源要求估計(jì)執(zhí)行時(shí)間估計(jì)執(zhí)行時(shí)間最遲完成時(shí)間最遲完成時(shí)間要求的主存量要求的主存量要求外設(shè)的類型及臺(tái)數(shù)要求外設(shè)的類型及臺(tái)數(shù)要求文件量和輸出量要求文件量和輸出量資源使用情況資源使用情況進(jìn)入系統(tǒng)時(shí)間進(jìn)入系統(tǒng)時(shí)間開(kāi)始執(zhí)行時(shí)間開(kāi)始執(zhí)行時(shí)間已執(zhí)行時(shí)間已執(zhí)行時(shí)間主存地址主存地址外設(shè)臺(tái)號(hào)外設(shè)臺(tái)號(hào)類型類型控制方式控制方式作業(yè)類型作業(yè)類型優(yōu)先級(jí)優(yōu)先級(jí)狀態(tài)狀態(tài)作業(yè)控制塊作業(yè)控制塊聯(lián)機(jī)和脫機(jī)聯(lián)機(jī)和脫機(jī) 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1414 一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退

12、出系統(tǒng)，一般都要經(jīng)歷般都要經(jīng)歷4 4個(gè)狀態(tài)：個(gè)狀態(tài)：提交、后備（收容）、執(zhí)行和完成。提交、后備（收容）、執(zhí)行和完成。1 1）提交狀態(tài)：）提交狀態(tài)：通過(guò)終端設(shè)備向計(jì)算機(jī)的磁盤(pán)輸入作業(yè)信息通過(guò)終端設(shè)備向計(jì)算機(jī)的磁盤(pán)輸入作業(yè)信息時(shí)所處的狀態(tài)。時(shí)所處的狀態(tài)。2 2）后備狀態(tài)：）后備狀態(tài)：作業(yè)的全部信息已輸入到磁盤(pán)的一個(gè)專用區(qū)作業(yè)的全部信息已輸入到磁盤(pán)的一個(gè)專用區(qū)( (輸入井輸入井) )中等待作業(yè)調(diào)度時(shí)所處的狀態(tài)。中等待作業(yè)調(diào)度時(shí)所處的狀態(tài)。3 3）執(zhí)行狀態(tài)：）執(zhí)行狀態(tài)：在后備作業(yè)隊(duì)列中的作業(yè)一旦被作業(yè)調(diào)度程在后備作業(yè)隊(duì)列中的作業(yè)一旦被作業(yè)調(diào)度程序選中，為它分配了必要的資源，并且建立了進(jìn)程序選中，為它分

13、配了必要的資源，并且建立了進(jìn)程, , 開(kāi)始開(kāi)始處理時(shí)所處的狀態(tài)。處理時(shí)所處的狀態(tài)。4 4）完成狀態(tài)：）完成狀態(tài)：作業(yè)完成其全部任務(wù)后，進(jìn)程撤消作業(yè)完成其全部任務(wù)后，進(jìn)程撤消, , 做善后做善后處理時(shí)的作業(yè)狀態(tài)稱為完成狀態(tài)。處理時(shí)的作業(yè)狀態(tài)稱為完成狀態(tài)。三、作業(yè)的狀態(tài) 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1515四、作業(yè)狀態(tài)的轉(zhuǎn)換 作業(yè)的狀態(tài)及其轉(zhuǎn)換作業(yè)的狀態(tài)及其轉(zhuǎn)換 執(zhí)執(zhí)行行 進(jìn)程調(diào)度進(jìn)程調(diào)度 內(nèi)存內(nèi)存 線程調(diào)度線程調(diào)度運(yùn)運(yùn)行行等等待待就就緒緒外存外存 就就緒緒等等待待提提交交后后備備完完成成作業(yè)輸入作業(yè)輸入 作業(yè)調(diào)度作業(yè)調(diào)度 交換調(diào)度交換調(diào)度 作業(yè)調(diào)度作業(yè)調(diào)度 執(zhí)執(zhí)行行 操作系統(tǒng) 第三章 處理

14、機(jī)調(diào)度與死鎖1616五、作業(yè)調(diào)度的功能 作業(yè)調(diào)度的主要任務(wù)：作業(yè)調(diào)度的主要任務(wù)：完成作業(yè)從后備狀態(tài)到運(yùn)行狀態(tài)和完成作業(yè)從后備狀態(tài)到運(yùn)行狀態(tài)和從運(yùn)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。從運(yùn)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。1 1）記錄系統(tǒng)中各作業(yè)的狀況）記錄系統(tǒng)中各作業(yè)的狀況。 作業(yè)調(diào)度程序應(yīng)包括以下功能：作業(yè)調(diào)度程序應(yīng)包括以下功能： 作業(yè)調(diào)度程序?yàn)榱颂暨x一個(gè)作業(yè)投入運(yùn)行，并且在運(yùn)作業(yè)調(diào)度程序?yàn)榱颂暨x一個(gè)作業(yè)投入運(yùn)行，并且在運(yùn)行中對(duì)它實(shí)施管理，它必須掌握該作業(yè)進(jìn)入系統(tǒng)時(shí)的有關(guān)行中對(duì)它實(shí)施管理，它必須掌握該作業(yè)進(jìn)入系統(tǒng)時(shí)的有關(guān)情況并隨時(shí)記錄該作業(yè)在各運(yùn)行階段的變化。為此，系統(tǒng)情況并隨時(shí)記錄該作業(yè)在各運(yùn)行階段的變化。為此，

15、系統(tǒng)為每一個(gè)已進(jìn)入系統(tǒng)的作業(yè)分配一個(gè)為每一個(gè)已進(jìn)入系統(tǒng)的作業(yè)分配一個(gè)作業(yè)控制塊作業(yè)控制塊JCBJCB(Job (Job Contrl block)Contrl block)。每個(gè)作業(yè)的。每個(gè)作業(yè)的JCBJCB在該作業(yè)進(jìn)入后備狀態(tài)時(shí)在該作業(yè)進(jìn)入后備狀態(tài)時(shí)由系統(tǒng)建立在該作業(yè)退出系統(tǒng)時(shí)由系統(tǒng)撤消。每個(gè)作業(yè)由系統(tǒng)建立在該作業(yè)退出系統(tǒng)時(shí)由系統(tǒng)撤消。每個(gè)作業(yè)在各階段的情況在各階段的情況( (包括分配的資源和作業(yè)狀態(tài)等包括分配的資源和作業(yè)狀態(tài)等) )都記錄在都記錄在它的它的JCBJCB中。中。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖17172) 2) 按一定的調(diào)度算法，從后備作業(yè)中挑選出一個(gè)或幾個(gè)作按一定的調(diào)度

16、算法，從后備作業(yè)中挑選出一個(gè)或幾個(gè)作業(yè)運(yùn)行。業(yè)運(yùn)行。 系統(tǒng)中處于后備狀態(tài)的作業(yè)較多，幾十個(gè)甚至幾百個(gè)，系統(tǒng)中處于后備狀態(tài)的作業(yè)較多，幾十個(gè)甚至幾百個(gè)，處于運(yùn)行狀態(tài)的作業(yè)只是有限的幾個(gè)如最多不超過(guò)處于運(yùn)行狀態(tài)的作業(yè)只是有限的幾個(gè)如最多不超過(guò)4 4個(gè)或個(gè)或8 8個(gè)。個(gè)。作業(yè)調(diào)度程序的一個(gè)重要職能就是在適當(dāng)?shù)臅r(shí)候按一定的調(diào)作業(yè)調(diào)度程序的一個(gè)重要職能就是在適當(dāng)?shù)臅r(shí)候按一定的調(diào)度原則從后備作業(yè)中挑選出若干個(gè)作業(yè)投入運(yùn)行。度原則從后備作業(yè)中挑選出若干個(gè)作業(yè)投入運(yùn)行。3) 3) 為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。 為該作業(yè)建立相應(yīng)的進(jìn)程，并且為這些進(jìn)程提供所需的為該作業(yè)

17、建立相應(yīng)的進(jìn)程，并且為這些進(jìn)程提供所需的資源，如內(nèi)存和外部設(shè)備等。資源，如內(nèi)存和外部設(shè)備等。4) 4) 在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作。 輸出如運(yùn)行時(shí)間、作業(yè)執(zhí)行情況等必要信息，回收該作輸出如運(yùn)行時(shí)間、作業(yè)執(zhí)行情況等必要信息，回收該作業(yè)所占用的全部資源，撤消與該作業(yè)有關(guān)的全部進(jìn)程和該作業(yè)所占用的全部資源，撤消與該作業(yè)有關(guān)的全部進(jìn)程和該作業(yè)的作業(yè)控制塊。業(yè)的作業(yè)控制塊。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1818六、作業(yè)調(diào)度目標(biāo)與性能衡量 （1 1）公平性）公平性（2 2）均衡使用資源）均衡使用資源（3 3）較高的吞吐量）較高的吞吐量（4 4）較快的響應(yīng)時(shí)間）較快

18、的響應(yīng)時(shí)間1.1.調(diào)度目標(biāo)調(diào)度目標(biāo) 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖1919（1 1）周轉(zhuǎn)時(shí)間）周轉(zhuǎn)時(shí)間T Ti i = = 完成時(shí)刻完成時(shí)刻TcTci i 提交時(shí)刻提交時(shí)刻TsTsi i = = 等待時(shí)間等待時(shí)間TwTwi i + + 運(yùn)行時(shí)間運(yùn)行時(shí)間 TrTri i對(duì)于進(jìn)入系統(tǒng)的對(duì)于進(jìn)入系統(tǒng)的n n個(gè)作業(yè)而言，個(gè)作業(yè)而言，平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T T為為用于衡量不同調(diào)度算法對(duì)同一作業(yè)流的調(diào)度性能用于衡量不同調(diào)度算法對(duì)同一作業(yè)流的調(diào)度性能:平均周轉(zhuǎn)時(shí)間越小，該作業(yè)調(diào)度算法的性能越好。平均周轉(zhuǎn)時(shí)間越小，該作業(yè)調(diào)度算法的性能越好。 2.2.調(diào)度性能衡量指標(biāo)調(diào)度性能衡量指標(biāo)iiiTnT11n

19、操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2020(2)(2)帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Wi = TiWi = TiTriTri它能說(shuō)明作業(yè)它能說(shuō)明作業(yè)i i的相對(duì)等待時(shí)間。的相對(duì)等待時(shí)間。 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 用于衡量同一調(diào)度算法對(duì)不同作業(yè)流的調(diào)度性能：用于衡量同一調(diào)度算法對(duì)不同作業(yè)流的調(diào)度性能：平均帶權(quán)周轉(zhuǎn)時(shí)間越小，作業(yè)調(diào)度算法對(duì)該作業(yè)流的調(diào)度平均帶權(quán)周轉(zhuǎn)時(shí)間越小，作業(yè)調(diào)度算法對(duì)該作業(yè)流的調(diào)度性能越好。性能越好。 對(duì)于批處理系統(tǒng)，主要依據(jù)平均周轉(zhuǎn)時(shí)間和平均帶對(duì)于批處理系統(tǒng)，主要依據(jù)平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間來(lái)作為衡量調(diào)度算法性能的指標(biāo)；而對(duì)于分權(quán)周轉(zhuǎn)時(shí)間來(lái)作為衡量調(diào)度算法性能的指標(biāo)

20、；而對(duì)于分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)，外加平均響應(yīng)時(shí)間作為衡量調(diào)度算時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)，外加平均響應(yīng)時(shí)間作為衡量調(diào)度算法性能的指標(biāo)。法性能的指標(biāo)。 niSiiTTnW11Wi 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2121七、作業(yè)調(diào)度算法 按作業(yè)來(lái)到的先后次序進(jìn)行調(diào)度。這種算法優(yōu)先考慮按作業(yè)來(lái)到的先后次序進(jìn)行調(diào)度。這種算法優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)，而不管它要求運(yùn)行時(shí)間的在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)，而不管它要求運(yùn)行時(shí)間的長(zhǎng)短。長(zhǎng)短。優(yōu)點(diǎn)：優(yōu)點(diǎn)：容易實(shí)現(xiàn)；容易實(shí)現(xiàn)；缺點(diǎn)：缺點(diǎn)：沒(méi)有考慮各個(gè)作業(yè)運(yùn)行特征和資源要求的差異，系沒(méi)有考慮各個(gè)作業(yè)運(yùn)行特征和資源要求的差異，系統(tǒng)效率較低。統(tǒng)效率較低。1.1.先來(lái)先服

21、務(wù)調(diào)度算法（先來(lái)先服務(wù)調(diào)度算法（FCFSFCFS） 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2222例：先來(lái)先服務(wù)調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)）例：先來(lái)先服務(wù)調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)）作業(yè)作業(yè)提交時(shí)間提交時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.0010.50 2.00 4 3 9.00 0.1010.5010.60 1.60 16 4 9.50 0.2010.6010.80 1.30 6.5平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T T1.7251.725平均帶

22、權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W W6.8756.875 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖23232. 2. 短作業(yè)優(yōu)先調(diào)度算法（短作業(yè)優(yōu)先調(diào)度算法（SJFSJF） 此算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè)。此算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè)。優(yōu)點(diǎn)：優(yōu)點(diǎn)：易于實(shí)現(xiàn)，效率比較高。易于實(shí)現(xiàn)，效率比較高。缺點(diǎn)：缺點(diǎn)：只照顧短作業(yè)而不考慮長(zhǎng)作業(yè)的利益。只照顧短作業(yè)而不考慮長(zhǎng)作業(yè)的利益。 如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長(zhǎng)作業(yè)如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長(zhǎng)作業(yè)長(zhǎng)時(shí)間等待而不能運(yùn)行。長(zhǎng)時(shí)間等待而不能運(yùn)行。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2424例：短作業(yè)優(yōu)先調(diào)度算法（單位：小時(shí)

23、，并以十進(jìn)制計(jì)）例：短作業(yè)優(yōu)先調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)）作業(yè)作業(yè)提交時(shí)間提交時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.3010.80 2.30 4.6 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.1010.30 0.80 4平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T T1.551.55平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W W5.155.15 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖25253. 3. 響應(yīng)比高者優(yōu)先調(diào)度算法響應(yīng)比

24、高者優(yōu)先調(diào)度算法 響應(yīng)比是指作業(yè)的響應(yīng)時(shí)間與作業(yè)估計(jì)運(yùn)行時(shí)間的比響應(yīng)比是指作業(yè)的響應(yīng)時(shí)間與作業(yè)估計(jì)運(yùn)行時(shí)間的比值。值。執(zhí)執(zhí)行行時(shí)時(shí)間間響響應(yīng)應(yīng)時(shí)時(shí)間間響響應(yīng)應(yīng)比比 選擇原則是優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等選擇原則是優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等待時(shí)間長(zhǎng)和運(yùn)行時(shí)間短的作業(yè)，它是待時(shí)間長(zhǎng)和運(yùn)行時(shí)間短的作業(yè)，它是FCFSFCFS和和SJFSJF算法的結(jié)合。算法的結(jié)合。響應(yīng)比響應(yīng)比1 1作業(yè)等待時(shí)間作業(yè)等待時(shí)間/ /執(zhí)行時(shí)間執(zhí)行時(shí)間 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2626 作業(yè)作業(yè)提交時(shí)間提交時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

25、1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.1010.60 2.10 4.2 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.6010.80 1.30 6.5例：響應(yīng)比高者優(yōu)先調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)例：響應(yīng)比高者優(yōu)先調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì)) )平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間T T1.6251.625， 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間W W5.6755.675 響應(yīng)比響應(yīng)比1 1作業(yè)等待時(shí)間作業(yè)等待時(shí)間/ /執(zhí)行時(shí)間執(zhí)行時(shí)間例如：當(dāng)作業(yè)例如：當(dāng)作業(yè)3 3結(jié)束時(shí)，結(jié)束時(shí)，Rp2= 1Rp2= 1作

26、業(yè)等待時(shí)間作業(yè)等待時(shí)間/ /可執(zhí)行時(shí)間可執(zhí)行時(shí)間=1+(10.10-8.50)/0.5=1+3.2=1+(10.10-8.50)/0.5=1+3.2Rp4= 1Rp4= 1作業(yè)等待時(shí)間作業(yè)等待時(shí)間/ /可執(zhí)行時(shí)間可執(zhí)行時(shí)間=1+(10.10-9.50)/0.2=1+3=1+(10.10-9.50)/0.2=1+3 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖2727 這種算法是根據(jù)確定的優(yōu)先數(shù)來(lái)選取作業(yè)，每次總是選這種算法是根據(jù)確定的優(yōu)先數(shù)來(lái)選取作業(yè)，每次總是選擇優(yōu)先級(jí)最高的作業(yè)。擇優(yōu)先級(jí)最高的作業(yè)。 4.4.最高優(yōu)先級(jí)優(yōu)先調(diào)度算法最高優(yōu)先級(jí)優(yōu)先調(diào)度算法規(guī)定用戶作業(yè)優(yōu)先數(shù)的方法規(guī)定用戶作業(yè)優(yōu)先數(shù)的方法:

27、 :1 1）由用戶自己提出作業(yè)的優(yōu)先數(shù)。）由用戶自己提出作業(yè)的優(yōu)先數(shù)。有的用戶為了自己的作業(yè)有的用戶為了自己的作業(yè)盡快被系統(tǒng)選中就設(shè)法提高自己作業(yè)的優(yōu)先數(shù)，這時(shí)系統(tǒng)可以盡快被系統(tǒng)選中就設(shè)法提高自己作業(yè)的優(yōu)先數(shù)，這時(shí)系統(tǒng)可以規(guī)定優(yōu)先數(shù)越高則需付出的計(jì)算機(jī)使用費(fèi)就越多，以作限制。規(guī)定優(yōu)先數(shù)越高則需付出的計(jì)算機(jī)使用費(fèi)就越多，以作限制。2 2）由系統(tǒng)綜合有關(guān)因素來(lái)確定用戶作業(yè)的優(yōu)先數(shù)。）由系統(tǒng)綜合有關(guān)因素來(lái)確定用戶作業(yè)的優(yōu)先數(shù)。 例如，根據(jù)作業(yè)的緩急程度、作業(yè)計(jì)算時(shí)間的長(zhǎng)短、等待例如，根據(jù)作業(yè)的緩急程度、作業(yè)計(jì)算時(shí)間的長(zhǎng)短、等待時(shí)間的多少、資源申請(qǐng)情況等來(lái)確定優(yōu)先數(shù)。確定優(yōu)先數(shù)時(shí)，時(shí)間的多少、資源申請(qǐng)

28、情況等來(lái)確定優(yōu)先數(shù)。確定優(yōu)先數(shù)時(shí)，各因素的比例應(yīng)根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)來(lái)分析這些因素在系統(tǒng)中的各因素的比例應(yīng)根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)來(lái)分析這些因素在系統(tǒng)中的地位而決定。地位而決定。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖28283.3 進(jìn)程調(diào)度進(jìn)程調(diào)度：進(jìn)程調(diào)度：就是系統(tǒng)按照某種算法把就是系統(tǒng)按照某種算法把CPUCPU動(dòng)態(tài)地分配給某一就動(dòng)態(tài)地分配給某一就緒進(jìn)程。進(jìn)程調(diào)度工作是通過(guò)進(jìn)程調(diào)度程序來(lái)完成的。緒進(jìn)程。進(jìn)程調(diào)度工作是通過(guò)進(jìn)程調(diào)度程序來(lái)完成的。一、調(diào)度/分派結(jié)構(gòu)調(diào)度程序：調(diào)度程序：將進(jìn)程插入就緒隊(duì)列，按一定原則保持隊(duì)列結(jié)構(gòu)；將進(jìn)程插入就緒隊(duì)列，按一定原則保持隊(duì)列結(jié)構(gòu)；分派程序：分派程序：將進(jìn)程從就緒隊(duì)列中移

29、出，建立它執(zhí)行的機(jī)器狀態(tài)。將進(jìn)程從就緒隊(duì)列中移出，建立它執(zhí)行的機(jī)器狀態(tài)。進(jìn)程切換進(jìn)程切換：把一個(gè)進(jìn)程讓出處理機(jī)，由另一個(gè)進(jìn)程占用處理機(jī)把一個(gè)進(jìn)程讓出處理機(jī)，由另一個(gè)進(jìn)程占用處理機(jī)的調(diào)度過(guò)程稱為的調(diào)度過(guò)程稱為“進(jìn)程切換進(jìn)程切換”。 分派程序首先將正在執(zhí)行的進(jìn)程的分派程序首先將正在執(zhí)行的進(jìn)程的CPUCPU現(xiàn)場(chǎng)信息保存在該進(jìn)現(xiàn)場(chǎng)信息保存在該進(jìn)程程PCBPCB的現(xiàn)場(chǎng)保護(hù)區(qū)中，再?gòu)谋徽{(diào)度選中的進(jìn)程的現(xiàn)場(chǎng)保護(hù)區(qū)中，再?gòu)谋徽{(diào)度選中的進(jìn)程PCBPCB的現(xiàn)場(chǎng)保護(hù)的現(xiàn)場(chǎng)保護(hù)區(qū)中取出它的區(qū)中取出它的CPUCPU現(xiàn)場(chǎng)信息恢復(fù)?，F(xiàn)場(chǎng)信息恢復(fù)。CPUCPU現(xiàn)場(chǎng)信息由程序狀態(tài)寄存現(xiàn)場(chǎng)信息由程序狀態(tài)寄存器、程序計(jì)數(shù)器以及若干

30、通用寄存器的內(nèi)容組成。器、程序計(jì)數(shù)器以及若干通用寄存器的內(nèi)容組成。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖29291.1.記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況。記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況。 二、進(jìn)程調(diào)度功能 記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況，對(duì)進(jìn)程控制塊記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況，對(duì)進(jìn)程控制塊PCBPCB的內(nèi)的內(nèi)容作相應(yīng)的登記、修改，記錄進(jìn)程的狀態(tài)特征。容作相應(yīng)的登記、修改，記錄進(jìn)程的狀態(tài)特征。2.2.按照一定調(diào)度策略選擇一個(gè)占有處理機(jī)的就緒進(jìn)程。按照一定調(diào)度策略選擇一個(gè)占有處理機(jī)的就緒進(jìn)程。 在處理機(jī)空閑時(shí)根據(jù)一定的原則選擇一個(gè)進(jìn)程去運(yùn)行，在處理機(jī)空閑時(shí)根據(jù)一定的原則選擇一個(gè)進(jìn)程去運(yùn)行，同時(shí)確定獲得處理

31、機(jī)的時(shí)間。同時(shí)確定獲得處理機(jī)的時(shí)間。3.3.實(shí)施處理機(jī)的分配和回收實(shí)施處理機(jī)的分配和回收( (進(jìn)行進(jìn)程上下文切換進(jìn)行進(jìn)程上下文切換)?；厥栈厥? :正在運(yùn)行的進(jìn)程由于某種原因讓出處理機(jī)，該進(jìn)程的狀正在運(yùn)行的進(jìn)程由于某種原因讓出處理機(jī)，該進(jìn)程的狀態(tài)改為態(tài)改為“阻塞阻塞”，插入到相應(yīng)隊(duì)列中，保留該進(jìn)程的，插入到相應(yīng)隊(duì)列中，保留該進(jìn)程的CPUCPU現(xiàn)場(chǎng)?，F(xiàn)場(chǎng)。分配分配: :根據(jù)調(diào)度原則選擇進(jìn)程去運(yùn)行，把選中進(jìn)程從就緒隊(duì)列中根據(jù)調(diào)度原則選擇進(jìn)程去運(yùn)行，把選中進(jìn)程從就緒隊(duì)列中移出移出, ,改狀態(tài)為改狀態(tài)為“運(yùn)行運(yùn)行”，把，把CPUCPU控制權(quán)交給被選中的進(jìn)程，將控制權(quán)交給被選中的進(jìn)程，將選中進(jìn)程的有關(guān)選

32、中進(jìn)程的有關(guān)PCBPCB現(xiàn)場(chǎng)信息，分別送到相應(yīng)的寄存器中。現(xiàn)場(chǎng)信息，分別送到相應(yīng)的寄存器中。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3030三、進(jìn)程調(diào)度時(shí)機(jī) 1 1）正在執(zhí)行的進(jìn)程完成其任務(wù)而正在執(zhí)行的進(jìn)程完成其任務(wù)而運(yùn)行完畢運(yùn)行完畢。 2 2）執(zhí)行中的進(jìn)程由于執(zhí)行中的進(jìn)程由于請(qǐng)求某個(gè)事件的發(fā)生請(qǐng)求某個(gè)事件的發(fā)生，比如，比如I/OI/O請(qǐng)求，請(qǐng)求，等待所需要的信號(hào)、信件的到來(lái)等而自己調(diào)用等待所需要的信號(hào)、信件的到來(lái)等而自己調(diào)用阻塞阻塞原語(yǔ)將自原語(yǔ)將自己阻塞起來(lái)，進(jìn)入相應(yīng)的等待隊(duì)列。己阻塞起來(lái)，進(jìn)入相應(yīng)的等待隊(duì)列。 3 3）在分時(shí)系統(tǒng)中，當(dāng)進(jìn)程使在分時(shí)系統(tǒng)中，當(dāng)進(jìn)程使用完規(guī)定的時(shí)間片用完規(guī)定的時(shí)間片

33、。 4 4）在在采用可搶占采用可搶占調(diào)度方式的系統(tǒng)中，當(dāng)具有更高優(yōu)先級(jí)的調(diào)度方式的系統(tǒng)中，當(dāng)具有更高優(yōu)先級(jí)的進(jìn)程要求使用處理機(jī)。進(jìn)程要求使用處理機(jī)。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3131四、進(jìn)程調(diào)度算法 采用最高優(yōu)先級(jí)優(yōu)先調(diào)度算法時(shí)，系統(tǒng)對(duì)每個(gè)進(jìn)程確采用最高優(yōu)先級(jí)優(yōu)先調(diào)度算法時(shí)，系統(tǒng)對(duì)每個(gè)進(jìn)程確定一個(gè)優(yōu)先數(shù)，進(jìn)程的優(yōu)先數(shù)用于表示進(jìn)程的重要性及運(yùn)定一個(gè)優(yōu)先數(shù)，進(jìn)程的優(yōu)先數(shù)用于表示進(jìn)程的重要性及運(yùn)行的優(yōu)先性。調(diào)度時(shí)，系統(tǒng)把處理機(jī)分配給優(yōu)先級(jí)最高的行的優(yōu)先性。調(diào)度時(shí)，系統(tǒng)把處理機(jī)分配給優(yōu)先級(jí)最高的就緒進(jìn)程。如果就緒進(jìn)程具有相同的優(yōu)先數(shù)，則再按先來(lái)就緒進(jìn)程。如果就緒進(jìn)程具有相同的優(yōu)先數(shù)，則再按先

34、來(lái)先服務(wù)的次序分配處理機(jī)。先服務(wù)的次序分配處理機(jī)。 先來(lái)先服務(wù)調(diào)度算法是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后先來(lái)先服務(wù)調(diào)度算法是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)選擇進(jìn)程分配處理機(jī)。次序來(lái)選擇進(jìn)程分配處理機(jī)。（一）最高優(yōu)先級(jí)優(yōu)先調(diào)度算法 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3232系統(tǒng)確定優(yōu)先數(shù)的方法： 1.1.靜態(tài)優(yōu)先數(shù)法：靜態(tài)優(yōu)先數(shù)法：靜態(tài)優(yōu)先數(shù)是在創(chuàng)建進(jìn)程時(shí)系統(tǒng)為其確靜態(tài)優(yōu)先數(shù)是在創(chuàng)建進(jìn)程時(shí)系統(tǒng)為其確定的，并且在進(jìn)程的生命期內(nèi)不再改變。定的，并且在進(jìn)程的生命期內(nèi)不再改變。 確定靜態(tài)優(yōu)先數(shù)的原則：確定靜態(tài)優(yōu)先數(shù)的原則：1 1）按進(jìn)程類型。）按進(jìn)程類型。系統(tǒng)進(jìn)程的優(yōu)先級(jí)高于用戶進(jìn)程的優(yōu)先級(jí)。系統(tǒng)進(jìn)程的優(yōu)先

35、級(jí)高于用戶進(jìn)程的優(yōu)先級(jí)。 2 2）按進(jìn)程使用的資源。）按進(jìn)程使用的資源。進(jìn)程所使用的資源越多，進(jìn)程的優(yōu)進(jìn)程所使用的資源越多，進(jìn)程的優(yōu)先級(jí)越低；反之，則進(jìn)程的優(yōu)先級(jí)越高。先級(jí)越低；反之，則進(jìn)程的優(yōu)先級(jí)越高。 3 3）按進(jìn)程的估計(jì)運(yùn)行時(shí)間。）按進(jìn)程的估計(jì)運(yùn)行時(shí)間。進(jìn)程的估計(jì)運(yùn)行時(shí)間越長(zhǎng)，進(jìn)進(jìn)程的估計(jì)運(yùn)行時(shí)間越長(zhǎng)，進(jìn)程的優(yōu)先級(jí)越低；反之，則進(jìn)程的優(yōu)先級(jí)越高。程的優(yōu)先級(jí)越低；反之，則進(jìn)程的優(yōu)先級(jí)越高。 4 4）由用戶指定。）由用戶指定。有些系統(tǒng)可以按收費(fèi)標(biāo)準(zhǔn)不同，設(shè)置不同的有些系統(tǒng)可以按收費(fèi)標(biāo)準(zhǔn)不同，設(shè)置不同的優(yōu)先級(jí)別，可以由用戶指定。優(yōu)先級(jí)別，可以由用戶指定。 靜態(tài)優(yōu)先級(jí)法實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，但不能反

36、映系統(tǒng)以及進(jìn)程靜態(tài)優(yōu)先級(jí)法實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，但不能反映系統(tǒng)以及進(jìn)程在運(yùn)行過(guò)程中的動(dòng)態(tài)變化情況，系統(tǒng)管理效果顯然不佳。在運(yùn)行過(guò)程中的動(dòng)態(tài)變化情況，系統(tǒng)管理效果顯然不佳。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖33332. 2. 動(dòng)態(tài)優(yōu)先數(shù)法。動(dòng)態(tài)優(yōu)先數(shù)法。動(dòng)態(tài)優(yōu)先數(shù)是指在系統(tǒng)創(chuàng)建進(jìn)程時(shí)，根動(dòng)態(tài)優(yōu)先數(shù)是指在系統(tǒng)創(chuàng)建進(jìn)程時(shí)，根據(jù)系統(tǒng)資源的使用情況和進(jìn)程的當(dāng)前特點(diǎn)確定一個(gè)優(yōu)先數(shù)，據(jù)系統(tǒng)資源的使用情況和進(jìn)程的當(dāng)前特點(diǎn)確定一個(gè)優(yōu)先數(shù)，然后，在進(jìn)程運(yùn)行過(guò)程中再根據(jù)情況的變化動(dòng)態(tài)調(diào)整進(jìn)程的然后，在進(jìn)程運(yùn)行過(guò)程中再根據(jù)情況的變化動(dòng)態(tài)調(diào)整進(jìn)程的優(yōu)先數(shù)。優(yōu)先數(shù)。 調(diào)整進(jìn)程優(yōu)先數(shù)的原調(diào)整進(jìn)程優(yōu)先數(shù)的原則：則： 1 1）進(jìn)

37、程占有處理機(jī)的時(shí)間越長(zhǎng)，則進(jìn)程的優(yōu)先級(jí)越低；進(jìn)程）進(jìn)程占有處理機(jī)的時(shí)間越長(zhǎng)，則進(jìn)程的優(yōu)先級(jí)越低；進(jìn)程的等待時(shí)間越長(zhǎng)，則進(jìn)程的優(yōu)先級(jí)越高。的等待時(shí)間越長(zhǎng)，則進(jìn)程的優(yōu)先級(jí)越高。 2 2）根據(jù)進(jìn)程所執(zhí)行的程序的輕重緩急程度，調(diào)整進(jìn)程的優(yōu)先）根據(jù)進(jìn)程所執(zhí)行的程序的輕重緩急程度，調(diào)整進(jìn)程的優(yōu)先數(shù)。數(shù)。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3434優(yōu)先權(quán)的變化規(guī)律：優(yōu)先權(quán)的變化規(guī)律： (1) (1) 如果進(jìn)程（作業(yè)）的等待時(shí)間相同，則要求服如果進(jìn)程（作業(yè)）的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短進(jìn)務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短進(jìn)程（作業(yè)）。程（作業(yè)）。 (2)

38、(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，進(jìn)程（作業(yè)）的優(yōu)當(dāng)要求服務(wù)的時(shí)間相同時(shí)，進(jìn)程（作業(yè)）的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。 (3) (3) 對(duì)于長(zhǎng)進(jìn)程（作業(yè)），進(jìn)程（作業(yè)）的優(yōu)先級(jí)對(duì)于長(zhǎng)進(jìn)程（作業(yè)），進(jìn)程（作業(yè)）的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，其優(yōu)先級(jí)便可升到很高， 從而也可獲得處理機(jī)（進(jìn)入主從而也可獲得處理機(jī)（進(jìn)入主存）。存）。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3535（二）時(shí)

39、間片輪轉(zhuǎn)調(diào)度算法 在分時(shí)系統(tǒng)中，為了滿足系統(tǒng)對(duì)響應(yīng)時(shí)間的要求，通在分時(shí)系統(tǒng)中，為了滿足系統(tǒng)對(duì)響應(yīng)時(shí)間的要求，通常采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。常采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。 1. 簡(jiǎn)單輪轉(zhuǎn)法(固定時(shí)間片輪轉(zhuǎn)法） 在這種調(diào)度算法中，系統(tǒng)把所有就緒進(jìn)程按到達(dá)的先在這種調(diào)度算法中，系統(tǒng)把所有就緒進(jìn)程按到達(dá)的先后順序形成一個(gè)就緒隊(duì)列，就緒隊(duì)列中的所有進(jìn)程按時(shí)間后順序形成一個(gè)就緒隊(duì)列，就緒隊(duì)列中的所有進(jìn)程按時(shí)間片依次輪流獲得處理機(jī)。片依次輪流獲得處理機(jī)。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3636 時(shí)間片的大小應(yīng)根據(jù)進(jìn)程要求系統(tǒng)給出應(yīng)答的時(shí)間和進(jìn)時(shí)間片的大小應(yīng)根據(jù)進(jìn)程要求系統(tǒng)給出應(yīng)答的時(shí)間和進(jìn)入系統(tǒng)的進(jìn)程數(shù)來(lái)決定

40、?？梢员硎緸椋喝胂到y(tǒng)的進(jìn)程數(shù)來(lái)決定?？梢员硎緸椋?N NT Tq q 其中，其中，q q是時(shí)間片的大小，是時(shí)間片的大小，T T是系統(tǒng)的響應(yīng)時(shí)間，是系統(tǒng)的響應(yīng)時(shí)間，N N是進(jìn)入系統(tǒng)是進(jìn)入系統(tǒng)的進(jìn)程數(shù)。的進(jìn)程數(shù)。 簡(jiǎn)單輪轉(zhuǎn)法的優(yōu)點(diǎn)是簡(jiǎn)單、方便，但由于采用固定時(shí)間簡(jiǎn)單輪轉(zhuǎn)法的優(yōu)點(diǎn)是簡(jiǎn)單、方便，但由于采用固定時(shí)間片的方式，調(diào)度欠靈活，服務(wù)質(zhì)量不夠理想。可以通過(guò)以下片的方式，調(diào)度欠靈活，服務(wù)質(zhì)量不夠理想?？梢酝ㄟ^(guò)以下兩個(gè)方面加以改進(jìn)：兩個(gè)方面加以改進(jìn)：1 1）將固定時(shí)間片方式改為可變時(shí)間片方式；）將固定時(shí)間片方式改為可變時(shí)間片方式；2 2）將單就緒隊(duì)列改為多就緒隊(duì)列。）將單就緒隊(duì)列改為多就緒隊(duì)列。 操作

41、系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖37372. 可變時(shí)間片輪轉(zhuǎn)法 時(shí)間片可變會(huì)給系統(tǒng)帶來(lái)好處。如果要求系統(tǒng)快速應(yīng)時(shí)間片可變會(huì)給系統(tǒng)帶來(lái)好處。如果要求系統(tǒng)快速應(yīng)答，則時(shí)間片小一些，這樣可使輪轉(zhuǎn)一遍的總時(shí)間減少而答，則時(shí)間片小一些，這樣可使輪轉(zhuǎn)一遍的總時(shí)間減少而可對(duì)進(jìn)程盡快應(yīng)答。如果進(jìn)程數(shù)少，則時(shí)間片可以大一些，可對(duì)進(jìn)程盡快應(yīng)答。如果進(jìn)程數(shù)少，則時(shí)間片可以大一些，這樣可減少進(jìn)程調(diào)度的次數(shù)，提高系統(tǒng)效率。這樣可減少進(jìn)程調(diào)度的次數(shù)，提高系統(tǒng)效率。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖3838可變時(shí)間片輪轉(zhuǎn)法中，可采取如下措施調(diào)整時(shí)間片：可變時(shí)間片輪轉(zhuǎn)法中，可采取如下措施調(diào)整時(shí)間片： 1) 1) 固定周期輪轉(zhuǎn)

42、法。固定周期輪轉(zhuǎn)法。 在這種方法中，每一輪調(diào)度中所得的時(shí)間片在這種方法中，每一輪調(diào)度中所得的時(shí)間片q q值的大值的大小僅在這一輪調(diào)度中有效。系統(tǒng)的響應(yīng)時(shí)間小僅在這一輪調(diào)度中有效。系統(tǒng)的響應(yīng)時(shí)間T T固定，在每一固定，在每一輪調(diào)度中，根據(jù)當(dāng)前就緒隊(duì)列中的進(jìn)程數(shù)輪調(diào)度中，根據(jù)當(dāng)前就緒隊(duì)列中的進(jìn)程數(shù)n n計(jì)算這一輪調(diào)度計(jì)算這一輪調(diào)度的時(shí)間片：的時(shí)間片：q qT/ n T/ n ， 然后進(jìn)行輪轉(zhuǎn)，每個(gè)進(jìn)程可獲得然后進(jìn)行輪轉(zhuǎn)，每個(gè)進(jìn)程可獲得這一輪的一個(gè)時(shí)間片這一輪的一個(gè)時(shí)間片q q。在此期間所到達(dá)的進(jìn)程暫不進(jìn)入。在此期間所到達(dá)的進(jìn)程暫不進(jìn)入就緒隊(duì)列，等此次輪轉(zhuǎn)完畢再一并進(jìn)入。系統(tǒng)根據(jù)此時(shí)就緒就緒隊(duì)列，等

43、此次輪轉(zhuǎn)完畢再一并進(jìn)入。系統(tǒng)根據(jù)此時(shí)就緒隊(duì)列的進(jìn)程數(shù)重新計(jì)算時(shí)間片隊(duì)列的進(jìn)程數(shù)重新計(jì)算時(shí)間片q q，然后開(kāi)始下一輪循環(huán)。，然后開(kāi)始下一輪循環(huán)。 2) 2) 時(shí)間片的大小取決于優(yōu)先級(jí)的高低時(shí)間片的大小取決于優(yōu)先級(jí)的高低，優(yōu)先級(jí)高的進(jìn)程分，優(yōu)先級(jí)高的進(jìn)程分得的時(shí)間片較大，優(yōu)先級(jí)低的進(jìn)程分得的時(shí)間片較小。得的時(shí)間片較大，優(yōu)先級(jí)低的進(jìn)程分得的時(shí)間片較小。 3) 3) 短作業(yè)的時(shí)間片較小，短作業(yè)的時(shí)間片較小，長(zhǎng)作業(yè)的時(shí)間片較大。長(zhǎng)作業(yè)的時(shí)間片較大。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖39393.多級(jí)反饋輪轉(zhuǎn)法（多重時(shí)間片輪轉(zhuǎn)調(diào)度算法） 調(diào)度算法的實(shí)施過(guò)程如下：調(diào)度算法的實(shí)施過(guò)程如下： 1. 1. 設(shè)置多

44、個(gè)就緒隊(duì)列，設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)就緒隊(duì)列賦予不同的優(yōu)先并為各個(gè)就緒隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)就緒隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)就緒隊(duì)列的優(yōu)先級(jí)。第一個(gè)就緒隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)就緒隊(duì)列的優(yōu)先級(jí)次之，其余各個(gè)就緒隊(duì)列的優(yōu)先級(jí)逐個(gè)降低。級(jí)次之，其余各個(gè)就緒隊(duì)列的優(yōu)先級(jí)逐個(gè)降低。2.2.賦予各個(gè)就緒隊(duì)列中進(jìn)程賦予各個(gè)就緒隊(duì)列中進(jìn)程的時(shí)間片也各不相同，優(yōu)先級(jí)越的時(shí)間片也各不相同，優(yōu)先級(jí)越高的就緒隊(duì)列中的進(jìn)程的時(shí)間片越小，反之，優(yōu)先級(jí)越低的高的就緒隊(duì)列中的進(jìn)程的時(shí)間片越小，反之，優(yōu)先級(jí)越低的就緒隊(duì)列中的進(jìn)程的時(shí)間片越大。就緒隊(duì)列中的進(jìn)程的時(shí)間片越大。 3.3.當(dāng)一個(gè)新被創(chuàng)建的進(jìn)程當(dāng)一個(gè)新被創(chuàng)建的進(jìn)程

45、進(jìn)入就緒隊(duì)列后，首先將它加入第進(jìn)入就緒隊(duì)列后，首先將它加入第一個(gè)就緒隊(duì)列的隊(duì)尾，按先來(lái)先服務(wù)的原則排隊(duì)等待調(diào)度。一個(gè)就緒隊(duì)列的隊(duì)尾，按先來(lái)先服務(wù)的原則排隊(duì)等待調(diào)度。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4040 當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如能在該時(shí)間片內(nèi)完成，則該進(jìn)當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如能在該時(shí)間片內(nèi)完成，則該進(jìn)程將被撤消；如果在一個(gè)時(shí)間片結(jié)束時(shí)該進(jìn)程尚未完成，調(diào)程將被撤消；如果在一個(gè)時(shí)間片結(jié)束時(shí)該進(jìn)程尚未完成，調(diào)度程序則將該進(jìn)程轉(zhuǎn)入第二個(gè)就緒隊(duì)列的隊(duì)尾，按先來(lái)先服度程序則將該進(jìn)程轉(zhuǎn)入第二個(gè)就緒隊(duì)列的隊(duì)尾，按先來(lái)先服務(wù)的原則排隊(duì)等待調(diào)度；如果它在第二個(gè)就緒隊(duì)列中運(yùn)行一務(wù)的原則排隊(duì)等待調(diào)度；如果它在第二

46、個(gè)就緒隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再以同樣的方法將它轉(zhuǎn)入第三個(gè)就緒個(gè)時(shí)間片后仍未完成，再以同樣的方法將它轉(zhuǎn)入第三個(gè)就緒隊(duì)列的隊(duì)尾，隊(duì)列的隊(duì)尾， 如此下去。如此下去。4.4.僅當(dāng)?shù)谝粋€(gè)就緒隊(duì)列空閑時(shí)，僅當(dāng)?shù)谝粋€(gè)就緒隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二個(gè)就緒調(diào)度程序才調(diào)度第二個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)陉?duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)? 1至第至第i i1 1個(gè)就緒隊(duì)列均為空時(shí)，個(gè)就緒隊(duì)列均為空時(shí)，才會(huì)調(diào)度第才會(huì)調(diào)度第i i個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行。個(gè)就緒隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第如果處理機(jī)正在第i i個(gè)就緒隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高個(gè)就緒隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先

47、級(jí)較高的就緒隊(duì)列時(shí)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，的就緒隊(duì)列時(shí)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i i個(gè)就緒隊(duì)列的隊(duì)個(gè)就緒隊(duì)列的隊(duì)尾，然后將處理機(jī)重新分配給新進(jìn)程。尾，然后將處理機(jī)重新分配給新進(jìn)程。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4141多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 就緒隊(duì)列 1就緒隊(duì)列 2就緒隊(duì)列 3就緒隊(duì)列 nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片： S1 S2 S3) 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖42423.4 死鎖 一、死鎖的概念死鎖：死鎖：各并發(fā)進(jìn)程彼此互相等

48、待對(duì)方所擁有的資源，且這各并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源。從而造成系統(tǒng)中一些進(jìn)程處于無(wú)休止的等待狀態(tài)，資源。從而造成系統(tǒng)中一些進(jìn)程處于無(wú)休止的等待狀態(tài)，在無(wú)外力作用的情況下，這些進(jìn)程永遠(yuǎn)也不能繼續(xù)前進(jìn)。在無(wú)外力作用的情況下，這些進(jìn)程永遠(yuǎn)也不能繼續(xù)前進(jìn)。我們稱這種現(xiàn)象為我們稱這種現(xiàn)象為死鎖死鎖。例：例：系統(tǒng)中只有一臺(tái)輸入機(jī)系統(tǒng)中只有一臺(tái)輸入機(jī)R1R1和一臺(tái)打印機(jī)和一臺(tái)打印機(jī)R2R2可供進(jìn)程可供進(jìn)程P1P1和和P2P2共享。共享。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4343進(jìn)程進(jìn)程P

49、1 P1 進(jìn)程進(jìn)程P2P2 請(qǐng)求資源請(qǐng)求資源R1 R1 請(qǐng)求資源請(qǐng)求資源R2R2 請(qǐng)求資源請(qǐng)求資源R2 R2 請(qǐng)求資源請(qǐng)求資源R1R1 釋放資源釋放資源R1 R1 釋放資源釋放資源R2 R2 釋放資源釋放資源R2 R2 釋放資源釋放資源R1R1 R1R1R2R2 兩個(gè)進(jìn)程死鎖的典型情況兩個(gè)進(jìn)程死鎖的典型情況 死鎖死鎖R1R2 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4444 進(jìn)程在同步和通信的過(guò)程進(jìn)程在同步和通信的過(guò)程當(dāng)中也會(huì)產(chǎn)生死鎖。當(dāng)中也會(huì)產(chǎn)生死鎖。 例如，在生產(chǎn)者例如，在生產(chǎn)者消費(fèi)者消費(fèi)者問(wèn)題中，若把生產(chǎn)者進(jìn)程中兩問(wèn)題中，若把生產(chǎn)者進(jìn)程中兩個(gè)個(gè)P P操作的順序顛倒如下圖所示：操作的順序顛倒如下

50、圖所示： 生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程Pi Pi 生產(chǎn)一個(gè)產(chǎn)品生產(chǎn)一個(gè)產(chǎn)品 產(chǎn)品送入緩沖區(qū)產(chǎn)品送入緩沖區(qū) P(avail) P(avail) P(mutex)P(mutex) V(mutex) V(mutex) V(full)V(full) 在這種情況下，當(dāng)緩沖區(qū)在這種情況下，當(dāng)緩沖區(qū)都已放滿了產(chǎn)品時(shí)，生產(chǎn)者仍都已放滿了產(chǎn)品時(shí)，生產(chǎn)者仍可執(zhí)行可執(zhí)行P(mutex)操作，于是操作，于是該生產(chǎn)者掌握了對(duì)緩沖區(qū)的存該生產(chǎn)者掌握了對(duì)緩沖區(qū)的存取 控 制 權(quán) ， 當(dāng) 它 繼 續(xù) 執(zhí) 行取 控 制 權(quán) ， 當(dāng) 它 繼 續(xù) 執(zhí) 行P(avail)P(avail)操作時(shí)，由于沒(méi)有空操作時(shí)，由于沒(méi)有空緩沖區(qū)，該生產(chǎn)者被

51、阻塞，并緩沖區(qū)，該生產(chǎn)者被阻塞，并在在avail上等待。上等待。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4545若此時(shí)有一個(gè)消費(fèi)者到達(dá)，盡管緩沖區(qū)中有產(chǎn)品，消費(fèi)者在若此時(shí)有一個(gè)消費(fèi)者到達(dá)，盡管緩沖區(qū)中有產(chǎn)品，消費(fèi)者在執(zhí)行執(zhí)行P(full)P(full)操作時(shí)通過(guò)，但緊接著執(zhí)行操作時(shí)通過(guò)，但緊接著執(zhí)行P(mutex)P(mutex)操作時(shí)，將操作時(shí)，將因緩沖區(qū)已被阻塞的生產(chǎn)者所占有，而使消費(fèi)者無(wú)法獲得緩因緩沖區(qū)已被阻塞的生產(chǎn)者所占有，而使消費(fèi)者無(wú)法獲得緩沖區(qū)的存取控制權(quán)而被阻塞。此時(shí)，出現(xiàn)了生產(chǎn)者和消費(fèi)者沖區(qū)的存取控制權(quán)而被阻塞。此時(shí)，出現(xiàn)了生產(chǎn)者和消費(fèi)者之間僵死的局面，亦即發(fā)生了死鎖。之間僵死的局

52、面，亦即發(fā)生了死鎖。二、產(chǎn)生死鎖的原因 產(chǎn)生的產(chǎn)生的根本原因根本原因是系統(tǒng)能夠提供的資源數(shù)少于需要該是系統(tǒng)能夠提供的資源數(shù)少于需要該資源的進(jìn)程數(shù)資源的進(jìn)程數(shù)( (系統(tǒng)資源不足系統(tǒng)資源不足) )。 1 1）對(duì)資源的分配策略（請(qǐng)求順序）不當(dāng)）對(duì)資源的分配策略（請(qǐng)求順序）不當(dāng) ； 2 2）進(jìn)程推進(jìn)順序非法。）進(jìn)程推進(jìn)順序非法。 死鎖起因是并發(fā)進(jìn)程的資源競(jìng)爭(zhēng)。死鎖起因是并發(fā)進(jìn)程的資源競(jìng)爭(zhēng)。 可剝奪性資源可剝奪性資源 非剝奪性資源非剝奪性資源 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4646 P1P1和和P2P2都占用都占用R1R1 P1 P1和和P2P2都占用都占用R2R2 P2P2的進(jìn)展的進(jìn)展 P1P1的

53、進(jìn)展的進(jìn)展 占用占用R1 R1 占用占用R2 R2 釋放釋放R1 R1 釋放釋放R2 R2 請(qǐng)求請(qǐng)求R1 R1 請(qǐng)求請(qǐng)求R2 R2 請(qǐng)求請(qǐng)求R1R1 請(qǐng)求請(qǐng)求R2 R2 釋放釋放R1R1 釋放釋放R2R2 占用占用R1 R1 1 1 2 2 3 3 占用占用R2R2下面用圖示來(lái)說(shuō)明進(jìn)程下面用圖示來(lái)說(shuō)明進(jìn)程P1P1和和P2P2的三種可能的進(jìn)展情況：的三種可能的進(jìn)展情況： 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4747三、死鎖存在的必要條件1 1）互斥條件。）互斥條件。進(jìn)程對(duì)其所要求的資源進(jìn)行排它性控制，進(jìn)程對(duì)其所要求的資源進(jìn)行排它性控制，即一次只有一個(gè)進(jìn)程可以使用一個(gè)資源。即一次只有一個(gè)進(jìn)程可以使用

54、一個(gè)資源。2 2）不剝奪條件。）不剝奪條件。進(jìn)程所獲得進(jìn)程所獲得的資源在未被釋放之前，不能被的資源在未被釋放之前，不能被其它進(jìn)程強(qiáng)行剝奪。其它進(jìn)程強(qiáng)行剝奪。3 3）占有且等待條件）占有且等待條件。進(jìn)程每。進(jìn)程每次申請(qǐng)它所需要的一部分資源，次申請(qǐng)它所需要的一部分資源，在進(jìn)程等待分配其它資源的同時(shí)，在進(jìn)程等待分配其它資源的同時(shí)，可以占有已分配的資源。可以占有已分配的資源。 P1P1P2P2 R1 R1 R2 R2被占有被占有 被占有被占有 請(qǐng)求請(qǐng)求 請(qǐng)求請(qǐng)求 4 4）環(huán)路條件。）環(huán)路條件。在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的循環(huán)等待鏈，循環(huán)等待鏈， 操作系統(tǒng) 第

55、三章 處理機(jī)調(diào)度與死鎖4848四、解決死鎖的方法（一）死鎖的防止（一）死鎖的防止( (預(yù)防預(yù)防) ) 1 1破壞互斥條件破壞互斥條件 為了破壞資源使用的互斥條件，就要允許多個(gè)進(jìn)程同為了破壞資源使用的互斥條件，就要允許多個(gè)進(jìn)程同時(shí)訪問(wèn)共享資源。但是這種方法受到資源本身固有特性的時(shí)訪問(wèn)共享資源。但是這種方法受到資源本身固有特性的限制，對(duì)某些資源是行不通的。例如打印機(jī)，就不允許多限制，對(duì)某些資源是行不通的。例如打印機(jī)，就不允許多個(gè)進(jìn)程在其運(yùn)行期間交替打印數(shù)據(jù)，打印機(jī)只能互斥使用。個(gè)進(jìn)程在其運(yùn)行期間交替打印數(shù)據(jù)，打印機(jī)只能互斥使用。而文件，可能允許多個(gè)進(jìn)程對(duì)其進(jìn)行讀訪問(wèn)，但只允許互而文件，可能允許多個(gè)

56、進(jìn)程對(duì)其進(jìn)行讀訪問(wèn)，但只允許互斥地寫(xiě)訪問(wèn)。因此，互斥條件難以破壞。斥地寫(xiě)訪問(wèn)。因此，互斥條件難以破壞。 死鎖的防止是通過(guò)設(shè)置某些嚴(yán)格的限制條件，以破壞死鎖的防止是通過(guò)設(shè)置某些嚴(yán)格的限制條件，以破壞產(chǎn)生死鎖的必要條件來(lái)防止死鎖的發(fā)生。產(chǎn)生死鎖的必要條件來(lái)防止死鎖的發(fā)生。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖4949 2 2破壞不剝奪條件破壞不剝奪條件 該策略規(guī)定，一個(gè)已保持了某些資源的進(jìn)程，若新的資該策略規(guī)定，一個(gè)已保持了某些資源的進(jìn)程，若新的資源要求不能立即得到滿足，它必須釋放已保持的所有資源。源要求不能立即得到滿足，它必須釋放已保持的所有資源。以后再需要時(shí)重新申請(qǐng)。這意味著，一個(gè)進(jìn)程已占有的資

57、源，以后再需要時(shí)重新申請(qǐng)。這意味著，一個(gè)進(jìn)程已占有的資源，在運(yùn)行過(guò)程中可能暫時(shí)地釋放，或說(shuō)被剝奪。在運(yùn)行過(guò)程中可能暫時(shí)地釋放，或說(shuō)被剝奪。問(wèn)題：?jiǎn)栴}：1 1）這種防止死鎖的策略實(shí)現(xiàn)起來(lái)比較復(fù)雜；）這種防止死鎖的策略實(shí)現(xiàn)起來(lái)比較復(fù)雜；2 2）一個(gè)資源在使用一段時(shí)間后被釋放，可能會(huì)造成前階段）一個(gè)資源在使用一段時(shí)間后被釋放，可能會(huì)造成前階段工作的失效，即使采取某些防范措施，也還會(huì)使前后兩次運(yùn)工作的失效，即使采取某些防范措施，也還會(huì)使前后兩次運(yùn)行的信息不連續(xù)。行的信息不連續(xù)。3 3）該策略還可能由于反復(fù)地申請(qǐng)和釋放資源，使進(jìn)程的執(zhí)）該策略還可能由于反復(fù)地申請(qǐng)和釋放資源，使進(jìn)程的執(zhí)行無(wú)限推遲。這不僅延

58、長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)行無(wú)限推遲。這不僅延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開(kāi)銷(xiāo)，又降低了系統(tǒng)吞吐量。開(kāi)銷(xiāo)，又降低了系統(tǒng)吞吐量。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖5050 3 3破壞占有且等待條件破壞占有且等待條件-資源的靜態(tài)分配策略資源的靜態(tài)分配策略 系統(tǒng)要求所有進(jìn)程一次性地申請(qǐng)其所需的全部資源。若系統(tǒng)要求所有進(jìn)程一次性地申請(qǐng)其所需的全部資源。若系統(tǒng)有足夠的資源分配給該進(jìn)程時(shí)，便一次把所有其所需的系統(tǒng)有足夠的資源分配給該進(jìn)程時(shí)，便一次把所有其所需的資源分配給該進(jìn)程。這樣，該進(jìn)程在整個(gè)運(yùn)行期間，便不會(huì)資源分配給該進(jìn)程。這樣，該進(jìn)程在整個(gè)運(yùn)行期間，便不會(huì)再提出任何資源要求，從而使請(qǐng)求條

59、件不成立。但在分配時(shí)再提出任何資源要求，從而使請(qǐng)求條件不成立。但在分配時(shí)只要有一種資源要求不能滿足，則已有的其它資源也全部不只要有一種資源要求不能滿足，則已有的其它資源也全部不分配給該進(jìn)程，該進(jìn)程只能等待。由于等待期間的進(jìn)程不占分配給該進(jìn)程，該進(jìn)程只能等待。由于等待期間的進(jìn)程不占有任何資源，因此，破壞了必要條件之有任何資源，因此，破壞了必要條件之3 3，防止了死鎖發(fā)生。，防止了死鎖發(fā)生。 破壞占有且等待條件破壞占有且等待條件-資單請(qǐng)求方式分配資源資單請(qǐng)求方式分配資源優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)單、易于實(shí)現(xiàn)，且很安全。簡(jiǎn)單、易于實(shí)現(xiàn)，且很安全。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死鎖5151缺點(diǎn)：缺點(diǎn)：1 1）資

60、源嚴(yán)重浪費(fèi)。）資源嚴(yán)重浪費(fèi)。 一個(gè)進(jìn)程一次獲得其所需的全部資源且獨(dú)占，其中可一個(gè)進(jìn)程一次獲得其所需的全部資源且獨(dú)占，其中可能有些資源很少使用，甚至在整個(gè)運(yùn)行期間都未使用，這能有些資源很少使用，甚至在整個(gè)運(yùn)行期間都未使用，這就嚴(yán)重地惡化了系統(tǒng)資源利用率：就嚴(yán)重地惡化了系統(tǒng)資源利用率：2 2）進(jìn)程延遲運(yùn)行。）進(jìn)程延遲運(yùn)行。 僅當(dāng)進(jìn)程獲得其所需全部資源后，方能開(kāi)始運(yùn)行，但僅當(dāng)進(jìn)程獲得其所需全部資源后，方能開(kāi)始運(yùn)行，但可能有許多資源長(zhǎng)期被其它進(jìn)程占用，致使進(jìn)程推遲運(yùn)行，可能有許多資源長(zhǎng)期被其它進(jìn)程占用，致使進(jìn)程推遲運(yùn)行，這往往要經(jīng)過(guò)很長(zhǎng)的時(shí)延。這往往要經(jīng)過(guò)很長(zhǎng)的時(shí)延。 操作系統(tǒng) 第三章 處理機(jī)調(diào)度與死