操作系统复习笔记(四)-白红宇

10.司机和售票员之间要协同工作:一方面只有售票员把车门关好了司机才能开车，因此售票员关好车门应通知司机开车;另一方面只有当汽车已经停下时,售票员才能开门让乘客上下客,司机停车后应该通知售票员,假定某辆汽车有一名司机和两名售票员,汽车当前正在始法站停车上客,

分析: 活动规律:

司机售票员(2名)

启动车辆上乘客

正常行驶关车门

到站停车售票

开车门

下乘客

售票员关好车门应该通知司机开车,因此要设置一个信号量用于司机判断是否可以启动车辆;此外，当汽车到站停下时,司机停车后要通知售票员,所以也要设置一个信号量用于通知售票员打开车门．由于有两名售票员，因此相应的信号量都需要设置两个.

begin

var stop1=0,stop2=0,run1=0,run2=0:semaphore;

cobegin

process driver

begin

repeat

p(run1);

p(run2);

启动车辆；

正常行驶；

到站停车；

v(stop1);

v(stop2);

end

process conductor1

begin

repeat;

上乘客；

关车门；

v(run1);

售票；

p(stop1);

开车门；

下乘客;

end

process conductor2

begin

repeat;

上乘客；

关车门；

v(run2);

售票；

p(stop2);

开车门；

下乘客;

end

coend

end

注:这是售票员优先的方式,若以司机优先的方式,程序如下:

begin

var stop1=0,stop2=0,run1=0,run2=0:semaphore;

cobegin

process driver

begin

repeat

正常行驶；

到站停车；

v(stop1);

v(stop2);

p(run1);

p(run2);

end

process conductor1

begin

repeat;

p(stop1);

开车门；

售票；

关车门；

v(run1);

end

process conductor2

begin

repeat;

p(stop2);

开车门；

售票；

关车门；

v(run2);

end

coend

end

11.两个学校之间有一条路,其中从s到t一段路每次只允许一辆车通过,但中间有一个小的"安全岛"M(同时允许两辆车停留),可供两辆车已经从两端进入小路的情况下错车使用.

分析:由于安全岛M仅仅允许两辆车停留,本应该作为临界资源而要设置信号量,但根据题意,任意时刻进入安全岛的车不会超过两辆(两个方向最多各有一辆),因此，不需要为M设置信号量,在路口s和路口t都需要设置信号量,以控制来自两个方向的车对路口资源的争夺.这两个信号量的初值都是1.此外，由于从s到t的一段路只允许一辆车通过,所以还需要设置另外的信号量用于控制,由于M的存在,可以为两端的小路分别设置一个互斥信号量.

begin

var s=1,t=1,sk=1,lt=1:semaphore;

cobegin

process p1

begin

repeat

p(s);

p(sk);

通过sk路段；

进入安全岛M;

v(sk);

p(lt);

通过lt路段；

v(lt);

v(s);

until false

end

process p2

begin

repeat;

p(t);

p(lt);

通过sk路段；

进入安全岛M;

v(lt);

p(sk);

通过lt路段；

v(sk);

v(t);

until false

end

coend

end

12.有一个理发师,一把理发椅和n把供等候理发的顾客坐的椅子,若没有顾客,则理发师睡觉,当一个顾客到来时,必须唤醒理发师进行理发,若理发师正在理发,又有顾客到来,则若有空椅子可坐就坐下来等,若没有空椅子就离开.

分析:需要设置一个信号量barber,初值为0,用于控制理发师和顾客之间的同步关系.还需要设置一个信号量customer,初值为0,用于离开顾客与等候顾客之间的同步控制,为了记录等候的顾客数,应该设置一个计数器count,初值为0.当一个顾客到达时,需要在count上做加1操作,并根据count值的不同分别采取不同的动作，当顾客离开时,要对count上做减1操作,并根据count值的不同分别采取不同的动作;由于count是共享变量,因此要互斥使用，为此设置一个互斥信号量mutex;

begin

var barber=0,customer=0,count=0,mutex=1:semaphore;

cobegin

process barber

begin

repeat

p(customer);

p(mutex);

count = count -1;

v(barber);

v(mutex);

理发;

until false

end

process customer

begin

repeat;

p(mutex);

if(count<n)

{

count = count +1;

v(customer);

p(barber);

理发；

}

else

{

v(mutex);

离开；

}

until false

end

coend

end

注:变形:有3个理发师,3把理发椅子,n把供等候理发的顾客坐的椅子.由于有3位理发师,所以一次同时可以为三个顾客服务,设置信号量max_capacity,用于表示空闲椅子的数量,初值为n.信号量barber_chair表示空闲理发师(椅)的数量,初值为3;信号量cust_ready,finished,leave_b_chair分别表示是否有顾客到来,理发完成,离开理发椅,它们的初值都为0;

begin

var max_capacity=n,barber_chair=3,cust_ready=0,finished=0,leave_b_chair = 0:semaphore;

cobegin

process barber

begin

repeat

p(cust_ready);

理发;

until false

end

process customer

begin

repeat;

p(max_capacity);//是否有空闲椅子；

进入店里；

p(barber_chair);//是否有空闲的理发椅；

坐在理发椅上；

v(cust_ready);//唤醒理发师；

p(finished);//是否完成理发；

离开理发椅；

v(leave_b_chair);

离开店；

v(max_capacity);

until false

end

coend

end

13.进程p0,p1共享变量flag,turn;他们进入临界区的算法如下:

var flag:array[0..1] of boolean;//初值为false

turn:01

process i (0或1)

while true

do begin

flag[i] =true;

while turn!=i

do begin

while flag[j]==false

do skip;//skip为空语句

turn = i

end

临界区;

flag[i] = false;

出临界区;

end

该算法能否正确地实现互斥?若不能,应该如何修改(假设flag,turn单元内容的修改和访问是互斥的).

分析:不能正确实现互斥.考虑如下情况:process0先执行到flag[0] = true,process1开始执行,进入内循环时,将turn设置为1;此时进程调度转到process0,process0可以进入内循环,由于flag[1]的值为true,所以process0再次将turn的值设置为0,重复上述操作,两个进程谁也不能进入临界区.

var flag:array[0..1] of boolean;//初值为false

turn:01

process 0

while true

do begin

flag[0] =true;

turn = 1

while flag[1]==true and turn = 1

do skip;//skip为空语句

临界区;

flag[0] = false;

出临界区;

end

process 0

while true

do begin

flag[1] =true;

turn = 0

while flag[0]==true and turn = 0

do skip;//skip为空语句

临界区;

flag[1] = false;

出临界区;

end

容易证明这种方法保证了互斥,对于进程0,一旦它设置flag[0]为true,进程1就不能进入其临界段.若进程1已经在其临界段中，那么flag[1]=true并且进程0被阻塞进入临界段.另一方面,防止了相互阻塞,假设进程0阻塞于while循环,这意味着flag[1]为true,而且turn=1,当flag[1]为false或turn为0时,进程0就可进入自己的临界段了.

本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2006/08/28/488556.html，如需转载请自行联系原作者