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

1第三章、進(jìn)程管理

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

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

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

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

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

2）從進(jìn)程動(dòng)作受主進(jìn)程控制；

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

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

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

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

在存儲(chǔ)區(qū)中劃出一塊共享存儲(chǔ)區(qū)，兩個(gè)進(jìn)程通過(guò)對(duì)申請(qǐng)的共享存儲(chǔ)區(qū)讀、寫(xiě)實(shí)現(xiàn)通信。4、消息或郵箱機(jī)制：

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

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

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

TYPEmessagebuffer=record

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

size; 消息長(zhǎng)度

text; 消息正文

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

end56公用信號(hào)量mutex：對(duì)消息緩沖區(qū)的的訪問(wèn)采取互斥措施;

私有信號(hào)量Sm：消息緩沖區(qū)無(wú)消息時(shí)，接收進(jìn)程不能接收，同步措施。發(fā)送進(jìn)程：Send(k,m)begin

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

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

end接收進(jìn)程：Receive(n)begin

摘下消息隊(duì)列中消息n

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

end

P(mutex)

V(mutex) V(Sm)

P(Sm) P(mutex)

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

選擇郵箱的一個(gè)空格x

把消息m放入空格x

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

end

Remove(m)beginlocalx

選擇郵箱的一個(gè)滿格x

取走消息m

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

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

以比特流方式傳送消息的通信管道，由文件系統(tǒng)的高速緩沖區(qū)構(gòu)成。10例：創(chuàng)建管道，父子進(jìn)程通過(guò)管道傳遞數(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實(shí)例2：書(shū)例P1541、接收消息程序client.c2、發(fā)送消息程序server.c3、在msg.c中，創(chuàng)建三個(gè)子進(jìn)程：其中兩個(gè)調(diào)用client.c

另一個(gè)調(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)/*子進(jìn)程2001*/

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

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

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

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

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

}

else

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

getpid());

}

}

}

wait(0);

wait(0);

wait(0);

}16子進(jìn)程2001子進(jìn)程2002子進(jìn)程2000TYPE：1TEXT：2001TYPE：1TEXT：2002TYPE：

2001TEXT：

2000TYPE：

2002TEXT：

2000消息隊(duì)列書(shū)例P16317實(shí)例3：和控制臺(tái)的通信i18①用戶進(jìn)程PiCCP的接口用戶進(jìn)程發(fā)出問(wèn)題：P_write(m)Begin

P(rq)

把m插入RQ隊(duì)列

V(rq)

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

P(question)

P(rq)

把m從RQ隊(duì)列取出

V(rq)End19②

CCP與DCP的接口CCP向outbuf送問(wèn)題：

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與顯示器的通信顯示器控制進(jìn)程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顯示器動(dòng)作DP：

D_ready=0Repeat if(echo=true)then

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

else

P(D_ready)

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

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

KCP與鍵盤的通信鍵盤控制進(jìn)程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鍵盤動(dòng)作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用戶進(jìn)程Pi的接口CCP發(fā)出回答：S_answer(a,i)Begin

P(sqi)

把a(bǔ)插入SQi隊(duì)列

V(sqi)

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

P(answeri)

P(sqi)

把a(bǔ)從SQi隊(duì)列取出

V(sqi)

End24會(huì)話控制進(jìn)程CCP的動(dòng)作描述Localk,m,xRepeat

U_receive(m)

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

write(x)

read(x)

將x編碼到m

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

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

內(nèi)容：把資源編號(hào)排序，要求進(jìn)程必須按編號(hào)遞增的順序申請(qǐng)資源：

m個(gè)資源，R1<R2<…<Rm，進(jìn)程P1保持了Ri，只能申請(qǐng)Rj，（j>i）;

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

編號(hào)原則：常用資源低序號(hào)，不常用資源高序號(hào)；

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

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

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

把空閑的3個(gè)中的2個(gè)分給B

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

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

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

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

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

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

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

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

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

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

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

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

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

進(jìn)程的性質(zhì)：

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

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

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

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

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

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

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

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

1）多個(gè)用戶對(duì)文件服務(wù)器提出文件訪問(wèn)請(qǐng)求；

2）前臺(tái)和后臺(tái)的分工處理；

3）異步處理；

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

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

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

操作系統(tǒng)內(nèi)核進(jìn)行管理，內(nèi)核提供系統(tǒng)調(diào)用和應(yīng)用程序接口創(chuàng)建、調(diào)度、撤消線程； 負(fù)責(zé)進(jìn)程和線程的調(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用來(lái)創(chuàng)建一個(gè)線程：

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

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