v(mutex) end
注销过程：(`3’) begin p(mutex) //申请退房 找出自己的登记项，并删除该项的登记 v(mutex) v(empty) end.
5有一个阅览室，共有100个座位。为了很好地利用它，读者进入时必须先在登记表上进行登记。该表表目设有座位号和读者姓名；离开时再将其登记项擦除。
试问：为描述读者的动作，应编写几个程序，应设几个进程、它们之间的关系怎样？并请用P、V操作描述进程之间的同步算法。
解：为了描述阅览室，用一个登记表来记录其使用情况。表中共有100项。每当有读者进入阅览室时，为了正确地登记，各读者应互斥使用(1’)。为此设两个信号量：mutex为互斥信号量，用来制约各读者互斥地进行登记，其初值为1；empty为同步信号量，用来制约各读者能同时进入阅览室的数量，其初值为100 (2’)。 下面用两个过程描述对表格应执行的动作： 登记过程：(`2’) 擦除过程：(`2’) begin begin P(empty) P(mutex) P(mutex) 找到自己的登记项擦除 找到一个登记项登记 V(mutex) V(mutex) V(empty) end end 为了正确地描述读者的动作，可以将读者看成进程。若干读者希望进入阅览室时，调用登记过程，退出阅览室时，调用擦除过程(1’)。
可见，一个程序可对应多个读者。可设的进程数由读者数决定，其动作如下：(`2’) begin 调用登记过程 进入阅览室阅读 准备退出 调用擦除过程 end.
6一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过；但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。
解：假设一座桥由N个桥墩，也即最多允许有N个人同向过河，用一个计数器R记录同时过河的人数(2’)。用S1信号量保护计数器，其初值为1，R的初值为0；互斥使用桥的信号量用S表示，其初值为1。(2’) 同步算法描述如下： procedure goriver()
begin L:P(S1); //为同时过河,申请对计数器计数
If R>N begin V(S1); goto L; end //同方向过河的人站满桥墩时,重新申请计数 R=R+1; If R==1 P(S); //申请过河 V(S1); //释放计数器的使用权 (3’) 占有一个桥墩,并顺序过河到对岸; P(S1); R=R-1;
If R==0 V(S); //如果已经无同向的人过河,释放占用权 V(S1); (3’) end.
7在一个飞机订票系统中，多个用户共享一个数据库。各用户可以同时查询信息，若有一个用户要订票，须更新数据库时，其余所有用户都不可以访问数据库。请用P,V操作设计一个同步算法，实现用户查询与订票功能。要求：当一个用户订票而需要更新数据库时，不能因不断有查询者到来而使其长时间等待。利用信号量机制保证其正常执行。
解：这是典型的读者——写者问题，查询信息的用户是读者，订票用户是写者，并且要求写者优先。(2’) 变量说明：(`2’)
计数变量
rc——正在运行的查询者进程数目，初值为0. 信号量
Sw——控制订票者进程的活动，初值为1. Src——互斥使用rc变量，初值为1.
S——当订票者到达时封锁后续的读进程，初值为1. 读者进程 P(S) P(Src) rc=rc+1
if (rc==1) P(Sw) V(Src)
V(S) (2’) 查询库当中的信息 P(Src) rc=rc-1;
if (rc==0) V(Sw) V(Src) (2’)
写者进程 (`2’) P(S) P(Sw)
更新数据库内容 V(Sw)
V(S)
8某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
(2)根据所定义的信号量，把应执行的PV操作填入下述空格中，以保证进程能够正确地并发执行。
COBEGIN PROCESS PI(I=1，2，??) begin
进入售票厅； 购票；
退出； end COEND
(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。
答：(1)定义一信号量S，初始值为20。 (1’) 意义：(`3’=1’*3)
S>0 S的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有20名顾客(购票者) S<0 |S|的值为等待进入售票厅的人数 (2)上空格为P(S) (2’) ；下空格为V(S) (2’)
(3)S的最大值为20 (1’ )；S的最小值为20－n (1’ )
9在公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开门关门，当售票员关好车门后，驾驶员才能开车行使。试用P/V操作实现司机与售票员间的同步。
解答：semaphore mutex1=0,mutex2=0; (2’) main(){
cobegin driver() busman()
coend
} (2’) driver(){
while(true){
p(mutex1) 启动公共汽车 正常开车 到站停车
v(mutex2) }
} (3’) busman(){
while(true){
关车门 v(mutex1) 售票
p(mutex2) 开车门 上下乘客 }
} (3’)
10并发问题：设有两个优先级相同的进程p1, p2如下。令信号s1, s2的初值为0，已知z=2，试问p1, p2并发运行结束后x=? y=? z=? 进程p1 进程p2 y := 1 x := 1 y := y+2 x := x+1 v(s1) p(s1) z := y+1 x := x+y p(s2) v(s2) y := z+y z := x+z 解答：（分析过程略 2’）从结果来看，两个进程无论谁先谁后，结果都是一样的。(2’) x = 5; y = 12; z = 9 (6’)
11 试用信号量机制来描述下述前趋图
M1 M5 M2 M4 M3 M7
M8
解答：首先定义信号量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都为0，分别表示相对应的进程是否完成：(2’) COBEGIN (`8’=1’*8) Process M1: begin
V(S12)
M6