操作系统之 进程与线程

进程

基本概念

你有没有想过，打开一个应用程序，操作系统都做了些什么？如果了解计算机结构的同学可能知道，程序会把需要用到的资源从移动到内存中使用，CPU会处理这些数据。实际上，操作系统为这个应用程序创建了一个名叫进程的东西，一个应用程序运行所需的东西都包含在这一个进程中。

专业一点来讲：进程是计算机中执行程序的基本单位，是程序在运行时的一个实例。它是操作系统进行资源分配和调度的基本单位。

在Windows操作系统，你可以打开任务管理器查看进程的详细信息。

每一个进程都有自己独一无二的标识符，称为进程ID，简写为PID。即使我们打开了多个相同的软件，操作系统也会为打开的软件创建不同的进程，进程之间的PID各不相同。即使这个进程已经终止了，新生成的进程也不会覆盖终止进程的PID。

进程的组成

操作系统为应用程序创建了一个实例，也就是进程，进程可以反映在内存中。在内存中进程一个进程由以下几个部分组成：

• PCB（进程控制块）：进程的详细信息，例如上图中CPU占用，内存占用的信息都保存在这个部分。操作系统控制进程只依赖于PCB。

• 程序段：程序的代码，一些指令组成。

• 数据段：程序运行保存的数据，在C++中可以分为栈内存、堆内存等等。

PCB是进程存在的唯一标志。

进程的特征

程序是静态的，存储在硬盘中。当我们打开程序，创建了进程，进程是动态的，进程有以下特征：

• 动态性：进程是程序的一次执行过程，动态产生，变化和消亡。

• 并发性：内存中可以有多个进程实体，并发运行。

• 独立性：进程是能够独立运行、独立获得资源、独立接受调度的最基本单位。

• 异步性：各进程是各自独立，不可预知的速度向前推进。操作系统需要提供进程同步机制来解决异步问题。

• 结构性：每个进程都有PCB。也后又程序段，数据段。

进程的状态

一个进程有以下5个状态，这些状态也定义在了PCB中：

1. 创建状态；

2. 就绪状态；

3. 运行状态；

4. 阻塞状态；

5. 终止状态。

其中就绪、运行和阻塞是基本状态。这些状态的转换如下图所示。

当我们双击打开一个应用程序的时候，进程就进入了创建态。带进程创建所需的工作进行完毕后，进程处于就绪态。CPU开始处理这个进程时（进程被调度），进程就过渡到运行态。如果进程需要等待某些资源可用时才能继续运行，该线程就会被暂时搁置，线程转换到了阻塞态。待资源可用时，进程又回到了就绪态。CPU是能处理的是有限的，为了保证每个进程都能及时得到处理，每个进程都有一个固定的时间片，时间片耗尽，进程就会从运行态切换到就绪态。若进程运行结束，或是发生异常退出，进程就会切换到终止态，操作系统会回收这个进程的资源，删除这个进程。

进程的组织方式

进程由各种的状态，操作系统可以根据PCB中的字段来识别当前进程的状态。此外操作系统还需要建立一定的数据结构来组织这些进程。常用的组织方式有链接方式和索引方式。

链接方式

链接方式中操作系统维护了几个的指针。例如执行指针，指向的PCB为正在执行进程的指针。再例如就绪队列指针，指针指向的是就绪态的进程。优先级较高的进程放在队头。

操作系统还会根据阻塞原因的不同，分为多个阻塞队列，如下图所示。

索引方式

操作系统中维护几个指针，但这几个指针指向的是索引表。操作系统会根据进程状态的不同，建立几张索引表。如下图所示：

进程的控制

操作系统可以控制进程，例如创建新进程，销毁已有进程，进程状态切换等功能。一言以蔽之，进程控制就是实现进程的状态转换。

原语

进程控制由操作系统内核中的原语实现。原语是在操作系统和并发编程中，作为基本操作的最小单位。原语具有原子性，它们通常是不可分割的操作，即在执行过程中不会被中断。

操作系统进程的状态转换之所以需要原语实现，是因为进程转换需要一系列操作，例如更改PCB的字段，在索引表中添加删除信息等。如果中途中断了运行过程，可能会导致进程同时出现在两个索引表中，造成难以预计的影响。

CPU可以通过关中断指令和开中断指令来完成操作的原子性。当CPU接收到关中断指令后，在执行后面的指令时不会受到中断信号的影响，直到接收到开中断指令，因此就实现了原子性。具体的流程图如下所示：

进程的创建

操作系统创建进程需要执行创建原语。创建原语的步骤如下：

• 申请空白PCB；

• 为新进程分配所需要的资源；

• 初始化PCB；

• 将PCB插入到就绪队列。

进程的终止

操作系统终止进程需要执行撤销原语。撤消原语的步骤如下：

• 从PCB集合中找到终止进程的PCB；

• 进程正在运行则立刻剥夺CPU，将CPU分配给其他进程；

• 终止所有子进程；

• 将该进程拥有的所有资源归还给父进程或操作系统；

• 删除PCB。

进程的阻塞

操作系统终止进程需要用到阻塞原语。阻塞原语的步骤如下：

• 找到阻塞进程对应的PCB；

• 保护进程的运行现场，将PCB的信息状态设置为“阻塞态”，暂时停止进程运行。

• 将PCB插入相应时间的等待队列。

进程的唤醒

操作系统唤醒进程需要唤醒原语，其步骤如下：

• 将时间等待队列中找到PCB；

• 将PCB从等待队列移除，设置进程为就绪态

• 将PCB插入就绪队列，等待被调度。

进程切换

进程切换需要切换原语，其步骤如下：

• 将运行环境信息存入PCB；

• PCB移入相应队列；

• 选择另一个进程执行，并更新其PCB；

• 根据PCB回复新进程所需要的运行环境。

在这里需要注意：运行环境信息是什么？通常来说，CPU执行指令是根据寄存器中的信息进行运行。

CPU中的寄存器是用于存储数据、指令和状态信息的高速存储单元。

在进程切换时，操作系统需要保存当前进程的状态，以便在以后恢复。以下是通常存储在进程控制块（PCB）中的寄存器信息：

• 程序计数器（PC）：指向当前执行指令的地址。

• 堆栈指针（SP）：指向当前堆栈的顶部，保存函数调用的上下文。

• 通用寄存器：所有通用寄存器的值，以便在恢复时能够恢复进程的状态。

• 状态寄存器/标志寄存器（PSW）：保存当前进程的状态信息，指示运算结果的状态。

• 基址寄存器和索引寄存器（如果适用）：用于存储内存地址的寄存器值。

进程通信 IPC

进程之间分配的内存是独立的，通常情况下进程之间是相互独立互不影响的。但是有的时候进程之间也需要通信。一个常见的场景：一个应用程序需要登陆，跳转到了浏览器进行登录。登陆完成后浏览器会将信息传送给应用程序。浏览器和应用程序就是两个独立的进程，两个进程需要通信才能完成这个操作。

进程通信需要操作系统把控。假如说进程之间的通信是随意的，那么一个恶意程序能够很轻松的修改其他的程序，或是破坏其他程序。这是需要操作系统来进行判断是否允许该进程完成某些进程通信，来最大程度的保护系统的安全性。

最常见的例子就是UAC系统，这是内置在Windows操作系统的一个用户权限控制系统，能够控制程序的一些行为。

进程之间的通信方式有以下几种：

• 共享内存

• 消息传递

• 管道通信

共享内存

共享内存是一种允许多个进程访问同一块内存区域的技术。通过这种方式，进程可以直接读写共享内存中的数据，而不需要通过操作系统的系统调用进行数据传输。

需要注意的是，进程间访问共享内存区是互斥的。来避免避免数据竞争和不一致性。可以使用操作系统内核提供的同步互斥工具。

共享内存也分为低级通信方式和高级通信方式：

• 基于数据结构的共享是一种低级共享方式。例如，共享空间中放入长度固定的数组。

• 基于存储区的共享是一种高级共享方式。数据的形式和存放位置由通信进程控制。

下面是一个简单的共享内存示例实验，在Windows和C++环境下分别运行：

sharing_memory_reader.cpp

sharing_memory_writer.cpp

先运行写入程序，再运行读取程序，可以看到两个进程间成功分享了字符串。

消息传递

消息传递机制允许一个进程发送消息到另一个进程，接收方可以接收并处理这些消息。这种方式通常是异步的，发送方和接收方不需要同时运行。

进程间传送消息需要用到两个原语和一个格式化的消息。发送进程首先编辑好格式化的消息，这个消息包括消息头（存储发送进程ID，消息长度等信息）和消息体（发送的消息），通过发送消息原语将消息存放在消息队列中。收取消息的进程通过接受消息原语收取收到的消息。通过读取消息体就可以实现消息的首发。

消息传递方式分为间接通信方式和直接通信方式：

• 间接通信方式：发送的消息不指定PID，存放在固定信箱中，收取消息则直接从信箱中获取信息。

• 直接通信方式：指定目的PID。

管道

管道是IPC的一种机制。允许一个进程将数据传输到另一个进程，实现过程简单。

管道遵循队列的先进先出FIFO原则，一个管道只能一个进程输入数据，另一个进程输出数据，支持数据的单向流动，或是不同时刻的双向流动（半双工）。想要实现同时双向通信（全双工），则需要两个管道。

管道的读写操作通常是阻塞的。当没有数据可读时，读取操作会阻塞；当管道已满时，写入操作也会阻塞。可以通过设置管道为非阻塞模式来避免这种情况。

管道的内部实现原理是在内存开辟了一块大小固定的内存缓冲区。这个缓冲区的大小通常是固定的，具体大小取决于操作系统的实现（例如，Linux上通常是64KB）。许多实现使用环形缓冲区来管理数据，这样可以有效地利用内存并支持高效的读写操作。

多个进程可以同时读和写管道，但需要互斥的访问。

下面是Windows下C++的管道实验程序：

pipe_server.cpp

pipe_client.cpp

先打开服务器程序，再打开客户端程序，客户端会通过管道给服务器发送消息。如下图所示：

命名管道可以实现两个不相关的进程之间的通信，非命名管道可以实现父子进程之间的通信。

对比

线程

线程的概念

操作系统需要并发的执行应用程序，这没有错。正因为进程的存在，我们能够在操作系统上同时运行多个程序。但是这些应用程序，也需要并发的运行一些模块，一个很简单的例子：带有UI界面的应用程序，其内部逻辑和UI系统通常是分开运行的，而分开运行的这些模块，就是放在了线程之中运行。

引入了线程，线程成了程序执行流的最小单位。而进程是系统资源的分配单元。线程可以看作是轻量级进程。

在系统开销方面，切换线程比切换进程开销要小得多。因为切换进程的步骤比较复杂，需要处理运行环境信息。

线程的属性

线程有以下属性：

• 线程是处理机调度的基本单位；

• 在多CPU计算机中，各个线程可以占用不同的CPU；

• 每个线程也有一个线程ID，线程控制块（TCB）；

• 线程也有就绪、阻塞和运行三种基本状态；

• 线程几乎不拥有系统资源；

• 统一进程的不同线程间共享进程的资源；

• 同一进程中的线程间通信几乎无需系统干预；

• 同一进程中的线程切换不会引起进程切换；

• 不同进程中的线程切换会引起进程切换；

• 切换同进程内的线程，系统开销很小；

• 切换进程，系统开销很大。

线程的实现方式

用户级线程

早期的多线程是由线程库实现的，称为用户级线程。操作系统只能看得到进程，却看不到线程。

下面是一个简单实现用户级线程的伪代码：

int main()
{
  int i = 0;
  while(true)
  {
    if (i == 0){模块1代码}
    if (i == 1){模块2代码}
    if (i == 2){模块3代码}
    i = (i + 1) % 3;
  }
}

用户级线程线程的管理工作全部由应用程序内部负责，不涉及CPU状态的转换。

• 优点：CPU不需要状态的转换，效率更高，开销小。

• 缺点：一个用户级进程被阻塞，则整个进程会被阻塞，并发度不高。

内核级线程

内核级线程是操作系统支持的线程。线程的管理现在可以由操作系统来完成。线程切换需要操作系统切换到内核态才能执行。

• 优点：一个线程阻塞，其他线程还能继续运行；

• 缺点：一个用户进程会占用多个内核级线程，线程切换需要转换到核心态，线程管理的成本高，开销大。

多线程模型

由用户级线程和内核级线程的特性，我们可以总结出以下三种多线程模型：

• 一对一模型；

• 多对一模型；

• 多对多模型；

一对一模型

一对一模型指的是一个用户级线程映射到一个内核级线程。有多少个用户级线程，就有多少个内核级线程。

多对一模型

多个用户级线程值映射到一个内核级线程，且一个进程只能被分配到一个内核级线程。

多对多模型

n个用户线程映射到m个内核级线程（n \geq m）。

当内核级线程中的所有线程都阻塞，整个进程才会阻塞。

对比

线程的状态与切换

上面说到，线程有三种状态：就绪态、运行态、阻塞态。这三种状态的转换和进程类似。

线程的结构

线程也有一块专属的控制块来存放线程的有关信息，称为线程控制块（TCB）。线程控制块包含了以下的信息：

• 线程标识符（TID）：唯一标识线程的ID，用于区分不同的线程。

• 线程状态：表示线程当前的状态，如运行、就绪、阻塞。

• 程序计数器（PC）：指向当前线程执行的下一条指令的地址。

• 寄存器状态：包含线程在上下文切换时的寄存器值，以便在恢复线程时能够正确恢复执行状态。

• 堆栈指针：指向线程的栈空间，存储局部变量和函数调用等信息。

• 优先级：线程的优先级信息，用于调度算法决定线程的执行顺序。

• 调度信息：包含调度算法所需的其他信息，如时间片、等待队列等。

• 线程的资源信息：线程所占用的资源，如打开的文件描述符、内存块等。

• 父线程/进程信息：线程所属的进程ID或父线程ID。

• 同步信息：线程之间的同步机制信息，如信号量、互斥锁等。

可以将多个TCB组织成线程表以便查询使用。

调度

调度的基本概念

假如说有几个进程（或者内核级线程）需要在处理机上运行，但是处理机只能同时运行一个（或几个）进程，操作系统如何决定它们上处理机的优先级？决定谁先上处理机？

调度（Scheduling）是操作系统中的一个关键功能，负责管理和分配处理器的使用，以确保多个进程或线程能够有效地共享处理器资源。它的主要目标是提高系统的效率和响应速度，同时确保公平性和满足不同进程的需求。

一个可能的调度方式是：先到先服务，就和排队一样，谁先来就调度它运行。但是这样也会有问题，一些紧急重要的进程可能会需要等待前面的进程全部运行完成才能运行。

还有一种是优先级调度，谁优先级高就让谁先上。但是如何决定优先级，这又是一个问题。决定优先级的过程需要用到调度算法，会在后面详细讲到。

调度的三个层次

高级调度

在介绍下面的内容前，需要明白一个定义：作业。

作业就是一个具体的任务。例如用户向操作系统提交了一个作业，代表着用户让操作系统启动一个应用程序。

而高级调度又称为作业调度，指从外存中作业的后备队列挑选一个作业调入内存，并创建进程。每个作业只能调入一次，调出一次。作业调入会建立PCB，调出出才撤销PCB。

低级调度

低级调度又称为（进程调度/处理机调度），指按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，这种调度的频率很高。

中级调度

中级调度又称为内存调度。当内存不够时，可能将某些进程的数据调出外存。被调到外存进行等待的进程为挂起状态，操作系统会把挂起的进程PCB组织成挂起队列。中级调度就是按照某种策列决定将哪个处于挂起状态的进程重新调入内存。

进程的七状态模型

在之前讲到了进程的五状态模型。现在进程添加了两种挂起状态：就绪挂起和阻塞挂起。

挂起状态指原来的进程映像调到了外存，阻塞状态进程还在内存中，只是在等待某种时间的发生。

进程调度的时机

需要进行进程调度的情况：

• 进程主动放弃：如进程正常终止，运行过程发生异常终止，请求阻塞；

• 进程被动放弃：时间片用完，有更紧急的事要处理，有更高优先级的进程进入就绪队列。

不能进行进程调度的情况：

• 处理中断时（原语）。

• 进程在操作系统内核程序临界区中。

• 在原子操作中，也就是原语。

在操作系统中，临界区（Critical Section）是指一段代码，它访问共享资源（如共享变量、文件、设备等），并且在同一时间只能被一个进程或线程执行。

操作系统内核程序临界区：这是指在操作系统内核中执行的临界区。内核临界区通常涉及对内核数据结构的访问，如进程控制块（PCB）、内存管理数据结构等。由于内核操作的特殊性和复杂性，内核中的临界区需要特别小心处理，以确保系统的稳定性和安全性。

进程调度的方式

进程调度的方式有两种：非剥夺调度方式和剥夺调度方式。

非剥夺调度方式

非剥夺调度方式又称为非抢占方式，只允许进程主动放弃，即使有更紧急的任务，也必须等待当前进程处理完毕。

剥夺调度方式

剥夺调度方式又称为抢占方式，当一个进程在处理机上执行时，如果有一个更重要更紧迫的进程需要用到处理机，则暂停该进程的使用，优先分配更重要紧迫的那个进程。

调度器/调度程序

需要发生调度进程调度时会运行调度程序。调度程序由以下事件触发：

• 创建新进程

• 进程退出

• 运行进程阻塞

• I/O中断发生

• 时钟中断

闲逛进程(idle)

闲逛进程是优先级最低的进程，也是最节能的进程。当操作系统发现现在没有进程需要运行时，就会运行闲逛进程。

调度算法的评价指标

在正式介绍调度算法前，需要了解调度算法的评价指标。

CPU利用率

CPU利用率指：CPU忙碌的时间在总时间的占比。

系统吞吐量

系统吞吐量指单位时间内完成作业的数量。

周转时间

周转时间是指一个任务从开始到完成所需的总时间。周转时间通常用于衡量作业或进程的响应效率。

平均周转时间

带权周转时间

带权周转时间通过将周转时间与进程的权重结合起来，提供了一个更全面的性能评估指标。

服务时间指进程实际占用CPU的时间。

平均带权周转时间就是各个任务带权周转时间之和与总任务数的比值。

等待时间

进程/作业处于等待处理机状态之和。

响应时间

用户从提交请求到首次产生相应的时间。

调度算法

先来先算法（FCFS）

按进程到达的顺序进行调度。正如我们平常排队购买商品。可以用于作业调度和进程调度。

• 非抢占式；

• 优点：公平，算法实现简单；

• 缺点：排在长作业后面的短作业需要等待很长的时间，带权周转时间很大。FCFS算法对长作业有利，对短作业不利。

• 不会导致饥饿。

短作业优先（SJF）

追求最少的平均等待时间，最少的平均周转时间和最少的平均带权周转时间。其规则是最短的作业和进程优先的到服务。可用于作业调度和进程调度。进程调度称为短进程优先。

• 是非抢占式的版本，也有抢占式的版本，称为剩余时间优先算法（SRTN）。

• 优点：拥有最短的平均等待时间和平均周转时间。

• 缺点：不公平，对短作业有利，长作业不利。作业进程的运行时间由用户提供，不一定真实。

• 长时间处理短作业会导致长作业饥饿。

高相应比优先（HRRN）

综合考虑作业和进程的等待时间，该算法在每次调度时会考虑各个作业和进程的相应比，选择响应比最高的作业和进程为其服务。

这种调度算法既可以用于作业调度，也可以用于进程调度。

• 非抢占式的算法；

• 综合考虑了等待时间和运行时间，当等待时间相同时，服务时间短的优先。要求服务时间相同时，短作业优先。

• 不会导致饥饿。

练习

以下是各个进程到达就绪队列的时间，尝试用不同算法表示各个进程上处理机运行的过程：

时间片流转（RR）

公平轮流的为每个进程服务。按照进程到达就绪队列的顺序，轮流的让每个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

这种算法只能用于进程调度。

• 抢占式的算法。

• 优点：公平，响应快，适用于分时操作系统。

• 缺点：高频率的进程切换会导致一定的开销。低频率则会退化为先来先算法。并且不能区分任务的紧急程度。

• 不会导致饥饿。

优先级调度算法

每个作业和进程有了自己的优先级，调度时选择优先级最高的作业或进程。

既可以用于作业调度，也可以用于进程调度，还可以用于I/O调度。

• 抢占式和非抢占式都有，非抢占式只在进程结束时判断，而抢占式还需再就绪队列变化时进行判断。

• 优先级分为静态优先级和动态优先级，动态优先级可以在创建进程后动态的进行调整。

• 优先级的分配通常遵循以下规则：

  • 系统进程优先级高于用户进程

  • 前台进程优先级高于后台进程

  • 操作系统更偏好I/O型进程

• 动态优先级会在以下情况进行调整：

  • 如果某进程在就绪队列等待了很长时间，可以提高其优先级；

  • 如果某进程运行了很长时间，可以降低其优先级。

• 优点：用优先级区分了紧急程度和重要程度，适用于实时操作系统，可以灵活的调整作业的偏好程度。

• 缺点：源源不断地高优先级进程到来，可能会导致饥饿。

• 会导致饥饿。

以下进程分别使用抢占式和非抢占式优先级调度算法，绘制其进程运行示意图：

多级反馈队列调度算法

该算法是各种算法的折中，其规则如下：

1. 设置多级就绪队列，各级队列的优先级从高到低，时间片从小到大。

2. 新进程到达时先进入第一级队列，按照FCFS原则排队等待被分配时间片。若时间片用完进程还未结束，则进程进入下一级队列的末尾。如果此时已经在最下级的队列，则重新放回该队列的队尾。

3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片。

该算法只能用于进程调度。

• 这种算法是抢占式的算法，如果更上级的队列中进入了一个新进程，那么新进程会抢占处理及，原来运行的进程放回原队列中。

• 优点：综合了各个算法的优点：对每个进程相对公平、新到达的进程可以快速响应、短进程用很少的时间就可以完成，还可以灵活的调整各个进程的偏好程度。

• 会导致饥饿。

多级队列调度算法

按进程类型分成不同的队列，不同的队列对于所调用的进程算法不同。

• 系统进程：使用优先级调度

• 交互式进程：使用RR

• 批处理进程：使用FCFS

同步与互斥

进程同步

前面我们知道，进程具有异步性：进程运行到哪，运行快慢我们无法进行控制。有些情况下，我们需要一些同步机制，例如说：操作同一块内存，某一个进程需要先往里面写数据，另一个进程才能读数据。线程的操作需要有一定的制约和先后的关系，才能保证其稳定性。

同步亦称直接制约关系，它是指为了完成某种任务而建立的两个和多个进程，这些进程需要再某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约各系就是源于它们之间的相互合作。

进程互斥

有些资源需要互斥的访问。例如，手机的摄像头只能同时由一个程序打开，我们称摄像头需要互斥的访问，摄像头称为临界资源。

对于临界资源，必须互斥的进行，互斥称为间接制约关系。进程互斥指当一个进程访问某临界资源，必须等临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源。

对于临界资源的互斥访问，逻辑上分为四个部分：

void process1()
{
    entry section;     // 进入区
    critical section;  // 临界区
    exit section;      // 退出区
    remainder section; // 剩余区
}

• 进入区：设置访问临界区的标志，检查是否可以进入临界区；

• 临界区：访问临界资源；

• 退出区：重新设置临界区的标志，解锁；

• 剩余区：其他处理；

为了高效实现互斥，需要遵循以下四个原则：

• 空闲让进：临界区空闲，可以允许请求临界区的进程立即进入临界区；

• 忙则等待：已有进程进入临界区，其他试图进入临界区的进程必须等待；

• 有限等待：对请求访问的进程，应保证在有限时间进入临界区（不能饥饿）；

• 让权等待：进程不能进入临界区，不要占着处理机，释放防止忙等待。

实现互斥的软件方法

单标志法

有一个标志来表示允许进入临界区的进程号。其核心思想是：两个进程在访问完临界区后，会把权限交给对方。伪代码如下：

int turn = 0;    // 表示当前允许进入临界区的进程号

// 进程0
void process0()
{
    while (turn != 0);          // (1)开始区
    critical section1(0);       // (2)临界区
    turn = 1;                   // (3)结束区
    remainder section2(0);      // (4)剩余区
}

// 进程1
void process1()
{
    while (turn != 1);          // (5)开始区
    critical section1(1);       // (6)临界区
    turn = 0;                   // (7)结束区
    remainder section2(1);      // (8)剩余区
}

当某一进程处于临界区时，其他进程想要使用临界资源，首先需要校验turn变量是否为自己的编号，如果不是，则就会一直循环，直到资源的使用权是自己(turn是自己)。

• 优点：实现了临界资源的互斥访问。

• 缺点：

  • 访问只能轮换，不能某进程访问完成后，再次继续访问。（1->2->3->4->1->等待），违反了空闲让进原则。

  • 持续while循环导致忙等待，违反了让权等待原则。

双标志先检查法

一个布尔型数组，数组大小为进程数，数组编号对应的值表示该进程是否在访问临界资源。其算法思想为：表达自己使用临界资源的意愿。伪代码如下：

bool flag[2] = {false, false};

// 进程0
void process0()
{
    while (flag[1]);          // (1)开始区: 看看别人想用吗
    flag[0] = true;           // (2)开始区：别人不用，表达我要用的意愿
    critical section1(0);     // (3)临界区
    flag[0] = false;          // (4)结束区：我用完了
    remainder section2(0);    // (5)剩余区
}

// 进程1
void process1()
{
    while (flag[0]);          // (6)开始区: 看看别人想用吗
    flag[1] = true;           // (7)开始区：别人不用，表达我要用的意愿
    critical section1(1);     // (8)临界区
    flag[1] = false;          // (9)结束区：我用完了
    remainder section2(1);    // (10)剩余区
}

这里开始区有两条语句：1. 检查别人要用吗；2. 告诉其他人我要用

这样某进程已经正在访问临界资源时，其他进程通过判断其他进程对应的标志，来决定是否要访问临界资源，实现了互斥访问。

问题出现在了开始区有两段语句，开始区不是原语，不能保证一气呵成执行完毕。假如说是这样的执行顺序：1->准备2->6->7->->8->开始2->3，那么两个进程都可以同时访问临界资源了。

• 优点：处在临界区的进程，其他进程无法访问临界资源；

• 缺点：

  • 可能会导致不同进程同时访问临界资源的情况，违反了忙则等待原则；

  • while循环导致处理机一直在运行，违反了让权等待原则。

双标志后检查法

与双标志先检查法类似，只不过将查询其他进程是否占用临界资源的代码放在了后面：

bool flag[2] = {false, false};

// 进程0
void process0()
{
    flag[0] = true;           // (1)开始区：表达我要用的意愿
    while (flag[1]);          // (2)开始区: 再看看别人想用吗
    critical section1(0);     // (3)临界区
    flag[0] = false;          // (4)结束区：我用完了
    remainder section2(0);    // (5)剩余区
}

// 进程1
void process1()
{
    flag[1] = true;           // (6)开始区：表达我要用的意愿
    while (flag[0]);          // (7)开始区: 再看看别人想用吗
    critical section1(1);     // (8)临界区
    flag[1] = false;          // (9)结束区：我用完了
    remainder section2(1);    // (10)剩余区
}

也可以实现某进程在临界区，其他进程无法使用临界资源的要求。避免了两个进程同时使用临界资源的情况，但这也带来了新的问题：

看下面的代码执行顺序：1->6->2->等待->7->等待，导致出现了两个进程都同时无法访问临界资源的情况，导致了卡死。

• 优点：与双标志先检查法类似，避免了某进程在临界区其他进程对于临界资源的使用。

• 缺点：

  • 可能导致所有进程无法使用资源的情况，违反了空闲让进和有限等待原则；

  • while循环违反了让权等待原则。

Peterson算法

该算法综合了单标志法和双标志后检查法，解决了两个算法的痛点。其算法核心是既表达意愿，又表达谦让。伪代码如下：

bool flag[2] = {false, false}; // 表达意愿
int turn = 0;                  // 表达谦让

// 进程0
void process0()
{
    flag[0] = true;                  // (1)开始区：表达我要用的意愿
    turn = 1;                        // (2)开始区：表达谦让，优先对方使用
    while (flag[1] && turn == 1);    // (3)开始区: 别人在用且我们表达了谦让，那就等别人用
    critical section1(0);            // (4)临界区
    flag[0] = false;                 // (5)结束区：我用完了
    remainder section2(0);  
}

// 进程1
void process1()
{
    flag[1] = true;                  // (1)开始区：表达我要用的意愿
    turn = 0;                        // (2)开始区：表达谦让，优先对方使用
    while (flag[0] && turn == 0);    // (3)开始区: 别人在用且我们表达了谦让，那就等别人用
    critical section1(0);            // (4)临界区
    flag[1] = false;                 // (5)结束区：我用完了
    remainder section2(0);  
}

Peterson算法保证了开始区的切换导致临界资源被重复使用的情况。这与现实生活类似：最后一个表达谦让的总是无法使用资源。不妨自己随便按照一些步骤做一下实验。

• 优点：保证了同一时刻临界资源只能被一个进程占用；

• 缺点：while循环导致的忙等待违反了让权等待。

实现互斥的硬件方法

软件方法中，我们需要想尽各种办法来避免中断带来的硬件影响。硬件方法处理起来就简单许多了。我们可以通过原语来避免中断的影响。方法有以下几种：

中断屏蔽方法

使用开中断和关中断指令来访问临界区资源：开中断->临界区->关中断。

这种方法简单粗暴，但是只适用于内核程序。程序员所写的程序无法直接调用内核指令，需要其他方法来解决。

TestAndSet指令 (TSL指令)

TesrAndSet指令是硬件实现的，不能被中断。其基本代码逻辑如下：

bool TestAndSet(bool *lock)
{
    bool old;
    old = *lock;
    *lock = true; // 上锁
    return old;
}

void process0()
{
    while (TestAndSet(&lock)); // 检查并上锁
    临界区...
    lock = false;   // 解锁
    剩余区...
}

TestAndSet相当于做了一个上锁的操作，但返回的是上锁前的状态，这样就能够判断出之前临界资源有没有被上锁。

这个操作也不符合让权等待的原则，会导致忙等。

Swap指令 （XCHG指令）

swap可以交换两个变量，本身属于原子操作，不能被中断。实现加锁的伪代码如下：

void process0()
{
    bool old = true;
    while (old) swap(&lock, &old); // 检查并上锁
    临界区...
    lock = false;   // 解锁
    剩余区...
}

这个思想和上面的TSL指令大同小异。只是利用了swap的原子性。缺点同样不符合让权等待，导致忙等。

互斥锁

解决临界区最简单的工具是互斥锁。进入临界区是应先获得锁，退出临界区应该释放锁。

有关C++使用互斥锁（mutex），可以参见以下文章：

其特性如下：

• 需要忙等，违反让权等待；

• 等待期间不需要切换上下文，若上锁时间短，则等待的代价低。

• 常用于多处理器系统；

• 不适用于单处理机系统，等待过程中不可能解锁。

信号量

上面提到的互斥算法都有一个通病：无法实现让权等待。在1965年荷兰学者Dijkstra提出了信号量机制，这是一种卓有成效的实现进程互斥和同步的方法。

用户进程可以使用操作系统提供的一对原语来对信号量进行操作，实现了进程同步和互斥。信号量实际上就是一个变量，用来表示系统中某种资源的数量。操作系统提供的一对原语是wait(S)原语和signal(S)原语，通常简称为P,V操作，将上面的函数可以简写为P(S)和V(S)。

整型信号量

用一个整数型的变量作为信号量，表示系统中某种资源的数量。一个简单的P,V函数如下：

int S = 1;  // 信号量，有一个资源

void wait(int &S)
{
    while (S <= 0); // 资源数不够，循环等待
    --S;            // 资源数足够，我用一个
}

void signal(int &S)
{
    ++S;            // 用完了，还回来
}

在访问临界资源时，先调用wait(S)，使用完成后再调用signal(S)。实现了简单的互斥操作。

但是仍然存在忙等的问题，违反了让权等待。

记录型信号量

记录型信号量是一个数据结构，里面既保存了剩余资源数，还维护了一个等待队列。伪代码如下：

struct semaphore
{
    int value;  // 剩余资源数
    struct process *L;  // 等待队列
};

void wait(semaphore &S)
{
    --S.value;
    if (S.value < 0)
    {
        block(S.L); // 阻塞原语，将进程阻塞
    }
}

void signal(semaphore &S)
{
    ++S.value;
    if (S.value <= 0)
    {
        wakeup(S.L);    //唤醒原语，将进程转换到就绪态
    }
}

当一个进程访问临界资源，先使用wait操作，发现资源数不够，那么就会使用阻塞原语将这个进程阻塞，避免了忙等。待上一个使用临界资源的线程使用完毕后，会调用一次signal，signal发现等待队列中有东西，就会执行唤醒原语，让进程继续运行，进程会继续执行wait，发现资源可用，就会使用。

至此我们成功解决了忙等导致的违反让权等待问题。

信号量实现同步

信号量实现互斥我们之前用简单的例子讲述了，此外信号量还能够实现进程同步。分析下面一段代码，可用资源数为0：

void process0()
{
    代码1;
    代码2;
    V(S);
    代码3;
}

void process1()
{
    P(S);
    代码4;
    代码5;
    代码6;
}

问题：代码4有可能在代码2之前执行吗？

答案是不会。如果先运行了P(S)，系统发现没有资源，就会阻塞这个线程。这个线程什么时候才能唤醒呢？直到其他进程运行了V(S)操作。由于代码2运行在V(S)之前，代码4运行在P(S)之后，P(S)只能运行在V(S)之后，导致代码4不可能在代码2之前执行。

这样，我们就实现了进程同步。保证了某个进程的代码在其他进程代码之前（之后运行）。简单来说，V(S)先运行，P(S)后运行。

下面给出这样一个前驱图，尝试通过PV操作实现图中的同步机制。

给每一条路径选取一个信号量，初值为0。

然后每条路径之前使用V操作，之后使用P操作，这样我们就能写出以下的代码：

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;
}

同步互斥常见问题

生产者-消费者问题

生产者-消费者问题是一个经典的同步互斥问题。情景如下：现在有一个生产者和一个消费者，以及一块固定大小的缓冲区。生产者可以生成数据放到缓冲区中，消费者可以从缓冲区中取走数据。这个问题有以下的同步互斥情况：

• 缓冲区空，消费者无法取数据；

• 缓冲区满，生产者无法放数据；

• 在同一时刻，只能由一个生产者或消费者访问缓冲区。

解决这个问题，需要用到两个信号量：

• empty: 表示缓冲区空闲的空间数量。如果它大于0，则生产者可以放入数据。初始化为总空间数。

• full: 表示缓冲区已有的数据数量。如果它大于0，则消费者可以取出数据。

还需要一个互斥锁：

• mutex: 初始化为1，生产者和消费者访问缓冲区之前需要上锁。

伪代码如下：

// 信号量初始化
semaphore empty = BUFFER_SIZE;   // 初始化为缓冲区大小
semaphore full = 0;              // 初始化为 0
semaphore mtx = 1;               // 互斥锁

producer() {
    while(1) {
        item = produce_item();    // 生成一个产品
        P(empty);                 // 等待有空位
        P(mtx);                   // 进入临界区
        buffer.push(item);        // 将产品放入缓冲区
        V(mtx);                   // 离开临界区
        V(full);                  // 通知消费者有数据
    }
}

consumer() {
    while(1) {
        P(full);                  // 等待有数据
        P(mtx);                   // 进入临界区
        item = buffer.pop();      // 从缓冲区取出一个产品
        V(mtx);                   // 离开临界区
        V(empty);                 // 通知生产者有空位
        use_item(item);           // 使用产品
    }
}

假设生产者先对互斥锁进行了P操作，然后在对empty进行了P操作会发生什么呢？假设缓冲区已满，生产者先上互斥锁，然后发现无法生产。消费者想要消费时，发现被锁了，无法消费，导致了循环等待的情况，发生了死锁。因此互斥锁的位置需要特别考虑。

多生产者-多消费者问题

这个问题是对生产者-消费者问题的扩充。现在生产者有很多个，生产不同类别的产品，消费者也有很多个，消费不同类型的产品。而缓冲区只有固定大小。这次假设缓冲区为1，生产者有2个，消费者有2个；下面几个例子可以解释其逻辑：

1. P1生产了产品1，放到了缓冲区，C1取走产品1；

2. P1生产的产品1，C2无法取走，这不是它要消费的产品；

3. P1生产了产品1，占用了空间，P2无法生产产品到缓冲区；

4. C1取走了产品1，P2生产的产品2占用了空间，随后被C2取走了。

仔细思考这个问题，发现其有以下的同步关系：

• C1只有当空间中有产品1才能取走1；

• C2只有当空间中有产品2才能取走2；

• 只有空间有空闲时，生产者才能生产产品；

还有以下的互斥关系：

• 缓冲区同一时刻只能被一个实体访问。

定义以下的信号量：

• mutex: 初始化为1，用作互斥锁；

• buffer: 初始化为1（空间大小），缓冲区剩余空间；

• production1: 初始化为0，表示目前拥有的产品1数量；

• production2: 初始化为0，表示目前拥有的产品2数量。

伪代码如下：

// 信号量初始化
semaphore mutex = 1;          // 互斥锁
semaphore buffer = 1;         // 缓冲区剩余空间
semaphore production1 = 0;    // 产品1的数量
semaphore production2 = 0;    // 产品2的数量

// 缓冲区
int buffer_content = 0;       // 0表示空，1表示产品1，2表示产品2

// 生产者 P1
producer1() {
    while (1) {
        item = produce_item1(); // 生成产品1
        P(buffer);              // 等待有空位
        P(mutex);               // 进入临界区

        buffer_content = 1;     // 将产品1放入缓冲区
        V(mutex);               // 离开临界区
        V(production1);         // 通知消费者有产品1
    }
}

// 生产者 P2
producer2() {
    while (1) {
        item = produce_item2(); // 生成产品2
        P(buffer);              // 等待有空位
        P(mutex);               // 进入临界区

        buffer_content = 2;     // 将产品2放入缓冲区
        V(mutex);               // 离开临界区
        V(production2);         // 通知消费者有产品2
    }
}

// 消费者 C1
consumer1() {
    while (1) {
        P(production1);         // 等待有产品1
        P(mutex);               // 进入临界区

        // 取走产品1
        buffer_content = 0;     // 清空缓冲区
        V(mutex);               // 离开临界区
        V(buffer);              // 通知生产者有空位
        use_item1();            // 使用产品1
    }
}

// 消费者 C2
consumer2() {
    while (1) {
        P(production2);         // 等待有产品2
        P(mutex);               // 进入临界区

        // 取走产品2
        buffer_content = 0;     // 清空缓冲区
        V(mutex);               // 离开临界区
        V(buffer);              // 通知生产者有空位
        use_item2();            // 使用产品2
    }
}

吸烟者问题

在这个问题中，有三个吸烟者和一个供应商。每个吸烟者需要三种材料之一来制作香烟：烟草、纸和火柴。供应商负责提供这些材料，但每次只提供两种材料。

吸烟者1需要烟草和纸。吸烟者2需要纸和火柴。吸烟者3需要火柴和烟草。供应商随机选择两种材料并将其放在桌子上。

这个问题有以下的同步关系：

• 只有当供应商提供了两种材料时，某个吸烟者才能开始制作香烟。

• 同一时刻只能有一个吸烟者访问桌子上的材料。

可以定义以下的信号信号量：

• offer1、offer2、offer3：分别表示桌子上提供的材料组合的信号量。

• finish：表示吸烟者已经完成吸烟的信号量。

• int i = 0;：用于跟踪当前提供的材料组合。

伪代码如下：

provider() {
    while (1) {
        if (i == 0) {
            // 将组合1（烟草和纸）放到桌上
            V(offer1);
        } else if (i == 1) {
            // 将组合2（纸和火柴）放到桌上
            V(offer2);
        } else if (i == 2) {
            // 将组合3（火柴和烟草）放到桌上
            V(offer3);
        }
        i = (i + 1) % 3; // 循环更新组合
        P(finish);       // 等待吸烟者完成
    }
}

// 吸烟者1
smoker1() {
    while (1) {
        P(offer1);  // 等待烟草和纸
        // 从桌上拿走组合
        // 吸烟
        V(finish);  // 通知供应商完成
    }
}

// 吸烟者2
smoker2() {
    while (1) {
        P(offer2);  // 等待纸和火柴
        // 从桌上拿走组合
        // 吸烟
        V(finish);  // 通知供应商完成
    }
}

// 吸烟者3
smoker3() {
    while (1) {
        P(offer3);  // 等待火柴和烟草
        // 从桌上拿走组合
        // 吸烟
        V(finish);  // 通知供应商完成
    }
}

读者写者问题

读者-写者问题是一个经典的同步问题，涉及多个进程对共享数据的读写操作。在读者-写者问题中，有两种类型的进程：

1. 读者（Reader）：可以并行读取共享数据，但不能在写者写入时读取。

2. 写者（Writer）：在写入共享数据时，不能有其他读者或写者访问该数据。

有以下的同步要求：

• 多个读者可以同时读取：当没有写者在写入时，多个读者可以同时访问数据。

• 独占写入：当有写者在写入时，所有的读者和其他写者必须等待，直到写者完成写入。

可以使用以下的信号量解决这个问题：

• writeLock：初始化为1，保证写入互斥；

• int readCount = 0：现在有几个读者在读。

• mutex：由于判断和写入readCount不在同一时间处理，需要对这个变量加锁。

伪代码如下：

semaphore mutex = 1;        // 确保互斥访问计数器
semaphore writeLock = 1;    // 确保写入互斥
int readCount = 0;          // 当前读者数量

// 读者
reader() {
    while (true) {
        P(mutex);            // 进入临界区
        readCount++;        // 增加读者计数
        if (readCount == 1) {
            P(writeLock);    // 第一个读者请求写锁
        }
        V(mutex);            // 离开临界区

        // 读取数据
        readData();

        P(mutex);            // 进入临界区
        readCount--;        // 减少读者计数
        if (readCount == 0) {
            V(writeLock);    // 最后一个读者释放写锁
        }
        V(mutex);            // 离开临界区
    }
}

// 写者
writer() {
    while (true) {
        P(writeLock);        // 请求写锁

        // 写入数据
        writeData();

        V(writeLock);        // 释放写锁
    }
}

上面这个代码实现了正常状况下的读者写者问题。下面考虑这样一个情况：读者1开始读，没有读完，写者准备写，发现正在读，便等读者1读完，此时又来了一个读者2，开始读。即使读者1读完了，写者先来的，资源还是优先分配给了读者2，这并不公平。因此我们可以设计一个写优先的读者写者问题。

解决方法就是，再加一个信号量，如果写者准备写，就上锁。接下来的读者即使来了，发现准备写，那也得等着。

semaphore mutex = 1;        // 确保互斥访问计数器
semaphore writeLock = 1;    // 确保写入互斥
semaphore writeFirst = 1;   // 写优先
int readCount = 0;          // 当前读者数量

// 读者
reader() {
    while (true) {
        P(writeFirst);
        P(mutex);            // 进入临界区
        readCount++;        // 增加读者计数
        if (readCount == 1) {
            P(writeLock);    // 第一个读者请求写锁
        }
        V(mutex);            // 离开临界区
        V(writeFirst);

        // 读取数据
        readData();

        P(mutex);            // 进入临界区
        readCount--;        // 减少读者计数
        if (readCount == 0) {
            V(writeLock);    // 最后一个读者释放写锁
        }
        V(mutex);            // 离开临界区
    }
}

// 写者
writer() {
    while (true) {
        P(writeFirst);
        P(writeLock);        // 请求写锁

        // 写入数据
        writeData();

        V(writeLock);        // 释放写锁
        V(writeFirst);
    }
}

哲学家进餐问题

有五位哲学家坐在圆桌旁，每位哲学家需要同时使用两根筷子（分别是左边和右边的筷子）才能吃饭。桌子上只有五根筷子，因此每位哲学家在吃饭时必须同时拿到左右两根筷子。

哲学家有几种状态：思考、饥饿、进食；哲学家饥饿就会拿起左手边和右手边的筷子吃饭。如果某一边筷子缺失，哲学家就必须等待。

其中的互斥同步问题很容易发现：

• 筷子是互斥使用的，一根筷子只能服务于同一个哲学家。

因此我们可以定义一个信号量数组，下标为筷子的编号。当哲学家使用某根筷子时，就给对应信号量加锁。

似乎到这里问题就解决了，但是思考这样一个场景：5个哲学家同时饿了，同时拿起了左手边的筷子。这时候，他们右手边没有筷子，那就必须等待了。这样就会导致循环等待，发生了死锁。

如何避免这样的问题？解决方案有很多：

1. 要求同时最多有四个哲学家进餐，如果有5个，第5个必须等待。

2. 奇数编号的哲学家先拿右手边的筷子，偶数编号哲学家先拿左手边筷子。

3. 拿筷子的这个动作是互斥的，同时只允许一个哲学家拿筷子。

以第三个为例，伪代码如下：

semaphore mutex = 1;        // 互斥锁，用于保护共享资源
semaphore chopsticks[5] = {1, 1, 1, 1, 1}; // 每根筷子的信号量

philosopher(i) {
    while (true) {
        think();           // 哲学家思考

        P(mutex);          // 进入临界区
        P(chopsticks[i]);  // 拿起左边的筷子
        P(chopsticks[(i + 1) % 5]); // 拿起右边的筷子
        V(mutex);          // 离开临界区

        eat();             // 哲学家吃饭

        V(chopsticks[i]);  // 放下左边的筷子
        V(chopsticks[(i + 1) % 5]); // 放下右边的筷子
    }
}

管程

管程（Monitor）是一种用于管理并发程序中共享资源的同步机制。它提供了一种高层次的抽象，帮助程序员更容易地控制对共享资源的访问，从而避免竞争条件和死锁等问题。

管程的基本概念：

1. 封装性：管程将共享资源和对其的操作封装在一起，外部程序只能通过管程提供的接口访问资源。这种封装性有助于隐藏实现细节，简化并发控制。

2. 互斥性：管程保证在同一时刻只有一个线程可以执行管程内部的代码。其他线程在尝试进入管程时会被阻塞，直到第一个线程退出。

3. 条件变量：管程通常配备条件变量，允许线程在某些条件不满足时挂起，并在条件满足时被唤醒。这使得线程能够有效地等待特定的状态，而不是持续轮询。

优点：

1. 简化并发控制：通过封装共享资源和同步机制，管程使得并发编程更容易理解和实现。

2. 减少错误：由于管程提供了互斥和条件变量的内置支持，程序员更不容易犯错，如忘记释放锁或错误地使用条件变量。

3. 提高可读性：管程的结构化设计使得代码更具可读性和可维护性。

死锁

什么是死锁

在前面的哲学家进餐问题就是一个简单的死锁示例。每个进程都占有着一种资源，而却等待着另一个被其他进程占有的资源，最终导致了无限等待。死锁的发生导致了资源的极大浪费，更有甚者可能导致整个程序的崩溃，我们需要一些方法避免死锁。

死锁和其他概念容易混淆，例如饥饿和死循环等：

• 饥饿：一个进程长期得不到想要的资源。可以说死锁会导致饥饿，不能说发生饥饿是因为出现了死锁。

• 死循环：由于程序设计原因或是故意设计，程序重复不断的执行循环，并没有出现资源占用之类的问题。

死锁的必要条件

互斥条件

只有对互斥使用的资源争抢才会导致死锁，可以共享的设备不会导致死锁。

不可剥夺条件

进程获得的资源除非自愿归还，否则不能被强行夺走。

请求和保持条件

进程已经保持了一个资源，还想要其他资源，而刚好这个资源被其他进程占有着。

循环等待条件

占有和保持的资源能够形成一条链，链中每一个进程获得的资源被下一个进程请求，形成了环。

以上四个条件为必要条件，若任何一个条件不成立，死锁都不会发生。

静态策略预防死锁

通过破坏死锁的任意一个必要条件，都可以预防死锁的发生，四种必要条件对应了四种方法：

1. 破坏互斥条件

可以通过一些方法把资源变成共享设备。例如使用SPOOLing技术。例如：进程使用打印机，打印机收到作业后排队，并通知进程占用结束。在占用资源时，其他进程也可以向其提交资源。打印机只需要一个一个将作业完成即可。

然而，大多数情况下根本无法破坏互斥条件，这更多是为了安全考虑，因此这种方法的适用性不强。

2. 破坏不可剥夺条件

有两种解决方案：如果某个进程请求新的资源得不到满足，必须释放自己保持的资源，以后需要时再申请；如果某个进程请求的资源被其他进程占有，操作系统可以协助将资源剥夺，这一般需要考虑进程的优先级。

这种方法的缺点也很明显：首先实现起来十分复杂；此外释放已获得资源可能导致前一段工作的失效。反复的申请和释放资源也会导致增加系统开销，降低系统吞吐量。有时会引发进程饥饿。

3. 破坏请求和保持条件

使用静态分配方法。进程在运行前请求它所需的所有资源，在运行期间一直占有着这些资源，直到程序运行结束。

这种方法资源利用率极低，很有可能会导致某些进程饥饿。

4. 破坏循环等待条件

可以采用顺序资源分配法。给系统中每个资源编号，规定每个进程必须按编号递增的顺序请求资源。只有占有小编号资源时才能申请大编号资源。大编号资源的进程不会返回来申请小编号资源，避免了循环等待。

这种方法具有操作复杂的缺点，增减编号需要按照一定的规律，而且还要保证编号递增顺序一致。

之前解决哲学家进餐问题，用到了哪些方法解决死锁呢？

动态策略避免死锁——银行家算法

银行家算法是由荷兰学者Edsger Dijkstra提出，用于避免死锁的方法，用于保证系统在分配资源时处于安全状态。

假设我们有一个系统，包含以下资源和进程：

• 三种相同类型的资源R1, R2, R3；

• 三个进程：P1, P2, P3；

可用资源数量分别为(Available)：（3，3，3）

每个线程的最大需求为(Maximum)：

• P1: 3, 2, 1

• P2: 1, 2, 2

• P3: 1, 0, 1

目前已经分配的资源数量为(Allocation)：

• P1: 1, 0, 1

• P2: 1, 2, 0

• P3, 0, 0, 1

因此，我们可以计算出需求(Need)：

• P1: 2, 2, 0 (3-1, 2-0, 1-1)

• P2: 0, 0, 2 (1-1, 2-2, 2-0)

• P3: 1, 0, 0 (1-0, 0-0, 1-0)

现在假设P1请求资源(1, 1, 0)，问我们能不能接受它的这次请求，并且不会导致死锁？

• 假设我们同意了这次请求，那么现在资源可用数为（0, 0, 1）P1的需求更新为 (1, 1, 0)。

• 那么这个资源能否满足其他的线程呢？我们发现，现在的资源可用数满足不了任何一个进程的需求，这表明有可能会发生死锁。所以这次请求应该被拒绝。

现在假设P2请求资源(0, 0, 1)，我们应该拒绝吗？

• 同样的，计算出现在的资源可用数：(1, 1, 0)，P2的需求更新为 (0, 0, 1)，已分配更新为(1, 2, 1)。

• 发现当前资源数可以满足P3的全部需求，那么我们假设优先给P3，之后P3运行完成释放资源，此时资源数更新为(1, 1, 1)。

• 此时这个资源数又能满足P2的需求，再将资源优先给P2，待其释放资源，资源数更新为(2, 3, 2)；

• 这时又能完成P1的需求，重复上述步骤，所有的进程资源都能被满足，资源数更新为(3, 3, 3)；

• 这表明我们找到了一条路径能够避免死锁的发生，因此这个请求应该同意。

以上就是银行家算法的核心思想。我们需要用专业术语来解释并且一般化到各种情况。

安全序列

在上面的第二个例子中，我们找到了P3->P2->P1这一条路径，发现了这条路径不会导致死锁。这条路径就称作为安全序列。安全序列就是系统中按照这种序列分配资源，每个进程都能顺利的完成，银行家算法的核心就是找到安全序列。

如果我们能够找到一条安全序列，就称系统处于安全状态。反之则是不安全状态。在不安全状态有可能返回到安全状态，但是我们需要悲观的看待问题，需要考虑到最坏的情况。所以我们需要一直让系统保持安全状态。

一般流程

假设有n个进程，m个资源。则最大需求数可以用n*m的矩阵表示，记作Max。已分配矩阵同理，记作Allocation。需求矩阵为Max - Allocation，记作Need。空闲资源数则可以是一个m个数字组成的向量，记作Available。某次需求也是长度为m的一位向量，由Pi进程发出，记作Request_i。

1. 如果\text{Request}_i[j] \le \text{Need}[i][j]\quad(0\le j\le m) ，继续到2，否则退出，表明请求资源数已经超过了它宣布的最大值。

2. 如果\text{Request}_i[j] \le \text{Available} [j]\quad(0\le j\le m) ，继续到3，否则退出，表明请求资源数已经超过了空闲资源数。

3. 系统试探着把资源分配给进程P_i , 并修改相应的数据：

4. 操作系统执行安全性算法，检查分配后是否处于安全状态，安全才分配。不安全则阻塞进程。

死锁的检测与解除

避免死锁的方法有很多种，还有一种是我们可以允许死锁的发生，但是需要不断地检测死锁，发现死锁则用一种方法解除死锁。如何检测死锁呢？

死锁的检测

检测死锁我们可以用资源分配图法：

定义一个二元组G=<V,E> 。其中：

• V 为结点集，有两种节点：P=\{P_1,P_2,...,P_n \} 和R = \{R_1,R_2,...,R_m\} 。

• E 为边集，元素为有序二元组<P_i,R_j> 或<R_j,P_i > 。

可以用一个图来表示：

其中图中的圆节点表示进程，方节点表示某种资源，其中黑点表示资源数目。进程节点指向方节点，表示进程正在请求某个资源（申请边<P_i,R_j> ）；黑点指向某进程节点（分配边<R_j,P_i > ），表示某个资源正在服务于某进程。

死锁定理：

• 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。

• 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。

判断有没有出现死锁，我们可以先对资源分配图进行化简，化简规则如下：

1. 找一个非孤立、只有分配边的进程结点，去掉分配边，将其变为孤立结点；

2. 再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边；

3. 重复以上步骤，若所有进程都可成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。

死锁状态的充分条件是：资源分配图是不可完全简化的。

上面的示意图就找不到一个非孤立、只有分配边的进程结点，不可简化，发生了死锁。

上面的有环但并不是死锁，因为能够化简。

死锁的解除

检测到了死锁，就需要对死锁进行解除，重要的是以最小的代价解除死锁，恢复系统运行。

1. 资源剥夺法：挂起死锁进程，并抢占它的资源。注意放置被挂起的进程发生饥饿。

2. 撤销进程法：撤销部分或全部死锁进程，剥夺资源。这种方法简单但是代价大。

3. 进程回退法：让一个或多个进程回退到避免死锁的地步，需要系统记录进程的历史信息而设置还原点。