操作系统课件os02进程同步.ppt

《操作系统课件os02进程同步.ppt》由会员分享，可在线阅读，更多相关《操作系统课件os02进程同步.ppt（58页珍藏版）》请在三一办公上搜索。

1、操作系统Operating Systems,2.3 进 程 同 步,进程同步的基本概念 两种形式的制约关系间接相互制约关系。间接相互制约源于资源共享直接相互制约关系。主要源于进程间的合作。,进程的同步与互斥,进程的两大关系：互斥（间接制约关系）：各进程竞争使用同一临界资源临界资源：一次只允许一个进程使用的系统资源进程同步（直接制约关系）：根据一定的时序关系合作完成一项任务为完成共同任务的并发进程基于某个条件来协调其活动,生产者-消费者问题,生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。,P,C,生产者-消费者问题,producer:repeat produc

2、e an item in nextp;while counter=n do no-op;bufferin:=nextp;in:=(in+1)mod n;counter:=counter+1;until false,consumer:repeat while counter=0 do no-op;nextc:=bufferout;out:=(out+1)mod n;counter:=counter-1;consumer the item in nextc;until false;,生产者-消费者问题,counter:=counter+1：,register1:=counter；register1

3、:=register1+1；counter:=register1；,counter:=counter-1：,register2:=counter；register2:=register2-1；counter:=register2；,生产者-消费者问题,生产者进程:/counter初始值=5 register1:=counter；register1:=register1+1；counter:=register1；,消费者进程 register2:=counter;register2:=register2-1;counter:=register2；;,程序的执行已经失去了再现性。解决此问题的关键是

4、应把变量counter作为临界资源处理，令生产者进程和消费者进程互斥地访问变量counter。,5,register1,5,register2,4,6,5,counter,4,6,临界区,把在每个进程中访问临界资源的那段代码称为临界区若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。repeatentry section（进入区）critical section；exit section（退出区）remainder section；until false；,临界区,同步机制应遵循的规则,空闲让进。忙则等待。有限等待。让权等待。,信号量机制,1 整型信号量定义为一个用于表

5、示资源数目的整型量S仅能通过两个标准的原子操作P操作(wait)和V操作(signal)来访问。wait(S)：while S=0 do no-op；S:=S-1；signal(S)：S:=S+1；,S,2 记录型信号量,记录型信号量机制是一种不存在“忙等”现象的进程同步机制。增加一个进程链表指针L用于链接上述的所有等待进程。记录型信号量采用了记录型的数据结构：type semaphore=recordvalue:integer；L:list of process；end,申请一个单位资源：procedure wait(S)var S：semaphore；begin S.value:=S.va

6、lue-1；if S.value0 then block(S.L)；end,释放一个单位资源：procedure signal(S)var S:semaphore；Begin S.value:=S.value+1；if S.value=0 then wakeup(S.L)；end,一般信号量,若信号量s.value为正值则s.value所代表的实际还可以使用的物理资源数.若信号量s.value为负值：则其绝对值等于登记排列在该信号量s队列之中等待的进程个数S.value的初值为1时：表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。,上述的进程互斥问题，是针对各进程之

7、间只共享一个临界资源而言的。,process A:process B:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)；,若进程A和B按下述次序交替执行wait操作：process A:wait(Dmutex)；于是Dmutex=0process B:wait(Emutex)；于是Emutex=0process A:wait(Emutex)；于是Emutex=-1 A阻塞process B:wait(Dmutex)；于是Dmutex=-1 B阻塞,3 AND同步机制的基本思想,采取原子操作方式：要么把它所请求的资源全部分配到进程要么一个也不

8、分配。可避免上述死锁情况的发生。在wait操作中，增加了一个“AND”条件AND同步，或称为同时wait操作Swait(Simultaneous wait),Swait(S1，S2，Sn)if S1=1 and and Sn=1 thenfor i:=1 to n do Si:=Si-1；endforelse 当发现第一个 Si1就把该进程放入等待队列，并将其指令计数器置于Swait操作的开始位置endif,Ssignal(S1，S2，Sn)for i:=1 to n doSi:=Si+1；Remove all the process waiting in the queue associat

9、ed with Si into the ready queue.endfor；,2.3.3 信号量的应用利用信号量实现进程互斥,Var mutex:semaphore=1;begin parbegin process 1:begin repeat wait(mutex);critical section；signal(mutex);remainder section;until false;end,process 2:begin repeat wait(mutex);critical section;signal(mutex);remainder section；until false;End

10、parend,mutex,1,0,NULL,-1,2.3.4 管程机制,管程引入把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作可利用共享数据结构抽象地表示共享资源，把对共享数据结构实施的操作定义为一组过程进程对共享资源的操作，都是通过这组过程对共享数据结构的操作来实现的确保每次仅有一个进程使用共享资源,管程的定义,一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据。管程的组成1.名称；2.局部于管程内部的共享数据结构说明；3.对该数据结构进行操作的一组过程；4.对局部于管程内部的共享数据设置初始值语句。,

11、管程的示意图,局部数据,条件变量,过程/函数1,过程/函数k,出口,初始化代码,入口,管程,等待调用过程的进程队列,管程等待区,管程的条件变量,条件变量出现在管程内的一种数据结构 Var x，y：condition只有在管程中才能被访问它对管程内的所有过程是全局的只能通过两个原语操作wait和signal来控制它。,x.wait,正在调用管程的进程因x条件需要被阻塞或挂起时调用x.wait：将自己插入到x条件的等待队列上并释放管程，直到x条件变化。此时其它进程可以使用该管程。,x.signal,正在调用管程的进程发现x条件发生了变化，则调用x.signal重新启动一个因x条件而阻塞或挂起的进程

12、。这与信号量机制中的signal操作不同。若进程Q因x条件阻塞，而正在调用管程的进程P执行x.signal操作后，Q被重新启动，可采用下述两种方式之一进行处理：P等待，直至Q离开管程或等待另一条件。Q等待，直至P离开管程或等待另一条件。,管程主要特性,模块化基本程序单位，可以单独编译；抽象数据类型包含数据和操作；信息隐蔽从外部看不到内部信息；,管程和进程不同,管程定义的是公共数据结构；进程定义的是私有数据结构PCB管程把共享变量上的同步操作集中起来临界区却分散在每个进程中；管程的设置则是解决共享资源的互斥使用问题设置进程的目的在于实现系统的并发性；进程通过调用管程中的过程对共享数据结构实行操作

13、管程为被动工作方式，进程则为主动工作方式；,管程和进程不同（续）,管程不能与其调用者并发进程之间能并发执行；管程是操作系统中的一个资源管理模块，供进程调用。进程具有动态性，由“创建”而诞生，由“撤销”而消亡,2.4 经典进程的同步问题,2.4.1 生产者消费者问题生产者消费者问题是相互合作的进程关系的一种抽象制约关系：只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息,P,C,信号量解决生产者消费者问题,用信号量及P、V操作解决进程间同步问题 一个生产者、一个消费者共享一个缓冲区多个生产者、多个消费者共享多个缓冲区,一个生产者、一个消费者共享一个缓冲区

14、的解,int B;semaphore empty;/可以使用的空缓冲区数semaphore full;/缓冲区内可以使用的产品数empty=1;/缓冲区内允许放入一件产品full=0;/缓冲区内没有产品,一个生产者、一个消费者共享一个缓冲区,cobeginprocess producer()process consumer()while(true)while(true)produce();P(empty);append()to B;V(full);coend,Empty,full,空 1,不满 0,0,满 1,无缓冲区-1,空-1,P(full);,V(empty);,consume();,t

15、ake()from B;,一组生产者，一组消费者，公用n个环形缓冲区,利用记录型信号量解决生产者消费者问题,Var buffer:array0,n-1 of item;in，out:integer:=0,0;/放入、取出缓冲区指针mutex:semaphore:=1；empty:semaphore:=n;/可以使用的空缓冲区数full:semaphore:=0;/缓冲区内可以使用的产品数,P1P2P3.Pm.,C1C2C3.Ck,生产者/消费者、共享多个缓冲区的解,parbeginProceducer_i:begin repeat produce an item nextp;wait(empt

16、y);wait(mutex);buffer(in):=nextp;in:=(in+1)mod n;signal(mutex);signal(full);until false;endparend,Consumer_j:begin repeat wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)mod n;signal(mutex);signal(empty)；consumer the item in nextc;until false;end parend end,永远等待,cobeginprocess producer_i()whil

17、e(true)produce();P(mutex);P(empty);append to Bin;in=(in+1)%k;V(mutex);V(full);coend,process consumer_j()while(true)P(full);P(mutex);take()from Bout;out=(out+1)%k;V(mutex);V(empty);consume();,empty,full,0,k,Mutex=1,Mutex=0,-1,信号量及P、V操作讨论,P、V操作必须成对出现当为互斥操作时，它们处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在

18、一起，那么P操作的顺序至关重要一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前两个V操作无关紧要,哲学家进餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把筷子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两只筷子，且每人只能直接从自己左边或右边去取筷子,解决思路,5位哲学家看作5个进程筷子是临界资源，在一段时间内只允许一位哲学家使用可以用一个信号量表示一只筷子由这五个信号量构成信号量数组。其描述如下：Var chopstick:array0，4 of semaphore；所有信号量均被初始化为1,用记录型信号量解

19、决哲学家进餐问题,第i位哲学家的活动可描述为：repeat wait(chopsticki)；wait(chopstick(i+1)mod 5)；eat；signal(chopsticki)；signal(chopstick(i+1)mod 5)；think；until false；,分析,上述解法可保证不会有两个相邻的哲学家同时进餐,问题,有可能引起死锁可能出现永远等待,有若干种办法可避免这类死锁,至多允许四个哲学家同时吃；奇数号先取左手边的筷子，偶数号先取右手边的筷子；每个哲学家取到手边的两把筷子才吃，否则一把筷子也不取。本质上就是AND同步问题用AND信号量机制可获得最简洁的解法。,利用

20、AND信号量机制解决哲学家进餐问题,Var chopsiick array of semaphore:=(1,1,1,1,1)；processirepeatthink；Swait(chopstick(i+1)mod 5，chopsticki)；eat；Ssignal(chopstick(i+1)mod 5，chopsticki)；until false；,读者-写者问题,有两组并发进程：读者和写者共享一个文件F，要求：允许多个读者同时执行读操作只允许一个写者执行写操作不允许任意一个写者和其他读者或其他写者同时访问文件,读者-写者问题：解决思路,为解决Reader与Writer进程间互斥设置信号

21、量Wmutex表示是否允许写的，初值为1,读者-写者问题：解决思路,设置一个整型变量Readcount表示正在读的进程数目初值为0Readcount是一个可被多个Reader进程访问的临界资源为它设置一个互斥信号量rmutex初值为1,parbeginReader:begin repeatwait(rmutex)；if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount

22、=0 then signal(wmutex)；/最后一个读者离开时通知写者 signal(rmutex)；until false；endparend,writer:beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End,parbeginReader:begin repeatwait(rmutex)；if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(

23、rmutex)；readcount:=readcount-1；if readcount=0 then signal(wmutex)；/最后一个读者离开时通知写者 signal(rmutex)；until false；endparend,writer:beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End,parbeginReader:begin repeatwait(rmutex)；if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；

24、signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 then signal(wmutex)；/最后一个读者离开时通知写者 signal(rmutex)；until false；endparend,writer:beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End,苹果桔子问题,苹果桔子问题桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果，妈妈专向盘子中放桔子

25、；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果,苹果桔子问题,解决思路：生产者消费者问题的变形，有两类生产者和两类消费者互斥：盘子同步：爸爸和女儿；妈妈和儿子进程数目,分析,设置3个信号量empty表示盘子能放的水果数目，初值为1full_o表示盘子里有无桔子，初值为0 full_a表示盘子里有无苹果，初值为0 empty,full_o,full_a:semaphore;empty:=1;full_o:=0;full_a:=0;,process father begin L1:削一个苹果；P(empty);放苹果;V(full_a);goto L1;end;process mothe

26、r begin L2:剥一个桔子；P(empty);放桔子；V(full_o);goto L2;end;,process daughter begin L4:P(full_a);取苹果；V(empty);吃苹果；goto L4;end;process son begin L3:P(full_o);取桔子；V(empty);吃桔子；goto L3;end;,问题,可以放n个水果？empty表示盘子能放的水果数目，初值为nfull_o表示盘子里有无桔子，初值为0 full_a表示盘子里有无苹果，初值为0 mutex对盘子的互斥访问,初值为1empty,full_o,full_a，mutext:se

27、maphore;empty:=n;full_o:=0;full_a:=0;mutex=1,process father begin L1:削一个苹果；P(empty);P(mutex);放苹果;V(mutex);V(full_a);goto L1;end;,process daughter begin L4:P(full_a);P(mutex);取苹果；V(mutex);V(empty);吃苹果；goto L4;end;,process mother Begin L2:剥一个桔子；P(empty);P(mutex);放桔子；V(mutex);V(full_o);goto L2;end;,process son begin L3:P(full_o);P(mutex);取桔子；V(mutex);V(empty);吃桔子；goto L3;end;,作业,P82-83 24 26 27 28,