[理學(xué)]第3章進(jìn)程管理ppt課件

1、第三章第三章 進(jìn)進(jìn) 程程 管管 理理數(shù)學(xué)與計(jì)算機(jī)學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院進(jìn)程調(diào)度進(jìn)程調(diào)度CPU調(diào)度調(diào)度要解決的問(wèn)題要解決的問(wèn)題nWHAT：按什么原那么分配按什么原那么分配CPU 進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法nWHEN：何時(shí)分配何時(shí)分配CPU進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī)nHOW： 如何分配如何分配CPU CPU調(diào)度過(guò)程進(jìn)程的上下文切換調(diào)度過(guò)程進(jìn)程的上下文切換處理機(jī)調(diào)度分成三個(gè)層次處理機(jī)調(diào)度分成三個(gè)層次處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源處理機(jī)調(diào)度算法對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的綜處理機(jī)調(diào)度算法對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響合性能指標(biāo)有重要影響可把處理機(jī)調(diào)度分成三個(gè)層次：可把處理機(jī)

2、調(diào)度分成三個(gè)層次：n 高級(jí)調(diào)度高級(jí)調(diào)度n 中級(jí)調(diào)度中級(jí)調(diào)度 低級(jí)調(diào)度低級(jí)調(diào)度高級(jí)調(diào)度高級(jí)調(diào)度也稱為也稱為作業(yè)調(diào)度或宏觀調(diào)度作業(yè)調(diào)度或宏觀調(diào)度高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天中級(jí)調(diào)度中級(jí)調(diào)度涉及涉及進(jìn)程在內(nèi)外存間的交換進(jìn)程在內(nèi)外存間的交換，從存儲(chǔ)器資，從存儲(chǔ)器資源管理的角度來(lái)看，把進(jìn)程的部分或全部換出到外源管理的角度來(lái)看，把進(jìn)程的部分或全部換出到外存上，可為當(dāng)前運(yùn)行進(jìn)程的執(zhí)行提供所需內(nèi)存空間存上，可為當(dāng)前運(yùn)行進(jìn)程的執(zhí)行提供所需內(nèi)存空間，將當(dāng)前進(jìn)程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必，將當(dāng)前進(jìn)程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問(wèn)須

3、在內(nèi)存里才能被處理機(jī)直接訪問(wèn)低級(jí)調(diào)度低級(jí)調(diào)度也稱也稱微觀調(diào)度微觀調(diào)度，從處理機(jī)資源分配的角度，從處理機(jī)資源分配的角度來(lái)看，處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運(yùn)來(lái)看，處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運(yùn)行狀態(tài)，低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由行狀態(tài)，低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要?jiǎng)?wù)實(shí)現(xiàn)時(shí)做到高效于低級(jí)調(diào)度算法的頻繁使用，要?jiǎng)?wù)實(shí)現(xiàn)時(shí)做到高效處理機(jī)調(diào)度分成三個(gè)層次處理機(jī)調(diào)度分成三個(gè)層次進(jìn)程調(diào)度的職能進(jìn)程調(diào)度的職能1記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況2確定分配處理機(jī)的原那么確定分配處理機(jī)的原那么 3分配處理機(jī)給進(jìn)程分配處理機(jī)給進(jìn)程 4從進(jìn)

4、程收回處理機(jī)從進(jìn)程收回處理機(jī)進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)是進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對(duì)控制協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng)即按一定的調(diào)度算法從就緒隊(duì)列的競(jìng)爭(zhēng)即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給的使用權(quán)交給被選中的進(jìn)程被選中的進(jìn)程進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行運(yùn)行當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)等待當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)等待I/O分時(shí)系統(tǒng)中時(shí)間片到分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒可搶占式當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒可搶占式例如：新創(chuàng)立一個(gè)進(jìn)程，

5、一個(gè)等待進(jìn)程變成例如：新創(chuàng)立一個(gè)進(jìn)程，一個(gè)等待進(jìn)程變成就緒就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作操作P操作，阻塞原語(yǔ)，喚醒原語(yǔ)操作，阻塞原語(yǔ)，喚醒原語(yǔ)進(jìn)程調(diào)度所用的主要數(shù)據(jù)構(gòu)造進(jìn)程調(diào)度所用的主要數(shù)據(jù)構(gòu)造一般情況下，進(jìn)程控制塊一般情況下，進(jìn)程控制塊PCB的組織的組織方式采用的是方式采用的是鏈接表鏈接表方式。方式。因此，在進(jìn)程調(diào)度中所用的主要數(shù)據(jù)因此，在進(jìn)程調(diào)度中所用的主要數(shù)據(jù)構(gòu)造是構(gòu)造是隊(duì)列隊(duì)列進(jìn)程調(diào)度的方式進(jìn)程調(diào)度的方式進(jìn)程調(diào)度的方式可分為進(jìn)程調(diào)度的方式可分為n非剝奪式非剝奪式剝奪式剝奪式進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法1先來(lái)先效勞先來(lái)先效勞2輪轉(zhuǎn)調(diào)度

6、輪轉(zhuǎn)調(diào)度3分級(jí)輪轉(zhuǎn)法分級(jí)輪轉(zhuǎn)法4優(yōu)先數(shù)法優(yōu)先數(shù)法確定算法的原那么確定算法的原那么具有公平性具有公平性資源利用率高特別是資源利用率高特別是CPU利用率利用率在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間 越短越好越短越好在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量先來(lái)先效勞先來(lái)先效勞first come first service, FCFS將用戶作業(yè)和就緒進(jìn)程按提交順序轉(zhuǎn)將用戶作業(yè)和就緒進(jìn)程按提交順序轉(zhuǎn)變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來(lái)先效勞的方式進(jìn)展調(diào)度處理照先來(lái)先效勞的方式進(jìn)展調(diào)度處理，是一種最簡(jiǎn)單的方法是一種最

7、簡(jiǎn)單的方法優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：對(duì)那些執(zhí)行時(shí)間較短的進(jìn)程來(lái)缺點(diǎn)：對(duì)那些執(zhí)行時(shí)間較短的進(jìn)程來(lái)說(shuō)，將等待較長(zhǎng)的時(shí)間，從而降低說(shuō)，將等待較長(zhǎng)的時(shí)間，從而降低CPU的利用率的利用率輪轉(zhuǎn)調(diào)度輪轉(zhuǎn)調(diào)度round robin ,RR讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待時(shí)間與讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待時(shí)間與享受效勞的時(shí)間成比例享受效勞的時(shí)間成比例輪轉(zhuǎn)法只能用來(lái)調(diào)度分配那些輪轉(zhuǎn)法只能用來(lái)調(diào)度分配那些可以搶占可以搶占的資源的資源時(shí)間片長(zhǎng)度的選擇時(shí)間片長(zhǎng)度的選擇是根據(jù)是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求和就緒隊(duì)列中所允許的最大進(jìn)間的要求和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)確定的程數(shù)確定的時(shí)間片的長(zhǎng)短的四個(gè)因素時(shí)間

8、片的長(zhǎng)短的四個(gè)因素時(shí)間片的長(zhǎng)短由如下四個(gè)因素決定：時(shí)間片的長(zhǎng)短由如下四個(gè)因素決定：1系統(tǒng)的響應(yīng)時(shí)間系統(tǒng)的響應(yīng)時(shí)間。當(dāng)進(jìn)程數(shù)目一定時(shí)，。當(dāng)進(jìn)程數(shù)目一定時(shí)，時(shí)間片的長(zhǎng)短直接影響系統(tǒng)的響應(yīng)時(shí)間。時(shí)間片的長(zhǎng)短直接影響系統(tǒng)的響應(yīng)時(shí)間。2就緒隊(duì)列中進(jìn)程的數(shù)目就緒隊(duì)列中進(jìn)程的數(shù)目。這與前面的問(wèn)。這與前面的問(wèn)題正好相反，即當(dāng)系統(tǒng)對(duì)響應(yīng)時(shí)間要求一定題正好相反，即當(dāng)系統(tǒng)對(duì)響應(yīng)時(shí)間要求一定時(shí)，時(shí)間片長(zhǎng)那么就緒隊(duì)列中進(jìn)程數(shù)應(yīng)少，時(shí)，時(shí)間片長(zhǎng)那么就緒隊(duì)列中進(jìn)程數(shù)應(yīng)少，反之亦然。反之亦然。3進(jìn)程狀態(tài)轉(zhuǎn)換的時(shí)間開(kāi)銷進(jìn)程狀態(tài)轉(zhuǎn)換的時(shí)間開(kāi)銷即進(jìn)程由就即進(jìn)程由就緒到運(yùn)行，由運(yùn)行到就緒所需要的時(shí)間。緒到運(yùn)行，由運(yùn)行到就緒所需要的時(shí)

9、間。4計(jì)算機(jī)本身的處理才能計(jì)算機(jī)本身的處理才能。執(zhí)行速度和可。執(zhí)行速度和可運(yùn)行作業(yè)的道數(shù)。運(yùn)行作業(yè)的道數(shù)。多級(jí)反響輪轉(zhuǎn)法多級(jí)反響輪轉(zhuǎn)法round robin with multiple feedback分級(jí)輪轉(zhuǎn)法就是將先前的一個(gè)就緒隊(duì)分級(jí)輪轉(zhuǎn)法就是將先前的一個(gè)就緒隊(duì)列，列，根據(jù)進(jìn)程的優(yōu)先數(shù)不同劃分兩個(gè)根據(jù)進(jìn)程的優(yōu)先數(shù)不同劃分兩個(gè)或兩個(gè)以上的就緒隊(duì)列，并賦給每個(gè)或兩個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先數(shù)隊(duì)列不同的優(yōu)先數(shù)在輪轉(zhuǎn)法中，進(jìn)程參加到就緒隊(duì)列在輪轉(zhuǎn)法中，進(jìn)程參加到就緒隊(duì)列對(duì)進(jìn)程區(qū)別對(duì)待，給予不同的優(yōu)先級(jí)對(duì)進(jìn)程區(qū)別對(duì)待，給予不同的優(yōu)先級(jí)和時(shí)間片，和時(shí)間片，可進(jìn)步系統(tǒng)資源的利用率可進(jìn)步系

10、統(tǒng)資源的利用率優(yōu)先數(shù)法優(yōu)先數(shù)法priority所謂優(yōu)先數(shù)法是指所謂優(yōu)先數(shù)法是指系統(tǒng)或用戶按某種原系統(tǒng)或用戶按某種原那么為進(jìn)程指定一個(gè)優(yōu)先級(jí)來(lái)表示該作那么為進(jìn)程指定一個(gè)優(yōu)先級(jí)來(lái)表示該作業(yè)或進(jìn)程所享有的調(diào)度優(yōu)先權(quán)業(yè)或進(jìn)程所享有的調(diào)度優(yōu)先權(quán)。該算法。該算法的的核心核心是是確定進(jìn)程的優(yōu)先級(jí)確定進(jìn)程的優(yōu)先級(jí)進(jìn)程的優(yōu)先數(shù)進(jìn)程的優(yōu)先數(shù)1進(jìn)程類型。進(jìn)程類型。根據(jù)不同類型的進(jìn)程確定其根據(jù)不同類型的進(jìn)程確定其優(yōu)先數(shù)。優(yōu)先數(shù)。 2運(yùn)行時(shí)間。運(yùn)行時(shí)間。通常規(guī)定進(jìn)程優(yōu)先數(shù)與進(jìn)程通常規(guī)定進(jìn)程優(yōu)先數(shù)與進(jìn)程所需運(yùn)行時(shí)間成反比，即運(yùn)行時(shí)間長(zhǎng)的一所需運(yùn)行時(shí)間成反比，即運(yùn)行時(shí)間長(zhǎng)的一般占用內(nèi)存也較多大作業(yè)，分配給它的優(yōu)般占用內(nèi)存也

11、較多大作業(yè)，分配給它的優(yōu)先數(shù)就越低，反之那么越高。先數(shù)就越低，反之那么越高。 3作業(yè)的優(yōu)先數(shù)。作業(yè)的優(yōu)先數(shù)。根據(jù)作業(yè)的優(yōu)先數(shù)來(lái)決根據(jù)作業(yè)的優(yōu)先數(shù)來(lái)決定其所屬進(jìn)程的優(yōu)先數(shù)。定其所屬進(jìn)程的優(yōu)先數(shù)。 4動(dòng)態(tài)優(yōu)先數(shù)動(dòng)態(tài)優(yōu)先數(shù)優(yōu)先級(jí)確實(shí)定方法優(yōu)先級(jí)確實(shí)定方法優(yōu)先級(jí)確實(shí)定方法優(yōu)先級(jí)確實(shí)定方法動(dòng)態(tài)法動(dòng)態(tài)法靜態(tài)法靜態(tài)法a靜態(tài)法根據(jù)進(jìn)程的靜態(tài)特征，在進(jìn)靜態(tài)法根據(jù)進(jìn)程的靜態(tài)特征，在進(jìn)程開(kāi)場(chǎng)之前就確定它們的優(yōu)先級(jí)，一旦程開(kāi)場(chǎng)之前就確定它們的優(yōu)先級(jí)，一旦開(kāi)場(chǎng)之后就不能改變開(kāi)場(chǎng)之后就不能改變。b動(dòng)態(tài)法把進(jìn)程的靜態(tài)特征和動(dòng)態(tài)特動(dòng)態(tài)法把進(jìn)程的靜態(tài)特征和動(dòng)態(tài)特征結(jié)合起來(lái)確定作業(yè)或進(jìn)程的優(yōu)先級(jí)，征結(jié)合起來(lái)確定作業(yè)或進(jìn)程的優(yōu)先級(jí)

12、，隨著進(jìn)程的執(zhí)行過(guò)程，其優(yōu)先級(jí)不斷變隨著進(jìn)程的執(zhí)行過(guò)程，其優(yōu)先級(jí)不斷變化化。靜態(tài)優(yōu)先級(jí)確實(shí)定原那么靜態(tài)優(yōu)先級(jí)確實(shí)定原那么作業(yè)調(diào)度中的優(yōu)先級(jí)確定的原那么作業(yè)調(diào)度中的優(yōu)先級(jí)確定的原那么由用戶自己根據(jù)作業(yè)的緊急程度輸入由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先級(jí)；一個(gè)適當(dāng)?shù)膬?yōu)先級(jí)；由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級(jí)；先級(jí)；系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級(jí)。級(jí)。進(jìn)程調(diào)度中的優(yōu)先級(jí)確定的原那進(jìn)程調(diào)度中的優(yōu)先級(jí)確定的原那么么按進(jìn)程的類型給予不同的優(yōu)先級(jí)。一般地按進(jìn)程的類型給予不同的優(yōu)先級(jí)。一般地進(jìn)程被分為進(jìn)程被分為系統(tǒng)進(jìn)程系統(tǒng)進(jìn)程和和

13、用戶進(jìn)程用戶進(jìn)程，對(duì)于用，對(duì)于用戶進(jìn)程和系統(tǒng)進(jìn)程均可以再按照功能分為戶進(jìn)程和系統(tǒng)進(jìn)程均可以再按照功能分為不同的類型并賦予不同的優(yōu)先級(jí)。不同的類型并賦予不同的優(yōu)先級(jí)。將作業(yè)的優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)將作業(yè)的優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。靜態(tài)優(yōu)先級(jí)的優(yōu)缺點(diǎn)靜態(tài)優(yōu)先級(jí)的優(yōu)缺點(diǎn)基于靜態(tài)優(yōu)先級(jí)的調(diào)度算法基于靜態(tài)優(yōu)先級(jí)的調(diào)度算法優(yōu)點(diǎn)是優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷小實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷??；缺點(diǎn)是缺點(diǎn)是系統(tǒng)的效率底下，調(diào)度性能不系統(tǒng)的效率底下，調(diào)度性能不高高動(dòng)態(tài)優(yōu)先級(jí)確實(shí)定原那么動(dòng)態(tài)優(yōu)先級(jí)確實(shí)定原那么根據(jù)根據(jù)進(jìn)程占有進(jìn)程占有CPU的時(shí)間的長(zhǎng)短的時(shí)間的長(zhǎng)短來(lái)決來(lái)決定定根據(jù)根據(jù)就緒進(jìn)程等待就緒進(jìn)程等待CPU的時(shí)間長(zhǎng)

14、短的時(shí)間長(zhǎng)短來(lái)來(lái)決定決定動(dòng)態(tài)優(yōu)先級(jí)的優(yōu)缺點(diǎn)動(dòng)態(tài)優(yōu)先級(jí)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)是優(yōu)點(diǎn)是調(diào)度性能高，系統(tǒng)資源的利用率調(diào)度性能高，系統(tǒng)資源的利用率高高缺點(diǎn)是缺點(diǎn)是系統(tǒng)開(kāi)銷大系統(tǒng)開(kāi)銷大根據(jù)已占有處理機(jī)的進(jìn)程是否可被剝奪而分根據(jù)已占有處理機(jī)的進(jìn)程是否可被剝奪而分為為優(yōu)先占有法和優(yōu)先剝奪法優(yōu)先占有法和優(yōu)先剝奪法兩種。兩種。a優(yōu)先占有法的原理是：優(yōu)先占有法的原理是：一旦某個(gè)最高優(yōu)一旦某個(gè)最高優(yōu)先數(shù)的就緒進(jìn)程分得處理機(jī)之后，只要不是先數(shù)的就緒進(jìn)程分得處理機(jī)之后，只要不是其自身的原因被阻塞如要求其自身的原因被阻塞如要求I/O操作而不操作而不能繼續(xù)運(yùn)行時(shí)，就一直運(yùn)行下去，直至運(yùn)行能繼續(xù)運(yùn)行時(shí)，就一直運(yùn)行下去，直至運(yùn)行完畢。完

15、畢。b優(yōu)先剝奪法的原理是：優(yōu)先剝奪法的原理是：當(dāng)一個(gè)正在運(yùn)行當(dāng)一個(gè)正在運(yùn)行的進(jìn)程即使其時(shí)間片未用完，無(wú)論什么時(shí)候的進(jìn)程即使其時(shí)間片未用完，無(wú)論什么時(shí)候，只要就緒隊(duì)列中有一個(gè)比它的優(yōu)先數(shù)高的，只要就緒隊(duì)列中有一個(gè)比它的優(yōu)先數(shù)高的進(jìn)程，優(yōu)先數(shù)高的進(jìn)程就可以取代以前正在進(jìn)程，優(yōu)先數(shù)高的進(jìn)程就可以取代以前正在運(yùn)行的進(jìn)程，投入運(yùn)行運(yùn)行的進(jìn)程，投入運(yùn)行優(yōu)先占有法和優(yōu)先剝奪法優(yōu)先占有法和優(yōu)先剝奪法例：例：調(diào)度用的進(jìn)程狀態(tài)切換圖調(diào)度用的進(jìn)程狀態(tài)切換圖 進(jìn)程調(diào)度的主要問(wèn)題就是采用某種算法進(jìn)程調(diào)度的主要問(wèn)題就是采用某種算法合理有效合理有效地把處理機(jī)分配給進(jìn)程，其調(diào)地把處理機(jī)分配給進(jìn)程，其調(diào)度算法應(yīng)盡可能度算法應(yīng)盡

16、可能進(jìn)步資源的利用率進(jìn)步資源的利用率，減減少處理機(jī)的空閑時(shí)間少處理機(jī)的空閑時(shí)間。對(duì)于用戶作業(yè)采。對(duì)于用戶作業(yè)采用較合理的平均響應(yīng)時(shí)間，以及盡可能用較合理的平均響應(yīng)時(shí)間，以及盡可能地增強(qiáng)處理機(jī)的處理才能，防止有些作地增強(qiáng)處理機(jī)的處理才能，防止有些作業(yè)長(zhǎng)期不能投入運(yùn)行。這些業(yè)長(zhǎng)期不能投入運(yùn)行。這些“合理的原合理的原那么那么往往是互相制約的，甚至是矛盾往往是互相制約的，甚至是矛盾的，難以全部到達(dá)要求的，難以全部到達(dá)要求進(jìn)程調(diào)度的主要問(wèn)題進(jìn)程調(diào)度的主要問(wèn)題死鎖死鎖Deadlock死鎖的根本概念死鎖的根本概念死鎖的解決方案死鎖的解決方案預(yù)防，防止，檢測(cè)及解除預(yù)防，防止，檢測(cè)及解除死鎖的解決方案死鎖的解決

17、方案產(chǎn)生死鎖的例子產(chǎn)生死鎖的例子申請(qǐng)不同類型資源產(chǎn)生死鎖申請(qǐng)不同類型資源產(chǎn)生死鎖P1：申請(qǐng)打印機(jī)申請(qǐng)打印機(jī)申請(qǐng)掃描儀申請(qǐng)掃描儀使用使用釋放打印機(jī)釋放打印機(jī)釋放掃描儀釋放掃描儀P2：申請(qǐng)掃描儀申請(qǐng)掃描儀申請(qǐng)打印機(jī)申請(qǐng)打印機(jī)使用使用釋放打印機(jī)釋放打印機(jī)釋放掃描儀釋放掃描儀 設(shè)系統(tǒng)有一臺(tái)打印機(jī)設(shè)系統(tǒng)有一臺(tái)打印機(jī)R1R1一臺(tái)掃描儀一臺(tái)掃描儀R2R2，兩進(jìn)，兩進(jìn)程共享這兩臺(tái)設(shè)備。程共享這兩臺(tái)設(shè)備。 用信號(hào)量用信號(hào)量S1S1表示表示R1R1是否可用，用信號(hào)量是否可用，用信號(hào)量S2S2表示表示R2R2是否是否可用，可用， S1S1、 S2S2初值為初值為1 1.P P( (S S1 1) )P P( (S

18、S2 2) )占用占用R R1 1占用占用R R2 2V V( (S S2 2) )V V( (S S1 1) ).P P( (S S2 2) )P P( (S S1 1) )占用占用R R1 1占用占用R R2 2V V( (S S1 1) )V V( (S S2 2) ).進(jìn)程進(jìn)程A A進(jìn)程進(jìn)程B B死鎖的解決方案死鎖的解決方案R1R1R2R2簡(jiǎn)單的死鎖例子簡(jiǎn)單的死鎖例子 死鎖的解決方案死鎖的解決方案產(chǎn)生死鎖現(xiàn)象的原因產(chǎn)生死鎖現(xiàn)象的原因系統(tǒng)提供的資源不能滿足每個(gè)進(jìn)程的使系統(tǒng)提供的資源不能滿足每個(gè)進(jìn)程的使用用在多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合在多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理理死鎖的定義死

19、鎖的定義一組進(jìn)程中，每個(gè)進(jìn)程都一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待無(wú)限等待被該被該組進(jìn)程中另一進(jìn)程所占有的資源，因此組進(jìn)程中另一進(jìn)程所占有的資源，因此永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程關(guān)于死鎖的一些結(jié)論關(guān)于死鎖的一些結(jié)論參與死鎖的進(jìn)程最少是兩個(gè)參與死鎖的進(jìn)程最少是兩個(gè)兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子參與死鎖的進(jìn)程是當(dāng)前系

20、統(tǒng)中所有進(jìn)程的子集集注：假如死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)注：假如死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。資源，甚至導(dǎo)致系統(tǒng)崩潰。資源資源永久性資源永久性資源：可以被多個(gè)進(jìn)程屢次使用：可以被多個(gè)進(jìn)程屢次使用可再用資源可再用資源n可搶占資源可搶占資源n不可搶占資源不可搶占資源臨時(shí)性資源臨時(shí)性資源：只可使用一次的資源；如信：只可使用一次的資源；如信號(hào)量號(hào)量,中斷信號(hào)，同步信號(hào)等可消耗性資中斷信號(hào)，同步信號(hào)等可消耗性資源源“申請(qǐng)申請(qǐng)-分配分配-使用使用-釋放釋放形式形式產(chǎn)生死鎖的四個(gè)必要條件產(chǎn)生死鎖的四個(gè)必要條件互斥使用資源獨(dú)占互斥使用資源獨(dú)占不可侵占不可剝奪不可侵占不可剝奪懇求和保持部分分配，占

21、有申請(qǐng)懇求和保持部分分配，占有申請(qǐng)循環(huán)等待循環(huán)等待產(chǎn)生死鎖的四個(gè)必要條件產(chǎn)生死鎖的四個(gè)必要條件1 互斥使用資源獨(dú)占互斥使用資源獨(dú)占n一個(gè)資源每次只能給一個(gè)進(jìn)程使用一個(gè)資源每次只能給一個(gè)進(jìn)程使用2 不可侵占不可剝奪不可侵占不可剝奪資源申請(qǐng)者不能強(qiáng)行的從資源占有者手資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋中奪取資源，資源只能由占有者自愿釋放放產(chǎn)生死鎖的四個(gè)必要條件產(chǎn)生死鎖的四個(gè)必要條件3 懇求和保持懇求和保持部分分配，占有申請(qǐng)部分分配，占有申請(qǐng)一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持對(duì)原有資源的占有對(duì)原有資源的占有 只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配

22、只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配產(chǎn)生死鎖的四個(gè)必要條件產(chǎn)生死鎖的四個(gè)必要條件 存在一個(gè)進(jìn)程等待隊(duì)列存在一個(gè)進(jìn)程等待隊(duì)列 P1 , P2 , , Pn,其中其中P1等待等待P2占有的資源，占有的資源，P2等待等待P3占有的資源，占有的資源，Pn等待等待P1占有的占有的資源，形成一個(gè)進(jìn)程等待環(huán)路資源，形成一個(gè)進(jìn)程等待環(huán)路1死鎖是進(jìn)程之間的一種特殊關(guān)系，死鎖是進(jìn)程之間的一種特殊關(guān)系，是由資源競(jìng)爭(zhēng)引起的僵局關(guān)系，因此，是由資源競(jìng)爭(zhēng)引起的僵局關(guān)系，因此，當(dāng)我們提到死鎖時(shí)，至少涉及到兩個(gè)進(jìn)當(dāng)我們提到死鎖時(shí)，至少涉及到兩個(gè)進(jìn)程。雖然單個(gè)進(jìn)程也可能鎖住自己，但程。雖然單個(gè)進(jìn)程也可能鎖住自己，但那是程序設(shè)計(jì)錯(cuò)誤而

23、不是死鎖；那是程序設(shè)計(jì)錯(cuò)誤而不是死鎖；2當(dāng)出現(xiàn)死鎖時(shí)，首先要弄清楚被鎖當(dāng)出現(xiàn)死鎖時(shí)，首先要弄清楚被鎖的是哪些進(jìn)程，因競(jìng)爭(zhēng)哪些資源被鎖；的是哪些進(jìn)程，因競(jìng)爭(zhēng)哪些資源被鎖；關(guān)于死鎖的進(jìn)一步說(shuō)明關(guān)于死鎖的進(jìn)一步說(shuō)明關(guān)于死鎖的進(jìn)一步說(shuō)明關(guān)于死鎖的進(jìn)一步說(shuō)明3在多數(shù)情況下，一系統(tǒng)出現(xiàn)死鎖，是指在多數(shù)情況下，一系統(tǒng)出現(xiàn)死鎖，是指系統(tǒng)內(nèi)的一些而不是全部進(jìn)程被鎖，它們是系統(tǒng)內(nèi)的一些而不是全部進(jìn)程被鎖，它們是因競(jìng)爭(zhēng)某些而不是全部資源而進(jìn)入死鎖的，因競(jìng)爭(zhēng)某些而不是全部資源而進(jìn)入死鎖的，假設(shè)系統(tǒng)的全部進(jìn)程都被鎖住，我們稱系統(tǒng)假設(shè)系統(tǒng)的全部進(jìn)程都被鎖住，我們稱系統(tǒng)處于癱瘓狀態(tài)；處于癱瘓狀態(tài)；4系統(tǒng)癱瘓意味著所有進(jìn)程都

24、進(jìn)入了睡眠系統(tǒng)癱瘓意味著所有進(jìn)程都進(jìn)入了睡眠等待狀態(tài)，但所有進(jìn)程都睡眠了，假如等待狀態(tài)，但所有進(jìn)程都睡眠了，假如其中至少有一個(gè)進(jìn)程可由其中至少有一個(gè)進(jìn)程可由I/O中斷喚醒的話，中斷喚醒的話，這并不一定就是癱瘓狀態(tài)。這并不一定就是癱瘓狀態(tài)。死鎖定理死鎖定理1假如不出現(xiàn)任何環(huán)，那么此時(shí)系假如不出現(xiàn)任何環(huán)，那么此時(shí)系統(tǒng)內(nèi)不存在死鎖統(tǒng)內(nèi)不存在死鎖2假如出現(xiàn)了環(huán)，且處于此環(huán)中的假如出現(xiàn)了環(huán)，且處于此環(huán)中的每類資源均只有一個(gè)實(shí)體時(shí)，那么有環(huán)每類資源均只有一個(gè)實(shí)體時(shí)，那么有環(huán)就出現(xiàn)死鎖，此時(shí)，環(huán)是系統(tǒng)存在死鎖就出現(xiàn)死鎖，此時(shí)，環(huán)是系統(tǒng)存在死鎖的的充分必要條件充分必要條件解決死鎖的方法解決死鎖的方法不考慮此問(wèn)

25、題：不考慮此問(wèn)題：不讓死鎖發(fā)生：不讓死鎖發(fā)生： 靜態(tài)策略：設(shè)計(jì)適宜的資源分配算法，靜態(tài)策略：設(shè)計(jì)適宜的資源分配算法，不讓死鎖發(fā)生不讓死鎖發(fā)生 動(dòng)態(tài)策略：動(dòng)態(tài)策略：讓死鎖發(fā)生：讓死鎖發(fā)生：死鎖預(yù)防死鎖預(yù)防定義：定義：在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。詳細(xì)的做法是發(fā)生死鎖。詳細(xì)的做法是破壞產(chǎn)生死鎖的四破壞產(chǎn)生死鎖的四個(gè)必要條件之一個(gè)必要條件之一，如允許進(jìn)程同時(shí)訪問(wèn)某些，如允許進(jìn)程同時(shí)訪問(wèn)某些資源，然而，這種方法不能解決訪問(wèn)那些不資源，然而，這種方法不能解決訪問(wèn)那些不允許被同時(shí)訪問(wèn)的資源帶來(lái)的死鎖問(wèn)題，比允許被同時(shí)訪問(wèn)的資源帶來(lái)的死鎖問(wèn)題，比方打印機(jī)等

26、。另一種方法那么是打破資源的方打印機(jī)等。另一種方法那么是打破資源的部分分配這個(gè)死鎖產(chǎn)生的必要條件。即預(yù)先部分分配這個(gè)死鎖產(chǎn)生的必要條件。即預(yù)先分配各并發(fā)進(jìn)程所需要的全部資源。分配各并發(fā)進(jìn)程所需要的全部資源。 另一種死鎖的預(yù)防方法是打破死鎖的環(huán)路另一種死鎖的預(yù)防方法是打破死鎖的環(huán)路條件。即把資源分類按順序排列，使進(jìn)程在條件。即把資源分類按順序排列，使進(jìn)程在申請(qǐng)、保持資源時(shí)不形成環(huán)路。申請(qǐng)、保持資源時(shí)不形成環(huán)路。死鎖預(yù)防死鎖預(yù)防破壞破壞“不可剝奪不可剝奪條件條件在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即得到滿足而

27、變?yōu)榈却隣顟B(tài)之前，必須釋得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，假設(shè)需要再重新放已占有的全部資源，假設(shè)需要再重新申請(qǐng)申請(qǐng)死鎖預(yù)防死鎖預(yù)防破壞破壞“懇求和保持懇求和保持條件條件要求每個(gè)進(jìn)程在運(yùn)行前必須一次性要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請(qǐng)它所要求的所有資源，且僅當(dāng)該進(jìn)申請(qǐng)它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才給予一次性分程所要資源均可滿足時(shí)才給予一次性分配配死鎖預(yù)防死鎖預(yù)防破壞破壞“循環(huán)等待循環(huán)等待條件條件采用資源有序分配法：采用資源有序分配法：把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次序資源時(shí)必須嚴(yán)格按資源編號(hào)

28、的遞增次序進(jìn)展，否那么操作系統(tǒng)不予分配進(jìn)展，否那么操作系統(tǒng)不予分配死鎖防止定義死鎖防止定義定義：定義：在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)可以滿足的資源申請(qǐng)進(jìn)展動(dòng)每一個(gè)系統(tǒng)可以滿足的資源申請(qǐng)進(jìn)展動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果斷定是否分配態(tài)檢查，并根據(jù)檢查結(jié)果斷定是否分配資源，假設(shè)分配后系統(tǒng)可能發(fā)生死鎖，資源，假設(shè)分配后系統(tǒng)可能發(fā)生死鎖，那么不予分配，否那么予以分配那么不予分配，否那么予以分配平安狀態(tài)與不平安狀態(tài)平安狀態(tài)與不平安狀態(tài)平安狀態(tài)：平安狀態(tài)：假如存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的平假如存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的平安序列安序列P1，Pn，那么系統(tǒng)處于平安狀態(tài)，

29、那么系統(tǒng)處于平安狀態(tài)平安序列：平安序列： 一個(gè)進(jìn)程序列一個(gè)進(jìn)程序列P1，Pn是平安的，假是平安的，假如對(duì)于每一個(gè)進(jìn)程如對(duì)于每一個(gè)進(jìn)程Pi1in，它以后尚需要，它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程程Pj j i 當(dāng)前占有資源量之和，系統(tǒng)處于當(dāng)前占有資源量之和，系統(tǒng)處于平安狀態(tài)平安狀態(tài) 平安狀態(tài)一定是沒(méi)有死鎖發(fā)生的平安狀態(tài)一定是沒(méi)有死鎖發(fā)生的平安狀態(tài)與不平安狀態(tài)平安狀態(tài)與不平安狀態(tài)不平安狀態(tài)不平安狀態(tài):n不存在一個(gè)平安序列不存在一個(gè)平安序列不平安狀態(tài)一定導(dǎo)致死鎖不平安狀態(tài)一定導(dǎo)致死鎖死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除死鎖檢測(cè)：死鎖檢測(cè)：允許死

30、鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生一旦死鎖發(fā)生那么采取專門(mén)的措施，一旦死鎖發(fā)生那么采取專門(mén)的措施，解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行運(yùn)行死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除檢測(cè)時(shí)機(jī)：檢測(cè)時(shí)機(jī)：n當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖其缺點(diǎn)是系統(tǒng)的開(kāi)銷大其缺點(diǎn)是系統(tǒng)的開(kāi)銷大n定時(shí)檢測(cè)定時(shí)檢測(cè)系統(tǒng)資源利用率下降時(shí)檢測(cè)死鎖系統(tǒng)資源利用率下降時(shí)檢測(cè)死鎖死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除死鎖檢測(cè)算法死鎖檢測(cè)算法每個(gè)進(jìn)程和資源指定唯一編號(hào)每個(gè)進(jìn)程和資源指定唯一編號(hào)設(shè)置一張資源分配表設(shè)置一張資源

31、分配表記錄各進(jìn)程與其占用資源之間的關(guān)系記錄各進(jìn)程與其占用資源之間的關(guān)系設(shè)置一張進(jìn)程等待表設(shè)置一張進(jìn)程等待表記錄各進(jìn)程與要申請(qǐng)資源之間的關(guān)系記錄各進(jìn)程與要申請(qǐng)資源之間的關(guān)系死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除死鎖的解除死鎖的解除重要的是以最小的代價(jià)恢復(fù)系統(tǒng)的運(yùn)重要的是以最小的代價(jià)恢復(fù)系統(tǒng)的運(yùn)行。方法如下：行。方法如下：n重新啟動(dòng)重新啟動(dòng)n撤消進(jìn)程撤消進(jìn)程n剝奪資源剝奪資源進(jìn)程回退進(jìn)程回退處理死鎖的綜合措施處理死鎖的綜合措施Howard在在1973年提出將解決死鎖的根本年提出將解決死鎖的根本方法組合起來(lái)，并對(duì)由不同類資源競(jìng)爭(zhēng)所引起方法組合起來(lái)，并對(duì)由不同類資源競(jìng)爭(zhēng)所引起的死鎖采用對(duì)它來(lái)說(shuō)是最正確的方法來(lái)解決，的死鎖采用對(duì)它來(lái)說(shuō)是最正確的方法來(lái)解決，以此來(lái)全面解決死鎖問(wèn)題。這一個(gè)思想是基于以此來(lái)全面解決死鎖問(wèn)題。這一個(gè)思