第1頁/89教學內(nèi)容（一）基本概念特權(quán)指令管態(tài)目態(tài)P129進程、程序的關(guān)系和區(qū)分進程的類型、性質(zhì)和狀態(tài)進程調(diào)度的策略和常用算法 靜、動態(tài)優(yōu)先數(shù)法、輪轉(zhuǎn)法、分級調(diào)度法進程的限制與管理——進程限制塊PCB（二）進程的同步與互斥（三）死鎖(四)作業(yè)管理與限制第2頁/89教學內(nèi)容及本單元涉及的章節(jié)3.3處理器管理3.6操作系統(tǒng)的用戶接口第3頁/89一、基本概念程序單道程序、多道程序、依次程序、并發(fā)程序依次程序與并發(fā)程序的特征進程進程的特征、性質(zhì)、狀態(tài)及轉(zhuǎn)換進程限制進程調(diào)度第4頁/891、程序的有關(guān)概念程序（Program）是為解決某個問題用計算機語言或吩咐設(shè)計、編寫的一系列指令的有序集合。程序的依次執(zhí)行一個程序通常分為若干個具有確定獨立性的程序段，這些程序段是按邏輯步驟編排的，只有當當前程序段執(zhí)行完成后，才將限制權(quán)轉(zhuǎn)交到下一個程序段并執(zhí)行下一個程序段。第5頁/89程序依次執(zhí)行舉例一設(shè)有一個程序有三個程序段，分別執(zhí)行I（輸入）、C（計算）和P（輸出）操作。執(zhí)行依次為：ICP

只有‘輸入’了數(shù)據(jù)，才能‘計算’這些數(shù)據(jù)，也只有‘計算’產(chǎn)生了結(jié)果，才能‘輸出’它們。這些邏輯關(guān)系（依次）是不能隨意變更的。

結(jié)果

數(shù)據(jù)第6頁/89程序依次執(zhí)行舉例二

假設(shè)有n個作業(yè)，每個作業(yè)都由三個程序段：輸入段Ii、計算段Ci、輸出段Pi。在早期單道程序系統(tǒng)中，作業(yè)執(zhí)行流為：作業(yè)1I1C1P1作業(yè)2I2C2P2作業(yè)nInCnPn作業(yè)執(zhí)行順序第7頁/89單道程序處理及特性一次只處理一個程序。該程序獨享系統(tǒng)資源。單個程序的特性：1、依次性操作按程序規(guī)定的依次執(zhí)行。2、封閉性程序在執(zhí)行過程中獨享系統(tǒng)資源，不受外界因素的干擾和影響。3、可再現(xiàn)性只要初始條件相同，無論以何種方式、速度、重復執(zhí)行多少次，結(jié)果是相同的。第8頁/89多道程序處理及特性同時將多個程序裝入內(nèi)存，并同時處理它們，整個系統(tǒng)資源為多個程序共享。由于多道程序具有并發(fā)的特點，在任一時刻，系統(tǒng)內(nèi)部（內(nèi)存）同時運行著多個程序；受系統(tǒng)資源的制約，每個程序處理過程的行為是不確定的（系統(tǒng)內(nèi)部狀態(tài)因此而不同）。輸入計算??????

?

計算計算打印???

???

計

算打

印A(優(yōu)先級高）CA1A2B1B2B3C1C2多道程序并行運行示意圖A1輸入B1

C1打印OSB2OSB3打印

A2CPU

OSCPUC2CPUCPUCPUCPUCPUB

程序并發(fā)執(zhí)行舉例第10頁/89單道和多道程序處理的區(qū)分在單道程序處理環(huán)境下，各邏輯步驟之間的關(guān)系是確定的、不受外界影響而變更的。在多道程序處理環(huán)境下，并發(fā)處理機制中必定存在著干脆或間接的相互依靠和相互制約的關(guān)系，從而使被處理的多道程序失去了程序固有的特性：封閉性、可再現(xiàn)性。第11頁/89程序并發(fā)處理特征

1、失去了程序的封閉性，請分析下列程序begin用cobegin和coend表示程N:integer序能并發(fā)執(zhí)行。N：=0cobeginbeginbeginL1：programAL2：programBN:=N+1printNgotoL1N:=0endgotoL2coendendend并發(fā)程序段A并發(fā)程序段B加1打印清零第12頁/89程序并發(fā)處理特征——失去了程序的封閉性分析：若先執(zhí)行程序A，N值大于0；再執(zhí)行程序B時，先輸出一個大于0的N值，然后，N值變?yōu)?。若先執(zhí)行程序B，N值等于0，先輸出一個0的N值；再執(zhí)行程序A時，N值變?yōu)?。由于程序A和程序B都是以各自獨立的速度運行，則因速度不同而結(jié)果不同。所以并發(fā)執(zhí)行程序失去了依次程序的封閉性。

第13頁/89程序并發(fā)處理特征——程序與計算結(jié)果不再一一對應(yīng)程序在依次執(zhí)行時，程序與“計算”間有著一一對應(yīng)的關(guān)系。在并發(fā)執(zhí)行時，一個共享程序可為多個用戶作業(yè)調(diào)度，而使程序處于多個執(zhí)行中，從而形成了多個“計算”。因此，程序和計算間一一對應(yīng)的關(guān)系不復存在。如何表示并發(fā)程序的特性？第14頁/892、進程及有關(guān)概念進程（Process）就是程序的一次執(zhí)行過程，是系統(tǒng)進行資源安排和調(diào)度的一個獨立單位。“進程”這個概念是1966年美國麻省理工學院的J.H.Sallexer提出的。處理器（CPU）管理又稱處理器調(diào)度。處理器是計算機系統(tǒng)中的重要資源，所以它管理的好壞在很大程度上干脆影響系統(tǒng)的效率。處理器管理又分兩級：作業(yè)調(diào)度和進程調(diào)度。進程管理是由程序管理進化而來，是和程序管理密不行分的。作業(yè)調(diào)度見本PPT87第15頁/89進程的性質(zhì)1）動態(tài)性進程有自己的生命周期。2）并發(fā)性在系統(tǒng)中可以同時存在多個進程； OS同時接受和處理多個進程。3）異步性不同進程在邏輯上相互獨立，有各自 的運行“軌跡”。4）制約性由于計算機資源是有限的，不同進程共享CPU和I/O通道及設(shè)備，因此相互制約。第16頁/89進程與程序的區(qū)分進程是動態(tài)概念，程序是靜止概念。進程的存在是短暫的，程序的存在是永久的。假如程序是劇本，那么表演過程就是進程；假如程序是菜譜，那么烹調(diào)過程就是進程；電影膠片呢通過多次執(zhí)行，一個程序可對應(yīng)多個進程；通過調(diào)用關(guān)系，一個進程可包括多個程序(父進程和子進程）進程在結(jié)構(gòu)上是由程序、數(shù)據(jù)集、進程限制塊（PCB）三部分組成的。PCB程序數(shù)據(jù)第17頁/89進程的狀態(tài)進程在其存在的過程中，它們的狀態(tài)是不斷發(fā)生變更的。一般來說，進程有三種基本狀態(tài)：就緒狀態(tài)、運行狀態(tài)、等待狀態(tài)。就緒狀態(tài)已經(jīng)獲得投入運行所必需的一切資源，一旦安排到CPU，就可以馬上執(zhí)行。這是一種邏輯上可運行狀態(tài)（“萬事俱備，只欠東風”）。運行狀態(tài)進程獲得了CPU及其它一切所需資源，正在CPU上運行著,也是唯一在運行的。堵塞狀態(tài)由于資源得不到滿足，進程運行受阻，處于暫停狀態(tài)，等待資源安排后，再投入運行。第18頁/89進程狀態(tài)轉(zhuǎn)換示意圖

運行狀態(tài)堵塞狀態(tài)

就緒狀態(tài)

進程調(diào)度

等待資源時間用完獲得資源

進程調(diào)度程序

來自作業(yè)調(diào)度

交作業(yè)管理進程在整個生存周期中，由進程調(diào)度程序限制，在這三種狀態(tài)之間進行轉(zhuǎn)換。第19頁/893、進程管理進程管理的核心是進程的限制和調(diào)度。進程自投入運行時起，即交由進程調(diào)度程序管理。依據(jù)什么標準選擇怎樣的進程投入運行？如何管理不同類型進程的資源？接受什么策略進行安排資源？…。這些都是進程管理的問題。第20頁/89進程限制進程限制的職責是對系統(tǒng)中全部進程實行有效的管理；它應(yīng)當具有創(chuàng)建進程、撤消進程、變更進程狀態(tài)的實力。為便于對進程進行管理，進程具有特殊的構(gòu)成形式。PCB程序數(shù)據(jù)進程名優(yōu)先數(shù)當前狀態(tài)寄存器內(nèi)容………指向下一個PCBPCB說明信息保留信息第21頁/89進程的組成進程是程序在一個數(shù)據(jù)集合上的運行過程，它由三部分組成：程序它主要用于描述進程所要完成的功能。數(shù)據(jù)集合它包括程序執(zhí)行時所須要的數(shù)據(jù)和工作區(qū)。進程限制塊（PCB——ProcessControlBlock)它記錄進程限制信息，是進程動態(tài)特性的反映。第22頁/89進程限制塊——PCB進程限制塊PCB是進程的唯一標識。當創(chuàng)建一個新進程時，系統(tǒng)就建立一個PCB；它記錄和描述該進程的運行變更過程及參數(shù)變更。事實上，系統(tǒng)是通過PCB對進程進行實際限制和管理的。通過感知PCB，感知進程的存在。PCB中包括：進程名進程唯一的代號進程優(yōu)先級標明該進程要求CPU的迫切程度進程當前狀態(tài)記錄進程當前狀態(tài)寄存器內(nèi)容 記錄中斷現(xiàn)場信息，以備復原用第23頁/89進程限制塊PCB的組織形式為了便于對進程調(diào)度管理，必需對進程進行合理的組織。進程限制塊PCB是定長記錄（類似于UNIX中的i索引結(jié)點表），接受兩種組織方式。

線性表結(jié)構(gòu)PCB組織形式鏈表結(jié)構(gòu)第24頁/89PCB鏈表結(jié)構(gòu)

運行隊列

就緒隊列堵塞隊列PCBr隊頭指針PCBsPCBs+1PCBs+2PCBtPCBt+1PCBt+2唯一在運行的第25頁/89進程限制的實現(xiàn)通過進程限制原語原語由若干條機器指令構(gòu)成的，用以完成某一特定功能的一段程序。原語在執(zhí)行期間是不行分割的。（1）創(chuàng)建原語：按進程調(diào)用者供應(yīng)的參數(shù)，形成PCB。（2）掛起（堵塞）原語：將某進程置于堵塞狀態(tài)。（3）激活（喚醒）原語：將某進程置為就緒狀態(tài)，等待CPU。（4）撤消原語：撤消進程，釋放所占用的全部資源，刪除該程序的PCB。第26頁/894.進程調(diào)度的任務(wù)及功能進程調(diào)度任務(wù)按確定的算法，動態(tài)地將處理器（CPU）安排給就緒隊列中的某個進程，使之執(zhí)行。進程調(diào)度功能記錄系統(tǒng)中全部進程的狀態(tài)、優(yōu)先數(shù)和所用資源的狀況。當CPU空閑時，按確定的算法將CPU安排給某一進程、并確定CPU時間片的長度。動態(tài)地調(diào)度進程、修改進程的狀態(tài)、以及修改相應(yīng)的排隊隊列。第27頁/89進程調(diào)度方式剝奪方式當“重要”或“系統(tǒng)”的進程出現(xiàn)時，便暫停正在執(zhí)行的進程，馬上將CPU安排給“重要”或“系統(tǒng)”的進程。非剝奪方式讓正在執(zhí)行的進程接著執(zhí)行，直到該進程完成或發(fā)生其它事務(wù)，而變更為其它狀態(tài)后，才移交CPU限制權(quán)。第28頁/89進程調(diào)度算法考慮進程調(diào)度算法的因素有：1、盡量提高資源利用率，削減CPU空閑時間；2、對一般作業(yè)接受較合理的平均響應(yīng)時間；3、應(yīng)避開有的作業(yè)長期得不到響應(yīng)的狀況。進程調(diào)度算法： 優(yōu)先數(shù)法 輪轉(zhuǎn)調(diào)度法 分級調(diào)度法第29頁/89常用的算法是把CPU安排給具有最高優(yōu)先數(shù)的進程。靜態(tài)優(yōu)先數(shù)法進程優(yōu)先數(shù)是在系統(tǒng)創(chuàng)建進程時確定的，一經(jīng)確定，在進程運行期間就不再變更。動態(tài)優(yōu)先數(shù)法進程優(yōu)先數(shù)在進程運行中，隨進程特性的變更不斷修改進程的優(yōu)先數(shù)，實現(xiàn)更精確的調(diào)度。優(yōu)先數(shù)法第30頁/89輪轉(zhuǎn)調(diào)度法（動態(tài)法）先將就緒態(tài)進程按FIFO規(guī)則排成一個隊列，將CPU劃分為等長的時間片，安排給隊列中的每個進程。進程在運行了一個時間片q后，排至隊尾，如此循環(huán)。時間片q的取值為：q過小，系統(tǒng)開銷增加；q過大，又退化為FIFO法。一般來說，q值取為：q=100ms為宜。第31頁/89分級調(diào)度法（動態(tài)法）結(jié)合優(yōu)先數(shù)法和輪轉(zhuǎn)調(diào)度法分為具有較高優(yōu)先數(shù)的前臺隊列和較低優(yōu)先數(shù)的后臺隊列進程調(diào)度以固定的時間片把處理器安排給前臺隊列中的進程，僅當前臺隊列中的進程已全部完成或等待I/O操作時，才把處理器安排給后臺進程。第32頁/89臨界資源：一次僅允許一個進程運用的資源。如打印機、讀卡機、緩沖區(qū)、變量等。臨界區(qū)：進程中運用臨界資源的那段程序。各進程之間存在著相互制約、相互依靠的關(guān)系：同步:兩個事務(wù)的發(fā)生存在某種時序關(guān)系，假如系統(tǒng)中若干個進程要完成同一個任務(wù)，則進程之間要協(xié)調(diào)其推動的速度，以便正確完成作業(yè)運行，此即同步。請看兩個例子互斥：對于某一臨界資源，一組進程不能同時進入臨界區(qū)去運用它。一個進入，其他必需等待。請看兩個例子進程同步和互斥的實現(xiàn)方法二、進程的同步與互斥例1：進程同步的例子電子郵件信箱發(fā)送進程A接收進程B當信箱滿時，發(fā)送進程只有等待接收進程取走信件，當信箱空時，接收進程必需等待發(fā)送進程發(fā)送信件。12n……34例2:X=fun1(y)*fun2(Z)計算fun1(y)進程P2算完fun2(Z)?取用P2計算結(jié)果計算fun2(Z)設(shè)置計算完成標記終止YN進程P1進程P2????兩個協(xié)同工作進程的同步

35例1:公共地段交通十字路口的限制：公共地段互斥36例2:X=COUNTX=X+1COUNT=XY=COUNTY=Y+1COUNT=Y臨界區(qū)臨界區(qū)進程A進程B????????????????進程A與B對公共變量COUNT進行互斥操作，最終實現(xiàn)COUNT增加2。若A與B按下面依次推動，結(jié)果COUNT只實現(xiàn)增加1。A:X=COUNT；A:X=X+1;COUNT=X；B:Y=COUNT；B:Y=Y+1;COUNT=Y；用P-V原語對進程中信號量進行操作的方法（簡稱P-V操作）。原語：由若干條機器指令構(gòu)成，完成某一特定功能的一段程序。P原語操作過程：P操作記為P（S），其中S為一信號量，其執(zhí)行依次完成以下兩個動作：（1）

S：=S1，表示申請運用一個資源；（2）

若S0，表示系統(tǒng)中有資源可用，現(xiàn)進程可接著執(zhí)行。（3）

若S0，表示系統(tǒng)中沒有可用資源，則置該進程堵塞狀態(tài)，到S信號量的隊列中去等待，直到其他進程在S上 執(zhí)行V操作釋放它為止。信號量的概念和P、V原語是荷蘭科學家提出的。把交通管理的信號燈方法搬到了操作系統(tǒng)中。所謂信號量是一個與隊列有關(guān)的整型變量，表示系統(tǒng)中某類資源的數(shù)量。當其值大于0時，表示系統(tǒng)中尚有可用資源；當其值為負時，其確定值表示還欠缺的資源數(shù)。信號量的值僅能由P操作和V操作來變更，操作系統(tǒng)利用它的狀態(tài)對進程和資源進行管理。進程的同步與互斥的實現(xiàn)方法V原語操作過程：V操作記為V（S），其中S為一信號量，其執(zhí)行依次完成以下兩個動作：（1）

S：=S+1，表示釋放一個資源；（2）

若S0，表示系統(tǒng)中沒有等待該資源的進程，現(xiàn)進程可接著執(zhí)行（走）。（3）若S0，表示系統(tǒng)中有等待該資源的進程，則喚醒S信號量隊列中的第一個進程，使其插入到就緒隊列，現(xiàn)進程接著執(zhí)行。39第39頁/89（1）實現(xiàn)進程同步（a）非對稱制約（2）實現(xiàn)進程同步（b）雙向制約 ——生產(chǎn)者與消費者問題（3）實現(xiàn)進程互斥(1)干脆通信（消息緩沖區(qū)）(2)信箱通信(3)基于共享數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)通信P-V操作的應(yīng)用進程通信S=0把P-V操作用于進程同步???

進程AC:P(S)同步點同步條件???

進程BV(S)假定進程A前進到C點時，必需等到進程B執(zhí)行完同步條件才能接著前進。為了實現(xiàn)進程A與進程B在C點同步，設(shè)置信號量S初始值為0。在進程A的C點處設(shè)置P操作，在進程B設(shè)置V操作。假定A先于B到達C點，它要在S上執(zhí)行P操作，使S=-1<0，進程A被迫在S的隊列等待，始終等到進程B執(zhí)行了V操作之后，才能將其喚醒變?yōu)榫途w。反之，假定在進程A到達同步點之前先由B對S做了V操作，使S=1，因此當進程A到達C點做P操作時，由于S減１為０，就不會受到阻礙而順當?shù)赝ㄟ^同步點。41S1表示緩沖區(qū)中是否有供打印的數(shù)據(jù)，S1>0表示有數(shù)據(jù)；S2表示緩沖區(qū)中的數(shù)據(jù)是否被取走，S2>0表示已取走，有空的緩沖區(qū)；初值：S1=0，S2=0；查詢進程S把查詢結(jié)果寫到緩沖區(qū)V(S1)P(S2)???

???

打印進程PP(S1)把緩沖區(qū)內(nèi)容打印輸出V(S2)??????42生產(chǎn)者進程L1:{生產(chǎn)物品}P(S1)緩沖區(qū)物品V(S2)消費者進程C1:P(S2)從緩沖區(qū)取物品V(S1){消費物品}S1=1;S2=0;43為使這段操作能互斥進行，設(shè)置S1初值為1，S2初值為0。 其中：S1——緩沖區(qū)中是否有空，S1>0

有空緩沖區(qū)；

S2—— 緩沖區(qū)中是否有物品可供消費，S2>0有物品。則無論在何處中斷，均能進行協(xié)調(diào)工作。S=1進程A的臨界區(qū)P(S)進程AV(S)進程B的臨界區(qū)P(S)進程BV(S)為使這段操作能互斥進行，設(shè)置一個信號量S初值為1，在每個地段的入口處，支配對S的P操作，出口處做V操作。誰先對S做P操作，就會使S的值由1變?yōu)?，且自己獲準進入臨界區(qū)。另一進程再對S進行P操作，試圖進入自己的臨界地段，就會因為S的值由0變?yōu)?1而受到阻擋。只有等到在臨界地段內(nèi)的進程退出臨界地段時對S做V操作，使S的值由-1變?yōu)?，才會解除這一阻擋而放行，從而實現(xiàn)進程的互斥。44Y=COUNTY=Y+1COUNT=Y臨界區(qū)V(S)P(S)進程BX=COUNTX=X+1COUNT=X臨界區(qū)V(S)P(S)進程A設(shè)置S，初值為145dA發(fā)送區(qū)senddBReceive接收區(qū)1A進程B進程PCBB進程

直接通信P136...Send(B,dA)...B5Hello第一個消息緩沖區(qū)<A5HelloN—ptrH-ptrA5Hello...Receive(A,dB)46mutexssmSendP(sml)申請格子把信件從信件發(fā)送區(qū)讀到信箱格子中V(sm2)ReceiveP(sm2)限制是否有信件把第一個格子中的信件讀到信件接收區(qū)V(sm1)申請格子由信號量sm1限制（有格子）Sm2限制格子里是否有信件47信箱通信初值Sm1=1，Sm2=0２、死鎖產(chǎn)生的緣由（四個必要條件）（Ａ）資源不能共享（資源獨占性）。（Ｂ）資源接受動態(tài)安排原則：資源在等待新資源時，接著占 有已安排到的資源。（C）資源的不行剝奪性：一個進程占有的資源不能被別的進 程強行搶占。（D）允許進程間非法交叉推動依次的存在：導致循環(huán)等待資源，無法前進。48三、死鎖死鎖：每個進程所要求的資源都已被另一個進程占用，出現(xiàn)沒有一個進程能接著運行，這種狀況稱“死鎖”。打印機進程A進程B讀卡機進程A申請到打印機進程A須要讀卡機進程B申請到讀卡機進程B須要打印機49例如：進程A和B以下面的推動速度前進，導致死鎖。A：申請打印機2.B：申請讀卡機 3.A：申請讀卡機4.B：申請打印機第49頁/89*死鎖的檢測與復原允許死鎖產(chǎn)生，當死鎖發(fā)生時能檢測出來，并且有實力處理，進行復原?！りP(guān)于資源獨占性：接受可以使非共享設(shè)備變?yōu)楣蚕碓O(shè)備。解決死鎖的方法*死鎖的預防破壞產(chǎn)生死鎖的4個必要條件中的任何一個。·破壞“資源的不行剝奪性”（申請不到資源時，釋放原先已占有的，進入等待，以后再一起申請）?！て茐膶Y源接受動態(tài)的部分安排原則（每個進程必需提出它所須要的全部資源，只有完全滿足時，才能啟動）?！て茐难h(huán)等待。*死鎖的避開躲避死鎖的發(fā)生。接受虛擬技術(shù)，使非共享設(shè)備變成共享設(shè)備，以避開死鎖。用戶1用戶2用戶3??????輸出輸出輸出打印打印機主機51破壞資源獨占性假脫機技術(shù)（教材P153）系統(tǒng)資源進行統(tǒng)一編號。進程申請運用資源時，必需嚴格依據(jù)編號的升序進行。

進程資源ABC1、卡片輸入機

（3臺）√√√

2、行式打印機（2臺）√√*3、磁帶機（1臺）√*52破壞循環(huán)等待打破環(huán)路條件：將全部資源編號，申請時按依次申請，先申請小號，再申請大號，這樣，能保證申請到最大號者，確定運行完成。第52頁/89例：三個進程P1,P2,和P3,所須要磁帶機分別為10，4，9臺，系統(tǒng)中共12臺。T0時刻 最大需求 P1 10 P2 4 P3 9

T0時刻存在一個平安序列<P2,P1,P3>所以系統(tǒng)平安。假如P3懇求1臺,狀態(tài)發(fā)生變更.已安排5 22可用3

還需5 27找不到一個平安序列.狀態(tài)擔憂全.懇求不能滿足。假如P1懇求1臺,狀態(tài)發(fā)生變更.結(jié)果如何？假如P2懇求1臺,狀態(tài)發(fā)生變更.結(jié)果又如何？若把題中的12改為11，則T0時刻系統(tǒng)是擔憂全的，因為這時系統(tǒng)中雖有2臺可用設(shè)備，但不存在平安序列。當然，若不依據(jù)平安序列安排資源，平安狀態(tài)可能變?yōu)閾鷳n全狀態(tài)。<P2,P1,P3><P2,P1,P3>第53頁/89死鎖的避開死鎖的避開是這樣一種應(yīng)付死鎖的方法：系統(tǒng)在運行過程中實行動態(tài)的資源安排策略，保證系統(tǒng)不進入可能導致系統(tǒng)陷入死鎖狀態(tài)的所謂擔憂全狀態(tài)，以避開死鎖發(fā)生。常用的避開死鎖的算法是“銀行家算法”，系統(tǒng)接受此法給進程安排資源時，需先推斷“假如安排，系統(tǒng)狀態(tài)是否平安”，這很像銀行家放貸前的思索過程。第54頁/89(1)平安狀態(tài)與平安序列1)平安狀態(tài)若在某一時刻，系統(tǒng)能按某種進程依次，如<P1,P2,…,Pn>，來為每個進程安排其所需的資源，直至最大需求，使每個進程均可順當完成。則稱此時系統(tǒng)的狀態(tài)為平安狀態(tài)，稱這樣的一個進程序列<P1,P2,…,Pn>為平安序列。2)擔憂全狀態(tài)若在某時刻，系統(tǒng)無法找到一個平安序列，則稱系統(tǒng)處于擔憂全狀態(tài)。第55頁/89留意：（1）系統(tǒng)在某一時刻的平安序列可能不唯一，但這不影響對系統(tǒng)平安性的推斷。（2）平安狀態(tài)是非死鎖狀態(tài)，而擔憂全狀態(tài)并不確定是死鎖狀態(tài)。即系統(tǒng)處于平安狀態(tài)確定可以避開死鎖，而系統(tǒng)處于擔憂全狀態(tài)則僅僅有可能進入死鎖狀態(tài)。平安狀態(tài)擔憂全狀態(tài)死鎖狀態(tài)第56頁/89銀行家算法銀行家擁有一筆周轉(zhuǎn)資金客戶要求分期貸款，假如客戶能夠得到各期貸款，就確定能夠歸還貸款，否則就確定不能歸還貸款銀行家應(yīng)謹慎的貸款，防止出現(xiàn)壞帳用銀行家算法避開死鎖操作系統(tǒng)比作（銀行家）操作系統(tǒng)管理的資源比作(周轉(zhuǎn)資金)進程比作（要求貸款的客戶）為了避開死鎖的發(fā)生，系統(tǒng)對進程提出的每一個資源懇求，先不是真正去安排，而是依據(jù)當時資源的運用狀況，按確定的算法去進行模擬安排后的結(jié)果。只有當探測結(jié)果不會導致死鎖，才真正接收進程提出的這一懇求。類似下棋常用的算法是“銀行家算法”（1965年提出）。銀行家算法的思想:（假定在單類資源的安排上實行這一算法）。死鎖的避開每個用戶必需預先申請它所需的貸款總數(shù)，且此數(shù)值不能超過銀行資金總數(shù)；每個用戶每次只能向銀行申請一個單位貸款數(shù)；銀行依據(jù)當時的資金狀況，可能馬上滿足用戶申請，或者須要用戶等待一段時間；當用戶貸款總數(shù)達到申請數(shù)后，必需在有限時間內(nèi)一次歸還全部貸款。第58頁/89假如全部進程的“能執(zhí)行完”均為1，表示接受這次懇求是平安的；否則短暫不能接受進程的這次資源懇求。假如找到了，就假設(shè)它獲得了最大資源數(shù)，并運行結(jié)束。于是把它的“能執(zhí)行完”標記置為1。這樣就能假定收回它運用的全部資源，使系統(tǒng)剩余資源數(shù)增加。在這一假設(shè)下，檢查每個進程對資源的還須要數(shù)?？茨芊裾业揭粋€進程，其還需數(shù)目小于系統(tǒng)剩余資源數(shù)。假如找不到，那么系統(tǒng)就有可能死鎖，因為任何進程都無法運行結(jié)束。在平安狀態(tài)下，系統(tǒng)接到進程的資源懇求后，先假定接受這一懇求，把須要的資源安排給這個進程。單種資源銀行家算法的基本思想單種資源銀行家算法：將全部進程的“能執(zhí)行完”標記清0假定接受該懇求,把資源安排給進程將系統(tǒng)當前全部剩余資源與”能執(zhí)行完”標記為0的進程還需資源數(shù)比較,找出一個能滿足其全部需求的進程找到了嗎？將該進程的”能執(zhí)行完”標記置為1,系統(tǒng)收回它所要求的全部資源數(shù)YN檢查全部進程的“能執(zhí)行完”標記還有”能執(zhí)行完”標記為0的進程嗎？這一懇求擔憂全,短暫不予接受YN這一懇求是安全的,可以安排.....在“能執(zhí)行完”標記為0的進程中重復以上兩步，直到找不到資源還需數(shù)小于系統(tǒng)剩余資源數(shù)的進程時為止。進程已分配數(shù)還需要數(shù)A13B42C53系統(tǒng)剩余2進程已分配數(shù)還需要數(shù)A22B42C53系統(tǒng)剩余1例1：假定某系統(tǒng)有12臺磁帶機，A最大須要量4B最大須要量6C最大須要量8單種資源銀行家算法實例(a)(b)經(jīng)過若干次申請、安排，系統(tǒng)的狀態(tài)（a）狀態(tài)時，若進程A提出申請1臺磁帶機后，接受銀行家算法系統(tǒng)假定安排后的狀態(tài)一個平安序列BAC狀態(tài)擔憂全.懇求不能滿足第60頁/89例24個客戶每個都有一個貸款額度單種資源銀行家算法的基本思想已運用：已安排；最大：一共需求（b）一個平安序列MBAS（c)在（b）狀態(tài)下答應(yīng)BARBARA的申請，將擔憂全第61頁/89對每個懇求進行檢查，是否會導致?lián)鷳n全狀態(tài)。若是，則不滿足該懇求；否則便滿足檢查狀態(tài)是否平安的方法：是看它是否有足夠的資源滿足一個距最大需求最近的客戶，如此反復下去。假如全部投資最終都被收回，則該狀態(tài)是平安的，最初的懇求可以批準。

系統(tǒng)擁有某類資源10個進程已有資源數(shù)還要申請資源數(shù)P44Q22R27a、單項資源的銀行家算法第62頁/89假如存在這種進程，那么假定它已獲得須要的全部資源，并完成工作，把它的“能執(zhí)行完”標記設(shè)置成1。收回它占用的資源，更新向量V。檢查還需資源表中是否有一個進程的行向量小于或等于向量V。假如沒有，那么系統(tǒng)就可能會死鎖，因為現(xiàn)在任何進程都無法完成了。多種資源銀行家算法的執(zhí)行步驟系統(tǒng)設(shè)兩張表：“安排資源表”，記錄已安排給各進程的資源數(shù)；“還需資源表”，記錄各進程還須要的資源數(shù)。設(shè)3個向量：R記錄各種資源的總數(shù)，A記錄各種資源已安排數(shù)，V記錄各種資源的剩余數(shù)。進程磁帶機繪圖儀打印機CD-ROMA3011B0100C1110D1101E0000進程磁帶機繪圖儀打印機CD-ROMA1100B0112C3100D0010E2110已安排資源表還需資源表R[6342](資源總數(shù))A[5322](已安排數(shù))V[1020](剩余數(shù)).假定接受一個進程提出的資源懇求，修改向量A和V。....重復以上兩步，直至再也找不到行向量小于或等于向量V的進程。

檢查全部進程的“能執(zhí)行完”標記。若這個標記都是1，則表示都能順當?shù)赝瓿?。因此，接受資源分配后導致的新狀態(tài)是平安的；假如仍存在“能執(zhí)行完”標志為0的進程，則說明這一懇求所導致的狀態(tài)是擔憂全的，應(yīng)短暫拒絕該懇求。多類資源的安排（Habermann算法P140）第63頁/89b、多項資源的銀行家算法先定義幾個向量：

Resource=(R1,R2,…,Rm):系統(tǒng)各類資源的總數(shù)；aVailable=(V1,V2,…,Vm):系統(tǒng)未安排的資源數(shù)量V向量第64頁/89最大需求矩陣--每個進程對每類資源的最大需求量,Cij表示進程Pi需Rj類資源最大數(shù)Claim=C11C12C1mC11C11C11Cn1Cn1Cnm………第65頁/89安排矩陣—表示進程當前已分得的資源數(shù),Aij表示進程Pi已分到Rj類資源的個數(shù)

Allocation=A11A12A1mA21A21A21An1An1Anm………第66頁/89下列關(guān)系式確保成立?

Ri=Vi+∑Aki對i=1,..,m,k=1,..,n;表示全部資源要么已被安排、要么尚可安排?Cki≤Rj對i=1,..,m,k=1,..,n;表示進程申請資源數(shù)不能超過系統(tǒng)擁有的資源總數(shù)?Aki≤Cki對i=1,..,m,k=1,..,n;表示進程申請任何類資源數(shù)不能超過聲明的最大資源需求數(shù)第67頁/89匯總向量R--總的資源、A--已安排資源、V--剩余資源RAVPPT63狀態(tài)下平安推斷，平安序列？SEE教材P144例題留意F向量第68頁/89總的資源R、已安排資源A、剩余資源V圖示為平安狀態(tài)，平安序列（D，A，E，B，C）RAV第69頁/89...系統(tǒng)中有A~G共7個進程，6個同類資源r~w，當前的資源所屬關(guān)系如下：死鎖的檢測與復原1.利用資源安排圖檢測死鎖rAsCDFwuGtBEv.A得到資源r，須要資源s；.B不占有資源，須要資源t；.C不占有資源，須要資源s；D得到資源u和s，須要資源t；.E得到資源t，須要資源v；F得到資源w，須要資源s；G得到資源v，須要資源u。2.利用表格檢測死鎖環(huán)路資源占用的進程進程等待的資源rAsCtBuBvAAt進程等待的資源AtBCsv通過建立“資源安排表”和“進程等待表”，隨時檢測資源的安排是否構(gòu)成環(huán)路。假定現(xiàn)有3個進程A~C，有5個同類型資源r~v。SEEPPT75資源安排表進程等待表進程等待表3.死鎖的復原一是刪除環(huán)中的若干進程，釋放占用的資源，使其他進程能接著運行；二是臨時把某個資源從占用者手中剝奪，給另一個進程運用；三是周期地記錄各進程執(zhí)行狀況。一旦檢測到死鎖，就按記錄的文件進行回退，讓損失減到最小。第70頁/89當系統(tǒng)為進程安排資源時，若未實行任何限制性措施保證不進入死鎖狀態(tài)，則系統(tǒng)必需供應(yīng)解除死鎖的手段。1.資源安排圖R1R2P1P2用方框代表資源，圓圈代表進程。畫一條由資源到進程的有向邊，表示把該資源安排給這個進程；畫一條由進程到資源的有向邊，表示該進程要申請這個資源。這樣的圖就是所謂的“資源安排圖”。第71頁/89R1

R2P1P2R1R2

P1P2R1R2P1P2第72頁/89例如，對于P={P1,P2,P3}，R={R1,R2,R3,R4}，E={<P1,R1>，<P2,R3>，<R1,P2>，<R2,P2>，<R3,P3>，<P3,R2>，<R2,P1>}，它的資源安排圖如圖所示?？梢宰C明，假如資源安排圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖；假如圖中存在環(huán)路，則系統(tǒng)中可能存在死鎖。假如每個資源類中均只包含一個資源，則環(huán)路的存在即意味著死鎖的存在，此時，環(huán)路是死鎖的充分必要條件。在圖中，有兩個環(huán)：第73頁/89圖5-7資源安排圖(含環(huán)路)P1→R1→P2→R3→P3→R2→P1P2→R3→P3→R2→P2P1、P2、P3均處于死鎖狀態(tài)。SEE教材P143例題資源號占有資源的進程號a1b3c2d2e1進程號等待資源1c2資源分配表進程等待表進程號等待資源1c2b3e(1)(2)(3)e132bc進程間對資源的循環(huán)等待對進程資源狀態(tài)圖的化簡可通過對系統(tǒng)全部資源和進程進行編號，并設(shè)置一張資源安排表和一張進程等待表來實現(xiàn)：假設(shè)系統(tǒng)現(xiàn)在有資源為a、b、c、d、e。系統(tǒng)有3個進程，分別用編號1~3表示。在某一時刻，系統(tǒng)資源安排表如圖（1）所示，假定這時各進程按下列方式提出申請資源：進程1申請資源c進程2申請資源b進程3申請資源e經(jīng)過考察資源安排表并填寫資源申請表，發(fā)覺出現(xiàn)了循環(huán)等待鏈，產(chǎn)生了死鎖。一經(jīng)發(fā)覺死鎖，必需馬上解除。出現(xiàn)進程循環(huán)鏈的現(xiàn)象進程1ae進程3c進程2bd第76頁/893死鎖定理當且僅當S的資源安排圖是不行完全化簡的，S為死鎖狀態(tài)。死鎖的解除：1)終止死鎖進程；2)按確定依次中止進程直至釋放到有足夠的資源來完成剩下的進程為止；3)從被鎖住進程中強迫剝奪資源以解除死鎖。第77頁/89用戶與操作系統(tǒng)之間的接口 －程序一級的接口系統(tǒng)調(diào)用 －作業(yè)限制一級的接口

作業(yè)狀態(tài)及轉(zhuǎn)換圖

作業(yè)調(diào)度作業(yè)限制四、作業(yè)管理與限制第78頁/89人機界面（HCI-HumanComputerInterface）用戶接口實質(zhì)上是供應(yīng)了一個人機界面，包括：基于字符界面的接口基于圖形用戶界面接口（GUI-GraphicalUserInterface）多媒體接口其他特殊類型的接口

用戶接口圖形用戶接口多媒體型接口字符型及其他特殊型接口基于MOTIF基于