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

1.死锁

（1）定义

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

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

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

（3）应对方法

①防止

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

1）破坏第一个条件

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

2）破坏第二个条件

静态分配。

3）破坏第三个条件

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

4）破坏第四个条件

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

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

②避免

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

③银行家算法（Dijkstra提出）

算法思想：

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

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

银行家算法的基本思想：

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

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

例题视频：

④检测和解除

例题视频：

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); // 允许向盘中取水果，放水果
        吃掉苹果;
    }
}

③读写者问题

1）问题描述

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

2）代码

方案1

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

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

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

方案2

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

算法核心思想 在于设置了一个 计数器 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）为什么引入管程

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

（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）应用

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

两个例题：

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

5.进程通信

（1）定义

进程通信(Inter-Process Communication，简称IPC)，是进程之间的信息交换。

（2）分类

• 低级通信：交换信息量少，通信控制复杂

  • 信号通信机制
  • 信号量及其原语操作

• 高级通信：用户直接利用OS提供的通信命令传输大量数据，通信控制细节由OS完成，对用户透明

  • 管道提供的共享文件通信机制
  • 共享存储区通信机制
  • 消息传递通信机制

（3）信号通信机制

定义

信号机制又称软中断，是一种进程之间进行通信的简单通信机制，通过发送一个指定的信号来通知进程某个异常事件发生，并进行适当处理，迫使进程执行信号处理程序，信号处理完毕后，被中断进程将恢复执行。

用户、内核和进程都能生成信号请求：

• 用户：用户能通过输入Ctrl + C，或终端驱动程序分配给信号控制字符的其他任何键来请求内核产生信号
• 内核：当进程执行出错时，内核检测到事件并利用信号通知进程，例如非法段存取、浮点数溢出(SIGFPE)、或非法操作码
• 进程：进程可通过系统调用kill给另一个进程发送信号，一个进程可通过信号与另一个进程通信

（4）管道通信机制

①定义

管道：是连接读写进程实现他们之间通信的一个特殊文件。

管道是一个共享文件，连接读写进程实现通信。写进程往管道一端写入信息，读进程从管道另一端读信息。

管道可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。

②分类

管道分为两种类型：

• 匿名管道（unnamedpipe）
• 命名管道（namedpipe）

1）匿名管道

• 匿名管道是不命名的，是在父进程和子进程之间，或同一父进程的两个子进程之间传输数据的无名字的单向管道；
• 通常由父进程创建管道，然后由要通信的子进程继承通道的读端点句柄或写端点句柄，然后实现通信；
• 父进程还可以建立两个或更多个继承匿名管道读和写句柄的子进程。这些子进程可以使用管道直接通信，不需要通过父进程；
• 匿名管道是单机上实现子进程标准I/O重定向的有效方法，但它不能在网上使用，也不能用于两个不相关的进程之间。

2）命名管道

• 命名管道是服务器进程和一个或多个客户进程之间通信的单向或双向管道；
• 不同于匿名管道的是命名管道可以在不相关的进程之间和不同计算机之间使用，服务器建立命名管道时给它指定一个名字，任何进程都可以通过该名字打开管道的另一端，根据给定的权限和服务器进程通信。

（5）共享存储

定义

指两个或多个进程共同拥有一块内存区，该区中的内容可被进程访问。

• 一个进程首先创建一块内存区作为通信使用，而其余进程则将这块内存区映射到自己的虚存空间也就是说需访问共享内存的进程必须在自身地址空间增加一个新内存区，映射与共享内存区相关的页框；
• 每个进程读写自己的虚地址空间中对应共享内存区时，就可以与其他进程进行通信。

（6）消息传递

消息是格式化的数据，在计算机网络中称之为报文。

消息传递特点：

• 正在执行的进程间可在任何时刻发送/请求消息
• 消息传递机制与进程的阻塞和释放紧密联系
  • 一个进程在某一时刻的执行依赖于另一进程的消息或等待其他进程对发出消息的回答
• 消息传递提供了进程同步能力，进一步扩充了并发进程间对数据的共享