軟件技術(shù)處理器管理ppt課件

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)機(jī)械工業(yè)出版社計(jì)算機(jī)軟件技術(shù)基礎(chǔ)機(jī)械工業(yè)出版社第八章第八章處置器管理處置器管理本章根本內(nèi)容與要求本章根本內(nèi)容與要求n根本內(nèi)容根本內(nèi)容n作業(yè)的概念作業(yè)的概念n進(jìn)程的概念進(jìn)程的概念n進(jìn)程形狀及進(jìn)程控制進(jìn)程形狀及進(jìn)程控制n處置機(jī)調(diào)度處置機(jī)調(diào)度n進(jìn)程的同步和互斥進(jìn)程的同步和互斥n死鎖問題死鎖問題n要求要求n掌握進(jìn)程的概念及作用掌握進(jìn)程的概念及作用n掌握進(jìn)程的控制與調(diào)度方法掌握進(jìn)程的控制與調(diào)度方法n掌握進(jìn)程的同步與互斥、掌握進(jìn)程的同步與互斥、P、V操作操作n掌握死鎖的概念和死鎖的處理方法掌握死鎖的概念和死鎖的處理方法 第一節(jié)第一節(jié) 作業(yè)的概念作業(yè)的概念一、作業(yè)的定義一、作業(yè)的定義二、作

2、業(yè)的組成二、作業(yè)的組成三、作業(yè)的形狀三、作業(yè)的形狀一、作業(yè)的定義一、作業(yè)的定義 作業(yè)是用戶在一次算題過程中或一個(gè)作業(yè)是用戶在一次算題過程中或一個(gè)事務(wù)處置中要求計(jì)算機(jī)系統(tǒng)所做的任務(wù)的事務(wù)處置中要求計(jì)算機(jī)系統(tǒng)所做的任務(wù)的集合。集合。二、作業(yè)的組成二、作業(yè)的組成作業(yè)由程序、數(shù)據(jù)和作業(yè)闡明書組成作業(yè)由程序、數(shù)據(jù)和作業(yè)闡明書組成 。作業(yè)控制塊作業(yè)控制塊JCB作業(yè)被收容到外存后，系統(tǒng)為每個(gè)作業(yè)建立作業(yè)被收容到外存后，系統(tǒng)為每個(gè)作業(yè)建立一個(gè)一個(gè)JCB，它詳細(xì)記錄作業(yè)的有關(guān)信息，它詳細(xì)記錄作業(yè)的有關(guān)信息作業(yè)名作業(yè)名狀態(tài)狀態(tài)優(yōu)先數(shù)優(yōu)先數(shù)運(yùn)行時(shí)間運(yùn)行時(shí)間位置位置長度長度外設(shè)申請(qǐng)外設(shè)申請(qǐng)下一下一JCB指針指針JCB

3、1JCB2JCB3作業(yè)隊(duì)列作業(yè)隊(duì)列(Job Control Block)(Job Control Block)三、作業(yè)的形狀三、作業(yè)的形狀1 1提交形狀提交形狀 用戶向機(jī)房提交作業(yè)或經(jīng)過終端鍵用戶向機(jī)房提交作業(yè)或經(jīng)過終端鍵盤將作業(yè)輸入，其作業(yè)所處的形狀為提交形狀。盤將作業(yè)輸入，其作業(yè)所處的形狀為提交形狀。2 2收容形狀收容形狀 作業(yè)的全部信息已輸入外存儲(chǔ)器中作業(yè)的全部信息已輸入外存儲(chǔ)器中并建立并建立JCBJCB表，等待運(yùn)轉(zhuǎn)，又稱后備形狀。表，等待運(yùn)轉(zhuǎn)，又稱后備形狀。3 3執(zhí)行形狀執(zhí)行形狀 作業(yè)被調(diào)度程序選中后就給它分配作業(yè)被調(diào)度程序選中后就給它分配必要的資源，并按照作業(yè)步的順序，依次為每個(gè)必要

4、的資源，并按照作業(yè)步的順序，依次為每個(gè)作業(yè)步建立對(duì)應(yīng)的主進(jìn)程，然后將其提交給進(jìn)程作業(yè)步建立對(duì)應(yīng)的主進(jìn)程，然后將其提交給進(jìn)程管理模塊，由進(jìn)程調(diào)度程序管理并調(diào)度執(zhí)行。管理模塊，由進(jìn)程調(diào)度程序管理并調(diào)度執(zhí)行。4 4完成形狀完成形狀 作業(yè)執(zhí)行終了或出錯(cuò)而中途停頓，作業(yè)執(zhí)行終了或出錯(cuò)而中途停頓，釋放其占用的全部資源，預(yù)備退出系統(tǒng)。釋放其占用的全部資源，預(yù)備退出系統(tǒng)。 提交作業(yè)收容執(zhí)行完成外存內(nèi)存設(shè)備管理作業(yè)管理區(qū)分配作業(yè)的生命期作業(yè)的生命期作業(yè)從進(jìn)入計(jì)算機(jī)系統(tǒng)到運(yùn)轉(zhuǎn)終了、退出作業(yè)從進(jìn)入計(jì)算機(jī)系統(tǒng)到運(yùn)轉(zhuǎn)終了、退出系統(tǒng)的整個(gè)過程分成四個(gè)階段系統(tǒng)的整個(gè)過程分成四個(gè)階段第二節(jié)第二節(jié) 進(jìn)程的概念進(jìn)程的概念一、引入

5、進(jìn)程概念的緣由一、引入進(jìn)程概念的緣由 二、進(jìn)程定義二、進(jìn)程定義 三、進(jìn)程與程序的區(qū)別三、進(jìn)程與程序的區(qū)別 四、作業(yè)和進(jìn)程的關(guān)系四、作業(yè)和進(jìn)程的關(guān)系 單道程序系統(tǒng)下的程序執(zhí)行具有順序性、資源獨(dú)單道程序系統(tǒng)下的程序執(zhí)行具有順序性、資源獨(dú)占性封鎖性、確定性可再現(xiàn)性特點(diǎn)。占性封鎖性、確定性可再現(xiàn)性特點(diǎn)。多道程序系統(tǒng)中程序執(zhí)行出現(xiàn)新特點(diǎn)：相互制約多道程序系統(tǒng)中程序執(zhí)行出現(xiàn)新特點(diǎn)：相互制約性、隨機(jī)性、資源共享、與速度有關(guān)性。因此：性、隨機(jī)性、資源共享、與速度有關(guān)性。因此：用程序這個(gè)靜態(tài)的概念來懇求運(yùn)用系統(tǒng)資源曾經(jīng)用程序這個(gè)靜態(tài)的概念來懇求運(yùn)用系統(tǒng)資源曾經(jīng)不適宜；不適宜；一個(gè)程序段或程序，能夠?qū)?yīng)多個(gè)一個(gè)程

6、序段或程序，能夠?qū)?yīng)多個(gè)“計(jì)算，程序計(jì)算，程序與與“計(jì)算已不具有一一對(duì)應(yīng)關(guān)系。計(jì)算已不具有一一對(duì)應(yīng)關(guān)系。 一、引入進(jìn)程概念的緣由一、引入進(jìn)程概念的緣由 進(jìn)程是一個(gè)可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集進(jìn)程是一個(gè)可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集上的一次執(zhí)行過程。它是系統(tǒng)分配資源的根本單位。上的一次執(zhí)行過程。它是系統(tǒng)分配資源的根本單位。進(jìn)程是由程序、數(shù)據(jù)集和進(jìn)程控制塊三部分組成。進(jìn)程是由程序、數(shù)據(jù)集和進(jìn)程控制塊三部分組成。二、進(jìn)程定義二、進(jìn)程定義進(jìn)程控制塊進(jìn)程控制塊 PCBPCB (Process Control Block) (Process Control Block)n是進(jìn)程的檔案，是進(jìn)程的檔案，記錄各進(jìn)

7、程執(zhí)記錄各進(jìn)程執(zhí)行情況。行情況。n是進(jìn)程存在的是進(jìn)程存在的標(biāo)志標(biāo)志n進(jìn)程與進(jìn)程與PCBPCB是一是一一對(duì)應(yīng)的一對(duì)應(yīng)的進(jìn)程名進(jìn)程名當(dāng)前狀態(tài)當(dāng)前狀態(tài)優(yōu)先數(shù)優(yōu)先數(shù)存儲(chǔ)信息存儲(chǔ)信息程序首址程序首址啟動(dòng)地址啟動(dòng)地址數(shù)據(jù)地址數(shù)據(jù)地址現(xiàn)場(chǎng)信息現(xiàn)場(chǎng)信息指令計(jì)數(shù)器指令計(jì)數(shù)器程序狀態(tài)字程序狀態(tài)字堆棧指針堆棧指針隊(duì)列指針隊(duì)列指針三、進(jìn)程與程序的區(qū)別三、進(jìn)程與程序的區(qū)別1 1進(jìn)程是一個(gè)動(dòng)態(tài)的概念，是執(zhí)行程序的動(dòng)態(tài)過程。進(jìn)程是一個(gè)動(dòng)態(tài)的概念，是執(zhí)行程序的動(dòng)態(tài)過程。而程序是一個(gè)靜態(tài)的概念，是進(jìn)程運(yùn)轉(zhuǎn)的靜態(tài)文本。而程序是一個(gè)靜態(tài)的概念，是進(jìn)程運(yùn)轉(zhuǎn)的靜態(tài)文本。2 2進(jìn)程能真實(shí)地描畫并發(fā)執(zhí)行，且具有并發(fā)性，而進(jìn)程能真實(shí)地描畫并

8、發(fā)執(zhí)行，且具有并發(fā)性，而程序沒有。程序沒有。3 3一個(gè)進(jìn)程可以執(zhí)行一個(gè)或多個(gè)程序。反之，同一一個(gè)進(jìn)程可以執(zhí)行一個(gè)或多個(gè)程序。反之，同一程序也能夠由多個(gè)進(jìn)程同時(shí)執(zhí)行。程序也能夠由多個(gè)進(jìn)程同時(shí)執(zhí)行。4 4程序可以作為一種軟件資源長期堅(jiān)持，而進(jìn)程那程序可以作為一種軟件資源長期堅(jiān)持，而進(jìn)程那么是程序的一次執(zhí)行過程，它不具有存儲(chǔ)性。么是程序的一次執(zhí)行過程，它不具有存儲(chǔ)性。 四、作業(yè)與進(jìn)程的關(guān)系四、作業(yè)與進(jìn)程的關(guān)系1 1作業(yè)是用戶向計(jì)算機(jī)提交義務(wù)的義務(wù)虛體，而作業(yè)是用戶向計(jì)算機(jī)提交義務(wù)的義務(wù)虛體，而進(jìn)程是完成用戶義務(wù)的執(zhí)行實(shí)體；進(jìn)程是完成用戶義務(wù)的執(zhí)行實(shí)體；2 2一個(gè)作業(yè)可由多個(gè)進(jìn)程組成，且必需至少有一一

9、個(gè)作業(yè)可由多個(gè)進(jìn)程組成，且必需至少有一個(gè)進(jìn)程；個(gè)進(jìn)程；3 3作業(yè)的概念主要用在批處置系統(tǒng)中，而進(jìn)程的作業(yè)的概念主要用在批處置系統(tǒng)中，而進(jìn)程的概念那么幾乎用在一切多道系統(tǒng)中。概念那么幾乎用在一切多道系統(tǒng)中。 第三節(jié)第三節(jié) 進(jìn)程形狀及進(jìn)程控制進(jìn)程形狀及進(jìn)程控制一、進(jìn)程形狀一、進(jìn)程形狀 二、進(jìn)程控制二、進(jìn)程控制一、進(jìn)程形狀一、進(jìn)程形狀運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)就緒就緒等待等待選中選中等待事件發(fā)生等待事件發(fā)生(如如I/O懇求懇求)等待終了等待終了如等到如等到I/O資源資源落選落選(時(shí)間到時(shí)間到作業(yè)調(diào)度作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度完成完成進(jìn)程隊(duì)列進(jìn)程隊(duì)列n系統(tǒng)經(jīng)常把處于一樣形狀的進(jìn)程鏈接在一同，稱系統(tǒng)經(jīng)常把處于一樣形狀的進(jìn)程

10、鏈接在一同，稱進(jìn)進(jìn)程隊(duì)列程隊(duì)列n就緒隊(duì)列：由假設(shè)干就緒進(jìn)程按一定次序鏈接起來的就緒隊(duì)列：由假設(shè)干就緒進(jìn)程按一定次序鏈接起來的隊(duì)列。隊(duì)列。n等待隊(duì)列：把等待資源或等待某些事件的進(jìn)程陳列的等待隊(duì)列：把等待資源或等待某些事件的進(jìn)程陳列的隊(duì)列隊(duì)列n由于進(jìn)程控制塊能標(biāo)志進(jìn)程的存在和動(dòng)態(tài)描寫進(jìn)程的由于進(jìn)程控制塊能標(biāo)志進(jìn)程的存在和動(dòng)態(tài)描寫進(jìn)程的特性，因此，進(jìn)程隊(duì)列可以用進(jìn)程控制塊的銜接來構(gòu)特性，因此，進(jìn)程隊(duì)列可以用進(jìn)程控制塊的銜接來構(gòu)成。成?！舅妓黝}】【思索題】1. 有沒有這樣的形狀轉(zhuǎn)換，為什么？ 等待運(yùn)轉(zhuǎn)； 就緒等待進(jìn)程形狀進(jìn)程形狀作業(yè)的生命期作業(yè)的生命期提交提交作業(yè)作業(yè)收容收容執(zhí)行執(zhí)行完成完成運(yùn)轉(zhuǎn)運(yùn)轉(zhuǎn)就

11、緒就緒阻塞阻塞二、進(jìn)程控制二、進(jìn)程控制 經(jīng)過原語實(shí)現(xiàn)。原語是由假設(shè)干機(jī)器指令構(gòu)經(jīng)過原語實(shí)現(xiàn)。原語是由假設(shè)干機(jī)器指令構(gòu)成的完成某種特定功能的程序段，其執(zhí)行過程成的完成某種特定功能的程序段，其執(zhí)行過程具有不可分割性。具有不可分割性。創(chuàng)建原語創(chuàng)建原語阻塞原語阻塞原語 運(yùn)轉(zhuǎn)態(tài)運(yùn)轉(zhuǎn)態(tài)阻塞態(tài)阻塞態(tài) 喚醒原語喚醒原語 阻塞態(tài)阻塞態(tài)就緒態(tài)就緒態(tài) 撤銷原語撤銷原語第四節(jié)第四節(jié) 處置器調(diào)度處置器調(diào)度一、高級(jí)調(diào)度作業(yè)調(diào)度、宏觀一、高級(jí)調(diào)度作業(yè)調(diào)度、宏觀調(diào)度調(diào)度二、中級(jí)調(diào)度交互調(diào)度二、中級(jí)調(diào)度交互調(diào)度三、低級(jí)調(diào)度進(jìn)程調(diào)度、微觀三、低級(jí)調(diào)度進(jìn)程調(diào)度、微觀調(diào)度調(diào)度進(jìn)程形狀進(jìn)程形狀一、高級(jí)調(diào)度作業(yè)調(diào)度一、高級(jí)調(diào)度作業(yè)調(diào)度

12、1 1、功能、功能按照一定的調(diào)度算法對(duì)外存上處于后備形狀的作業(yè)進(jìn)按照一定的調(diào)度算法對(duì)外存上處于后備形狀的作業(yè)進(jìn)展選擇；展選擇；給選中的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，給選中的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程；并建立相應(yīng)的進(jìn)程；作業(yè)運(yùn)轉(zhuǎn)終了時(shí)，回收該作業(yè)占用的資源，輸出必要作業(yè)運(yùn)轉(zhuǎn)終了時(shí)，回收該作業(yè)占用的資源，輸出必要的信息，撤銷該作業(yè)的的信息，撤銷該作業(yè)的JCBJCB與相應(yīng)的進(jìn)程。與相應(yīng)的進(jìn)程。 2 2、調(diào)度時(shí)機(jī)、調(diào)度時(shí)機(jī)設(shè)設(shè)m m為系統(tǒng)支持的在主機(jī)上運(yùn)轉(zhuǎn)的最大作業(yè)數(shù)，為系統(tǒng)支持的在主機(jī)上運(yùn)轉(zhuǎn)的最大作業(yè)數(shù)，n n為在為在主機(jī)上運(yùn)轉(zhuǎn)的當(dāng)前作業(yè)數(shù)。假設(shè)主機(jī)上運(yùn)轉(zhuǎn)的當(dāng)

13、前作業(yè)數(shù)。假設(shè)nmnS0 0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。時(shí)，表示該類臨界資源的可用個(gè)數(shù)。S0S0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。時(shí)，表示該類臨界資源的可用個(gè)數(shù)。S0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。時(shí)，表示該類臨界資源的可用個(gè)數(shù)。S0時(shí)，表示等待運(yùn)用該類臨界資源的進(jìn)程個(gè)數(shù)。時(shí)，表示等待運(yùn)用該類臨界資源的進(jìn)程個(gè)數(shù)。進(jìn)程形狀進(jìn)程形狀三、用三、用P P，V V原語實(shí)現(xiàn)進(jìn)程互斥原語實(shí)現(xiàn)進(jìn)程互斥 P(mutex)V(mutex)P1P2P3臨界區(qū)臨界區(qū)P(mutex)P(mutex)V(mutex)V(mutex)Y=COUNTY=Y+1COUNT=Y臨界區(qū)臨界區(qū)V(S)P(S)進(jìn)程進(jìn)程BX=COUN

14、TX=X+1COUNT=X臨界區(qū)臨界區(qū)V(S)P(S)進(jìn)程進(jìn)程AS=1實(shí)現(xiàn)進(jìn)程互斥實(shí)現(xiàn)進(jìn)程互斥P操作操作V操作操作同步條件同步條件S=0同步點(diǎn)同步點(diǎn)四、用四、用P P，V V原語操作實(shí)現(xiàn)簡單同步原語操作實(shí)現(xiàn)簡單同步 1.1.用用P P，V V操作描畫前趨關(guān)系操作描畫前趨關(guān)系五、五、P P、V V原語在進(jìn)程同步原語在進(jìn)程同步/ /互斥問題中的運(yùn)用互斥問題中的運(yùn)用P1P2P3P4P5P6int f2=0,f3=0,f4=0,f5=0,f6=0;int f2=0,f3=0,f4=0,f5=0,f6=0;main()main() cobegin cobegin P1();P2();P3();P4();

15、P5(); P6(); P1();P2();P3();P4();P5(); P6(); coend coend P1()P1() . . v(f2);v(f3);v(f2);v(f3); P2()P2() p(f2); p(f2); . . v(f4);v(f5);v(f4);v(f5); P3()P3() p(f3); p(f3); . . v(f6); v(f6); P4()P4() p(f4); p(f4); . . v(f6); v(f6); P5()P5() p(f5); p(f5); . . v(f6); v(f6); P6()P6() p(f6); p(f6); p(f6); p

16、(f6); p(f6) p(f6) .; .; P1P2P3P4P5P6五、五、P P、V V原語在進(jìn)程同步原語在進(jìn)程同步/ /互斥問題中的運(yùn)用互斥問題中的運(yùn)用2.2.消費(fèi)者消費(fèi)者消費(fèi)者問題消費(fèi)者問題 同步問題：同步問題：1.只需緩沖池未滿，消費(fèi)者便可將音訊送入緩沖池，只需緩沖池未滿，消費(fèi)者便可將音訊送入緩沖池，否那么等待。否那么等待。2.只需緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)只需緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)音訊，否那么等待。音訊，否那么等待?；コ鈫栴}：互斥問題：1.消費(fèi)者與消費(fèi)者之間、消費(fèi)者與消費(fèi)者之間互斥訪消費(fèi)者與消費(fèi)者之間、消費(fèi)者與消費(fèi)者之間互斥訪問緩沖池。問緩沖池。2

17、.消費(fèi)者和消費(fèi)者之間互斥訪問緩沖池。消費(fèi)者和消費(fèi)者之間互斥訪問緩沖池。消費(fèi)者與消費(fèi)者之間的同步與互斥問題消費(fèi)者與消費(fèi)者之間的同步與互斥問題 互斥信號(hào)量互斥信號(hào)量S：初值為：初值為1，表示沒有進(jìn)程進(jìn)入臨界區(qū)。，表示沒有進(jìn)程進(jìn)入臨界區(qū)。 計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0：初值為：初值為0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。 計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn：初值為：初值為n，表示緩沖區(qū)中空位置個(gè)數(shù)。，表示緩沖區(qū)中空位置個(gè)數(shù)。 為實(shí)現(xiàn)消費(fèi)者與消費(fèi)者的同步與互斥，設(shè)三個(gè)為實(shí)現(xiàn)消費(fèi)者與消費(fèi)者的同步與互斥，設(shè)三個(gè)信號(hào)量：信號(hào)量：同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S

18、0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=nt=0S0=0S=1同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=1S0=0S=1互斥信號(hào)量互

19、斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=2S0= -1S=1阻塞阻塞互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位

20、置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=3S0= -1S=0阻塞阻塞互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)

21、程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=4S0=0S=0阻塞阻塞互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=5S0=0S= -1阻塞阻塞互斥信號(hào)

22、量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=6S0=0S=0阻塞阻塞互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位

23、置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=nt=7S0=0S=0互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1

24、P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=8S0=0S=0互斥信號(hào)量互斥信號(hào)量S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)同步互斥算法：同步互斥算法：消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程P1P(Sn)P(S)緩沖區(qū)緩沖區(qū) 產(chǎn)品產(chǎn)品V(S0)V(S)消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程C1P(S0)P(S)取產(chǎn)品取產(chǎn)品V(Sn)V(S)采用時(shí)間片采用時(shí)間片輪轉(zhuǎn)法：輪轉(zhuǎn)法：Sn=n-1t=9S0=0S=1以此循以此循環(huán)往復(fù)環(huán)往復(fù)互斥信號(hào)量互斥信號(hào)量

25、S=1，互斥信號(hào)量。，互斥信號(hào)量。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量S0=0，表示產(chǎn)品數(shù)目。，表示產(chǎn)品數(shù)目。計(jì)數(shù)信號(hào)量計(jì)數(shù)信號(hào)量Sn=n，表示緩沖區(qū)中空位置個(gè)數(shù)，表示緩沖區(qū)中空位置個(gè)數(shù)練習(xí)練習(xí)n在用信號(hào)量實(shí)現(xiàn)對(duì)臨界資源的互斥訪問在用信號(hào)量實(shí)現(xiàn)對(duì)臨界資源的互斥訪問時(shí)，假設(shè)信號(hào)量的初值是時(shí)，假設(shè)信號(hào)量的初值是2，當(dāng)前值是，當(dāng)前值是-1，表示有表示有 個(gè)進(jìn)程等待運(yùn)用該資源。個(gè)進(jìn)程等待運(yùn)用該資源。 答案：答案：1 設(shè)有三個(gè)進(jìn)程互斥地運(yùn)用兩臺(tái)打印機(jī)，設(shè)有三個(gè)進(jìn)程互斥地運(yùn)用兩臺(tái)打印機(jī)，那么用那么用P、V操作管理時(shí)信號(hào)量操作管理時(shí)信號(hào)量S的能夠的能夠取值為取值為_。 答案：答案： -1，0，1，2練習(xí)：練習(xí)： 當(dāng)有當(dāng)有n

26、個(gè)并發(fā)進(jìn)程共享某個(gè)臨界資源時(shí)，個(gè)并發(fā)進(jìn)程共享某個(gè)臨界資源時(shí)，互斥信號(hào)量的取值范圍是互斥信號(hào)量的取值范圍是 。 A -11 B -1(n-1) C - (n-1) 1 D - (n-1) (n-1)答案答案:C第六節(jié)第六節(jié) 死鎖問題死鎖問題一、死鎖的概念一、死鎖的概念二、死鎖產(chǎn)生的緣由二、死鎖產(chǎn)生的緣由三、死鎖產(chǎn)生的必要條件三、死鎖產(chǎn)生的必要條件四、死鎖的排除方法四、死鎖的排除方法 一、死鎖的概念一、死鎖的概念 R1 R2P1P2死鎖是指兩個(gè)或多個(gè)進(jìn)程無休止地等候著永遠(yuǎn)不死鎖是指兩個(gè)或多個(gè)進(jìn)程無休止地等候著永遠(yuǎn)不會(huì)出現(xiàn)的事件而發(fā)生的一種形狀會(huì)出現(xiàn)的事件而發(fā)生的一種形狀 。二、死鎖產(chǎn)生的緣由二、死

27、鎖產(chǎn)生的緣由n系統(tǒng)資源缺乏系統(tǒng)資源缺乏n進(jìn)程推進(jìn)的順序不當(dāng)進(jìn)程推進(jìn)的順序不當(dāng)進(jìn)程進(jìn)程1 1 進(jìn)程進(jìn)程2 2懇求懇求R1 R1 懇求懇求R2R2懇求懇求R2 R2 懇求懇求R1R1釋放釋放R1 R1 釋放釋放R2R2釋放釋放R2 R2 釋放釋放R1R1 R1 R2P1P2三、死鎖產(chǎn)生的必要條件三、死鎖產(chǎn)生的必要條件所涉及的資源是非共享的互斥條件所涉及的資源是非共享的互斥條件進(jìn)程在等待新資源時(shí)進(jìn)程在等待新資源時(shí),繼續(xù)占用已分配的資源繼續(xù)占用已分配的資源懇求和堅(jiān)持條件懇求和堅(jiān)持條件一個(gè)進(jìn)程占有的資源不能被別的進(jìn)程強(qiáng)行攻一個(gè)進(jìn)程占有的資源不能被別的進(jìn)程強(qiáng)行攻占不剝奪條件占不剝奪條件前一個(gè)進(jìn)程獲得的資源

28、正是后一個(gè)進(jìn)程所懇前一個(gè)進(jìn)程獲得的資源正是后一個(gè)進(jìn)程所懇求的求的,從而構(gòu)成一個(gè)進(jìn)程的循環(huán)鏈環(huán)路等待從而構(gòu)成一個(gè)進(jìn)程的循環(huán)鏈環(huán)路等待條件條件 R1 R2P1P2四、死鎖的排除方法四、死鎖的排除方法預(yù)防防止檢測(cè)和恢復(fù)四、死鎖的排除方法四、死鎖的排除方法 1. 1. 死鎖的預(yù)防死鎖的預(yù)防在系統(tǒng)運(yùn)轉(zhuǎn)之前就采取措施，即在系統(tǒng)設(shè)計(jì)時(shí)確定資在系統(tǒng)運(yùn)轉(zhuǎn)之前就采取措施，即在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，消除發(fā)生死鎖的任何能夠性。源分配算法，消除發(fā)生死鎖的任何能夠性。只需破壞任一必要條件，死鎖就不會(huì)產(chǎn)生只需破壞任一必要條件，死鎖就不會(huì)產(chǎn)生突破第二條：采用資源一次性分配戰(zhàn)略突破第二條：采用資源一次性分配戰(zhàn)略 。每個(gè)進(jìn)

29、程必需一次性懇求它所要求的資源。每個(gè)進(jìn)程必需一次性懇求它所要求的資源。突破第三條：采用資源暫時(shí)釋放戰(zhàn)略突破第三條：采用資源暫時(shí)釋放戰(zhàn)略 。懇求不到資源，那么釋放全部資源。懇求不到資源，那么釋放全部資源。突破第四條：采取資源順序運(yùn)用法突破第四條：采取資源順序運(yùn)用法 。系統(tǒng)中的一切資源都賦予獨(dú)一的編號(hào)，每個(gè)進(jìn)程只能系統(tǒng)中的一切資源都賦予獨(dú)一的編號(hào)，每個(gè)進(jìn)程只能按編號(hào)的升序懇求資源。即對(duì)于同一個(gè)進(jìn)程來說，按編號(hào)的升序懇求資源。即對(duì)于同一個(gè)進(jìn)程來說，它一旦懇求了一個(gè)編號(hào)為它一旦懇求了一個(gè)編號(hào)為i i的資源，就不允許再懇的資源，就不允許再懇求其編號(hào)在求其編號(hào)在i i前面的資源前面的資源1輸入機(jī)，2打印機(jī)

30、，3穿孔機(jī)，4磁帶機(jī)，5磁盤2. 2. 死鎖的防止死鎖的防止 允許死鎖產(chǎn)生的四個(gè)必要條件存在，當(dāng)系統(tǒng)允許死鎖產(chǎn)生的四個(gè)必要條件存在，當(dāng)系統(tǒng)有能夠產(chǎn)生死鎖時(shí)，小心地防止。有能夠產(chǎn)生死鎖時(shí)，小心地防止。四、死鎖的排除方法四、死鎖的排除方法 銀行家算法銀行家算法銀行家貸款問題銀行家貸款問題:設(shè)有一銀行，將固定數(shù)量的設(shè)有一銀行，將固定數(shù)量的共享資金提供應(yīng)一定數(shù)量的客戶借用，銀行提共享資金提供應(yīng)一定數(shù)量的客戶借用，銀行提出如下規(guī)定出如下規(guī)定: (1) 每個(gè)客戶必需預(yù)先提出本人的最大借款額，每個(gè)客戶必需預(yù)先提出本人的最大借款額，這個(gè)最大借款額不能超越銀行的共享資金總數(shù)。這個(gè)最大借款額不能超越銀行的共享資金

31、總數(shù)。 (2) 每個(gè)客戶可以分期借款，每次只能借一萬每個(gè)客戶可以分期借款，每次只能借一萬元。元。 (3) 銀行對(duì)于客戶的借款要求，要么立刻滿足，銀行對(duì)于客戶的借款要求，要么立刻滿足，要么讓其等待一段有限的時(shí)間。要么讓其等待一段有限的時(shí)間。 (4) 客戶借款數(shù)到達(dá)其預(yù)先提出的最大借款額客戶借款數(shù)到達(dá)其預(yù)先提出的最大借款額后，必需在有限的時(shí)間內(nèi)一次性完成對(duì)銀行的后，必需在有限的時(shí)間內(nèi)一次性完成對(duì)銀行的還款。還款。平安形狀平安形狀假設(shè)銀行在某一時(shí)間內(nèi)可以使一切的客戶在假設(shè)銀行在某一時(shí)間內(nèi)可以使一切的客戶在有限的時(shí)間內(nèi)借走并且還清借款，那么稱銀有限的時(shí)間內(nèi)借走并且還清借款，那么稱銀行處于平安形狀。行處

32、于平安形狀。銀行家算法銀行家算法就是用于決議能否立刻貸款給就是用于決議能否立刻貸款給客戶，以確保銀行處于客戶，以確保銀行處于 平安形狀。平安形狀。銀行家算法銀行家算法狀態(tài)狀態(tài)銀行銀行甲甲乙乙丙丙A10(8)(3)(9)B24(4)2(1)2(7)C14(4)3(0)2(7)D4歸還歸還E08(0)2(7)F8歸還歸還G19(0)H10歸還歸還狀態(tài)狀態(tài)銀行銀行甲甲乙乙丙丙A10(8)(3)(9)B24(4)2(1)2(7)C15(3)2(1)2(7)D05(3)2(1)3(6)E死鎖死鎖例：某銀行資金總數(shù)例：某銀行資金總數(shù)10萬元，萬元，甲、乙、丙懇求貸款總數(shù)分甲、乙、丙懇求貸款總數(shù)分別為別為8

33、、3、9萬元萬元銀行家算法銀行家算法目目 前前 占占 有有 量量 最最 大大 需需 求求 量量 尚尚 需需 要要 量量P 1143P 2462P 3583系系 統(tǒng)統(tǒng) 剩剩 余余 量量2我們把銀行換成操作系統(tǒng)，共享資金換成資我們把銀行換成操作系統(tǒng)，共享資金換成資源，借款客戶換成懇求資源源，借款客戶換成懇求資源 的進(jìn)程，于是發(fā)的進(jìn)程，于是發(fā)現(xiàn)完全可以借助于現(xiàn)完全可以借助于銀行家算法銀行家算法的原理平安的原理平安地分配資源。地分配資源。關(guān)于關(guān)于“防止死鎖的討論防止死鎖的討論n優(yōu)點(diǎn)：允許死鎖的必要條件存在，比預(yù)防優(yōu)點(diǎn)：允許死鎖的必要條件存在，比預(yù)防死鎖的條件放松了，資源利用率提高死鎖的條件放松了，資源利用率提高n要求資源數(shù)量固定不變，難以做到！要求資源數(shù)量固定不變，難以做到！n要求用戶數(shù)量固定不變，難以做到！要求用戶數(shù)量固定不變，難以做到！n只能保證有限時(shí)間內(nèi)得到滿足！只能保證有限時(shí)間內(nèi)得到滿足！n要求用戶事先闡明其最大的資源需求，困要求用戶事先闡明其最大的資源需求，困難！難！3. 3. 死鎖的檢測(cè)死鎖的檢測(cè) 允許死鎖的產(chǎn)生，每隔一段時(shí)間進(jìn)展檢測(cè)，允許死鎖的產(chǎn)生，每隔一段時(shí)間進(jìn)展檢測(cè)，假設(shè)存在死鎖，那么即決之。假設(shè)存在死鎖，那么即決之。 可以經(jīng)過化簡資源分配圖處理?？梢越?jīng)過化簡資