操作系統(tǒng)授課教師：王玲芬OperatingSystem2-437室進(jìn)程管理Processmanagement主要內(nèi)容為什么要引入進(jìn)程的概念進(jìn)程的表示和調(diào)度狀態(tài)進(jìn)程的控制進(jìn)程調(diào)度線程及其管理進(jìn)程通信死鎖問題四、經(jīng)典的進(jìn)程同步互斥問題1.生產(chǎn)者─消費(fèi)者問題消費(fèi)者生產(chǎn)者同步問題： 生產(chǎn)者進(jìn)程P不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號(hào)量Sn，表示可用緩沖區(qū)數(shù)

消費(fèi)者進(jìn)程Q不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號(hào)量S0表示產(chǎn)品數(shù)量Sn初值為1，S0初值為0消耗該產(chǎn)品生產(chǎn)者進(jìn)程P消費(fèi)者進(jìn)程QP(Sn)V(Sn)生產(chǎn)一種產(chǎn)品產(chǎn)品送入緩沖區(qū)P(S0)V(S0)從緩沖區(qū)取取一產(chǎn)品Sn初值為1，S0初值為0消耗該產(chǎn)品生產(chǎn)者進(jìn)程P消費(fèi)者進(jìn)程QP(Sn)V(Sn)生產(chǎn)一種產(chǎn)品產(chǎn)品送入緩沖區(qū)P(S0)V(S0)從緩沖區(qū)取取一產(chǎn)品Sn初值為n，S0初值為0多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者要不要對(duì)緩沖區(qū)（臨界資源）進(jìn)行互斥操作？消耗該產(chǎn)品生產(chǎn)者進(jìn)程Pi消費(fèi)者進(jìn)程QiP(Sn)V(Sn)生產(chǎn)一種產(chǎn)品產(chǎn)品送入緩沖區(qū)P(S0)V(S0)從緩沖區(qū)取取一產(chǎn)品Sn初值為n，S0初值為0互斥訪問緩沖區(qū)消耗該產(chǎn)品生產(chǎn)者進(jìn)程Pi消費(fèi)者進(jìn)程QiP(Sn)V(Sn)生產(chǎn)一種產(chǎn)品產(chǎn)品送入緩沖區(qū)P(S0)V(S0)從緩沖區(qū)取取一產(chǎn)品S互斥信號(hào)量，初值為1P(S)V(S)P(S)V(S)BeginB:array[0..n-1]ofinteger;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;CobeginProcessproduceri(i=1,2,…,m)beginL1:produceaproduct;

P(Sn);P(S);B[p]:=product;p:=(p+1)modn;

V(s0);V(s);gotol1endProcessconsumetj(j=1,2,…,k)begin

L2:P(S0);P(S);takeaproductformB[R];R:=(R+1)modn;

V(sn);V(s);consumegotol2end;coeng;end;消耗該產(chǎn)品生產(chǎn)者進(jìn)程Pi消費(fèi)者進(jìn)程QiV(Sn)生產(chǎn)一種產(chǎn)品產(chǎn)品送入緩沖區(qū)P(S0)V(S0)從緩沖區(qū)取取一產(chǎn)品S互斥信號(hào)量，初值為1P(S)V(S)P(S)V(S)P(Sn)用信號(hào)量解題的關(guān)鍵步驟：

信號(hào)量的設(shè)置；

給信號(hào)量賦初值（常用的互斥和同步信號(hào)量值的大?。?/p>

P、V操作安排的位置（其中，P的順序不能顛倒，V的順序任意）注意區(qū)分1）公用信號(hào)量,互斥時(shí)使用的信號(hào)量：它聯(lián)系著一組共行進(jìn)程，初值為１，每個(gè)進(jìn)程均可對(duì)之施加Ｐ、Ｖ操作。2）私用信號(hào)量：一般信號(hào)量：它聯(lián)系著一組共行進(jìn)程，但其初值為０，或?yàn)槟硞€(gè)正整數(shù)ｎ，表示資源的數(shù)目，主要用于進(jìn)程同步。只允許擁有它的進(jìn)程對(duì)之施加Ｐ操作。用P、V操作能解決的問題互斥：信號(hào)量初值為1同步：信號(hào)量的初值為0資源分配：信號(hào)量的初值為n2.讀者寫者問題

有兩組并發(fā)進(jìn)程:讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作互斥互斥RRW讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待BeginS,Sr:semaphore;rc:integer;S:=Sr:=1;rc:=0;CobeginprocessReaderi(i=1,2,…,m)beginP(Sr);rc:=rc+1;ifrc=1thenP(S);V(Sr);readfileFP(Sr)rc:=rc-1;ifrc=0thenV(S);V(Sr)endprocessWriterj(j=1,2..k)beginP(S);WritefileFV(S)end初值：S=1,Sr=1,rc=0如果讀者來：1）無讀者、寫者，新讀者可以讀2)有讀者讀,新讀者也可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待processReaderi(i=1,2,…,m)beginP(Sr);rc:=rc+1;ifrc=1thenP(S);V(Sr);readfileFP(Sr)rc:=rc-1;ifrc=0thenV(S);V(Sr)endprocessWriterj(j=1,2..k)beginP(S);WritefileFV(S)end初值：S=1,Sr=1,rc=0如果讀者來：1）無讀者、寫者，新讀者可以讀2)有讀者讀,新讀者也可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待讀者優(yōu)先，會(huì)造成寫者等待很長(zhǎng)時(shí)間寫者優(yōu)先？寫者等，新讀者不能讀課后思考題1)信號(hào)量的物理含義：S>0表示有S個(gè)資源可用S=0表示無資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P.V操作討論P(yáng)(S):表示申請(qǐng)一個(gè)資源V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0

P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操的順序至關(guān)重要,而兩個(gè)V操作無關(guān)緊要BeginB:array[0..n-1]ofinteger;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;CobeginProcessproduceri(i=1,2,…,m)beginL1:produceaproduct;

P(Sn);P(S);B[p]:=product;p:=(p+1)modn;

V(s0);V(s);gotol1endProcessconsumetj(j=1,2,…,k)begin

L2:P(S0);P(S);takeaproductformB[R];R:=(R+1)modn;

V(sn);V(s);consumegotol2end;coeng;end;課后思考題優(yōu)點(diǎn)：簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問題）缺點(diǎn)：不夠安全；P.V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜P.V操作的優(yōu)缺點(diǎn)五、信號(hào)量集

1.AND型信號(hào)量集2.一般“信號(hào)量集”六、引入更高級(jí)的工具管程問題關(guān)鍵:在程序的許多地方都有信號(hào)量的操作想法:將共享數(shù)據(jù)、互斥(同步)操作集中隱藏起來，由輔助工具負(fù)責(zé)展開 monitorexample{intcounter;voidproducer(x);voidconsumer(x);} while(true){ducer(x);} while(true){example.consumer(x);}編譯器將其展開 while(true){mutex.P();producer函數(shù)體;if(??)xx.V();mutex.V();}管程描述管程將共享數(shù)據(jù)、同步互斥等封裝起來管程里的數(shù)據(jù)結(jié)構(gòu)只能通過管程中的操作訪問初始化共享數(shù)據(jù)操作一次只允許一個(gè)進(jìn)程調(diào)用這些操作(互斥進(jìn)入)條件變量(condition)關(guān)聯(lián)一個(gè)隊(duì)列，用來實(shí)現(xiàn)同步隱式實(shí)現(xiàn)互斥條件變量上的操作只有wait(即P)和signal(即V)隱式實(shí)現(xiàn)同步條件x用管程解決生產(chǎn)者消費(fèi)者問題

monitorProducerConsumer{intcounter;conditionfull,empty;

voidenter(x){if(counter==N)full.wait();將x放入緩沖區(qū);counter++;if(counter==1)empty.signal();}

itemremove(){if(counter==0)empty.wait();從緩存區(qū)取出x;counter--;if(counter==N-1)full.signal();}}

voidproducer(){while(true){生產(chǎn)x;ProducerConsumer.enter(x);}}

voidconsumer(){while(true){x=ProducerConsumer.remove();}}實(shí)際操作系統(tǒng)提供哪些同步工具!§5.4高級(jí)通訊通訊:進(jìn)程間信息的傳遞低級(jí)通訊:進(jìn)程間控制信息的傳遞(控制進(jìn)程的速度)進(jìn)程通訊類型（消息緩沖、信箱通訊、共享文件）高級(jí)通訊:進(jìn)程間大批量數(shù)據(jù)的傳遞(效率高)

一、消息緩沖通信（直接通訊）發(fā)送進(jìn)程在自己的工作區(qū)域,設(shè)置發(fā)送區(qū),然后,調(diào)用發(fā)送原語將信息發(fā)送到消息緩沖區(qū)，接收進(jìn)程也是先在自己的工作區(qū)域準(zhǔn)備好接收區(qū),然后調(diào)用接收原語，將消息緩沖區(qū)的消息接收到工作區(qū)。2.發(fā)送和接收原語Send(receiver,addr)Receiver(addr)發(fā)送進(jìn)程發(fā)消息時(shí)要指定接收進(jìn)程的名字，1.消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)發(fā)送者進(jìn)程標(biāo)識(shí)符：Sender消息長(zhǎng)度：size消息正文:text指向下一消息緩沖區(qū)的指針：nextSender:ASIZE:5TEXT:hello接收者進(jìn)程發(fā)送消息地址接收消息地址3.PCB中應(yīng)增數(shù)據(jù)項(xiàng)：mq 消息隊(duì)列指針mutex消息隊(duì)列互斥信息量sm 消息隊(duì)列資源信息量（消息數(shù)）mqmutexsmsender:Asize:5text:Hellosend(B,a)sender:Asize:5text:hellonext:0發(fā)送區(qū)sender:Asize:5text:Helloreceive(A，b)接收區(qū)ab進(jìn)程APCB(B)進(jìn)程B4.發(fā)送與接收過程用P.V操作來實(shí)現(xiàn)Send原語:Send（B，a）P(mmutex);Begin把緩沖區(qū)掛到接收進(jìn)程根據(jù)B找接收進(jìn)程，的消息鏈鏈尾;如果沒找到出錯(cuò)返回;V(mmutex);申請(qǐng)空緩沖區(qū)P（sb）；V(sm);P(bmutex);END取空緩沖區(qū);V(bmutex);把消息從a處copy到空緩沖區(qū);其中sb初值:n;sm初值:0Receive(b)課堂練習(xí)用P.V操作來實(shí)現(xiàn)Receive原語:Receive(A，b)P(bmutex);Begin把空緩沖區(qū)掛到空白P（sm）緩沖區(qū)鏈尾;V(bmutex);

V(sb);P(mmutex);END從消息鏈中取進(jìn)程A發(fā)來的消息內(nèi)容復(fù)制到工作區(qū)bV(mmutex);

其中sb初值:n;sm初值:0Receive(A,b)課堂練習(xí)二、信箱通訊（間接通信）：

發(fā)送進(jìn)程發(fā)消息時(shí)不指定接收進(jìn)程的名字，而是指定一個(gè)中間媒介，即信箱。進(jìn)程間通過信箱實(shí)現(xiàn)通信發(fā)送原語：send(MB,Message)接收原語：receive(MB,Message)信箱頭格子1格子2格子3…格子n進(jìn)程A發(fā)送信件進(jìn)程B接收信件(1)信箱的數(shù)據(jù)結(jié)構(gòu)boxname:信箱名boxsize:信箱大小mesnum:已存信件數(shù)fremnum;空的格子數(shù)boxnameboxsizemesnumfremnum信件滿信件滿格子空……格子空(2)發(fā)送與接收原語Send(boxname,msg)Receiver(boxname,msg)Send（boxname，msg）BeginlocalX;根據(jù)boxname找到信箱;

P（fremnum);

選擇標(biāo)志為空的格子；把消息msg放入空的格子X中；置格子X為滿標(biāo)志；

V(mesnum);endreceive（bosname，msg）BeginlocalX;根據(jù)boxname找到信箱;

P（mesnum);選擇標(biāo)志為滿的格子X；將X中的信件取出放入meg中；置格子X為空標(biāo)志；

V(fremnum);end三、管道通信方式Pipe(共享文件）

也稱共享文件方式，基于文件系統(tǒng)，利用一個(gè)打開的共享文件連接兩個(gè)相互通信的進(jìn)程，文件作為緩沖傳輸介質(zhì)發(fā)送進(jìn)程接收進(jìn)程字符流方式寫入讀出先進(jìn)先出順序有關(guān)的系統(tǒng)功能調(diào)用：pipe(fd)fd:intfd[2]其中:fd[0]、fd[1]文件描述符（讀、寫）write(fd,buf,byte)、read(fd,buf,byte)

fd:文件描述符buf:信息傳送的源（目標(biāo)）地址byte:傳送的字節(jié)數(shù)lockf(fd,function,byte)fd:文件描述符function:1:鎖定0:解鎖byte:鎖定的字節(jié)數(shù)，0:從當(dāng)前位置到文件尾sleep: