操作系统 并发控制

并发控制概论

一组进程在执行时间上重叠，一个进程执行的第一条指令可能是在另一个进程执行的最后一条指令完成之前开始的，这就是进程的并发性。从宏观来看，一个时间段中有多个进程同时处于活动状态，而从微观来看，任一时刻仅有一个进程在处理器上运行。综上，进程并发的实质是一个CPU在多个进程之间的多路复用。

并发程序间的关系

• 无关
  • 不同的并发进程在不同的变量集合上操作，一个进程的执行与其他并发进程的执行无关
  • 进程读取的变量集合\(R(P)=\{a_1,a_2,...a_n\}\)，进程改变的变量集合\(W(P)=\{b_1,b_2,...,b_n\}\)，如果两个进程\(P_1\)、\(P_2\)的变量集合满足\((R(P_1)\cap W(P_2))\cup (R(P_2)\cap W(P_1))\cup (W(P_1)\cap W(P_2))=\emptyset\)，那么这两个进程就是无关的。这个条件叫做Bernstein条件。
• 交互
  • 一组并发进程（线程）共享某些变量，一个进程的执行可能影响其他并发进程的执行
  • 竞争关系（间接制约）
    • 解决手段：进程互斥访问同一共享资源，即任何时刻最多允许一个进程访问某一共享资源，其他进程需要等到该进程释放资源后才能访问该资源
  • 协作关系（直接制约）
    • 解决手段：进程同步，即通过某个条件（或变量）协调多个进程的活动，进程在需要依赖另一个进程的工作时进入等待状态，直到另一个进程发出信号时再被唤醒执行
  • 进程互斥是一种特殊的进程同步（互斥锁）

并发程序的优缺点

优点：

• 对于单处理器系统，可以让处理器与I/O设备同时工作，提高效率
• 对于多（核）处理器系统，可以让各个进程在不同的处理器（核心）上并行执行，加快计算速度
• 简化了程序设计任务（更接近于现实世界：某事和某事同时发生）

缺点：

• 对于有一组有交互关系的并发进程，如果不加管理，可能会出现一些与时间有关的错误出现，例如永远等待、结果不一致等。

临界区管理

• 临界区：并发进程中与共享变量有关的程序段称之为临界区
• 临界资源：共享变量代表的资源
• 临界区管理：保证一个进程在某一资源的临界区执行时，不让另一个进程进入相关的临界区，从而实现对共享变量的互斥访问。
• 临界区调度的原则
  • 一次至多有一个进程能够进入某一临界区
  • 不能让一个进程无限地留在临界区（其他进程无法推进）
  • 无空等待，有空让进，择一而入
• 临界区的嵌套可能造成进程无法离开临界区（发生死锁）
  • 如：region X do {...; region Y do {...}; ...}（进入X的临界区，然后在X的临界区进入Y的临界区）。如果有另一进程执行region Y do {...; region X do {...}; ...}则可能出现两个进程死锁的现象。

软件方式

Dekker算法

基本思想：进程进入临界区前，首先把自己的标识置为true，然后检查对方标识和临界区指示器turn，如果对方标识为true且指示器turn指向对方，则等待；否则进入临界区，在离开临界区时，修改自己的标识为false并把指示器指向对方。

Peterson算法

基本思想：进程进入临界区前，首先把自己的标识置为true，然后令指示器指向对方，之后检查对方标识和指示器，如果对方标识为true且指示器指向对方，则等待；否则进入临界区，在离开临界区时，修改自己的标识为false。

硬件方式

硬件提供相关指令以实现自旋锁，常用于内核临界区管理（例如：TSL测试并置位指令，该指令将lock变量原值复制到寄存器，然后将lock变量置为1；又例如：XCHG对换指令，将两个变量的值交换，借助该指令可以实现自旋锁）

自旋锁很少被用于用户层，因为自旋锁依赖于忙等待（等待时需要不断检查自旋锁状态）所以效率低下（持续占用CPU资源），而持续占用CPU资源检查自旋锁又可能会造成操作系统误判进程状态进而分配更多CPU资源

同步问题

• 一个典型的进程同步问题：有若干个生产者和若干个消费者，它们共享一个缓冲区，生产者生产数据放入缓冲区，消费者从缓冲区取走数据。因此，需要解决生产者与消费者、生产者与生产者、消费者与消费者之间的同步问题，例如：当前缓冲区状态（空/满），从何处取数据，能不能取数据（不能有多个消费者同时取走同一份数据），能不能放数据（不能有多个生产者同时向同一位置存放数据）等。

• 解决方法：进程之间通过交换信号或消息来达到进程协调运行的目的

• 常见的同步机制

  • 信号量与PV操作
  • 管程
  • 消息传递

信号量与PV操作

基于之前对自旋锁的讨论可以看出，自旋锁需要占用较多的系统资源来进行忙等待，所以通常只被用于操作系统内核。对于用户层程序，通常使用由操作系统提供的同步机制来进行进程间的同步。

原语：P（荷兰语：Proberen，测试），V（荷兰语：Verhogen，增量），除了对信号量赋初值外，信号量仅能通过以上两个原语进行操作。P操作首先会测试信号量是否大于0，如果大于0，则会将信号量减一，否则将等待信号量大于0后再减一；V操作会将信号量加一。

信号量分类：

• 按用途

  • 公有信号量（进程互斥）
    • 多个进程均可以对该信号量进行PV操作，从而实现互斥（例如：初始化信号量为1，进入临界区前先对该信号量做P操作，离开临界区后再对该信号量做V操作）
  • 私有信号量（进程同步）
    • 某个进程只对该信号量进行P操作和V操作中的一种，从而实现进程同步（例如：如果进程A在某处需要依赖于进程B的工作，则初始化信号量为0，在进程A需要进程B工作的地方先进行P操作，B进程在完成任务后进行V操作，这样就实现了A和B的同步）

• 按取值

  • 二元信号量（只有0/1，用于进程互斥）

  • 一般信号量（初始值可以为任意非负整数，用于进程互斥或进程同步）

    一般信号量可以由二元信号量构造产生

• 按结构

  • 整形信号量
    • 信号量s为一非负整数，P(s)在s大于0时将s减一，否则持续等待，直至s大于0，V(s)将信号量加一
  • 记录型信号量
    • 信号量s包含两个分量：value和queue，queue用于记录等待的进程，当value小于等于0时执行P操作，进程将会被加入queue中；当value小于0时执行V操作，系统将会唤醒queue中某个等待的进程

当信号量的值为正时，该值可以看作当前可用的资源数量；当信号量的值为负时，该值的绝对值可以看作当前正在等待资源的进程数量。P操作可以看作请求一个资源，V操作可以看作释放一个资源。

管程

使用信号量和PV操作实现同步时，对共享资源的管理分散在各进程中，这可能容易造成程序设计错误，因此出现了管程这一机制。

管程的基本思想时把分散在各进程中的临界区集中进行管理（类似于面向对象编程中的类），并把系统中的共享资源用数据结构抽象地表示出来。管程是程序设计语言地一种结构成分，和信号量具有同等的表达能力，管程是一种同步逻辑的封装机制，通过封装好的管程，编写程序不再需要考虑共享资源的同步问题。（例如，如果有一个封装好的容器类对象，在编写多线程程序时，各个线程无需考虑对该容器类对象的同步或互斥访问问题，只需要调用容器类封装好的存取函数）

管程体内的各个函数均是互斥进行的，即在任意时刻，只有一个进程位于管程体内，所以编写管程时无需考虑互斥访问的问题。

• 条件变量：用于阻塞进程的一种信号量
• wait原语：当一个管程过程无法继续时，对某个条件变量执行wait原语，这将会使调用该管程过程的进程阻塞
• signal原语：用于唤醒阻塞在某一条件变量上的某个进程，此时存在执行signal的进程与被唤醒进程同时位于管程体内的问题，这与管程的互斥性相悖，有两种解决方法：
  • 执行signal的进程等待，直到被唤醒的进程退出管程（完成执行或需要等待其他条件变量）（Hoare实现）
  • 被唤醒的进程等待，直到执行signal的进程退出管程（完成执行或需要等待其他条件变量）（Mesa实现）
  • 对signal执行的位置做出限制，只允许在管程体函数末尾执行signal操作（Hanson实现）

管程实现

• Hoare实现

  • 采用执行signal的进程等待，直到被唤醒的进程退出管程的方法解决互斥性问题，使用PV操作实现进程间的互斥

  • 实现方法：引入两个信号量mutex和next，其中mutex用于实现进程互斥调用管程过程，初始化为1；next用于让执行signal的进程挂起自己，初始化为0。引入计数器next_count，用于记录在信号量next上等待的进程数。对于每个条件变量，设置一个初始化为0的信号量x_sem和一个记录等待该条件变量进程数量的计数器x_count。

    • 具体实现代码如下所示：

      

      Hoare方法实现管程

    • 对于外部过程，需要通过如下方式保证管程的互斥性：

      

      Hoare方法实现管程

    • 文字描述：在使用管程体的任何一个函数之前，首先要通过P操作申请管程使用权（以实现互斥访问），在申请到权限后进入管程体执行各种操作，操作完成后优先将控制权转移给因为signal操作而主动挂起的进程，如果没有这样的进程则释放控制权给其他进程（即释放互斥锁）。

      • 如果需要等待某个条件变量则使用wait操作，wait操作首先将x_count加一（以记录该条件变量上等待的进程数），之后就可以释放控制权给其他进程了，在这里优先释放控制权给之前因为signal操作而主动挂起的进程，如果没有这样的进程则释放控制权给其他进程（即释放互斥锁），在释放控制权之后，执行P操作以等待被唤醒，唤醒后将x_count减一（同样为了记录该条件变量上等待的进程数）。
      • 如果需要向某个条件变量进行signal操作，则首先检查有没有等待该条件变量的进程，如果没有，signal操作无效；否则先将next_count加一（以记录自己的挂起），然后释放控制权给等待条件变量的某个进程，最后通过P操作等待自己被唤醒，唤醒后将next_count减一。

进程通信

常见的通信机制：

• 信号通信
• 共享文件
• 共享存储区
• 消息传递

信号通信

信号通信又称软中断，是一种简单的通信机制，通过发送一个特定的信号来通知进程某个异常事件发生，信号可以是内核发送给进程，也可以是一个进程发送给另一个进程。

之前的文章中也提到了信号机制，点击这里查看

共享文件

也叫管道通信，通过一个特殊的称之为管道（pipeline）的共享文件连接两个读写进程，管道允许进程按照先进先出的方式单向传送数据。

                                +------------------------------+
                                |                              |
+-------------+                 |                              |             +---------------+
|             |    byte stream  |                              | byte stream |               |
|  Process 1  +---------------->|           pipeline           +-----------> |   Process 2   |
|   (Write)   |                 |                              |             |     (Read)    |
+-------------+                 |                              |             +---------------+
                                |                              |
                                +------------------------------+

共享文件可以借助于文件系统的机制实现，包括管道文件的创建、打开、关闭以及读写。进程对共享文件互斥使用，即一个进程正在读或写时，另一个进程必须等待。共享文件的大小是有限制的，因此通信双方需要正确同步（在共享文件装满之前取走数据，以避免后来的数据无法写入而造成进程阻塞）。

有名管道

普通的匿名管道（PIPE）仅能连接具有共同祖先的进程（通过fork继承管道文件的访问权限），并且具有临时性，难以提供全局服务。在UNIX中，有名管道（FIFO）作为一种永久性通信机制具有UNIX文件名、访问权限，并且性能与普通管道相同（数据被读取后消失，即先进先出FIFO）。

关于有名管道和匿名管道，也可以看看https://blog.csdn.net/qq_36016407/article/details/53818280

共享存储区

共享存储区是进程通信中最快捷和有效的方法，具体过程是：进程向系统共享存储区申请一个分区段，并指定关键字；若系统已为其他进程分配了该分区，则返回对应的关键字给申请者。分区段连接到进程的虚拟空间，进程可以通过对该区段的读/写来实现通信。

消息传递

基本概念：消息是一组信息，由消息头和消息体组成。通过send和receive两个消息传递原语实现进程间通信，通常是异步send（即不必等到接收方receive再发送），同步receive（即必须等发送方send后才能接收）。常见的做法是构建消息队列（消息的链表），并由消息队列标识符标识一个队列。

死锁

死锁是指因为某些原因导致进程始终获取不到所需的资源（或者无法满足某些条件）而永远处于等待状态的现象。一组进程处于死锁状态是指：如果在一个进程集合中得每个进程都在等待只能由该集合中其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。

死锁举例

进程推进顺序不当产生死锁

进程P				进程Q
1.请求读卡机		1.请求打印机
2.请求打印机		2.请求读卡机
...				...
产生死锁的执行顺序：P1->Q1->P2->Q2

PV操作使用不当产生死锁

与上一例类似，即某个进程先对信号量a执行P操作，再对信号量b执行P操作；另一个进程先对信号量b执行P操作，再对信号量a执行P操作，两个进程均因为第二个P操作无法满足而阻塞不前，发生死锁。

同类资源分配不当产生死锁

5个同类资源，5个请求进程，每个进程需要请求2个资源才能继续执行。如果按照轮流分配，每次分配一个资源的分配方式将导致死锁。

对临时性资源使用不加限制产生死锁

在进程通信中，消息作为临时性资源如果使用不当将发生死锁。例如：

• P1等待P3的消息到达后向P2发送消息
• P2等待P1的消息到达后向P3发送消息
• P3等待P2的消息到达后向P1发送消息

死锁的防止

死锁存在的四个必要条件（Coffman，1971）：

• 互斥条件
• 占有和等待条件
• 不剥夺条件
• 循环等待条件

常见的死锁防止方法：

• 静态分配策略，破坏第二个条件
• 层次分配策略，破坏第四个条件

死锁的避免

破坏死锁存在的条件往往会导致低效的程序运行和较低的资源使用率，因此尝试通过对每一次资源申请进行分析来判断是否会造成死锁，从而避免死锁的发生。

常见算法

• 资源轨迹图
  • 略
• 银行家算法
  • 前提条件
    • 每个进程必须事先说明自己对每种资源所要求的最大数量，并承诺在获得所需的资源后能够在有限时间内归还
    • 进程可以分多次向系统申请所需资源
  • 算法的关键是对进程发出的资源申请做出判断，因此又称“资源分配拒绝法”
  • 算法对于一次资源申请的判断依据是，如果同意该申请，是否存在一个安全状态序列使所有进程最终均能获得所需的资源，如果存在则可以同意此次资源申请，否则拒绝此次申请
  • 缺陷：
    • 进程很难在运行前知道自己所需资源的最大数量
    • 算法要求系统中各进程必须是无关的，即没有同步要求
    • 算法无法处理进程数量和资源数量动态变化的情况

死锁的检测

使用资源分配图：

• 描述进程和资源间申请及分配关系的一种有向图，图中顶点分为进程和资源两种，一条进程->资源的有向边为申请边，代表进程申请资源，一条资源->进程的有向边为分配边，代表资源被分配给进程。
• 对于每种资源只有一个实例的情况，如果资源分配图中出现环则意味着出现死锁
• 对于有资源存在多个实例的情况，首先需要进行化简：如果某个进程满足了所有需要的资源（出度为0），则将它占有的资源全部释放，从而变成一个孤立的点，释放的资源转而分配给其他需要的进程。重复该过程，知道资源分配图无法继续化简，如果图中没有边，则没有死锁发生，否则出现了死锁，图中所有非孤立的进程就是发生死锁的进程

死锁的解除

• 终止所有死锁进程
• 一次终止一个进程，直到死锁解除
• 逐步从进程占用的资源中抢夺资源给其他进程使用，直到死锁解除