我的书签
添加书签
移除书签4.5 自测练习答案
一、填空题
1.进程同步
2.多路复用
3.直接制约和间接制约
4.信号量
5.临界资源
6.等待
7.1、1～-(m-1)
8.互斥、P(mutex)、V(mutex)
9.临界区
10.管程
11.M、M～-(N-M)
12.相应资源，P、V操作
13.同步、条件变量
14.发送、接收
15.s＞0、等待、就绪
16.2≤K≤M
17.互斥使用、忙则等待、有限等待、让权等待
18.动态策略
19.请求并保持、循环等待
20.死锁避免
二、单项选择题
1.B 2.A 3.B 4.B 5.B
6.A 7.B 8.C 9.B 10.A
11.D 12.A 13.B 14.C 15.D
16.B 17.B 18.C 19.A 20.C
21.D 22.A 23.B 24.A 25.D
26.D 27.D 28.B 29.B 30.A
三、不定项选择题
1.ACDEF 2.BCE 3.AD 4.ACDE 5.A
6.ACDE 7.CD 8.ABCD
四、是非题
1.正确
2.正确
3.错误：可以实现共享，但要通过互斥访问方式共享。
4.正确
5.错误：有安全序列则一定是没有死锁发生。不安全序列一定导致死锁，但不安全状态不一定是死锁状态。
6.错误：P、V操作不能防止死锁。
7.错误：P1与P3没有共享同一个临界资源，因而没有互斥关系。
8.错误：不是全部，如，内存是共享资源，但允许多个进程同时访问。
9.正确
10.错误：资源分配图中出现了环路，只能说明系统处于不安全状态，但不是所有不安全状态都能导致死锁状态。
11.正确
12.错误：管程中的过程是可中断的。
13.正确
14.错误：银行家算法是一种死锁避免算法，它不是严格限制产生死锁的必要条件，而是防止系统进入不安全状态。
15.错误：只有涉及死锁的进程处于阻塞状态。
16.正确
17.正确
18.错误：循环等待只是产生死锁的4个条件之一，当互斥、占有并等待、非抢占和循环等待这4个条件同时满足，才会出现死锁。
19.错误：参与死锁的所有进程都等待资源。
20.正确
五、综合题
1.答：并发进程的执行，实际上是进程活动的某种交叉或重叠，某些交叉次序可能得到错误结果。由于具体交叉的形成与进程的推进速度有关，而速度是时间的函数，因而将这种错误称为与时间有关的错误。
例如，在父子俩中，父亲存钱，儿子取钱的两个进程SAVE和TAKE如下：
int amount=0;
main()
{
创建进程SAVE;
创建进程TAKE;
}
SAVE()
{
int m1;
m1=amount;
m1=m1+1000;
amount=m1;
}
TAKE()
{
int m2;
m2=amount;
m2=m2-1000;
amount=m2;
}
假设父子俩可能会同时存钱和取钱，因此，两个进程是并发的。
将SAVE和TAKE进程分解为以下6程序段：
S1:m1=amount;S2:m1=m1+1000;S3:amount=m1;
T1:m2=amount;T2:m2=m2-1000;T3:amount=m2;
根据Bernstein条件，S1和T1可以并发执行；S2和T2可以并发执行；但S3和T3不可以并发执行。由于没有对amount进行互斥操作，当两个进程交替执行时，最后导致amount的值有可能不正确。
假设父亲先存了两次钱，但在第三次存钱的时候，儿子在取钱。如果最后被执行的语句顺序若是先S3后T3，则amount=1000；如果最后被执行的语句顺序若是先T3后S3，则amount=3000；而实际的amount应该为2000元。这就是发生了与时间有关的错误。
2.答：将PA和PB进程分解为以下6程序段，这6程序段具有相对的完整性，都可以作为一个单独的执行过程存在。
SA1:x:=1;
x:=x+1;
SA2:x:=x+y;
SA3:z:=x+z;
SB1:y:=1;
y:=y+3;
SB2:z:=y+1;
SB3:y:=y+z;
根据Bernstein条件
R(SA1)={x}，R(SA2)={x,y}，R(SA3)={x,z}，R(SB1)={y}，R(SB2)={y}，R(SB3)={y,z}
W(SA1)={x}，W(SA2)={x}，W(SA3)={z}，W(SB1)={y}，W(SB2)={z}，W(SB3)={y}
R(SA1)∩W(SB1)∪R(SB1)∩W(SA1)∪W(SA1)∩W(SB1)=空集
R(SA2)∩W(SB2)∪R(SB2)∩W(SA2)∪W(SA2)∩W(SB2)=空集
可知：SA1与SB1可以并发执行，SA2与SB2可以并发执行。SA3与SB3因变量交集不为空，而不能并发执行。因此SA3与SB3的执行顺序不同，可能会有不同的结果。
如果先执行SA3，则x=6，y=15，z=11；如果先执行SB3，则x=6，y=9，z=11。
3.答：将PA和PB进程分解为以下6程序段：
SA1:x:=1;
x:=x+1;
SA2:z:=x+1;
SA3:z:=x+z;
SB1:y:=1;
y:=y+3;
SB2:z:=y+1;
SB3:y:=y+z;
根据Bernstein条件，SA1与SB1可以并发执行，SA3与SB3可以并发执行。SA2与SB2因变量交集不为空，而不能并发执行。因此SA2与SB2的执行顺序不同，可能会有不同的结果。
如果先执行SA2，则x=7，y=9，z=5；如果先执行SB2，则x=5，y=7，z=3。
4.答：“忙式等待”是指不进入等待状态的等待。“让权等待”则是阻塞式等待，因为得不到共享资源而阻塞自己，让出CPU给其他进程。
两者相同之处是进程都不具备继续向前推进的条件。
不同之处在于“忙等待”进程不主动放弃CPU，尽管可能会被剥夺。通常是采用循环测试的方法不断检测自己是否可以进入临界区，浪费了CPU时间，因而是低效的；而处于“让权等待”的进程主动放弃CPU，是高效的。
5.答：从前驱图中可以看出，进程P1必须最先执行，P1运行前，其他进程必须等待。P1执行结束后，进程P2、P3、P4才可以开始执行。进程P5必须等到P2、P3、P4全部执行完成后，才可以开始执行。为了确保这一执行顺序，设4个同步信号量S2、S3、S4、S5分别表示进程P2、P3、P4、P5是否可以开始执行，初值均设为0。
进程同步操作描述如下（使用类C语言描述）：
6.答：mutex1和mutex2是两个公用信号量，用于控制进程对缓冲区1和缓冲区2这两个临界资源访问的互斥。avail1、full1、avail2、full2分别对应两个缓冲区，其中avail的初始值为1，表示可以利用的缓冲区的数目为1；full的初值为0，表示存在于缓冲区内的数据的个数为0。通过对这两组私用信号量的P、V操作，就实现了进程间的同步。
3个进程之间的同步描述如下（使用类C语言描述）：
7.【分析】
本题的难度较大，没有直接给出进程之间的制约关系，而是给出了一个数量上的控制公式。应将这一公式转化成对信号量的操作，不可直接在程序中用表达式来控制程序流程。
本题给出的第一个条件是常遇到的临界资源访问控制，可以用一个公用（互斥）信号量来控制。题目给出的第二个条件可以分解为两个表达式：（-N＜A产品数量-B产品数量）和（A产品数量-B产品数量＜M）。换言之，就是指存放A的操作次数不能比存放B的操作次数少N次以上，存放A的操作次数不能比存放B的操作次数多M次以上，即若只存放产品A，最多可以存放M-1个；若只存放产品B，最多可以存放N-1个。这两个条件等价于一个生产者-消费者问题，只是两个私用（同步）信号量的初始值有所不同而已。
答：产品A和产品B的入库过程如下所示（使用类C语言描述）：
semaphore mutex,sa,sb;
mutex=0;
sa=M-1;
sb=N-1;
cobegin
storeA();
storeB();
coend
storeA()
{
P(sa);
P(mutex);
store A;
V(sb);
V(mutex);
}
storeB()
{
P(sb);
P(mutex);
store B;
V(sa);
V(mutex);
}
8.答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自独立的速度向前推进。但由于它们共享某些临界资源，而产生了临界区问题。按规定进程必须互斥进入临界区。
本题给出的这种算法不能保证互斥，因而是不安全的。例如，本题目中的进程在执行期间可能会出现如下场景：
进程P0先执行enter-crtsec(0)，在执行期间，时间片到，P1执行enter-crtsec(1)，（可以看出进入临界区的enter-crtsec(i)不是一个原子操作，即enter-crtsec(i)对应的这段代码不是一个原子操作）。若进程P0执行完enter-crtsec(0)之后，进入临界区，此时时间片到，进程P1执行完enter-crtsec(1)后，也进入了临界区，此时进程P0和P1都执行完enter-crtsec(i)，而且都进入了临界区。此外，flag[0]和flag[1]的值仍为false（flag[0]和flag[1]初值均为false，可以看出enter-crtsec(i)中的语句没有任何互斥作用）。
9.【分析】
本题考察使用P、V操作实现进程同步的掌握情况。一般地，若要求进程B在进程A之后方可执行时，只需在进程B执行前进行P操作，而在进程A执行完时要对同一信号进行V操作即可。本题要求列出8个进程的控制关系，使题目显得较为复杂，但对进程之间的同步控制方法理解掌握透彻后，解答此类题目应不会感到困难。
通常的解题步骤如下：
1）确定进程数量、约束条件，以及进程之间的同步互斥关系。
2）确定设置信号量的种类、个数，以及为信号量赋初值。
3）使用类C或者类Pascal语言描述同步关系。
答：这些程序运行时之间的同步关系描述如下（使用类C语言描述）：
semaphore s13,s14,s15,s23,s24,s25;
semaphore s36,s48,s57,s68,s78;
s13=0;s14=0;s15=0;
s23=0;s24=0;s25=0;
s36=0;s48=0;s57=0;
s68=0;s78=0;
cobegin
prog1();
prog2();
prog3();
prog4();
prog5();
prog6();
prog7();
prog8();
coend
prog1()
{
do all work;
V(s13);
V(s14);
V(s15);
}
prog2()
{
do all work;
V(s23);
V(s24);
V(s25);
}
prog3()
{
P(s13);
P(s23);
do all work;
V(s36);
}
prog4()
{
P(s14);
P(s24);
do all work;
V(s48);
}
prog5()
{
P(s15);
P(s25);
do all work;
V(s57);
}
prog6()
{
P(s36);
do all work;
V(s68);
}
prog7()
{
P(s57);
do all work;
V(s78);
}
prog8()
{
P(s48);
P(s68);
P(s78);
do all work;
}
10.【分析】
本题要求写出的算法与前面的题目有所不同。这里的两类进程（读者进程和写者进程）控制机制是不相同的。对于写者进程，只能独占文件，即当有写者时，不能有其他进程运行；对于读者进程，可以与其他的读者进程共享文件，即当有读者进程时，只允许其他的读者进程进入，而不允许写者进程运行。此外，当全部正在运行的读者进程运行完成后，才允许其他的写者进程进入。
为了达到这一控制效果，引入一个变量rc，用于记录当前正在运行的读者进程数。每个读者进程进入系统后须对rc值加1。当rc值由0变为1时，说明是第一个读者进程进入，因此需要该读者进程对控制写者进程的信号量进行P操作，以便与写者进程互斥运行；当rc值由非0值增加时，说明不是第一个读者进程，此时控制写者进程的信号量已经经过P操作控制，禁止写者进程进入，因此不需要再次对该信号量进行P操作。
当读者进程退出时，须对rc做减1的操作。如发现减1后值变为0，说明是最后一个读者退出，因此需要该读者进程对控制写者进程的信号量进行V操作，以便使写者进程能够进入。
答：1）进程间的制约关系有3类：一是读者进程之间允许读；二是读者进程与写者进程之间必须互斥；三是写者进程之间必须互斥。
2）进程间控制的算法如下所示（使用类C语言描述）：
semaphore mutex1,mutex2;
mutex1=1;
mutex2=1;
int rc=0;
cobegin
reader();
writer();
coend
reader()
{
P(mutex1);
rc=rc+1;
if(rc==1)P(mutex2);
V(mutex1);
reading the file;
P(mutex1);
rc=rc-1;
if(rc==0)V(mutex2);
V(mutex1);
}
writer()
{
P(mutex2);
writing the file;
V(mutex2);
}
3）为了提高写者进程的优先级，我们增加一个信号量w，用以在写者进程到达封锁后继的读者进程。相应的控制算法如下：
semaphore mutex1,mutex2;
int rc,w;
mutex1=1;
mutex2=1;
rc=0;
w=1;
cobegin
reader();
writer();
coend
reader()
{
P(w);
P(mutex1);
rc=rc+1;
if(rc==1) P(mutex2);
V(mutex1);
V(w);
reading the file;
P(mutex1);
rc=rc-1;
if(rc==0) V(mutex2);
V(mutex1);
}
writer()
{
P(w);
P(mutex2);
writing the file;
V(mutex2);
V(w);
}
11.答：1）A和B进程的相互制约关系如下：当缓冲区满时，A进程不可写，必须等待；当缓冲区空时，B进程不可以读，必须等待。
2）A和B两进程的同步算法如下（使用类Pascal语言描述）：
var buffer :array 0..N-1 of T;
in,out:0..N-1;
var mutex,s1,s2:semaphore;
mutex:=1;s1:=0;s2:=N;
in:=out:=0;
procedure a:
begin
repeat
生产数据m;
P(s2);
P(mutex);
buffer(in):=m;
in:=(in+1)MOD N;
V(mutex);
V(s1);
forever
end
procedure b:
begin
repeat
P(s1);
P(mutex);
m:=buffer(out);
out:=(out+1)MOD N;
V(mutex);
V(s2);
消费m;
forever
end
其中，mutex是两个进程的同步互斥信号量，其初始值为1；s2是A进程进入的空缓冲区的个数，其初值为N；s1是缓冲区中装有数据的缓冲区的个数，其初值为0。
12.答：这是一个多进程互斥问题。图书阅览室有200个座位，需要设置互斥信号量S1，控制读者进程对座位的竞争；另外读者进入还是离开都必须在登记表中登记，而登记表只有一个，需要互斥访问，因此需要设置互斥信号量S2，控制读者进程对登记表的使用。设置两个互斥信号量的初值为S1=200，S2=1。
读者进程的并发过程描述如下（使用类C语言描述）：
semaphore S1,S2;
S1=200;
S2=1;
cobegin
process reader i()//i=1,2,…,200
{
P(S1);
P(S2);
在表中登记读者姓名、座位号、进入时间;
V(S2);
…
阅览图书;
…
P(S2);
在表中登记离开时间;
V(S2);
V(S1);
}
coend
13.答：使用类C语言描述并发过程：
semaphore S1,S2;
S1=200;
S2=1;
cobegin
enter();
exit();
coend
process enter()
{
P(S1);
P(S2);
在表中登记读者姓名、座位号、进入时间;
V(S2);
…
阅览图书;
}
process exit()//i=1,2,…,200
{
…
P(S2);
在表中登记离开时间;
V(S2);
V(S1);
}
14.答：管程是编程语言的组成部分，编译器可以识别管程，并用某种方式对其互斥做出安排。进入管程时的互斥由编译器负责，在任一时刻，用管程的程序员不需要关心编译器是如何实现互斥的，只需要将所有的临界区转换为管程中的过程即可，不会存在两个进程同时使用临界区的情况。
典型的处理方法是：当一个进程调用管程过程时，该过程的前几条指令将检查在管程中是否存在其他的活跃进程，若没有进程存在，则该调用进程可以进入管程；否则；该调用进程将被阻塞，直到另一个进程离开管程并将其唤醒。
对于同步的控制采用引入条件变量，以及相关的两个操作wait和signal。当管程过程发现自己无法继续运行下去时，会对某个条件变量执行wait操作，导致自己阻塞，将另一个等待在管程外的进程调入管程，这种自身阻塞直到管程中另一个进程对同一个条件变量执行signal操作而被唤醒。
管程实现生产者-消费者问题，设缓冲区的大小count=N。
采用类Pascal语言描述的管程：
montitor Producer_Consumer;
integer count;
condition full,empty;
procedure insert(item:integer);
begin
if count=N then wait(full);
insert_item(item);
count:=count+1;
if count=1 then signal(empty);
end;
function remove:integer;
begin
if count:=0 then wait(empty);
remove:=remove_item;
count:=count-1;
if count:=N-1 then signal(full);
end;
count:=0;
end monitor;
通过管程实现生产者-消费者问题：
procedure Producer;
begin
while true do
begin
item:=produce_item;
Producer_Consumer.instert(item)
end
end;
procedure Consumer;
begin
while true do
begin
item:=Producer_Consumer.remove;
consume_item(item)
end
end;
15.答：采用信箱方式的一种变体实现生产者-消费者问题。生产者和消费者分别创建足够容纳N条消息的信箱，在信箱创建时确定消息的数量为N,send和receive调用中的地址参数是信箱的地址。生产者向消费者发送包含实际数据的消息，消费者则向生产者发送空消息。当生产者进程试图向一个满的信箱发消息时，将被阻塞，直到信箱中的消息被取走。消费者进程首先向生产者进程发送N个空消息，生产者进程取走空消息并送回一条填充了内容的消息。
使用N条消息实现生产者-消费者问题：
procedure Producer;
begin
integer item;
message m;
while true do
begin
item:=produce_item;//生产产品
receive(Consumer,＆m);//等待消费者进程发送空消息
build_message(＆m item);//创建一个包含产品的待发送消息
send(Consumer,＆m);//发送消息给消费者
end
end;
procedure Consumer;
begin
integer item,i=0;
message m;
while i＜N do
begin
send(Producer,＆m)//发送空消息给生产者
i:=i+1;
end
while true do
begin
receive(Producer,＆m)//接收包含产品的消息
item:=extract_item(＆m);//将产品从消息中提取出来
send(Producer,＆m);//发送空消息给生产者
consume_item(item);//消费产品
end
end;
16.答：设置信箱最大的好处，就是发送进程和接收进程之间没有处理时间上的限制。一个信箱可考虑成发送进程和接收进程之间大小固定的私有数据结构，它不像缓冲区那样被系统内所有进程所共享，因此，发送进程和接收进程之间对信箱的操作不存在互斥的概念。
为了记录信箱中空格数和消息个数，设置信号量fromnum为发送进程的私用信号量，信号量mesnum为接收进程的私用信号量。fromnum的初值为信箱的空格数n，mesnum的初值为0。
用P、V操作来实现send原语和receive原语。
send(m):
begin local x
P(fromnum);
选择空格x;
将消息m放入空格x中;
置格x的标志为满;
V(mesnum);
end
receive(m):
begin local x
P(mesnum);
选择满格x;
把满格x中的消息取出放入m中;
置格x标志为空;
V(fromnum);
end
从这个实例中可以看出，调用send(m)和receive(m)的进程之间只存在同步关系，而不存在互斥关系。
17.答：证明如下。
设max(i)表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已经分配的资源量。由题设条件可知：
max(1)+max(2)+…+max(n)=need(1)+…+need(n)+alloc(1)+…+alloc(n)＜m+n
假设该系统发生死锁，那么m个资源应该全部分配出去，即
alloc(1)+…+alloc(n)=m
且所有进程将陷入无限等待状态，即所有进程的need＞0。由上述两式可得：
need(1)+…+need(n)＜n
上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，使得need（i）=0，即它已经获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放所占有的全部资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。
18.答：使用类Pascal语言描述如下。
begin
integer mutex,avail,full;
mutex:=1;
avail:=n;
full:=0;
cobegin
producer:
begin
L1:produce next product;
P(avail);
P(mutex);
add to buffer;
V(full);
V(mutex);
goto L1;
end
cosumer:
begin
L2:P(full);
P(mutex);
take data from buffer;
V(avail);
V(mutex);
goto L2:
end
coend
end
要使该操作流程产生死锁，只需改动P操作的顺序。能产生死锁的操作流程如下。
begin
integer mutex,avail,full;
mutex:=1;
avail:=n;
full:=0;
cobegin
producer:
begin
L1:produce next product;
P(mutex);
P(avail);
add data to buffer;
V(mutex);
V(full);
goto L1:
end
cosumer:
begin
L2:P(mutex);
P(full);
take data from buffer;
V(mutex);
V(avail);
goto L2:
end
coend
end
在这个流程中，由于生产者和消费者在生产和消费之前，都要对mutex进行P操作，因此会导致生产者进入临界区后（对mutex进行P操作后），因无缓冲区而被阻塞；消费者由于无法进入临界区，无法释放缓冲区，从而导致死锁。同样的，当消费者进入临界区后（对mutex进行P操作后），由于无可供使用而被阻塞；而生产者由于无法进入临界区，无法生产产品，从而导致死锁。
19.答：饥饿就是一个处于就绪状态的、可运行的进程，由于其他进程总是优先于它（如其他进程优先级比它高，并且是优先级调度），而被调度程序无限制地拖延而不能被执行。当饥饿到一定程度的进程所赋予的任务，即使完成也不再具有实际意义时，称该进程被饿死（starve to death）。
考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿，以至饿死。
饥饿和饿死与资源分配策略（policy）有关，在一个实际系统中，资源请求与释放是经常发生的进程行为。对于每类系统资源，操作系统需要确定一个分配策略，资源分配策略可能是公平的，能保证请求者在有限的时间内获得所需资源；资源分配策略也可能是不公平的，即不能保证等待时间上界的存在。在后一种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待，而发生了进程饥饿（starvation），甚至饿死。因而防止饥饿与饿死可从公平性考虑，确保所有进程不被忽视，如FCFS调度算法或者优先级调度算法中，采用动态优先级策略。
活锁（live lock）是一个与饥饿相关的概念。在忙式等待条件下发生的饥饿，称为活锁，如不公平的互斥算法。
20.答：饿死与死锁有一定相同点：二者都是由于竞争资源而引起的；但又有明显差别，主要表现在如下几个方面：
1）从进程状态考虑，死锁进程都处于等待状态，处于运行或就绪状态的进程并非处于等待状态，但却可能被饿死。
2）死锁进程等待永远不会被释放的资源，饿死进程等待会被释放的资源，但却不会分配给自己的资源，表现为等待时限没有上界（排队等待或忙式等待）。
3）死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死。
4）死锁一定涉及多个进程，而饥饿或被饿死的进程有可能只有一个。
5）在饥饿的情形下，系统中至少有一个进程能正常运行，只是饥饿进程得不到执行机会；而死锁则可能会使涉及的多个进程都得不到执行的机会，使整个系统最终崩溃。
21.答：概率为1/3。
假设每个进程读取3个记录的顺序为随机的，每种读取记录的顺序可能性一样；此时，每个进程读取3个记录的顺序为3！，即6种。两者结合则有6×6=36种可能的排列。不难看出，只要是两个进程第一次申请的记录相同，则不会发生死锁，即其中一个进程得到第一个记录，另外一个进程因为等待此记录而阻塞，不会申请其他记录，确保所有记录都可由第一个进程读完后再释放第二个进程。两个进程第一次同时申请记录1的排列有4种：
A：1，2，3；B：1，2，3
A：1，2，3；B：1，3，2
A：1，3，2；B：1，2，3
A：1，3，2；B：1，3，2
同理，两个进程第一次同时申请记录2的排列为4种，同时申请记录3的排列也为4种，也就是共有12种排列是不会发生死锁的，故系统保证不发生死锁的概率为12/36=1/3。
22.答：1）P、V操作是进程之间通过共享变量实现信息传递；而高级通信机制是由系统提供发送原语send与接收原语receive两个操作，进程间通过这两个操作进行通信，无须共享任何变量。
2）基本原理：操作系统是管理一个用于进程通信的缓冲池，其中的每个缓冲区单元可存放一条信息。想要发送消息时，发送者从中申请一个可用缓冲区buffer，接收者取出一条消息时再释放该buffer，每个进程均设置一条消息队列，任何发送给该进程的消息均暂存在其消息队列中。
3）缓冲区的格式说明：Sptr指示该消息的发送者，Nptr指向队列中下一个缓冲区的指针，Text为消息正文。设置互斥信号量mutex（其初值为1）与一个同步通信信号量sm（初值为0），sm也用于记录消息队列中现存消息的数目。
send(a)的操作如下：
begin
new(p);
P.Sptr=address of the sender;
Move message to bufferP;
Find the receiver;
P(mutex);
add bufferP to the message queue;
V(sm);
V(mutex);
end
23.答：司机与售票员两个进程之间的控制关系为同步关系。
对于算法1，两进程的主要控制关系为：首先司机启动车辆，当汽车到站司机停车后，售票员才可以开车门；当售票员关好车门后，司机才可以启动车辆。因此需要引入两个私有信号量，司机进程的私有信号量run，初值设为1；售票员进程的私有信号量close，初值设为0。
（1）P(run)
（2）V(close)
（3）P(close)
（4）V(run)
对于算法2，两进程的主要控制关系为：首先当售票员关好车门后，司机才可以启动车辆；当汽车到站司机停车后，售票员才可以开车门。因此需要引入两个私有信号量，司机进程的私有信号量run，初值设为0；售票员进程的私有信号量close，初值设为0。
（5）P(run)
（6）V(close)
（7）V(run)
（8）P(close)
24.【分析】
在此题中，一方面需要对死锁产生的必要条件明确掌握，而且还需要对可用资源向量、进程的资源分配向量，以及进程的需求向量的概念有所了解。
资源向量是用向量的形式表示资源的数量。每一类资源对应向量中的一个元素。在本题中，系统有3类资源，因此表示资源情况的向量有3个元素，分别表示为这3类资源的数量。系统可用资源向量中的数量表示出系统当前可用的资源数目，进程的分配向量表示该进程已获得的资源数量，而需求向量则表示该进程还需要分配的资源数量。
本题解题的关键在于：分析题目所给出的在阻塞时对资源的处理方式，根据处理方式与系统死锁的必要条件的比较来分析系统是否会产生死锁。对于满足产生死锁的4个必要条件的系统，则应根据死锁的必要条件给出相应的例子。
答：1）在本例中不会产生死锁，因为它不满足死锁的第3个条件，即不剥夺条件。进程所获得的资源在未使用完毕之前，可以被其他进程剥夺。这样，系统就不会产生死锁。
2）这种方法会导致某些进程无限期地等待。因为被阻塞的进程的资源可以被剥夺，所以被阻塞的进程所拥有资源数量不会因为进程的推进而逐渐增加。这样，随着进程的向前推进，并不能保证进程一定能获得所需要的全部资源。
例如，本题中进程A申请（2，2，1）后再申请（0，0，1）被阻塞。此后，进程C又剥夺了进程A的一个资源，使得进程A的资源变为（1，2，1），其需求向量为（1，0，1）。之后，若再创建的进程总是申请第一和第三类资源，总是占有系统所剩余的第一和第三类资源的全部，且不被阻塞，那么，进程A将会无限期地等待。
25.答：1）最大资源需求数见表4-3所填内容。
2）对于T0时刻的进程资源请求，算法检测过程如下：
可用资源（1，6，2，2）可以满足P0，
可用资源（1，6，5，4）可以满足P3，
可用资源（1，9，8，6）可以满足P1，
可用资源（2，9，8，6）可以满足P2，
可用资源（3，12，13，10）可以满足P4。
T0时刻存在一个安全序列{P0，P3，P1，P2，P4}，因此系统是安全的。
3）对于T1时刻进程P1的资源请求，算法检测过程如下：
答案1：若试探性分配给P1（1，2，2，2），可用资源数为（0，4，0，0），不能满足任何一个进程的资源需求。找不到一个安全序列，因此系统不能满足P1的要求。
答案2：P1进程事先对资源D的需求数为0，现在申请2个D资源，超出预先设定的最大资源需求数值，因此系统不能满足P1的要求。
26.答：
1）系统在T0时刻：存在一个安全序列（P4，P5，P1，P2，P3），因而是安全的。
2）若在T0时刻进程P2请求资源（0，3，4），因为可用资源的数量不够，所以只能推迟分配。
3）在2）的基础上，若进程P4请求资源（2，0，1），系统可以满足。因为当分配给P4后，系统剩余的可用资源为（0，3，2），仍然能找到一个安全的序列，如（P4，P5，P1，P2，P3）。
27.答：进程死锁的检测有多种方法，这里给出利用化简进程-资源有向图的方式进行死锁的检测的方法。利用化简进程-资源有向图的方式，可以检测出系统的某一状态s是否处于死锁状态，其化简方法如下：
1）从有向图中找出既不阻塞又非孤立的结点进程Pi。在顺利的情况下，Pi可以获得它所需要的资源不断向前推进，直至运行完毕。然后释放它所占有的全部资源而处于潜伏状态，这相当于在图上消去Pi所有的请求边和分配边，使之成为孤立结点。
2）进程Pi所释放的资源，可以唤醒某些因等待该资源而被阻塞的进程Pj，在顺利的情况下，Pj又可以获得它所需资源继续推进，直至进行完毕，然后释放它所占有的全部资源，而处于潜伏状态。这相当于在图上消去Pj所有的请求边和分配边，使之成为孤立的点。
3）在实施了上述的一系列化简化步骤后，若消去所有的边，则称该图是可完全化简的。
4）若有向图不能通过任何进程予以化简，则称该图是不可简化的。
28.【分析】
哲学家进餐问题是进程同步与互斥中的一个典型问题。本题要求分析算法是否满足同步机制的准则，即每次至多有一个进程进入临界区，进程应在有限时间内进入临界区，进程在临界区停留有限时间。
本题所给出的算法会在特定的情况下产生死锁，因此无法满足同步机制的有限等待准则。为了解决这一问题，我们可以用额外的信号量来控制对临界资源访问，避免死锁。
答：上述同步算法不满足同步机制的有限等待准则。当每个哲学家都只拿到一把叉子时，发生死锁。一种改进的算法如下：
VAR fork:array[0..4] of semaphore;
VAR mutex:semaphore;
fork[0]:=fork[1]:=fork[2]:=fork[4]:=1;
mutex:=1;
cobegin
Pi:repeat//第i个哲学家的生活过程
think for while;
P(mutex);
P(fork[i]);
P(for[(i+1)MOD 5]);
V(mutex);
eat for while;
V(fork[i]);
V(fork[(i+1)MOD 5]);
until false
coend
