計算機操作系統(tǒng)第三章處理機調(diào)度與死鎖

1、第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖主要內(nèi)容主要內(nèi)容3.1 3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 3.2 3.2 調(diào)度算法調(diào)度算法 3.3 3.3 實時調(diào)度實時調(diào)度 3.4 3.4 多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度 3.5 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 3.6 3.6 預防死鎖的方法預防死鎖的方法 3.7 3.7 死鎖的檢測與解除死鎖的檢測與解除 在多道程序系統(tǒng)中，一個作業(yè)被提交后必須經(jīng)過處在多道程序系統(tǒng)中，一個作業(yè)被提交后必須經(jīng)過處理機調(diào)度后，方能獲得處理機執(zhí)行。理機調(diào)度后，方能獲得處理機執(zhí)行。對于批量型作業(yè)而言，通常需要經(jīng)歷對于批量

2、型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度作業(yè)調(diào)度(又稱又稱高級調(diào)度或長程調(diào)度高級調(diào)度或長程調(diào)度)和和進程調(diào)度進程調(diào)度(又稱低級調(diào)度或又稱低級調(diào)度或短程調(diào)度短程調(diào)度)兩個過程后方能獲得處理機；兩個過程后方能獲得處理機；對于終端型作業(yè)，則通常只需經(jīng)過進程調(diào)度即可獲對于終端型作業(yè)，則通常只需經(jīng)過進程調(diào)度即可獲得處理機。得處理機。3.1 處理機調(diào)度的基本概念處理機調(diào)度的基本概念 3.1.1 高級、中級和低級調(diào)度高級、中級和低級調(diào)度 1. 高級調(diào)度高級調(diào)度(High Scheduling) 高級調(diào)度高級調(diào)度(High Level Scheduling)又稱為作業(yè)調(diào)又稱為作業(yè)調(diào)度或長程調(diào)度度或長程調(diào)度(LongT

3、erm Scheduling)，其主要功能，其主要功能是根據(jù)某種算法，把是根據(jù)某種算法，把外存上處于后備隊列中的那些作外存上處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存業(yè)調(diào)入內(nèi)存，也就是說，它的，也就是說，它的調(diào)度對象是作業(yè)調(diào)度對象是作業(yè)。在每在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。 1) 接納多少個作業(yè)接納多少個作業(yè) 2) 接納哪些作業(yè)接納哪些作業(yè) 按照先來先服務、短作業(yè)優(yōu)先、作按照先來先服務、短作業(yè)優(yōu)先、作業(yè)優(yōu)先級三種調(diào)度算法。業(yè)優(yōu)先級三種調(diào)度算法。3.1.2 低級調(diào)度低級調(diào)度通常也把低級調(diào)度通常也把低級調(diào)度(Low Level Scheduling)稱為進

4、稱為進程調(diào)度或短程調(diào)度程調(diào)度或短程調(diào)度(ShortTerm Scheduling)，它所，它所調(diào)度的對象是進程調(diào)度的對象是進程(或內(nèi)核級線程或內(nèi)核級線程)。進程調(diào)度是最基本的一種調(diào)度，在多道批處理、分進程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時和實時三種類型的時和實時三種類型的OS中，都必須配置這級調(diào)度。中，都必須配置這級調(diào)度。進程調(diào)度的基本概念進程調(diào)度的基本概念進程調(diào)度的實質(zhì)進程調(diào)度的實質(zhì): 就是將處理器資源合理分配給就是將處理器資源合理分配給適當?shù)?，一方面確保任務的時間約束能被滿足，適當?shù)?，一方面確保任務的時間約束能被滿足，另一方面盡量提高處理器資源的利用率。另一方面盡量提高處理器資源的

5、利用率。進程調(diào)度就是從就緒狀態(tài)的進程中，挑選一個進進程調(diào)度就是從就緒狀態(tài)的進程中，挑選一個進程到處理器上運行。程到處理器上運行。操作系統(tǒng)中負責進程調(diào)度的程序稱為進程調(diào)度器操作系統(tǒng)中負責進程調(diào)度的程序稱為進程調(diào)度器（scheduler）或分派器）或分派器(dispatch）。）。調(diào)度要解決的問題調(diào)度要解決的問題WHAT：按什么原則分配：按什么原則分配CPU 調(diào)度算法調(diào)度算法WHEN：何時分配：何時分配CPU 調(diào)度的時機調(diào)度的時機HOW： 如何分配如何分配CPU 調(diào)度過程及進程的上下文切換調(diào)度過程及進程的上下文切換void OS_Sched (void) INT8U y; OS_ENTER_CRI

6、TICAL(); if (OSIntNesting = 0) & (OSLockNesting = 0) /* Sched. only if all ISRs done & not locked */ y = OSUnMapTblOSRdyGrp; /*Get pointer to HPT ready*/ OSPrioHighRdy = (INT8U)(y OSTCBPrio; self = TRUE; else if (prio = OSTCBCur-OSTCBPrio) /* See if suspending self */ self = TRUE; else self

7、= FALSE; /* No suspending another task */ ptcb = OSTCBPrioTblprio; if (ptcb = (OS_TCB *)0) /* Task to suspend must exist */ OS_EXIT_CRITICAL(); return (OS_TASK_SUSPEND_PRIO); if (OSRdyTblptcb-OSTCBY &= ptcb-OSTCBBitX) = 0 x00) /* Make task not ready */ OSRdyGrp &= ptcb-OSTCBBitY; ptcb-OSTCBS

8、tat |= OS_STAT_SUSPEND; /* Status of task is SUSPENDED */ OS_EXIT_CRITICAL(); if (self = TRUE) /* Context switch only if SELF */ OS_Sched(); return (OS_NO_ERR);1低級調(diào)度的功能低級調(diào)度的功能低級調(diào)度的主要功能如下：低級調(diào)度的主要功能如下：(1)按某種算法選取進程（調(diào)度）。按某種算法選取進程（調(diào)度）。(2)保存處理機的現(xiàn)場信息（上下文切換第一保存處理機的現(xiàn)場信息（上下文切換第一步驟）步驟）(3) 把處理器分配給進程（上下文切換第二步把處理

9、器分配給進程（上下文切換第二步驟）。驟）。2進程調(diào)度中的三個基本機制進程調(diào)度中的三個基本機制為了實現(xiàn)進程調(diào)度，應具有如下三個基本機制：為了實現(xiàn)進程調(diào)度，應具有如下三個基本機制：(1) 排隊器排隊器為了提高進程調(diào)度的效率，應事先將系統(tǒng)中所有的就緒為了提高進程調(diào)度的效率，應事先將系統(tǒng)中所有的就緒進程按照一定的方式排成一個或多個隊列。進程按照一定的方式排成一個或多個隊列。(2) 分派器分派器(調(diào)度程序調(diào)度程序)分派器把由進程調(diào)度程序所選定的進程，從就緒隊列中分派器把由進程調(diào)度程序所選定的進程，從就緒隊列中取出該進程取出該進程, 將處理機分配給它。將處理機分配給它。(3) 上下文切換機制上下文切換機制

10、當對處理機進行切換時，會發(fā)生兩對上下文切換操作。當對處理機進行切換時，會發(fā)生兩對上下文切換操作。 1) 非搶占方式非搶占方式(Non-preemptive Mode)在采用這種調(diào)度方式時，一旦把處理機分配給某進在采用這種調(diào)度方式時，一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下程后，不管它要運行多長時間，都一直讓它運行下去，去，決不會因為時鐘中斷等原因而搶占正在運行進決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經(jīng)分配給它程的處理機，也不允許其它進程搶占已經(jīng)分配給它的處理機。的處理機。直至該進程完成，自愿釋放處理機，或發(fā)生某事件直至該進程完成，自

11、愿釋放處理機，或發(fā)生某事件而被阻塞時，才再把處理機分配給其他進程。而被阻塞時，才再把處理機分配給其他進程。3. 進程調(diào)度方式進程調(diào)度方式 在采用非搶占調(diào)度方式時，可能引起進程調(diào)度的因素可歸在采用非搶占調(diào)度方式時，可能引起進程調(diào)度的因素可歸結(jié)為這樣幾個：結(jié)為這樣幾個： 正在執(zhí)行的進程執(zhí)行完畢，正在執(zhí)行的進程執(zhí)行完畢， 或因發(fā)生某事件而不能再繼續(xù)或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行； 執(zhí)行中的進程因提出執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；請求而暫停執(zhí)行； 在進程通信或同步過程中執(zhí)行了某種原語操作，如在進程通信或同步過程中執(zhí)行了某種原語操作，如P操作操作(wait操作操作)、Block原語、原語

12、、suspend原語等。原語等。 這種調(diào)度方式的優(yōu)點是這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小實現(xiàn)簡單、系統(tǒng)開銷小，適用于大，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務的要求難以滿足緊急任務的要求立立即執(zhí)行，因而可能造成難以預料的后果。顯然，在要求比較即執(zhí)行，因而可能造成難以預料的后果。顯然，在要求比較嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。嚴格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。 2) 搶占方式搶占方式(Preemptive Mode) 這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個正在執(zhí)行的進程，將已分配給該進程

13、的處理機重個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。新分配給另一進程。搶占方式的優(yōu)點：搶占方式的優(yōu)點：可以防止一個長進程長時間占用可以防止一個長進程長時間占用處理機，能為大多數(shù)進程提供更公平的服務，特別處理機，能為大多數(shù)進程提供更公平的服務，特別是能滿足對響應時間有著較嚴格要求的實時任務的是能滿足對響應時間有著較嚴格要求的實時任務的需求。需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占的原則有：搶占的原則有： 優(yōu)先權(quán)原則優(yōu)先權(quán)原則 通常是對一些重要的和緊急的作業(yè)賦通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。予較高的優(yōu)

14、先權(quán)。(2) 短作業(yè)短作業(yè)(進程進程)優(yōu)先原則優(yōu)先原則。 (3) 時間片原則。時間片原則。 3. 中級調(diào)度中級調(diào)度(Intermediate-Level Scheduling) 中級調(diào)度又稱中程調(diào)度中級調(diào)度又稱中程調(diào)度(Medium-Term Scheduling)。 引引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。量。 為此，為此，應使那些暫時不能運行的進程調(diào)至外存上去等待，應使那些暫時不能運行的進程調(diào)至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些。當這些進程重又

15、具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度進程重又具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進程，重新調(diào)來決定把外存上的哪些又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。程調(diào)度。 三種調(diào)度的小結(jié)三種調(diào)度的小結(jié)進程調(diào)度的運行頻率最高，在分時系統(tǒng)中通常是進程調(diào)度的運行頻率最高，在分時系統(tǒng)中通常是10100 ms 便進行一次進程調(diào)度，因此把它稱為短程調(diào)度。為避免便進行一次進程調(diào)度，因此把它稱為短程調(diào)度。為避免進程調(diào)度占用太多的進程調(diào)度占用太多的CPU時間，進程

16、調(diào)度算法不宜太復雜。時間，進程調(diào)度算法不宜太復雜。作業(yè)調(diào)度往往是發(fā)生在一個作業(yè)調(diào)度往往是發(fā)生在一個(批批)作業(yè)運行完畢，退出系統(tǒng)，作業(yè)運行完畢，退出系統(tǒng)，而需要重新調(diào)入一個而需要重新調(diào)入一個(批批)作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周作業(yè)進入內(nèi)存時，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其運行頻率較低，故允許作業(yè)調(diào)度算法花費較多的時間。運行頻率較低，故允許作業(yè)調(diào)度算法花費較多的時間。中級調(diào)度的運行頻率基本上介于上述兩種調(diào)度之間，因此把中級調(diào)度的運行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。它稱為中程調(diào)度。3.1

17、.2 調(diào)度隊列模型調(diào)度隊列模型 1. 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型 圖 3 - 1 僅具有進程調(diào)度的調(diào)度隊列模型 就 緒隊 列阻 塞隊列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完3.2 調(diào)度隊列模型和調(diào)度準則調(diào)度隊列模型和調(diào)度準則1. 僅有進程調(diào)度的調(diào)度隊列模型僅有進程調(diào)度的調(diào)度隊列模型 每個進程在執(zhí)行時都可能出現(xiàn)以下三種情況：每個進程在執(zhí)行時都可能出現(xiàn)以下三種情況：(1) 任務在給定的時間片內(nèi)已經(jīng)完成，該進程便在任務在給定的時間片內(nèi)已經(jīng)完成，該進程便在釋放處理機后進入釋放處理機后進入完成狀態(tài)完成狀態(tài)；(2) 任務在本次分得的時間片內(nèi)尚未完成，任務在本次分得

18、的時間片內(nèi)尚未完成，OS便將便將該任務再放入該任務再放入就緒隊列的末尾就緒隊列的末尾；(3) 在執(zhí)行期間，進程因為某事件而被阻塞后，被在執(zhí)行期間，進程因為某事件而被阻塞后，被OS放入放入阻塞隊列阻塞隊列。2. 具有高級和低級調(diào)度的調(diào)度隊列模型具有高級和低級調(diào)度的調(diào)度隊列模型 圖 3-2 具有高、低兩級調(diào)度的調(diào)度隊列模型 就 緒隊列進程調(diào)度CPU進程完成等待事件1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后備 隊列作業(yè)調(diào)度按一定的作業(yè)調(diào)度算法，從外存的后備隊列中選擇一作業(yè)調(diào)度按一定的作業(yè)調(diào)度算法，從外存的后備隊列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進程，送入就緒隊列，然后

19、才批作業(yè)調(diào)入內(nèi)存，并為它們建立進程，送入就緒隊列，然后才由進程調(diào)度按照一定的進程調(diào)度算法選擇一個進程，把處理機由進程調(diào)度按照一定的進程調(diào)度算法選擇一個進程，把處理機分配給該進程。分配給該進程。當在當在OS 中引入中級調(diào)度后，人們可把進程的就緒中引入中級調(diào)度后，人們可把進程的就緒狀態(tài)分為內(nèi)存就緒狀態(tài)分為內(nèi)存就緒(表示進程在內(nèi)存中就緒表示進程在內(nèi)存中就緒)和外存和外存就緒就緒(進程在外存中就緒進程在外存中就緒)。把阻塞狀態(tài)進一步分成內(nèi)存阻塞和外存阻塞兩種狀把阻塞狀態(tài)進一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。態(tài)。在調(diào)出操作的作用下，可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)在調(diào)出操作的作用下，可使進程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外

20、存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。緒。3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 3. 同時具有三級調(diào)度的調(diào)度隊列模型同時具有三級調(diào)度的調(diào)度隊列模型 圖 3-3 具有三級調(diào)度時的調(diào)度隊列模型 就緒隊列進程調(diào)度CPU就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)3.1.3 處理機調(diào)度算法的目標處理機調(diào)度算法的目標1。調(diào)度算法的共同目標：。調(diào)度算法的共同目標：1、提高資源利用

21、率提高資源利用率CPUCPU利用率利用率= CPU= CPU有效工作時間有效工作時間/(CPU/(CPU有效工作時間有效工作時間+CPU+CPU空閑等待時間空閑等待時間) )2 2、公平性、公平性3 3、系統(tǒng)資源使用的平衡性、系統(tǒng)資源使用的平衡性4 4、策略強制執(zhí)行、策略強制執(zhí)行調(diào)度的原則：滿足用戶的需要和系統(tǒng)的需要。調(diào)度的原則：滿足用戶的需要和系統(tǒng)的需要。（1）周轉(zhuǎn)時間短）周轉(zhuǎn)時間短。，是指從作業(yè)被提交給系統(tǒng)，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔（稱開始，到作業(yè)完成為止的這段時間間隔（稱為作業(yè)周轉(zhuǎn)時間）。為作業(yè)周轉(zhuǎn)時間）。作業(yè)在外存后備隊列上等待調(diào)度的時間作業(yè)在外存后備隊

22、列上等待調(diào)度的時間進程在就緒隊列上等待進程調(diào)度的時間進程在就緒隊列上等待進程調(diào)度的時間進程在進程在CPU上執(zhí)行的時間上執(zhí)行的時間進程等待進程等待IO操作完成的時間。操作完成的時間。 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務的時間與系統(tǒng)為它提供服務的時間Ts之之比，即比，即W=T/Ts，稱為帶權(quán)周轉(zhuǎn)時間，平均帶權(quán)周，稱為帶權(quán)周轉(zhuǎn)時間，平均帶權(quán)周轉(zhuǎn)時間則可表示為轉(zhuǎn)時間則可表示為: （2）系統(tǒng)吞吐量高）系統(tǒng)吞吐量高單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。盡量多選擇短作業(yè)運行。（3）處理機利用率高）處理機利用率高選擇合適的調(diào)度方法和調(diào)度算法提高CPU利用率。選擇大作業(yè)運行。3、分時系統(tǒng)的目標、分時系統(tǒng)的

23、目標（1）響應時間快）響應時間快（2） 均衡性均衡性系統(tǒng)響應時間的快慢與用戶所請求的服務的復雜系統(tǒng)響應時間的快慢與用戶所請求的服務的復雜性相適應。性相適應。分時系統(tǒng)中，所謂響應時間，是從用戶通過分時系統(tǒng)中，所謂響應時間，是從用戶通過鍵盤（或者鼠標）提交一個請求開始，直至鍵盤（或者鼠標）提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應為止的時間。系統(tǒng)首次產(chǎn)生響應為止的時間。響應時間包括三部分時間：響應時間包括三部分時間：從鍵盤輸入的請求信息傳送到處理機的時間。從鍵盤輸入的請求信息傳送到處理機的時間。處理機對請求信息進行處理的時間。處理機對請求信息進行處理的時間。將所形成的響應信息回送到終端顯示器的時間。將

24、所形成的響應信息回送到終端顯示器的時間。4、實時系統(tǒng)的目標、實時系統(tǒng)的目標（1）截至時間的保證）截至時間的保證所謂截止時間，是指某任務所謂截止時間，是指某任務必須開始執(zhí)行的最遲必須開始執(zhí)行的最遲時間時間，或，或必須完成的最遲時間必須完成的最遲時間。（也叫做時限，。（也叫做時限，即即deadlinedeadline）（2）可預測性）可預測性保證任務執(zhí)行的連續(xù)性，執(zhí)行流程能夠事先確定保證任務執(zhí)行的連續(xù)性，執(zhí)行流程能夠事先確定。：正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行（包括：當前執(zhí)行進程被中斷、時不能再繼續(xù)執(zhí)行（包括：當前執(zhí)行進程被中斷、時間片

25、用完了、掛起自己、退出等）；間片用完了、掛起自己、退出等）；執(zhí)行中的進程因提出執(zhí)行中的進程因提出IO請求而暫停執(zhí)行；請求而暫停執(zhí)行；在進程通信或同步過程中執(zhí)行了某種原語操作，如在進程通信或同步過程中執(zhí)行了某種原語操作，如P、V操作原語，操作原語，Block原語，原語， Wakeup原語等。原語等。就緒隊列中新進入了進程。（如創(chuàng)建了新的進程，就緒隊列中新進入了進程。（如創(chuàng)建了新的進程，或者某個進程被喚醒、某個進程被激活）或者某個進程被喚醒、某個進程被激活）調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的系統(tǒng)所規(guī)定的資源分配算法。對于不同的系

26、統(tǒng)目標，通常采用不同的調(diào)度算法。目標，通常采用不同的調(diào)度算法。1.先來先服務先來先服務2.短進程優(yōu)先短進程優(yōu)先3.時間片輪轉(zhuǎn)時間片輪轉(zhuǎn)4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法實時調(diào)度算法實時調(diào)度算法最早截至時間優(yōu)先最早截至時間優(yōu)先EDF算法算法1. 先來先服務調(diào)度算法先來先服務調(diào)度算法(FCFS)缺陷：對待短作業(yè)（進程）不公平，如果他們排在隊缺陷：對待短作業(yè)（進程）不公平，如果他們排在隊列后面，則其等待時間遠大于其執(zhí)行時間。列后面，則其等待時間遠大于其執(zhí)行時間。短作業(yè)短作業(yè)(進程進程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進程是指對短作業(yè)或短進程優(yōu)先調(diào)度的算法。它們可以分別

27、用于作業(yè)調(diào)度和進程調(diào)度優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進程調(diào)度。短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)的調(diào)度算法的調(diào)度算法，是從后備隊列中選擇一個或，是從后備隊列中選擇一個或若干個若干個估計運行時間最短的作業(yè)估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。，將它們調(diào)入內(nèi)存運行。短進程優(yōu)先短進程優(yōu)先(SPF)調(diào)度算法調(diào)度算法，則是從就緒隊列中選出一，則是從就緒隊列中選出一估計估計運行時間最短的進程運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。重新

28、調(diào)度。 (1) 該算法對長作業(yè)不利，如作業(yè)該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)的周轉(zhuǎn)時間由時間由10增至增至16，其帶權(quán)周轉(zhuǎn)時間由，其帶權(quán)周轉(zhuǎn)時間由2增至增至3.1。更嚴重的是，如果有一長作業(yè)。更嚴重的是，如果有一長作業(yè)(進程進程)進進入系統(tǒng)的后備隊列入系統(tǒng)的后備隊列(就緒隊列就緒隊列)，由于調(diào)度程，由于調(diào)度程序總是優(yōu)先調(diào)度那些短作業(yè)序總是優(yōu)先調(diào)度那些短作業(yè)(進程進程)，將導致將導致長作業(yè)長作業(yè)(進程進程)長期不被調(diào)度長期不被調(diào)度。 (2) 不能保證緊迫性作業(yè)不能保證緊迫性作業(yè)(進程進程)會被及時處理。會被及時處理。 (3) 由于作業(yè)由于作業(yè)(進程進程)的長短只是根據(jù)用戶所提的長短只是根據(jù)用戶所

29、提供的估計執(zhí)行時間而定的，而用戶不一定對供的估計執(zhí)行時間而定的，而用戶不一定對執(zhí)行時間估計那么準確，致使該算法不一定執(zhí)行時間估計那么準確，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。能真正做到短作業(yè)優(yōu)先調(diào)度。在時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進程按先來在時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進程按先來先服務的原則，排成一個隊列，每次調(diào)度時，把先服務的原則，排成一個隊列，每次調(diào)度時，把CPUCPU分配給隊首進程。并令其執(zhí)行一個時間片。分配給隊首進程。并令其執(zhí)行一個時間片。時間片處理過程：時間片處理過程：當執(zhí)行的時間片用完時，由一個當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，操作系統(tǒng)便根據(jù)此信號計

30、時器發(fā)出時鐘中斷請求，操作系統(tǒng)便根據(jù)此信號來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；來停止該進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。同時也讓它執(zhí)行一個時間片。以此保證就緒隊列中的所有進程，在一給以此保證就緒隊列中的所有進程，在一給定的時間內(nèi)，均能獲得一時間片的處理機定的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間，換言之，系統(tǒng)能在給定的時間執(zhí)行時間，換言之，系統(tǒng)能在給定的時間內(nèi)，響應所有用戶的請求。內(nèi)，響應所有用戶的請求。內(nèi)核在滿足下列條件時，將把內(nèi)核在滿足下列條件時，將把CPU

31、CPU交給下交給下一個就緒態(tài)的進程：一個就緒態(tài)的進程：當前進程因為某種原因暫停執(zhí)行，如被阻塞；當前進程因為某種原因暫停執(zhí)行，如被阻塞；當前進程在時間片還沒有結(jié)束時已經(jīng)完成了；當前進程在時間片還沒有結(jié)束時已經(jīng)完成了；時間片結(jié)束。時間片結(jié)束。有四個進程按時間片進行輪轉(zhuǎn)調(diào)度有四個進程按時間片進行輪轉(zhuǎn)調(diào)度(按按1個個時間片和時間片和4個時間片進行調(diào)度個時間片進行調(diào)度).1.1.時間片的大小對計算機性能的影響。時間片時間片的大小對計算機性能的影響。時間片太大、太小都不好。太大、太小都不好。2.2.存在的問題：未有效利用系統(tǒng)資源。對于短存在的問題：未有效利用系統(tǒng)資源。對于短的、計算型進程比較有利，因為該進

32、程充分的、計算型進程比較有利，因為該進程充分利用時間片，而利用時間片，而I/OI/O型進程卻不利，因為在兩型進程卻不利，因為在兩次次I/OI/O之間僅需很少的之間僅需很少的CPUCPU時間，卻需要等待時間，卻需要等待一個時間片。一個時間片。3.3.常用于分時系統(tǒng)及事務處理系統(tǒng)。常用于分時系統(tǒng)及事務處理系統(tǒng)。該算法是把該算法是把處理機分配給處理機分配給就緒隊列就緒隊列中優(yōu)先中優(yōu)先級最高的進程級最高的進程。該算法分兩種類型：非搶占式優(yōu)先權(quán)算法該算法分兩種類型：非搶占式優(yōu)先權(quán)算法和搶占式優(yōu)先權(quán)調(diào)度算法和搶占式優(yōu)先權(quán)調(diào)度算法 在這種方式下，系統(tǒng)一旦把處理機分配給就在這種方式下，系統(tǒng)一旦把處理機分配給就

33、緒隊列中緒隊列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進程后，該進程便一的進程后，該進程便一直執(zhí)行下去，直至完成；直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進程。高的進程。在這種方式下，系統(tǒng)同樣是把處理機分配給在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進程，進程調(diào)度程序就立即停止先權(quán)更高的進程，進程調(diào)度程序就立即停止當前進程的執(zhí)行，重新將處

34、理機分配給新到當前進程的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進程。的優(yōu)先權(quán)最高的進程。在采用這種調(diào)度算法時，是在采用這種調(diào)度算法時，是每當系統(tǒng)中出每當系統(tǒng)中出現(xiàn)一個新的就緒進程現(xiàn)一個新的就緒進程i時，就將其優(yōu)先權(quán)時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進程與正在執(zhí)行的進程j的優(yōu)先權(quán)的優(yōu)先權(quán)Pj進行比較進行比較。如果如果PiPj，原進程，原進程Pj便繼續(xù)執(zhí)行；便繼續(xù)執(zhí)行；如果是如果是PiPj, 則立即停止則立即停止Pj的執(zhí)行，做進的執(zhí)行，做進程切換，使程切換，使i進程投入執(zhí)行。進程投入執(zhí)行。 特點：特點：能更好地滿足緊迫作業(yè)的要求，故能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，

35、以而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。及對性能要求較高的批處理和分時系統(tǒng)中。 缺點：缺點：系統(tǒng)開銷較大。系統(tǒng)開銷較大。 靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。的整個運行期間保持不變。動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán) 動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進程時所賦予的優(yōu)先動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能加而改變的，以便獲得更好的調(diào)度性能。 （1 1）進程類型。進程類型。系統(tǒng)進程

36、的優(yōu)先權(quán)高于一系統(tǒng)進程的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。般用戶進程的優(yōu)先權(quán)。 （2 2）進程對資源的需求。進程對資源的需求。對要求少的進程對要求少的進程應賦予較高的優(yōu)先權(quán)。應賦予較高的優(yōu)先權(quán)。 （3 3）用戶要求。用戶要求。按照各進程的執(zhí)行流程和按照各進程的執(zhí)行流程和進程的緊迫程度來指定進程的優(yōu)先權(quán)。進程的緊迫程度來指定進程的優(yōu)先權(quán)。問題在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行得不到保證。，其主要的不足之處是長作業(yè)的運行得不到保證。有沒有什么辦法既考慮到短作業(yè)，又能夠估計長作業(yè)呢？有沒有什么辦法既考慮到短作

37、業(yè)，又能夠估計長作業(yè)呢？如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a 提高，提高，則長作業(yè)在等待一定的時間后，必然有機會分配到處理則長作業(yè)在等待一定的時間后，必然有機會分配到處理機。機。優(yōu)先權(quán)的變化規(guī)律可描述為：優(yōu)先權(quán)的變化規(guī)律可描述為： 要要求求服服務務時時間間要要求求服服務務時時間間等等待待時時間間優(yōu)優(yōu)先先權(quán)權(quán)由于等待時間與服務時間之和，就是系統(tǒng)對該作業(yè)由于等待時間與服務時間之和，就是系統(tǒng)對該作業(yè)的的響應時間響應時間，故該優(yōu)先權(quán)又相當于，故該優(yōu)先權(quán)又相當于響

38、應比響應比RP。要求服務時間要求服務時間響應時間響應時間要求服務時間要求服務時間要求服務時間要求服務時間等待時間等待時間優(yōu)先權(quán)優(yōu)先權(quán)(1) 如果作業(yè)的等待時間相同，則要求服務的時間如果作業(yè)的等待時間相同，則要求服務的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。 (2) 當要求服務的時間相同時，作業(yè)的優(yōu)先權(quán)決當要求服務的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務。因而它實現(xiàn)的是先來先服務。 (3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間對于長作業(yè)，作業(yè)的

39、優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，級便可升到很高， 從而也可獲得處理機。從而也可獲得處理機。 該算法既照顧了短作業(yè)，又考慮了作業(yè)該算法既照顧了短作業(yè)，又考慮了作業(yè)到達的先后次序，不會使長作業(yè)長期得到達的先后次序，不會使長作業(yè)長期得不到服務。不到服務。利用該算法時，每次調(diào)度之前，都須先利用該算法時，每次調(diào)度之前，都須先做響應比的計算，做響應比的計算，會增加系統(tǒng)開銷會增加系統(tǒng)開銷。由于在實時系統(tǒng)中都存在著若干個實時進程由于在實時系統(tǒng)中都存在著若干個實時進程或任務，或任務， 實時進程通常帶有某種程度的實時進程通常帶

40、有某種程度的緊迫性；緊迫性； 需要引入一種新的調(diào)度解決實時進程的調(diào)度，需要引入一種新的調(diào)度解決實時進程的調(diào)度，即實時調(diào)度。即實時調(diào)度。 3.4 實時調(diào)度實時調(diào)度實時系統(tǒng)：實時系統(tǒng)：計算機計算機及時及時響應外部事件的請求，響應外部事件的請求，在在規(guī)定的時間內(nèi)規(guī)定的時間內(nèi)完成對該事件的處理，并控完成對該事件的處理，并控制所有實時設備和實時任務協(xié)調(diào)一致的運行。制所有實時設備和實時任務協(xié)調(diào)一致的運行。提供必要的信息提供必要的信息 （1）就緒時間。）就緒時間。（2）開始截止時間和完成截止時間。）開始截止時間和完成截止時間。（3）處理時間。）處理時間。（4）資源要求。）資源要求。（5）優(yōu)先級。）優(yōu)先級。在

41、實時系統(tǒng)中，通常都有著多個實時任務。若處理在實時系統(tǒng)中，通常都有著多個實時任務。若處理機的處理能力不夠強，則有可能因處理機忙不過來機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務不能得到及時處理，從而導致發(fā)而使某些實時任務不能得到及時處理，從而導致發(fā)生難以預料的后果。生難以預料的后果。假定系統(tǒng)中有假定系統(tǒng)中有m 個周期性的硬實時任務，它們的處個周期性的硬實時任務，它們的處理時間可表示為理時間可表示為Ci，周期時間表示為，周期時間表示為Pi，則在單處，則在單處理機情況下，必須滿足下面的限制條件：理機情況下，必須滿足下面的限制條件：假如系統(tǒng)中有假如系統(tǒng)中有6個硬實時任務，它們的周期時個

42、硬實時任務，它們的周期時間都是間都是 50 ms，而每次的處理時間為，而每次的處理時間為 10 ms，則不難算出，此時是不能滿足上式的，因，則不難算出，此時是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑解決的方法是提高系統(tǒng)的處理能力，其途徑有二：有二：其一仍是采用單處理機系統(tǒng)，但須增強其處理能其一仍是采用單處理機系統(tǒng)，但須增強其處理能力，以顯著地力，以顯著地減少對每一個任務的處理時間減少對每一個任務的處理時間；其二是采用多處理機系統(tǒng)。其二是采用多處理機系統(tǒng)。在含有硬實時任務的實時系統(tǒng)中，廣泛采用在含有硬實時任務的實時系統(tǒng)中，廣泛采用搶占機制搶

43、占機制。當一個優(yōu)先權(quán)更高的任務到達時，。當一個優(yōu)先權(quán)更高的任務到達時，允許暫停當前任務，而令高優(yōu)先權(quán)任務立即允許暫停當前任務，而令高優(yōu)先權(quán)任務立即投入運行，這樣便可滿足該硬實時任務對截投入運行，這樣便可滿足該硬實時任務對截止時間的要求。止時間的要求。 該機制應具有如下兩方面的能力：該機制應具有如下兩方面的能力： (1) 對外部中斷的快速響應能力。對外部中斷的快速響應能力。為使在緊迫的外部事件請求為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應，要求系統(tǒng)具有快速硬件中斷機構(gòu)，還中斷時系統(tǒng)能及時響應，要求系統(tǒng)具有快速硬件中斷機構(gòu)，還應使禁止中斷的時間間隔盡量短，應使禁止中斷的時間間隔盡量短， 以免耽誤

44、時機以免耽誤時機(其它緊迫任其它緊迫任務務)。 (2) 快速的任務分派能力?？焖俚娜蝿辗峙赡芰?。在完成任務調(diào)度后，便應進行任務在完成任務調(diào)度后，便應進行任務切換。為了提高任務切換的速度，切換。為了提高任務切換的速度， 應使系統(tǒng)中的每個運行功應使系統(tǒng)中的每個運行功能單位適當?shù)男?，以減少任務切換的時間開銷。能單位適當?shù)男。詼p少任務切換的時間開銷。 該算法是根據(jù)任務的該算法是根據(jù)任務的開始截止時間（或者結(jié)束截至開始截止時間（或者結(jié)束截至時間）時間）來確定任務的優(yōu)先級。截止時間愈早，其優(yōu)先來確定任務的優(yōu)先級。截止時間愈早，其優(yōu)先級愈高。級愈高。要求在系統(tǒng)中保持一個實時任務就緒隊列，該隊列要求在系統(tǒng)中

45、保持一個實時任務就緒隊列，該隊列按各任務截止時間的早晚排序；按各任務截止時間的早晚排序；具有最早截止時間的任務排在隊列的最前面具有最早截止時間的任務排在隊列的最前面。調(diào)度。調(diào)度程序總是選擇就緒隊列中的第一個任務，為之分配處程序總是選擇就緒隊列中的第一個任務，為之分配處理機，使之投入運行。理機，使之投入運行。 任務調(diào)度EDF調(diào)度當一個進程執(zhí)行完（或不能繼續(xù)執(zhí)行），則換另一當一個進程執(zhí)行完（或不能繼續(xù)執(zhí)行），則換另一個進程占處理機執(zhí)行，稱為進程切換。個進程占處理機執(zhí)行，稱為進程切換。在進程切換時，要保護執(zhí)行現(xiàn)場。在進程切換時，要保護執(zhí)行現(xiàn)場。執(zhí)行現(xiàn)場稱為進程的上下文。包括執(zhí)行現(xiàn)場稱為進程的上下文。

46、包括CPU主要寄存器，主要寄存器，如如SP，PC，通用寄存器。，通用寄存器。進程進程1 1進程進程2 2內(nèi)核調(diào)度程序內(nèi)核調(diào)度程序保存進程保存進程1 1的上下文到的上下文到PCB1PCB1從從PCB2PCB2恢復進程恢復進程2 2的上下文的上下文保存進程保存進程2 2的上下文到的上下文到PCB2PCB2從從PCB1PCB1恢復進程恢復進程1 1的上下文的上下文時間時間1 保存進程上下文環(huán)境保存進程上下文環(huán)境2 更新當前運行進程的控制塊內(nèi)容，將其狀態(tài)改更新當前運行進程的控制塊內(nèi)容，將其狀態(tài)改為就緒或阻塞狀態(tài)為就緒或阻塞狀態(tài)3 將進程控制塊移到相應隊列（就緒隊列或阻塞將進程控制塊移到相應隊列（就緒隊

47、列或阻塞隊列）隊列）4 改變需投入運行進程的控制塊內(nèi)容，將其狀態(tài)改變需投入運行進程的控制塊內(nèi)容，將其狀態(tài)變?yōu)檫\行狀態(tài)變?yōu)檫\行狀態(tài)5 恢復需投入運行進程的上下文環(huán)境恢復需投入運行進程的上下文環(huán)境Linux進程切換（進程切換（context_switch() ）本質(zhì)上）本質(zhì)上兩步：兩步：1) 進程頁表進程頁表PGD切換；切換；2) 內(nèi)核態(tài)堆棧和硬件上下文切換（包括內(nèi)核態(tài)堆棧和硬件上下文切換（包括CPU寄存器）；寄存器）； context_switch()通過調(diào)用通過調(diào)用switch_mm()切切換進程空間，調(diào)用換進程空間，調(diào)用switch_to切換內(nèi)核上下切換內(nèi)核上下文環(huán)境。文環(huán)境。作業(yè)1：分析分

48、析Linux3.0源代碼中的源代碼中的switch_to函數(shù)。搞函數(shù)。搞清楚進程上下文切換的過程。清楚進程上下文切換的過程。所謂死鎖（所謂死鎖（Deadlock），是指），是指多個進程在運多個進程在運行過程中因爭奪資源而造成的一種僵局行過程中因爭奪資源而造成的一種僵局（Deadly- Embrace），當進程處于這種僵），當進程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再持狀態(tài)時，若無外力作用，它們都將無法再向前推進。向前推進。3.5.1、產(chǎn)生死鎖的原因、產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點：產(chǎn)生死鎖的原因可歸結(jié)為如下兩點： （1）競爭資源。）競爭資源。 （2）進程間推進順序非法。

49、）進程間推進順序非法。1）可剝奪和非剝奪性資源）可剝奪和非剝奪性資源可搶占性資源可搶占性資源: 是指某進程在獲得這類資源后，是指某進程在獲得這類資源后，該資源可以再被其他進程或系統(tǒng)剝奪。如該資源可以再被其他進程或系統(tǒng)剝奪。如CPU ，對于這類資源是對于這類資源是不會引起死鎖不會引起死鎖的。的。不可搶占性資源不可搶占性資源: 當系統(tǒng)把這類資源分配給某進當系統(tǒng)把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自行程后，再不能強行收回，只能在進程用完后自行釋放。釋放。 如打印機等，對于這類資源如打印機等，對于這類資源會引起死鎖會引起死鎖。 2）競爭不可搶占性資源）競爭不可搶占性資源在系統(tǒng)中所

50、配置的非剝奪性資源，由于它們的在系統(tǒng)中所配置的非剝奪性資源，由于它們的數(shù)量不能滿足諸進程運行的需要，會使進程在數(shù)量不能滿足諸進程運行的需要，會使進程在運行過程中，因爭奪這些資源而陷入僵局。運行過程中，因爭奪這些資源而陷入僵局。例如，系統(tǒng)中只有一臺打印機例如，系統(tǒng)中只有一臺打印機R1和一臺磁帶機和一臺磁帶機R2，可供進程，可供進程P1和和P2共享。處理不好，在共享。處理不好，在P1與與P2之間會形成僵局，引起死鎖。之間會形成僵局，引起死鎖。 圖 I/O設備共享時的死鎖情況 此箭頭表示P1已經(jīng)獲得R1資源此箭頭表示P1申請R2資源 3）競爭臨時性（可消耗性）競爭臨時性（可消耗性 ）資源）資源 臨時

51、性資源，臨時性資源，也稱之為消耗性資源，也稱之為消耗性資源，它也可能引起死鎖。它也可能引起死鎖。例如：例如：S1、S2和和S3是臨時性資源，是由進是臨時性資源，是由進程程P1、P2和和P3產(chǎn)生的消息。如果消息通信產(chǎn)生的消息。如果消息通信處理順序不當也會發(fā)生死鎖。處理順序不當也會發(fā)生死鎖。圖 3-13 進程之間通信時的死鎖 S2P1S3P3S1P2產(chǎn)生接收2.進程推進順序不當引起死鎖進程推進順序不當引起死鎖1）進程推進順序合法）進程推進順序合法進程推進順序合法不會引起進程死鎖的。進程推進順序合法不會引起進程死鎖的。 2）進程推進順序非法）進程推進順序非法 若并發(fā)進程若并發(fā)進程P1和和P2推進順序

52、不合法，進入推進順序不合法，進入不安全狀態(tài)，于是發(fā)生了進程死鎖。不安全狀態(tài)，于是發(fā)生了進程死鎖。 2. 進程推進順序不當引起死鎖進程推進順序不當引起死鎖 1) 進程推進順序合法進程推進順序合法 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D不安全區(qū)域D除了曲線4外，都是安全的 D 2) 進程推進順序非法進程推進順序非法 若并發(fā)進程若并發(fā)進程P1和和P2按曲線所示的順序推進，按曲線所示的順序推進，它們將進入不安全區(qū)它們將進入不安全區(qū)D內(nèi)。內(nèi)。 此時此時P1保持了資源保持了資源R1, P2保持了資源

53、保持了資源R2, 系統(tǒng)處于系統(tǒng)處于不安全狀態(tài)。因為，這時兩進程再向前推進，便可不安全狀態(tài)。因為，這時兩進程再向前推進，便可能發(fā)生死鎖。能發(fā)生死鎖。例如，當例如，當P1運行到運行到P1:Request(R2)時，將因時，將因R2已被已被P2占用而阻塞；當占用而阻塞；當P2運行到運行到P2: Request(R1)時，也將時，也將因因R1已被已被P1占用而阻塞，于是發(fā)生了進程死鎖。占用而阻塞，于是發(fā)生了進程死鎖。 （1）互斥條件：互斥條件：指進程對所分配到的資源進行排它指進程對所分配到的資源進行排它性使用性使用 。（2）請求和保持條件：）請求和保持條件：指進程已經(jīng)保持了至少一個指進程已經(jīng)保持了至少

54、一個資源，但又提出了新的資源請求資源，但又提出了新的資源請求 。 （3）不可搶占條件：）不可搶占條件：指進程已獲得的資源，在未使指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自用完之前，不能被剝奪，只能在使用完時由自己釋放。己釋放。 （4）環(huán)路等待條件：）環(huán)路等待條件：指在發(fā)生死鎖時，必然存在一指在發(fā)生死鎖時，必然存在一個個進程進程資源的環(huán)形鏈資源的環(huán)形鏈 。（1）預防死鎖）預防死鎖：是通過設置某些限制條件，：是通過設置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預防發(fā)生死鎖。個或幾個條件，來預防發(fā)生死鎖。（2）避免死鎖：

55、）避免死鎖：是在資源的動態(tài)分配過程中，是在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進入不安全狀態(tài)，用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖。從而避免發(fā)生死鎖。 （3）檢測死鎖：）檢測死鎖：通過系統(tǒng)所設置的檢測機構(gòu)，通過系統(tǒng)所設置的檢測機構(gòu)，及時地檢測出死鎖的發(fā)生，并精確地確定與及時地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源；死鎖有關(guān)的進程和資源；（4）解除死鎖：）解除死鎖：當檢測到系統(tǒng)中已發(fā)生死鎖當檢測到系統(tǒng)中已發(fā)生死鎖時，須將進程從死鎖狀態(tài)中解脫出來。常用時，須將進程從死鎖狀態(tài)中解脫出來。常用的實施方法是的實施方法是撤消或掛起一些進程撤消或掛起一些進程。預防死鎖的方

56、法是使四個必要條件中的第預防死鎖的方法是使四個必要條件中的第2、3、4條件之一不能成立，來避免發(fā)生條件之一不能成立，來避免發(fā)生死鎖。至于必要條件死鎖。至于必要條件1，因為它是由設備，因為它是由設備的固有屬性所決定的，不僅不能改變，還的固有屬性所決定的，不僅不能改變，還應加以保證。應加以保證。系統(tǒng)規(guī)定所有進程在開始運行之前，都必須系統(tǒng)規(guī)定所有進程在開始運行之前，都必須一次性地申請其在整個運行過程所需的全部一次性地申請其在整個運行過程所需的全部資源資源。從而進程在整個運行期間，便不會再提出資從而進程在整個運行期間，便不會再提出資源要求，從而摒棄了請求和保持條件，由此源要求，從而摒棄了請求和保持條件

57、，由此可以避免發(fā)生死鎖?？梢员苊獍l(fā)生死鎖。優(yōu)點：優(yōu)點：簡單、易于實現(xiàn)且很安全。簡單、易于實現(xiàn)且很安全。缺點：缺點：資源被嚴重浪費，使進程延遲運行。資源被嚴重浪費，使進程延遲運行。 v 1）摒棄）摒棄“請求和保持請求和保持”條件條件當一個已經(jīng)保持了某些資源的進程，再提出新的資當一個已經(jīng)保持了某些資源的進程，再提出新的資源請求而不能立即得到滿足時，源請求而不能立即得到滿足時，必須釋放它已經(jīng)保必須釋放它已經(jīng)保持了的所有資源。待以后需要時再重新申請持了的所有資源。待以后需要時再重新申請。從而。從而破壞破壞了了“不剝奪不剝奪”條件條件。缺點：這種預防死鎖的方法，實現(xiàn)起來比較復雜且缺點：這種預防死鎖的方法

58、，實現(xiàn)起來比較復雜且要付出很大代價。因為一個資源在使用一段時間后，要付出很大代價。因為一個資源在使用一段時間后，它的被迫釋放可能會造成前段工作的失效。還會使它的被迫釋放可能會造成前段工作的失效。還會使進程前后兩次運行的信息不連續(xù)。進程前后兩次運行的信息不連續(xù)。 這種方法中規(guī)定，系統(tǒng)將所有資源按類型這種方法中規(guī)定，系統(tǒng)將所有資源按類型進行線性排隊，并賦予不同的序號。進行線性排隊，并賦予不同的序號。 所有所有進程對資源的請求必須嚴格按照資源序號進程對資源的請求必須嚴格按照資源序號遞增的次序提出。遞增的次序提出。當進程以及獲取資源當進程以及獲取資源Ri，當且僅當，當且僅當F（Rj）F(Ri)時，才允

59、許其申請資源時，才允許其申請資源Rj。這樣，在所形成的資源分配圖中，不可能這樣，在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路，因而再出現(xiàn)環(huán)路，因而摒棄了摒棄了“環(huán)路等待環(huán)路等待”條條件件。 避免死鎖與預防死鎖的方法不同，不是實現(xiàn)避免死鎖與預防死鎖的方法不同，不是實現(xiàn)采取某種限制措施，破壞產(chǎn)生死鎖的必要條采取某種限制措施，破壞產(chǎn)生死鎖的必要條件，而是在資源動態(tài)分配過程中，防止系統(tǒng)件，而是在資源動態(tài)分配過程中，防止系統(tǒng)進入不安全狀態(tài)，以避免發(fā)生死鎖。進入不安全狀態(tài)，以避免發(fā)生死鎖。1安全狀態(tài)安全狀態(tài)所謂安全狀態(tài)，是指系統(tǒng)能按某種進程順序，如所謂安全狀態(tài)，是指系統(tǒng)能按某種進程順序，如，依次為，依次為n個

60、進程分配其所需資個進程分配其所需資源，直至其最大需求，使每個進程都可順利地完成，源，直至其最大需求，使每個進程都可順利地完成，稱系統(tǒng)處于安全狀態(tài)。稱系統(tǒng)處于安全狀態(tài)。稱稱P1，P2，Pn序列為安全序列。否則，序列為安全序列。否則，如如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)。 進程進程最大需最大需求求已分配已分配還需要還需要可可用用P11055 3P2422P3927 所以所以時刻，不能滿足時刻，不能滿足P3的請求。的請求。避免死鎖的關(guān)鍵在于避免死鎖的關(guān)鍵在于如何準確的預測是否如何準確的預測是否會出現(xiàn)死鎖，從而避免死鎖。會出現(xiàn)死鎖，從而避免死鎖。最有代表性