V(mutex_flag); p(mutex_queue);
将print分配给queue队首进程； queue下移； V(mutex_queue); } }
21. 试用管程实现单一资源的管理。 解：
TYPE single_resource=MONITOR; Var state: (free,used);//资源状态 q: condition;//等待队列 define require, release; PROCEDURE require; BEGIN
IF state=used THEN wait(q); state:=used; END;
PROCEDURE release; BEGIN
state:=free; signal(q); END;
BEGIN state:=free END;
22. 虽然管程是互斥进入的，但管程中定义的外部子程序必须是可再入的，试说明原因。 答：管程互斥是在变量级别的，同一管程类型可以有多个实例，而管程内部子程序只在管程类型定义时生成一套代码，为保障对不同管程变量的操作具有相同语义，管程外部子程序必须是可再入的。
23. 编写一个管程，使得调用进程能够等待若干指定时间单位(ticks)．可以假定有一个硬件实时钟，每隔一个tick时间单位调用该管程一次。
解：两个外部过程：sleep用于进程等待指定时间，tick用于时钟中断记数和唤醒等待进程。 TYPE sleep_interval=MONITOR; Var count: integer;//tick计数 q: condition;//等待队列 define sleep, tick;
PROCEDURE sleep(interval:integer);
26
BEGIN
count:=interval wait(q); END;
PROCEDURE tick; BEGIN
count:=count-1; IF count=0 THEN signal(q); END;
BEGIN END;
24. 管程与会合这两种同步机制之间的主要差别何在?
答：管程与会合都属于集中式结构化同步机制，但二者的实现机理完全不同。管程是被动性语言成分，管程本身不能占有处理机，管程外部子程序是由调用进程占有处理机执行的。会合是主动性语言成分，一个任务调用另一任务中的入口时，入口代码是由被调用任务自己占有处理机执行的。
25. 试用会合给出读写问题的解法，要求写者优先．
解：定义一个任务，包含如下四个入口：start_read,finish_read,
start_write,finish_write。该问题的关键是：strat_write的入口条件不应考虑当前读者情况，当会合发生后再判断当前是否有读者，并与其finish_read会合。这里显然需要accept语句的嵌套。
task readers_and_writers is start_read; finish_read; start_write; finish_write;
end readers_and_writers;
task body readers_and_writers is read_count,write_count:integer; read_count:=0; write_count:=0; loop select
when write_count=0 => accept start_read do
read_count:=read_count+1; end start_read
or when read_count>0 => accept finish_read do read_count:=read_count-1;
27
end finish_read;
or when write_count=0 =>//也许当前有读者 accept start_write do
while read_count>0 do//等待读者读完 accept finish_read do read_count:=read_count-1 end finish_read end while
write_count:=write_count+1; end start_write
or when write_count>0 => accept finish_write do
write_count:=write_count-1; end finish_write end select; end loop;
end readers_and_writers;
26. 关于读者/写者问题,有人给出如下改进解法: semaphore r_w_w, mutex, s; (初值均为1) int count; (初值为0) 读者活动： P(s); P(mutex); count++;
if (count= =1) P(r_w_w); V(mutex); V(s); {读操作} P(mutex); count--;
If (count= =0) V(r_w_w); V(mutex);
写者活动： P(s); P(r_w_w); {写操作} V(r_w_w); V(s);
分析上述改进算法的调度效果。
答：由于s以及读者和写者对s的操作，读者和写者都不会无限等待，因而算法不会出现饿死现象，是一个公平的解法
28
五、 死锁习题及解答:
1．下面关于死锁问题的叙述哪些是正确的，哪些是错误的，说明原因。
(1) 参与死锁的所有进程都占有资源；
(2) 参与死锁的所有进程中至少有两个进程占有资源； (3) 死锁只发生在无关进程之间； (4) 死锁可发生在任意进程之间。
答：说法（1）是错误的，应该是参与死锁的所有进程都等待资源。如下图所示，参与进程p1、p2、p3、p4，尽管p3、p4不占有资源，但也卷入死锁。
说法(2)正确。 参与死锁的进程至少有两个，设为p1,p2，p1占有资源r1而等待资源r2，p2占有资源r2而等待资源r1。
说法(3)错误。死锁也可能发生在相关进程之间，如p1和p2也可能是相关进程。 说法(4)正确，死锁既可能发生在相关进程之间，也可能发生在无关进程之间。即死锁可发生在任意进程之间。
2． 试证明当每个资源类中仅有一个资源实例时，资源分配图中的环路是死锁的充要条件。
证明：已知必要条件成立，即发生死锁必存在环路，下面只需证明充分条件，即在每类资源仅有一个实例的前提下，环路意味着死锁。假定环路上共有k个进程(k32)，设这k个进程为p1,p2,?,pk。p1等待p2占有的资源r1，p2等待p３占有的资源r２，?，pk等待p１占有的资源rk。显然，这k个资源类中的所有资源实例均被环路上的进程所占有，环路外的进程有关资源的任何释放动作必不涉及这k类资源，因而无法使环路上的等待进程解除等待状态，因而这k个进程将无限期地等待下去，即发生死锁。证毕。
3．什么叫饥饿？什么叫饿死？什么叫活锁？举例说明之．
答：在一个动态系统中，资源请求与释放是经常性发生的进程行为。对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。资源分配策略可能是公平的(fair)，能保证请求者在有限的时间内获得所需资源；资源分配策略也可能是不公平的(unfair)，即不能保证等待时间上界的存在。在后一种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予
29
的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。 考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿以至饿死。
与饥饿相关的另外一个概念称为活锁(live lock)，在忙式等待条件下发生的饥饿，称为活锁。例如不公平的互斥算法。
4． 死锁与饿死之间有何相同点和不同点?
答：饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面：
(1) 从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死；
(2) 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)；
(3) 死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死；
(4) 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。
饥饿和饿死与资源分配策略(policy)有关，因而防止饥饿与饿死可从公平性考虑，确保所有进程不被忽视，如FCFS分配算法。
5． 何谓银行家算法的保守性? 举例说明之。
答：银行家算法的保守性是指银行家算法只给出了进程需要资源的最大量，而所需资源的具体申请和释放顺序仍是未知的，因而银行家只能往最坏处设想．
考虑资源集合R={A(1),B(1)}，进程集合P={p1,p2}，已知进程p1和进程p2的活动序列分别为：p1：a,b,,; p2：b,,b,a,,。显然p1和p2的资源最大需求量均为A(1)，B(1)。假定某时刻系统状态如下：
Claim AllocationNeed Available ABABABAB
p1:11100101 p2:110011
即此时p1的a被系统接受。 其后系统接收到的命令有两种可能，一是p1的请求b，二是p2的请求b。 假定为p2的请求b，因Request[2]=(0,1)￡Need[2]=(1,1)，故该请求是合
30