操作系統(tǒng)第三章調(diào)度與死鎖ppt課件

1、第三章 進(jìn)程調(diào)度是實(shí)現(xiàn)多道程序系統(tǒng)的關(guān)鍵，直接影響到操作系統(tǒng)的性能，是本章討論的主要問題。3.1 調(diào)度的根本概念調(diào)度的根本概念 (一一 作業(yè)從進(jìn)入系統(tǒng)到完成，能夠要閱歷三級調(diào)度過程：作業(yè)從進(jìn)入系統(tǒng)到完成，能夠要閱歷三級調(diào)度過程：1、高級調(diào)度、高級調(diào)度 又稱為作業(yè)調(diào)度，它決議將哪些在外存上處于又稱為作業(yè)調(diào)度，它決議將哪些在外存上處于后備形狀的作業(yè)調(diào)入主機(jī)內(nèi)存，預(yù)備執(zhí)行。因此，有時把它后備形狀的作業(yè)調(diào)入主機(jī)內(nèi)存，預(yù)備執(zhí)行。因此，有時把它稱為接納調(diào)度。稱為接納調(diào)度。2、低級調(diào)度、低級調(diào)度 又稱為進(jìn)程調(diào)度，它決議就緒隊(duì)列中哪個進(jìn)程又稱為進(jìn)程調(diào)度，它決議就緒隊(duì)列中哪個進(jìn)程將獲得處置機(jī)，并實(shí)踐執(zhí)行將處置機(jī)

2、分配給進(jìn)程的操作。執(zhí)將獲得處置機(jī)，并實(shí)踐執(zhí)行將處置機(jī)分配給進(jìn)程的操作。執(zhí)行分配處置機(jī)的程序稱為分派程序。行分配處置機(jī)的程序稱為分派程序。3、中級調(diào)度、中級調(diào)度 中級調(diào)度的主要作用是在內(nèi)存和外存之間進(jìn)展中級調(diào)度的主要作用是在內(nèi)存和外存之間進(jìn)展進(jìn)程交換，以處理內(nèi)存緊張的問題。如它將內(nèi)存中處于等待進(jìn)程交換，以處理內(nèi)存緊張的問題。如它將內(nèi)存中處于等待形狀的某些進(jìn)程調(diào)至外存對換區(qū)，以騰出內(nèi)存空間，而將外形狀的某些進(jìn)程調(diào)至外存對換區(qū)，以騰出內(nèi)存空間，而將外存對換區(qū)上已具備運(yùn)轉(zhuǎn)條件的進(jìn)程重新調(diào)入內(nèi)存，預(yù)備運(yùn)轉(zhuǎn)存對換區(qū)上已具備運(yùn)轉(zhuǎn)條件的進(jìn)程重新調(diào)入內(nèi)存，預(yù)備運(yùn)轉(zhuǎn)。故又稱為交換調(diào)度。故又稱為交換調(diào)度。 阻塞形狀

3、就緒就緒形狀形狀執(zhí)行執(zhí)行形狀形狀調(diào)度調(diào)度I/O懇求懇求進(jìn)程進(jìn)程釋放釋放時間時間片到片到后備作業(yè)隊(duì)列后備作業(yè)隊(duì)列CPU就緒隊(duì)列就緒隊(duì)列內(nèi)存內(nèi)存外存外存阻塞隊(duì)列阻塞隊(duì)列作業(yè)調(diào)度作業(yè)調(diào)度等待事件等待事件中級調(diào)度中級調(diào)度即交換調(diào)度即交換調(diào)度交換文件交換文件就緒隊(duì)列就緒隊(duì)列阻塞隊(duì)列阻塞隊(duì)列三級調(diào)度的模型三級調(diào)度的模型3.1 調(diào)度的根本概念調(diào)度的根本概念 (三三作業(yè)調(diào)度是確定哪些作業(yè)可以被調(diào)入內(nèi)存。作業(yè)調(diào)度是確定哪些作業(yè)可以被調(diào)入內(nèi)存。進(jìn)程調(diào)度是確定哪個進(jìn)程可以占有進(jìn)程調(diào)度是確定哪個進(jìn)程可以占有CPUCPU并執(zhí)行。并執(zhí)行。作業(yè)調(diào)度是進(jìn)程調(diào)度的根底，作業(yè)被調(diào)入內(nèi)存后，作業(yè)調(diào)度是進(jìn)程調(diào)度的根底，作業(yè)被調(diào)入內(nèi)存

4、后，是以進(jìn)程的方式執(zhí)行的。是以進(jìn)程的方式執(zhí)行的。在一個在一個OSOS中進(jìn)程調(diào)度與作業(yè)調(diào)度的算法是一致的。中進(jìn)程調(diào)度與作業(yè)調(diào)度的算法是一致的。？問題？問題？各級調(diào)度間的關(guān)系各級調(diào)度間的關(guān)系3.1 調(diào)度的根本概念調(diào)度的根本概念 (四四 作業(yè)步作業(yè)步 將一個作業(yè)劃分為假設(shè)干個順序處置的步驟，將一個作業(yè)劃分為假設(shè)干個順序處置的步驟，作作 業(yè)步相互獨(dú)立又相互關(guān)聯(lián)。業(yè)步相互獨(dú)立又相互關(guān)聯(lián)。 作業(yè)作業(yè) 是用戶懇求計(jì)算機(jī)系統(tǒng)執(zhí)行的一次獨(dú)立的上機(jī)任是用戶懇求計(jì)算機(jī)系統(tǒng)執(zhí)行的一次獨(dú)立的上機(jī)任 務(wù)，是可以共享公共資源區(qū)域的一族有關(guān)進(jìn)程家族。務(wù)，是可以共享公共資源區(qū)域的一族有關(guān)進(jìn)程家族。 從靜態(tài)觀念看，作業(yè)由從靜態(tài)觀

5、念看，作業(yè)由 控制命令系列、程序集、數(shù)據(jù)控制命令系列、程序集、數(shù)據(jù) 集三部分構(gòu)成。集三部分構(gòu)成。補(bǔ)充：關(guān)于作業(yè)的概念補(bǔ)充：關(guān)于作業(yè)的概念作業(yè)控制塊作業(yè)控制塊 JCBJob Control Block用于描畫作業(yè)。用于描畫作業(yè)。 定義為記錄類型作業(yè)名、優(yōu)先級、建立時間、形狀外定義為記錄類型作業(yè)名、優(yōu)先級、建立時間、形狀外 存地址、大小等。存地址、大小等。 作業(yè)形狀作業(yè)形狀 作業(yè)在其生命期中，共有四種形狀：作業(yè)在其生命期中，共有四種形狀：關(guān)于作業(yè)的形狀關(guān)于作業(yè)的形狀 作業(yè)形狀作業(yè)形狀 作業(yè)在其生命期中，共有四種形狀：作業(yè)在其生命期中，共有四種形狀： 進(jìn)入、后備、運(yùn)轉(zhuǎn)、完成進(jìn)入、后備、運(yùn)轉(zhuǎn)、完成完成

6、完成執(zhí)行執(zhí)行就緒就緒阻塞阻塞進(jìn)入進(jìn)入后備后備運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)提交提交作業(yè)作業(yè)調(diào)度調(diào)度完成完成問題：引起進(jìn)程調(diào)度的緣由有哪些？問題：引起進(jìn)程調(diào)度的緣由有哪些？3.1 調(diào)度的根本概念調(diào)度的根本概念 (五五 非搶占式非剝奪式非搶占式非剝奪式 進(jìn)程進(jìn)程 一旦被調(diào)度一旦被調(diào)度 ，就不斷占有，就不斷占有CPUCPU，直到完成或，直到完成或因發(fā)生某事件而被阻塞因發(fā)生某事件而被阻塞I/OI/O懇求。懇求。 搶占式剝奪式搶占式剝奪式 進(jìn)程未執(zhí)行完，可由調(diào)度程序剝奪其進(jìn)程未執(zhí)行完，可由調(diào)度程序剝奪其CPUCPU，另分配，另分配給別的進(jìn)程。給別的進(jìn)程。 搶占的緣由有：優(yōu)先級、時間片、短進(jìn)程等。搶占的緣由有：優(yōu)先級、時間片、

7、短進(jìn)程等。在在OSOS中，進(jìn)程調(diào)度的方式分為兩類。中，進(jìn)程調(diào)度的方式分為兩類。3.1 調(diào)度的根本概念調(diào)度的根本概念 (六六 記錄系統(tǒng)中一切進(jìn)程的執(zhí)行情況記錄系統(tǒng)中一切進(jìn)程的執(zhí)行情況 確定分配處置機(jī)的原那么調(diào)度算法確定分配處置機(jī)的原那么調(diào)度算法 分配處置機(jī)給進(jìn)程分配處置機(jī)給進(jìn)程 回收處置機(jī)、進(jìn)展進(jìn)程上下文切換回收處置機(jī)、進(jìn)展進(jìn)程上下文切換顯然，進(jìn)程調(diào)度的中心問題是調(diào)度算法。顯然，進(jìn)程調(diào)度的中心問題是調(diào)度算法。3.1 調(diào)度的根本概念調(diào)度的根本概念 (七七 1。周轉(zhuǎn)時間短。周轉(zhuǎn)時間短 周轉(zhuǎn)時間周轉(zhuǎn)時間TTTumaround Time 對作業(yè)對作業(yè)從作業(yè)提交到完成。從作業(yè)提交到完成。 對進(jìn)程對進(jìn)程第一

8、次進(jìn)入就緒隊(duì)列到運(yùn)轉(zhuǎn)終了。第一次進(jìn)入就緒隊(duì)列到運(yùn)轉(zhuǎn)終了。 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間ATTAverage Tumaround Time ATT= Ti 帶權(quán)平均帶權(quán)平均 W= 其中：其中： Ti 各進(jìn)程的各進(jìn)程的TT Tri 實(shí)踐執(zhí)行時間實(shí)踐執(zhí)行時間2. 2. 呼應(yīng)時間快呼應(yīng)時間快 呼應(yīng)時間呼應(yīng)時間RTRTResponse TimeResponse Time輸入鍵盤命輸入鍵盤命令到屏幕顯示結(jié)果。令到屏幕顯示結(jié)果。四四. 調(diào)度算法準(zhǔn)那么調(diào)度算法準(zhǔn)那么 調(diào)度算法應(yīng)該盡能夠提高資源利用率，減少調(diào)度算法應(yīng)該盡能夠提高資源利用率，減少CPU空閑空閑時間時間,公平效力?？蓮囊韵路矫嫠妓鳎汗叫ЯΑ？蓮囊韵路?/p>

9、面思索：1ni=1nTiTrii=1n1 n3.2 3.2 調(diào)度算法調(diào)度算法 一一 先來先效力FCFS算法 最短CPU運(yùn)轉(zhuǎn)期優(yōu)先SCBF算法 最高優(yōu)先權(quán)HPF算法 時間片輪轉(zhuǎn)RR算法 多級反響隊(duì)列算法思索題思索題 1、各種調(diào)度算法的特點(diǎn)、性能如何？適宜于、各種調(diào)度算法的特點(diǎn)、性能如何？適宜于 哪類哪類 OS？ 2。最高優(yōu)先權(quán)算法中，動態(tài)優(yōu)先權(quán)有何實(shí)踐。最高優(yōu)先權(quán)算法中，動態(tài)優(yōu)先權(quán)有何實(shí)踐意義？意義？3.2 3.2 調(diào)度算法調(diào)度算法 二二 一一. .、先來先效力、先來先效力FCFSFCFS算法算法 FCFSFirst Come First Server 法，又稱為先法，又稱為先進(jìn)先出進(jìn)先出FIF

10、O算法，就緒進(jìn)程按照進(jìn)入的先后次序陳算法，就緒進(jìn)程按照進(jìn)入的先后次序陳列，調(diào)度程序總是選擇隊(duì)首的進(jìn)程執(zhí)行。列，調(diào)度程序總是選擇隊(duì)首的進(jìn)程執(zhí)行。 這是一種非剝奪式的調(diào)度算法，簡單、易實(shí)現(xiàn)。這是一種非剝奪式的調(diào)度算法，簡單、易實(shí)現(xiàn)。 對短進(jìn)程易出現(xiàn)等待時間長，效力質(zhì)量差。對短進(jìn)程易出現(xiàn)等待時間長，效力質(zhì)量差。 該算法有利于該算法有利于CPU忙碌型的進(jìn)程，不利于忙碌型的進(jìn)程，不利于I/O忙碌型的進(jìn)忙碌型的進(jìn) 程。程。1n 該算法只能用于輔助算法。該算法只能用于輔助算法。3.2 3.2 調(diào)度算法調(diào)度算法 二二二、二、 最短最短CPUCPU運(yùn)轉(zhuǎn)期優(yōu)先運(yùn)轉(zhuǎn)期優(yōu)先SCBFSCBF算法算法n+1nnt 該算法

11、優(yōu)于該算法優(yōu)于FCFS，但出息程等待時間長，估算誤差較大。，但出息程等待時間長，估算誤差較大。 SCBFShortest CPU Burst First ，即調(diào)度程序總，即調(diào)度程序總是選擇是選擇CPU運(yùn)轉(zhuǎn)時間最短的進(jìn)程執(zhí)行。運(yùn)轉(zhuǎn)時間最短的進(jìn)程執(zhí)行。其中其中 為估計(jì)的第為估計(jì)的第n個個CPU 周期。周期。tn 為實(shí)踐值。為實(shí)踐值。 為控制值，為控制值，0 1，常取，常取 0.5n 對最短對最短CPU運(yùn)轉(zhuǎn)期的估算，依賴于系統(tǒng)的下一個運(yùn)轉(zhuǎn)期的估算，依賴于系統(tǒng)的下一個CPU周周期中，實(shí)現(xiàn)較困難。進(jìn)程的期中，實(shí)現(xiàn)較困難。進(jìn)程的CPU時間時間 的估算公式：的估算公式：n+13.2 3.2 調(diào)度算法調(diào)度算法

12、 三三 三、三、 最高優(yōu)先權(quán)最高優(yōu)先權(quán)HPFHPF算法算法 調(diào)度程序每次都將調(diào)度程序每次都將CPU分配給就緒隊(duì)列中具有最高優(yōu)先級分配給就緒隊(duì)列中具有最高優(yōu)先級Highest Priority的進(jìn)程。該算法的中心是優(yōu)先級確實(shí)定。的進(jìn)程。該算法的中心是優(yōu)先級確實(shí)定。 調(diào)度方式分為剝奪調(diào)度方式分為剝奪式和非剝奪式。式和非剝奪式。 靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級 在創(chuàng)建進(jìn)程時根據(jù)進(jìn)程的特性或者用戶要求賦予，在進(jìn)在創(chuàng)建進(jìn)程時根據(jù)進(jìn)程的特性或者用戶要求賦予，在進(jìn)程的整個生命期中不能改動。程的整個生命期中不能改動。 簡單、易實(shí)現(xiàn)，但是調(diào)度性能不高，優(yōu)先級低的進(jìn)程能簡單、易實(shí)現(xiàn)，但是調(diào)度性能不高，優(yōu)先級低的進(jìn)程能夠長期

13、等待。夠長期等待。 動態(tài)優(yōu)先級動態(tài)優(yōu)先級 在創(chuàng)建進(jìn)程時為進(jìn)程賦予一個根本優(yōu)先級，在進(jìn)程的執(zhí)在創(chuàng)建進(jìn)程時為進(jìn)程賦予一個根本優(yōu)先級，在進(jìn)程的執(zhí)行過程中可隨進(jìn)程的特性動態(tài)改動。行過程中可隨進(jìn)程的特性動態(tài)改動。 引起優(yōu)先級改動的緣由：引起優(yōu)先級改動的緣由： 進(jìn)程等待進(jìn)程等待CPU時間長短，執(zhí)行所需時間長短，執(zhí)行所需CPU時間長短等。時間長短等。 分兩類優(yōu)先級：分兩類優(yōu)先級：3.2 3.2 調(diào)度算法調(diào)度算法 四四三、最高優(yōu)先權(quán)三、最高優(yōu)先權(quán)HPFHPF算法算法確定進(jìn)程優(yōu)先級的普通原那么：確定進(jìn)程優(yōu)先級的普通原那么： 1. 進(jìn)程的類型進(jìn)程的類型 例如：例如： 系統(tǒng)進(jìn)程高于用戶進(jìn)程；系統(tǒng)進(jìn)程高于用戶進(jìn)程；

14、前臺進(jìn)程高于后臺進(jìn)程；前臺進(jìn)程高于后臺進(jìn)程； 實(shí)時進(jìn)程高于普通進(jìn)程。實(shí)時進(jìn)程高于普通進(jìn)程。 2. 對資源的需求量及類型對資源的需求量及類型 占用占用CPU時間少的，運(yùn)用內(nèi)存資源少的進(jìn)程優(yōu)時間少的，運(yùn)用內(nèi)存資源少的進(jìn)程優(yōu)先級高。先級高。 3. 按作業(yè)到達(dá)系統(tǒng)的時間順序按作業(yè)到達(dá)系統(tǒng)的時間順序 4. 按用戶類型和要求按用戶類型和要求 3.2 3.2 調(diào)度算法調(diào)度算法 五五 四、四、 時間片輪轉(zhuǎn)時間片輪轉(zhuǎn)RRRR算法算法 該算法主要用于分時系統(tǒng)，按照公平效力的原那么，該算法主要用于分時系統(tǒng)，按照公平效力的原那么，為進(jìn)程分配為進(jìn)程分配CPU時間片。是一種剝奪式的算法。時間片。是一種剝奪式的算法。 輪轉(zhuǎn)

15、法的關(guān)鍵是時間片的選?。狠嗈D(zhuǎn)法的關(guān)鍵是時間片的選取： 時間片太大，那么輪轉(zhuǎn)法蛻化為時間片太大，那么輪轉(zhuǎn)法蛻化為FCFS法。法。 時間片太小，那么添加時間片太小，那么添加CPU的額外開銷。的額外開銷。 影響時間片設(shè)置的主要要素：影響時間片設(shè)置的主要要素： 系統(tǒng)呼應(yīng)時間系統(tǒng)呼應(yīng)時間R、就緒進(jìn)程數(shù)、就緒進(jìn)程數(shù)N、計(jì)算機(jī)處置才干等。、計(jì)算機(jī)處置才干等。 時間片長度：時間片長度： q = R / N max3.2 3.2 調(diào)度算法調(diào)度算法 六六 五、高呼應(yīng)比優(yōu)先調(diào)度算法五、高呼應(yīng)比優(yōu)先調(diào)度算法HRNHRN HRNHighest Response ratio Next算法將短進(jìn)算法將短進(jìn)程優(yōu)先與動態(tài)優(yōu)先級

16、相結(jié)合。所謂高呼應(yīng)是指進(jìn)程獲得程優(yōu)先與動態(tài)優(yōu)先級相結(jié)合。所謂高呼應(yīng)是指進(jìn)程獲得調(diào)度的呼應(yīng)，即優(yōu)先數(shù)調(diào)度的呼應(yīng)，即優(yōu)先數(shù)R。 R =W+T/T = 1+W/T T 估計(jì)進(jìn)程執(zhí)行的時間。估計(jì)進(jìn)程執(zhí)行的時間。 W 進(jìn)程等待的時間。進(jìn)程等待的時間。 隨著進(jìn)程等待時間的添加，優(yōu)先權(quán)動態(tài)添加。隨著進(jìn)程等待時間的添加，優(yōu)先權(quán)動態(tài)添加。 對等待一樣時間的短進(jìn)程比出息程優(yōu)先權(quán)添加得多。對等待一樣時間的短進(jìn)程比出息程優(yōu)先權(quán)添加得多。 出息程隨著等待時間添加也會被調(diào)度。出息程隨著等待時間添加也會被調(diào)度。3.2 3.2 調(diào)度算法調(diào)度算法 七七 六、多級隊(duì)列調(diào)度六、多級隊(duì)列調(diào)度 根據(jù)作業(yè)性質(zhì)不同分為假設(shè)干個就緒隊(duì)列，根

17、據(jù)作業(yè)性質(zhì)不同分為假設(shè)干個就緒隊(duì)列，如：系統(tǒng)進(jìn)程隊(duì)列，交互進(jìn)程隊(duì)列，批處置隊(duì)如：系統(tǒng)進(jìn)程隊(duì)列，交互進(jìn)程隊(duì)列，批處置隊(duì)列等。對各隊(duì)列采用不同的調(diào)度算法。列等。對各隊(duì)列采用不同的調(diào)度算法。3.2 3.2 調(diào)度算法調(diào)度算法 八八 亦稱多級反響輪轉(zhuǎn)法亦稱多級反響輪轉(zhuǎn)法Round Robin with Multiple FeedbackRound Robin with Multiple Feedback實(shí)現(xiàn)根本思想：實(shí)現(xiàn)根本思想：1 1。按優(yōu)先級分別設(shè)置。按優(yōu)先級分別設(shè)置N N個就緒隊(duì)列，優(yōu)先級愈高的隊(duì)列分配個就緒隊(duì)列，優(yōu)先級愈高的隊(duì)列分配 的時間片愈小。的時間片愈小。2 2。系統(tǒng)總是先調(diào)度當(dāng)前優(yōu)先級最

18、高的隊(duì)列中的進(jìn)程，只需當(dāng)。系統(tǒng)總是先調(diào)度當(dāng)前優(yōu)先級最高的隊(duì)列中的進(jìn)程，只需當(dāng) 最高優(yōu)先級隊(duì)列為空時，才去調(diào)度低一優(yōu)先級隊(duì)列中的進(jìn)最高優(yōu)先級隊(duì)列為空時，才去調(diào)度低一優(yōu)先級隊(duì)列中的進(jìn) 程。程。3 3。進(jìn)程被調(diào)度后，假設(shè)未執(zhí)行完時間片到，那么優(yōu)先級降低，進(jìn)。進(jìn)程被調(diào)度后，假設(shè)未執(zhí)行完時間片到，那么優(yōu)先級降低，進(jìn) 程排入相應(yīng)優(yōu)先級隊(duì)列的隊(duì)尾。程排入相應(yīng)優(yōu)先級隊(duì)列的隊(duì)尾。4 4。同一優(yōu)先級隊(duì)列，按照。同一優(yōu)先級隊(duì)列，按照FCFSFCFS算法調(diào)度。算法調(diào)度。 多級反響隊(duì)列是一種綜合調(diào)度算法，對進(jìn)程就緒隊(duì)列進(jìn)行動態(tài)調(diào)度和管理。七、多級反響隊(duì)列七、多級反響隊(duì)列3.2 3.2 調(diào)度算法調(diào)度算法 九九七、多級反響

19、隊(duì)列七、多級反響隊(duì)列3.3 3.3 進(jìn)程調(diào)度實(shí)例進(jìn)程調(diào)度實(shí)例 ( (一一一。一。VMSVMS進(jìn)程調(diào)度進(jìn)程調(diào)度 綜合調(diào)度算法：以優(yōu)先級為根底的多級反響隊(duì)列。綜合調(diào)度算法：以優(yōu)先級為根底的多級反響隊(duì)列。 VMS VMS中的優(yōu)先級：中的優(yōu)先級： 1 1。硬件優(yōu)先級。硬件優(yōu)先級IPLIPL中斷優(yōu)先級，存儲在硬件中斷優(yōu)先級，存儲在硬件PCBPCB中。中。 2 2。軟件優(yōu)先級。軟件優(yōu)先級 0 310 31級存儲在軟件級存儲在軟件PCBPCB中。中。 1631 1631 實(shí)時優(yōu)先級靜態(tài)優(yōu)先級，用于實(shí)時實(shí)時優(yōu)先級靜態(tài)優(yōu)先級，用于實(shí)時進(jìn)程。進(jìn)程。 不受時間片影響，進(jìn)程一旦被調(diào)度，不受時間片影響，進(jìn)程一旦被調(diào)度，

20、不斷執(zhí)行不斷執(zhí)行 到到 終了。終了。 0 15 0 15 正常優(yōu)先級正常優(yōu)先級 動態(tài)優(yōu)先級，用于非實(shí)動態(tài)優(yōu)先級，用于非實(shí)時進(jìn)程，時進(jìn)程， 為每個優(yōu)先級隊(duì)列設(shè)置不同的為每個優(yōu)先級隊(duì)列設(shè)置不同的 時間時間片。優(yōu)先級片。優(yōu)先級 愈高，時間片愈短。愈高，時間片愈短。 系統(tǒng)中的進(jìn)程按照優(yōu)先級排成系統(tǒng)中的進(jìn)程按照優(yōu)先級排成32個就緒隊(duì)列，系統(tǒng)個就緒隊(duì)列，系統(tǒng)總是按總是按FCFS算法先調(diào)度當(dāng)前優(yōu)先級最高的隊(duì)列中的算法先調(diào)度當(dāng)前優(yōu)先級最高的隊(duì)列中的進(jìn)程。對實(shí)時進(jìn)程。對實(shí)時 進(jìn)程和正常進(jìn)程采用不同的調(diào)度戰(zhàn)略。進(jìn)程和正常進(jìn)程采用不同的調(diào)度戰(zhàn)略。3.3 3.3 進(jìn)程調(diào)度實(shí)例進(jìn)程調(diào)度實(shí)例 ( (二二 正常優(yōu)先級進(jìn)程正

21、常優(yōu)先級進(jìn)程0 15在創(chuàng)建時，系統(tǒng)為其分配了在創(chuàng)建時，系統(tǒng)為其分配了 根本優(yōu)先級：根本優(yōu)先級： 交互進(jìn)程為交互進(jìn)程為4，批處置進(jìn)程為，批處置進(jìn)程為3。 優(yōu)先級提升幅度的原那么：優(yōu)先級提升幅度的原那么： 隨著進(jìn)程等待時間添加，優(yōu)先級提升幅度添加。隨著進(jìn)程等待時間添加，優(yōu)先級提升幅度添加。 因進(jìn)程類型而定；受因進(jìn)程類型而定；受 I/O 限制的進(jìn)程提升幅度大于受限制的進(jìn)程提升幅度大于受計(jì)算限制的進(jìn)程。計(jì)算限制的進(jìn)程。VMSVMS中進(jìn)程優(yōu)先級的動態(tài)提升中進(jìn)程優(yōu)先級的動態(tài)提升 在進(jìn)程運(yùn)轉(zhuǎn)過程中，優(yōu)先級會有不同幅度在進(jìn)程運(yùn)轉(zhuǎn)過程中，優(yōu)先級會有不同幅度0 6的提的提 升，使進(jìn)程獲得調(diào)度的能夠性。升，使進(jìn)程獲

22、得調(diào)度的能夠性。進(jìn)程優(yōu)先級下降進(jìn)程優(yōu)先級下降 ：當(dāng)進(jìn)程由于時間片到或者等待某事：當(dāng)進(jìn)程由于時間片到或者等待某事件發(fā)生而釋放件發(fā)生而釋放CPU時，優(yōu)先級下降。時，優(yōu)先級下降。優(yōu)先級改動后的進(jìn)程排到相應(yīng)隊(duì)列的隊(duì)尾優(yōu)先級改動后的進(jìn)程排到相應(yīng)隊(duì)列的隊(duì)尾 。優(yōu)先級隊(duì)列優(yōu)先級隊(duì)列31301516140靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級動態(tài)優(yōu)先級動態(tài)優(yōu)先級CPU等等待待隊(duì)隊(duì)列列優(yōu)優(yōu)先先級級下下降降進(jìn)程按照優(yōu)先級排成進(jìn)程按照優(yōu)先級排成32個就緒隊(duì)列。個就緒隊(duì)列。每個就緒隊(duì)列按照每個就緒隊(duì)列按照FCFS算法排隊(duì)。算法排隊(duì)。優(yōu)先級越高時間片越小。優(yōu)先級越高時間片越小。3.3 3.3 進(jìn)程調(diào)度實(shí)例進(jìn)程調(diào)度實(shí)例 ( (三三 進(jìn)程的

23、優(yōu)先權(quán)分進(jìn)程的優(yōu)先權(quán)分31級級1 - 31，為動態(tài)優(yōu)先級：在根，為動態(tài)優(yōu)先級：在根本優(yōu)先級的根底上動搖本優(yōu)先級的根底上動搖 + 2級。級。 根本優(yōu)先權(quán)設(shè)置根本優(yōu)先權(quán)設(shè)置4組組 優(yōu)先權(quán)等級優(yōu)先權(quán)等級 優(yōu)先權(quán)范圍優(yōu)先權(quán)范圍 Idle 閑置閑置 1 6 Normal 規(guī)范規(guī)范 6 10 High 高級高級 11 15 Realtime實(shí)時實(shí)時 16 31 進(jìn)程調(diào)度過程中優(yōu)先權(quán)的動態(tài)提升有何實(shí)踐意義？進(jìn)程調(diào)度過程中優(yōu)先權(quán)的動態(tài)提升有何實(shí)踐意義？WINDOWS NT 的進(jìn)程優(yōu)先級的進(jìn)程優(yōu)先級問問 題題3.5 3.5 線程的根本概念線程的根本概念 一一 為了減少進(jìn)程并發(fā)執(zhí)行的開銷，提高系統(tǒng)性能。將為了減少

24、進(jìn)程并發(fā)執(zhí)行的開銷，提高系統(tǒng)性能。將資源分配與調(diào)度分開資源分配與調(diào)度分開引入線程。引入線程。3.5 3.5 線程的根本概念線程的根本概念 二二線程線程1 1的的TCBTCB線程線程2 2的的TCBTCB線程線程3 3的的TCBTCBTCBCPU 形狀形狀堆棧堆棧程序計(jì)數(shù)器程序計(jì)數(shù)器 . . .存放器存放器PCB進(jìn)程標(biāo)識進(jìn)程標(biāo)識資源清單資源清單 . . .TCB輸入線程輸入線程 主線程主線程 計(jì)算線程計(jì)算線程 輸出線程輸出線程 圖圖1圖圖2主線程主線程 創(chuàng)建線程創(chuàng)建線程 1 。 創(chuàng)建線程創(chuàng)建線程 n圖圖32. 線程線程 的并發(fā)性的并發(fā)性 同一進(jìn)程同一進(jìn)程 的多個線程具有并發(fā)執(zhí)行的特性，線程之間的

25、多個線程具有并發(fā)執(zhí)行的特性，線程之間相互約束，線程執(zhí)行過程呈現(xiàn)延續(xù)性。線程也具有就緒、相互約束，線程執(zhí)行過程呈現(xiàn)延續(xù)性。線程也具有就緒、 阻塞和執(zhí)行三種根本形狀。阻塞和執(zhí)行三種根本形狀。3. 線程資源 線程可以與其它同屬一個進(jìn)程的線程共同擁有該進(jìn)程的資源。3.5 3.5 線程的根本概念線程的根本概念 三三4. 4. 線程的調(diào)度線程的調(diào)度 線程作為調(diào)度的根本單位，在線程作為調(diào)度的根本單位，在windows NT windows NT 等等3232位位OSOS 中，采用按優(yōu)先級調(diào)度的戰(zhàn)略。中，采用按優(yōu)先級調(diào)度的戰(zhàn)略。 線程的調(diào)度算法與進(jìn)程類似，對線程的調(diào)度算法與進(jìn)程類似，對CPUCPU的分配也分搶

26、的分配也分搶占占 式和非搶占式。式和非搶占式。3.5 3.5 線程的根本概念線程的根本概念 四四3.7 3.7 死鎖的根本概念一死鎖的根本概念一1、爭奪資源引起死鎖 例1：P1，P2兩個進(jìn)程爭奪打印機(jī)和讀卡機(jī)。P1P2打印機(jī)讀卡機(jī) P1曾經(jīng)懇求到打印機(jī)， 又懇求讀卡機(jī)。 P2曾經(jīng)懇求到讀卡機(jī)， 又懇求打印機(jī)。打印機(jī)和讀卡機(jī)為打印機(jī)和讀卡機(jī)為非剝奪性資源。非剝奪性資源。例例3 3、 P1 P1，P2P2，P3 P3 三個進(jìn)程之間通訊：三個進(jìn)程之間通訊： P1 P1產(chǎn)生音訊產(chǎn)生音訊S1S1，接納，接納P3P3產(chǎn)生的音訊產(chǎn)生的音訊S3S3； P2 P2產(chǎn)生音訊產(chǎn)生音訊S2S2，接納，接納P1P1產(chǎn)生

27、的音訊產(chǎn)生的音訊S1S1； P3 P3產(chǎn)生音訊產(chǎn)生音訊S3S3，接納，接納P2P2產(chǎn)生的音訊產(chǎn)生的音訊S2S2；按以下次序運(yùn)轉(zhuǎn)：按以下次序運(yùn)轉(zhuǎn)：P1：RequestS3；ReleaseS1P2：RequestS1；ReleaseS2P3：RequestS2；ReleaseS3P1P3P2S2S3S1P1P2P3按照以上的順序執(zhí)行會產(chǎn)生死鎖嗎？按照以上的順序執(zhí)行會產(chǎn)生死鎖嗎？問題？例例2 2、 在消費(fèi)者在消費(fèi)者消費(fèi)者問題中假設(shè)交換兩個消費(fèi)者問題中假設(shè)交換兩個P P操作操作 的次序，能夠引起死鎖。的次序，能夠引起死鎖。SiSi暫時性資暫時性資源源3.7 死鎖的根本概念三死鎖的根本概念三消費(fèi)者進(jìn)程：

28、消費(fèi)者進(jìn)程： 消費(fèi)一個產(chǎn)品消費(fèi)一個產(chǎn)品 m ； . . . Pempty； Pmutex； 將產(chǎn)品將產(chǎn)品 m放入緩沖區(qū)；放入緩沖區(qū)； in ：=in +1 mod n ； V mutex； V full； 消費(fèi)者進(jìn)程： P full； P mutex ； 從緩沖區(qū)取產(chǎn)品m； out ：=out+1 mod n ； V mutex； V empty；消費(fèi)者消費(fèi)者消費(fèi)者問題算法：消費(fèi)者問題算法：3.7 死鎖的根本概念四死鎖的根本概念四 由于由于 產(chǎn)生死鎖的根本緣由是爭奪共享資源，從而得產(chǎn)生死鎖的根本緣由是爭奪共享資源，從而得到產(chǎn)生死鎖的必要條件是：到產(chǎn)生死鎖的必要條件是： 互斥條件互斥條件 進(jìn)程互

29、斥運(yùn)用臨界資源。進(jìn)程互斥運(yùn)用臨界資源。 不剝奪條件不剝奪條件 資源只能由占有它的進(jìn)程釋放，不能資源只能由占有它的進(jìn)程釋放，不能 被其它進(jìn)程剝奪。被其它進(jìn)程剝奪。 非剝奪資源非剝奪資源 部分分配條件部分分配條件 進(jìn)程在懇求新資源的同時，堅(jiān)持對某進(jìn)程在懇求新資源的同時，堅(jiān)持對某 些資源的占有。些資源的占有。 環(huán)路等待條件環(huán)路等待條件 存在循環(huán)等待鏈，在鏈中每個進(jìn)程都存在循環(huán)等待鏈，在鏈中每個進(jìn)程都 在等待它的前一進(jìn)程所持有的資源。在等待它的前一進(jìn)程所持有的資源。3.7 死鎖的根本概念五死鎖的根本概念五 顯然，假設(shè)出現(xiàn)死鎖將對操作系統(tǒng)呵斥極大的危害，顯然，假設(shè)出現(xiàn)死鎖將對操作系統(tǒng)呵斥極大的危害，甚至使系統(tǒng)癱瘓，如何處理死鎖是操作系統(tǒng)設(shè)計(jì)的重要甚至使系統(tǒng)癱瘓，如何處理死鎖是操作系統(tǒng)設(shè)計(jì)的重要問題。問題。 限制并發(fā)進(jìn)程對于資源的限制并發(fā)進(jìn)程對于資源的需求，破壞產(chǎn)生死需求，破壞產(chǎn)生死 鎖的必鎖的必要條件。嚴(yán)厲限制死鎖的要條件。嚴(yán)厲限制死鎖的發(fā)生。發(fā)生。三。處理死鎖的方法預(yù)防死鎖預(yù)防死鎖防止死鎖防止死鎖在資源的動