第3章進程管理

3.1進程的引入

3.2進程的結構

3.3進程控制

3.4進程的同步與互斥

3.5進程間通信

3.6進程調度

3.7死鎖

3.8線程1兩種制約關系直接相互制約關系（同步）

間接相互制約關系（互斥）產生的原因進程合作資源共享

2進程的同步（1）直接相互制約關系（同步）指系統中一些進程需要相互合作，共同完成一項任務,這種協作進程之間相互等待對方消息或信號的協調關系稱為進程同步.具體說，并發進程在一些關鍵點上可能需要互相等待與互通消息，進程間的相互聯系是有意識的安排的。產生的原因進程合作3進程的同步（2）一般同步問題有兩類保證一組合作進程按邏輯需要的執行次序執行

【例】司機P1

售票員P2

REPEATREPEAT

啟動關門

正常運行售票

到站停開門

UNTILFALSEUNTILFALSE保證共享緩沖區（共享數據）的合作進程的同步

【例】輸入進程PI緩沖區緩沖區計算進程PC打印進程PP4進程的互斥是解決進程間競爭關系(間接制約關系)的手段。間接相互制約關系（互斥）

是指若干個進程同時競爭一個需要互斥使用的資源時，任何時刻最多允許一個進程去使用，其他要使用該資源的進程必須等待，直到該資源被釋放。進程間要通過某種中介發生聯系，是無意識安排的。產生的原因資源共享互斥是一種特殊的同步逐次使用互斥資源，也是對進程使用資源次序上的一種協調。5臨界資源臨界資源

系統中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。硬件臨界資源：打印機、磁帶機軟件臨界資源：只能排它使用的變量、表格、隊列6臨界資源實例二人合作存款

count=100;PAS1:N=count;S2:N=N+100;S3:count=N;PBS4:M=count;S5:M=M+200;S6:count=M;執行情況：（1）PA—>PB,PB—>PAcount=400

√

（2）S1—>PB—>S2—>S3count=200

×（3）S4—>PA—>S5—>S6count=300

×因count是一個互斥性使用的變量，是一個臨界資源7臨界區臨界區（臨界段）在進程中訪問臨界資源的那段代碼區。例子8具有臨界資源的進程結構

……/*進入區*/criticalsection;/*臨界區*//*退出區*/remaindersection;/*剩余區*/……entrysectionexitsection9訪問臨界區應遵循的原則空閑讓進

當無進程在臨界區時，任何有權使用臨界區的進程可進入。忙則等待

不允許兩個以上的進程同時進入臨界區。有限等待

任何進入臨界區的要求應在有限的時間內得到滿足。讓權等待

不能進入臨界區的進程應放棄占用CPU。10臨界區互斥解決方法軟件用編程解決缺點：

(1)忙等待

(2)實現過于復雜，需要高的編程技巧硬件專用機器指令方法屏蔽中斷方法缺點：忙等待信號量機制11硬件解法（1）測試與設置指令int

TS(intlock){TS=lock;lock=1;}測試與設置指令的使用

intlock=0;M/*進入臨界區前執行*/whileTS(lock)doskip;

臨界區

/*離開臨界區后執行*/

lock:=0;M12硬件解法（2）交換指令Swap(intlock,intkey){

inttemp;temp=lock;lock=key;key=temp}交換指令的應用intlock=0;每個進程定義一個局部變量intkey;進入臨界區前執行：

key=1;

do

swap(lock,key)whilekey=0;離開臨界區后執行：lock=0;13硬件解法（3）

進入臨界區前執行：執行“關中斷”指令

離開臨界區后執行：執行“開中斷”指令14信號量機制一類資源抽象成S（信號量）信號量只能由P、V操作對其進行操作的變量。信號量的使用應注意必須置一次且只能置一次初值初值只能為非負整數只能執行P、V操作15整型信號量整型信號量信號量S：整型量，除初始化外僅能通過P、V操作訪問P和V操作原語定義：

intS;S=1;

P(S)：whileS≤0dono-opS=S-1；

V(S)：S=S+1；S（信號量）一類資源抽象成整型量16記錄型信號量記錄型信號量信號量S：記錄型數據結構,一個分量為整型量value,另一個分量為信號量隊列L；一類資源抽象成S（信號量）value0L=nil17信號量的物理含義

S.value>0:表示有S.value個資源可用

S.value=0:表示無資源可用

S.value<0:則|S.value|表示等待隊列中的進程個數

信號量的初值應該大于等于0信號量的值(-2)信號量隊列指針18structsemaphore{

intvalue;

int*L;}voidP(structsemaphoreS);{S.value=S.value–1;/*把信號量減去1*/

ifS.value<0thenblock(S.L);/*若信號量小于0，則調用P(S)的進程被置成等待信號量S的狀態*/}物理意義：申請一個資源，如果申請成功，則返回；如果申請不成功，則掛在該資源的等待隊列上。voidV(structsemaphoreS);{S.value=S.value+1; /*把信號量加1*/ifS.value<=0thenwakeup(S.L);/*若信號量小于等于0，則釋放一個等待信號量s的進程*/}物理意義：歸還一個資源，如果沒有進程等待該資源，則返回；如果有進程在等待，把等待的進程從L上移到就緒隊列。記錄型信號量描述19P、V操作討論

P(S)：表示申請一個資源

V(S)：表示釋放一個資源。

P、V操作必須成對出現，有一個P操作就一定有一個V操作P、V操作的優點

簡單，而且表達能力強，可解決任何互斥問題P、V操作的缺點

不夠安全，P、V操作使用不當會出現死鎖，遇到復雜互斥問題時，實現復雜。20用P、V操作實現互斥信號量初值為1對于兩個并發進程，互斥信號量的值僅取1、0和-1三個值：若mutex.value＝1表示沒有進程進入臨界區若mutex.value＝0表示有一個進程進入臨界區若mutex.value

＝-1表示一個進程進入臨界區，另一個進程等待進入。對于n個并發進程，互斥信號量的取值范圍是？

-(n-1)～121利用記錄型信號量實現進程互斥P(mutex)V(mutex)P1P2互斥區P(mutex)V(mutex)22利用P、V操作實現兩個進程互斥的模板如下：

structsemaphoremutex;

mutex.value=1;mutex.L=nil;

{

cobegin

ProcessP1:{

M

P(mutex);

臨界區1

V(mutex);

M

}ProcessP2:{

M

P(mutex);

臨界區2

V(mutex);

M

}

coend}

23使用PV操作實現互斥應注意識別臨界資源是否被共享;是否有排它性使用要求。臨界區代碼應盡量短小，不能有死循環。P和V原語應分別緊靠臨界區的頭尾。P、V操作在同一進程中必須成對出現。24思考題

用記錄型信號量解決二人存款問題，用類C語言編寫進程互斥算法。25用P、V操作實現進程的同步只要信號量初值是一個大于等于0的整數就能達到同步的目的，就可以直接使用P、V操作實現同步互斥是一種特殊的同步P、V操作既可以實現互斥，也可以實現同步26利用信號量實現進程同步的實例設有三個并發執行的進程P1、P2、P3，其前趨圖如下，試用信號量實現這三個進程同步。設兩個同步信號量S1、S2分別表示進程P2、P3能否開始執行structsemaphoreS1,S2=0,0;/*初值均為0*/{

cobeginP1:{V(S1);

V(S2);}P2:{P(S1);

;}P3:{P(S2);;}

coend}

P1P3P227使用PV操作實現同步應注意信號量的設置信號量的初值

PV操作要成對出現，并在不同的進程中28信號量及P、V操作討論(1)

P、V操作必須成對出現，有一個P操作就一定有一

個V操作(2)當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(3)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關重要。一個同步P操作與一個互斥P操作在一起時，同步

P操作在互斥P操作前，而兩個V操作無關緊要。29PV操作實現互斥與同步的模板進程互斥

S初值為1

P1

P2

P(S)P(S)

臨界區1臨界區2V(S)V(S)在P1與P2中設置相同的P、V操作進程同步

S1初值為n，S2初值為0

P1

P2

P(S1)

P(S2)

段1段2

V(S2)

V(S1)30經典的進程同步問題生產者/消費者問題讀者/寫者問題哲學家進餐問題31生產者/消費者問題

生產者消費者問題是一種同步問題的抽象描述。計算機系統中的每個進程都可以消費（使用）或生產（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當某一進程使用某一資源時，可以看作是消費，稱該進程為消費者。而當某一進程釋放某一資源時，它就相當于生產者。32生產者/消費者問題(描述)

通過一個公用緩沖池可以把一群生產者p1,p2…,pm，和一群消費者Q1,Q2,…,Qn聯系起來。如圖:只要緩沖區未滿，生產者就可以把產品送入緩沖區;只要緩沖區未空，消費者就可以從緩沖區中取走物品。33生產者/消費者問題(圖示)3435生產者/消費者必須互斥36生產者/消費者必須同步37生產者/消費者問題(分析)為解決生產者消費者問題，應該設兩個同步信號量，一個說明空緩沖區的數目，用empty表示，初值為緩沖池的大小N，另一個說明已用緩沖區的數目，用full表示，初值為０。由于在此問題中有i個生產者和j個消費者，它們在執行生產活動和消費活動中要對緩沖池進行操作。由于緩沖池是一個臨界資源，必須互斥使用，所以，另外還需要設置一個互斥信號量mutex，其初值為１。struct

semaphoneempty=n,full=0,mutex=1;voidbuffer[n-1];

intin=0,out=0;38生產者/消費者問題(解決)Consumerj:while(1){

P(full);

P(mutex);

從Buffer[out]取產品;out=(out+1)modn;

V(mutex);

V(empty);

消費產品;}coend;cobegin

procedurei:while(1){

生產產品;

P(empty);

P(mutex);

往Buffer[in]放產品;in=(in+1)modn;

V(mutex);

V(full);

}39生產者/消費者問題(思考)在生產者進程和消費者進程中，兩個P操作的執行順序是否能交換？兩個V操作的執行順序是否能交換？40思考題

兩個進程合作完成數據計算和打印工作，計算進程未計算完就不可打印，反之也然，雙方共用一個緩沖區，寫出此算法。緩沖區計算進程PC打印進程PP41讀者/寫者問題有兩組并發進程:

讀者和寫者,共享一個數據文件

要求：允許多個讀者同時執行讀操作不允許讀者、寫者同時操作不允許多個寫者同時操作42讀者/寫者問題

如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者、寫者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待43讀者寫者問題的解法為實現讀者和寫者、寫者和寫者之間的互斥，設置一個互斥信號量Wmutex=1由于“讀—讀”允許，再設置一個整型變量Readcount表示正在讀的進程數，初值Readcount=0由于Readcount是一個可被多個讀者進程訪問的臨界資源，所以要為它設置一個互斥信號量Rmutex=1讀者—寫者算法如下：讀者：{

P(Rmutex);

ifreadcount=0then

P(Wmutex);

Readcount=Readcount+1;

V(Rmutex);

讀

P(Rmutex);

Readcount=Readcount-1;ifReadcount=0then

V(Wmutex);

V(Rmutex);}寫者：

{

P(Wmutex);

寫

V(Wmutex);}44哲學家就餐問題有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個哲學家的行為是思考，感到饑餓，取筷子，然后吃通心粉，放筷子，思考。為了吃通心粉，每個哲學家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子筷子是臨界資源，要用5個互斥信號量來表示這5只筷子。45哲學家就餐問題解設fork[5]為5個信號量，初值均為1struct

semaphore

fork[4];fork[i]:=1;Philosopheri：While(1){

思考；

P(fork[i]);P(fork[(i+1)mod5])；

進食；

V(fork[i]);V(fork[(i+1)mod5])；}

以上解法會出現死鎖,為防止死鎖發生可采