操作系统同步算法_计算机组成原理期末考试

费翔林课本习题

思考题

1.试述顺序程序设计的特点以及采用顺序程序设计的优缺点

【答案】

特点：

• 执行的顺序性：一个程序在处理器上是严格按序执行的，每个操作必须在下一个操作开始前结束
• 环境的封闭性：运行程序独占全机资源，资源状态只能由此程序本身决定，也不受到外界环境因素影响
• 结果的确定性：程序在执行过程中允许1出现中断，但是这种中断不会对程序最终结果产生影响，也就是说程序执行结果与他的执行速度无关
• 过程的可再现性：程序针对同一个数据结构的执行过程在下一次执行时会重现，也即重复执行程序会获得相同搞得执行过程和计算结果

优点是程序的编址和调试很方便，但缺点就是计算机系统效率低下

2.试述并发程序设计的特点以及采用并发程序设计的优缺点（★★★）

【答案】

特点：程序的执行不再是顺序的，一个程序未执行完而另一个程序便已经开始执行，程序外部的顺序特性消失，程序与计算不再一一对应

优点

• 若为单处理器系统，可以有效利用资源，让处理器和设备,设备和设备同时工作，充分发挥硬部件的并行工作能力
• 若为多处理器系统，可以让进程在不同处理器上物理地并行工作，加快计算速度
• 简化程序设计任务，一般来说，编制并发的小程序进度快，容易保证正确性

缺点

• 可能会出现各种与时间有关的错误，例如结果唯一或永远等待

3.解释并发与并行（★★★）

【答案】

• 并行性是指两个或多个事件在同一时刻发生
• 并发性是指两个或多个事件在同一时间间隔发生

在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行

4.解释可再入程序与可再用程序

• 可再入程序：又称为可重入程序，是指能被多个程序同时调用的程序，是纯代码，在执行过程中不被修改
• 可再用程序：在调用过程中可以自身修改，在调用它的程序退出之前是不允许其他程序来调用的

5.解释并发进程的无关性和交互性（★★★）

【答案】

• 无关性：无关的并发进程是指它们分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关，也即一个进程不会改变另一个与其并发执行进程的变量
• 交互性：交互的并发进程共享某些变量，一个进程的执行可能会影响其他进程的执行结果，交互的并发进程之间具有制约关系

6.解释进程的竞争与协作关系

【答案】

• 竞争关系：批处理系统中建立多个批处理进程，分时系统中建立多个交互式进程，它们共享一套计算机系统资源，使得原本不存在逻辑关系的诸进程因共享资源而产生了交互和制约关系，这是间接制约关系，又叫做互斥关系，操作系统必须协调对共享资源的争用
• 协作关系：一个作业可涉及一组并发进程，它们为了完成共同任务需要分工协作，由于每个进程都独立地以不可预知的速度推进，在执行的先后次序上就要有约束，需要相互协作的进程在某些关键点上协调各自的工作。当其中一个进程到达关键点后，在尚未得到其伙伴进程发来的消息或信号之前应该阻塞自己，等待协作者发来信号或消息后方被唤醒并继续执行。这种协作进程之间需要排定执行先后次序的协调关系是直接制约关系，称为进程同步

7.试述进程的互斥与同步两个概念之间的异同（★★★）

【答案】

• 进程同步：进程同步又叫做直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调工作次序而产生一种制约关系
• 进程互斥：进程互斥叫做间接制约关系，它是指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束后，并释放资源后，另一个进程才可以访问

8.什么是临界区和临界资源？临界区管理的基本原则是什么（★★★）

【答案】

• 临界区：并发进程中与共享变量有关的程序段称为临界区
• 临界资源：共享变量所代表的资源称为临界资源

四个原则

• 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
• 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
• 有限等待：对请求访问的进程，应该保证能在有限时间内进入临界区，也就是不能饥饿
• 让权等待：当进程不能进入临界区时，应该立即释放处理机，防止进程处于忙等待状态

11.试述Deek而算法实现临界区互斥的原理

算法思想：该算法会设置一个布尔型的数组flag[]，用于标记各进程是否想要进入临界区，比如”flag[0]=true“表示0号进程$P_0$现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有则把自身对应的标志设置为true，之后开始访问临界区

具体实施：设置一个布尔型的数组flag[]，开始时均设置为flase，表示都不想进入临界区，以分析$P_1$为例

• 开始，$P_1$进程会检查$P_0$进程是否想要进入临界区，如果flag[0]=true，那么$P_1$就会被卡住
• 如果flag[0]=false，表示$P_1$此时确认$P_0$不想进入临界区，那么它就不会被卡住。然后它进入临界区之前，会被自己的flag[1]设置为true，向其他进程表明自己想要进入临界区
• 临界区访问完毕之后，设置flag[1]=false

算法缺陷：违背了“忙则等待”原则。因为在这种算法下，两个进程是并发的，并发导致异步，意味着两个进程可能会同时访问临界区

10.试述Peterson算法实现临界区互斥的原理

算法思想：为了防止两个进程为了进入临界区而无限期等待，又设置了一个变量turn，每个进程先设置自己的标志后再设置turn标志，再同时检测另一个进程状态标志和不允许进入标志，以保证两个进程同时要求进入临界区时，只允许一个进程进入临界区

具体实施：以分析对于$P_1$进程为例：

• flag[1]=true表示$P_1$想要进入临界区，然后turn=0，是一种“谦让操作”，表示可以优先让$P_0$进入临界区
• 此时如果$P_0$已经在临界区，那么$P_1$while循环满足，就会被卡住；如果$P_0$不想进入临界区，那么肯定有$P_0$的flag[0]=flase,$P_1$就不会被卡住

算法优点：遵循了空闲让进、忙则等待、有限等待这三个原则

算法缺陷：相较于前三种算法来说，是比较好的，但是还是有缺陷，未能遵循让权等待的原则。因为在上面的那个例子中，即便$P_1$不能进入临界区，它还是会卡在while循环，不能释放处理机，使处理机处于了忙等状态

11.哪些硬件设施可以实现临界区管理？简述其用法

【答案】

---

①：中断屏蔽方法
思想：当一个进程正在使用处理机执行它的临界区代码时，为了防止其他进程进入临界区进行访问的，直接“暴力的”禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换

优缺点

• 优点： 简单、高效
• 缺点： 不适用于多处理机，限制了处理机交替执行程序的能力，因此执行的效率会明显降低；且只适用于内核进程，不适用于用户进程（因为开关中断指令属于特权指令）

---

②：TestAndSet指令(TSL)
思想：可以为每个临界资源设置一个共享布尔变量lock，lock=true表示正在被占用，初值设为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock，如果有进程在临界区，则重复检查，直到进程退出。大致逻辑如下

while TestAndSet(&lock);//上锁检查 //临界区代码段 lock=false;//解锁、退出区 //剩余区代码段 

TestAndSet指令：这是一个原子操作，执行过程中绝对不会被中断，使用硬件实现。其功能是读出指令标志后把该标志设为true。以下是功能描述

bool TestAndSet(bool* lock) { 
    bool old;//用于存放*lock原来的值 old=*lock; *lock=true;//无论是否加锁，一律设为true return old;//返回lock原来的值 } 

具体过程

• 如果刚开始lock=false，则TSL返回的old就是false，while条件不满足，直接进入临界区
• 如果刚开始lock=true，则TSL返回的old就是true,while条件满足，会一直循环，直到当前访问临界区的进程在退出区进行解锁

优缺点

• 优点： 相比软件方法，TSL把上锁和检查操作使用硬件的方式编程了原子操作。所以实现简单，不会像软件实现那样产生逻辑漏洞
• 缺点： 不满足让权等待 ，暂时无法进入临界区的进程会占用CPU并循环执行TSL，使CPU忙等

---

③：swap指令（exchange）
能不能完成原子操作可以看其汇编指令，比如++i这就不是原子操作，因为它需要三条汇编指令，需要经过加载-运算-放回操作

思想：可以为每个临界资源设置一个共享布尔变量lock，lock=true表示正在被占用，初值设为false；然后在每个进程中再设置一个局部变量key，用于和lock交换信息。在进入临界区之前，先利用swap指令交换lock与key的内容，然后检查key的状态，有进程在临界区时，重复交换和检查过程，直到进程退出。大致逻辑如下

key=true; while(key!=false) swap(&lock,&key); //临界区代码段 lock=false; //剩余区代码段 

swap指令：该指令用于交换两个字的内容，使用硬件实现。属于原子操作，其对应的汇编指令如下

xchgb %al,mutex 

• 王道书上给出了C语言描述，但是我觉得不好，这是原子性操作，那种代码感觉似乎需要三个步骤一样，直接看汇编即可。其中al和mutex是寄存器

具体过程

• 如果刚开始临界区就已经被上锁，那么先将其记录在key上，也即key=true，那么此时while循环条件满足，一直执行swap，直到此时处在临界区的进程退出时将lock设为false，交换给key，然后结束循环
• 如果刚开始临界区没有被上锁，那么先将其记录在key上，也即key=false，那么此时while循环条件不满足，直接进入临界区

优缺点

• 优点：实现简单，不会像软件实现那样产生逻辑漏洞，适用于多处理机环境
• 缺点：不满足让权等待 ，暂时无法进入临界区的进程会占用CPU并循环执行TSL，使CPU忙等

12.什么是信号量？如何对其分类（★★★）

【答案】

1965年，荷兰计算机科学家E. W. Djkstra提出新的同步工具一信 号量和PV提作，他将交通管制中多种颜色的信号灯管理方法引人操作系统，让多个进程通过特殊变
量展开交互。一个进程在某一关键点 上被迫停 止执行直至接收到对应的特殊变量值，通过这一措施， 任何复杂的进程交互要求均可得到满足，这种特殊变量就是信号量( semaphore)。为了通过信号量传送信号,进程可利用P和V两个特殊操作来发送和接收信号，如果协作进程的相应信号仍未送到，则进程被挂起直至信号到达为止。在操作系统中用信号量表示物理资源的实体，它是一个与队列有关的整型变量。具体实现时，信号量是一种变量类型，用一个记录型数据结构表示，有两个分量：一个是信号量的值,另一个是信号量队列指针。信号量在操作系统中主要用于封锁临界区、进程同步及维护资源计数。除了赋初值之外,信号量仅能由同步原语PV对其进行操作，不存在其他方法可以检查或操作信号量,PV操作的不可分割性确保执行时的原子性及信号量值的完整性。Dijkstra 发明信号量操作原语:P和V操作(荷兰语中“检测”(Pro-beren)和“增量”( Verhogen)的首字母)，常用的符号还有up和down等。利用信号量和PV操作既可解决并发进程竞争问题，又可解决并发进程协作问题

按其用途分类：

• 公用信号量：联系一组并发进程，相关进程均可在此信号量上执行PV操作，初值为1，用于实现进程互斥
• 私有信号量：联系一组并发进程，仅允许信号量所用的进程执行P操作，而其他相关进程可在其上执行V操作，初值往往为0或正整数，多用于并发进程同步

按其取值分类：

• 二值信号量：仅允许取值为0或1，主要用于解决进程互斥问题
• 一般信号量：允许取大于1的数值，主要用于解决进程同步问题

PV操作

• P操作（wait(S)原语）：这个操作会把信号量减去1，相减后如果信号量<0则表示资源已经被占用，进程需要阻塞；相减后如果信号量$\ge 0$，则表明还有资源可以使用，进程可以正常执行
• V操作（signal(S)原语）：这个操作会把信号量加上1，相加后如果信号量$\le 0$，则表明当前有阻塞中的进程，于是会把该进程唤醒；相加后如果信号量>0，则表明当前没有阻塞中的进程

13.为什么PV操作均为不可分割的原语操作

【答案】

因为他们被定义为了如下数据结构和不可中断过程（以记录型信号量为例）

typedef struct semaphore { 
    int value;//信号量值 struct pcb* list;//信号量队列指针 } void P(semapore s) { 
    s.value--; if(s.vaue < 0) sleep(s.list); } void V(semaphore s) { 
    s.value++; if(s.value <= 0) wakeup(s.list); } 

14.何为管程？它有哪些属性（★★★）

【答案】

管程(Monitor)：它是一种特殊的软件模块，由以下部分组成

• 局部于管程的共享数据结构说明——可以理解为类的成员
• 对该数据结构进行操作的一组过程(函数)——可以理解为类的方法
• 对局部于管程的数据设置初始值的语句——可以理解为类的构造函数
• 管程有一个名字——可以理解为类名

所以，管程是一个代表共享资源的数据结构，进程对共享资源的申请、释放等操作是通过过程来实现的（过程就是对这一数据结构的操作），这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥，即：

monitor Test//定义了一个名称为"Test"的管程 { 
    Data Structure DS;//定义共享数据结构，对应系统中的某种共享资源 Init_Code()//对共享数据结构初始化语言 { 
    DS=5;//初始资源数目为5 } Take_Away()//过程1：申请一个资源 { 
    对共享数据结构的一系列操作 DS--;//可用资源数目减一 ... } Give_Back()//过程2：归还一个资源 { 
    对共享数据结构的一系列操作 DS++;//可用资源数目加一 ... } } 

管程基本特征：

• 共享性：管程中的移出过程可被所有要调用管程的过程的进程所共享
• 安全性：管程的局部变量只能由此管程的过程访问，不允许进程或其他管程来直接访问，一个管程的过程也不应该访问任何非局部于它的变量
• 互斥性：在任一时刻，共享资源的进程可以访问管程中的管理此资源的过程，但最多只有一个调用者能够真正进入管程，其他调用者必须等待直至管程可用

15.试述管程中条件变量的含义和作用（★★★）

【答案】

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程，为此，将阻塞原因定义为条件变量condition

如果一个进程被阻塞的原因有多个，那么就设置多个条件变量，而每一个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对于条件变量的操作只有两种：wait和signal

• x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程
• x.signal：当x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程

逻辑描述如下

monitor Test() { 
    Data Structure DS;//定义共享数据结构，对应系统中的某种共享资源 condition x;//定义了一个条件变量x Init_Code(){ 
   ...} Take_Away() { 
    if(DS<=0) { 
    x.wait();//资源不够，在条件变量x上阻塞的大概 } 资源足够，分配资源，做一系列相应处理 } Give_Back() { 
    归还资源，做一系列相应处理 if(进程在等待) x.sginal();//唤醒一个阻塞进程 } } 

可以看出：相较于信号量，条件变量或者管程把具体的同步互斥关系实现封装了起来，只暴露两个特别简单的接口以供程序员调用，而这两个接口其反应的本质问题就是资源是否存在，能否互斥访问的问题，程序员不用关心复杂的同步互斥关系，只关心在相应的程序逻辑下资源数目的问题

16.试比较管程与进程

【答案】

• 管程所定义的是公用数据结构，而进程定义的是私有数据结构
• 管程把共享变量上的同步操作集中在一起统一管理，而临界区却分散在每个进程中
• 管程是为了解决进程共享资源的互斥而建立的，而进程是为了占有系统资源和实现系统并发性而引入的
• 管程被欲使用的共享资源的所有进程所调用，管程和调用它的进程不能并行工作；而进程之间可以并行工作
• 管程可以作为语言或操作系统部分，不必创建或撤销；进程有其生命周期

17.为什么引入进程通信

【答案】

并发进程之间的交互必须满足两个基本要求:同步和通信。进程同步本质上是一种仅传送信号的进程通信，通过修改信号量，进程之间可以建立联系，相互协调运行和协同工作,但它缺乏传递数据的能力。在多任务系统中，可由多个进程分工协作完成同一任务,于是它们需要共享一些数据和相互交换信息，某些情况下交换的信息量很少，但在很多场合需要交换大批数据，可以通过通信机制来完成。进程之间互相交换信息的工作称为进程通信( Inter – Process Communication,IPC) ,线程通信是从进程通信演变而来,由于可区分单线程结构进程和多线程结构进程,进程通信实质上就是进程中的线程之间的通信。通信方式有很多，包括信号(signal)通信机制，管道( pipeline)通信机

18.试述信件、信箱和间接通信原语

【答案】

19.什么是管道？如何通过管道机制实现进程间通信（★★★）

【答案】

管道是连接读写进程的一个特殊文件，允许按照FIFO方式传送数据，也能使进程同步执行。管道是单向的，发送进程视管道文件为输出文件，以字符流的形式把大量数据送入管道；接受进程视管道文件为输入文件，从管道中接受数据，所以也称为管道通信

20.试述进程的低级通信工具和高级通信工具（★★★）

【答案】

21.什么是死锁（★★★）

【答案】

死锁：所谓死锁，是指多个进程因竞争资源而造成的一种互相等待的局面，若无外力作用，这些进程将无法向前推进

• 专业定义：如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的事件，而无限期陷入僵持的局面称之为死锁

生活中死锁的例子：我拿了你房间的钥匙，而我在自己的房间；你拿了我的房间的钥匙，而你又在自己的房间。如果我要从自己的房间走出去，必须要拿到你手中的钥匙，但是你要走出来又必须要拿到我手中的钥匙，于是形成了死锁

22.试述死锁产生的必要条件

【答案】

①：互斥条件
互斥条件：是指只有对必须互斥使用的资源抢夺时才可能导致死锁。比如打印机设备就可能导致互斥，但是像内存、扬声器则不会

• 进程A已经获得资源，进程B只能等待

②：不可剥夺条件

不可剥夺条件：是指进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

③：持有并等待条件
持有并等待条件：是指进程已经至少保持了一个资源，但又提出了新的资源请求，但是该资源又被其他进程占有，此时请求进程被阻塞，但是对自己持有的资源保持不放

④：循环等待条件

循环剥夺条件：是指存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

23.列举死锁的各种防止策略

【答案】

死锁处理策略：主要分为以下三种

• 预防死锁：破坏死锁产生的四个必要条件中的一个或几个
• 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁。例如银行家算法
• 死锁的检测和解除：允许死锁产生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解决死锁

应用题

1.如何用信号量实现互斥操作

【答案】

思想：

• 1：分析并发进程的关键活动，划定临界区
• 2：设置互斥信号量mutex，初值1
• 3：在临界区之前执行P操作
• 3：在临界区之后执行V操作

具体描述：

可用如下描述大致逻辑，有两个进程$P_1$和$P_2$

semaphore mutex=1;//互斥信号量 P1() { 
    //其他代码 P(mutex);//进入临界区前加锁 临界区代码 V(mutex);//退出临界区时要解锁 } P1() { 
    //其他代码 P(mutex);//进入临界区前加锁 临界区代码 V(mutex);//退出临界区时要解锁 } 

• 进程$P_1$在访问临界资源前，先执行了$P$操作，由于信号量初值mutex=1，所以$P_1$在执行完$P$操作后mutex变为0，$P_1$访问临界资源
• 此时进程$P_2$也想要访问临界资源，执行$P$操作后，其mutex变为了-1，表明系统中已经没有可以分配的资源，所以执行block原语，被阻塞
• $P_1$访问完临界资源后，执行$V$操作，信号量恢复，即mutex=0，然后使用wakeup原语唤醒阻塞中$P_2$，并将资源分配给它
• $P_2$访问完成之后，执行$V$操作，使信号量恢复至初值，即mutex=1

注意：
1：对不同的临界资源需要设置不同的互斥信号量。例如$P_1$和$P_2$进程争抢A这种资源，那么就可以设置互斥信号量为mutex1，$P_3$和$P_4$进程争抢B这种资源，那么就可以设置互斥信号量为mutex2

semaphore mutex1=1; semaphore mutex2=1; 

2：一定注意P、V操作必须成对出现

• 缺少P操作： 不能保证临界资源的互斥访问
• 缺少V操作： 导致资源永远不会释放，继而等待进程永远不会被唤醒

2.如何用信号量实现同步操作

【答案】

思想：

• 1：分析什么地方需要实现同步关系，也即必须保证一前一后执行的两个操作（或代码）
• 2：设置同步信号量S，初值0
• 3：在必须要先执行的操作（代码）之后执行V操作
• 4：在必须要后执行的操作（代码）之前执行P操作

具体描述：

可用如下描述大致逻辑，有两个进程$P_1$和$P_2$。其中代码4要执行必须保证代码1和代码2先执行完毕，因此V操作在代码1、2后面执行；同样代码1和代码2执行完毕之后才能执行代码4，因此P操作要在代码4之前。总体上看$P_1$一定要先于$P_2$运行

semphore S=0;//同步信号量 P1() { 
    代码1； 代码2 V(S); 代码3; } P2() { 
    P(S); 代码4； 代码5 代码6; } 

• 如果先执行了P操作，那么表明此时$P_2$先于$P_1$执行（这不是我们期望的顺序）。此时，由于S=0，P操作后S=-1，所以$P_2$就会执行block原语进行阻塞。当$P_1$的代码2执行完之后，就会执行V操作，此时S++，所以S=0，所以$P_1$就会执行wakeup原语，唤醒$P_2$进程，这样$P_2$就可以继续执行代码4了。满了同步
• 如果先执行了V操作，那么表明此时$P_1$先于$P_2$执行（这正是我们期望的顺序），于是S++，S=1，当$P_2$执行P操作时，由于S=1，也即有可用资源就会使S–，也即S=0，所以$P_2$不会执行block原语，而是继续向下执行代码4

3.如何用信号量实现前驱关系

【答案】

所谓前驱关系就是要实现多组进程的同步关系，如下

• $P_1$中有一句代码S1
• $P_2$中有一句代码S2
• $P_3$中有一句代码S3
• $P_4$中有一句代码S4
• $P_5$中有一句代码S5
• $P_6$中有一句代码S6

这些代码需要按照如下前驱图所规定的顺序执行

思想：

• 1：要为每一对前驱关系各设置一个同步变量
• 2：在必须要先执行的操作（代码）之后对相应的同步变量执行V操作
• 3：在必须要后执行的操作（代码）之前对相应的同步变量执行P操作
  

具体描述：

可用如下描述大致逻辑，有六个进程$P_1$~$P_6$。

P1() { 
    ... S1; V(a); V(b); ... } P2() { 
    ... P(a); S2; V(c); V(d); ... } P3() { 
    ... P(b); S3; V(g); ... } P4() { 
    ... P(c); S4; V(e); ... } P5() { 
    ... P(d); S5; V(f); ... } P6() { 
    ... P(e); P(f); P(g); S6; ... } 

4.用信号量解决生产者与消费者问题

【答案】

实现同步

• 生产者：将产品放入缓冲区前需要执行P(empty)以消耗一个空闲缓冲区；放入缓冲区之后需要执行V(full)以增加一个产品数量
• 消费者：从缓冲区取出产品之前需要执行P(full)以消耗一个产品；从缓冲区取出产品之后需要执行V(empty)以增加一个空闲缓冲区

实现互斥

• 生产者：将产品放入缓冲区前需要执行P(mutex)；放入缓冲区之后需要执行V(mutex)
• 消费者：从缓冲区取出产品之前需要执行P(mutex)；从缓冲区取出产品之后V(mutex)

因此代码如下

semaphore mutex=1;互斥信号量，实现对缓冲区的互斥访问 semaphore empty=n;同步信号量，表示空闲缓冲区数量 semaphore full=0;同步信号量，表示非空闲缓冲区数量，也就是产品数量 Producer() { 
    while(1) { 
    //生产者生产数据 p(empty);要用什么，P一下 //获取空缓冲区 p(mutex)：互斥夹紧 //将数据放入缓冲区 V(mutex)：互斥夹紧 V(full)：提供什么，V一下 //产品数量增加 } } Producer() { 
    while(1) { 
    p(full);要用什么，P一下 //获取产品 p(mutex)：互斥夹紧 //消费者取出产品 V(mutex)：互斥夹紧 V(empty)：提供什么，V一下 //空缓冲区增加 //消费者使用数据 } } 

5. 多生产者多消费者问题
   

【答案】

semaphore plate=1;//盘子中还可以放多少个水果 semaphore apple=0;//盘子中有几个苹果 semaphore orange=0;//盘子中有几个句子 dad() { 
    while(1) { 
    准备一个苹果； P(plate);//互斥放水果 向盘子中放苹果； V(apple);//可以取苹果  } } mom() { 
    while(1) { 
    准备一个橘子； P(plate);//互斥放水果 向盘子中放橘子； V(orange);//允许取橘子  } } son() { 
    while(1) { 
    P(orange);//互斥从盘子中取橘子 取橘子 V(plate);//取完归还盘子 吃橘子 } } daughter() { 
    while(1) { 
    P(apple);//互斥从盘子中取苹果 取苹果 V(plate);//取完归还盘子 吃苹果 } } 

6.读者写者问题、

【答案】

关系分析：找出题目中描述的各个进程，分析它们之间的同步、互斥关系

• 互斥关系：写进程与写进程；写进程与读进程
• 同步关系：桌子上有组合一/二/三时，第一/二/三个抽烟者取走东西，这是三个同步关系；还有抽烟者抽完烟之后要发出完成信号，这是第四个同步关系

整理思路：根据各进程的操作流程确定P、V操作的大致顺序

• 对于写者来说，它与任何进程都是互斥的，因此可以设置一个互斥信号量rw，在写者访问共享文件前后分别执行P、V操作
• 对于读者进程，如果它也像前面那样，那么就不符合读者进程可以同时访问文件的要求了。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，所以我们可以让第一个访问文件的读进程“加锁”，也就是P操作，然后让最后一个访问完文件的读进程进行解锁，也就是V操作。所以可以设置一个整形变量count来记录当前有几个读进程在访问文件
• 对于读进程来说，在某一时刻多个读进程并发执行。而我们对count变量的判断是无法实现原子性操作的，所以这里count就是一种临界资源了，需要对其进行保护，可以设置互斥信号量mutex

设置信号量：设置需要的信号量，并根据题目条件确定信号量初值

• 设置信号量count为计数器，用于记录当前读者的数量，初值为0；
• 设置mutex为互斥信号量，用于保护更新count变量时的互斥；
• 设置互斥信号量rw，用于保证读者和写者的互斥访问

int count=0; semaphore mutex=1; semaphore rw=1; 

对于写者，在写文件之前进行P操作，写完之后进行V操作，就可以实现写者与其他进程的互斥

writer() { 
    while(1) { 
    P(rw);//写之前加锁 写文件; V(rw);//写之后解锁 } } 

对于读者，第一个读者进入会加锁，最后一个读者退出时进行解锁

reader() { 
    while(1) { 
    P(mutex);//使用P操作保护count，防止多个读进程对临界资源的操作 if(count==0) P(rw);//第一个读进程 count++; V(mutex); 读文件; P(mutex); count--; if(count==0) V(rw);//最后一个读进程 V(mutex); } } 

但是上面代码还存在一个bug：读进程是优先，只要有读进程在读，写进程就会一直被阻塞，写进程饿死。

所以如果希望写进程优先，也就是说当有读进程在读时，若有写进程请求访问，那么应该禁止后续读进程请求，等到本次读进程完毕之后，立即让写进程执行，只有在无写进程的情况下才允许读进程再次运行。因此可以再增设一个信号量w，用于实现写优先

int count=0; semaphore mutex=1; semaphore rw=1; semaphore w=1;//用于实现写优先 writer() { 
    while(1) { 
    P(w); P(rw);//写之前加锁 写文件; V(rw);//写之后解锁 V(w); } } reader() { 
    while(1) { 
    p(w);//在无写进程的情况下进入 P(mutex);//使用P操作保护count，防止多个读进程对临界资源的操作 if(count==0) P(rw);//第一个读进程 count++; V(mutex); V(w); 写文件; P(mutex); count--; if(count==0) V(rw);//最后一个读进程 V(mutex); } } 

7.吸烟者问题（单生产者多消费者问题）

【答案】

semaphore offer1=0;//组合一的数量 semaphore offer2=0;//组合二的数量 semaphore offer3=0;//组合三的数量 semaphore finish=0;//抽烟是否完成 int i=0;//用于实现轮流抽烟 

对于生产者，其内部进行逻辑判断，利用取余的方式轮流放置组合一、二和三，放置完成之后如果消费者不执行V(finish)，它将会在P(finish)处被阻塞

provider { 
    while(1) { 
    if(i==0) { 
    组合一放桌子上 V(offer1); } else if(i==1) { 
    组合二放桌子上 V(offer2); } else if(i==2) { 
    组合三放桌子上 V(offer3); } i=(i+1)%3; P(finish); } } 

对于这三个消费者，他们各自在进入时首先会检查是否有自己的组合，如果没有将会被阻塞，如果有，执行完毕之后使用V(finish)通知生产者生产

smoker1() { 
    while(1) { 
    P(Offer1); 一系列卷烟、抽烟操作、拿走组合一 V(finish); } } smoker2() { 
    while(1) { 
    P(Offer2); 一系列卷烟、抽烟操作、拿走组合二 V(finish); } } smoker3() { 
    while(1) { 
    P(Offer3); 一系列卷烟、抽烟操作、拿走组合三 V(finish); } } 

8.哲学家进餐问题

【答案】

semaphore chopsticks[5]={ 
   1,1,1,1,1}; semaphore mutex=1;//取筷子信号量 P i()//i号哲学家进程 { 
    while(1) { 
    P(mutex)： P(chopsticks[i]);//拿左 P(chopsticks[i+1]%5);//拿右 V(mutex); 吃饭 V(chopsticks[i]);//拿左 V(chopsticks[i+1]%5);//拿右 思考 } } 

9.

【答案】

（1）解:在汽车行驶过程中,司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门让乘客.上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步

int s1=0;//表示是否允许司机启动车辆 int s2=0;//表示是否允许售票员开门 driver() { 
    P(S1); 启动车辆 正常行车 到站停车 V(S2); } Conductor() { 
    关车门 V(S1) 售票 P(S2); 开车门 }