操作系統(tǒng)第二章 進程管理

第二章

進程管理2.1.1程序的順序執(zhí)行及特征一、程序執(zhí)行有固定的時序。（圖2-1p27）二、特征：順序性、封閉性、可再現(xiàn)性2.1進程的基本概念I1C1P1I2C2P22.1.2前趨圖定義有向無循環(huán)圖表示方式： （1）p1--->p2（2）--->={(p1,p2)|p1必須在p2開始前完成}（圖2-2P27）節(jié)點表示：一條語句，一個程序段，一進程。P1P1P1P12.1.3程序的并發(fā)執(zhí)行一、多個程序的并發(fā)執(zhí)行（可能性分析）I1I2I3I4C1C2C3C4P1P2P3P4t程序的并發(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以不同的速度運行有以下三種不同的結果程序的并發(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.

2.1.4進程的特征和狀態(tài)1.進程的特征和定義一、定義：程序的一次執(zhí)行過程1.結構特征進程：由程序段、數(shù)據(jù)段及進程控制塊三部分構成，總稱“進程映像”。2.動態(tài)性由“創(chuàng)建”而產(chǎn)生，由“調度”而執(zhí)行；由得不到資源而阻塞；由撤消而消亡。（而程序是靜態(tài)的）。2.1.4進程的特征和狀態(tài)(2)3.并發(fā)性只有建立了進程，才能并發(fā)執(zhí)行。4.獨立性。獨立運行，獨立獲得資源。5.異步性：（間斷性）2.1.4進程的特征和狀態(tài)(3)2.進程的三種基本狀態(tài)（圖2-5p31）就緒狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)就緒阻塞執(zhí)行時間片完進程調度I/O請求I/O完成圖2－5進程的三種基本狀態(tài)及其轉換2.1.4進程的特征和狀態(tài)(4)3.掛起狀態(tài)（被換出內存的狀態(tài)）引入原因終端用戶請求父進程請求負荷調節(jié)需要操作系統(tǒng)需要進程狀態(tài)的轉換(圖2-6)活動就緒靜止就緒活動阻塞靜止阻塞靜止就緒活動就緒靜止阻塞活動阻塞圖2－6具有掛起狀態(tài)的進程狀態(tài)圖執(zhí)行活動就緒靜止就緒活動阻塞靜止阻塞激活掛起激活掛起釋放釋放掛起請求I/O實驗寫一個程序描述進程狀態(tài)遷移過程。要求：提供導致進程狀態(tài)變化的調用接口，包括創(chuàng)建、刪除、調度、阻塞、時間到、掛起、激活等。實現(xiàn)進程列表顯示的接口。注：這里設計的進程是一個假設的對象實體，是由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護的進程。2.1.5進程控制塊1.進程控制塊的作用是進程存在的唯一標志；PCB(processcontrolblock)常駐內存2.進程控制塊中的信息標識、處理機狀態(tài)，進程調度信息，進程控制信息pid進程狀態(tài)現(xiàn)場優(yōu)先級阻塞原因程序地址同步機制資源清單鏈接指針2.1.5進程控制塊(2)3.PCB的組織鏈接（p33圖2-7）索引(p34圖2-8)執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91等待隊列示例structwait_queue{ structtask_struct*task; structwait_queue*next;};PCBPCBPCB2.1.5進程控制塊(3)3.PCB的組織索引(p34圖2-8)PCB1PCB2PCB3PCB4PCB5PCB6PCB7執(zhí)行指針就緒表指針阻塞表指針補充PCB和進程的代碼數(shù)據(jù)放在一起嗎？系統(tǒng)態(tài)和用戶態(tài)系統(tǒng)空間和用戶空間系統(tǒng)調用和普通調用的區(qū)別？系統(tǒng)調用會引起從用戶態(tài)進入核心態(tài)2.2進程控制2.2.1進程的創(chuàng)建一、進程圖：描述了進程的家族關系：（P34圖2-9）子進程可繼承父的資源，撤消時應歸還給父進程，父的撤消會撤消全部子進程。二、引起創(chuàng)建進程的事件：1.用戶登錄：為終端用戶建立一進程2.作業(yè)調度：（不是進程調度）為被調度的作業(yè)建立進程3.提供服務：如要打印時建立打印進程2.2.1進程的創(chuàng)建(2)4.應用請求：由應用程序建立多個進程三、進程的創(chuàng)建：（creat原語）1.申請空白PCB（一個系統(tǒng)的PCB是有限的）2.為新進程分配資源（不同于一般的分配，PCB-LIST在一個特殊區(qū)域）3.初始化PCB4.將新進程插入就緒隊列。2.2.2進程的終止一、引起進程終止的事件1.正常結束：如Halt、logoff2.異常結束：如Protecterror、overtime等3.外界干預：a.系統(tǒng)員kill進程；b.父進程終止；c.父進程請求。2.2.2進程的終止(2)二、進程的終止過程（1）檢查進程狀態(tài)；（2）執(zhí)行態(tài)――>中止，且置調度標志為真。（3）有無子孫需終止。（4）歸還資源給其父進程或系統(tǒng)。（5）從PCB隊列中移出PCB.2.2.3進程的阻塞與喚醒一、引起進程阻塞和喚醒的事件1.請求系統(tǒng)服務而得不到滿足時，如問系統(tǒng)請求打印。2.啟動某種操作而需同步時：如該操作和請求該操作的進程需同步運行（即非異步操作）。3.新數(shù)據(jù)尚未到達：如進程A寫，進程B讀，則A未寫，完B不能讀。4.無新工作可做。2.2.3進程的阻塞與喚醒(2)二、進程阻塞過程：是進程自身的一種主動行為a.調block原語b.停止執(zhí)行，修改PCB入阻塞隊列（一個或多個），并轉調度。三、喚醒過程其它相關進程完成。a.wakeup原語b.修改PCB，入就緒隊列可見，有block原語，在其它進程中就應有wakeup原語。2.2.4進程的掛起與激活一、進程的掛起過程由進程自己或其父進程調suspend原語完成，將該進程PCB移到指定區(qū)域，注意狀態(tài)的改變，有可能要重新調度。二、進程的激活過程。active原語（如在外存，調入內存，改變狀態(tài)，根據(jù)情況看是否調度，如搶先或非搶先）。阻塞、喚醒一般由OS實現(xiàn)，而掛起與激活可由用戶干預。2.3進程同步同步：并發(fā)進程在執(zhí)行次序上的協(xié)調，以達到有效的資源共享和相互合作，使程序執(zhí)行有可再現(xiàn)性。2.3.1進程同步的基本概念1.兩種形式的制約關系資源共享關系：（進程間接制約）需互斥地訪問臨界資源。相互合作關系：（進程直接制約）2.臨界資源：（一次僅允許一個進程訪問的資源）引起不可再現(xiàn)性是因為臨界資源沒有互斥訪問。生產(chǎn)者－消費者問題Varn,integer;Typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;生產(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;生產(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)定義：進程訪問臨界資源的那段代碼。訪問臨界資源的描述：進入?yún)^(qū)：檢查有無進程進入臨界區(qū)：退出區(qū)：將訪問標志復位Repeat Entrysection Criticalsection Exitsection Untilfalse3.臨界區(qū)4.同步機制應遵循的準則1.空閑讓進2.忙則等待3.有限等待：應保證為有限等待，不會產(chǎn)生死等。4.讓權等待：不能進入臨界區(qū)的執(zhí)行進程應放棄CPU執(zhí)行權。2.3.2信號量機制1整型信號量是一個整型量，通過2個原子操作wait(s)和signal(s)來訪問。Wait(s):whiles<=0dono-op s:=s-1;Signal(s): s:=s+1;2記錄型信號量由于整型機制中會不斷測試不滿足“讓權等待”而引入typesemaphore=recordvalue:integer;L:listofprocess;endL:為進程鏈表，用于鏈接所有等待該類資源進程。procedurewait(s)vars:semaphorebegins.value:=s.value–1;ifs.value<0themblock(S,L)end2記錄型信號量(2)proceduresignal(S)vars: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ù)目。3AND型信號量當不用它時，有可能發(fā)生系統(tǒng)死鎖。死鎖：在無外力作用下的一種僵持狀態(tài)。AND信號量例：P42.特點：要么全分配，要么一個也不分配。3AND型信號量processA:wait(Dmutex);wait(Emutex);processB:wait(Emutex);wait(Dmutex);若2進程交替執(zhí)行，則死鎖3AND型信號量Swait(s1,s2,…,sn) ifs1≥1and…andsn≥1then fori:=1tondosi:=si-1;endfor else placetheprocessinthewaitingqueuewiththefirstsifoundwithsi<1,andsettheprogramcountofthisprocesstothebeginningofswaitoperation endifSsignal(s1,s2,…,sn) fori:=1tondosi:=si+1;removealltheprocesswaitinginthequeueassociatedwithsiintothereadyqueueendfor4信號量集(略)為提高效率而對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時，不能進入。2.3.3信號量的應用1.利用信號量實現(xiàn)互斥varmutex:semaphore:=1 begin parbegin process1:begin repeat

wait(mutex); criticalsetion

signal(mutex); remaindersection untilfalse; end1.利用信號量實現(xiàn)互斥(2)process2:begin repeat

wait(mutex); criticalsetion

signal(mutex); remaindersection untilfalse; endparend

2.利用信號量來描述前趨關系(1)S1S2S3S4S5S6abcdegf圖2－10前趨圖舉例利用信號量來描述前趨關系(2)Vara,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; parendend2.4經(jīng)典進程同步問題2.4.1生產(chǎn)者－－消費者問題2.4.2哲學家進餐問題2.4.3讀者－－寫者問題一、利用記錄型信號量解決生產(chǎn)者一消費者問題mutex：使諸進程互斥地訪問緩沖區(qū)（n個緩沖區(qū)）empty、full：空、滿緩沖區(qū)數(shù)量。Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem; in,out:integer:=0,0; begin parbeginproducer:begin repeat … Produceaniteminnextp; …一、利用記錄型信號量解決生產(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;endparendend二、利用AND信號量解決生產(chǎn)者——消費者問題varmutex,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;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;endparendend2.4.2哲學家進餐問題1.利用記錄型信號量解決哲學家進餐問題Varchopstick:array[0,…,4]ofsemaphore;Repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);…eat…signal(chopstick[i]);signal(chopstick[(i+1)mod5]);…think;Untilfalse2.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]);Untilfalse2.4.3讀者——寫者問題特點： 讀進程可共享同一對象。寫進程不可共享同一對象。一、利用記錄型信號量解決讀者——寫者問題varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0; begin parbegin reader:begin repeat wait(rmutex); ifreadcount=0thenwait(wmutex); readcount:=readcount+1; signal(rmutex); … performreadoperation一、利用記錄型信號量解決讀者——寫者問題 performreadoperation … wait(rmutex); readcount:=readcount-1; ifreadcount=0thensignal(wmutex); signal(rmutex); untilfalse; end

一、利用記錄型信號量解決讀者——寫者問題 writer:begin repeat wait(wmutex) performwriteoperation; signal(wmutex) untilfalse; endparendend二、信號量集解決讀者——寫者問題(略)varRNinteger; L,mx:semaphore:=RN,q;beginparbeginreader:begin repeatswait(L,1,1);swait(mx,1,0);… performreadoperation; … ssignal(L,1);untilfalse;endwriter:begin

二、信號量集解決讀者——寫者問題（略）writer:beginrepeatswait(mx,1,1;L,RN,0);performwriteoperation;ssignal(mx,1);untilflase;endparendend

2.5管程機制引入原因：為了避免凡要使用臨界資源的進程都自備同步操作wait(s)和signal(s).將同步操作的機制和臨界資源結合到一起，形成管程。2.5.1管程的基本概念一、定義：一個數(shù)據(jù)結構和能為并發(fā)進程所執(zhí)行的一組操作。局部于管程的共享變量。對該數(shù)據(jù)結構進程操作的一組過程。對局部管程數(shù)據(jù)設置初值。二、條件變量： x.y:x.wait;x.signal;x.queue2.5.2利用管程解決生產(chǎn)者——消費者問題一、建立管程：PC包括：二過程： （1）put(item)過程；（2）get(item)過程一變量：count≥n時滿；≤0時空初始：in=out=count=0Typeproducer-consumer=monitorvarin,out,count：integer;buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)procedureentryget(item)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:=0end2.5.2利用管程解決生產(chǎn)者——消費者問題例：producer:begin repeat produceaitemnextp PC.put(item); untilfalse. EndConsumer:begin repeat PC.get(item); Consumetheiteminnextc; Untilfalse end 可見，由管程來實現(xiàn)后，進程的同步更簡單明了。練習a,b兩點間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：當ab間有車輛在行駛時同方向的車可以同時駛入ab段，但另一方向的車必須在ab段外等待；當ab之間無車時，到達a（或b）的車輛可以進入ab段，但不能從a，b點同時駛入；當某方向在ab段行駛的車輛使出了ab段且無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。請用wait,signal工具對ab段實現(xiàn)正確管理。答：Semaphores,mutexab,mutexbaPab：Wait(mutexab)Countab++Ifcountab=1thenwait(s);Signal(mutexab)

…..wait(mutexab)countab--;ifcountab=0thensignal(s)signal(mutexab);答：Pba:wait(mutexba)countba=countba+1;Ifcountba=1thenwait(s)wait(mutexba)enter; ……wait(mutexba)countba--;ifcountba=0thensignal(s) signal(mutexba);2.6進程通信概念：進程間的信息交換。實例：信號量機制（一種低級通信） 缺點：（1）效率低 （2）通信對用戶不透明高級通信特點：效率高，通信實現(xiàn)細節(jié)對用戶透明2.6.1進程通信的類型一、共享存貯器系統(tǒng)1.基于共享數(shù)據(jù)結構的通信方式：produce-consume中的緩沖區(qū)，低效，不透明。系統(tǒng)只提供了一共享存貯器，適于少量通信。2.基于共享存儲區(qū)的通信方式：系統(tǒng)提供：共享存儲區(qū)。通信過程：（1）向系統(tǒng)申請一個或多個分區(qū)（2）獲得分區(qū)獲后即可讀/寫.特點：高效，速度快。2.6.1進程通信的類型二、消息傳遞系統(tǒng)（可用于異種機）信息單位：消息（報文）是目前的主要通信方式，分為直接通信方式、間接通信方式實現(xiàn)：一組通信命令（原語），具有透明性--->同步的實現(xiàn)。三、管道通信管道：連接一個讀進程和一個寫進程之間通信的共享文件。功能：大量的數(shù)據(jù)發(fā)收。注意：（1）互斥（2）同步（3）對方是否存在2.6.2直接/間接通信方式（消息通信的2種方式）一、直接send(Receiver,message)receive(Sender,message)例：解決生產(chǎn)—消費問題。 repeat …produceaniteminnextp;…send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);…consumertheiteminnextc;untilfalse;2.6.2直接/間接通信方式（消息通信的2種方式）二、間接（可以實現(xiàn)非實時通信）優(yōu)點：在讀/寫時間上的隨機性寫進程――>信箱（中間實體）――>讀進程原語（1）信息的創(chuàng)建與撤消：信箱名屬性（公用、私用、共享）（共享者名字）（2）消息的發(fā)送和接收Send(mailbox,message)Receive(mailbox,message)2.6.2直接/間接通信方式（消息通信的2種方式）二、間接（可以實現(xiàn)非實時通信）信箱類型（1）私用：擁有者有讀/寫數(shù)，其它只有寫權，（單向）存在期＝進程存在期。（2）公用：系統(tǒng)創(chuàng)建，雙向，存在期=系統(tǒng)存在期。（3）共享信箱：一般進程創(chuàng)建，并指明其共享者，是雙向。發(fā)送—接收進程之間的關系：（1）一對一關系；（2）多對一關系；（3）一對多關系；（4）多對多關系：公用信箱。2.6.3消息傳遞系統(tǒng)中的幾個問題一、通信鏈路：（1）顯式建立：（進程完成）（2）隱式建立：（系統(tǒng)完成）鏈路類型：（1）由連接方法分：點—點鏈路，多點鏈路。（2）由通信方式分：單向、雙向。（3）由容量分：無容量（無緩沖區(qū)）、有（有緩沖區(qū)）。2.6.3消息傳遞系統(tǒng)中的幾個問題二、消息格式：消息頭：含控制信息如：收/發(fā)進程名，消息長度、類型、編號消息內容：定長消息：系統(tǒng)開銷小，用戶不便（特別是傳長消息用戶）變長消息：開銷大，用戶方便。2.6.3消息傳遞系統(tǒng)中的幾個問題三、進程同步方式1.發(fā)送和接收進程阻塞（匯合）用于緊密同步，無緩沖區(qū)時。2.發(fā)送進程不阻塞，接收進程阻塞（多個）相當于接收進程（可能是多個）一直等待發(fā)送進程，如：打印進程等待打印任務。3.發(fā)送/接收進程均不阻塞一般在發(fā)、收進程間有多個緩沖區(qū)時。2.6.4消息緩沖隊列通信機制一、數(shù)據(jù)結構1.消息緩沖區(qū)typemessagebuffer=recordsender:size:text:next:指向下一指針2.PCB中應增數(shù)據(jù)項：typepcb=recordmq 消息隊列指針mutex消息隊列互斥信息量sm 消息隊列資源信息量（表資源消息數(shù)）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);end2.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; end2.6.4消息緩沖隊列通信