condition full,empty; int count; void insert(int item) { if (count==N) wait(full); insert(item); count=count+1; if (count==1) signal(empty); } int remover() { if (count==0) wait(empty); remove=remove_item; count=count-1; if (count==N-1) signal(full); } count=0; end monitor void producer() { while (true) { item=produce_item; ProducerConsumer.insert(item); } }
void consumer() { while (true) { item=ProducerConsumer.remove; consume(item) } }
(9) 进程的高级通信机制有哪些？请简要说明。
解：
进程的高级通信机制分为三大类：共享存储系统、消息传递系统和管道通信系统。 1. 共享存储器系统：在共享存储器系统中，相互通信的进程通过共享某些数据结构或
共享存储区实现进程之间的通信。该系统又可进一步细分为两种方式：基于共享数据结构的通信方式和基于共享存储区的通信方式。
2. 消息传递系统：消息传递机制可以实现不同主机间多个CPU上进程的通信。这种
方式需要使用两条原语send和receive来发送和接收格式化的消息(message)。 3. 管道通信系统：管道通信是一种以文件系统为基础实现的适用于在进程之间实现大
量数据传送的通信方式。
(10) 什么是死锁？产生死锁的原因和必要条件是什么？
解：
所谓死锁是指在一个进程集合中的所有进程都在等待只能由该集合中的其它一个进程才能引发的事件而无限期地僵持下去的局面。
产生死锁的原因可以归结为两点：1）竞争资源， 2）各进程之间的推进顺序不当。 产生死锁的必要条件有四个：1）互斥条件， 2）不剥夺条件， 3）请求和保持条件， 4）环路条件。
(11) 死锁的预防策略有哪些？请简要说明。
解：
死锁的预防策略有三，说明如下：
1. 摒弃请求和保持条件：为摒弃请求和保持条件，系统中需要使用静态资源分配法，
该方法规定每一个进程在开始运行前都必须一次性地申请其在整个运行过程中所需的全部资源。此时，若系统有足够的资源，就把进程需要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它，即使有部分资源处于空闲状态也不分配给该进程。这样，当一个进程申请某个资源时，它不能占有其它任何资源，在进程运行过程中也不会再提出资源请求。这种方法破坏了请求和保持条件，从而避免死锁的发生。 2. 摒弃不剥夺条件：要摒弃“不剥夺条件”，可以使用如下策略：进程在需要资源时
才提出请求，并且进程是逐个地申请所需资源，如果一个进程已经拥有了部分资源，然后又申请另一个资源而不可得时，其现有资源必须全部释放。在这种方法中，进程只能在获得其原有资源和所申请的新资源时才能继续执行。 3. 摒弃环路等待条件：为确保环路等待条件不成立，可以在系统中实行资源有序分配
策略，即系统中的所有资源按类型被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。
(12) 某系统中有A、B、C、D四类资源，且其总数量都是8个。某时刻系统中有5个进程，判断下列资源状态是否安全？若进程P2申请资源(1，1，1，1)，能否为其分配？
进程 P0 P1 P2 P3 P4 Need A B C D 0 0 4 3 2 6 3 0 3 2 1 5 4 0 2 0 0 5 5 4 Allocation A B C D 0 0 2 2 1 1 0 0 2 1 0 3 2 0 0 0 0 2 2 2 解：
现在对该时刻的状态进行安全分析： 由于Available向量为（3，4，4，1），所以Work向量初始化为（3，4，4，1） 此时的Work小于任意的Need[i]向量，所以系统处于不安全状态
由于Request2(1,1,1,1)
Allocation A P0 0 B 0 C 2 D 2 Need A 0 B 0 C 4 D 3 Available A B C D P1 1 P2 3 P3 2 P4 0 1 2 0 2 0 1 0 2 0 4 0 2 2 2 4 0 6 1 0 5 3 0 2 5 0 4 0 4 2 3 3 0 然后进行安全性检测：
此时Available向量为（2,3,3,0），所以Work向量初始化为（2,3,3,0），此时的Work小于任意的Need[i]向量，所以系统处于不安全状态，所以不可以为P2分配资源
(13) 三个进程P1、P2、P3都需要5个同类资源才能正常执行直到终止，且这些进程只有在需要设备时才申请，则该系统中不会发生死锁的最小资源数量是多少？请说明理由。
解：
系统中不会发生死锁的最小资源数量是13，这样可以保证当每一个进程都占有4个资源的时候，有一个进程可以获得最后一个资源后被运行，运行完毕后释放资源，于是其余进程也能顺利运行完，所以不会死锁。
(14) 在解决死锁问题的几个方法中，哪种方法最易于实现，哪种方法使资源的利用率最高？
解：
预防死锁这个方法实现简单，效果突出；避免死锁这种方法系统吞吐量和资源利用率较高。
(15) 考虑由n个进程共享的具有m个同类资源的系统，如果对于i=1,2,3,…,n,有Need[i]>0并且所有进程的最大需求量之和小于m+n，试证明系统不会产生死锁。
解：
本题中只有一种资源，不妨设Max[i]为第i个进程的资源总共需要量，Need[i]为第i个进程还需要的资源数量，Allocation[i]表示第i个进程已经分配到的资源数量，Available为系统剩余的资源数，其中i=1,2,3,…,n。
假设此系统可以发生死锁。
系统剩余的资源数量为Available（Available>=0），由假设，因为系统处于死锁状态，所以Available个资源无法分配出去，所以每个进程的Need[i]都大于Available，
即 Need[i]>=Available+1
所以 ∑Need[i]>=n*(Available+1)=n*Available+n, ① 因为剩下的资源数是Available，所以已经分配出去的资源数为m – Available;
即 ∑Allocation[i]=m – Available ② 由①式和②式可以得到：
∑Need[i] + ∑Allocation[i]>=n*Available+n+ m – Available=（n-1）*Available+m+n ③ 又因为n>=1，所以（n-1）>=0，又因为Available>=0，所以（n-1）*Available>=0 ④ 由③式和④式可以得到∑Need[i] + ∑Allocation[i]>=0+m+n=m+n ⑤ 根据题意知： ∑Max[i] (16) 某车站售票厅，在任何时刻最多可以容纳 20 名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。若把一个购票者看作一个进程，请回答以下问题： ① 用信号量管理这些并发进程时，应该怎样定义信号量，写出信号量的初值以及信号量的各取值的含义。 ② 根据所定义的信号量，写出相应的程序来保证进程能够正确地并发执行。 ③ 如果购票者最多为n个人，试写出信号量取值的可能变化范围(最大值和最小值)。 解： ①定义信号量S,初值为20，当s > 0时，它表示可以继续进入购票厅的人数，当s = 0时表示厅内已有20人正在购票，当s < 0时| s |表示正等待进入的人数。 ②semaphore S=20; begin parbegin procedure:begin repeat wait(s); Enter and buy ticket; signal(s); until false; end parend end ③最大值为20，最小值为20-n (17) 在测量控制系统中的数据采集任务时，把所采集的数据送往一单缓冲区；计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两个任务共享单缓冲区的同步算法。 解： semaphore mutex = 1; semaphore full = 0; semaphore empty = 1; begin parbegin collect: begin repeat ?? collect data in nextp; wait(empty); wait(mutex); buffer:=nextp; signal(mutex); signal(full); until false; end compute: begin repeat ?? wait(full); wait(mutex); nextc:=buffer; signal(mutex); signal(empty); compute data in nextc; until false; end parend end (18) 桌上有一空盘，允许存放一只水果。爸爸可以向盘中放苹果，也可以向盘中放桔子，儿子专等着吃盘中的桔子，女儿专等着吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者用，请用信号量实现爸爸、儿子和女儿3个并发进程的同步。 解： 本题中应设置三个信号量S、So、Sa，信号量S表示盘中是否为空，其初值为1；So表示盘中是否有桔子，其初值为0；Sa表示盘中是否有苹果，其初值为0。同步描述如下： 爸爸: P(S); 儿子：P(So); 女儿：P(Sa); 将水果放入盘中 从盘子中取出桔子 从盘子中取出苹果 if (放入的是桔子) v(So)； V（S）； V（S）； else v(Sa)； 吃桔子 吃苹果； (19) 设某系统中有3个进程Get、Process和Put，共用两个缓冲区buffer1和buffer2。假设buffer1中最多可以放11个信息，现在已经放入了两个信息；buffer2最多可以放5个信息。Get进程负责不断地将输入信息送入buffer1中，Process进程负责从buffer1中取出信息进行处理，并将处理结果送到buffer2中，Put进程负责从buffer2中读取结果并输出。试用信号量机制实现它们的同步与互斥。 解： semaphore empty1=9; //buffer1空的数量 semaphore full1=2; //buffer1满的数量 semaphore empty2=5; //buffer2空的数量 semaphore full2=0; //buffer2满的数量 in1,in2,out1,out2:integer := 2,0,1,0; Get(){ while(1){ wait(empty1) in1=(in1+1)mod11 signal(full1) } } Process（）{ while(1){ wait(full1) out1=(out1+1)mod11 signal(empty1)