第三章-湯小丹-計算機操作系統(tǒng)-官方課件-第四版-計算機-操作系統(tǒng)--課件學(xué)習(xí)教案

1、會計學(xué)1第三章第三章-湯小丹湯小丹-計算機操作系統(tǒng)計算機操作系統(tǒng)(co zu x tn)-官方課件官方課件-第四版第四版-計算機計算機-操作系統(tǒng)操作系統(tǒng)(co zu x tn)-課件課件第一頁，共127頁。3.1 處理機調(diào)度的層次和調(diào)度算處理機調(diào)度的層次和調(diào)度算法的目標(biāo)法的目標(biāo)在多道程序系統(tǒng)中，調(diào)度的在多道程序系統(tǒng)中，調(diào)度的實質(zhì)是一種資源分配，處理機調(diào)實質(zhì)是一種資源分配，處理機調(diào)第1頁/共126頁第二頁，共127頁。3.1.1 3.1.1 處理機調(diào)度的層次處理機調(diào)度的層次(cngc)(cngc)1. 1. 高級調(diào)度高級調(diào)度(High Level (High Level 第2頁/共126頁第三頁

2、，共127頁。3.1.2 3.1.2 處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法的目標(biāo)1. 1. 處理機調(diào)度算法的共同處理機調(diào)度算法的共同目標(biāo)目標(biāo)第3頁/共126頁第四頁，共127頁。(2) 公平性。公平性是指應(yīng)公平性。公平性是指應(yīng)使諸進程都獲得合理的使諸進程都獲得合理的CPU 時間，時間，不會發(fā)生進程饑餓現(xiàn)象。公平性不會發(fā)生進程饑餓現(xiàn)象。公平性是相對的，對相同類型的進程應(yīng)是相對的，對相同類型的進程應(yīng)獲得相同的服務(wù)；但對于不同類獲得相同的服務(wù)；但對于不同類型的進程，由于其緊急程度或重型的進程，由于其緊急程度或重要性的不同，則應(yīng)提供不同的服要性的不同，則應(yīng)提供不同的服務(wù)。務(wù)。(3) 平衡性。由于在系統(tǒng)中

3、平衡性。由于在系統(tǒng)中執(zhí)行。執(zhí)行。第4頁/共126頁第五頁，共127頁。2. 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)(1) 平均周轉(zhuǎn)時間短。平均周轉(zhuǎn)時間短。對每個用戶而言，都希望自對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，則總是希計算機系統(tǒng)的管理者，則總是希Tn1Tn1ii第5頁/共126頁第六頁，共127頁。為了進一步反映調(diào)度的性能，為了進一步反映調(diào)度的性能，更清晰地描述各進程在其周轉(zhuǎn)時更清晰地描述各進程在其周轉(zhuǎn)時間中，等待和執(zhí)行時間的具體分間中，等待和執(zhí)行時間的具體分 n1isiTTn1W第6頁/共126頁第七頁，共127頁。(2) 系統(tǒng)吞

4、吐量高。由于吞系統(tǒng)吞吐量高。由于吞吐量是指在單位時間內(nèi)系統(tǒng)所完吐量是指在單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)，因而它與批處理作成的作業(yè)數(shù)，因而它與批處理作業(yè)的平均長度有關(guān)。事實上，如業(yè)的平均長度有關(guān)。事實上，如果單純是為了獲得高的系統(tǒng)吞吐果單純是為了獲得高的系統(tǒng)吞吐量，就應(yīng)盡量多地選擇短作業(yè)運量，就應(yīng)盡量多地選擇短作業(yè)運行。行。第7頁/共126頁第八頁，共127頁。第8頁/共126頁第九頁，共127頁。第9頁/共126頁第十頁，共127頁。3.2 3.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度第10頁/共126頁第十一頁，共127頁。3.2.1 3.2.1 批處理系統(tǒng)批處理系統(tǒng)(xtng)(xtng)中中第11

5、頁/共126頁第十二頁，共127頁。2. 作業(yè)控制塊作業(yè)控制塊(Job Control Block，JCB)為了管理和調(diào)度為了管理和調(diào)度(diod)作作業(yè)，在多道批處理系統(tǒng)中，為每業(yè)，在多道批處理系統(tǒng)中，為每個作業(yè)設(shè)置了一個作業(yè)控制塊個作業(yè)設(shè)置了一個作業(yè)控制塊JCB，它是作業(yè)在系統(tǒng)中存在的，它是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對作業(yè)進標(biāo)志，其中保存了系統(tǒng)對作業(yè)進小等小等)、資源使用情況等。、資源使用情況等。第12頁/共126頁第十三頁，共127頁。3. 作業(yè)運行的三個階段和三作業(yè)運行的三個階段和三種狀態(tài)種狀態(tài)作業(yè)從進入作業(yè)從進入(jnr)系統(tǒng)到運系統(tǒng)到運行結(jié)束，通常需要經(jīng)歷收容、運行結(jié)束

6、，通常需要經(jīng)歷收容、運第13頁/共126頁第十四頁，共127頁。3.2.2 3.2.2 作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)是，根作業(yè)調(diào)度的主要任務(wù)是，根據(jù)據(jù)(gnj)JCB(gnj)JCB中的信息，檢查系中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對資源統(tǒng)中的資源能否滿足作業(yè)對資源的需求，以及按照一定的調(diào)度算的需求，以及按照一定的調(diào)度算法，從外存的后備隊列中選取某法，從外存的后備隊列中選取某第14頁/共126頁第十五頁，共127頁。3.2.3 3.2.3 先來先服務(wù)先來先服務(wù)(FCFS)(FCFS)和短和短作業(yè)優(yōu)先作業(yè)優(yōu)先(SJF)(SJF)調(diào)度算法調(diào)度算法1. 1. 先來先服務(wù)

7、先來先服務(wù)(first-come (first-come first-servedfirst-served，F(xiàn)CFS)FCFS)調(diào)度算法調(diào)度算法FCFSFCFS是最簡單的調(diào)度算法，是最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可該算法既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。當(dāng)在作業(yè)調(diào)度中用于進程調(diào)度。當(dāng)在作業(yè)調(diào)度中程。然后把它放入就緒隊列。程。然后把它放入就緒隊列。第15頁/共126頁第十六頁，共127頁。2. 短作業(yè)優(yōu)先短作業(yè)優(yōu)先(short job first，SJF)的調(diào)度算法的調(diào)度算法由于在實際情況中，短作業(yè)由于在實際情況中，短作業(yè)(進程進程)占有很大比例，為了能使占有很大比例，為了能使它

8、們能比長作業(yè)優(yōu)先執(zhí)行，而產(chǎn)它們能比長作業(yè)優(yōu)先執(zhí)行，而產(chǎn)生了短作業(yè)優(yōu)先調(diào)度算法。生了短作業(yè)優(yōu)先調(diào)度算法。1) 短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法第16頁/共126頁第十七頁，共127頁。2) 短作業(yè)優(yōu)先算法的缺點短作業(yè)優(yōu)先算法的缺點(qudin)SJF調(diào)度算法較之調(diào)度算法較之FCFS算法算法有了明顯的改進，但仍然存在不有了明顯的改進，但仍然存在不容忽視的缺點容忽視的缺點(qudin)：(1) 必須預(yù)知作業(yè)的運行時必須預(yù)知作業(yè)的運行時間。在采用這種算法時，要先知間。在采用這種算法時，要先知第17頁/共126頁第十八頁，共127頁。(3) 在采用在采用FCFS算法時，算法時，人人機無法實現(xiàn)交互。機無法實現(xiàn)

9、交互。第18頁/共126頁第十九頁，共127頁。3.2.4 3.2.4 優(yōu)先級調(diào)度算法和高響優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法應(yīng)比優(yōu)先調(diào)度算法1. 1. 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法(priority-scheduling (priority-scheduling algorithmalgorithm，PSA)PSA)我們可以這樣來看作業(yè)的優(yōu)我們可以這樣來看作業(yè)的優(yōu)程度。程度。第19頁/共126頁第二十頁，共127頁。2. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法(Highest Response Ratio Next，HRRN) 在批處理系統(tǒng)中，在批處理系統(tǒng)中，F(xiàn)CFS算算法所考慮的只是作

10、業(yè)的等待時間，法所考慮的只是作業(yè)的等待時間，而忽視了作業(yè)的運行時間。而而忽視了作業(yè)的運行時間。而的性能。的性能。第20頁/共126頁第二十一頁，共127頁。高響應(yīng)比優(yōu)先算法是如何實高響應(yīng)比優(yōu)先算法是如何實現(xiàn)的呢現(xiàn)的呢? 如果我們能為每個作業(yè)如果我們能為每個作業(yè)引入一個動態(tài)優(yōu)先級，即優(yōu)先級引入一個動態(tài)優(yōu)先級，即優(yōu)先級要求服務(wù)時間要求服務(wù)時間等待時間優(yōu)先權(quán)第21頁/共126頁第二十二頁，共127頁。由于等待時間與服務(wù)時間之由于等待時間與服務(wù)時間之要求服務(wù)時間響應(yīng)時間要求服務(wù)時間要求服務(wù)時間等待時間PR第22頁/共126頁第二十三頁，共127頁。3.3 3.3 進進 程程 調(diào)調(diào) 度度第23頁/共12

11、6頁第二十四頁，共127頁。3.3.1 3.3.1 進程調(diào)度的任務(wù)、機制進程調(diào)度的任務(wù)、機制和方式和方式1. 1. 進程調(diào)度的任務(wù)進程調(diào)度的任務(wù)第24頁/共126頁第二十五頁，共127頁。2. 進程調(diào)度進程調(diào)度(diod)機制機制為了實現(xiàn)進程調(diào)度為了實現(xiàn)進程調(diào)度(diod)，在進程調(diào)度在進程調(diào)度(diod)機制中，應(yīng)機制中，應(yīng)第25頁/共126頁第二十六頁，共127頁。第26頁/共126頁第二十七頁，共127頁。3. 進程調(diào)度方式進程調(diào)度方式1) 非搶占方式非搶占方式(Nonpreemptive Mode)在采用這種調(diào)度方式時，一在采用這種調(diào)度方式時，一第27頁/共126頁第二十八頁，共127

12、頁。2) 搶占方式搶占方式(Preemptive Mode)這種調(diào)度方式允許調(diào)度程序這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個正在根據(jù)某種原則，去暫停某個正在執(zhí)行的進程，將已分配給該進程執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。的處理機重新分配給另一進程。在現(xiàn)代在現(xiàn)代OS中廣泛采用搶占方式，中廣泛采用搶占方式，但搶占方式比較復(fù)雜，所需付出但搶占方式比較復(fù)雜，所需付出的系統(tǒng)開銷也較大。的系統(tǒng)開銷也較大。第28頁/共126頁第二十九頁，共127頁。3.3.2 3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法1. 1. 輪轉(zhuǎn)法的基本原理輪轉(zhuǎn)法的基本原理在輪轉(zhuǎn)在輪轉(zhuǎn)(RR)(RR)法中，系統(tǒng)將

13、所法中，系統(tǒng)將所有的就緒進程按有的就緒進程按FCFSFCFS策略排成一策略排成一個就緒隊列。系統(tǒng)可設(shè)置每隔一個就緒隊列。系統(tǒng)可設(shè)置每隔一定時間定時間( (如如3030ms)ms)便產(chǎn)生一次中斷，便產(chǎn)生一次中斷，第29頁/共126頁第三十頁，共127頁。2. 進程切換時機進程切換時機在在RR調(diào)度算法中，應(yīng)在何調(diào)度算法中，應(yīng)在何時進行時進行(jnxng)進程的切換，可進程的切換，可分為兩種情況：分為兩種情況： 若一個時間片若一個時間片尚未用完，正在運行的進程便已尚未用完，正在運行的進程便已第30頁/共126頁第三十一頁，共127頁。3. 時間片大小的確定時間片大小的確定在輪轉(zhuǎn)算法中，時間片的大在輪

14、轉(zhuǎn)算法中，時間片的大小對系統(tǒng)性能有很大的小對系統(tǒng)性能有很大的影響。影響。 第31頁/共126頁第三十二頁，共127頁。第32頁/共126頁第三十三頁，共127頁。第33頁/共126頁第三十四頁，共127頁。3.3.3 3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法1. 1. 優(yōu)先級調(diào)度算法的類型優(yōu)先級調(diào)度算法的類型優(yōu)先級進程調(diào)度算法，是把優(yōu)先級進程調(diào)度算法，是把第34頁/共126頁第三十五頁，共127頁。2. 優(yōu)先級的類型優(yōu)先級的類型1) 靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級是在創(chuàng)建進程時靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，在進程的整個運行期間確定的，在進程的整個運行期間保持不變。優(yōu)先級是利用某一范保持不變。

15、優(yōu)先級是利用某一范第35頁/共126頁第三十六頁，共127頁。2) 動態(tài)優(yōu)先級動態(tài)優(yōu)先級動態(tài)優(yōu)先級是指在創(chuàng)建進程動態(tài)優(yōu)先級是指在創(chuàng)建進程第36頁/共126頁第三十七頁，共127頁。3.3.4 3.3.4 多隊列調(diào)度算法多隊列調(diào)度算法如前所述的各種調(diào)度算法，如前所述的各種調(diào)度算法，尤其在應(yīng)用于進程調(diào)度時，由于尤其在應(yīng)用于進程調(diào)度時，由于系統(tǒng)中僅設(shè)置一個進程的就緒隊系統(tǒng)中僅設(shè)置一個進程的就緒隊列，即低級調(diào)度算法是固定的、列，即低級調(diào)度算法是固定的、第37頁/共126頁第三十八頁，共127頁。3.3.5 3.3.5 多級反饋隊列多級反饋隊列(multileved feedback queue)(mu

16、ltileved feedback queue)調(diào)度算法調(diào)度算法第38頁/共126頁第三十九頁，共127頁。第39頁/共126頁第四十頁，共127頁。(2) 每個隊列都采用每個隊列都采用FCFS算算法。當(dāng)新進程進入內(nèi)存后，首先法。當(dāng)新進程進入內(nèi)存后，首先將它放入第一隊列的末尾，按將它放入第一隊列的末尾，按FCFS原則等待調(diào)度。當(dāng)輪到該原則等待調(diào)度。當(dāng)輪到該進程執(zhí)行時，如它能在該時間片進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可撤離內(nèi)完成，便可撤離(chl)系統(tǒng)。系統(tǒng)。第40頁/共126頁第四十一頁，共127頁。(3) 按隊列優(yōu)先級調(diào)度。調(diào)按隊列優(yōu)先級調(diào)度。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列度程序首先調(diào)

17、度最高優(yōu)先級隊列中的諸進程運行，僅當(dāng)?shù)谝魂犃兄械闹T進程運行，僅當(dāng)?shù)谝魂犃锌臻e時才調(diào)度第二隊列中的進程空閑時才調(diào)度第二隊列中的進程運行；換言之，僅當(dāng)?shù)谶\行；換言之，僅當(dāng)?shù)?(i-1)所所第41頁/共126頁第四十二頁，共127頁。2. 調(diào)度算法的性能調(diào)度算法的性能在多級反饋在多級反饋(fnku)隊列調(diào)隊列調(diào)度算法中，如果規(guī)定第一個隊列度算法中，如果規(guī)定第一個隊列第42頁/共126頁第四十三頁，共127頁。3.3.6 3.3.6 基于公平原則的調(diào)度算基于公平原則的調(diào)度算法法1. 1. 保證調(diào)度算法保證調(diào)度算法保證調(diào)度算法是另外一種類保證調(diào)度算法是另外一種類型的調(diào)度算法，它向用戶所做出型的調(diào)度算法，

18、它向用戶所做出第43頁/共126頁第四十四頁，共127頁。在實施公平調(diào)度算法時系統(tǒng)在實施公平調(diào)度算法時系統(tǒng)中必須具有這樣一些功能：中必須具有這樣一些功能：(1) 跟蹤計算每個進程自創(chuàng)跟蹤計算每個進程自創(chuàng)建以來已經(jīng)執(zhí)行的處理時間。建以來已經(jīng)執(zhí)行的處理時間。(2) 計算每個進程應(yīng)獲得的計算每個進程應(yīng)獲得的處理機時間，即自創(chuàng)建以來的時處理機時間，即自創(chuàng)建以來的時間除以間除以n。(3) 計算進程獲得處理機時計算進程獲得處理機時它，并讓該進程一直運行，直到它，并讓該進程一直運行，直到超過最接近它的進程比率為止。超過最接近它的進程比率為止。第44頁/共126頁第四十五頁，共127頁。2. 公平分享調(diào)度算法

19、公平分享調(diào)度算法分配給每個進程相同的處理分配給每個進程相同的處理第45頁/共126頁第四十六頁，共127頁。3.4 實實 時時 調(diào)調(diào) 度度在實時系統(tǒng)中，可能存在著在實時系統(tǒng)中，可能存在著兩類不同性質(zhì)的實時任務(wù)，即兩類不同性質(zhì)的實時任務(wù)，即第46頁/共126頁第四十七頁，共127頁。3.4.1 3.4.1 實現(xiàn)實時調(diào)度的基本條實現(xiàn)實時調(diào)度的基本條件件1. 1. 提供必要的信息提供必要的信息為了實現(xiàn)實時調(diào)度，系統(tǒng)應(yīng)為了實現(xiàn)實時調(diào)度，系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的信息：向調(diào)度程序提供有關(guān)任務(wù)的信息：第47頁/共126頁第四十八頁，共127頁。(3) 處理時間，一個任務(wù)從處理時間，一個任務(wù)從開始執(zhí)行，

20、直至開始執(zhí)行，直至(zhzh)完成時所完成時所需的時間。需的時間。(4) 資源要求，任務(wù)執(zhí)行時資源要求，任務(wù)執(zhí)行時所需的一組資源。所需的一組資源。第48頁/共126頁第四十九頁，共127頁。2. 系統(tǒng)處理能力強系統(tǒng)處理能力強在實時系統(tǒng)中，若處理機的在實時系統(tǒng)中，若處理機的處理能力不夠強，則有可能因處處理能力不夠強，則有可能因處理機忙不過，而致使某些實時任理機忙不過，而致使某些實時任務(wù)不能得到及時處理，從而導(dǎo)致務(wù)不能得到及時處理，從而導(dǎo)致1PCm1iii第49頁/共126頁第五十頁，共127頁。提高系統(tǒng)處理能力提高系統(tǒng)處理能力(nngl)的途徑有二：一是采用單處理機的途徑有二：一是采用單處理機系

21、統(tǒng)，但須增強其處理能力系統(tǒng)，但須增強其處理能力NPCm1iii第50頁/共126頁第五十一頁，共127頁。3. 采用搶占式調(diào)度機制采用搶占式調(diào)度機制(jzh)在含有在含有HRT任務(wù)的實時系統(tǒng)任務(wù)的實時系統(tǒng)第51頁/共126頁第五十二頁，共127頁。4. 具有快速切換機制具有快速切換機制為保證硬實時任務(wù)能及時運為保證硬實時任務(wù)能及時運行，在系統(tǒng)行，在系統(tǒng)(xtng)中還應(yīng)具有中還應(yīng)具有快速切換機制，使之能進行任務(wù)快速切換機制，使之能進行任務(wù)的快速切換。該機制應(yīng)具有如下的快速切換。該機制應(yīng)具有如下兩方面的能力：兩方面的能力：(1) 對中斷的快速響應(yīng)能力。對中斷的快速響應(yīng)能力。第52頁/共126頁第

22、五十三頁，共127頁。3.4.2 3.4.2 實時調(diào)度算法的分類實時調(diào)度算法的分類(fn li) (fn li) 可以按不同方式對實時調(diào)度可以按不同方式對實時調(diào)度第53頁/共126頁第五十四頁，共127頁。1. 非搶占式調(diào)度算法非搶占式調(diào)度算法第54頁/共126頁第五十五頁，共127頁。2. 搶占式調(diào)度算法搶占式調(diào)度算法可根據(jù)搶占發(fā)生可根據(jù)搶占發(fā)生(fshng)時時間的不同而進一步分成以下兩種間的不同而進一步分成以下兩種調(diào)度算法：調(diào)度算法：第55頁/共126頁第五十六頁，共127頁。第56頁/共126頁第五十七頁，共127頁。3.4.3 3.4.3 最早截止時間最早截止時間(shjin)(sh

23、jin)優(yōu)先優(yōu)先EDF(Earliest Deadline EDF(Earliest Deadline 第57頁/共126頁第五十八頁，共127頁。第58頁/共126頁第五十九頁，共127頁。2. 搶占式調(diào)度方式用于周期搶占式調(diào)度方式用于周期(zhuq)實時任務(wù)實時任務(wù)圖圖3-7示出了將該算法用于搶示出了將該算法用于搶第59頁/共126頁第六十頁，共127頁。第60頁/共126頁第六十一頁，共127頁。3.4.4 3.4.4 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF(Least Laxity First)LLF(Least Laxity First)算法算法該算法在確定任務(wù)的優(yōu)先級該算法在確定任務(wù)的

24、優(yōu)先級時，根據(jù)的是任務(wù)的緊急時，根據(jù)的是任務(wù)的緊急( (或松或松弛弛) )程度。任務(wù)緊急程度愈高，程度。任務(wù)緊急程度愈高，賦予該任務(wù)的優(yōu)先級就愈高，以賦予該任務(wù)的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行使之優(yōu)先執(zhí)行(zhxng)(zhxng)。該算法主要用于可搶占調(diào)度該算法主要用于可搶占調(diào)度、A3A3、和和B1B1、B2B2、B3B3、，見圖，見圖3-83-8。第61頁/共126頁第六十二頁，共127頁。第62頁/共126頁第六十三頁，共127頁。第63頁/共126頁第六十四頁，共127頁。3.4.5 3.4.5 優(yōu)先級倒置優(yōu)先級倒置(priority (priority inversion proble

25、m) inversion problem) 1. 1. 優(yōu)先級倒置的形成優(yōu)先級倒置的形成當(dāng)前當(dāng)前OSOS廣泛采用優(yōu)先級調(diào)度廣泛采用優(yōu)先級調(diào)度第64頁/共126頁第六十五頁，共127頁。假如假如P3最先執(zhí)行，在執(zhí)行了最先執(zhí)行，在執(zhí)行了P(mutex)操作后，進入到臨界區(qū)操作后，進入到臨界區(qū)第65頁/共126頁第六十六頁，共127頁。第66頁/共126頁第六十七頁，共127頁。2. 優(yōu)先級倒置的解決方法優(yōu)先級倒置的解決方法一種簡單的解決方法是規(guī)定：一種簡單的解決方法是規(guī)定：第67頁/共126頁第六十八頁，共127頁。第68頁/共126頁第六十九頁，共127頁。3.5 死死 鎖鎖 概概 述述3.5.

26、1 資源問題資源問題在系統(tǒng)中有許多在系統(tǒng)中有許多(xdu)不不第69頁/共126頁第七十頁，共127頁。1. 可重用性資源和消耗性資可重用性資源和消耗性資源源1) 可重用性資源可重用性資源可重用性資源是一種可供用可重用性資源是一種可供用戶重復(fù)使用多次的資源，它具有戶重復(fù)使用多次的資源，它具有如下性質(zhì)：如下性質(zhì)：(1) 每一個可重用性資源中每一個可重用性資源中的單元只能分配給一個進程的單元只能分配給一個進程(jnchng)使用，不允許多個進使用，不允許多個進程程(jnchng)共享。共享。(3) 系統(tǒng)中每一類可重用性系統(tǒng)中每一類可重用性資源中的單元數(shù)目是相對固定的，資源中的單元數(shù)目是相對固定的，

27、進程進程(jnchng)在運行期間既不在運行期間既不能創(chuàng)建也不能刪除它。能創(chuàng)建也不能刪除它。第70頁/共126頁第七十一頁，共127頁。2) 可消耗性資源可消耗性資源可消耗性資源又稱為臨時性可消耗性資源又稱為臨時性資源，它是在進程運行期間，由資源，它是在進程運行期間，由進程動態(tài)地創(chuàng)建和消耗的，它具進程動態(tài)地創(chuàng)建和消耗的，它具有如下性質(zhì)：有如下性質(zhì)： 每一類可消耗性每一類可消耗性資源的單元數(shù)目在進程運行期間資源的單元數(shù)目在進程運行期間第71頁/共126頁第七十二頁，共127頁。2. 可搶占性資源和不可搶占可搶占性資源和不可搶占性資源性資源1) 可搶占性資源可搶占性資源可把系統(tǒng)中的資源分成兩類，可

28、把系統(tǒng)中的資源分成兩類，一類是可搶占性資源，是指某進一類是可搶占性資源，是指某進第72頁/共126頁第七十三頁，共127頁。3.5.2 3.5.2 計算機系統(tǒng)中的死鎖計算機系統(tǒng)中的死鎖1. 1. 競爭競爭(jngzhng)(jngzhng)不可搶不可搶占性資源引起死鎖占性資源引起死鎖第73頁/共126頁第七十四頁，共127頁。第74頁/共126頁第七十五頁，共127頁。第75頁/共126頁第七十六頁，共127頁。2. 競爭可消耗資源引起死鎖競爭可消耗資源引起死鎖現(xiàn)在進一步介紹競爭可消耗現(xiàn)在進一步介紹競爭可消耗第76頁/共126頁第七十七頁，共127頁。第77頁/共126頁第七十八頁，共127頁

29、。3. 進程推進順序不當(dāng)引起死進程推進順序不當(dāng)引起死鎖鎖除了系統(tǒng)中多個進程對資源除了系統(tǒng)中多個進程對資源第78頁/共126頁第七十九頁，共127頁。1) 進程推進順序合法進程推進順序合法(hf)在進程在進程P1和和P2并發(fā)執(zhí)行時，并發(fā)執(zhí)行時，如果按圖如果按圖3-14中的曲線所示的中的曲線所示的順序推進：順序推進：P1：Request(R1)P1：Request(R2)P1：Releast(R1)P1：推進順序是合法推進順序是合法(hf)的。的。第79頁/共126頁第八十頁，共127頁。2) 進程推進順序非法進程推進順序非法若并發(fā)進程若并發(fā)進程P1和和P2按圖按圖3-14中曲線所示的順序推進，它

30、們中曲線所示的順序推進，它們將進入不安全區(qū)將進入不安全區(qū)D內(nèi)。此時內(nèi)。此時P1保保持了資源持了資源R1，P2保持了資源保持了資源R2，系統(tǒng)系統(tǒng)(xtng)處于不安全狀態(tài)。處于不安全狀態(tài)。第80頁/共126頁第八十一頁，共127頁。第81頁/共126頁第八十二頁，共127頁。3.5.3 3.5.3 死鎖的定義、必要條件死鎖的定義、必要條件和處理和處理(chl)(chl)方法方法第82頁/共126頁第八十三頁，共127頁。2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件雖然進程在運行過程中可能雖然進程在運行過程中可能會發(fā)生死鎖，但產(chǎn)生進程死鎖是會發(fā)生死鎖，但產(chǎn)生進程死鎖是必須具備一定條件的。綜上所述必須

31、具備一定條件的。綜上所述第83頁/共126頁第八十四頁，共127頁。3. 處理處理(chl)死鎖的方法死鎖的方法目前處理目前處理(chl)死鎖的方法死鎖的方法第84頁/共126頁第八十五頁，共127頁。3.6 3.6 預(yù)預(yù) 防防 死死 鎖鎖第85頁/共126頁第八十六頁，共127頁。3.6.1 3.6.1 破壞破壞“請求和保持請求和保持”條條件件為了能破壞為了能破壞“請求和保持請求和保持”條件，系統(tǒng)必須保證做到：當(dāng)一條件，系統(tǒng)必須保證做到：當(dāng)一個進程在請求資源時，它不能持個進程在請求資源時，它不能持第86頁/共126頁第八十七頁，共127頁。2. 第二種協(xié)議第二種協(xié)議第87頁/共126頁第八十

32、八頁，共127頁。3.6.2 3.6.2 破壞破壞“不可搶占不可搶占”條件條件為了能破壞為了能破壞“不可搶占不可搶占”條條件，協(xié)議中規(guī)定件，協(xié)議中規(guī)定(gudng)(gudng)，當(dāng)，當(dāng)一個已經(jīng)保持了某些不可被搶占一個已經(jīng)保持了某些不可被搶占第88頁/共126頁第八十九頁，共127頁。3.6.3 3.6.3 破壞破壞“循環(huán)循環(huán)(xnhun)(xnhun)等等待待”條件條件第89頁/共126頁第九十頁，共127頁。3.7 3.7 避避 免免 死死 鎖鎖第90頁/共126頁第九十一頁，共127頁。3.7.13.7.1系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)在死鎖避免方法中，把系統(tǒng)在死鎖避免方法中，把系統(tǒng)的狀態(tài)分為

33、安全狀態(tài)和不安全狀的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。當(dāng)系統(tǒng)處于安全狀態(tài)時，可態(tài)。當(dāng)系統(tǒng)處于安全狀態(tài)時，可避免發(fā)生死鎖。反之避免發(fā)生死鎖。反之(fnzh)(fnzh)，第91頁/共126頁第九十二頁，共127頁。2. 安全狀態(tài)之例安全狀態(tài)之例假定假定(jidng)系統(tǒng)中有三個系統(tǒng)中有三個進程進程P1、P2和和P3，共有，共有12臺磁帶臺磁帶第92頁/共126頁第九十三頁，共127頁。3. 由安全狀態(tài)向不安全狀態(tài)由安全狀態(tài)向不安全狀態(tài)第93頁/共126頁第九十四頁，共127頁。3.7.2 3.7.2 利用銀行家算法避免利用銀行家算法避免(bmin)(bmin)死鎖死鎖最有代表性的避免最有代表性的避免

34、(bmin)(bmin)死鎖的算法是死鎖的算法是DijkstraDijkstra的銀行家的銀行家第94頁/共126頁第九十五頁，共127頁。1. 銀行家算法銀行家算法(sun f)中的中的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)為了實現(xiàn)銀行家算法為了實現(xiàn)銀行家算法(sun f)，在系統(tǒng)中必須設(shè)置這樣四個，在系統(tǒng)中必須設(shè)置這樣四個數(shù)據(jù)結(jié)構(gòu)，分別用來描述系統(tǒng)中數(shù)據(jù)結(jié)構(gòu)，分別用來描述系統(tǒng)中第95頁/共126頁第九十六頁，共127頁。2. 銀行家算法銀行家算法(sun f)設(shè)設(shè)Requesti是進程是進程Pi的請求的請求向量，如果向量，如果Requestij=K，表示，表示進程進程Pi需要需要K個個Rj類型的資源。類型的資源

35、。當(dāng)當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：述步驟進行檢查：第96頁/共126頁第九十七頁，共127頁。(3) 系統(tǒng)試探著把資源分配系統(tǒng)試探著把資源分配(fnpi)給進程給進程Pi，并修改下面數(shù)，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：據(jù)結(jié)構(gòu)中的數(shù)值：Availablej = Availablej-Requestij; Allocationi, j = Allocationi, j+Requestij;恢復(fù)原來的資源分配恢復(fù)原來的資源分配(fnpi)狀態(tài)，狀態(tài)，讓進程讓進程Pi等待。等待。第97頁/共126頁第九十八頁，共127頁。3. 安全性算法安全性算法系統(tǒng)所執(zhí)行的安全性

36、算法可系統(tǒng)所執(zhí)行的安全性算法可描述描述(mio sh)如下：如下：(1) 設(shè)置兩個向量：設(shè)置兩個向量： 工作工作向量向量Work，它表示系統(tǒng)可提供給，它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)進程繼續(xù)運行所需的各類資源數(shù)true。第98頁/共126頁第九十九頁，共127頁。(2) 從進程集合中找到一個從進程集合中找到一個能滿足下述條件的進程：能滿足下述條件的進程： Finishi=false; Needi, jWorkj;若找到，執(zhí)行步驟若找到，執(zhí)行步驟(3)，否則，否則，執(zhí)行步驟執(zhí)行步驟(4)。(3) 當(dāng)進程當(dāng)進程Pi獲得資源后，可獲得資源后，可第99頁/共126頁第一百頁，共127頁。

37、4. 銀行家算法之例銀行家算法之例假定系統(tǒng)中有五個進程假定系統(tǒng)中有五個進程P0, 第100頁/共126頁第一百零一頁，共127頁。第101頁/共126頁第一百零二頁，共127頁。(1) T0時刻的安全性：利用時刻的安全性：利用安全性算法對安全性算法對T0時刻的資源分配時刻的資源分配第102頁/共126頁第一百零三頁，共127頁。第103頁/共126頁第一百零四頁，共127頁。(2) P1請求資源：請求資源：P1發(fā)出請發(fā)出請求向量求向量Request1(1, 0, 2)，系統(tǒng)按，系統(tǒng)按銀行家算法進行檢查：銀行家算法進行檢查： Request1(1, 0, 2)Need1(1, 2, 2)； Re

38、quest1(1, 0, 第104頁/共126頁第一百零五頁，共127頁。第105頁/共126頁第一百零六頁，共127頁。(3) P4請求資源：請求資源：P4發(fā)出請發(fā)出請求向量求向量Request4(3，3，0)，系統(tǒng)，系統(tǒng)按銀行家算法進行按銀行家算法進行(jnxng)檢查：檢查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，讓，讓P4等待。等待。第106頁/共126頁第一百零七頁，共127頁。第107頁/共126頁第一百零八頁，共127頁。(5) 進行安全性檢查：可用進行安全性檢查：可用第108頁/共126頁第一百

39、零九頁，共127頁。3.8 死鎖的檢測與解除死鎖的檢測與解除如果在系統(tǒng)中，既不采取死如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免鎖預(yù)防措施，也未配有死鎖避免算法，系統(tǒng)很可能會發(fā)生死鎖。算法，系統(tǒng)很可能會發(fā)生死鎖。第109頁/共126頁第一百一十頁，共127頁。3.8.1 3.8.1 死鎖的檢測死鎖的檢測為了能對系統(tǒng)中是否已發(fā)生為了能對系統(tǒng)中是否已發(fā)生了死鎖進行檢測，在系統(tǒng)中必須：了死鎖進行檢測，在系統(tǒng)中必須： 保存有關(guān)資源的請求和分配保存有關(guān)資源的請求和分配第110頁/共126頁第一百一十一頁，共127頁。該圖是由一組結(jié)點該圖是由一組結(jié)點N和一組和一組邊邊E所組成的一個對偶所組成的一個

40、對偶G=(N, E)，它具有下述形式的定義和限，它具有下述形式的定義和限制：制：(1) 把把N分為兩個互斥的子集，分為兩個互斥的子集，即一組進程結(jié)點即一組進程結(jié)點P=P1, P2, , Pn和一組資源結(jié)點和一組資源結(jié)點R=R1, R2, , Rn，N=PR。在圖。在圖3-19所示的例子所示的例子(l zi)中，中，P=P1, ，R=，N= 。圖圖3-19中示出了兩個請求邊和兩中示出了兩個請求邊和兩個分配邊，即個分配邊，即E=(P1, R2), (R2, P2), (P2, R1), (R1, P1)。第111頁/共126頁第一百一十二頁，共127頁。第112頁/共126頁第一百一十三頁，共12

41、7頁。2死鎖定理死鎖定理(dngl)我們可以利用把資源分配圖我們可以利用把資源分配圖加以簡化的方法加以簡化的方法(圖圖3-19)，來檢，來檢測當(dāng)系統(tǒng)處于測當(dāng)系統(tǒng)處于S狀態(tài)時，是否為狀態(tài)時，是否為死鎖狀態(tài)。簡化方法如下：死鎖狀態(tài)。簡化方法如下：(1) 在資源分配圖中，找出在資源分配圖中，找出第113頁/共126頁第一百一十四頁，共127頁。第114頁/共126頁第一百一十五頁，共127頁。(2) P1釋放資源后，便可使釋放資源后，便可使P2獲得資源而繼續(xù)運行，直至獲得資源而繼續(xù)運行，直至P2完成完成(wn chng)后又釋放出它所后又釋放出它所占有的全部資源，形成圖占有的全部資源，形成圖(c)所示所示第115頁/共126頁第一百一十六頁，共127頁。3死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)類似死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)類似于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：(1) 可利用資源向量可利用資源向量Available，它表示了它表示了m類資源中每一類資源類資源中每一類資源的可用數(shù)目。的可用數(shù)