《操作系统C 第2章 进程管理3典型的同步问题课件》由会员分享，可在线阅读，更多相关《操作系统C 第2章 进程管理3典型的同步问题课件（42页珍藏版）》请在金锄头文库上搜索。
1、知识回顾,信号量机制 管程？,2.4 经典的进程同步问题,本节我们讨论几个实现进程互斥和同步的经典例子。这里的主要问题是如何选择信号量和如何安排P、V原语的使用顺序。,2.4.1生产者和消费者问题,生产者和消费者问题是进程相互合作关系的一种抽象。例如，输入时，输入进程是生产者，计算进程是消费者；而输出时，计算进程是生产者，打印进程是消费者。,生产者一消费者问题(producer-consumerproblem)是指若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。,利用记录型信号量解决： 基本工作：生产者生产消息放入缓冲区 消费者从缓冲区取走消息 互斥：缓冲池是临界资源，设置信号量m
2、utex=1 同步: (生产者)有空缓冲区放产品，唤醒等待的 消费者进程；无空缓冲区则阻塞。 (消费者)有产品取走，唤醒等待的生产者进 程；无产品则阻塞。 实现同步需要设置两个信号量empty=n,full=0,可设置三个信号量：full、empty和mutex。,Var full,empty,mutex:semaphore:=0,n,1; Buffer: array0,n-1 of item; In, out: integer:=0, 0; Producer: begin repeat produce an item in nextp; wait(empty) wait(mutex) buf
3、ferin:=nextp; in:=(in+1) mod n; signal(mutex); signal(full); until false; end;,consumer: begin repeat wait(full) wait(mutex) nextc := bufferout; out:=(out+1) mod n; signal(mutex); signal(empty); consume the item in nextc; until false; end;,注意： 要先对同步信号量进行P操作，再对互斥信号量进行P操作，否则可能引起死锁。,思考题: 如何解决因PV操作的顺序而引
4、起的死锁问题？,利用AND型信号量解决： Begin Produce an item in nextp; Swait(empty,mutex); Buffer(in):=nextp; In:=(in+1) mod n Ssignal(mutex,full); Until false; end,Begin Swait(full,mutex); nextc:= Buffer(out) ; Out:=(out+1) mod n; Ssignal(mutex,full); Consume an item in nextc; Until false; end,3 利用管程解决生产者-消费者问题,假设已实
5、现管程monitor的enter,leave,signal,wait操作 定义一个管程名pc； 定义整形变量count,in,out； count产品数量，in第一个空缓冲区指针，out第一个不空的缓冲区指针 定义条件变量full, empty; full指向因缓冲区满而等待的队列, empty指向因缓冲区空而等待的队列； 定义缓冲区array 0.n-1; 定义过程put(item)和get(item); 初始化共享变量。,Type pc=monitor; Var in, out, count: integer; Buffer: array0,n-1 of item; Var full, e
6、mpty: condition;,过程定义,Procedure put(item) begin if count=n then full.wait; bufferin:=nextp; in:=(in+1) mod n; count :=count+1; empty.signal; end;,Procedure get(item) Begin If count=0 then empty.wait; nextc := Bufferout; out:=(out+1) mod n; Count :=count-1; full.signal; End;,初始化共享变量,Begin In:=0; Out:
7、=0; Count:=0; End;,利用管程解决生产者-消费者问题,Producer: Begin Repeat Produce an item in nextp; Pc.put(item); Until false; End;,consumer: Begin Repeat Pc.get(item); consume an item in nextc; Until false; End;,【思考题】,有一个仓库，可以存放A和B两种产品，但要求： （1） 每次只能存入一种产品（A或B） （2） nA产品数量B产品数量m。 其中，n和m是正整数。试用P、V操作描述产品A与B的入库过程。 提示：设
8、两个信号量Sa、Sb Sa表示允许A产品比B产品多入库的数量 Sb表示允许B产品比A产品多入库的数量,解,设两个信号量Sa、Sb，初值分别为m-1，n-1 Sa表示允许A产品比B产品多入库的数量 Sb表示允许B产品比A产品多入库的数量 设互斥信号量mutex，初值为1。,B产品入库进程： j = 0; while (1) P(Sb); P(mutex); B产品入库 V(mutex); V(Sa); 消费产品; ;,A产品入库进程：i = 0;while (1) 生产产品; P(Sa); P(mutex); A产品入库 V(mutex); V(Sb); ;,2读者一写者问题,读者一写者问题(r
9、eaders-writersproblem)是指多个进程对一个共享文件进行读写操作的问题。 即对共享文件的读写操作限制关系包括：“读写互斥、“写一写”互斥和“读读”允许。,有两组并发进程: 读者和写者,共享一组数据区(文件) 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,第一类：读者优先,如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,设有两个信号量w=1，mutex=1 另设一个全局变量r
10、eadcount =0 w用于读者和写者、写者和写者之间的互斥 readcount表示正在读的读者数目 mutex用于对readcount 这个临界资源的互斥访问,读者： while (1) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 读 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;,写者： while (1) P(w); 写 V(w); ;,思考题：reader进程中第一个V(mutex)和第二个P(mutex)能否去掉？,【思考题】写优先,修改以上读者
11、写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须等待，无论是否有读者在读。 提示，增加一个信号量，用于在写者到达后封锁后续的读者,增加一个信号量s，初值为1,读者： while (1) P(s); P(mutex); readcount +; if (readcount=1) P (w); V(mutex); V(s); 读 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;,写者： while (1) P(s); P(w); 写 V(w); V(s); ;,利用信号量集机制解决读者写者问题,增加一个限制条件，最多
12、只允许Rn个读者同时读。 引入一个信号量L, 表示允许读者数目，初值为Rn。 Mx表示允许写，初值为1。,Var Rn integer; L, Mx:semaphore:=Rn,1; Reader:begin Swait(L,1,1; mx,1,0); Read; Ssignal(L,1); End;,writer:begin Swait(mx,1,1; L,Rn,0); write; Ssignal(mx,1); End;,三、哲学家就餐问题 问题描述： 有5位哲学家，他们的生活方式是交替进行思考和进餐，公用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五只筷子，哲学家饥饿时必须同时拿起左右
13、筷子才能进餐，进餐完毕，放下筷子继续思考。,用记录型信号量机制： Var chopstick array04of semaphore:=1,1,1,1,1; Process i(i=0,1,2,3,4):begin Think; P(chopsticki); P(chopsticki+1 mod 5); Eat; v(chopsticki); v(chopsticki+1 mod 5); Until false; End;,思考题： 上面哲学家记录型信号量解决的进餐问题 存在什么问题？如何解决？,最多仅允许四个哲学家同时去拿左边的筷子。 使用AND型信号量机制解决 规定奇数号科学家先拿左边的筷
14、子，偶数号科学家先拿右边的筷子。,2利用AND信号量解决哲学家进餐问题,Var chopstick array of semaphore:=(1,1,1,1,1) Think; Sp(chopstick(i+1) mod 5,chopsticki) Eat; Sv(chopstick(i+1) mod 5 ,chopsticki) Until false;,【思考题1】,如图，试用信号量实现这三个进程的同步。,【思考题2】,如图，试用信号量实现这6个进程的同步,【思考题3】,用P.V操作解决下图之同步问题,get,copy,put,s,t,设置四个信号量Sin=1，Sout=0，Tin=1，T
15、out=0；,get： while（1） P(Sin）; 将数放入S; V(Sout); ,copy： while（1） P(Sout）; P(Tin）; 将数从S取出放入T; V(Tout); V(Sin); ,put： while（1） P(Tout）; 将数从T取走; V(Tin); ,【思考题4】 有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：,(1) 为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？,(2) 用类Pascal语言和P, V操作写出这些进程间的同步算法。,beginS1:=100 (有100个座位)S2:=0 (有没阅读者)mutex: =1cobeginP1: repeatP(S1);P(mutex);登记信息;V(muetx);V(S2)就座，阅读； until false coend end,P2: repeatP(S2)P(mutex);消掉信息;V(muetx);V(S1);离开阅览室; until false,
