操作系统习题2(含答案)

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

联系客服:779662525#qq.com(#替换为@)