-
CH3
应用题参考答案
1
、
有三个并发进程：
R
负责从输入设备读入信息块，
M
负责对信息块加工处理；
P
负责打
印输出信息块。今提供；
l
）一个缓冲区，可放置
K
个信息块；
2
）二个缓冲区，每个可放置
K
个信息块；
试用信号量和
P
、
V
操作写出三个进程正确工作的流程。
答：
1 ) var B :
array [ 0 , k-1 ] of item
sread : semaPhore : = k
smanage : semaPhore : = 0
swrite : semaphore : = 0
rptr : integer : = O
mptr
: integer : = O
wptr
：
integer : = 0
x : item
cobegin
process reader
process manager process
writer
begin
begin begin
LI : read a message intox L2
: P ( smanage ) L3 : P
( swnte )
P
(
sread
)
;
x:=B[mptr];
x:=B[swrite];
B[rptr]:=x;
mptr:=(mptr+1)
mod
k;
wptr:=(wptr+1) mod k;
Rptr:=(rptr+1)
mod
k;
manage
the
message
in
x;
V(sread);
V(smanage);
B[mptr]:=x;
print the message in x;
Goto
L1;
V(swrite);
goto L3;
End;
goto
L2;
end;
End;
coend
2 ) var A , B :array [ 0 , k -l ] of
item
sPut1 : semaphore:=k;
SPut2: semaPhore:=k;
sget1
: semaPhore : = 0
sget2 : semaphore
: = 0
put1
：
integer
：
=O
put2
：
integer : =
0
get1
：
integer
：
=O
get2 :
integer : = O
cobegin
process
reader
;
processn
manager;
process Writer
begin
begin
begin
Ll
:
read
a
message
into
x
;
L2
:
P
(
sgetl
)
;
L3
:
P ( sgetZ )
P
(
SPut1
)
;
x
:
=
A
[
get1]
;
x
:
= B [get2];
A
[put1]:=x
;
get1
：
(get1+1
)
mod
k
;
get2:=
（
get2 + l )
mod k
Put1:=(put1+1)
mod
k;
V(sput1);
V(sput2);
V(sget1);
manage
the
message
into
x;
print the message in x;
Goto
L1;
P(sput2);
goto L3;
Put2:=(put2+1) mod k;
V(sget2);
Goto L2;
End;
Coend
2
设有
n
个进程共享一个互斥段，如果：
(
1
）每次只允许一个进程进入互斥段；
( 2
）每次最多允许
m
个进程（
m
簇
n
）同时进入互斥段。
试问：所采用的
信号量初值是否相同？信号量值的变化范围如何？
答：所采用的互斥信号量初值不同。
1
）互斥信号量初值为
1
，变化范围为［
-n
＋
l , 1
］。
当没有进程进入互斥段时，信号量值为
1
；当有
1
个进程进入互斥段但没有进
程等待进入互斥段时，信号量值为
O
；当有
1
个进程进入互斥段且有一个
进程
等待进入互斥段时，信号量值为
-1
；最多可能有
n
-1
个进程等待进入互斥段，
故此时信号量的值应为
-<
/p>
（
n - 1
）也就是
-n+1
。
2
）互斥信号量初值为
m
，变化范围为
［
-n
＋
m , m
］。
当没有进程进入互斥段时，信号量值为
m
；当有
1
个进程进入互斥段但没有进
程等待进入互斥段时，信号量值为
m - 1
：当有
m
个进程进入互斥段且没有一
个进程等待进入互斥段时，信号量值为
0
：当有
m
个进程进入互斥段且有一个
进程等待进入互斥段时，信号量值为一
l
；最多可能有
n - m
个进程等待
进入
互斥段，故此时信号量的值应为
-(n-m)
也就是
-n+m.
3
有
两个优先级相同的进程
P1
和
P2
，各自执行的操作如下，信号量
S1
和
S2
初
值均为
0<
/p>
。试问
Pl
、
P2
并发执行后，
x
、
y
、
z
的值各为多少？
P1:
P2:
Begin
begin
Y:=1;
x:=1;
Y:=y+3;
x:=x+5;
V(S1);
P(S1);
Z:=Y+1;
X:X+Y;
P(s2);
V(S2);
Y:=z+y;
z:=z+x;
End
end
答：现对进程语句进行编号，以方便描述．
P1 :
P2 :
begin
begin
y : = 1
；①
x :=1
⑤
y :=y+3
；②
x
：
x+5
⑥
V(S1);
P(S1);
Z:Y+1
；③
x
：
X
＋
Y
;
⑦
P(s2);
V(S2);
Y:=z+y;
④
z
：
=Z+X
；⑧
End
end
①
、②
、⑤
和⑥
是不相交语句，可以任何次序交
错执行，而结果是唯一的。
接着无论系统如何调度进程并发执行，当执行到语句⑦
时，可以得到
x = 10 ,
y = 4
。按
Bernstein
条件，语句③
的执行结果不受语句⑦
的影响，故语句
③
执行后得到
z
=
5
。最后，语句④
和⑧
并发执行，这时得到了两种结果为：
语句④
先执行：
x =10 , y =9 , z= 150
语句⑧
先执行：
x =10 , y =19 , z =15
此外，还有第三种情况，语句③
被推迟，直至语句⑧
后再执行，于是
依次执行
以下三个语句：
7
：二
z + X :
z : =
y + 1
y :
＝
Z
十
y
这时
z
的值只可能是
y
＋
1=5
，故
y
=Z
＋
Y=5 +
4=9
，而
x = 10
。
第三种情况为：
x = 10
，
Y=9 , Z = 5
。
4
有一
阅览室，
读者进入时必须先在一张登记表上登记，
该表为每一座
位列出一
个表目，
包括座号、
姓名，<
/p>
读者离开时要注销登记信息；
假如阅览室共有
100
个
座位。试用：
l
）信号量和
P
、
V
操作；
2
）管程，来实现用户进程的同步算
法。
答：
1
）使用信号量和
P
、
v
操作：
var name
：
array [
l
?
100]of A
A
= record
number
：
integer
name
：
string
end
for i : = 1 to 100 do
{A [ i ].number
：
i
；
A [
i ].name :null;}
mutex , seatcount :
semaphore
i : integer
；
mutex : = l seatcount : =
100
cobegin
{
process readeri ( var
readename
：
string )
（
i=1 , 2
?
)
{
P ( seatcount )
P
（
mutex )
for i
: = 1 to 100 do i++
if A [ i
].name
＝
null then A [ i ].nam
e
：
readername
；
reader get the seat
number=i
；
/*A[I].number
V ( mutex )
进入阅览室，座位号
i
，座下读书；
P ( mutex
)
A[i]name
：
null
V
（
mutex )
V(seatcount);
离开阅览室；
}
}
coend
2
）使用管程操作：
TYPE readbook=monitor
VAR
R: condition
I,seatcount
：
integer;
name
：
array [
l:100] of string
DEFINE rcadercome,
readerleave
USE check , wait ,
signal , release
Procedure
readercome ( readername )
begin
check ( IM )
if
seatcount
≥
100 wait ( R,IM )
seatcount : = seatcount + 1
for i=1 to 100 do i++
if
name[i] ==null then name[i]:= readername;
get the seat number = i
release ( IM )
end
procedure readerleave ( readername )
begin
check ( IM )
seatcount--;
for i = 1 to 1
00 do i++
if
name
［
i
］
readername then name
［
i
］
:null;
release ( IM )
end
begin
seatcount : =
1OO name:
＝
null
end
cobegin
{
process readeri ( i = 1 , 2
．?
）
begin
readercome ( readername
）
;
read the book
readerleave (
readername
）
;
leave the readroom;
end
}
coend.
5.
在一个盒子里，
混装了数量相等的黑白围棋子·
现在
用自动分拣系统把黑子、
白子分开，设分拣系统有二个进程
P1
和
P2
，其中
P1
拣白子；
P2
拣黑子。规
定每个进程每次拣一子；
当一个进程在拣时，
不允
许另一个进程去拣；
当一个进
程拣了一子时，必须让另一个进程
去拣．试写出两进程
P1
和
P2
能并发正确执
行的程序。
答
1
：实质上是两个进程的同步问题，设信号量
s1
和
s2
分别表示可拣白子和
黑子，不失一般性，若令先拣白子。
var
S1 , S2 : semaphore;
S1 : = l; S2
：
=0;
cobegin
{
process P1
begin
repeat
P( S1 )
拣白子
V ( S2 )
until false
end
process P2
begin
repeat
P ( S2 )
拣黑子
V (S1 )
until false
end
}
coend .
答
2 :
TYPE
pickup-chess = MONITOR
VAR flag :
boolean
S-black , s-white : codition
;
DEFINE pickup-black , pickup-white
USE wait,signal , check , release
procedure pickup-black
begin
check(IM )
if flag then wait(s-black,IM )
flag :
＝
true;
pickup a black;
signal(S-white,IM);
release ( IM )
end
procedure pickup-white
begin
check ( IM )
if not flag then wait(S-white,IM );
flag :=false
pickup a
white
signal ( S-black,IM )
release ( IM )
end
begin
flag:=true
end
main ( )
{
cobegin
process -B ( )
process -W ( )
coend
}
process-B ( )
begin
-black ( )
other
end
process-W ( )
begin
-white( )
other
end
6
管程的同步机制使用条件变量和
wait
及
signal
，尝试为管程设计一
种仅仅
使用一个原语操作的同步机制。
答：可以采用形如
waituntil
＜条件表达式＞的同步原语。如
waituntil
( numbersum + number < K )
表
示进程由于条件不满足而应等待，当进程号累
加和小于
K
时，系统应唤醒该进程工作．
7
设公共汽车上，司机和售票员的活动分别如下：
司机的活动：启动车辆：正常行车；到站停车。
售票员的活动：关车门；售票；开车门。
在汽车不断地到站、
停车、
行驶过程中，
< br>这两个活动有什么同步关系？用信号量
和
P
、
V
操作实现它们的同步。
答：
在汽车行驶过程中，
司机活动与售票员活动之间的同步关系为：
售票员关车
门后，
向司机发开车信号，
司机接到开车信号后启动车辆，
在汽车正常行驶过程
中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司
机启
动车辆的动作必须与售票员关车门的动作取得同步；
售票员开车门的动作也
必须与司机停车取得同步。应设置两个信号量：
S1
、
S2
;S1
表示是否允许司机
启动汽车（其初值为
0
)
;S2
表示是否允许售票员开门（其初值为
0
）。用
P
、
v
原语描述如下：
var S1 ,
S2 : semaphore
S1=0
；
S2=0
；
cobegin
{
driver ( )
busman ( )
}
coend
driver ( )
begin
while ( 1 ) {
P ( S1 )
启动车辆；正常行车；到站停车；
V ( S2 )
}
end
busman ( )
begin
while ( 1 ) {
关车门；
V ( 51 )
售票
;
P ( S2 )
开车门；
上下乘客；
}
end
8
、一个快餐厅有
4
类职员：
( l
）领班：接受顾客点菜；
( 2
）厨师：准备顾
客的饭菜；
( 3 )
包工：将做好的饭菜打包；
( 4
）
出纳员：收款并提交食品。
每个职员可被看作一个进程，
试用一
种同步机制写出能让四类职员正确并发运行
的程序。
答：典型的进程同步问题，可设四个信号量
51
、
S2
、
S3
和
S4
来协调进程工
作。
var S1 , S2 ,S3 , S4 : semaphore
S1 : = 1 S2
：
=S3 : = S4 : = 0
cobegin
{ process P1
begin
repeat
有顾客到来；
P ( S1 )
；
接受顾客点菜；
V ( 52 )
；
untile false
；
end
process
P2
begin
repeat
P (S2 )
准备顾客的饭菜；
v ( S3 )
;
untile false
end
process P3
begin
repeat
P (S3 )
将做好的饭菜打包；
V ( S4
)
untile false
end
process P4
begin
repeat
P( 54 )
;
收款并提交食品；
V (
51 )
ufltile false
end
}
coend .
9
、在信号量
S
上作
P
、
v
操作时，
S
的值发生变化，当
S>
0
、
S=0
、
S< 0
时，
它们的的物理意义是什么？
答：
S
的值表示它代表的物理资源的使用状态：
S
>
0
表示还有共享资源可供使
用。
S
阅表示共享资源正被进程使用但没有进程等待使用资源。
S
<
0
表示资源
已被分配完，还有进程等待使用资源。
10 ( 1
）两个并发进程并发执行，其中，
A
、
B
、
C
、
D
、
E
是原语，试给出
可能的并发执行路径。
Process P Process Q
begin begin
A D
B E
C end :
end
( 2
）两个并发进程
P1
和
P2
并发执行，它们的程序分别如下：
P
1 P2
repeat
repeat
k:=k
×
2
print k
k:=k+1 k:=0
until false until false
若令
k
的初值为
5
，让
P1
先执行两个循环，然后，
P1
和
P2
又并发执行
< br>了一个循环，写出可能的打印值，指出与时间有关的错误。
答：
( 1
）共有
10
种交错执行的路径：
A
、
B
、
C
、
D
、
E;
A
、
B
、
D
、
E
、
C; A
、
B
、
D
、
C
、
E
;
A
、
D
、
B
、
E
、
C; A
、
D
、
B
、
C
、
E;
A
、
D
、
E
、
B
、
C
D
、
A
、
B
、
E
、
C;
D
、
A
、
B
、
C
、
E; D
、
A
、
E
、
B
、
C
; D
、
E
、
A
、
B
、
C
。
( 2
）把语句编号，以便于描述：
P1 P2
repeat repeat
k:=k
×
2
；①
printk
；③
k:=k+l
；②
k:=0
；④
until false
until false
l ) K
的初值为
5
，故
P1
执行两个循环后，
K = 23
。
2
）语句并发执行有以下情况：
①
、②
、③
、④
，这时的打印值为：
47
③
、④
、①
、②
，这时的打印值为：
23
①
、③
、②
、④
，这时的打印值为：
46
①
、③
、④
、②
，这时的打印值为：
46
③
、①
、②
、④
，这时的打印值为：
23
③
、①
、④
、②
，这时的打印值为：
23
由于进程
P1
和
P2
并发执行，共享了变量
K
，故产生了‘结果不唯一’。
11
证明信号量与管程的功能是等价的：
( l
）用信号量实现管程；
( 2
）用管程实现信号量。
答：
( 1
）用信号量实现管程；
Hoare
是用信号量实现管程的一个例子，
详见课文内容。
下面介绍另一种简单方
法：
每一个管程都对应一个<
/p>
mutex
，
其初值为
1
，
用来控制进程互斥调用管程。
再设一个初值为
0
的信号量，用来阻塞等待资源的进程。相应的用信号量实现
的管程库过程为：
Var
mutex,c:semaphore
mutex:=1 c:=0
void enter-monitor ( )
/*
进入管程代码，保证互斥
P (
mutex )
}
void leave-
monitor-normally (
)/*
不发信号退出管程
{
V ( mutex )
}
void leave-with-sigal(c)
/*
在条件
c
上发信号并退出管程，释放一个等
待
c
条件的进程。｛注意这时没有开放管程，因为刚刚被释放的进程己在管程
中。
V ( c )
}
void wait(c)
/*
等待条件
c
，开放管程
{
V ( mutex )
P (c)
}
( 2
）用管程实现信号量。
TYPE
semaphore=monitor
VAR S condition
C:integer
DEFINE P
, V
USE check , wait , signal ,
release
procedure P
begin
check ( IM )
C:= C-1 :
if C < 0 then
wait ( S,IM )
release ( IM )
end
procedure V
begin
check ( IM ) :
C : = C + 1
if
C
≤
0 then signal ( S,IM )
release ( IM )
end
begin
C:=
初值
;
End.
12
证明消息传递与管程的功能是等价的：
( 1
）用消息传递实现管程；
( 2
）用管程实现消息传递。
答：
( 1
）用消息传递实现管程；
用消息传递可以实现信号量（见
13 ( 2 ) )
，用信号量可以实现管程（见
11
(1 ) )
，那么，把两种方法结合起来，就可以用用消息传递实现管程。
( 2
）用管程实现消息传递。
TYPE mailbox=monitor
VAR r
, k , count:integer
buffer <
/p>
：
array[0
?
n-1] of message
full ,
empty:condition
DEFINE add , get
USE check , wait , signal , release
procedure add ( r )
begin
check ( IM )
if count=n then wait (
full,IM )
buffer
[r]:=message
r:
＝
(r+1) mod n
count:=count + 1
if count
= 1 then sighal ( empty , IM )
release ( IM )
end
procedure get ( m )
begin
check ( IM )
if count = 0 then wait (
empty , IM )
m:=buffer [
k
」；
count : = count-1
if
count
＝
n-1 then signal ( full
, IM )
release ( IM )
end
begin
r:= 0
; k:= 0 count:=0
end
13
证明信号量与消息传递是等价的：
(
1
）用信号量实现消息传递；
(
2
）用消息传递实现信号量。
答：
( l
）用信号量实现消息传递；
1
）
把消息队列组织成一个共享队列，
用一个
互斥信号量管理对该队列的入队操
作和出队操作
.
2
）发送消息是一个入队操作，当队列存储区满时，设计一个
同步信号量阻塞
send
操作。
3
）
接收消息是一个出队操作，
当队列存储区空时，
设计另一个同步信号量阻塞
receive
操作。
( 2
）用消息传递实现信号量。
l
）
为每一个信号量建立一个同步管理进程，
它包含了一个计数器，
记录信号量
值；还为此信号量设立一个等
待进程队列
2
）应用进程执行
P
或
V
操作时，将会调用相应
P
、
V
库过程。库过程的功能
是：
把应用进程封锁起来，
所执行的
P
、
V
操作的信息组织成消息，
执行
send
发
送给与信号量对应的同步管理进程，之后，再执行
receive
操作以接收同步管
理进程的应答。
3
）
当消息到达后，
同步管理进程计数并查看信号量状态。
如果信号量的值为负
的话，执行
P
操作的应用进程被阻塞，挂到等待进程队列
，所以，不再要送回
答消息。此后，当
V
操作执行完后，同步管理进程将从信号量相应队列中选取
一个进程唤醒，
并回送一个应答消息。
正常情况下，
同步管理进程
回送一个空应
答消息，然后，解锁执行
P
、
V
操作的应用程序。
14
使用（
1
）消息传递，
(
2
）管程，实现生产者和消费者问题。答：
(
1
）见
课文
ch3 3.5.4
节。（
2
）见课文
Ch3 3.4.3
节。
15
试利用记录型信号量和
P
、
V
操作写出一个不会出现死锁的五
个哲学家进餐
问题的算法。答：
var forki:array
[0
?
4] of semaphore
forki:=1
cobegin
{
process Pi /*
i = 0 , 1 , 2 , 3 */
begin
L1 :
思考：
P(fork[i]) / * i =4,P(fork
[0]) * /
P(fork[i+1] mod 5) / * i
=4P
（
fork
[4]
）
* /
吃通心面；
V (fork[i]
;
V (fork([i+1] mod 5 )
goto L1
end
}
coend
16 Dijkstra
临界区软件算法描述如下：
var
flag
：
array[0
?
n] of (idle,want-in
，
in_cs )
turn:integer tune:0 or 1 or
?
or , n-1
process
Pi(i=0,1
，?
,n-1)
var j integer
begin
repeat
repeat
flag [i] :want_in
while
turn
≠
1 do
if
flag[turn]==idle then turn:=i
flag[i]:= ip_cs
j:=0
while (j < n ) & (j==1 or flag[j]
≠
in_cs )
do j:=j
+ 1
until j
≥
n
:
critical section
flag
[i]:=idle
??
until false
end .
试说明该算法满足临界区原则。
答：为方便描述，把
Dijkstra
程序的语句进行编号：
repeat
flag[i]:=want_in
；①
while
turn
≠
i do
②
if
flag[trun]==idle then turn:=i
；③
flag[i]: =
in_cs
；④
j:= O
while(j < n ) & (j==1 or flag[j]
≠
in_cs
）⑤
do j:=j + 1
@
until j
≥
n
critical section
flag[i]
:=idle
；⑦
?
( l
）满足互斥条件
当所有的巧都不在临
界区中，满足
flag[j]
≠
in_
cs
（对于所有
j
,
j
≠
i
）条件
时，
Pi
才能进入它的临界区，而且进程
Pi
不会改变除自己外的其他进程所对
应的
flag[j]
的值。另外，进程
Pi
总是先置自己的
flag[j]
为
in_cs
后，才去
判别
Pj
进程的
flag[j]
的值是否等于
in_cs
所以，
此算法能保证
n
个进程互斥
地进入临界区。
( 2
）不会发生无休止等待进入临界区
由于任何一个进程
Pi
在执行进入临界区代码时先执行语句①
，其相应的
flag[i]
的值不会是
idle
。注意到
flag[i]
＝
in_cs
并不意味着
turn<
/p>
的值一定
等于
i
。我们来看以下情况，不失一般性，令
turn
的初值为
0
，且
P0
不工作，
所以，
flag[turn]=fl
ag[0]=idle
。
但是若干个其他进程是可能同时交替执
行的，
假设让进程
Pj(j=l
,
2
,
?
n
-l
）
交错执行语句①
后
（这时
flag[j]=want_in
）
，
再做语句②
（第一个
while
语句），来查询
flag[turn]
的状态。显然，都满足
< br>turn
≠
i
，所以，都可以执行语句③
，让自己的
turn
为
j
。但
t
urn
仅有一个
值，该值为最后一个执行此赋值语句的进程号，
设为
k
、即
turn=k
(1
≤
k
≤
n
-1
）。接着，进程
Pj(j=1,
2,
?
n-l
)
交错执行语句④
，于是最多同时可能有
n-1
个进程处于
in_cs
状态，但不要忘了仅有一个进程能成功执行语句④
，将
加
m
置为自己的值。
假设｛
P1
,
P2
，?
Pm
｝是一个己将
flag[i]
置为
in_cs
(
i
=1,2,
?
,m
)
( m
≤
n
-1
）的进程集合，并且已经假设当前
turn=k (
1
≤
k
≤
m
)
，则
Pk
必
将在有限时间内首先进入临界区。
因为集合中除了
Pk <
/p>
之外的所有其他进程终将
从它们执行的语句⑤
（第二个
while
循环语句
）
退出，
且这时的
j
值必小于
n
，
故内嵌
until
起作用，返回到起始语句①
重新执行，再次置
flag [ i ] =
want_in
，继续第二轮循环，这时的情况不同了，
flag[turn]
=flag[ k]
必定
≠
idle
（
而为
in_cs
< br>）
。
而进程
Pk
发现最终除自身外的所有进程
Pj
的
flag[j]
≠
in_cs
，并据此可进入其临界区。
17
另一个经典同步问题：吸烟者问题
(patil , 1971
）。三个吸烟者在一个房
间内，还有一个香烟供应者。为了制造
并抽掉香烟，每个吸烟者需要三样东西：
烟草、
纸和火柴，
供应者有丰富货物提供。
三个吸烟者中，
第
一个有自己的烟草，
第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西
放在桌子
上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，
供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试采用：
(
1
）信号量和
P
、
v
操作，
( 2
）管程编写他们同步工作的程序。答：
( 1
）用信号量和
P
、
v
操作。
vars , S1 ,S2 , S3 semaphore
S:=1 S1:=S2:=S3:=0
fiag1 , flag2 , fiag3 : Boolean
fiag1:=flag2:=flag3:=true;
cobegin
{
process
供应者
begin
repeat
P(S)
取两样香烟原料放桌上，由
flagi
标记；
/
*
nago1
、
nage2
、
nage3
代表烟草、纸、火柴
if flag2 & flag3 then V(S1) /
＊供纸和火柴
else
if flag1 & fiag3 then V(S2 ) /
＊供烟草和火柴
else
V(S3) /
＊供烟草和纸
untile
false
end
process
吸烟者
1
begin
repeat
P(S1)
取原料；
做香烟；
V(S)
吸香烟；
untile false
;
process
吸烟者
2
begin
repeat
P
(S2 )
取原料；
做香烟；
V(S)
吸香烟；
untile false
;
process
吸烟者
3
begin
repeat
P
(S3 )
取原料；
做香烟；
V ( S )
吸香烟；
untile false
;
coend .
( 3
）用管程。
TYPE mskesmoke=moonitor
VAR
S, S1 ,S2 ,S3 : condition
flag1 ,
flag2, flag3 : boolean
DEFINE give ,
take1 , take2 , take3
USE check ,
wait , signal , release
procedure
give
begin
check ( IM )
准备香烟原料；
if
桌上有香烟原料
then wait( S , IM )
把准备的香烟原料放桌上；
if
fiag2 & flag3 then signal ( S1
,IM
）
;
if flag1 &
flag3 then signal ( S2 ,IM ) else signal (S3 ,
IM )
release ( IM )
end
procedure take1
begin
check(IM):
if
桌上没有香烟原料
then
wait ( S1 ,IM
）
;
else
取原料；
signal ( S , IM )
release ( IM )
end
procedure take2
begin
check ( IM ) :
if
桌上没有香烟原料
then wait(S2,IM);
else
取原料；
signal ( S , IM )
release
（
IM
）
;
end
procedure take3
begin
check ( IM ) :
if
桌上没有香烟原料
then
wait(S3,IM);
else
取原料
signal ( S
,IM )
release ( IM )
end
begin
flag1:=flag2:=flag3:=true;
end.
cobegin
{
process
供应者
begin
repeat
Call ();
??
until false
end
process
吸烟者
1
begin
repeat
Call 1()
做香烟，吸香烟；
until
false
end
process
吸烟者
2
begin
repeat
Call 2()
做香烟，吸香烟；
until
false
end
process
吸烟者
3
begin
repeat
Call 3();
做香烟，吸香烟；
until
false
end
}
coend .
18
、
如图所示，四个进程
Pi
（
i=0
?
3
）和四个信箱
Mj
(j=0
?
3 )
，进程
间借助相邻信箱传递消息，即
Pi
每次从
Mi
中取一条消息，经加工后送入
M(i
+
1)
mod4
，其中
M0
、
M1
、
M2
、
M3
;
可存放
3
、
3
、
2
、
2
个消息。初始状态
下，
MO
装了三条消息，其余为空。试以
P
、
V
为操作工具，写出
Pi
（
i=0
?
3
）
的同步工作算法
答：
var mutexl ,
mutexZ , mutex3
，
mutex0
:semaphore;
Mutex1
＝
< br>nutex2:=mutex3:=mutex0:=1;
Empty0,empty1,empty2, empty3;
semaphore;
empty:=0 empty1:=3
empty:=2:=empty3:=2;
full0 , full1 ,
full2 , full3:semphore
full0:=3;full1:=full2:=full3:=0;
in0,in1,in2,in3,out0
,out2,out3,;intger;
in0:=in1:
＝
in2:
＝
in3:=out0:
=out1:=out2:=out3:=0;
cobegin
{
process P0
begin
repeat
P(full0);
P(mutex0);
从<
/p>
M0[out0]
取一条消息；
out0:=(out0+1) mod 3
V(mutex0);
V(empty0)
加工消息；
P(empty1)
P(mutex1)
消息已
M1[in1];
In1:=(in1+1) mod 3;
V(mutex1)
V(full1 )
untile false
end
process P1
begin
repeat
P ( full1 )
P ( mutex1 )
从
M1[out1]
取一条消息；
Out1:=(out1+1) mod 3
V(mutex1);
V(empty1);
加工消息
;
P(empty2);
P(mutex2 )
消息己
M2[in2];
In2:=(in2+1) mod 2;
V(mutex2
)
v ( full2 )
untile
false
end
process P2
begin
repeat
P(full2)
P(mutex2 )
从
M2
[out2]
取一条消息；
out2:=(out2 + l ) mod 2;
V(mutex2)
V(empty2)
加工消息；
P(empty3)
P(mutex3)
消息己
M3[in3];
in3:=(in3+1) mod 2
V(mutex3)
V(full3)
untile false
end
process P3
begin
repeat
P(full3)
P(mutex3)
从
M3[out3]
取一条消息
;
out3:=(out3+1)mod 2;
V
(mutex3)
V (empty3)
加工消息；
P ( empty0
)
P ( mutex0 )
消息己
MO[in0];
In0:=(in0+1) mod 3
V(mutex0)
V(full0)
untile false
end
{
coend
19
、有三组进程
Pi
、
Qj
、
Rk
，其中
Pi
、
Qj
构成一对生产者和消费者，共享
一个由
< br>M1
个缓区构成的循环缓冲池
buf1
。
Qj
、
Rk
凡构成另一对生产者和消费
者，
共享一个由
M2
个缓冲区构成的循环缓冲池
buf2
。
如果
Pi
每次生
产一个产
品投入
buf1,Qj
每次从
中取两个产品组装成一个后并投入
buf2
，
< br>Rk
每次从中取
三个产品包装出厂
.
试用信号量和
P
、
V
操作写出它们同步工作的程序。
答：
var mutex1 ,
mutex2 , mutex3 : semaphore;
empty1 ,
empty2 , full1 , full2 semaphore
in1 , in2 , out1 , out2 : integer
counter1 , counter2:integer
buffer1:
array[0
?
M1-1] of item
buffer2:array[0
?
M2-1]of item
;
empty1:=M1 empty:=M2;
in1 : = in2 :=out1:=out2:=0
counter1:=counter2:=0
fun1:=full2:
＝
mutex1:=mutex2:=mutex3:=1;
cobegin
{
process Pi
begin
L1:
P(empty1)
P(mutex1 )
put an
item into buffer [in1]
in1:=(in1+1) mod M1
counter++;
if counter1 = 2 then {
counter1:=0;V(full1);}
V(mutex)
goto L1;
end
process Qj
begin
L2:
P ( full2)
P ( mutex1 )
take an item from buffer1[out1];
out1:=(out1+1) mod M1;
take
an item from buffer1[out1]
out1:=(out1 + 1) mod M1
V
( mutex1 )
V ( empty1 )
V ( empty1 )
Process the
products
P ( emPty2)
P
( mutex2 )
put an item into buffer2
[ in2 ]
in2:=( in2 + l ) mod M2
counter2 + +
if counter2
= 3 then { counter2:=0 V( full2 ) }
V ( mutex2)
goto L2
process Rk
begin
L3 :
P ( full2 )
P ( mutex2 )
take an item
from buffer2 [out2];
out2: = ( out2 + 1
) mod M2
take an item from buffer2
[out2]
out2:=( out2 + 1) mod M2
take an item from buffer2 [out2];
out2:=(out2 + 1 ) mod M2
v
( mutex2 )
V ( empty2 )
V ( empty2 )
V ( empty2 )
;
packet the products
goto L3
end
}
coend
20
在一个实时系统中，有两个进程
P
和
Q
，它们循环工作。
P
每隔
1
秒由脉
冲寄存器获得输入，并把它累计到整型变量
W
上，同时清除脉冲寄存器。
Q
每
隔
1
小时
输出这个整型变量的内容并将它复位。系统提供了标准例程创
PUT
和
OUT
卫
UT
供拍，提供了延时系统调用
Delay
(
seconds
）。试写出两个
并发进
程循环工作的算法。
答：
Var W
,V:integer;
Mutex:semaphore;
W:=0 V:=0 mutex:1;
cobegin {
process P
begin
repeat
P(mutex)
delay (1)
V
＝
INPUT
W:=W + V
清除脉冲寄存器；
V
(mutex) untile false
end
process Q
begin
repeat
P ( mutex )
delay ( 60 )
OUTPUT ( W
)
W : = 0
V ( mutex )
;
untile false
}
coend .
21
系统有同类资源
m
个，被
n
个进程共享，问：当
m
>
n
和
m
≤
n <
/p>
时，每个进
程最多可以请求多少个这类资源时，使系统一定不会发
生死锁？
答：当
m
≤
n
时，每个进程最多请求
1
个这类资源
时，系统一定不会发生死锁。
当
m
>
n
时，如果
m/n
不整除，每个进程最多可以请求”商＋
1
”个这类资源，
否则为”商”个资源，使系统一定不会发生死锁？
< br>
22 N
个进程共享
M <
/p>
个资源，
每个进程一次只能申请释放一个资源，
< br>每个进程最
多需要
M
个资源，所
有进程总共的资源需求少于
M+N
个，证明该系统此时不会
产生死锁。
答卜设
max
(
i
）表示第
i
个进程的最大资源需求量，
need
(
i
）表示第
i
个
进程还需要的资源量，
alloc
( i
）表示第
i
个进程已分配的
资源量。由题中
所给条件可知：
max ( 1
）
+
?
+max( n ) = ( need
(1)+
?
+need( n ))+((alloc(1)+
?
源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。
）个时，这时至少系统还有
+alloc(n))
如果在这个系统中发生了死锁，那么一方面
m
个资源应该全部分配出去，
alloc
(1)
＋?
+alloc ( n
）
=m
另一方面所有进程将陷入无限等待状态。可以推出
need(1)+
?
+need
(n)< n
上式表示死锁发生后，
n
个进程还需要的资源量之和小于
n
，这意味着此刻至
少存在一个进程
i
, need ( i ) = 0
，即它已获得了所需要的全部资源。既然
该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资
答
2
：由题意知道，
n
×
m < m + n
是成立的，
等式变换
n
×
( m - 1 ) + n < n + m
即
n
×
(m-
1) < m
于是有
n
×
(
m-1 ) + 1
或
n
×
(
m-1 ) + 1
≤
m
这说明当
n
个进程都取得了最大数减
1
个即（
m-
1
一个资源可分配。故该系统是死锁无关的。
23
一条公路两次横跨运河，两个运河桥相距
100
米，均带有闸门，以供船只通
过运河桥。
运河和公路
的交通均是单方向的。
运河上的运输由驳船担负。
在一驳
船接近吊桥
A
时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾
P
通
过此桥为止。对吊桥
B
也按同样次序处理。一般典型的驳船长度为
200
米，当
它在河上航行时是否会产生死锁？若会，
说
明理由，
请提出一个防止死锁的办法，
并用信号量来实现驳船的
同步。
答：当汽车或驳船未同时到达桥
A
时
，以任何次序前进不会产生死锁。但假设
汽车驶过了桥
A
，它在继续前进，并且在驶过桥
B
之前，此时有驳船并快速地
通过了桥
A
，驳船头到达桥
B
，这时会发生死锁。因为若吊起吊桥
B
让驳船通
过，
则汽车无法通过桥
B
；
若不吊起吊桥
B
让汽车通过，
则驳船无法通过桥
B <
/p>
。
可用两个信号量同步车、船通过两座桥的动作。
var Sa , Sb : semaphore
Sa:=Sb:=1
cobegin
{
process
驳船
begin
P(Sa )
P(Sb )
船过桥
A
、
B
V(Sa )
;
V(Sb )
end
process
汽车
begin
P ( Sa )
P ( Sb )
车过桥
A
、
B
V ( Sa )
V ( Sb )
end
}
coend
24 Jurassic
公园有一个恐龙博物馆和一个花园
，
有
m
个旅客租卫辆车，
每辆
车仅能乘一个一旅客。旅客在博物馆逛了一会，然后，排队乘坐旅行车
，挡一辆
车可用喊飞它载入一个旅客，再绕花园行驶任意长的时间。若
< br>n
辆车都己被旅
客乘坐游玩，
则想坐车的旅客需要等待。
如果一辆车己经空闲，
但没有游玩的
旅
客了，
那么，
车辆要等待。
试用信号量和
P
、
V
操作同步
m
个旅客和
n
辆车子。
答：这是一个汇合机制，有
两类进程：顾客进程和车辆进程，需要进行汇合、即
顾客要坐进车辆后才能游玩，开始时
让车辆进程进入等待状态
var sc1 , sck ,
sc
，
Kx,xc
，
mutex : semaphore
sck:=kx:=sc:=xc:=0
；
sc1:=n
；
mutex : =
1
sharearea
：一个登记车辆被服务乘客信息的共享区；
cobegin
process
顾客
i ( i = 1 , 2
，?
）
begin
P ( sc1 )
/
＊车辆最大数量信号量
P ( mutex ) /
＊封锁共享区，互斥操作
在共享区
sharearea
登记被
服务的顾客的信息：起始和到达地点，行驶时
间
V ( sck ) /*
释放一辆车
,
即顾客找到一辆空车
P
（
Kx
）
;
/*
待游玩结束之后，顾客等待下车
V ( sc1 )
/*
空车辆数加
1
End
Process
车辆
j(j=1,2
,3
?
)
Begin
L:P(sck);
/*
车辆等待有顾客来使用
在共享区
sharearea
登记那一辆车被使用，并与顾客进程汇合；
V(mutex);
/*
这时可开放共享区，让另一顾客雇车
V(kx);
/*
允许顾客用此车辆
车辆载着顾客开行到目的地；
V(xc);
/*
允许顾客下车
Goto L;
End
coend
25
今有
k
个进程，它们的标号依次为
1
、
2
、?
、
k
，如果允许它们同时读
文件
file
，
但必须满足条件：
参加同时读文件的
进程的标号之和需小于
K
，
请
使用：
1
）信号量与
P
、
v
操作，
2
）管程，编写出协调多进程读文件的程序。
答
1 : l
）使用信号量与
P
、
v
操作
var waits , mutex :semphore
numbersum:integer:=0
wait:=0
；
mutex:=1
;
cobegin
{
process readeri ( var number:integer )
begin
P(mutex )
L:if
numbersum+number
≥
K
then
{
V
(
mutex
)
;
P
(
waits
)
;
goto
L
;
}
Then
numbersum:numbersum+number;
V (mutex )
;
Read file
P(mutex )
numbersum: = numbersum-number
V(waits )
V(mutex )
2
）使用管程：
TYPE
sharefile = MONITOR
VAR numbersum ,n :
integer
SF : codition
DEFINE startread , endread
USE wait , signal , check , release
procedure startread ( var number
：
integer : )
begin
check (IM )
L :if
（
number +
numbersum )
≥
K then
{wait(SF,IM) goto L }
Numbersum:=numbersum+number;
release (IM )
end
procedure endread (var
number:integer )
begin
check(IM )
numbersum : = numbersum - number
signal ( SF , IM )
release ( IM )
end
begin
numbersum:=0
end .
main()
{
cobegin
process-i()
coend
}
process-i()
var number :
integer
begin
number :
＝进程读文件编号；
startread(number);;
read F
;
endread(number)
end <
/p>
26
、设当前的系统状态如下：系统此时
Available=(1,1,2):
l
）计算各个进程还需要的资源数
Cki - Aki ?
( 2
）系统是否处于安全状态，为什么？
( 3 ) P2
发出请求向量
request2 ( 1 , o , 1 )
，系统能把资源分给它吗？
( 4
）若在
P2
申请资源后，若
P1
发出请求向量
req
够
stl ( 1 ,0, l )
，系
统能把资源分给它吗？
( 5
）若在
P1
申请资源后，若
P3
发出请求向量
request3 ( 0
,0
，
l )
，系
统能把资源分给它吗？
答：
( 1 ) P1 , P2 , P3 , P4
的
Cki . Aki
分别为：
( 2 , 2 , 2
）、（
1 ,
0 , 2
）、（
1 , 0 , 3
）、（
4 , 2 , 0 ) ( 4
）系统处于安全状态，存在安
全序：
P2 , P1 ,
P3 , P4
( 5
）可以分配，存在安全序列：
P2 , P1 , P3 ,
P4 .
( 6
）不可以分配，资源不足。
( 7
）不可以分配，不安全状态。
27
系统有
A
、
B
、
C
、
D
共
4
种资源，在某时刻进程
PO
、
Pl
、
PZ
、
P3
和
P4
对资源的占有和需求情况如表，试解答下列问题：
系统此时处于安全状态吗？
若此时
P2
发出
request2 ( 1
、
2
、
2
、
2 )
，系统能分配资源给它吗？为什
么？
答：
( l
）系统处于安全状态，存在安全序列：
P0, P3 , P4
, P1 , P2
。
( 2
）不能分配，否则系统会处于不安全状态。
28
把死锁检测算法用于下面的数据，并请问：
Available=(1,0,2,0)
( l
）此时系统处于安全状态吗？
( 2
）若第二个进程提出资源请求
request2( 0 , 0
, 1 , 0 )
系统能分配资
源给它吗？
(3
）执行（
2
）之后
，若第五个进程提出资源请求
request5( 0 ,0 ,1 ,0
)
系统
能分配资源给它吗？
答：
( l
）此时可以找出进程安全序列：
P4 , P1 , P5 ,
P2 , P3
。故系统处
于安全状态。
( 2
）可以分配，存在安全序列：
P4 , P1 , P5,
P2 , P3
。
( 3
）不可分配，系统进入不安全状态。
29
）考虑一个共有巧
0
个存储单元的系统，如下分配给三个进程，
P1
最大需
求
70
，己占有
25
;
以
P2
最大需求
60
，己占有
40
;
P3
最大需求
60
，己占
有
45
。使用银行家算法，以确定下面的任何一个请求是否安全。（
l
) P4
进
程到达，
P4
最大需求
60
，最初请求
25
个。（
2
)
P4
进程到达，
P4
最大需求
60
，最初请求
35
。如果安全，找出安
全序列；如果不安全，给出结果分配情
况。
答：
( l
）由于系统目前还有
150-25-40-45=40
个单元，
P4
进程到达，把
25
个单
元分给它。这时系统还余
15
个单元，可把
15
个单元分给
P3
，它执行完后会
释放
60
个单元。
于是可供
P1
（还要
45
个单元）
,
P2
（还要
20
个单元）
,
P4(
< br>还
要
35
个单元
)
任何一个执行。
安全序列为：
（
1
）
P4
进程到达，
P4
最大需求
60
，最初请求
35
。如果把
35
个单元分给
P4
，
< br>系统还余
5
个单元，不再能满足任何一个进程的需求，系
统进入不安全状态。
30
有一个仓库，
可存放
X
、
Y
两种产品，
仓库的存储空间足够大，
但要求：
(
l
）
每次只能存入一种产品
X
或
Y , ( 2
）满足
-N
＜
X
产品数量
-Y
产品数量＜
M
。
其中，
N
和
M
是正整数，
试用信号量与
P
、
V
操作实现产品
X
与
Y
的入库过程。
答：本题给出的表达式可分解为制约条件：
-N < X
产品数量
-Y
产品数量
X
产品数量
-Y
产品数量＜
M
也就是说，
X
产品的数量不能比
Y
产品的数量少
N
个以上，
X
产品的数量不能
比
Y
产品的数量多
M
个以上。可以设置两个信号量来控制
X
、
Y
产品的存放数
量：
SX
表示当前允许
X
产品比
Y
产品多入库的数量，即在当前库存量和
Y
产品不
入库的情况下，
还可以允许
SX
个
X
产品入库；
< br>初始时，
若不放
Y
而仅放
X
产品，
则
SX
最多为
M-1
个。
sy
表示当前允许
Y
产品比
x
产品多入库的数量，即在当前库存量和
x
产品不
入库的情况下，还可以允许
sy
个
Y
产品入库．初始时，若不放
X
而仅放
Y
产
品，则
sy
最多为
N
-1
个。当往库中存放入一个
X
产品时，则允许存入
Y
产品
的数量也增加
1
，故信号量
sy
应加
1
：当往库中存放入一个
Y
产品时，则允
许存入
X
产品的数量也增加
1
，故信号量
sx
应加
1 .
var mutex
: semaphore = 1 /*
互斥信号量＊
/
sx , sy : semaphore;
sx =
M-1 sy = = N - l
cobegin
{
process X
｛
repeat
P(sx )
P
（
mutex )
将
X
产品入库；
V(mutex )
V ( sy )
until false
}
process Y
{ repeat
P ( sy )
P
（
mutex )
将
Y
产品入库；
V
（
mutex )
V (
px )
until false
}
}
coend .
31
有一个仓库可存放
A
、
B
两种零件，
最大库容量各为
m
个。
生产车间不断地
取
A
和
B
进行装配，每次各取一个
．为避免零件锈蚀，按先入库者先出库的原
则。
有两组供应商分
别不断地供应
A
和
B
，
每次一个。
为保证配套和合理库存，
当某种零件比另一种零件超过
n ( n < m
）个时，暂停对数量大的零件的进货，
集中补充数量少的零件．试用信号量与
P
、
V
操作正确地实现它们之间的同步
关系。
答：按照题意，应满足以下控制关系：
A
零件数量
-B
零件数量≤
n B
零件数
量
-A
零件数量≤
n : A
零件数量≤
m B
零件数量≤
m
．四个控制关系分别用
信号量
sa
、
sb
、
empty1
和
empty2
实施。为遵循先入库者先出库的原则，
A
、
B
零件可以组织成两个循形队列，
并增加入库指针
in1
、
in2
和出库指针
out1
、
out2
来控制顺序。并发程序编制如下：
Var
empty1,empty2,full1,full2:semaphore;
Mutex ,sa,sb:semaphore;
In1,in2,out1,out2:integer;
B
uffer1,buffer2:array[0
?
m-1]o
f item;
Empty1:=empty2:=m;
Sa:=sb:=n;
In1:=in2=out1:=out2:=0;
Cobegin
{
Process
producerA
{repeat
P(empty1);
P(sa);
P(mutex);
Buffer1[in1]:=A
零件
;
In1:=(in1+1)mod m;
V(mutex);
V(sb);
V(full1);
Untile false;
}
Process producer B
{repeat
P(empty2);
P(sb);
P(mutex);
Buffer2[in2]:=B
零件
;
In2:=(in2+1)mod
m;
V(mutex);
V(sa);
V(full2);
Untile false;
}
Process take
{repeat
P(full1);
P(full2);
P(mutex);
Take from buffer1[out1] and buffer2[out
2]
中的
A
，
B
零件；
Out1:=(out1+1)mod m;
Out2:=(out2+1)mod m;
V(mutex);
V(empty1);
V(empty2);
把
A
和
B
装配成产品；
Until false
}
}
Coend.
32
进程
Al
、
A2
、?、
An1
通过
m
个缓冲区向进程
B1
、
B2
、?
、
Bn2
不断
地发送消息．发送和接收工作符合以下规则：
(
l
）每个发送进程每次发送一个消息，写进一个缓冲区，缓冲
区大小与消息长
度相等；
(
2
）对每个消息，
Bl
、
BZ
、二、
BnZ
都需接收一次，并读入各自的数据区内；
( 3
）当
M
个缓冲区都满时，则发送进程等待，当没有消息可读时，接收进程
等待．
试用信号量和
PV
操作编制正确控制消息的发送和接收的程序。
答：本题是生产者一消费者问题的一个变形，一组生产者
A1
, A2
，?
An1
和
一组消费者
B1
,
B2
，?
Bn2
共用
m
个缓冲区，每个缓冲区只要写
一次，但需
要读
n2
次。因此，可以把这一组缓冲区看成
n2
组缓冲区，每个发送者需要同
时写
n2
组缓冲区中相应的
n2
个缓冲区，而
每一个接收者只需读它自己对应的
那组缓冲区中的对应单元。
应设置一个信号量
mutex
实现诸
进程对缓冲区的互斥访问；两个信号量数组
empty[n2]
和
full[n2]
描述
n2
组缓冲区的使用情况．其同步关系描述如下：
var mutex ,
empty[n2],full[n2]:semaphore
i
:integer mutex=1
for(i=0;i<=n2-1;i++)
{
empty[i]=m;
Full[i]=0;
}
main ( )
{
cobegin
A1 (
)
A2 ( )
?
An1 ( )
B1 ( )
B2 ( )
?
Bn2 ( )
coend
send ( ) /
＊进程
Ai
发送消息＊
/
{ int i
for
（
i=0;i<=n2-1;
i++
）
;
P(empty[i]);
P (mutex )
将消息放入缓冲区；
V
（
mutex )
for(i
=0
；
i<=n2-1;i++)
V(full[i]);
}
receive (i)
/
＊进程
Bi
接收消息＊
/
{
P(full[i]);
P(mutex);
将消息从缓冲区取出；
v
（
mutex )
v (
empy[i])
Ai ( )
/
＊发送进程
A1 , A2
，?
An1
的程序类似，这里给出
进程
Ai
的描述＊
l {
{
While(1)
{
?
send ( )
?
}
}
Bi ( ) /
＊接收进程
Bl ,
B2
，?
BnZ
的程序类似，这里给出进程
Bi
描述＊
/
{
while(i)
(
?
receive ( i )
?
}
}
某系统有
R1
设备
3
台，
R2
设备
4
台，它们被
Pl
、
PZ
、
P3
和
P4
进程共享，
且己知这
4
个进程均按以下顺序使用设备：
一申请
Rl
一申请
R2
一申请
RI
～释放
Rl
一释放
R2
一释放
Rl
( 1
）系统运行中可能产生死锁吗？为什么？
( 2
）若可能的话，请举出一种情况，并画出表示该死锁状
态的进程一资源图．
答：
(
l
）系统四个进程需要使用的资源数为
Rl
各
2
台，
R2
各
1
台。可见资
源数不足，
同时各进程申请资源在先，
有可能产生死锁发生
的四个条件，
故系统
可能产生死锁。
(
2
）
当三个进程执行完申请资源
Rl
，
开始执行申请资源
R2
时，
第四个进程会因没有资源
Rl
而被阻塞。当三个进程执行完申请资源
R2
后，系
统还剩
1
个
R2
资源。而这三个进程因执行申请第二个资源
Rl
而全部被阻塞，
系统进入死锁。
34
如图所示，左右两队杂技演员
过独木桥，为了保证安全，请用
PV
操作和信
号量来解决过独木桥问题。
只要桥上无人，
则允许一方
的人过桥，
待一方的人全
部过完后，另一方的人才允许过桥。<
/p>
答：
var wait
，
mutex1
，
mutex2 , bridge1 , bridge2
: semaphore
mutex1:
＝
mutex2:=bridgel:=bridge2:=1;wait:=0;
counter1 , counter2 : integer
cobegin
{
process P
左
process P
右
begin begin
P ( mutex1 )
P ( mutex2 )
Count1 ++;
count2 ++
；
if
count1
=
1
then
P(
wait
)
; if
count2
=
1
then
P(
wait
)
;
V ( mutex1 )
; V( mutex2)
P(bridge1)
P ( bridge2 )
过独木桥；
过独木桥；
V (
bridge1) V(
bridge2 )
P ( mutex1)
P ( mutex2 )
Count1--
count2--
；
if
count1 = 0 then V(wait) if
count2 = 0 then P
(wait)
V
( mutex1) V
(mutex2)
end
end
} coend
35
修改读者一写者的同步算法，
使它对写者优先，
即一旦有写者到达，
后续的
读者必须等待，而无论是否
有读者在读文件。（
1
）用信号量和
P
、
v
操作实
现；
( 2
）用管程实现。
答：（
1
）用信号量和
P
、
V
操作实现
为了提
高写者的优先级，增加了一个信号量
S
，用于在写进程到达后封
锁后续的
读者。其控制流程如下：
Var rmutex,wmutex,s:semaphore;
Rmutex=1;wmutex=1;s=1;
Count:integer:=0;
Main()
{cobegin
Reader();
Writer();
Coend
}
Reader()
Begin
While(1)
{ P(s);
P(rmutex);
If(count==0)
P(wmutex);
Count++;
V(rmutex);
V(s);
读文件；
P(rmutex);
Count--;
If (count==0)
v(wmutex);
V(rmutex);
}
Writer()
Begin
While(1)
{
P(s);
P(wmutex);
写文件；
V(wmutex);
V(s);
}
End.
(2)
用管程实现
TYPE read-write=monitor
Var
rc,wc:integer;
R,W:condition;
DEPINE start-read , end-read , start-
riter , end-writer;
USE wait , signal ,
check , release
procedure start-
read;
begin
check ( IM ) :
if wc > 0 then wait ( R ,IM )
rc:=rc + 1;
signal ( R , IM
)
release ( IM )
end
procedure end-read
begin
check ( IM )
rc:=rc-1
If rc=0 then
signal ( W , IM )
release ( IM )
end
procedure
start-write
begin
check
( IM )
wc:=wc + 1
if
rc > 0 or wc > 1 then wait ( W , IM ) :
release ( IM )
end
procedure end-write
begin
check ( IM )
wc:=wc-1 :
if wc > 0 then signal ( W , IM )
else signal ( R , IM )
release ( IM )
end
begin
rc:=0; wc:=0 R:=0
W:=0
end .
Cobegin {
process P1
begin
??
call -read;
??
Read;
call -read
end
process P2
begin
??
Call -writer;
??
Write;
??
Call -write;
??
End;
}
Coend.
36
假定某计算机系统有
R1
和
R2
两类可再使用资源
（其中
R1
有两个单位，
R2
有
一个单位），它们被进程
P1,
P2
所共享，且已知两个进程均以下列顺序使用两
类资源．
→申请
R1
→申请
R2
→申请<
/p>
R1
→释放
R1
→释放
R2
→释放
R1
→
试求出系统运行过程中可能到达的死锁点，
并画出死锁点的资源分配图
（或称进
程→资源
图）。
答：当两个进程都执行完第一步（都占用
R1
）时，系统进入不安全状态。这时
无论哪个进程
执行完第二步，死锁都会发生。可能到达的死锁点：进程
P1
占
有
一个
R1
和一个
R2
，而进程
P2
占有一个
R1
。或者相反。这时己形
成死锁。进
程
--
资源图为：
37
、
某工
厂有两个生产车间和一个装配车间，两个生产车间分别生产
A
、
B
两
种零件，装配车间的任务是把
A
、
B
两种零件组装成产品。两个生产
车间每生
产一个零件后都要分别把它们送到装配车间的货架
Fl
、
F2
上，
F1
存放零件
A
,
F2
存放零件
B , Fl
和
F2
的容量均为可以存放
10
个零件。装
配工人每次从货
架上取一个
A
零件和一个
B
零件，然后组装成产品。请用：
(
l
）信号量和
P
、
V
操作进行正确管理，
( 2
）管程进行正确管理．
答：
( 1
）信号量和
P
、
V
操作进行正确管理．
var Fl
, F2 : ARRAY [ 0
?
9 ] of
item;
SP1 , SP2 , SI1 , SI2:seMaphore
in1 , in2
，
outl
，
outZ
：
integer
in1:=
0;in2:=0;out1:=0
；
out2:=0
；
SP1:=10;SP2:=10;SI1:=0;SI2:=0;
Main()
{cobegin
Producer1();
Producer2();
Installer()
Coend
}
Process producer1()
Begin
While(true)
{
Produce
A
零件；
P(SP1);
F1[in1]:A;
In1:=(in1+1) mod
10
V(SI1);
}
End
Process producer2()
Begin
While(true)
{
Produce B
零件；
P(SP2);
F2(in2):=B;
In2:=(in2+1) mod 10
V(SI2);
}
End
-
-
-
-
-
-
-
-
-
上一篇：(完整版)2019年高考英语阅读理解猜测词意
下一篇：全球机场三字代码表