操作系統(tǒng)第3章-3

1第三章、進程管理

3.1 進程的概念3.2 進程的描述3.3 進程狀態(tài)及其轉(zhuǎn)換3.4 進程控制3.5 進程互斥3.6 進程同步3.7 進程通信3.8 死鎖問題3.9 線程23.7 進程通信一、進程通信：

進程之間的信息交換、數(shù)據(jù)傳送。

低級通信：少量控制信息的交換，一個/幾個字節(jié)。

高級通信：高效、大量地傳送數(shù)據(jù)，交換信息。二、進程通信方式：1、主從式：（終端控制進程與終端進程）

1）主進程可自由使用從進程的資源和數(shù)據(jù)；

2）從進程動作受主進程控制；

3）主、從進程的關(guān)系固定。2、會話式：（用戶進程與磁盤管理進程）

1）使用進程要得到服務(wù)進程的許可；

2）服務(wù)進程自控地完成對使用進程的服務(wù)；

3）通信時二者有固定的連接關(guān)系。33、共享存儲區(qū)方式：（UNIXSystemV)

在存儲區(qū)中劃出一塊共享存儲區(qū)，兩個進程通過對申請的共享存儲區(qū)讀、寫實現(xiàn)通信。4、消息或郵箱機制：

1）發(fā)送進程和接收進程之間有用于存放傳送消息的緩沖區(qū)或郵箱；

2）發(fā)送進程向空緩沖區(qū)或郵箱發(fā)送信息，接收進程從滿緩沖區(qū)或郵箱接收信息；

3）發(fā)送進程和接收進程之間沒有直接固定的聯(lián)系。4三、消息緩沖機制：（直接通信方式，多對一）消息緩沖區(qū)： 進程通信的基本單位，記錄消息的內(nèi)容等信息，為多個進程共享，其數(shù)據(jù)結(jié)構(gòu)描述為：

TYPEmessagebuffer=record

sender_ptr; 指向發(fā)送進程的指針

size; 消息長度

text; 消息正文

next_ptr; 指向下一個消息緩沖區(qū)的指針

end56公用信號量mutex：對消息緩沖區(qū)的的訪問采取互斥措施;

私有信號量Sm：消息緩沖區(qū)無消息時，接收進程不能接收，同步措施。發(fā)送進程：Send(k,m)begin

向系統(tǒng)申請一個消息緩沖區(qū)

將發(fā)送消息m送到新消息緩沖區(qū) 把緩沖區(qū)鏈入接收進程k的消息隊列

end接收進程：Receive(n)begin

摘下消息隊列中消息n

把n復(fù)制到接收區(qū) 釋放消息緩沖區(qū)

end

P(mutex)

V(mutex) V(Sm)

P(Sm) P(mutex)

V(mutex)7四、郵箱通信：（間接通信方式，靈活）郵箱：發(fā)送進程和接收進程之間設(shè)置的大小固定的私有數(shù)據(jù)結(jié)構(gòu)（多個消息組成的隊列），由接收進程所擁有。工作條件：發(fā)送至少有一個空格，接收時至少有一個滿格。特點：發(fā)送、接收基本無時間限制。缺點：占用大量內(nèi)存，接口多，效率低。（公用信箱）8同步措施：設(shè)置一對私有信號量，記錄郵箱中空格滿格的數(shù)量Deposit(m)beginlocalx

選擇郵箱的一個空格x

把消息m放入空格x

置格x為滿標(biāo)志

end

Remove(m)beginlocalx

選擇郵箱的一個滿格x

取走消息m

置格x為空標(biāo)志

endP(formnum)V(mesnum)P(mesnum)V(formnum)9實例1：管道P66

以比特流方式傳送消息的通信管道，由文件系統(tǒng)的高速緩沖區(qū)構(gòu)成。10例：創(chuàng)建管道，父子進程通過管道傳遞數(shù)據(jù)。#include<stdio.h>main(){intx,fd[2];charbuf[30],s[30];

pipe(fd);while((x=fork())==-1);if(x==0){sprintf(buf,"thisisanexample!");

write(fd[1],buf,30);

exit(0);}else{wait(0);

read(fd[0],s,30);printf("result:%s",s);}}11實例2：書例P1541、接收消息程序client.c2、發(fā)送消息程序server.c3、在msg.c中，創(chuàng)建三個子進程：其中兩個調(diào)用client.c

另一個調(diào)用server.c

相互之間發(fā)送消息12接收消息程序client.c#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>#defineMSGKEY75structmsgform{longmtype;charmtext[256];};main(intargc,char*argv[]){structmsgformmsg;intmsgqid,pid,*pint;

msgqid=msgget(MSGKEY,0777|IPC_CREAT);printf("msgqid=%d\n\n",msgqid);pid=getpid();pint=(int*)msg.mtext;*pint=pid;msg.mtype=1;

msgsnd(msgqid,&msg,sizeof(int),0);

msgrcv(msgqid,(structmsgform)&msg,sizeof(msg),pid,0);pint=(int*)msg.mtext;pid=(int)*pint;printf("Client%s:receivefromServerprocess%d\n",argv[1],pid);}13發(fā)送消息程序server.c--1#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>#defineMSGKEY75structmsgform{longmtype;charmtext[256];};intmsgqid;main(){structmsgformmsg;inti,*pint;intpid;externcleanup();for(i=0;i<20;i++)signal(i,cleanup);

msgqid=msgget(MSGKEY,0777|IPC_CREAT);printf("msgqid=%d\n\n",msgqid);

14發(fā)送消息程序server.c--2for(;;){msgrcv(msgqid,(structmsgform*)&msg,256,1,0);pint=(int*)msg.mtext;pid=(int)*pint;printf("Server:receivefromClientprocess%d\n\n",pid);msg.mtype=pid;pint=(int*)msg.mtext;*pint=getpid();

msgsnd(msgqid,&msg,sizeof(int),0);}cleanup(){msgctl(msgqid,IPC_RMID,0);exit();}15msg.c#include<sys/types.h>#include<stdio.h>#include<unistd.h>main(){intpid1,pid2,pid3;pid1=vfork();if(pid1==0)/*子進程2001*/

{printf("\nClient1process%4d:\n",getpid());execlp("/…/client","client","1",NULL);}else{pid2=vfork();if(pid2==0)/*子進程2002*/

{printf("Client2process%4d:\n",getpid());execlp("/…/client","client","2",NULL);}

else{pid3=vfork();if(pid3==0)/*子進程2000*/

{printf("Server3process%4d:\n",getpid());

execlp("/…/server","server",NULL);

}

else

{printf("\nThisisParentprocess%4d!\n",

getpid());

}

}

}

wait(0);

wait(0);

wait(0);

}16子進程2001子進程2002子進程2000TYPE：1TEXT：2001TYPE：1TEXT：2002TYPE：

2001TEXT：

2000TYPE：

2002TEXT：

2000消息隊列書例P16317實例3：和控制臺的通信i18①用戶進程PiCCP的接口用戶進程發(fā)出問題：P_write(m)Begin

P(rq)

把m插入RQ隊列

V(rq)

V(question)EndCCP接收問題：U_receive(m)Begin

P(question)

P(rq)

把m從RQ隊列取出

V(rq)End19②

CCP與DCP的接口CCP向outbuf送問題：

outbuf_empty=1Write(y)Begin

P(outbuf_empty) copy(outbuffromy)

V(outbuf_full)EndDCP從outbuf中接收：

outbuf_full=0Receive(k)Begin

P(outbuf_full) copy(outbuftok)

V(outbuf_empty)End20③

DCP與顯示器的通信顯示器控制進程DCP：

D_busy=1初始化{清除outbuf，echo=false}Beginif(outbuf滿)then

receive(k)

P(D_busy)

把k送入顯示器數(shù)據(jù)緩沖區(qū)

V(D_ready)else echo=true

echobuf中字符置入顯示器緩沖區(qū)fiEnd顯示器動作DP：

D_ready=0Repeat if(echo=true)then

打印顯示器緩沖區(qū)中字符

else

P(D_ready)

打印顯示器緩沖區(qū)中消息

V(D_busy)Until(顯示器關(guān)機)21④

KCP與鍵盤的通信鍵盤控制進程KCP：

T_busy=1初始化{清除inbuf、echobuf}Begin

P(T_ready)

從鍵盤數(shù)據(jù)緩沖區(qū)x中取出字符x.m

Send(x.m)

將x.m送入echobuf

V(T_busy)End鍵盤動作KP：

T_ready=0Repeat

P(T_busy)

把鍵入字符送入鍵盤數(shù)據(jù)緩沖區(qū)x

V(T_ready)Until(終端關(guān)閉)22⑤

CCP與KCP的接口KCP向inbuf送回答：

inbuf_empty=1Send(k)Begin

P(inbuf_empty) copy(inbuffromk)

V(inbuf_full)EndCCP從inbuf中接收回答：

inbuf_full=0Read(x)Begin

P(inbuf_full) copy(inbuftox)V(inbuf_empty)End23⑥

CCP用戶進程Pi的接口CCP發(fā)出回答：S_answer(a,i)Begin

P(sqi)

把a插入SQi隊列

V(sqi)

V(answeri)End用戶進程接收回答：P_read(a)Begin

P(answeri)

P(sqi)

把a從SQi隊列取出

V(sqi)

End24會話控制進程CCP的動作描述Localk,m,xRepeat

U_receive(m)

將消息m的進程標(biāo)號置入k中 將消息m解碼變換到x

write(x)

read(x)

將x編碼到m

S_answer(m,k)Until（CCP結(jié)束）253.8 死鎖問題一、死鎖的定義

指多個進程因競爭資源而造成的僵局，即各自等待對方的資源，而在得到對方資源前又不會釋放自己擁有的資源，在無外力作用下，各進程將永遠(yuǎn)不能向前推進。26二、死鎖的起因1、資源競爭： 可剝奪性資源（CPU、內(nèi)存） 非剝奪性資源（打印機）：分配后不能強行收回。272、進程推進順序非法：合法非法28三、產(chǎn)生死鎖的必要條件：1、互斥條件：2、不剝奪條件：3、部分分配條件（請求和保持）：4、環(huán)路條件： 防止死鎖發(fā)生，破壞四個必要條件中的一個或多個即可（主要是第3、4個，第1、2條受資源特性的限制）。29四、死鎖的排除方式1、死鎖的預(yù)防2、死鎖的避免3、死鎖的檢測和恢復(fù)301、死鎖的預(yù)防——破壞四個必要條件中的一個或多個2）有序資源使用法——打破“環(huán)路條件”

內(nèi)容：把資源編號排序，要求進程必須按編號遞增的順序申請資源：

m個資源，R1<R2<…<Rm，進程P1保持了Ri，只能申請Rj，（j>i）;

原理：總有一個進程占據(jù)較高序號的資源，其后申請的資源必空閑，從而滿足需要一直往前推進，再釋放已用資源。

編號原則：常用資源低序號，不常用資源高序號；

缺點：序號順序相對穩(wěn)定限制新設(shè)備；當(dāng)一個進程的資源使用順序和編號順序不一致時，資源閑置浪費；限制用戶的編程自由。1）預(yù)先靜態(tài)分配法——打破“部分分配條件”

內(nèi)容：進程一次性申請和分配全部所需資源，未全部滿足則等待。

缺點：資源嚴(yán)重浪費；進程延遲運行。312、死鎖的避免思路：在動態(tài)分配資源的過程中預(yù)測出發(fā)生死鎖的可能性，加以避免。判斷此次分配是否會導(dǎo)致系統(tǒng)進入“不安全狀態(tài)”？安全狀態(tài)：系統(tǒng)至少存在一個安全序列不會發(fā)生死鎖。例：進程需求量已分配空閑資源A1053B42C92

把空閑的3個中的2個分給B

把空閑的3個中的2個分給C安全的分配：不安全分配：32銀行家算法基本模式： 將進程分為若干步，每一步使用的資源固定，當(dāng)進程每一步申請資源時，將請求、分配、釋放、空閑的情況結(jié)合起來計算，看是否符合分配條件。數(shù)據(jù)結(jié)構(gòu)：

n個并發(fā)進程P1…Pn共享m個資源R1…Rm： 可用資源向量Available[m]:Available[j]—資源Ri現(xiàn)有的空閑個數(shù) 最大需求矩陣Max[n*m]:Max[i,j]—進程Pi對資源Rj的最大需要數(shù) 分配矩陣Allocation[n*m]:Allocation[i,j]—進程Pi已獲得資源Rj的數(shù)量 需求矩陣Need[n*m]:Need[i,j]—進程Pi還需要資源Rj的數(shù)量

Need[i，j]=Max[i，j]-Allocation[i，j]333435例：五個進程共享三類資源A、B、C，每類資源數(shù)量為10、5、7。時刻T0的資源分配情況如下：MaxAllocationNeedAvaillableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P44330024311057-725 = 33236

對T0時刻進行安全性分析后，可以找到一個安全序列{P1，P3，P4，P2，P0}，則系統(tǒng)安全。T0WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057true37P1發(fā)出請求Req(1,0,2）

<=Need(1,2,2）及Availlable(3,3,2）

為P1試探分配，修改Availlable、Allocation、Need

T1時刻進行安全性分析，找到安全序列{P1，P3，P4，P0，P2}說明系統(tǒng)安全，可以為P1實施分配T1WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057trueT033212220038P4發(fā)出請求Req(3，3，0）：

Req(3，3，0）<=Need(4，3，1)

Req(3，3，0）>Availlable(2，3，0)，不能分配，等待。

P0發(fā)出請求Req(0，2，0）：

Req(0，2，0）<=Need(7，4，3)

Req(0，2，0）<=Availlable(2，3，0)，試探分配，修改數(shù)據(jù)：AllocationNeedAvaillableABCABCABCP0030723210P1302020P2302600P3211011P4002431無法滿足任何進程不能分配393、死鎖的檢測和恢復(fù)1）死鎖的檢測：判斷死鎖是否發(fā)生？2）死鎖的恢復(fù)： 終止各進程，或逐個終止，直至先后釋放的資源能夠滿足剩余進程的需要。403.9 線程一、線程的引入

為實現(xiàn)持續(xù)的并發(fā)執(zhí)行，引入進程，但由于各種原因，若干進程間會出現(xiàn)頻繁調(diào)度、切換，進行上下文切換的開銷花去不少CPU時間，降低并發(fā)的效率。

進程的性質(zhì)：

1、是系統(tǒng)進行資源分配和調(diào)度的基本單位—PCB。

2、是程序?qū)δ硞€數(shù)據(jù)集在處理機上的執(zhí)行過程。

把兩個特點分開，由進程負(fù)責(zé)資源的管理，由進程創(chuàng)建的若干個線程完成運行的特性，線程共享所屬進程的資源，減少線程間切換的花銷。進程上下文

進程執(zhí)行活動過程的靜態(tài)描述，是進程執(zhí)行所依賴的環(huán)境。

當(dāng)系統(tǒng)調(diào)度新進程占有處理機時，新老進程的上下文發(fā)生轉(zhuǎn)換。42二、線程的概念

進程內(nèi)的基本調(diào)度單位； 是相對獨立的執(zhí)行單元（子任務(wù)）；進程線程資源分配的基本單位。處理機調(diào)度的基本單位，與資源分配無關(guān)，多個線程共享所屬進程的資源。不同進程有不同的虛擬地址空間，有外存掛起狀態(tài)。同一進程內(nèi)的線程共享同一地址空間，無外存掛起狀態(tài)。進程存在的標(biāo)志：進程控制塊PCB上下文切換時間長線程的存在標(biāo)志：線程控制表TCB及相關(guān)堆棧和寄存器上下文切換時間短43線程控制塊TCB的內(nèi)容1、線程的狀態(tài)；2、CPU現(xiàn)場信息:

PC、PSW、通用寄存器、堆棧指針44三、線程的特點1、由進程所創(chuàng)建，一個進程至少創(chuàng)建一個線程，線程也可以創(chuàng)建線程；2、線程不擁有資源，只共享所屬進程的資源；3、同一進程下的線程運行在相同的地址空間；4、線程之間需要互斥和同步機制；5、線程有生命期，在生命期中有狀態(tài)的變化；6、類似程序，但一般不是完整的程序。45四、線程的狀態(tài)1、就緒：具備運行條件，只等CPU；2、執(zhí)行：占有CPU運行；3、阻塞：因為某事件讓出CPU，等待；46五、線程的優(yōu)點1、創(chuàng)建和撤消線程、線程切換的開銷小，提高了并發(fā)效率；一個進程的開銷大約是一個線程開銷的30倍左右.2、線程共享同一地址空間的內(nèi)存和文件，減少了通信的開銷；3、減少用戶等待時間，提高系統(tǒng)響應(yīng)速度；4、促使用戶設(shè)計出邊界清晰、模塊獨立性好的程序。47六、線程的使用范圍1、多處理機系統(tǒng)：

用戶程序根據(jù)功能劃分成不同線程，放在不同處理機上運行。2、單處理機系統(tǒng)：

1）多個用戶對文件服務(wù)器提出文件訪問請求；

2）前臺和后臺的分工處理；

3）異步處理；

4）加快執(zhí)行速度；

5）組織復(fù)雜的工作；48七、線程的分類1、用戶級線程：

用戶程序在用戶空間執(zhí)行線程庫，創(chuàng)建、調(diào)度、撤消線程，操作系統(tǒng)內(nèi)核只管理進程； 用戶級線程調(diào)度只進行線程上下文切換，不涉及處理機狀態(tài)，與內(nèi)核無關(guān)；2、系統(tǒng)級線程：

操作系統(tǒng)內(nèi)核進行管理，內(nèi)核提供系統(tǒng)調(diào)用和應(yīng)用程序接口創(chuàng)建、調(diào)度、撤消線程； 負(fù)責(zé)進程和線程的調(diào)度；49例：Linux下的多線程程序example.c#include<stdio.h>#include<pthread.h>voidthread(void)

{inti;

for(i=0;i<3;i++)

printf("Thisisapthread.\n");

}intmain(void)

{pthread_tid;

inti,ret;

ret=pthread_create(&id,NULL,(void*)thread,NULL);

if(ret!=0)

{

printf("Createpthreaderror!\n");exit(1);

}

for(i=0;i<3;i++)

printf("Thisisthemainprocess.\n");

pthread_join(id,NULL);

return(0);

}50相關(guān)函數(shù)函數(shù)pthread_create用來創(chuàng)建一個線程：

第一個參數(shù)為指向線程標(biāo)識符的指針，第二個參數(shù)用來設(shè)置線程屬性，第三個參數(shù)是線程運行函數(shù)的起始地址，最后一個參數(shù)是運行函數(shù)的參數(shù)。 創(chuàng)建線程成功后，新創(chuàng)建的線程則運行參數(shù)三和參數(shù)四確定的函數(shù)，原來的線程則繼續(xù)運行下一行代碼。函數(shù)pthread_join用來等待一個線程的結(jié)束：

第一個參數(shù)為被等待的線程標(biāo)識符，第二個參數(shù)為一個用戶定義的指針，它可以用來存儲被等待線程的返回值。 這個函數(shù)是一個線程阻塞的函數(shù)，調(diào)用它的函數(shù)將一直等待到被等待的線程結(jié)束為止，當(dāng)函數(shù)返回時，被等待線程的資源被收回。編寫運行Linux下的多線程程序，需要使用頭文