軟件技術(shù)基礎(chǔ)：操作系統(tǒng)處理器管理

1、3.3 處理器管理在多道程序運(yùn)行時(shí)，操作系統(tǒng)對處理機(jī)的管理就是通過對進(jìn)程的管理來實(shí)現(xiàn)的。代表性的進(jìn)程定義：1 ） 進(jìn)程是程序的一次執(zhí)行；2）進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算；3）進(jìn)程可定義為一個(gè)數(shù)據(jù)結(jié)構(gòu)及能在其上進(jìn)行操作的一個(gè)程序；4）進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)；5）進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單 位。2 .3.1 基本概念與術(shù)語1.作業(yè)和進(jìn)程作業(yè)是從事物處理看工作的處理過程。進(jìn)程是從系統(tǒng)處理看工作的處理過程。例：醫(yī)生看病，病人看病需要掛號、預(yù)約、就診、驗(yàn)血、做 CT,就診、取藥等作業(yè)。醫(yī)生診斷過程就是進(jìn)程。就診的環(huán)節(jié)，病

2、人稱為作業(yè)，醫(yī)生稱為進(jìn)程診療室就是CPU（ 1 ）作業(yè)、作業(yè)步一個(gè)作業(yè)是指在一次應(yīng)用業(yè)務(wù)處理過程中， 從輸入開始到輸出結(jié)束，用戶要求計(jì)算機(jī)所做的有關(guān)該次業(yè)務(wù)處理的全部工作。作業(yè)由不同的順序相連的作業(yè)步組成。 作業(yè)步是在一個(gè)作業(yè)的處理過程中，計(jì)算機(jī)所做的相對獨(dú)立的工作。（ 2）進(jìn)程和程序進(jìn)程與程序的關(guān)系? 程序是指令的有序集合，其本身沒有任何運(yùn)行的含義，是一個(gè)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，它是一個(gè)動(dòng)態(tài)的概念。? 程序可以作為一種軟件資料長期存在，而進(jìn)程是有一定生命期的。程序是永久的，進(jìn)程是暫時(shí)的。? 進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能；進(jìn)程是由程序和數(shù)據(jù)兩部分組成的。? 進(jìn)程

3、具有創(chuàng)建其他進(jìn)程的功能，而程序沒有。? 同一程序同時(shí)運(yùn)行于若干個(gè)數(shù)據(jù)集合上，它將屬于若干個(gè)不同的進(jìn)程。也就是說同一程序可以對應(yīng)多個(gè)進(jìn)程。特權(quán)指令、處理機(jī)狀態(tài)特權(quán)指令：只能由操作系統(tǒng)使用非特權(quán)指令：供一般用戶使用管態(tài)（主態(tài)、執(zhí)行狀態(tài)）：此時(shí)處理器執(zhí)行特權(quán)指令。目態(tài)（算態(tài)、題目狀態(tài)）：此時(shí)處理器處于用戶狀態(tài)。3處理器管理3.4.1 處理機(jī)調(diào)度的層次1 . 高級調(diào)度高級調(diào)度又稱為作業(yè)調(diào)度或宏觀調(diào)度。其主要功能是根據(jù)一定的算法，從輸入的一批任務(wù)（作業(yè)）中選出若干個(gè)作業(yè)，分配必要的資源，如內(nèi)存、外設(shè)等，為它建立相應(yīng)的用戶作業(yè)進(jìn)程和為其服務(wù)的系統(tǒng)進(jìn)程（如輸入/輸出進(jìn)程），最后把它們的程序和數(shù)據(jù)調(diào)入內(nèi)存，等

4、待進(jìn)程調(diào)度程序?qū)ζ鋱?zhí)行調(diào)度，并在作業(yè)完成后作善后處理工作。2 .中級調(diào)度中級調(diào)度涉及進(jìn)程在內(nèi)外存間的交換。為緩解內(nèi)存緊張問題，在許多系統(tǒng)中設(shè)立了中級調(diào)度。中級調(diào)度的主要功能是在內(nèi)存使用緊張時(shí)，將一些暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存對換到外存上等待。以后，當(dāng)內(nèi)存有足夠的空閑空間時(shí)，再將合適的進(jìn)程重新?lián)Q入內(nèi)存，等待進(jìn)程調(diào)度。引入中級調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。3 .低級調(diào)度低級調(diào)度又稱進(jìn)程調(diào)度或微觀調(diào)度，其主要功能是根據(jù)一定的算法，將 CPU分派給就緒進(jìn)程隊(duì)列中的一個(gè)進(jìn)程。執(zhí)行低級調(diào)度功能的程序稱為進(jìn)程調(diào)度程序，由它實(shí)現(xiàn)CPU在進(jìn)程間的切換。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，在一

5、般的操作系統(tǒng)中都必須有進(jìn)程調(diào)度，而且它的策略的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。時(shí)間片到作業(yè)調(diào)度!就緒隊(duì)列作業(yè)交互式用戶中級制度!就緒，掛起隊(duì)列阻塞，掛起隊(duì)列事件發(fā)生阻塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成）中級調(diào)度等待事件4 .3.2作業(yè)調(diào)度1作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊提交狀態(tài)：一個(gè)作業(yè)被提交給機(jī)房后或用戶通過終端鍵盤向計(jì)算機(jī)鍵入其作業(yè)時(shí)所處的狀 態(tài)后備狀態(tài)（收容狀態(tài)）：作業(yè)的全部信息都已通過輸入機(jī)輸入，并由操作系統(tǒng)將其存在磁盤 的某些分區(qū)（存放作業(yè)的輸入井）中等待運(yùn)行。運(yùn)行狀態(tài)：作業(yè)一旦被作業(yè)調(diào)度程序選中而被送入主存中投入運(yùn)行。完成狀態(tài)：作業(yè)完成其全部運(yùn)行，釋放出其所占用的全部資源。準(zhǔn)備退出系統(tǒng)時(shí)的作業(yè)。作

6、業(yè)控制塊1)2)3)4)5)6)7)作業(yè)標(biāo)識作業(yè)名估計(jì)運(yùn)行時(shí)間優(yōu)先級作業(yè)創(chuàng)建時(shí)間作業(yè)狀態(tài)作業(yè)對其他資源的要求2.作業(yè)調(diào)度的功能通常作業(yè)調(diào)度程序要完成以下的工作:(1)(2)(3)(4)按照某種調(diào)度算法，從作業(yè)隊(duì)列中選取 作業(yè)進(jìn)入內(nèi)存。調(diào)用存儲(chǔ)管理和設(shè)備管理程序，為選中 的作業(yè)分配內(nèi)存和外設(shè)。為選中的作業(yè)建立相應(yīng)的進(jìn)程。作業(yè)運(yùn)行完畢時(shí)回收該作業(yè)站用的資源, 程控制塊）與相應(yīng)的進(jìn)程。作業(yè)基本情況描述作叱控制描述作業(yè)資掘要求描述要求處理時(shí)間內(nèi)存空間外設(shè)類型和數(shù)量 處理機(jī)優(yōu)先級 庫函數(shù)或?qū)嵱贸绦?等等用戶名作業(yè)務(wù)使用悟言名允許最大處理時(shí)間 等等控制方式 操作順序 出借處理 等等輸出必要的信息，撤消該作

7、業(yè)的JCB (進(jìn)1)2)3)4)5)(1)(2)先來先服務(wù)算法基于優(yōu)先級的調(diào)度算法 優(yōu)先數(shù)=（等待時(shí)間）小作業(yè)可能回等待時(shí)間比較長。2-（要求運(yùn)行時(shí)間）-輸出量(3)3.3.3分時(shí)和優(yōu)先級相結(jié)合的作業(yè)調(diào)度 進(jìn)程調(diào)度3.作業(yè)調(diào)度算法調(diào)度算法的設(shè)計(jì)原則公平提高資源利用率 對資源的均衡使用 提高該系統(tǒng)的吞吐量響應(yīng)時(shí)間短幾種調(diào)度算法:1 .進(jìn)程的狀態(tài)轉(zhuǎn)換和進(jìn)程控制塊1.進(jìn)程的三種基本狀態(tài)所以又稱它進(jìn)程在運(yùn)行過程中有 3種基本狀態(tài)。這些狀態(tài)與系統(tǒng)調(diào)度占有處理機(jī)密切相關(guān)。 們?yōu)檫M(jìn)程調(diào)度狀態(tài)。運(yùn)行狀態(tài)（Running）當(dāng)一個(gè)進(jìn)程已分配到處理機(jī)，它的程序正由處理機(jī)執(zhí)行時(shí)，稱此進(jìn)程處于執(zhí)行狀態(tài)。就緒狀態(tài)（Rea

8、dy）如果進(jìn)程已具備執(zhí)行條件，但是因?yàn)樘幚頇C(jī)已由其他進(jìn)程占用，暫時(shí)不能執(zhí)行而等待分配處理機(jī)，稱此為就緒狀態(tài)。等待狀態(tài)（ Blocked ，阻塞狀態(tài)）進(jìn)程因等待某一事件（如等待某一輸入，輸出操作完成）而暫時(shí)不能運(yùn)行的狀態(tài)稱為等待狀態(tài)，此時(shí)即使CPU 空閑，它也無法使用。進(jìn)程控制塊的組成：進(jìn)程名特征信息進(jìn)程狀態(tài)信息調(diào)度優(yōu)先權(quán)通信信息現(xiàn)場保護(hù)區(qū)資源需求進(jìn)程實(shí)體信息族系關(guān)系其他信息2 .進(jìn)程控制進(jìn)程控制：系統(tǒng)使用一些具有特定功能的程序段來撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)，實(shí)現(xiàn)資源共享的目的。這種控制是通過原語來實(shí)現(xiàn)的。原語：是機(jī)器指令的延伸，是由若干條機(jī)器指令構(gòu)成

9、的用以完成特定功能的一段程序。原語是操作系統(tǒng)設(shè)計(jì)的、不可中斷的程序，即具有原子性的程序，它用于實(shí)現(xiàn)某種獨(dú)立功能并可以被其他進(jìn)程調(diào)用。為保證操作的正確性，原語在執(zhí)行期間是不可分割的，在許多機(jī)器中為了實(shí)現(xiàn)上的方便，規(guī)定在執(zhí)行原語操作時(shí)，要屏蔽中斷，以保證原語操作的不可分割性。用于進(jìn)程控制的原語有：1 .進(jìn)程創(chuàng)建原語2 .進(jìn)程調(diào)度原語3 .進(jìn)程阻塞原語（進(jìn)程等待原語）4 .進(jìn)程喚醒原語5 .進(jìn)程撤銷原語3 .進(jìn)程調(diào)度算法（1 ）優(yōu)先數(shù)法（2） 輪轉(zhuǎn)調(diào)度法（3） 分級調(diào)度法（4） 多道程序并發(fā)運(yùn)行出現(xiàn)的問題1 .進(jìn)程的同步和互斥（1） 同步與互斥進(jìn)程之間的相互制約關(guān)系由于進(jìn)程是并發(fā)執(zhí)行的，多個(gè)進(jìn)程之間

10、必然存在著各種形式的制約關(guān)系。一般來說，并發(fā)進(jìn)程之間存在兩種形式的制約關(guān)系。1 ）資源共享關(guān)系，又稱為間接相互制約關(guān)系，指進(jìn)程之間本來彼此無關(guān)，但因?yàn)楣蚕硐到y(tǒng)資源，如CPU 、內(nèi)存、I/O 設(shè)備等而產(chǎn)生的相互制約關(guān)系。2)進(jìn)程合作關(guān)系，又稱為直接相互制約關(guān)系，指多個(gè)進(jìn)程之間具有合作關(guān)系，用于完成 共同的任務(wù)，如同一個(gè)作業(yè)的輸入、計(jì)算、輸出進(jìn)程之間必然是相互合作的關(guān)系，他們必須按照一定的次序運(yùn)行。所謂進(jìn)程同步，是指對多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，操作系統(tǒng)中用于保證這種協(xié)調(diào)關(guān)系的相應(yīng)機(jī)制稱為進(jìn)程同步機(jī)制。對于資源共享關(guān)系的進(jìn)程，應(yīng)該保證多個(gè)并發(fā)進(jìn)程互斥訪問臨界資源；而對于相互合作的進(jìn)程，應(yīng)該保證

11、他們在執(zhí)行次序上的協(xié)調(diào)。臨界資源臨界資源是依次只能被一個(gè)進(jìn)程訪問的資源。獨(dú)占設(shè)備、內(nèi)存中的公共數(shù)據(jù)結(jié)構(gòu)、 公共變量等都是臨界資源。臨界區(qū)在并發(fā)進(jìn)程中，對共享變量操作的那段程序叫臨界區(qū)。進(jìn)程互斥一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不 允許交叉執(zhí)行的單位執(zhí)行。即不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為 互斥。例如：進(jìn)程pl, p2都需要使用打印機(jī)，如果讓它們同時(shí)使用，則兩個(gè)進(jìn)程的輸出交織在 一起，打印出的結(jié)果無法使用。 為了解決這一問題，進(jìn)程使用之前先要提出申請，一旦系統(tǒng)將打印機(jī)分配給它，就一直由它獨(dú)占使用，其它申請使用打印機(jī)的進(jìn)程則必須等待。例如

12、：Pi：Ricount;P2R2-count;Pi：Ri-Ri +1;count Ri；P2R2JR2 +1;count JR2；雖然Pi, P2P都又count作了加procedure T1(x)var x:integer ；beginread(x);臨If x>=1-界then x:=x-1; 區(qū) write(x)；end;1,但count中只增加了 1。： p, 卜 6/procedure T2(x) var x:integer ； begin正-g .read(x);臨Aend;1.2.3.4.5.(2)解決同步與互斥的工具P-V操作對彳t號量s (整數(shù)型)操作的定義為P操彳P(

13、s)ss-1If(s<0)thenstatus(q) -"blocked ”將進(jìn)程 q 置為"阻塞"/Insert(Q,q)將q插入阻塞隊(duì)列中ReturnV操彳V(s)1. . s -s+12. If(s<=0)then3. remove(Q,R)/將R移出阻塞隊(duì)列 Q4. status(R) -"ready”將 R 置為"就緒"/5. Insert(RL,R)/將R插入就緒隊(duì)列中 RL/6. Return(3)用P-V操作實(shí)現(xiàn)進(jìn)程互斥P(s)Rjcountl|5?Rj +1界countV(s)« I «

14、;p_臨+1 界count'*-R；V(s)(4)用P-V操作實(shí)現(xiàn)進(jìn)程同步1)非對稱制約如果進(jìn)程Pi在執(zhí)彳T到L1處從進(jìn)程P2獲取某些信息后才能繼續(xù)執(zhí)行，而這些信息卻是P2到達(dá)L2處后才能提供，為此著兩個(gè)進(jìn)程必須采用如下方式進(jìn)行同步：IIL1:產(chǎn)生信息港取信息L：V(s)> ll>> V> V設(shè)置s=0,在進(jìn)程P2尚未完成V(s)操作之前，進(jìn)程 Pi只能處于等待狀態(tài)。2)雙向制約一生產(chǎn)者和消費(fèi)者問題防止生產(chǎn)者將物品放入已滿的緩沖區(qū)中，同時(shí)也禁止消費(fèi)者從空緩沖區(qū)中取物品。生產(chǎn)者消費(fèi)者口： 生產(chǎn)物品6：取內(nèi)P國)從皴沖區(qū)取物品將物品放入綾沖區(qū)V(5L)VCW消費(fèi)物品

15、Goto LiGato Ci一個(gè)緩沖區(qū)時(shí)設(shè)置初值 & =1 , S2=0。n個(gè)緩沖區(qū)時(shí)設(shè)置初值 S1=n, S2=0O2 .進(jìn)程通信(1)直接通信方式。發(fā)送進(jìn)程直接把消息發(fā)送給接收者，并將它掛在接收進(jìn)程的消息緩沖 隊(duì)列上。接收進(jìn)程從消息緩沖隊(duì)列中取得消息，這種通信方式也稱為消息緩沖通信。,接收進(jìn)程從中取得消息。(2)間接通信。發(fā)送進(jìn)程將消息發(fā)送到某種中間實(shí)體中(信箱) 這種通信方式也稱信箱通信。在網(wǎng)絡(luò)中稱為電子郵件系統(tǒng)。3 .死鎖(1)死鎖的原因和必要條件死鎖產(chǎn)生的原因可歸結(jié)為如下兩點(diǎn)：(1)資源有限。當(dāng)系統(tǒng)中多個(gè)進(jìn)程共享資源，如打印機(jī)、公用隊(duì)列等，其數(shù)目不足以滿足諸進(jìn)程的需要，會(huì)引起

16、進(jìn)程對資源的競爭而產(chǎn)生死鎖。(2)并發(fā)進(jìn)程間的推進(jìn)順序不當(dāng)。進(jìn)程在運(yùn)行過程中，請求和釋放資源的順序不當(dāng)，也會(huì) 導(dǎo)致產(chǎn)生進(jìn)程死鎖。得到尺 得到S 釋放及 釋放三,l,_J申請到RA的進(jìn)度申請到S死鎖的必要條件：互斥條件：涉及的資源是非共享的。不剝奪條件：不能強(qiáng)行剝奪進(jìn)程擁有的資源。部分分配條件：進(jìn)程在等待一新資源時(shí)繼續(xù)占有 已分配的資源。環(huán)路條件：存在一種進(jìn)程的循環(huán)鏈， 鏈中的每一 個(gè)進(jìn)程已獲得的資源同時(shí)被鏈中的下一個(gè)進(jìn)程 所請求。(2)死鎖的預(yù)防通過破壞死鎖存在的 (4個(gè))必要條件來防止死鎖發(fā) 生。(1)破壞互斥條件如果允許系統(tǒng)資源都能共享使用，則系統(tǒng)不會(huì)進(jìn) 入死鎖狀態(tài)。但這種方法不是切實(shí)可行

17、的。因?yàn)橛?資源若是共享使用。 例如：打印機(jī)在多進(jìn)程打印， 能每個(gè)進(jìn)程打印一行，則無法保證其正確性。又如， 對臨界資源的訪問就必須互斥進(jìn)行。(2)破壞占有等待(二個(gè)方法)方法一：進(jìn)程申請到它所需要的所有資源后，才能開始運(yùn)行，又稱預(yù)先靜態(tài)分配法。例如，一個(gè)制表打印進(jìn)程，需共有打印機(jī)，才能運(yùn)行。此方法雖可保證無死鎖，但是a.資源的利用率低(在程序運(yùn)行中，打印機(jī)空閑)；b.由于所需資源不能在一次中得到全部滿足，而使 作業(yè)無限期延長。方法二：進(jìn)程提出申請資源前必須釋放已占有的一切資源。這些雖然能提高資源利用率，但要仔細(xì)進(jìn)行程序設(shè)計(jì)，有時(shí)仍需提前申請資源才能保證正確性。這使用戶倍感不便。R注1要考慮無限

18、等待現(xiàn)象(其實(shí)質(zhì)與死鎖一樣)。例：P1申請12r3 ,而僅有r3。這時(shí)P2申請r3;則把r3給P2 ,某一進(jìn)程Pi又釋放了 1 r2 ,而P1又因無r3,仍需等待直到餓死P1。我們應(yīng)有相應(yīng)的防止措施。比如按申請資源的先后次序給進(jìn)程賦優(yōu)先級。這種資源預(yù)先分配的方法，適于對外存空間的分配。因?yàn)樽鳂I(yè)運(yùn)行期間所需外存變化不大。（3）破壞非剝奪性條件在進(jìn)程主動(dòng)釋放占有的資源前即予以剝奪，也能保證系統(tǒng)不出現(xiàn)死鎖。方法一：當(dāng)進(jìn)程 Pi申請rj類資源時(shí)，檢查rj中有無可分配的資源，有則分配給 Pi;否則將 Pi占有的資源全部釋放進(jìn)入等待狀態(tài)。方法二：當(dāng)Pi申請rj時(shí)，檢查rj中有無可分配的資源，有則分配；否則

19、檢查占有rj類資源的進(jìn)程Pk。若Pk處于等待資源狀態(tài)， 則剝奪Pk的rj分給Pi;若Pk處于不等待資源狀態(tài)， 則置Pi于等待資源狀態(tài) （此日Pi原占有的資源可能被剝奪。）R注1剝奪資源時(shí)，需保存中間信息。因使用資源的進(jìn)程尚未主動(dòng)釋放資源，這樣開銷很大。故只宜在CPU和主存這類重要資源的管理上使用。不宜剝奪臨介資源等類型資源。（4）破壞循環(huán)等待條件采用資源順序分配法，可以破壞循環(huán)等待條件。 該方法首先給系統(tǒng)中的資源編號（唯一）,即尋找一個(gè)函數(shù) F: R - N （R ：表資源類集合）即r1,r2,，riJJJF（ri） = i1 2i每個(gè)進(jìn)程只能按序號由小到大的順序申請資源，而且對它所必須使用的

20、且屬于某一類的 所有資源，必須一次申請完。比如：某一進(jìn)程已占有資源r1, r2,，ri,又申請ri+1 ,資源分配程序則檢查是否有對于任意j1,2,i,有F（rj） < F（rj+1）,若不滿足則拒絕分配。采用資源順序分配法，系統(tǒng)不會(huì)出現(xiàn)循環(huán)等待。因?yàn)樵谌魏螘r(shí)刻，總有一個(gè)進(jìn)程占有較高序號的資源，該進(jìn)程繼續(xù)請示的資源必然是空閑的。故該進(jìn)程可一直向前推進(jìn)。（換言之，系統(tǒng)中總有進(jìn)程可以順序運(yùn)行完畢，這個(gè)進(jìn)程執(zhí)行結(jié)束后會(huì)釋放它所占有的全部資源喚 醒等待中的進(jìn)程或滿足其它進(jìn)程的請求。）優(yōu)點(diǎn)：有序資源分配法提高了資源利用率（比靜態(tài)法）缺點(diǎn)：順序號與實(shí)際需要資源的順序不一致，導(dǎo)致資源的浪費(fèi)。例：輸入機(jī)

21、1 #，打印機(jī)2#,穿孔機(jī)3#,磁盤機(jī)4#某進(jìn)程使用 32,而2-3長 期擱置。事實(shí)上用戶使用的資源通常是有一定順序的。2 .避免死鎖死鎖四個(gè)必要條件 （互斥、占有等待、非剝奪、循環(huán)等待）死鎖預(yù)防是嚴(yán)格破壞4個(gè)必要條件之一，一定不出現(xiàn)死鎖；而死鎖的避免是不那么嚴(yán)格地限制死鎖必要條件的存在，其目的是提高系統(tǒng)的資源利用率。萬一當(dāng)死鎖有可能出現(xiàn)需申請申源個(gè)數(shù)Qaim4已占資占個(gè)數(shù)Loan4進(jìn)程used = loan + claim時(shí)，就小心避免這種情況的發(fā) 生。92C712每次進(jìn)行資源分配時(shí)，需要 通過判斷系統(tǒng)狀態(tài)來決定這次 分配后，是否仍存在一條確保系 統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)的路徑，否 則不予分配。避

22、免死鎖的算法：銀行家算法假設(shè)有三個(gè)進(jìn)程 P、Q、R,系統(tǒng)只有某類資源共 10個(gè)，而三個(gè)進(jìn)程合計(jì)申請資源數(shù)為20個(gè)。目前的分配情況如下：而系統(tǒng) 8 + 2 = 10 t T T 已分配剩 共有 Loan Cash Capital此后P、R再申請資源就不能分配了。因?yàn)楝F(xiàn)在只剩下 2個(gè)資源，不能滿足它們的最大要求（P:4, R:7）,如果將剩下2個(gè)分配給P或R,則會(huì)產(chǎn)生死鎖。己占還“1P 53 吐 62I皮02I21R?627然而將2個(gè)資源分給Q （只需一個(gè)）則系統(tǒng)資源回 收為4個(gè)尸44P440 3 0 =>Q可運(yùn)行結(jié)R27束、桿放 R27此后可將4個(gè)資源分組P -即 Q 一 P 一 R由此可

23、見，按銀行家算法來分配資源是不會(huì)產(chǎn)生死鎖的。因?yàn)榘丛撍惴ǚ峙滟Y源時(shí)，每次分配后總存在一個(gè)進(jìn)程， 如果讓它獨(dú)立單獨(dú)運(yùn)行下去，必然可獲得它所需的全部資源，也就是說它能結(jié)束。而它結(jié)束后可以歸還這類資源來滿足其它申請者的需要。這也說明了存在一個(gè)合理的系統(tǒng)狀態(tài)序列，可確保系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)的路徑。單一種類資源引出的銀行家算法的基本思想也同樣適用于多種類的資源情況：rir2小A I0b100°i110i10IE 1Q0上rlr2%r4F°212421Q11Li_1資源已分配情況最大需求還需（剩余需求）矩陣總共資源數(shù)r = (6, 3, 4, 2)已分資源數(shù)s = (5, 3, 2,

24、2)余下資源數(shù)t = (1,0, 2, 0)先做D 做完后余下資源數(shù)：t = (2, 1,2, 1)再做A 做完后余下資源數(shù)：t = (5, 1,3, 2)再做B 做完后余下資源數(shù)：t = (5, 2, 3, 2)再做C 做完后余下資源數(shù)：t = (6, 3, 4, 2)再做E 做完后余下資源數(shù)：t = (6, 3, 4, 2)的對應(yīng)to(1)尋找剩余矩陣的某一未標(biāo)記的行x,使得它的每一個(gè)元素都不大于向量t元素，如果找不到轉(zhuǎn)(4)。(2)對于找到的行x,表示可以滿足它，標(biāo)記此進(jìn)程，并將它占有的資源加到向量(3)重復(fù)上述步驟，轉(zhuǎn)(1)。(4)如果所有進(jìn)程都已標(biāo)記，則狀態(tài)是安全的，否則為不安全。(

25、4)死鎖的檢測和恢復(fù)矩陣簡化法還需(剩余需求)矩陣總共資源數(shù)r = (6, 3, 4, 2)已分資源數(shù)s = (5, 3, 2, 2)余下資源數(shù) t = (1,0, 2, 0)先做 D t = (2, 1,2, 1)死鎖的恢復(fù)一旦發(fā)現(xiàn)死鎖及時(shí)排除，是有關(guān)排除死鎖的研究。當(dāng)前系統(tǒng)中使用的死鎖恢復(fù)辦法有兩種：(進(jìn)程撤消，資源剝奪)(1)強(qiáng)制性地從系統(tǒng)中撤消進(jìn)程，并剝奪它們的資源給剩下的進(jìn)程使用。(使前面的工作全部損失)(2)使用一個(gè)有效的掛起和解掛機(jī)構(gòu)來掛起一些進(jìn)程。其實(shí)質(zhì)是從被掛起的進(jìn)程那里搶占資源以解除死鎖。(即可從死鎖中恢復(fù)，又使進(jìn)程的損失最小)3.3.5多道程序設(shè)計(jì)基礎(chǔ)一并行程序設(shè)計(jì)1 .

26、順序程序設(shè)計(jì)(1)順序性：程序運(yùn)行時(shí)必須嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。(2)封閉性：(程序在運(yùn)行時(shí)獨(dú)占全機(jī)資源)程序運(yùn)行結(jié)果和它執(zhí)行的速度無關(guān)。(3)可再現(xiàn)性：當(dāng)對某一程序重復(fù)執(zhí)行時(shí)，只要其初始條件相同，必將獲得相同的結(jié)果。這對程序員檢測，校正程序的錯(cuò)誤帶來很大的方便。Ajf ARf耐 Bcr/Ct* CL Coy r模塊A模塊B 模塊C2 .并行程序設(shè)計(jì)(1) 并行性：多個(gè)或程序段可以并行執(zhí)行，在單處理器系統(tǒng)中即可互相切換。(并發(fā)性)(2) 共享性：系統(tǒng)中各程序不但共享硬件資源，而且共享軟件資源(程序副本和數(shù)據(jù)集)(3) 同步與互斥：這是并行性和共享性帶來的必然結(jié)果，3 .并行程序設(shè)計(jì)語言(1) 同步問題說明部分