計算機操作系統(tǒng)之進程管理

第二章

進程管理2.1.1

程序的順序執(zhí)行及特征一、程序執(zhí)行有固定的時序。（圖2-1p27）二、特征：順序性、封閉性、可再現(xiàn)性2.1進程的基本概念I1C1P1I2C2P22007年1月2.1.2前趨圖定義有向無循環(huán)圖表示方式： （1）p1--->p2（2）--->={(p1,p2)|p1必須在p2開始前完成}（圖2-2P27）節(jié)點表示：一條語句，一個程序段，一進程。P1P1P1P12007年1月2.1.3程序的并發(fā)執(zhí)行一、多個程序的并發(fā)執(zhí)行（可能性分析）I1I2I3I4C1C2C3C4P1P2P3P4t2007年1月程序的并發(fā)執(zhí)行(2)二、特征間斷性失去封閉性：主要由共享資源引起不可再現(xiàn)性：P29例，設N的初值為n。有2個循環(huán)程序A和B，它們共享一個變量N，程序A每執(zhí)行一次時，都要做N:=N+1;B則每次要執(zhí)行Print(N),然后再做N:=0.若程序A,B以不同的速度運行有以下三種不同的結(jié)果2007年1月程序的并發(fā)執(zhí)行(3)N:=N+1在print(N)和N:=0之前，則N值分別為n+1,n+1,0.N:=N+1在print(N)和N:=0之后，則N值分別為n,0，1.N:=N+1在print(N)和N:=0之間，則N值分別為n,n+1,0.

2007年1月2.1.4進程的特征和狀態(tài)1.進程的特征和定義一、定義：程序的一次執(zhí)行過程1.結(jié)構(gòu)特征進程：由程序段、數(shù)據(jù)段及進程控制塊三部分構(gòu)成，總稱“進程映像”。2.動態(tài)性由“創(chuàng)建”而產(chǎn)生，由“調(diào)度”而執(zhí)行；由得不到資源而阻塞；由撤消而消亡。（而程序是靜態(tài)的）。2007年1月2.1.4進程的特征和狀態(tài)(2)3.并發(fā)性只有建立了進程，才能并發(fā)執(zhí)行。4.獨立性。獨立運行，獨立獲得資源。5.異步性：（間斷性）2007年1月2.1.4進程的特征和狀態(tài)(3)2.進程的三種基本狀態(tài)（圖2-5p31）就緒狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)就緒阻塞執(zhí)行時間片完進程調(diào)度I/O請求I/O完成圖2－5進程的三種基本狀態(tài)及其轉(zhuǎn)換2007年1月2.1.4進程的特征和狀態(tài)(4)3.掛起狀態(tài)（被換出內(nèi)存的狀態(tài)）引入原因終端用戶請求父進程請求負荷調(diào)節(jié)需要操作系統(tǒng)需要進程狀態(tài)的轉(zhuǎn)換(圖2-6)活動就緒

靜止就緒活動阻塞

靜止阻塞靜止就緒

活動就緒靜止阻塞

活動阻塞2007年1月圖2－6具有掛起狀態(tài)的進程狀態(tài)圖執(zhí)行活動就緒靜止就緒活動阻塞靜止阻塞激活掛起激活掛起釋放釋放掛起請求I/O2007年1月實驗寫一個程序描述進程狀態(tài)遷移過程。要求：提供導致進程狀態(tài)變化的調(diào)用接口，包括創(chuàng)建、刪除、調(diào)度、阻塞、時間到、掛起、激活等。實現(xiàn)進程列表顯示的接口。注：這里設計的進程是一個假設的對象實體，是由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護的進程。2007年1月2.1.5進程控制塊1.進程控制塊的作用是進程存在的唯一標志；PCB(process

controlblock)常駐內(nèi)存2.進程控制塊中的信息標識、處理機狀態(tài)，進程調(diào)度信息，進程控制信息pid進程狀態(tài)現(xiàn)場優(yōu)先級阻塞原因程序地址同步機制資源清單鏈接指針2007年1月2.1.5進程控制塊(2)3.PCB的組織鏈接（p33圖2-7）索引(p34圖2-8)PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針2007年1月等待隊列示例structwait_queue{

struct

task_struct*task;

structwait_queue*next;};PCBPCBPCB2007年1月2.1.5進程控制塊(3)3.PCB的組織索引(p34圖2-8)PCB1PCB2PCB3PCB4PCB5PCB6PCB7執(zhí)行指針就緒表指針阻塞表指針2007年1月補充PCB和進程的代碼數(shù)據(jù)放在一起嗎？系統(tǒng)態(tài)和用戶態(tài)系統(tǒng)空間和用戶空間系統(tǒng)調(diào)用和普通調(diào)用的區(qū)別？系統(tǒng)調(diào)用會引起從用戶態(tài)進入核心態(tài)2007年1月2.2進程控制2.2.1進程的創(chuàng)建一、進程圖：描述了進程的家族關系：（P34圖2-9）子進程可繼承父的資源，撤消時應歸還給父進程，父的撤消會撤消全部子進程。二、引起創(chuàng)建進程的事件：1.用戶登錄：為終端用戶建立一進程2.作業(yè)調(diào)度：（不是進程調(diào)度）為被調(diào)度的作業(yè)建立進程3.提供服務：如要打印時建立打印進程2007年1月2.2.1進程的創(chuàng)建(2)4.應用請求：由應用程序建立多個進程三、進程的創(chuàng)建：（creat原語）1.申請空白PCB（一個系統(tǒng)的PCB是有限的）2.為新進程分配資源（不同于一般的分配，PCB-LIST在一個特殊區(qū)域）3.初始化PCB4.將新進程插入就緒隊列。2007年1月2.2.2進程的終止一、引起進程終止的事件1.正常結(jié)束：如Halt、logoff2.異常結(jié)束：如Protecterror、overtime等3.外界干預：a.系統(tǒng)員kill進程；b.父進程終止；c.父進程請求。2007年1月2.2.2進程的終止(2)二、進程的終止過程（1）檢查進程狀態(tài)；（2）執(zhí)行態(tài)――>中止，且置調(diào)度標志為真。（3）有無子孫需終止。（4）歸還資源給其父進程或系統(tǒng)。（5）從PCB隊列中移出PCB.2007年1月2.2.3進程的阻塞與喚醒一、引起進程阻塞和喚醒的事件1.請求系統(tǒng)服務而得不到滿足時，如問系統(tǒng)請求打印。2.啟動某種操作而需同步時：如該操作和請求該操作的進程需同步運行（即非異步操作）。3.新數(shù)據(jù)尚未到達：如進程A寫，進程B讀，則A未寫，完B不能讀。4.無新工作可做。2007年1月2.2.3進程的阻塞與喚醒(2)二、進程阻塞過程：是進程自身的一種主動行為a.調(diào)block原語b.停止執(zhí)行，修改PCB入阻塞隊列（一個或多個），并轉(zhuǎn)調(diào)度。三、喚醒過程其它相關進程完成。a.wakeup原語b.修改PCB，入就緒隊列可見，有block原語，在其它進程中就應有wakeup原語。2007年1月2.2.4進程的掛起與激活一、進程的掛起過程由進程自己或其父進程調(diào)suspend原語完成，將該進程PCB移到指定區(qū)域，注意狀態(tài)的改變，有可能要重新調(diào)度。二、進程的激活過程。active原語（如在外存，調(diào)入內(nèi)存，改變狀態(tài)，根據(jù)情況看是否調(diào)度，如搶先或非搶先）。阻塞、喚醒一般由OS實現(xiàn)，而掛起與激活可由用戶干預。2007年1月2.3進程同步同步：并發(fā)進程在執(zhí)行次序上的協(xié)調(diào)，以達到有效的資源共享和相互合作，使程序執(zhí)行有可再現(xiàn)性。2007年1月2.3.1進程同步的基本概念1.兩種形式的制約關系資源共享關系：（進程間接制約）需互斥地訪問臨界資源。相互合作關系：（進程直接制約）2.臨界資源：（一次僅允許一個進程訪問的資源）引起不可再現(xiàn)性是因為臨界資源沒有互斥訪問。2007年1月生產(chǎn)者－消費者問題Varn,integer;Typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;2007年1月生產(chǎn)者－消費者問題producer:repeat… produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;2007年1月生產(chǎn)者－消費者問題（2）設counter的初值為5register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;register1:=counter; (register1:=5)register1:=register1+1; (register1:=6)register2:=counter; (register2:=5)register2:=register2-1; (register2:=4)counter:=register1; (counter:=6)counter:=register2; (counter:=4)2007年1月定義：進程訪問臨界資源的那段代碼。訪問臨界資源的描述：進入?yún)^(qū)：檢查有無進程進入臨界區(qū)：退出區(qū)：將訪問標志復位Repeat Entrysection Criticalsection Exitsection Untilfalse3.臨界區(qū)2007年1月4.同步機制應遵循的準則1.空閑讓進2.忙則等待3.有限等待：應保證為有限等待，不會產(chǎn)生死等。4.讓權(quán)等待：不能進入臨界區(qū)的執(zhí)行進程應放棄CPU執(zhí)行權(quán)。2007年1月2.3.2信號量機制1整型信號量是一個整型量，通過2個原子操作wait(s)和signal(s)來訪問。Wait(s):whiles<=0dono-op s:=s-1;Signal(s): s:=s+1;2007年1月2記錄型信號量

由于整型機制中會不斷測試不滿足“讓權(quán)等待”而引入typesemaphore=recordvalue:integer;L:listofprocess;endL:為進程鏈表，用于鏈接所有等待該類資源進程。procedurewait(s)vars:semaphorebegins.value:=s.value–1;ifs.value

<0themblock(S,L)end2007年1月2記錄型信號量(2)

proceduresignal(S)var

s:semaphonebegins.value:=s.vaule+1ifs.value<=0thenwakeup(s.L)end用wait(s)和signal(s)實現(xiàn)同步與互斥。在記錄型信號量機制中：s.value初值：表示系統(tǒng)中某類資源的數(shù)目。s.value<0:表該信號量鏈表中已阻塞進程的數(shù)目。2007年1月3AND型信號量當不用它時，有可能發(fā)生系統(tǒng)死鎖。死鎖：在無外力作用下的一種僵持狀態(tài)。AND信號量例：P42.特點：要么全分配，要么一個也不分配。2007年1月3AND型信號量processA:wait(Dmutex);wait(Emutex);processB:wait(Emutex);wait(Dmutex);若2進程交替執(zhí)行，則死鎖2007年1月3AND型信號量Swait(s1,s2,…,sn) ifs1≥1and…and

sn≥1then fori:=1tondosi:=si-1;endfor else placetheprocessinthewaitingqueuewiththefirstsifoundwithsi<1,andsettheprogramcountofthisprocesstothebeginningofswaitoperation endifSsignal(s1,s2,…,sn) fori:=1tondosi:=si+1;removealltheprocesswaitinginthequeueassociatedwithsiintothereadyqueue

endfor2007年1月4信號量集(略)為提高效率而對AND信號的擴充。（P43）三種特例：（1）Swait(S,d,d)：允許每次申請d個資源。 當資源數(shù)少于d時，不予分配。（2）Swait(s,1,1)：S>1，記錄型信號量。

S=1時，互斥型信號量。（3）Swait(s,1,0)，可控開關，當時，允許進入，S<1時，不能進入。2007年1月2.3.3信號量的應用

1.利用信號量實現(xiàn)互斥var

mutex:semaphore:=1 begin

parbegin process1:begin repeat

wait(mutex); criticalsetion

signal(mutex); remaindersection untilfalse; end2007年1月1.利用信號量實現(xiàn)互斥(2)

process2:begin repeat

wait(mutex); criticalsetion

signal(mutex); remaindersection untilfalse; endparend

2007年1月2.利用信號量來描述前趨關系(1)S1S2S3S4S5S6abcdegf圖2－10前趨圖舉例2007年1月利用信號量來描述前趨關系(2)Var

a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;Begin

parbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S1;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;

parendend2007年1月2.4經(jīng)典進程同步問題2.4.1生產(chǎn)者－－消費者問題2.4.2哲學家進餐問題2.4.3讀者－－寫者問題2007年1月一、利用記錄型信號量解決生產(chǎn)者一消費者問題mutex：使諸進程互斥地訪問緩沖區(qū)（n個緩沖區(qū)）empty、full：空、滿緩沖區(qū)數(shù)量。Var

mutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem; in,out:integer:=0,0; begin

parbeginproducer:begin repeat … Produceaniteminnextp; …2007年1月一、利用記錄型信號量解決生產(chǎn)者一消費者問題wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);Untilfalse;endconsumer:begin repeat

wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);Consumertheiteminnextc;Untilfalse;endparendend2007年1月二、利用AND信號量解決生產(chǎn)者——消費者問題

var

mutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1]ofitem; inout:integer:=0,0;begin

parbegin producer:begin repeat … produceaniteminnextp; …

swait(empty,mutex);

buffer(in):=nextp;2007年1月in:=(in+1)modn;ssingal(mutex,full);Untilfalse;EndConsumer:beginrepeat

swait(full,mutex);

nextc:=buffer(out); out:=(out+1)modn;

ssignal(mutex,empty); consumertheiteminnextc;untilfalse;endparendend2007年1月2.4.2哲學家進餐問題1.利用記錄型信號量解決哲學家進餐問題2007年1月2.4.2哲學家進餐問題1.利用AND信號量解決哲學家進餐問題Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processiRepeatthink;Sswait(chopstick[(i+1)mod5],chopstick[i]);eatSsignal(chopstick[(i+1)mod5],chopstick[i]);Untilfalse2007年1月2.4.3讀者——寫者問題特點： 讀進程可共享同一對象。寫進程不可共享同一對象。2007年1月一、利用記錄型信號量解決讀者——寫者問題

var

rmutex,wmutex:semaphore:=1,1;

readcount:integer:=0; begin

parbegin reader:begin repeat

wait(rmutex); ifreadcount=0thenwait(wmutex);

readcount:=readcount+1;

signal(rmutex); … performreadoperation2007年1月一、利用記錄型信號量解決讀者——寫者問題

performreadoperation …

wait(rmutex);

readcount:=readcount-1; ifreadcount=0thensignal(wmutex);

signal(rmutex); untilfalse; end 2007年1月一、利用記錄型信號量解決讀者——寫者問題

writer:begin repeat

wait(wmutex) performwriteoperation;

signal(wmutex) untilfalse; end

parendend2007年1月二、信號量集解決讀者——寫者問題(略)varRNinteger; L,mx:semaphore:=RN,q;begin

parbeginreader:begin repeatswait(L,1,1);swait(mx,1,0);… performreadoperation; … ssignal(L,1);untilfalse;endwriter:begin2007年1月二、信號量集解決讀者——寫者問題（略）

writer:beginrepeatswait(mx,1,1;L,RN,0);performwriteoperation;

ssignal(mx,1);untilflase;end

parendend2007年1月2.5管程機制引入原因：為了避免凡要使用臨界資源的進程都自備同步操作wait(s)和signal(s).將同步操作的機制和臨界資源結(jié)合到一起，形成管程。2.5.1管程的基本概念一、定義：一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行的一組操作。局部于管程的共享變量。對該數(shù)據(jù)結(jié)構(gòu)進程操作的一組過程。對局部管程數(shù)據(jù)設置初值。二、條件變量：

x.y:x.wait;x.signal;x.queue2007年1月2.5.2利用管程解決生產(chǎn)者——消費者問題

一、建立管程：PC包括：二過程： （1）put(item)過程；（2）get(item)過程一變量：count≥n時滿；≤0時空初始：in=out=count=0Typeproducer-consumer=monitorvar

in,out,count：integer;buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)procedureentryget(item)2007年1月2.5.2利用管程解決生產(chǎn)者——消費者問題

Procedureentryput(item) begin ifcount≥nthennotfull.wait;

buffer(in):=nextp; in:=(in+1)modn count:=count+1; ifnotempty.queuethennotempty.signal; endProcedureentryget(item) begin ifcount≤0thennotempty.wait;

nextc:=buffer(out); out:=(out+1)modn count:=count-1; ifnotfull.queuethennotfull.signal; endBeginin:=out:=0;count:=0end2007年1月2.5.2利用管程解決生產(chǎn)者——消費者問題

例：producer:begin repeat produceaitemnextp PC.put(item); untilfalse. EndConsumer:begin repeat

PC.get(item); Consumetheiteminnextc; Untilfalse end 可見，由管程來實現(xiàn)后，進程的同步更簡單明了。2007年1月練習

a,b

兩點間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：當ab間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在ab段外等待；當ab之間無車時，到達a（或b）的車輛可以進入ab段，但不能從a，b點同時駛?cè)?；當某方向在ab段行駛的車輛使出了ab段且無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。請用wait,signal工具對ab段實現(xiàn)正確管理。2007年1月答：Semaphores,mutexab,mutexbaPab：Wait(mutexab)Countab++Ifcountab=1thenwait(s);Signal(mutexab)

…..wait(mutexab)countab--;ifcountab=0thensignal(s)signal(mutexab);2007年1月答：Pba:wait(mutexba)countba=countba+1;Ifcountba=1thenwait(s)wait(mutexba)enter; ……wait(mutexba)countba--;ifcountba=0thensignal(s)

signal(mutexba);2007年1月2.6進程通信概念：進程間的信息交換。實例：信號量機制（一種低級通信） 缺點：（1）效率低 （2）通信對用戶不透明高級通信特點：效率高，通信實現(xiàn)細節(jié)對用戶透明2007年1月2.6.1進程通信的類型一、共享存貯器系統(tǒng)1.基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式：produce-consume中的緩沖區(qū)，低效，不透明。系統(tǒng)只提供了一共享存貯器，適于少量通信。2.基于共享存儲區(qū)的通信方式：系統(tǒng)提供：共享存儲區(qū)。通信過程：（1）向系統(tǒng)申請一個或多個分區(qū)（2）獲得分區(qū)獲后即可讀/寫.特點：高效，速度快。2007年1月2.6.1進程通信的類型二、消息傳遞系統(tǒng)（可用于異種機）信息單位：消息（報文）是目前的主要通信方式，分為直接通信方式、間接通信方式實現(xiàn)：一組通信命令（原語），具有透明性--->同步的實現(xiàn)。三、管道通信管道：連接一個讀進程和一個寫進程之間通信的共享文件。功能：大量的數(shù)據(jù)發(fā)收。注意：（1）互斥（2）同步（3）對方是否存在2007年1月2.6.2直接/間接通信方式（消息通信的2種方式）

一、直接send(Receiver,message)receive(Sender,message)例：解決生產(chǎn)—消費問題。

repeat …produceaniteminnextp;…

send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);…consumertheiteminnextc;untilfalse;2007年1月2.6.2直接/間接通信方式（消息通信的2種方式）

二、間接（可以實現(xiàn)非實時通信）優(yōu)點：在讀/寫時間上的隨機性寫進程――>信箱（中間實體）――>讀進程原語（1）信息的創(chuàng)建與撤消：信箱名屬性（公用、私用、共享）（共享者名字）（2）消息的發(fā)送和接收Send(mailbox,message)Receive(mailbox,message)2007年1月2.6.2直接/間接通信方式（消息通信的2種方式）

二、間接（可以實現(xiàn)非實時通信）信箱類型（1）私用：擁有者有讀/寫數(shù)，其它只有寫權(quán)，（單向）存在期＝進程存在期。（2）公用：系統(tǒng)創(chuàng)建，雙向，存在期=系統(tǒng)存在期。（3）共享信箱：一般進程創(chuàng)建，并指明其共享者，是雙向。發(fā)送—接收進程之間的關系：（1）一對一關系；（2）多對一關系；（3）一對多關系；（4）多對多關系：公用信箱。2007年1月2.6.3消息傳遞系統(tǒng)中的幾個問題一、通信鏈路：（1）顯式建立：（進程完成）（2）隱式建立：（系統(tǒng)完成）鏈路類型：（1）由連接方法分：點—點鏈路，多點鏈路。（2）由通信方式分：單向、雙向。（3）由容量分：無容量（無緩沖區(qū)）、有（有緩沖區(qū)）。2007年1月2.6.3消息傳遞系統(tǒng)中的幾個問題二、消息格式：消息頭：含控制信息如：收/發(fā)進程名，消息長度、類型、編號消息內(nèi)容：定長消息：系統(tǒng)開銷小，用戶不便（特別是傳長消息用戶）變長消息：開銷大，用戶方便。2007年1月2.6.3消息傳遞系統(tǒng)中的幾個問題三、進程同步方式1.發(fā)送和接收進程阻塞（匯合）用于緊密同步，無緩沖區(qū)時。2.發(fā)送進程不阻塞，接收進程阻塞（多個）相當于接收進程（可能是多個）一直等待發(fā)送進程，如：打印進程等待打印任務。3.發(fā)送/接收進程均不阻塞一般在發(fā)、收進程間有多個緩沖區(qū)時。2007年1月2.6.4消息緩沖隊列通信機制一、數(shù)據(jù)結(jié)構(gòu)1.消息緩沖區(qū)typemessagebuffer=recordsender:size:text:next:指向下一指針2.PCB中應增數(shù)據(jù)項：typepcb=recordmq

消息隊列指針mutex

消息隊列互斥信息量sm

消息隊列資源信息量（表資源消息數(shù)）2007年1月2.6.4消息緩沖隊列通信機制二、發(fā)送原語

proceduresend(receiver,a)begin

getbuf(a.size,i);

i.sender:=a.sender;

i.size:=a.size;

i.text:=a.text;

i.next:=0;

getid(PCBset,receiver.j);

wait(j.mutex);

insert(j.mq,i);

signal(j.mutex);

signal(j.sm);end2007年1月2.6.4消息緩沖隊列通信機制三、接收原語procedurereceive(b) begin j:=internalname;

wait(j.sm);

wait(j.mutex);

remove(j.mq,i);

signal(j.mutex);

b.sender:=i.sender;

b.size:=i.size;

b.text:=i.text; end2007年1月2.6.4消息緩沖隊列通信機制sender:Asize:5text:hellonext:0smmutexmqsender:Asize:5text:Hellosend(B,a)發(fā)送區(qū)A接收區(qū)Basender:Asize:5text:Helloreceive(b)b進程APCB(B)進程B2007年1月練習試說明如果使用send_mailbox和receive_mailbox

原語實現(xiàn)打印文件的系統(tǒng)。欲打印