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

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

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

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

4、后，是以進程的方式執(zhí)行的。是以進程的方式執(zhí)行的。在一個在一個OSOS中進程調(diào)度與作業(yè)調(diào)度的算法是一致的。中進程調(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è)步相互獨立又相互關(guān)聯(lián)。業(yè)步相互獨立又相互關(guān)聯(lián)。 作業(yè)作業(yè) 是用戶懇求計算機系統(tǒng)執(zhí)行的一次獨立的上機任是用戶懇求計算機系統(tǒng)執(zhí)行的一次獨立的上機任 務(wù)，是可以共享公共資源區(qū)域的一族有關(guān)進程家族。務(wù)，是可以共享公共資源區(qū)域的一族有關(guān)進程家族。 從靜態(tài)觀念看，作業(yè)由從靜態(tài)觀

5、念看，作業(yè)由 控制命令系列、程序集、數(shù)據(jù)控制命令系列、程序集、數(shù)據(jù) 集三部分構(gòu)成。集三部分構(gòu)成。補充：關(guān)于作業(yè)的概念補充：關(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è)在其生命期中，共有四種形狀： 進入、后備、運轉(zhuǎn)、完成進入、后備、運轉(zhuǎn)、完成完成

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

7、短進程等。在在OSOS中，進程調(diào)度的方式分為兩類。中，進程調(diào)度的方式分為兩類。3.1 調(diào)度的根本概念調(diào)度的根本概念 (六六 記錄系統(tǒng)中一切進程的執(zhí)行情況記錄系統(tǒng)中一切進程的執(zhí)行情況 確定分配處置機的原那么調(diào)度算法確定分配處置機的原那么調(diào)度算法 分配處置機給進程分配處置機給進程 回收處置機、進展進程上下文切換回收處置機、進展進程上下文切換顯然，進程調(diào)度的中心問題是調(diào)度算法。顯然，進程調(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è)提交到完成。 對進程對進程第一

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

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

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

11、優(yōu)于該算法優(yōu)于FCFS，但出息程等待時間長，估算誤差較大。，但出息程等待時間長，估算誤差較大。 SCBFShortest CPU Burst First ，即調(diào)度程序總，即調(diào)度程序總是選擇是選擇CPU運轉(zhuǎn)時間最短的進程執(zhí)行。運轉(zhuǎn)時間最短的進程執(zhí)行。其中其中 為估計的第為估計的第n個個CPU 周期。周期。tn 為實踐值。為實踐值。 為控制值，為控制值，0 1，常取，常取 0.5n 對最短對最短CPU運轉(zhuǎn)期的估算，依賴于系統(tǒng)的下一個運轉(zhuǎn)期的估算，依賴于系統(tǒng)的下一個CPU周周期中，實現(xiàn)較困難。進程的期中，實現(xià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分配給就緒隊列中具有最高優(yōu)先級分配給就緒隊列中具有最高優(yōu)先級Highest Priority的進程。該算法的中心是優(yōu)先級確實定。的進程。該算法的中心是優(yōu)先級確實定。 調(diào)度方式分為剝奪調(diào)度方式分為剝奪式和非剝奪式。式和非剝奪式。 靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級 在創(chuàng)建進程時根據(jù)進程的特性或者用戶要求賦予，在進在創(chuàng)建進程時根據(jù)進程的特性或者用戶要求賦予，在進程的整個生命期中不能改動。程的整個生命期中不能改動。 簡單、易實現(xiàn)，但是調(diào)度性能不高，優(yōu)先級低的進程能簡單、易實現(xiàn)，但是調(diào)度性能不高，優(yōu)先級低的進程能夠長期

13、等待。夠長期等待。 動態(tài)優(yōu)先級動態(tài)優(yōu)先級 在創(chuàng)建進程時為進程賦予一個根本優(yōu)先級，在進程的執(zhí)在創(chuàng)建進程時為進程賦予一個根本優(yōu)先級，在進程的執(zhí)行過程中可隨進程的特性動態(tài)改動。行過程中可隨進程的特性動態(tài)改動。 引起優(yōu)先級改動的緣由：引起優(yōu)先級改動的緣由： 進程等待進程等待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算法算法確定進程優(yōu)先級的普通原那么：確定進程優(yōu)先級的普通原那么： 1. 進程的類型進程的類型 例如：例如： 系統(tǒng)進程高于用戶進程；系統(tǒng)進程高于用戶進程；

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

15、法的關(guān)鍵是時間片的選取：輪轉(zhuǎn)法的關(guān)鍵是時間片的選?。?時間片太大，那么輪轉(zhuǎn)法蛻化為時間片太大，那么輪轉(zhuǎn)法蛻化為FCFS法。法。 時間片太小，那么添加時間片太小，那么添加CPU的額外開銷。的額外開銷。 影響時間片設(shè)置的主要要素：影響時間片設(shè)置的主要要素： 系統(tǒng)呼應(yīng)時間系統(tǒng)呼應(yīng)時間R、就緒進程數(shù)、就緒進程數(shù)N、計算機處置才干等。、計算機處置才干等。 時間片長度：時間片長度： 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算法將短進算法將短進程優(yōu)先與動態(tài)優(yōu)先級

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

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

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

19、隊列七、多級反響隊列3.3 3.3 進程調(diào)度實例進程調(diào)度實例 ( (一一一。一。VMSVMS進程調(diào)度進程調(diào)度 綜合調(diào)度算法：以優(yōu)先級為根底的多級反響隊列。綜合調(diào)度算法：以優(yōu)先級為根底的多級反響隊列。 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 實時優(yōu)先級靜態(tài)優(yōu)先級，用于實時實時優(yōu)先級靜態(tài)優(yōu)先級，用于實時進程。進程。 不受時間片影響，進程一旦被調(diào)度，不受時間片影響，進程一旦被調(diào)度，

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

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

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

23、優(yōu)先權(quá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實時實時 16 31 進程調(diào)度過程中優(yōu)先權(quán)的動態(tài)提升有何實踐意義？進程調(diào)度過程中優(yōu)先權(quán)的動態(tài)提升有何實踐意義？WINDOWS NT 的進程優(yōu)先級的進程優(yōu)先級問問 題題3.5 3.5 線程的根本概念線程的根本概念 一一 為了減少進程并發(fā)執(zhí)行的開銷，提高系統(tǒng)性能。將為了減少

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

25、多個線程具有并發(fā)執(zhí)行的特性，線程之間相互約束，線程執(zhí)行過程呈現(xiàn)延續(xù)性。線程也具有就緒、相互約束，線程執(zhí)行過程呈現(xiàn)延續(xù)性。線程也具有就緒、 阻塞和執(zhí)行三種根本形狀。阻塞和執(zhí)行三種根本形狀。3. 線程資源 線程可以與其它同屬一個進程的線程共同擁有該進程的資源。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)度算法與進程類似，對線程的調(diào)度算法與進程類似，對CPUCPU的分配也分搶

26、的分配也分搶占占 式和非搶占式。式和非搶占式。3.5 3.5 線程的根本概念線程的根本概念 四四3.7 3.7 死鎖的根本概念一死鎖的根本概念一1、爭奪資源引起死鎖 例1：P1，P2兩個進程爭奪打印機和讀卡機。P1P2打印機讀卡機 P1曾經(jīng)懇求到打印機， 又懇求讀卡機。 P2曾經(jīng)懇求到讀卡機， 又懇求打印機。打印機和讀卡機為打印機和讀卡機為非剝奪性資源。非剝奪性資源。例例3 3、 P1 P1，P2P2，P3 P3 三個進程之間通訊：三個進程之間通訊： 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；按以下次序運轉(zhuǎn)：按以下次序運轉(zhuǎn)：P1：RequestS3；ReleaseS1P2：RequestS1；ReleaseS2P3：RequestS2；ReleaseS3P1P3P2S2S3S1P1P2P3按照以上的順序執(zhí)行會產(chǎn)生死鎖嗎？按照以上的順序執(zhí)行會產(chǎn)生死鎖嗎？問題？例例2 2、 在消費者在消費者消費者問題中假設(shè)交換兩個消費者問題中假設(shè)交換兩個P P操作操作 的次序，能夠引起死鎖。的次序，能夠引起死鎖。SiSi暫時性資暫時性資源源3.7 死鎖的根本概念三死鎖的根本概念三消費者進程：

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

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