操作系统3：进程同步和经典的进程同步问题

小灰灰 2024-03-16 22:53 54阅读 0赞

**目录**

一、进程同步

1、进程同步的基本概念

（1）两种形式的制约关系

（2）临界资源(Critical Resouce)

（3）临界区(critical section)

（4）同步机制应遵循的规则

2、硬件同步机制

（1）关中断

（2）利用 Test-and-Set 指令实现互斥

（3）利用 Swap 指令实现进程互斥

3、信号量机制

（1）整型信号量

（2）记录型信号量

（3）AND型信号量

（4）信号量集

4、信号量的应用

（1）利用信号量实现进程互斥

（2）利用信号量实现前趋关系

5、管程机制

（1）什么是管程？

（2）条件变量

二、经典的进程同步问题

1、生产者——消费者问题

（1）利用记录型信号量解决生产者-消费者问题

（2）利用AND信号量解决生产者-消费者问题

（3）利用管程解决生产者-消费者问题

2、哲学家进餐问题

（1）利用记录型信号量解决哲学家进餐问题

（2）利用AND信号量机制解决哲学家进餐问题

3、读者——写者问题

（1）利用记录型信号量解决读者-写者问题

（2）利用信号量集机制解决读者-写者问题

--------------------

## 一、进程同步 ##

为保证多个进程能有条不紊地运行，在多道程序系统中，必须引入进程同步机制。单处理机系统中的进程同步机制有：**硬件同步机制、信号量机制、管程机制**等，利用它们可以保证程序执行的可再现性。// 保证程序执行结果的确定性

### 1、进程同步的基本概念 ###

进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。

#### （1）两种形式的制约关系 ####

在多道程序环境下，对于同处于一个系统中的多个进程，由于它们共享系统中的资源或为完成某一任务而相互合作，它们之间可能存在着以下两种形式的制约关系：

**1 - 间接相互制约关系**

多个程序在并发执行时，由于共享系统资源，如 CPU、I/O 设备等，致使在这些并发执行的程序之间形成相互制约的关系。对于像打印机、磁带机这样的临界资源，必须保证多个进程对之只能互斥地访问，由此，在这些进程间形成了源于对该类资源共享的所谓间接相互制约关系。为了保证这些进程能有序地运行，对于系统中的这类资源，必须由系统实施统一分配，即用户在要使用之前，应先提出申请，而不允许用户进程直接使用。// 线程间无协作关系

**2 - 直接相互制约关系**

某些应用程序，为了完成某任务而建立了两个或多个进程。这些进程将为完成同一项任务而相互合作。进程间的直接制约关系就是源于它们之间的相互合作。例如，有两个相互合作的进程一输入进程 A 和计算进程 B，它们之间共享一个缓冲区。进程A 通过缓冲向进程 B 提供数据。进程 B 从缓冲中取出数据，并对数据进行处理。但如果该缓冲空时计算进程因不能获得所需数据而被阻塞。一旦进程 A 把数据输入缓冲区后便将进程 B 唤醒。反之，当缓冲区已满时，进程 A 因不能再向缓冲区投放数据而被阻塞，当进程 B 将缓冲区数据取走后便可唤醒 A。// 线程间相互协作

#### （2）临界资源(Critical Resouce) ####

许多硬件资源如打印机、 磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享。// 即共享资源或者共享变量

#### （3）临界区(critical section) ####

不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问。我们把在每个进程中访问临界资源的那段代码称为临界区（critical section）。

显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。

因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区（entry section）。相应地，在临界区后面也要加上一段称为退出区（exit section）的代码，用于将临界区正被访问的标志恢复为未被访问的标志。进程中除上述进入区、临界区及退出区之外的其它部分的代码在这里都称为剩余区。这样，可把一个访问临界资源的循环进程描述如下：

while(TURE)
        {
            进入区
            临界区
            退出区
            剩余区
        }

#### （4）同步机制应遵循的规则 ####

为实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则：// 准则和重要，即标准

*  空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
 *  忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
 *  有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
 *  让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

// 其实就三个条件：空闲让进、忙则等待、有限等待

### 2、硬件同步机制 ###

许多计算机提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临界区问题。// 使用硬件指令

实际上，在对临界区进行管理时，可以将标志看做一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的时候，则应立即把其锁上，以阻止其它进程进入临界区。显然，为防止多个进程同时测试到锁为打开的情况，测试和关锁操作必须是连续的，不允许分开进行。

#### （1）关中断 ####

关中断是实现互斥的最简单的方法之一。在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。由此，保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥。但是，关中断的方法存在许多缺点：// 局限性很大

*  滥用关中断权力可能导致严重后果。
 *  关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力。
 *  关中断方法也不适用于多CPU 系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

#### （2）利用 Test-and-Set 指令实现互斥 ####

借助一条硬件指令：“测试并建立”指令 TS(Test-and-Set) 实现互斥。在许多计算机中都提供了这种指令。TS 指令的一般性描述如下：

boolean TS(boolean lock){
        Boolean old;
        old = lock;
        lock = TRUE;
        return old;
    }

这条指令可以看作为一个函数过程，其执行过程是不可分割的，即是一条原语。其中，lock 有两种状态：当 lock = FALSE 时，表示该资源空闲；当 lock = TRUE 时，表示该资源正在被使用。

用TS 指令管理临界区时，为每个临界资源设置一个布尔变量 lock，由于变量 lock 代表了该资源的状态，故可把它看成一把锁。lock 初值为 FALSE，表示该临界资源空闲。进程在进入临界区之前，首先用 TS 指令测试 lock，如果其值为 FALSE，则表示没有进程在临界区内，可以进入，并将 TRUE 值赋予 lock，这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试直到 TS(s) 为 TRUE。// 其实就是让检测和设置 lock 的值成为一条原语

利用 TS 指实现斥的循环进程结构可描述如下：

do(
        ...
        while TS(&lock);   // 进入
        critical section;  // 临界区
        lock = FALSE;      // 退出
        remainder section; // 剩余区
    while(TRUE);

#### （3）利用 Swap 指令实现进程互斥 ####

该指令称为对换指令，在 Intel 80x86 中又称为 XCHG 指令，用于交换两个字的内容。其处理过程描述如下：

void swap(boolean a, boolean b){
        boolean temp;
        temp = a;
        a = b;
        b = temp;
    }

用对换指令可以简单有效地实现互斥，方法是为每个临界资源设置一个全局的布尔变量 lock，其初值为 false，在每个进程中再利用一个局部布尔变量 key。利用 Swap 指令实现进程互斥的循环进程可描述如下：// 交换过程是原子的，所以 key 的值不会在同一时刻不同进程出现不同的值

do {
        key = TRUE;
        do {
            swap(&lock, &key);
        } while (key != FALSE);
        临界区操作;
        lock = FALSE;
        ...
    } while(TRUE);

利用上述硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其它访问进程必须不断地进行测试，处于一种 “忙等” 状态，不符合 “让权等待” 的原则，造成处理机时间的浪费，同时也很难将它们用于解决复杂的进程同步问题。// 不能避免忙等问题

### 3、信号量机制 ###

信号量机制已被广泛地应用于单处理机和多处理机系统以及计算机网络中。

#### （1）整型信号量 ####

整型信号量为一个用于表示资源数目的整型量 S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作（Atomic Operation）wait(S) 和 signal(S) 来访问（即 P、V 操作）。wait 和 signal 操作可描述如下：// 等待和唤醒

wait(S){
        while(S<=0); // 循环等待
        S--;
    }
    signal(S){
        S++;
    }

wait(S) 和 signal(S) 是两个原子操作，它们在执行时是不可中断的。

#### （2）记录型信号量 ####

在整型信号量机制中的 wait 操作，只要是信号量 S <= 0，就会不断地测试。因此，该机制并未遵循 “让权等待” 的准则，而是使进程处于 “忙等” 的状态。

记录型信号量机制则是一种不存在 “忙等” 现象的进程同步机制。但在采取了 “让权等待” 的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量 value 外，还应增加一个进程链表指针 list，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。// 信号量 + 阻塞队列

它所包含的上述两个数据项可描述如下：

typedef struct {
        int value;                             // 信号量
        struct process_control_block list;     // 阻塞队列
    } semaphore;

相应地，wait(S) 和 signal(S) 操作可描述如下：

wait(semaphore S){
        S->value--;
        if(S->value < 0) block(S->list); // 进入阻塞队列
    }
    signal(semaphore S){
        S->value++;
        if(S->value<=0) wakeup(S->list); // 从阻塞队列中唤醒
    }

在记录型信号量机制中，S -> value 的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次 wait 操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为 S -> vaue--；// 扣除一个信号量

当 S.value <0 时，表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞，放弃处理机，并插入到信号量链表 S -> list 中。可见，该机制遵循了 “让权等待” 准则。此时 S -> value 的绝对值表示在该信号量链表中已阻塞进程的数目。// 资源缺失，进程等待

对信号量的每次 signal 操作表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个，故 S -> value++ 操作表示资源数目加 1。若加 1 后仍是 S -> vaue <= 0，则表示在该信号量链表中仍有等待该资源的进程被阻塞，故还应调用 wakeup 原语，将 S -> list 链表中的第一个等待进程唤醒。// 唤醒进程

如果 S -> value 的初值为 1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

#### （3）AND型信号量 ####

AND 同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。因为需要在 wait 操作中增加了一个 “AND” 条件，故称为 AND 同步。// 同时分配多个信号量，避免死锁情况的发生

#### （4）信号量集 ####

在前面的记录型信号量机制中，wait(S) 或 signal(S) 操作仅能对信号量施以加 1 或减 1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要 N 个单位时，便要进行 N 次 wait(S) 操作，这显然是低效的，甚至会增加死锁的概率。此外，在有些情况下，为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。因此，当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。//（1）同时对多个资源申请或释放（2）分配之前，检测资源数量

基于上述两点，可以对 AND 信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次 P、V 原语操作中完成申请或释放。进程对信号量 S(i) 的测试值不再是 1，而是该资源的分配下限值 T(i)，即要求 S(i) >= T(i)，否则不予分配。一旦允许分配，进程对该资源的需求值为 D(i)，即表示资源占用量，进行 S(i) = S(i) - D(i) 操作，而不是简单的 S(i) = S(i) - 1。由此形成一般化的 “信号量集” 机制。

对应的 S\_wait 和 S\_signal 格式为：// 这个主要是为了看后边的伪代码

S_wait(S1, T1, D1, ..., Sn, Tn, Dn);
    S_signal(S1, D1, ..., Sn, Dn);

一般 “信号量集” 还有下面几种特殊情况：

*  S\_wait(S,T,D)：此时在信号量集中只有一个信号量 S，但允许它每次申请 D 个资源，当现有资源数少于 T 时，不予分配。（T >= D）
 *  S\_wait(S,1,1)：此时的信号量集已蜕化为一般的记录型信号量（S > 1时）或互斥信号量（S = 1时）。
 *  S\_wait(S,1,0)：这是一种很特殊且很有用的信号量操作。当 S > 1 时，允许多个进程进入某特定区；当 S 变为 0 后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。// 读写锁的实现

### 4、信号量的应用 ###

#### （1）利用信号量实现进程互斥 ####

为使多个进程能互斥地访问某临界资源，**只需为该资源设置一互斥信号量 mutex**，并设其初始值为 1，然后将各进程访问该资源的临界区 CS 置于 **wait(mutex)** 和 **signal(mutex)** 操作之间即可。

**实现原理：**每个欲访问该临界资源的进程在进入临界区之前，都要先对 mutex 执行 wait 操作，若该资源此刻未被访问，本次 wait 操作必然成功，进程便可进入自己的临界区，这时若再有其它进程也欲进入自己的临界区，由于对 mutex 执行 wait 操作定会失败，因而此时该进程阻塞，从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对 mutex 执行 signal 操作，以便释放该临界资源。// 临界资源的获取逻辑

利用信号量实现两个进程互斥的描述如下：

**1 -** 设 mutex 为互斥信号量，其初值为 1，取值范围为 （-1，0，1）。当 mutex=1 时，表示两个进程皆未进入需要互斥的临界区；当 mutex=0 时表示有一个进程进入临界区运行，另外一个必须等待，挂入阻塞队列；当 mutex=-1 时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。

**2 -** 代码描述：

semaphore mutex=1;
    // 进程1
    PA(){
        while(1){
            wait(mutex);
            临界区;
            signal(mutex);
            剩余区;
        }
    }
    // 进程2
    PB(){
        while(1){
            wait(mutex);
            临界区;
            signal(mutex);
            剩余区;
        }
    }

在利用信号量机制实现进程互斥时应该注意，wait(mutex) 和 signal(mutex) 必须成对地出现。缺少 wait(mutex) 将会导致系统混乱，不能保证对临界资源的互斥访问；而缺少 signal(mutex)将会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程不能被唤醒。

#### （2）利用信号量实现前趋关系 ####

还可利用信号量来描述程序或语句之间的前趋关系。

假设有两个并发执行的进程 P1 和 P2。P1 中有语句 S1；P2 中有语句 S2。我们希望在 S1 后再执行 S2。为实现这种前趋关系，只需使进程 P1 和 P2 共享一个公用信号量 S，并赋予其初值为 0，将 signal(S) 操作放在语句 S1 后面，而在 S2 语前面插入 wait(S) 操作，即

在进程 P1 中，用:
        S1; signal(S);  // S1 之后唤醒
    
    在进程 P2 中，用: 
        wait(S); S2;    // S2 之前等待

由于 S 被初始化为 0 ，这样若 P2 先执行必定阻塞，只有在进程 P1 执行完 S1；signal(S)；操作后，使 S 增为 1 时，P2 进程方能成功执行语句 S2。// 控制 S1 -> S2 的执行顺序

### 5、管程机制 ###

虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作 waitS) 和 signal(S)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的**进程同步工具：管程（Monitors）**。// 解决大量信号量分散，管控难度大等问题

#### （1）什么是管程？ ####

系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表示该资源，而忽略它们的内部结构和实现细节。// 资源可以被抽象

因此，可以利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程。进程对共享资源的申请、释放和其它操作必须通过这组过程，间接地对共享数据结构实现操作。对于请求访问共享资源的诸多并发进程，可以根据资源的情况接受或阻塞，确保每次仅有一个进程进入管程，执行这组过程，使用共享资源，达到对共享资源所有访问的统一管理，有效地实现进程互斥。// 定义一个过程，对资源进行同一管理

代表**共享资源的数据结构**以及由**对该共享数据结构实施操作的一组过程**所组成的资源管理程序共同构成了一个操作系统的资源管理模块，我们称之为**管程**。管程被请求和释放资源的进程所调用。// 管程是一个资源管理程序：数据结构 + 操作过程

由上述的定义可知，管程由四部分组成：

*  管程的名称
 *  管程的共享数据结构
 *  对数据结构进行操作的一组过程
 *  对管程的共享数据设置初始值的语句

下图是一个管程的示意图：

![813d2bb9eb09456ab4f22a8854e16811.png][]

管程的语法描述如下：

Monitor monitor_name{                 /*管程名*/
        share variable declarations;      /*共享变量说明*/
        cond declarations;                /*条件变量说明*/
        public:                           /*能被进程调用的过程*/
            void P1(......)               /*对数据结构操作的过程*/
            {......}
            void P2(......)               
            {......}
            ...... 
            void PN(......)              
            {......}
            ...... 
        {                                 /*管程主体*/
            initialization code;          /*初始化代码*/
            ......
        }
    }

管程中包含了面向对象的思想，它将表示共享资源的数据结构及其对数据结构操作的一组过程，包括同步机制，都集中并封装在一个对象内部，隐藏了实现细节。封装于管程内部的数据结构仅能被封装于管程内部的过程所访问，任何管程外的过程都不能访问它；反之，封装于管程内部的过程也仅能访问管程内的数据结构。所有进程要访问临界资源时，都只能通过管程间接访问，而管程每次只准许一个进程进入管程，执行管程内的过程，从而实现了进程互斥。// 管程的工作原理，管程是对资源同步操作的进一步抽象

管程主要有以下特性：// 管程就是一个封装好的程序

*  模块化，即管程是一个基本程序单位，可以单独编译
 *  抽象数据类型，指管程中不仅有数据，而且有对数据的操作
 *  信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，当供管程外的进程调用时，管程中的数据结构以及过程的具体实现对外部不可见

**管程和进程的区别**

*  虽然二者都定义了数据结构，但进程定义的是私有数据结构 PCB，管程定义的是公共数据结构，如消息队列等
 *  二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关操作，而管程主要是进行同步操作和初始化操作
 *  设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题
 *  进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程则为主动工作方式
 *  进程之间能并发执行，而管程则不能与其调用者并发
 *  进程具有动态性，由 “创建” 而诞生，由 “撤消” 而消亡，而管程则是操作系统中的一个资源管理模块，供进程调用。

// 两者的区别还是很大的，虽然都是一段程序，都定义了自己的数据结构，但本质上就不是同一个东西

// 操作系统也就是一套程序，用来操作硬件指令，实现资源的管理，例如 Linux 就是用 C 写的

#### （2）条件变量 ####

在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语 wait 和 signal。当某进程通过管程请求获得临界资源而未能满足时，管程便调用 wait 原语使该进程等待，并将其排在等待队列上。仅当另一进程访问完成并释放该资源之后，管程才又调用 signal 原语，唤醒等待队列中的队首进程。

但是仅仅有上述的同步工具是不够的，考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间的等待。为了解决这个问题，引入了条件变量 condition。通常，一个进程被阻塞或挂起的条件可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。// 是用条件变量的原因，条件来分配管程

管程中对每个条件变量都须予以说明，其形式为：conditionx,y；对条件变量的操作仅仅是 wait 和 signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为 x.wait 和 x.signal，其含义为：

*  x.wait：正在调用管程的进程因 x 条件需要被阻塞或挂起，则调用 x.wait 将自己插入到 x 条件的等待队列上，并释放管程，直到 x 条件变化。此时其它进程可以使用该管程。
 *  x.signal：正在调用管程的进程发现 x 条件发生了变化，则调用 x.signal，重新启动个因 x 条件而阻寨或挂起的进程，如果存在多个这样的进程，则选择其中的一个，如果没有，继续执行原进程，而不产生任何结果。这与信号量机制中的 signal 操作不同。因为后者总是要执行 s=s+1 操作，因而总会改变信号量的状态。

// 为不同条件设置不同的阻塞队列，从而不阻塞其他进程对管程的使用

## 二、经典的进程同步问题 ##

### 1、生产者——消费者问题 ###

生产者-消费者问题（The proceducer-consumer problem）是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此，该问题有很大的代表性及实用价值。// 进程合作问题的抽象

![91f24b0e45d0452ab9de0ec26f47055d.png][]

#### （1）利用记录型信号量解决生产者-消费者问题 ####

假定在生产者和消费者之间的公用缓冲池中具有 **n** 个缓冲区，这时可利用互斥信号量 **mutex** 实现诸进程对缓冲池的互斥使用；利用信号量 **empty** 和 **full** 分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

对生产者 - 消费者问题可描述如下：

//缓冲区存数据指针和取数据指针
    int in=0, out=0
    //缓冲区
    item buffer[n];
    //信号量
    semaphore mutex=1,empty=n,full=0;
    
    //生产者
    void proceducer(){
        do {
            producer an item nextp; //生产元素
            ...
            wait(empty); //获取一个缓冲块: empty-1
            wait(mutex); //获取信号量: mutex-1
            buffer[in] = nextp;
            in = (in+1) % n; // 调整指针
            signal(mutex); //释放信号量: mutex+1
            signal(full);  //通知消费+1: full+1
        }while(TRUE);
    }
    
    //消费者
    void consumer() {
        do {
            wait(full); //等待full信号量: full-1
            wait(mutex); //获取信号量: mutex-1
            nextc = buffer[out];
            out =(out+1)% n;
            signal(mutex);
            signal(empty);
            consumer the item in nextc; //消费数据
        } while(TRUE);
    }
    
    //主函数
    void main(){
        cobegin
            proceducer();consumer();
        coend
    }

在生产者 - 消费者问题中应注意：首先，在每个程序中用于实现互斥的 wait(mutex) 和 signal(mutex) 必须成对地出现；其次，对资源信号量 empty 和 full 的 wait 和 signal 操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty) 在计算进程中，而 signal(empty) 则在打印进程中，计算进程若因执行 wait(empty) 而阻塞，则以后将由打印进程将它唤醒；最后，在每个程序中的多个 wait 操作顺序不能颠倒。应先执行对资源信号量的 wait 操作，然后再执行对互斥信号量的 wait 操作，否则可能引起进程死锁。// 信号量的等待和通知必须成对出现

#### （2）利用AND信号量解决生产者-消费者问题 ####

对于生产者-消费者问题，也可利用 AND 信号量来解决，用 Swait(empty，mutex) 来代替 wait(empty) 和 wait(mutex)；用 Ssignal(mutex，full) 来代替 signal(mutex) 和 signal(full)：用 Swait(full，mutex) 代替 wait(full) 和 wait(mutex)，以及用 Ssignal(mutex，empty) 代替Signal(mutex) 和 Signal(empty)。// 把分散信号量操作聚集到一起

利用 AND 信号量来解决生产者-消费者问题的算法中的生产者和消费者可描述如下：

//缓冲区存数据指针和取数据指针
    int in=0, out=0
    //缓冲区
    item buffer[n];
    //信号量
    semaphore mutex=1,empty=n,full=0;
    
    //生产者
    void proceducer(){
        do {
            producer an item nextp; //生产元素
            ...
            Swait(empty，mutex); //获取信号量-1
            buffer[in] = nextp;
            in = (in+1) % n; // 调整指针
            Ssignal(mutex，full); //释放信号量+1
        }while(TRUE);
    }
    
    //消费者
    void consumer() {
        do {
            Swait(full，mutex); //获取信号量-1
            nextc = buffer[out];
            out =(out+1)% n;
            Ssignal(mutex，empty); //释放信号量+1
            consumer the item in nextc; //消费数据
        } while(TRUE);
    }

#### （3）利用管程解决生产者-消费者问题 ####

在利用管程方法来解决生产者-消费者问题时，首先需要为它们建立一个管程，并命名为procducer\_consumer，或简称为 PC。其中包括两个过程：

*  **put(x)** 过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量 count 来表示在缓冲池中已有的产品数目，当 count >= N 时，表示缓冲池已满，生产者须等待。//放数据
 *  **get(x)** 过程。消费者利用该过程从缓冲池中取出一个产品，当 count ≤ 0 时，表示缓冲池中已无可取用的产品，消费者应等待。//取数据

对于条件变量 not\_full 和 not\_empty，分别有两个过程 c\_wait 和 c\_signal 对它们进行操：

*  **c\_wait(condition)** 过程：当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条件 condition 的队列上。//阻塞在条件队列
 *  **c\_signal(condition)** 过程：唤醒在 c\_wait 执行后阻塞在条件 condition 队列上的进程，如果这样的进程不止一个，则选择其中一个实施唤醒操作；如果队列为空，则无操作而返回。//从条件队列唤醒

PC管程可描述如下：

//定义一个管程
    Monitor procducer_consumer {
        //缓冲区
        item buffer[N];  
        //缓冲区指针
        int in, out;
        //条件
        condition not_full, not_empty;
        //计数
        int count;
        //控制过程
        public:
            void put(item x) {
                if(count >= N) c_wait(not_full); //如果缓冲区满，需等待，信号-1
                buffer[in] = x; 
                in = (in+1) % N; 
                count++                          //缓冲区存放数据数量+1
                c_signal(not_empty);             //释放缓冲区部位空信号，信号+1
            }
    
            void get(item x) {
                if (count <= 0) c_wait(not_empty); //如果缓冲区为空，需等待，信号-1
                x = buffer[out];
                out =(out+1) % N;
                count--;
                c_signal(not_full);                //释放信号，信号+1
            }
        //初始化指针的值
        {in=0;out=0;count=0;}
    }JPC;

在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：

//生产者
    void producer() {
        item x;
        while(TRUE) {
            ...
            produce an item in nextp;
            PC.put(x);     //使用管程放数据，放数据过程中buffer资源互斥
        }
    }
    
    //消费者
    void consumer) {
        item x;
        while(TRUE) {
            PC.get(x);    //使用管程取数据，取数据过程中buffer资源互斥
            consume the item in nextc;
            ...
        }
    }
    
    //主函数
    void main(){
        co_begin
            proceducer(); consumer();
        co_end
    }

### 2、哲学家进餐问题 ###

哲学家进餐问题(The Dinning Philosophers Problem)。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。// 多进程多资源同步问题

![e0cec64c7fd14b3fa1c82e9df8cd9e02.png][]

#### （1）利用记录型信号量解决哲学家进餐问题 ####

经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。

其描述如下：// 把共享资源数量抽象为信号量

semaphore chopstick[5] = {1,1,1,1,1};

所有信号量均被初始化为 1，第 i 位哲学家的活动可描述为：

do {
        wait(chopstick[i]);            //获取左边筷子，chopstick-1
        wait(chopstick[(i+1)%5]);      //获取右边筷子，chopstick-1
        ...
        //eat
        ...
        signal(chopstick[il);          //释放左边筷子，chopstick+1
        signal(chopstick[(i+1)%5]);    //获取右边筷子，chopstick+1
        ...
        //think
        ...
    } while(TRUE);

在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行 wait(chopstick\[i\])；成功后，再去拿他右边的筷子，即执行 wait(chopstick\[(i+1)%5\])；又成功后便可进餐。进餐毕，又先放下他左边的筷子，然后再放他右边的筷子。//按照顺序拿筷子

虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但却有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量 chopstick 均为 0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。//引发死锁问题

对于这样的死锁问题，可采取以下几种解决方法：

*  至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。//限制进程数
 *  仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。//资源获取不可中断
 *  规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是 1、2 号哲学家竞争 1号筷子；3、4 号哲学家竞争 3 号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

#### （2）利用AND信号量机制解决哲学家进餐问题 ####

在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是一个 AND 同步问题，故用 AND 信号量机制是最简洁的解法。// 一个进程需要使用多个临界资源

//定义临界资源
    semaphore chopstick chopstick[5]= {1,1,1,1,1};
    
    do {
        ...
        //think
        ...
        Sswait(chopstick[(+1)%5], chopstick[i]);  //同时锁定两个信号量+2
        ...
        //eat
        ...
        Ssignal(chopstick[(i+1)%5], chopstick[i]); //同时释放两个信号量-2
    } while(TRUE);

### 3、读者——写者问题 ###

一个数据文件可被多个进程共享，如果把只要求读该文件的进程称为 **“Reader进程”**，其他进程则称为 **“Writer 进程”**。允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共享对象。因为这种访问将会引起混乱。// 读写锁，即共享锁和排他锁

所谓 “读者-写者(Reader-Writer Problem)问题” 是指保证一个 Writer 进程必须与其他进程互斥地访问共享对象的同步问题。

#### （1）利用记录型信号量解决读者-写者问题 ####

为实现 Reader 与 Writer 进程间在读或写时的互斥而设置了一个互斥信号量 w\_mutex。另外，再设置一个整型变量 Read\_count 表示正在读的进程数目。由于只要有一个 Reader 进程在读，便不允许 Writer 进程去写。因此，仅当 read\_count = 0，表示尚无 Reader 进程在读时，Reader 进程才需要执行 wait(w\_mutex) 操作。若 wait(w\_mutex) 操作成功，Reader 进程便可去读，相应地，做 read\_count\+1 操作。// 写读互斥，读读共享

同理，仅当 Reader 进程在执行了 read\_count 减 1 操作后其值为 0 时，才须执行 signal(w\_mutex) 操作，以便让 Writer 进程写操作。又因为 read\_count 是一个可被多个 Reader 进程访问的临界资源，因此，也应该为它设置一个互斥信号量 r\_mutex。

![111507b718574102ab5f443db6664748.png][]

读者-写者问题可描述如下：

//定义读信号量，写信号量
    semaphore r_mutex=1，w_mutex=l;
    //读进程统计
    int read_count = 0;
    
    //读操作
    void reader() {
        do {
            wait(r_mutex);                     //读信号量 -1
            if(read_count==0) wait(w_mutex);   //读操作进入时，阻塞写操作
            readcount++;                       //临界资源，读进程数+1
            signal(r_mutex);                   //释放读信号量+1
            ...
            perform read operation;            //此时读操作中仍然持有写信号量
            ...
            wait(r_mutex);                     
            readcount--;
            if(read_count==0) signal(w_mutex); //读操作退出时，如果读进程数量为0，释放写信号量
            signal(r_mutex);
        } while(TRUE)
    }
    
    //写操作
    void writer() {
        do {
            wait(w_mutex);             //写操作，写信号量-1
            perform write operation;
            signal(w_mutex);           //退出写操作，写信号量+1
        } while(TRUE);
    }
    
    //主函数
    void main(){
        cobegin
            writer();reader();
        coend
    }

#### （2）利用信号量集机制解决读者-写者问题 ####

这里的读者一写者问题，与前面的略有不同，它增加了一个限制，即最多只允许 RN 个读者同时读。为此，又引入了一个信号量 L，并赋予其初值为 RN，通过执行 wait(L,1,1) 操作来控制读者的数目，每当有一个读者进入时，就要先执行 wait(L,1,1) 操作，使 L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN+1 个读者要进入读时，必然会因 wait(L,1,1) 操作失败而阻塞。

// 格式说明：wait（信号量，下限值，需求量），当信号量 < 下限值，不允许分配信号量，阻塞

// signal（信号量，释放量）

对利用信号量集来解决读者-写者问题的描述如下：

//定义读者数量
    int RN;
    //定义信号量L、信号量mx
    semaphore L=RN, mx=1;
    
    //读操作
    void reader() {
        do {
            Swait(L, 1, 1);             // 信号量L,下限值1,当 L>=1 时，分配1个信号量
            Swait(mx, 1, 0);            // 信号量mx,下限值1,当 L>=1 时，分配0个信号量，也就是不扣减 mx 信号量
            perform read operation;
            ...
            Ssignal(L, 1);              // 释放一个L信号量，L+1
        } while(TRUE);
    }
    
    //写操作
    void writer() {
        do {
            Swait(mx, 1, 1, L, RN, 0);  // 同时满足，mx>=1，扣减1个mx && L=RN,不扣减L数量
            perform write operation;
            Ssignal(mx, 1);             // 释放mx
        } while(TRUE);
    }
    
    //主函数
    void main() {
        cobegin
            reader(); writer();
        coend
    }

其中，Swait(mx,1,0) 语句起着开关的作用。只要无 writer 进程进入写操作，mx=1，reader 进程就都可以进入读操作。但只要一旦有 writer 进程进入写操作时，其 mx=0，则任何 reader 进程就都无法进入读操作。Swait(mx, 1, 1, L, RN, 0) 语句表示仅当既无 writer 进程在写操作 (mx =1) 且无 reader 进程在读操作 (L=RN) 时，writer 进程才能进入临界区进行写操作。

// 只有在写操作时，才会扣减 mx 信号量，但同时确保没有进程在进行读操作，mx = 1 表示只允许 1 个进程进行写操作

// 读操作会扣减 L 的数量，但是也需要确保没有进程在写，即 mx = 1，L=RN，表示最多允许 RN 个进程一起读

// 该方式限制了读操作的进程数量，相比记录型信号量方式有一定的限制性

[813d2bb9eb09456ab4f22a8854e16811.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/89e2f42320284bbd9d9a8676e7d1d19d.png
[91f24b0e45d0452ab9de0ec26f47055d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4a8a34b028dd435d9ac1666929080248.png
[e0cec64c7fd14b3fa1c82e9df8cd9e02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/0f4f779980214efe8f5011033711e2d4.png
[111507b718574102ab5f443db6664748.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a585e21b3a4340fcbc3592e44231ccb0.png