第三章-并发进程的同步、互斥、通信与死锁

1.死锁

（1）定义

如果在一个进程集合中的每个进程都在等待只能由该集合中的其它进程才能引发的事件，而无限期陷入僵持的局面称为死锁。

（2）产生死锁的 4 个条件

互斥条件：进程互斥使用资源。
占有和等待条件（部分分配条件）：申请新资源时不释放已占有资源。
不剥夺条件：一个进程不能抢夺其他进程占有的资源。
循环等待条件（环路条件）：存在一组进程循环等待资源的现象。

（3）应对方法

①防止

上述四个条件中前三个条件是死锁产生的必要条件，不是充分条件，第四个条件是前三个条件同时存在时产生的结果，只要破坏这四个条件之一，死锁就可防止。

1）破坏第一个条件

使资源可同时访问而不是互斥使用。

2）破坏第二个条件

静态分配。

3）破坏第三个条件

采用剥夺式调度方法：申请资源未果时主动释放资源，然后去等待。

4）破坏第四个条件

采用层次分配策略，将系统中所有资源排列到不同层次中：

一个进程得到某层的一个资源后，只能再申请较高一层的资源；
当进程释放某层的一个资源时，必须先释放占用的较高层资源；
当进程获得某层的一个资源后，如果想申请同层的另一个资源，必须先释放同层中的已占用资源。

②避免

死锁避免方法允许系统中同时存在死锁的三个必要条件，即互斥、占有且等待和非抢占；每当进程提出资源申请时，系统分析满足该资源请求时系统是否会发生死锁，若不会发生则实施分配，否则拒绝分配。银行家算法就是避免死锁的一种方法。

③银行家算法（Dijkstra 提出）

算法思想：

一个银行家拥有资金 M，被 N 个客户共享，银行家对客户提出下列约束条件：

每个客户必须预先说明自己所要求的最大资金量
每个客户每次提出部分资金量申请和获得分配
如果银行满足了客户对资金的最大需求量，则客户在资金运作后一定可以很快归还资金

银行家算法的基本思想：

系统中的所有进程进入进程集合；
在安全状态下系统收到进程的资源请求后，先把资源试探性分配给它；
系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而保证这个进程运行完毕并归还全部资源；
把这个进程从集合中去掉，系统的剩余资源更多了，反复执行上述步骤；
最后，检查进程集合，若为空表明本次申请可行，系统处于安全状态，可实施本次分配；否则，有进程执行不完，系统处于不安全状态，本次资源分配暂不实施，让申请进程等待。

避免死锁的实质：系统在分配资源时，保证系统不进入不安全状态。

例题视频：

④检测和解除

例题视频：

2.互斥与临界区

（1）定义

并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”。

（2）临界区的调度原则

一次至多允许一个进程进入临界区内；
如果已有进程在临界区中，试图进入此临界区的其他进程应等待；
进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入；
临界区调度原则可总结成四字话：互斥使用、有空让进、忙则等待、有限等待、择一而入、让权等待、算法可行。算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁。

（3）实现临界区管理的硬件设施

用来实现互斥的硬件设施主要有：

关中断（进程在进入临界区之前先关中断，退出临界区时开中断）
测试并建立指令（专用的机器指令）
对换指令（交换两个字的内容）

3.信号量与 PV 操作

（1）定义

在操作系统中，信号量是用来表示物理资源的实体，信号量是一种软资源，是一个与队列有关的整型变量。

（2）应用

①哲学家进餐问题

1）问题描述

有五个哲学家围在一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和物质筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕后，放下筷子继续思考。

2）代码

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

Pi()
{
    P(mutex);
    P(chopstick[i]);           // 拿左边筷子
    P(chopstick[(i + 1) % 5]); // 拿右边筷子
    V(mutex);
    吃饭...;
    V(chopstick[i]);       // 放下左边
    V(chopstick[(i + 1)]); // 放下右边
    思考...;
}

②生产者-消费者问题

单生产者-消费者

1）问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没有满的时候，生产者才能把消息放入缓冲区，否则得等待缓冲区空闲出来；只有缓冲区不空的时，消费者才能从缓冲区取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者取出消息。

2）代码

semaphore mutex = 1; // 临界区互斥信号量
semaphore empty = n; // 空闲缓冲区
semaphore full = 0; // 缓冲区初始化为空

// 生产者
producer()
{
    while (1)
    {
        生产一个产品;
        P(empty); // 获取空缓冲区单元
        P(mutex); // 互斥，进入临界区
        把产品放入缓冲区;
        V(mutex); // 离开临界区，释放互斥信号量
        V(full);  // 满缓冲区数加 1，相当于放入缓冲区了，让缓冲区的数加 1
    }
}

// 消费者
consumer()
{
    while (1)
    {
        P(full);  // 消耗一个产品，如果没有数据就等待
        P(mutex); // 进入缓冲区
        从缓冲区取出一个产品;
        V(mutex); // 离开临界区，释放互斥信号量
        V(empty); // 空缓冲区数加 1
        使用产品;
    }
}

多生产者-消费者

1）问题描述

桌子上有个盘子，每次只能向其中放入一个水果。爸爸只往盘子中放苹果，妈妈只放橘子，儿子专门等盘子中的橘子，女儿则等苹果。只有盘子空时，爸妈才可向盘子放一个水果；当盘子中有自己需要的水果时，儿子或女儿才能取。

2）代码

semaphore plate = 1, apple = 0, orange = 0;

// 父亲进程
father()
{
    while (1)
    {
        准备一个苹果;
        P(plate); // 互斥向盘中取、放水果
        把苹果放入盘子;
        V(apple); // 允许取苹果
    }
}

// 母亲进程
mother()
{
    while (1)
    {
        准备一个橘子;
        P(plate); // 互斥向盘中取、放水果
        把橘子放入盘子;
        V(orange); // 允许取橘子
    }
}

// 儿子进程
son()
{
    while (1)
    {
        P(orange); // 互斥向盘中取橘子
        从盘中取出橘子;
        V(plate); // 允许向盘中取水果，放水果
        吃掉橘子;
    }
}

// 女儿进程
daughter()
{
    while (1)
    {
        P(apple); // 互斥向盘中取苹果
        从盘中取出苹果;
        V(plate); // 允许向盘中取水果，放水果
        吃掉苹果;
    }
}

warning

如果缓冲区数量大于 1，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。

③读写者问题

1）问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：① 允许多个读者可以同时对文件执行读操作；② 只允许一个写者往文件中写信息；③ 任一写者在完成写操作之前不允许其他读者或写者工作；④ 写者执行写操作前，应让已有的读者和写者全部退出。

2）代码

方案 1

设置 rw 和 mutex 两个信号量。rw 信号量用于实现读进程与写进程、写进程与写进程对共享文件的互斥访问。mutex 信号量用于保证对 count 变量的互斥访问。

a62d7354ba5944ffb4ca05e7662404f1

若没有设置 mutex 信号量，两个读进程并发执行到 if 条件且都满足，都会执行 P(rw)，会造成其中一个读进程阻塞的情况。设置 mutex 信号量，使得 count 信号量的检查和赋值操作一气呵成，保证了对 count 信号量访问的互斥性。

方案 1 存在的问题：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的。

方案 2

方案 2 是对方案 1 问题的修正，添加了 w 信号量，保证了读写公平。如：假设对共享文件的访问顺序是：读者 1→读者 2→ 写者 1 → 读者 3，读者 2 执行完后，写者 3 将会进行写文件，读者 3 进程将会被阻塞。待写者 1 写完文件后，读者 3 进行读写者 1 访问后的文件。

2b29530b97b94604b6d6bcafa84d217c

算法核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，还需考虑 count 变量的互斥性。算法实现：连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。算法又称读写公平法。

④睡眠理发师

1）问题描述

一个理发店有 N 张沙发和一张理发椅。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。

2）代码

int wait = 0;           // 顾客等待的数量
semaphore mutex = 1;    // 互斥访问 wait
semaphore barber = 0;   // 理发师信号量
semaphore customer = 0; // 顾客的信号量

// 理发师
void barber()
{
    while (1)
    {
        P(customer);     // 等待顾客来理发
        P(mutex);        // 申请互斥访问 wait
        wait = wait - 1; // 等待人数减少一人
        V(mutex);        // 释放临界资源
        V(barber);       // 让理发师去理发
        进行理发;
    }
}

// 顾客
void customer()
{
    while (1)
    {
        P(mutex); // 申请互斥访问 wait
        if (wait < 10)
        {
            // 代表 10 把椅子没有坐满 还可以坐人
            wait = wait + 1;
            V(mutex);
            V(customer);
            P(barber); // 等待理发师来理发
            去理发;
        }
        else
        {
            // 人满了，顾客直接离开
            V(mutex);
        }
    }
}

4.管程

（1）定义

管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成用来实现同步互斥功能的软件模块。

（2）为什么引入管程

把分散在各进程中的临界区集中起来进行管理；
防止进程有意、无意的违法同步操作；
便于用高级语言书写程序和程序正确性验证。

（3）结构

局部数据和条件变量组成管程内的数据结构
过程/函数 1 ~ 过程/函数 k 组成管程内的一组过程，对管程内的数据结构进行操作
初始化代码：对管程内的数据结构进行初始化

（4）实现

霍尔方法使用锁和条件变量两种同步机制：

使用 PV 操作原语实现锁机制，用于管程中过程的互斥
wait 操作实现在条件变量上的阻塞
当条件满足时使用 signal 操作唤醒进程

不要求 singal 操作是过程体的最后一个操作，且 wait 和 singal 操作可被设计成可以中断的过程

①mutex

信号量 mutex 用于管程中过程互斥调用，初值为 1
进程调用管程中的任何过程时，应执行 P(mutex)；进程退出管程时应执行 V(mutex) 开放管程，以便让其他调用者进入
为了使进程在等待资源期间，其他进程能进入管程，故在 wait 操作中也必须执行 V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源

②next 和 next-count

信号量 next 初值为 0，凡发出 singal 操作的进程应该用 P(next) 挂起自己，直到被释放进程退出管程或产生其他等待条件
进程在退出管程的过程前，须检查是否有别的进程在信号量 next 上等待，若有，则用 V(next) 唤醒它。next-count 初值为 0，用来记录在 next 上等待的进程个数

③x-sem 和 x-count

信号量 x-sem 初值为 0，申请资源得不到满足时，执行 P(x-sem) 挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器 x-count（初值为 0）记录等待资源的进程数
执行 singal 操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用 V(x-sem) 来实现

（5）应用

模拟管程决生产者消费者问题：

7169b03eb4f34d3aa0b4092f3d16b250

两个例题：

①管程只能实现进程的互斥。（×）解析：还有同步（来源：2016 年 408 第 32 题） ②若 x 是管程内的条件变量，则当进程执行 x.wait() 时所做的工作是（D） A. 实现对变量 x 的互斥访问 B. 唤醒一个在 x 上阻塞的进程 C. 根据 x 的值判断该进程是否进入阻塞态 D. 阻塞该进程，并将之插入 x 的阻塞队列中解析：条件变量是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的信号量（但不用修改信号量），都用于实现进程同步。但在同一时刻，管程中只能有一个进程在执行。