第三章进程管理5

用P、V原语实现进程同步和互斥
例5：某车站售票厅有20个窗口，任何时刻最 多可容纳20名购票者进入，当售票厅中少于20 名购票者时，则厅外的购票者可立即进入，否 则需在厅外等待。若把购票者看做一个进程， 请用P，V操作管理这些进程，要求如下： (1)在主函数中给出信号量的定义和初值。 (2)给出一个购票者进程的算法 (3)给出当购票者最多不超过n(设n>20)个时，信 号量可能的变化范围。
用P、V原语实现进程同步和互斥


理发师： repeat P(customers) V(barber) 给顾客理发 Until false



顾客： V(customers) P(barber) 获得理发服务
用P、V原语实现进程同步和互斥

例9：某工厂有两个生产车间和一个装配车间。 两个生产车间分别生产A、B两种零件，每生产 一个零件后都要分别把它们送到装配车间的货 架F1、F2上，F1上放零件A，F2上放零件B， F1和 F2的容量均为10个零件，装配工人每次 从架上取一个零件A和一个零件B，然后组装成 产品，请用P、V原语进行正确管理。
解：1）设私用信号量avail表示缓冲区中的空单 元数，full表示缓冲区中的满单元数；公用信号 量mutex表示整个缓冲区是否在使用 2）设初始值avail=n，full=0，mutex=1 3）描述
生产者----消费者问题
Producer: P(avail); P(mutex); Consumer: P(full); P(mutex); 取缓冲区中某单元数据 V(mutex); V(avail);



入水： L1:P(empty) P(count) P(mutex1) 从井中取水 V(mutex1) P(mutex2) 送水入缸 V(mutex2) V(count) V(full) Goto L1



Βιβλιοθήκη Baidu
取水： L2:P(full) P(count) P(mutex2) 从缸中取水 V(mutex2) V(count) V(empty) Goto L2

用P、V原语实现进程同步和互斥
(1)主函数算法 main() { int mutex=20; cobegin (2)购票者i的算法 pi() {p(mutex); 进入售票厅 占有一个窗口购票; p1();p2();…;pi();…;pn(); v(mutex); coend } } （3）信号量最大值为20，最小值为20-n


解：1）设公用信号量mutex1，mutex2 分别控制井和缸的互斥，count表示空闲 的水桶数；私用信号量empty表示缸中还 可以入几桶水，full表示缸中已入几桶水 2）设初始值mutex1=1， mutex2=1，empty=10，full=0， count=3 3）描述
用P、V原语实现进程同步和互斥



例7：图书馆阅览室有100个座位，一张登记表， 要求阅读者进入时登记，取得座位号，出来时注销 座位号。登记表同时只能由一个人使用，用P、V 原语描述一个读者进入和出来的过程。 分析： 1）互斥问题：登记表同时只能由一个人使用 2）同步问题：读者进入时，100个座位至少由 一 个是空的，出来时，要释放所占有的座位

装配工人 L3:P(full1) P(full2) P(mutex1) P(mutex2) 取AB零件装配 V(mutex1) V(mutex2) V(empty1) V(empty2) Goto L3
用P、V原语实现进程同步和互斥

两个进程PA和PB通过两个FIFO缓冲区队列连接（设缓 冲区队列的缓冲区个数都为n个），每个缓冲区长度等 于传送消息长度。进程PA和PB之间的通信满足如下条 件：
用P、V原语实现同步


1）设close为进程P1的私有信号量，表示售票员是否 关门，stop为进程P2的私有信号量，表示车辆是否停 止到站。 2）设初始值close=1，stop=0，表示车正在运行。 3）描述： P2: P1: B:P(stop) A:P(close) 开门 启动 关门 行车 V(close) 停车 售票 V(stop) Goto B Goto A
将数据送入缓冲区某单元
V(mutex); V(full);

注意:P操作顺序很重要：先检查是否有资源 可用，再检查是否互斥；V操作顺序无所谓
用P、V原语实现哲学家问题

例1：5个哲学家在圆桌前进餐，两个人之间各放 一根筷子。哲学家或者思考或者分别取左右手边 的筷子进餐。请用P、V原语描述每个哲学家的进 餐过程。
用P、V原语实现进程互斥与同步



解：1）设私用信号量avail表示阅览室中的空 座位数，公用信号量mutex表示登记表是否正 在使用 2）设初始值avail=100，mutex=1 3）描述： Enter: Leave:
P(avail) P(mutex) 登记 P(mutex) 注销 V(mutex)
生产者----消费者问题
P1 P2 ... Pm 共享缓冲区

C1 C2 ... Cn

分析： 1）同步问题：生产者想写入时，缓冲区中至 少有一个时空的，消费者想读出时，缓冲区中 至少有一个是满的 互斥问题：任一时刻只能有一个进程可以对缓 冲区操作
用P、V原语实现生产者----消费者问题


V(mutex)
V(avail)
用P、V原语实现进程同步和互斥

例8：某理发师，当没有顾客时，理发 师去睡觉；若有顾客进来时理发师正 在睡觉，则这个顾客会叫醒他。试用P、 V操作描述协调理发师和顾客之间的同 步问题（假设理发店里等候服务的队 伍可以无限长）
用P、V原语实现进程同步和互斥



解：1）设私用信号量customers表示等候服务 的顾客数，barber表示已经做好理发准备的理 发师个数 2）设初始值customers=0， barber=0， 表示没有顾客，理发师正在睡觉 3）描述：
think P(mutex)
P(s[i])
P(s[(i+1) mod 5]) V(mutex) eat V(s[i])
V (s[(i+1) mod 5])
Until false
用P、V原语实现同步

例2 设公共汽车上，司机和售票员的活 动如下。在汽车不断到站停车、行驶过 程中，这两个活动有什么同步关系？用P、 V原语实现他们的同步。
用P、V原语实现进程同步和互斥



A车间 L1:生产一个A P(empty1) P(mutex1) 放入F1上 V(mutex1) V(full1) Goto L1



B车间 L2:生产一个B P(empty2) P(mutex2) 放入F2上 V(mutex2) V(full2) Goto L2


至少有一个空缓冲区存在时，相应的发送进程才能发送一个 消息。 当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程 才能接收一个消息。PAPB缓冲区队列1缓冲区队列2

试描述对第1个缓冲队列操作的发送过程send(1 , m)和 接收过程receive(1 , m)。对第2个缓冲队列操作的发送 过程send(2 , m)和接收过程receive(2 , m)。这里1和2 分别代表缓冲队列1和缓冲队列2，m代表消息。
3 4 4 0 1 3 2 1 2
0
用P、V原语实现哲学家问题
Pi:repeat



解：1）设公用信号量 s[i]表示是否能取到第i 个筷子（i=0,1,2,3,4 ） 2）设初始值， s[i]=1 （i=0,1,2,3,4 ） 3）描述第i个哲学 家Pi：
think
P(s[i])
P(s[(i+1) mod 5])
复习


进程间的制约关系有哪两种？ 什么是进程互斥？什么是进程同步？ 什么是私用信号量？什么是公用信号量？ 各用于何处？ 解决进程互斥和同步问题的步骤是什么？
第三章 进程管理
习题课
生产者----消费者问题




把并发进程同步和互斥问题一般化，得到一个 抽象的模型，即生产者——消费者问题 生产者：释放某一类资源的进程 消费者：使用某一类资源的进程 问题描述：若干个进程通过有限的共享缓冲区 交换数据，其中生产者进程不断写入，消费者 进程不断读出，共享缓冲区共有n个，任一时 刻只能有一个进程对整个共享缓冲区进行操作
1）设同步信号量empty表示盘子是 否为空，orange和apple分别表示盘 子中放了橘子或苹果 2）设初值empty=1， orange=apple=0，表示盘子为空
女儿进程()： {while(没吃够) {P(apple); 从盘中取苹果; V(empty); } }
用P、V原语实现进程互斥与同步
缓冲区队列1 PB
PA 缓冲区队列2



解： 1）设私有信号量bufempty[1],buffull[1], bufempty[2],buffull[2]用于进程PA和PB之间 进行同步 2）设初始值bufempty[1]=n,buffull[1]=0, bufempty[2]=n,buffull[2]=0 3）描述
A车间 A B F1 A 装配工人
B车间
F2
B
用P、V原语实现进程同步和互斥



解：1）设公用信号量mutex1、mutex2控 制进程对F1、F2的互斥操作；私用信号量 empty1、empty2、full1、full2分别表示 F1空位数，F2空位数，F1上零件数，F2 上零件数 2）初始化mutex1=1，mutex2=1， empty1=10，empty2=10，full1=0， full2=0 3）描述：
T1( ) begin T1; V(s12); V(s13); end T2() begin P(s12); T2; V(s24); end T3() begin P(s13); T3; V(s34); end T4( ) begin P(s24); P(s34); T4; end

用P、V原语实现进程同步和互斥

例4：某寺庙，有小、老和尚若干。寺庙有一 水缸，可容10桶水，由小和尚提水入缸、取水 出缸供老和尚饮用，每次入水、取水仅为1桶， 且不可同时进行。水取自同一井中，口窄，每 次只能容一个桶取水。水桶总数为3个。用P、 V原语给出取水入水的算法描述
入 水 缸 出 水
井
用P、V原语实现进程同步和互斥


例3 设有一个作业由四个进程组成，这 四个进程在运行时必须按图所示的顺序， 用P、V原语操作表达四个进程的同步关 系。
T 1 T 3 T 2
T 4


解：1）设同步（私有）信号量 s12，s13，s24，s34 分别用于T1与T2，T1与T3，T2与T4，T3与T4之间进 行同步 2）设初始值s12=0，s13=0，s24=0，s34=0 3）PV原语描述：
PA调用

PB调用




Send(1,m) Begin Local x P (bufempty[1]) 按FIFO方式选择一个空 缓冲区buf(x) Buf(x) <—— 消息m buf(x)置满标记 V(buffull[1]) End
eat V(s[i])
V (s[(i+1) mod 5])
Until false
用P、V原语实现哲学家问题(完整)
Pi:repeat



解：1）设公用信号量 mutex表示哲学家是否能同 时取到2个筷子，s[i]表示 是否能取到第I个筷子 （i=0,1,2,3,4 ） 2）设初始值 mutex=1，s[i]=1 （i=0,1,2,3,4 ） 3）描述第i个哲学家 Pi：
用P、V原语实现进程同步和互斥
例6：桌上有一空盘，允许存放一只水果。爸 爸可向盘中放苹果，也可向盘中放桔子，儿子 专等吃盘中的桔子，女儿专等吃盘中的苹果。 规定当盘空时一次只能放一只水果供吃者取用， 请用P，V原语实现爸爸，儿子，女儿3个并发 进程的同步。

解答

父亲进程()： { while(1) {P(empty); 儿子进程()： 往盘中放水果; if(水果==橘子) {while(没吃够) {P(orange); { V(orange); } 从盘中取橘子; else V(empty); { V(apple); } } } } }