一、单项选择题
1．D  2．D  3．A  4．B  5．D  6．B  7．B  8．A  9．C
10．B 11．B 12．B 13．A 14．C 15．C 16．D 17．A 18. B

二、多项选择题
1．[分析]任何一台CPU在每一时刻只能解释执行一条指令，因而，不可能在同一时刻为多个进程服务。进程可同时执行的含义是一个进程的工作没有全部完成之前另一进程就可开始工作。所以，实际上多个进程是轮流占用CPU运行的。到底哪个进程能占用处理器不仅与进程自身有关，且受外界因素的影响；当多个进程竞争CPU时，必须由进程调度来决定当前哪个进程可以占用CPU；故每个进程都是走走停停的，进程执行的速度不能完全由进程自己来控制。
并发进程相互之间可能是无关的，即它们是各自独立的，这些进程中每一个进程的执行既不依赖于其它进程也不会影响其它进程的执行。但是，有些并发进程需使用共享资源，为保证进程执行的正确性，对共享资源的使用必须加以限制。同步就是并发进程中的一种制约关系，一个进程能否使用共享资源取决于其它进程的消息，只有指定的消息到达才可使用共享资源。如果无约束地使用共享资源，则可能出现多个进程交替地访问共享资源，于是就可能会出现与时间有关的错误。故本题的答案为C、D、E。
[题解]C、D、E。

2．[分析]根据P操作的定义，当调用P操作时, P操作把信号量S减去1，若结果小于0则调用者将等待信号量，否则可继续运行。因而，若调用P(S）后S的值为＞=0则进程可以继续运行，故应选择A和D。要注意不能选择C，因S<>0包含了S＞0和S＜0，当S＜0时进程将成为等待状态而不能运行。
[题解]A，D。

3．[题解]A，C，E。

4．[题解]A，B，C，D，E。

三、判断题
1．[题解]是。
2．［分析］如果不控制并发进程执行的相对速度，则它们在共享资源时可能会出现两种情况：一种是并发进程交替使用共享资源，这样就可能会发生与时间有关的错误；另一种是并发执行的速度没有致使它们交替使用共享资源，这时就不会出现与时间有关的错误。因而，本题的结论“一定会出现与时间有关的错误”是不对的。
[题解]否。

3．[分析]所谓防止死锁是指采用了某种方法后系统一定不会发生死锁。但是，使用PV操作不一定能防止死锁，教材中的五个哲学家问题就是例证。所以, PV操作可以防止死锁的说法是错误的。
[题解］否。

4. ［分析]如果一个进程单独执行时，那么执行结果只取决于进程本身，不受外界影响。但多个进程并发执行时，无论是进程本身的原因还是外界的因素都会影响到进程的执行速度。如果并发进程有共享变量且其执行速度造成了它们交替访问共享变量，那么进程的执行结果可能不惟一。故本题的阐述不确切。
[题解］否。

5．[题解］是。

6．[题解]是。

7．[分析］限制共享资源互斥使用后仍可能引起系统死锁，可举例说明。例如，教材中五个哲学家问题，采用了PV操作来保证共享资源的互斥使用，但还是发生了循环等待，且这种等待永远不能结束，引起了死锁。所以，资源的互斥使用不能保证系统不会死锁。
[题解]否。

8. [分析]若任何一个进程在申请新资源前总是先归还已得到的资源，则任何进程都不会发生“占有且等待资源”的情况。也就是说，这种资源分配策略能破坏形成死锁的四个必要条件中的第二个条件，故可防止死锁。
［题解］是。

四、填空题
1．封闭性，可再现性
2．并发进程
3．与时间有关的
4．临界区
5．P, V
6．竞争（或互斥），协作（或同步）
7．P, V
8．等待信号量，就绪
9．[分析］因规定该资源只能互斥使用，因而信号量的初值应定义为1。当n个进程各调用一次P操作时将使信号量的值为最小。
[题解]1，(1-n）或-(n-1)。
10．[分析]由于初值为10，因而调用了18次P操作后的值为（l0-18）=-8。再调用15次V操作的话则信号量的值为（－8＋15）=7。
「题解」7。
11．send（或发送），receive（或接收）
12．发送者的信件，信箱
13．互斥使用资源，循环等待资源
14 死锁防止，死锁避免
15．防止
16．静态分配，按序分配，剥夺式分配
17．不安全
18．银行家
19．安全
20．处理器，主存储器
21．循环等待资源
22．静态

五、问答题
1．[题解]进程的顺序性是指进程在顺序的处理器上的执行是严格按序的，只有在前一个操作结束后才能开始后继操作。
进程并发性是指一组进程可以轮流占用处理器，一个进程的工作没有全部完成之前，另一个进程就可开始工作。把这样的一组进程看做是同时执行的，把可同时执行的进程称为并发进程。
所以，进程的顺序性是对每个进程而言的，进程的并发性是对一组具有顺序性的进程而言的。一组进程并发执行时各进程轮流占用处理器交替执行，占用处理器的进程按各自确定的顺序依次执行指令。

2．［分析]由于“存款”和“取款”两个并发进程使用了共享变量amount，在进程中没有对共享变量的使用加以限制，因而当两个进程交叉访问共享变量时可能会出现与时间有关的错误。
因amount的初值为“0”，故当哥哥先存了两次钱后，amount的值应该为200（每次存人 100元）。之后，哥哥和弟弟各自调用SAVE和TAKE进行存款和取款，使两个进程同时执行。它们并发执行时可能有如下两种情况：
（1）进程在临界区执行没有被打断。此时若哥哥先执行了 m1:=amount；m1:= m1＋100；amount:=m1；则 amount的值为 300。然后，由弟弟执行 m2:= amount； m2:=m2-100；amount:= m2；则弟弟从 300元中取走了 100元使 amount的值保持为 200。如果弟弟先执行，则弟弟将从已有的200元存款中取出 100元使amount的值成为 100。然后，哥哥再执行存人 100元的工作而使amount的值仍为200。可见，无论是哥哥先执行存款还是弟弟先执行取款，只要各自在临界区的工作没有间断，则均使amount保持正确值。
（2）两个进程在临界区交替执行。此时可能哥哥先执行了 m1:=amount，但还没有执行后继操作时弟弟调用的 TAKE进程占用处理器执行了 m2:=amount，那么，m1和 m2都取到了相同的值 200。同样地，若两个进程先后执行了 m2:= amount和 m1:= amount，则 m1和 m2也都取到相同的值200。随后，两个进程并发执行时将使m1=300，m2=100。如果SAVE进程先执行amount:= m1，TAKE进程后执行 amount:= m2，则 amount的终值为 100。如果 TAKE进程先执行 amount:= m2，SAVE进程后执行 amount:= m1，则 amount的终值为 300。
可见，进程并发执行时该账号上可能出现的余额为100元，200元，300元，正确的余额数应该为200元。之所以会出现错误是由于没有限制进程互斥地进入相关临界区执行，为保证系统的安全，可用 PV操作实现互斥。用 PV操作管理时只需定义一个互斥信号量，其初值为“ 1”，用以限制每次只有一个进程可以进入临界区执行。
[题解]（1）系统工作时会出现与时间有关的错误，这是因为并发进程中没有对共享变量amount的使用加以限制，进程交叉访问amount时就会出错。
（2）账号上可能出现的余额为100元或200元或300元，正确的余额应该为200元。
（3）用PV操作管理时可定义一个信号量S,S的初值为1，信号量S用于限制进程互斥地进入相关临界区执行。
（4）使用PV操作管理后能保证正确并发执行的进程结构如下：
begin
amount:integer;
s:semaphore;
amount:=0; s:=1;
cobegin
Process SAVE
m1:integer;
begin
P(S);
m1:=amount;
m1:=m1+100;
amount:=m1;
V(S)
end;
Process TAKE
m2:integer;
begin
P(S);
m2:=amount;
m2:=m2-100;
amount:=m2;
V(S)
end;
coend:
end;3. [分析]司机与售票员的协作关系应该是：当售票员关好车门后司机才能启动车辆；当司机每到一站停车后售票员才能开车门让乘客上、下车。因此，他们之间应互通消息；车门是否已经关好？车是否已经到站停车？显然两者之间应该同步。用PV操作管理时应该定义两个信号量S1和S2分别表示两种不同的消息。
假定S1表示车门是否关好，当S1=1时表示车门已经关好，当S1=0时表示车门还开着。由于初始状态为开着门，故S1的初值应该为“0”。S2表示车是否驶到下一站点，当S2=1时表示车已经行驶到站且停车，当S2=0时表示车尚未到下一站。由于初始状态为车辆还在始发站尚未起步，因而S2的初值应该为“0”，表示车辆尚未行驶到下一个站点。
为了使司机和售票员能安全协调地工作，当发车时间到，售票员关车门后应调用V（S1）把车门已关好的消息发送出去；司机在启动车辆前应调用P（S1）来测试车门是否关好，当车门关好的消息到达时就可启动车辆，然后正常行驶直到下一站后停车；当车辆到站后司机应调用V（S2）把车已到站的消息发送出去；售票员每次开车门前都要调用P（S2）来测试是否已到站停车，当已到站停车的消息到达时就可开车门让乘客上、下车；然后关好车门，再通过V（S1）把车门已关好的消息再次发送出去，司机得到消息后又可启动车辆行驶。用PV操作实现了司机与售票员之间的协调工作，保证了车辆的行驶安全。
［题解]（1）司机与售票员之间应该同步。为了保证乘客安全，仅当售票员关好车门后司机才能启动车辆，也只有在车辆到站停稳后售票员才能开车门。因而，他们之间必须互通消息。
（2）用PV操作管理时应区分两种不同的消息，故应定义两个信号量S1和S2。S1表示车门是否关好石2表示车是否已到站停车。由于初始状态为车尚未始发、开着门，故S1和S2的初值均为“0”。
（3）用PV操作来协调司机与售票员的工作时，可把他们的工作流程修改如下：
4．[分析]首先要注意的是用PV操作实现进程通信与用通信机制实现进程通信是有区别的。利用通信机制实现进程通信需要两条基本的通信原语：send原语和 receive原语。利用 PV操作实现进程通信不需要通信原语，把公用信箱看做是一个可共享的缓冲区，发送进程可往缓冲区中存信件，接收进程可从中取信件。若把信件看做是物品的话，则相当于生产者（发送进程）生产了一件物品（组织一封信件）将其存人可共享的缓冲区（信箱）供消费者（接收进程）取出物品（信件）消费（处理信件）。于是，用PV操作管理共享信箱实现进程通信实际上就是生产者／消费者问题。
假定发送进程只要测试到信箱中没有放满信件就可把组织好的信件放人信箱中；接收进程只要测试到信箱中有信就可从中取出一封信件；系统中共有m个发送进程，r个接收进程。那么，发送进程与接收进程之间必须互通消息：信箱中是否可以存信件和信箱中是否有信件。显然应定义两个信号量SP和SG：
SP表示是否可以把信件存人信箱，由于信箱的容量为可存放n封信，因而SP的初值应该为n；
SG表示信箱中是否有信件，初始化时信箱中无信件，故SG的初值应该为0。
由于m个发送进程可能都要向信箱中存信件，r个接收进程可能都要从信箱中取信件，为防止信件的丢失和重复取信件，因而必须再定义指示存信和取信位置的指针以及互斥使用指针的信号量，具体定义如下：
k——指示信箱中可存放信件的位置；
t——指示可从信箱中取信的位置；
S1——限制 m个发送进程互斥使用指针 k存放信件的信号量，初值为 1；
S2——限制 r个接收进程互斥使用指针t从信箱中取信件的信号量，初值为1。
于是，任一个发送进程组织好信件后只要测试到信箱中尚未存满信件（调用P（SP）测试）且无进程在使用指针k（调用P（S1）测试）时就可把信件存人指针k所指示的位置，信件存人后修改指针k使它指向下一个可存信件的位置，且归还指针k的使用权（调用V（S1))和把信箱中增加一封信件的消息发送出去（调用V（SG))。任一个接收进程在测试到信箱中有信件（调用P（SG))且无进程在使用指针t（调用P（S2))时就可从指针t指示的位置取出一封信件，取出信件后修改指针t使它指向下一个可取信件的位置，且归还指针t的使用权（调用V（S2))和把信箱中增加了一个可存信件位置的消息发送出去（调用V（SP))。
[题解]用PV操作管理公用信箱实现进程通信时发送进程和接收进程可如下并发工作：
begin
B：array［0…（n-1）] of integer；
k, t: integer ；
S1，S2，SP，SG：Semaphore；
k：＝0；t：＝0；
S1：＝1；S2：＝1； SP：＝n；SG：＝0；
cobegin
Process Puti（i＝1，2，…m）
begin
组织一封信件；
P（SP）；
P（S1）；
B[k]：=信件；
k：=（k＋1）mod n；
V（S1）；
V（SG）
end；
Process Getj（j=1，2，…r）
begin
P（SG）；
P（S2）；
从B[t]中取一封信；
t：=(t+1）mod n；
V（S2）；
V（SP）；
处理信件
end；
coend；
end；

5．[分析]本题要求限制进程申请的资源数来确保系统的安全，若要使系统不发生死锁则应保证系统处于“安全状态”，即要保证所有的进程能在有限的时间里得到所需的资源。我们可以假设允许每个进程最多可以申请x个资源（1=＜x=＜m）那么，最坏的情况是每个进程都已得到了（x—1）个资源，现均要申请最后一个资源。因而，只要系统至少还有一个资源就可使其中一个或几个进程得到所需的全部资源，在它们执行结束后归还的资源又可供其它进程使用，故不可能发生死锁。也就是说，只要不等式n（x—1）＋1=＜m成立，则系统一定不会发生死锁。
[题解]假设每个进程最多可以申请X个资源，为保证系统不发生死锁，应该使下列不等式成立：
n（x-1）＋1=＜m
解上述不等式   nx=＜n＋m-1
x=＜1＋(m-1)/n
于是可得到：
当m=＜n时 x=1
当m＞n时 x=1+(m-1)/n
[讨论］在实际的系统中每个进程需要多少个资源是由进程自己决定的，不能人为地去限制它。但是，如果在设计系统时能预计到并发进程申请资源量的情况，则可用上述方法来预测系统的安全性。只要系统拥有的资源数、可能并发执行的进程数、每个进程所需资源量之间的关系符合上述关系，则不必受资源分配策略的限制，只要有空闲资源就可分配给申请者，系统不会出现死锁现象。
6．[分析]银行家算法是在保证至少有一个进程能得到所需的全部资源的前提下进行资源分配的。当进程请求分配资源时，银行家算法总是测试该进程对资源的尚需量，仅当系统的资源不少于它的尚需量时才会根据该进程当前的申请把资源分配给它。这样，可保证所有的进程在有限的时
间内能得到所需的全部资源，确保系统处于安全状态。
本题共有A、B、C、D四类资源，系统对这四类资源的拥有量为：A类3个、B类14个、C类12个、D类12个，可以把它记为（3，14，12，12）。根据五个进程对资源的需求和分配情况可知它们已占资源总数为（2，9，10，12），因而现在系统中各类资源的剩余量为（1，5，2，0）。每个进程对资源的尚需量为：
进程P1尚需（0，0，0，0）
进程P2尚需（0，7，5，0）
进程P3尚需（1，0，0，2）
进程P4尚需（0，0，2，0）
进程P5尚需（0，6，4，2）
现在来测试系统是否处于安全状态。由于进程P1已经得到了所需的全部资源，它在执行中不再会申请资源，因而可把资源先分配给进程P4，然后再依次分配给进程P2、P3、P5，使每个进程都在有限时间里能得到各自所需的全部资源，故系统处于安全状态。
但是，如果当前进程P2先提出需要资源（0，4，2，0）个时，按银行家算法暂时不能满足它的请求，这是因为当前剩余资源数（1，5，2，0)小于它尚需资源数（0，7，5，0）。
[题解］（1）系统拥有资源量为A类3个，B类14个，C类12个，D类12个，把它用（3，14，12，12）来表示。由于五个进程已占用的资源量为（2，9，10，12），故现在系统中各类资源的剩余量为（1，5，2，0）。
（2）根据各进程对资源的最大需求和已占资源量可知它们尚需的资源量如下：

由于进程P1不会再申请资源，根据系统当前的资源剩余量（1，5，2，0）可先满足进程P4的需求，当进程P4执行结束后归还所占的全部资源，收回的资源又可继续分配给其它进程。如果系统按如下顺序分配和回收资源：

则可保证所有进程在有限时间里得到所需的全部资源，因而，现在系统处于安全状态。
（3）如果现在进程PZ提出需要（0，4，2，0）个资源，则由于当前剩余的资源（1，5，2，0）小于它的尚需量（0，7，5，0），暂时不能满足它的请求。

7．［分析]对资源采取按序分配策略的话，需对系统中每个资源给出一个编号，且规定任何一个进程要申请两个以上资源时总是先申请编号小的资源，再申请编号大的资源。
假定系统共有m个资源，编号为1，2，…，m。若用R表示资源，则这m个资源为：
    R1，R2，……Rm
根据按序分配的原则，任何一个进程在得到了资源 Ri后，如果再申请资源 Rj则必定是 i＜j。
可用反证法来证明采用按序分配策略后系统不会死锁。于是，可以假设系统会死锁，则一定同时保持了死锁的四个必要条件，也就一定存在一组进程，它们形成了循环等待资源的情况。如果在这样的假设下，若推导出与题意前提相违背的结果，则这样的假设就是不成立的，即证明了系统是不会死锁的。
[题解］设系统有m个资源：R1，R2，……，Rm，进程申请两个以上资源时总是先申请编号小的资源，再申请编号大的资源。
用反证法。假定循环等待资源的条件成立，则一定存在一组进程P1，P2，……，Pn，其中每一个进程都在等待某个资源，而该资源却被另一个进程占有。如果进程Pi（i=1，2，…，n-1）在等待资源 Rki（1=＜ki=＜m），而资源 Rki已被进程 P（i＋1）占有，那么进程 Pn等待的资源一定被进程 P1占有。依照按序分配的原则可列出如下的关系表：

由此可推得：
    kn＜ki＜k2＜k3＜……＜k（n-1）＜kn
于是发生了kn＜k1而k1＜kn的矛盾。这个矛盾是因假设存在一组进程循环等待资源而引起的，故这个假设是不能成立的。即资源的按序分配策略破坏了死锁四个必要条件中的循环等待资源条件，因而系统一定不会发生死锁。

8．［题解]进程的并发执行可以提高计算机系统的工作效率，但必须对它们进行三个方面的管理以确保并发进程执行的正确性。
第一，并发进程的同步与互斥。并发进程在共享资源时可能出现与时间有关的错误，为保证系统的安全应实现正确的同步与互斥。
第二，进程通信。需要相互合作的并发进程之间经常要交换信息，使之能协调地完成任务。当需要交换大量信息时，应有专门的通信机制来实现信息的传递。
第三，死锁问题。由于并发进程执行的速度和采用的资源分配策略，使进程在竞争资源时可能引起系统死锁。因此，必须考虑如何防止、避免和检测死锁。

由此可推得：
    kn＜ki＜k2＜k3＜……＜k（n-1）＜kn
于是发生了kn＜k1而k1＜kn的矛盾。这个矛盾是因假设存在一组进程循环等待资源而引起的，故这个假设是不能成立的。即资源的按序分配策略破坏了死锁四个必要条件中的循环等待资源条件，因而系统一定不会发生死锁。

8．［题解]进程的并发执行可以提高计算机系统的工作效率，但必须对它们进行三个方面的管理以确保并发进程执行的正确性。
第一，并发进程的同步与互斥。并发进程在共享资源时可能出现与时间有关的错误，为保证系统的安全应实现正确的同步与互斥。
第二，进程通信。需要相互合作的并发进程之间经常要交换信息，使之能协调地完成任务。当需要交换大量信息时，应有专门的通信机制来实现信息的传递。
第三，死锁问题。由于并发进程执行的速度和采用的资源分配策略，使进程在竞争资源时可能引起系统死锁。因此，必须考虑如何防止、避免和检测死锁。