内容发布更新时间 : 2024/5/20 8:23:41星期一 下面是文章的全部内容请认真阅读。
( 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 是用信号量实现管程的一个例子，详见课文内容。下面介绍另一种简单方法：每一个管程都对应一个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 ：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 个进程互斥