[TOC]

什么是进程？

概念

  • 进程（process）：是一个具有一定独立功能的程序，关于某个数据集合的一次运行活动，是操作系统资源分配的基本单位

  • 要点

    1. 进程是程序的正在被执行的实例

      躺在磁盘里的程序不是进程，而是程序被加载到内存正在运行的过程才是进程

    2. 进程是程序在一个数据集合上运行的过程

    3. 进程是操作系统进行资源分配的基本单位

结构和特征

进程的结构

  • 控制块（Process Control Block, PCB）：进程的唯一标识，用以操作系统来辨别不同的进程，包括如下几部分：

    • OS根据PCB来对进程进行控制和管理，进程的创建和撤销都是根据PCB进行的
    • 存储：程序计数器、进程状态、CPU暂存器、存储器管理、输入输出状态等信息
    • PCB在新建进程时创建，并常驻内存，是进程实体的一部分，也是进程的唯一标识

  • 数据段：原始数据及进程开启后产生的各种数据

    • 数据区域（data region）：存储（全局和静态）变量和进程执行期间使用的动态分配的内存
    • 堆栈区域（stack region）：存储活动过程调用的指令和本地变量、中间数据

  • 程序段：存放在文本区域（text region），被多个进程共享

    存储处理器执行的代码，二进制格式

程序的一次执行过程就是一个进程，程序实体就是进程的映像

进程的特征（理解）

  • 动态性：由创建而生，由撤销而亡
  • 并发性：多个进程可以同时运行（相互之间互不干扰耶）
  • 独立性：独立资源分配（这样就可以保证更好的保证并发性）
  • 异步性：相互独立，互不干扰，各自以不可预知的速度向前推进或者说实体按异步方式运行

进程与线程

什么是线程？

  • 线程（thread）是一系列活动按事先设定好的顺序一次执行的过程，是一系列指令的集合
  • 是一条执行路径，不能单独存在，必须包含在进程中
  • 可以并发执行
  • 是程序执行的基本单位，每个线程可以独立执行，并共享进程的资源和内存空间
  • 线程是OS运算调度的最小单位

区别

进程是操作系统资源分配和调度的基本单位，也就是说，进程创建的目的其实就是操作系统向程序运行的那个过程分配资源；而线程是OS运算调度的最小单位，也就是说，线程才是真正使用CPU运算的，才是真正干活的。

而且，进程里的多个线程是共享进程资源的

  • 调度：OS中进程是资源分配的基本单位，线程是运算调度的最小单位
  • 资源：进程才拥有资源，多个线程可以共享进程资源（进程申请资源，线程只有资源的使用权）
  • 地址空间或其他资源：不同进程之间相互独立，但是同一进程里的不同线程是共用进程资源的，如内存等
  • 通信：进程通信需要其他手段辅助，线程通信就更为容易一点

线程相对于进程，大大降低了创建、撤销和切换可执行实体的成本和难度

为什么要引入线程？

  • 节省资源：线程比进程更容易创建和撤销，引入线程后，降低开销
  • 共享进程资源：线程可以共享进程的资源和内存空间，这使得线程间的通信更加容易
  • 提高响应能力：通过多线程技术，可以在后台执行耗时的任务，同时保持前台界面的响应性能
  • 提高系统的并发性：多个线程可以并行执行，从而提高系统的并发性和吞吐量。如java的多线程编程

线程的实现方式

用户级线程（ULT）

在用户空间实现的线程，叫用户级线程。OS无法感知用户级线程的存在，此时线程的创建、调度、切换、运行、销毁都是用户空间实现的，内核空间并没有参与，OS只是在起初给多个用户级线程所在的进程分配资源。剩下的线程调度和切换等线程的管理工作都是由应用程序完成的，OS并没有参与其中。

CPU分配到程序P，由程序P完成用户线程调度，分配资源

在这里插入图片描述

优点：

  • 线程的切换不需要转到内核空间，节省了模式切换的开销
  • 调度算法可以由进程根据需要，对自己的线程选择调度算法进行管理和调度，而与OS的低级调度算法无关
  • 用户级线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，因此用户级线程甚至可以在不支持线程机制的操作平台上实现

缺点：

  • 系统调用阻塞问题，再基于进程机制的OS中，大多数系统调用将使进程阻塞，因此当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程会被阻塞。而内核支持线程中的其他线程依然能运行
  • 不能利用多处理机进行多重处理的优点，内核每次分配给一个进程的仅有一个CPU，因此，进程中仅有一个线程能执行，在该线程放弃CPU前，其他线程只能等待
内核级线程（KLT）

在内核空间实现的线程，叫内核级线程。进程里的所有线程的管理工作都交由内核态来完成。当然，每个内核线程都会设置一个内核线程控制块（类似于PCB的作用）用以内核的感知和控制。

进程P通过轻量级进程LWP调用内核KLT，内核线程通过调度器Thread Scheduler调度将任务映射到相应的CPU上

在这里插入图片描述

但是，程序一般不会直接去使用内核线程，而是通过去使用内核线程的一种高级接口叫轻量级进程（Light Weight Process）去操作内核线程（官方定义名称，在大多数系统中，LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息，而这也是它之所以被称为轻量级的原因）。并且它们之间的关系是1:1存在。需要注意的是只有先支持内核线程，才能有轻量级进程。

优点：

  • 在多处理机系统中，内核能够同时调度同一进程中的多个线程并行执行
  • 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其他线程占有处理机运行，也可以运行其他进程中的线程。也就是说，不会出现一个线程阻塞，进程内的其他线程无法执行的情况
  • 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小
  • 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率

缺点：

  • 对于用户的线程切换而言，其模式切换的开销比较大，在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态进行，这是因为用户进程的线程在用户态运行，而线程的调度和管理是在内核实现的，系统开销较大
  • 相较于用户级线程而言，内核对内核级线程的支持是有限的
混合实现

使用用户线程和内核级线程混合实现这种方式，分别使用了用户线程和内核级线程的优点。在这种混合模式中，用户线程与内核级线程的数量比是不定的，即为N:M的关系。

进程P多个用户级线程开启，线程的创建、销毁、切换都是有自己来，但是线程调度、处理器映射通过分配轻量级进程来做系统调用。算是一种折中的做法吧

在这里插入图片描述

总结

进程

  • 作为系统资源分配的基本单位
  • 可以包括多个线程，一般来说，至少有一个线程
  • 进程不是一个可执行的实体，真正执行的是线程。进程只是负责应用程序实体的资源管理

线程

是运行和调度的基本单位

目的

  • 引入进程的目的在于，使多道程序并发执行而互不影响，提高系统的资源利用率和吞吐量
  • 引入线程的目的是为了减少程序在开发时的时空开销，提高系统的并发性。相较于进程而言，大大降低

进程是怎么运行的？

进程状态

进程阻塞原因以I/O请求为例

这里写图片描述

五种基本状态

就绪（Ready）

进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行

执行（Running）

进程处于就绪状态被调度后，进程进入执行状态

阻塞（Blocking）

正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法继续运行，进程受到阻塞。在满足请求时进入就绪状态等待进程调度

何时会发生？

例如，应用程序发出I/O请求时，需要等待系统调用的结果返回，那么这段等待时间是阻塞的，就可以将阻塞的进程的CPU使用权夺走，交给已经就绪的进程使用

创建（New）

进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态；当进程创建完成后，进程就会进入就绪态。

何时会发生？

例如：用户启动应用，应用开始加载到内存里，创建进程work

终止（Terminated）

进程结束，或出现错误，或被系统终止，进入终止状态，进行进程资源释放和回收。

何时会发生？

例如：正常结束、异常结束、外界干预

进程控制

即OS对进程实现有效的管理，包括创建新进程、撤销已有进程、挂起、阻塞和唤醒、进程切换等操作。OS通过原语操作实现进程控制

原语

  • 定义：由若干条指令组成，完成特定的功能，是一种原子操作

    其实就是将多条指令封装成函数并形成原子操作，用以进程控制

  • 特点

    1. 原子性：要么全做，要么都不做，执行过程不会被中断
    2. 在内核态（也叫管态、系统态、特权态、核心态）下执行，常驻内存
    3. 是内核的三大支撑功能之一（中断处理、时钟管理、原语操作）

  • 原语图

    创建原语（create）、阻塞原语（block）、唤醒原语（wakeup）、撤销原语（destroy）

    image-20230408213922993

创建

父子进程
  • 在OS中，允许一个进程创建另一个进程，创建者称为父进程，被创建者称为子进程，子进程也能创建更多孙进程。结构像树一样。如在UNIX中，由父子进程组成一个进程组。
  • 子进程可以继承父进程所拥有的的资源。当子进程被撤销时，应将从父进程那里获得的资源归还给父进程。此外，在撤销父进程的时候，也必须同时撤销其所有子进程。
  • 注意：在Windows中不存在任何进程层次结构，所有进程具有相同的地位。但当进程创建了一个进程时，进程创建者会获得一个句柄（令牌），可以用来被控制被创建的进程，但是这个句柄是可以传递的。也就是说，获得了句柄的进程就拥有控制该进程的权利，因此进程之间不是层次关系，而是是否获得句柄，控制与被控制的关系。
引进创建进程的典型事件
  1. 用户登录：在分时系统中，用户在终端键入登录命令后，若登录成功，系统将为该用户建立一个进程。
  2. 作业调度：在多道批处理系统中，当作业调度程序按一定算法调度到某些作业时，便将它们存入内存，为它们创建进程。
  3. 提供服务：当运行中用户程序提出某种请求，系统将专门创建一个进程来提供用户所需要的服务，如需要打印文件时，创建打印进程。
  4. 应用请求：用户进程自己创建新进程，与创建者进程以并发的形式完成特定任务。
进程创建过程

OS调用进程创建原语Create，该原语按照以下步骤创建一个新进程：

  1. 申请空白PCB，为新进程从申请获得唯一的数字标识符。
  2. 为新进程分配其运行所需资源，包括各种物理资源和逻辑资源，如CPU时间、所需内存大小、I/O设备等。
  3. 初始化PCB：①初始化标识信息（数字标识符和父进程标识符）②初始化处理机状态（程序计数器指向程序入口地址，栈指针指向栈顶）③初始化处理机控制信息（设置进程状态、优先级等）
  4. 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

终止

引起进程终止的事件
  1. 正常结束：表示进程的任务已经完成，准备退出运行。在批处理系统中，通常会在程序的最后安排一条Halt指令，用于向OS表示运行已结束。
  2. 异常结束：指进程在运行时发生了某种异常事件，使程序无法继续运行。常见的有： ① 越界：程序访问的存储区越出该进程的区域。 ② 保护错：进程视图访问一个不存在或不允许访问的资源或文件。 ③ 非法指令：程序试图去执行一条不存在的指令。 ④ 特权指令错：用户没有执行当前指令的权限。 ⑤ 运行超时：执行时间超过允许执行的最大值。 ⑥ 等待超时：进程等待某事件的时间超过规定最大值。 ⑦ 算术运算错：进程试图执行一个被进制的运算。 ⑧ I/O故障：在I/O过程发送了错误
  3. 外界干预：指进程应外界的请求而终止运行。这些干预有：程序员或操作系统干预；父进程请求；父进程终止。
进程终止过程

OS调用进程终止原语，按下述过程终止指定的进程：

  1. 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，读取进程的状态。
  2. 若进程处于执行状态，立即终止进程，并置调度标志位真，在进程终止后重新进程CPU调度。
  3. 若进程还有子孙进程，将它们也终止，防止它们称为不可控的进程。
  4. 将终止进程所拥有的全部资源归还给父进程，或归还给系统。
  5. 将终止进程的PCB从所在队列中移除，操作系统记录等待需要搜集信息的其它程序搜集信息。

阻塞和唤醒

在使用阻塞和唤醒时，必须成对使用，如果在某进程中引起了进程阻塞，那么与之合作的、或相关进程中必须安排一条该进程的唤醒原语，保证进程不会永久的处于阻塞状态，无法再运行。

引起进程的阻塞与唤醒的事件
  1. 向系统请求共享资源失败，请求者进程只能被阻塞，只有在共享资源空闲时，才会被唤醒。
  2. 等待某种操作的完成，在等待过程中应该是阻塞状态，等操作完成后，才会唤醒。
  3. 新数据尚未到达，进程只能阻塞，直到数据到达被唤醒。
  4. 等待新任务的到达，进程会阻塞，直到新任务到达会被唤醒，处理完成后又把自己阻塞起来。
进程阻塞过程

当需要阻塞进程时，进程调用阻塞原语block将自己阻塞，是一种主动行为。进入block状态后，进程先立即停止执行，然后将PCB的状态改为阻塞状态，并将PCB插入相应的阻塞队列。最后，重新进行CPU调度，切换前在PCB中保留当前进程的CPU状态，然后将CPU状态按新进程的PCB设置。

进程唤醒过程

当被阻塞进程所期待的事情发生，有关进程调用唤醒原语wakeup将等待该事件的进程唤醒。 执行过程：将阻塞进程从阻塞队列中移出，将其PCB的状态改为就绪状态，然后将PCB插入到就绪队列中。

挂起与激活

进程的挂起与激活操作分别通过suspend原语和active原语实现。值得注意的是：静止阻塞和静止就绪不是进程的五大基本状态之一。之后，直接在外存里放着，需要用的时候再加载到内存里

image-20230408222631030

进程的挂起

当系统中出现了引起进程挂起的事件，OS利用挂起原语suspend将指定进程或处于阻塞状态的进程挂起。 执行过程：首先检查被挂起进程的状态，如果是就绪状态，就改为就绪挂起状态；如果是阻塞状态，就改为阻塞挂起状态；为了方便用户或父进程考查该进程的运行情况，把该进程的PCB复制到某指定的内存区域（一般挂起状态的进程存在于外存）。如果被挂起进程正在执行，就重新进行调度。（也就是说，正在执行的进程不能被突然挂起，需要等到该进程调度到活动阻塞或活动就绪状态才行）

进程的激活

当系统中发生激活进程的时间时，OS将利用激活原语active将制定进程激活。 激活过程：先将进程（PCB）从外存调入内存，检查该进程现在的状态，若是就绪挂起，则改为就绪状态；若是阻塞挂起，则改为阻塞状态。加入采用抢占式调度策略，则每当有就绪挂起状态的进程被激活，就要检查是否需要进行重新调度（如使用优先级的话，检查激活进程的优先级是否大于当前正在运行的进程，如果低则不用重新调度；如果高则剥夺当前进程的运行，把CPU分配给刚激活的进程）。

进程切换

状态转换

进程调度

调度的概念

  • **定义：**根据一定的算法和规则将处理机资源进行重新分配的过程

  • **前提：**作业/进程数远大于处理机数目

  • **目的：**提高资源利用率，减少处理机的空闲时间

  • **调度程序：**一方面要满足特定系统用户的需求（快速响应），另一方面要考虑系统整体效率（系统平均周转时间）和调度算法本身的开销

  • 调度层次：

    image-20230413142916306

    1. 高级调度（作业调度）
      • 将外存里的后背作业队列调入内存，并筛入就绪队列
      • 只调入一次，调出一次
    2. 中级调度（内存调度）
      • 将进程调至外村，条件合适再调回内存
      • 在内、外村对换取进行进程对换
    3. 低级调度（进程调度）
      • 从就绪队列选取进程分配给处理机
      • 最基本的调度，频率非常高

进程调度的时机

什么时候会发生进程调度呢？引起进程调度的因素有哪些？这些也就是进程的调度时机。

  1. 正在执行的进程执行完毕
  2. 执行中的进程因提出I/O请求或发生等事件而暂停执行。
  3. 时间片完成
  4. 在进程通信或同步过程中执行了某种原语操作，如P操作（wait操作）阻塞
  5. 高优先者进入（适用于剥夺式调度的系统）

进程调度的方式

抢占式调度（剥夺式调度）

  • 定义：立即暂停当前进程，分配处理机的时间片给另一个进程

  • **原则：**优先权/短进程优先/时间片原则

    优先级更高的进程出现在就绪队列，那么当前进程直接让出CPU时间片给这个更高优先级的进程；

    短进程优先：短进程执行时间很短，那么可以直接去执行这个短进程

    时间片优先：当前进程的时间片用完后，需要将处理机的使用权移交给其他就绪态进程

  • **优点：**具有作业优先级，适合分时/实时操作系统

非抢占式调度（非剥夺式调度）
  • **定义：**若有进程请求执行，需要等待处理机执行完当前进程或当前进程阻塞
  • **缺点：**适合批处理系统，不适合分时/实时系统

进程调度的过程

  1. 保存镜像：记录进程的CPU现场
  2. 调度算法：确定分配处理机的原则
  3. 进程切换：分配处理机给其他进程
  4. 处理机回收：从进程收回处理机

进程调度的切换具体过程

  1. 检查是否允许上下文切换，有可能某进程处于原语操作中，不允许切换
  2. 保存当前进程的上下文（程序计数器PC指针，寄存器）
  3. 更新PCB信息
  4. 把此进程的PCB移入队列（可能是就绪队列，也可能是阻塞队列）
  5. 选择另一个就绪态队列执行，并更新PCB
  6. 更新内存管理的数据结构
  7. 恢复所选进程的上下文，将CPU执行权交给所选进程

典型的调度算法

FCFS（先来先服务）

First Come First Served

  • 定义：分配处理机给作业队列或就绪队列中队头的作业或就绪态进程
  • 原则：按照作业/就绪态进程到达顺序服务
  • **调度方式：**非抢占式调度
  • **适用场景：**作业调度、进程调度
  • **优点：**有利于CPU繁忙型作业，充分利用CPU资源
  • **缺点：**I/O繁忙型作业，操作耗时，CPU比较浪费
SJF（短作业优先）

Shortest Job First

  • 定义：所需服务时间最短的作业/就绪态进程优先分配处理机使用权

  • 原则：追求最少的平均（带权）周转时间

  • **调度方式：**SJF/SRTN非抢占式调度

    由于短作业优先调度算法里还是存在进程阻塞后，再加入就绪队列，此时进程已经进行了一部分工作，那么，再进行短作业调度时，看的就是剩余执行时间了。这种调度也被称为SRTN（Shortest Remaining Time Next）

  • **适用场景：**作业调度、进程调度

  • **优点：**平均等待/周转时间最少

  • **缺点：**长作业周转时间会增加或饥饿；估计时间不准确，不能保证紧迫任务计时处理

HRRN（高响应比优先调度）

HRRN（Highest Response Ratio Next）调度算法是介于先来先服务算法与最短进程优先算法之间的一种折中算法。先来先服务算法只考虑进程的等待时间而忽视了进程的执行时间，而最短进程优先调度算法只考虑用户估计的进程的执行时间而忽视了就绪进程的等待时间。

为此需要定义响应比Rp:

1

Rp=（等待时间+预计执行时间）/执行时间=响应时间/执行时间
  • 定义： Rp较大的进程获得处理机使用权
  • 原则：综合考虑作业或进程的等待时间和执行时间
  • **调度方式：**非抢占式
  • **适用场景：**作业调度、进程调度
  • **优点：**优点很明显，权衡了进程等待时间和执行时间，不会使得某些进程等待太长时间
  • **缺点：**一旦当前进程放弃执行权（完成或阻塞）时，那么就会重新计算所有进程的响应比；
PSA（优先级调度）

  • **定义：**又叫优先级调度，按作业/进程的优先级（紧迫程度）进行调度

  • **原则：**优先级最高（最紧迫）的作业/进程先调度

  • **调度方式：**抢占式/非抢占式（并不能获得即使执行）

    抢占式：高优先级的立即执行

    非抢占式：高优先级等待当前进程让出处理机后执行

  • **适用场景：**作业调度/进程调度

  • 优先级设置原则：

    • 静态/动态优先级
    • 系统>用户；交互型>非交互型;I/O型>计算型
    • 低优先级进程可能会产生”饥饿“，也就是低优先级进程的等待时间会大大延长
RR（时间片轮转调度）

  • **定义：**按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺

  • 原则：公平、轮流为每个进程服务，进程在一定时间内都能得到响应

  • **调度方式：**抢占式，由时钟确定时间，时间一到，就会产生中断

    时间片的决定因素

    • 系统的响应时间、就绪队列的进程数量、系统的处理能力

  • **适用场景：**进程调度

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

  • **缺点：**时间片太大，相当于FCFS；太小，处理机切换频繁，开销增大

MFQ（多级反馈队列调度）

  • 定义： 设置多个按优先级排序的就绪队列。优先级从高到低，时间片从小到大。新进程采用队列降级法

    新来的进程会进入第一季队列，然后分时间片来获得处理机；

    没有执行完，将会移动到下一级队列，前面的队列不为空，不执行后续队列进程

  • 原则：集前几种调度算法的有点，相当于PSA+RR

  • **调度方式：**抢占式

  • **适用场景：**进程调度

  • 优缺点：

    • 对各类型的相对公平：快速响应。

      新来的进程都是进入第一级队列，都会得到CPU时间片执行一会儿，没执行完会扔到下一级队列，等到上一级队列进程执行完毕，下一级的队列里的进程再次得到执行

    • 终端型作业用户：短作业优先

      作业越短，那么最终完成进程所在队列级数就会越小，所以整体来看，作业越短，进程完成时间就越短

    • 批处理作业用户：周转时间短

      当批处理的大量进程都需要执行时，使用MFQ算法调度，让每个进程都可以公平得到CPU时间片，这样算的话

    • 长批处理作业用户：每个进程都会被依次执行，当前进程没执行完毕就会塞入下一级队列等待执行。所以长批处理作业，也是会得到CPU时间片的，不会发生“饥饿”现象

    在多级反馈队列进程调度算法里，低优先级队列里的进程会发生”饥饿“吗？

    答：不会。因为MFQ调度算法里前面队列不为空，后面的队列就不会得到执行，所以低优先级的队列一定是被执行过至少一个CPU时间片的

进程之间是怎么协作的？

进程通信

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。

进程间通信目的一般有共享数据，数据传输，消息通知，进程控制等。以 Unix/Linux 为例，介绍几种重要的进程间通信方式：共享内存，管道，消息队列，信号量，信号，套接字

  • 定义

    进程间通信就是在不同进程之间传播或交换信息，那么不同进程之间存在着什么双方都可以访问的介质呢？进程的用户空间是互相独立的，一般而言是不能互相访问的，唯一的例外是共享内存区。另外，系统空间是“公共场所”，各进程均可以访问，所以内核也可以提供这样的条件。此外，还有双方都可以访问的外设。在这个意义上，两个进程当然也可以通过磁盘上的普通文件交换信息，或者通过“注册表”或其它数据库中的某些表项和记录交换信息。广义上这也是进程间通信的手段，但是一般都不把这算作“进程间通信”。进程间通信（IPC，Inter Process Communication）是一组编程接口，让程序员能够协调不同的进程，使之能在一个操作系统里同时运行，并相互传递、交换信息。IPC方法包括管道（PIPE）、消息队列、信号、共享存储以及套接字（Socket）。

  • 为什么需要进程间通信呢？

    因为有些复杂程序或者是系统需要多个进程或者线程共同完成某个具体的任务，那么也就需要进程之间通信和数据访问。整个系统以进程粒度运行可以进一步提高系统整体并行性能和内存访问安全，每个进程可以有各自的分工。所以多个进程共同完成一个大的系统是比单个进程多线程要有很大的优势。

管道

管道在Linux中就是文件（本质上就是内存里固定大小的缓冲区），而且大小固定，是以流的形式读写的：未满不读，已满不写，未空不写，已空不写。

例如：有个4kb大小的管道，那么写的时候，就是

如果你学过 Linux 命令，那你肯定很熟悉|这个竖线。

1

ps auxf | grep mysql

上面命令行里的|竖线就是一个管道，它的功能是将前一个命令ps auxf的输出，作为后一个命令grep mysql的输入，从这功能描述，可以看出管道传输数据是单向的，如果想相互通信，我们需要创建两个管道才行.

同时，我们得知上面这种管道是没有名字，所以|表示的管道称为匿名管道，用完了就销毁。

管道还有另外一个类型是命名管道，也被叫做 FIFO，因为数据是先进先出的传输方式。

在使用命名管道前，先需要通过 mkfifo 命令来创建，并且指定管道名字：

1

mkfifo myPipe

myPipe就是这个管道的名称，基于 Linux 一切皆文件的理念，所以管道也是以文件的方式存在，我们可以用ls看一下，这个文件的类型是 p，也就是 pipe（管道） 的意思：

1
2

$ ls -l
prw-r--r--. 1 root    root         0 Jul 17 02:45 myPipe

接下来，我们往myPipe这个管道写入数据：

1
2

echo "hello" > myPipe  # 将数据写进管道
                       # 停住了 ...

你操作了后，你会发现命令执行后就停在这了，这是因为管道里的内容没有被读取，只有当管道里的数据被读完后，命令才可以正常退出。

于是，我们执行另外一个命令来读取这个管道里的数据：

1
2

cat < myPipe  # 读取管道里的数据
hello

可以看到，管道里的内容被读取出来了，并打印在了终端上，另外一方面，echo 那个命令也正常退出了。

我们可以看出，管道这种通信方式效率低，不适合进程间频繁地交换数据。当然，它的好处，自然就是简单，同时也我们很容易得知管道里的数据已经被另一个进程读取了。

我们可以得知，对于匿名管道，它的通信范围是存在父子关系的进程。因为管道没有实体，也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通的目的。

img

在 shell 里面执行 A | B命令的时候，A 进程和 B 进程都是 shell 创建出来的子进程，A 和 B 之间不存在父子关系，它俩的父进程都是 shell。

img

另外，对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信。

消息队列

前面说到管道的通信方式是效率低的，因此管道不适合进程间频繁地交换数据。对于这个问题，消息队列的通信模式就可以解决。

比如，A 进程要给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。同理，B 进程要给 A 进程发送消息也是如此。

再来，消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体（数据块），消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。

image.png

消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁。

缺点

消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

共享内存

消息队列的读取和写入的过程，都会有发生用户态与内核态之间的消息拷贝过程。那共享内存的方式，就很好的解决了这一问题。

现代操作系统，对于内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中。所以，即使进程 A 和 进程 B 的虚拟地址是一样的，其实访问的是不同的物理内存地址，对于数据的增删查改互不影响。

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

img

Linux系统mmap的实现机制

信号量

用了共享内存通信方式，带来新的问题，那就是如果多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了。（脏写）

为了防止多进程竞争共享资源，而造成的数据错乱，所以需要保护机制，使得共享的资源，在任意时刻只能被一个进程访问。正好，信号量就实现了这一保护机制。

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。

信号量表示资源的数量，控制信号量的方式有两种原子操作：

  • 一个是 P 操作，这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
  • 另一个是 V 操作，这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程；

P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。 接下来，举个例子，如果要使得两个进程互斥访问共享内存，我们可以初始化信号量为 1。

img

具体的过程如下：

  • 进程 A 在访问共享内存前，先执行了 P 操作，由于信号量的初始值为 1，故在进程 A 执行 P 操作后信号量变为 0，表示共享资源可用，于是进程 A 就可以访问共享内存。

  • 若此时，进程 B 也想访问共享内存，执行了 P 操作，结果信号量变为了 -1，这就意味着临界资源已被占用，因此进程 B 被阻塞。

  • 直到进程 A 访问完共享内存，才会执行 V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执行 V 操作，使信号量恢复到初始值 1。

    可以发现，信号初始化为 1，就代表着是互斥信号量，它可以保证共享内存在任何时刻只有一个进程在访问，这就很好的保护了共享内存。 另外，在多进程里，每个进程并不一定是顺序执行的，它们基本是以各自独立的、不可预知的速度向前推进，但有时候我们又希望多个进程能密切合作，以实现一个共同的任务。

    例如，进程 A 是负责生产数据，而进程 B 是负责读取数据，这两个进程是相互合作、相互依赖的，进程 A 必须先生产了数据，进程 B 才能读取到数据，所以执行是有前后顺序的。

    那么这时候，就可以用信号量来实现多进程同步的方式，我们可以初始化信号量为 0。

    img

    具体过程：

  • 如果进程 B 比进程 A 先执行了，那么执行到 P 操作时，由于信号量初始值为 0，故信号量会变为 -1，表示进程 A 还没生产数据，于是进程 B 就阻塞等待；

  • 接着，当进程 A 生产完数据后，执行了 V 操作，就会使得信号量变为 0，于是就会唤醒阻塞在 P 操作的进程 B；

  • 最后，进程 B 被唤醒后，意味着进程 A 已经生产了数据，于是进程 B 就可以正常读取数据了。

可以发现，信号初始化为 0，就代表着是同步信号量，它可以保证进程 A 应在进程 B 之前执行。

信号

信号一般用于一些异常情况下的进程间通信，是一种异步通信，它的数据结构一般就是一个数字.

在 Linux 操作系统中， 为了响应各种各样的事件，提供了几十种信号，分别代表不同的意义。我们可以通过 kill -l 命令，查看所有的信号：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

$ kill -l
 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

运行在 shell 终端的进程，我们可以通过键盘输入某些组合键的时候，给进程发送信号。例如

  • Ctrl+C 产生 SIGINT 信号，表示终止该进程；

  • Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束；

    如果进程在后台运行，可以通过 kill 命令的方式给进程发送信号，但前提需要知道运行中的进程 PID 号，例如：

    kill -9 1050 ，表示给 PID 为 1050 的进程发送 SIGKILL 信号，用来立即结束该进程； 所以，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）。

    信号是进程间通信机制中唯一的异步通信机制

进程需要为信号设置相应的监听处理，当收到特定信号时，执行相应的操作，类似很多编程语言里的通知机制。

Socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。​

总结

进程通信方式总结

进程同步

概念

  1. 进程同步概念

    主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，使执行的结果具有可再现性。

  2. 进程之间的两种制约关系

    • 间接相互制约关系（互斥）：互斥地访问系统共享资源

    • 直接相互制约关系（同步）：进程间合作，比如进程A、B，进程B是对进程A的数据进行处理，那么进程B就一定要在进程A之后执行。

      例如管道，发送者先发满管道后，接收者才可以去读管道。

互斥的访问过程与原则

临界资源

一段时间仅允许一个进程访问的资源

临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。 并发进程对临界资源的访问必须做某种限制，否则就可能出现与时间有关的错误

临界资源访问过程
  1. **进入区：**尝试进入临界区，成功就上锁（lock）
  2. **临界区：**访问共享资源
  3. **退出区：**解锁（unlock），唤醒其他进程
  4. **剩余区：**剩余代码
1
2
3
4
5
6
7
8

//一个访问临界资源的循环进程描述伪代码如下：
while(true)
{
	进入区
	临界区
	退出区
	剩余区
}
临界资源访问原则
  • 空闲让进：临界区空闲，允许一个进程进入
  • 忙则等待：临界区已有进程，其他进程进入阻塞状态
  • 有限等待：处于等待的进程，等待的时间有限
  • 让权等待：等待时应让出CPU执行权，防止”忙等待“

互斥软件实现基本方法*

while代码就是自旋锁

单标志法

算法思想：两个进程在访问完临界区后会把临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

img

turn的初始值为0，即刚开始值允许0号进程进入临界区。

若P1先上执行机运行，则会一直卡在⑤。直到P1的时间片用完，发生调度，切换P0上处理机运行。代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即使切换会P1，P1依然会被卡在⑤。只有P0在退出区将turn改为1后，P1才能进入临界区。

因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”。

但是只能按照P0 -> P1 -> P0 -> P1…这样轮流访问。如果P0访问临界区完毕后，不再访问临界区，但是P1需要再次访问临界区时turn!=1，进程不能获得锁，一直阻塞，这样就违背“空闲让进”原则。

因此，单标记法存在的主要问题是：违背“空闲让进”原则和“让权等待”。

双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“falg[0]=ture”意味着0号进程P0现在向进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设置为true，之后开始访问临界区。

img

在高并发的情况下，有可能按照①⑤②⑥③…的顺序执行，那么P0和P1将会同时访问临界区。因此，双标志先检查法的主要问题是:违反“忙则等待”原则和“让权等待”。

原因在于进入区的“检查”和“上锁”不是原子的。“检查” 后，“上锁”前可能已经发生进程切换。

双标志后检查法

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作不是原子的，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

img

高并发下，按照①⑤②…的顺序执行，PO 和P1将都无法进入临界区。因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”、“让权等待”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

Peterson 算法

算法思想：结合双标记法、单标记法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

img

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

互斥硬件实现基本方法

中断屏蔽方法：关中断/开中断
  • 禁止一切中断，CPU执行完临界区之前，不会发生进程切换的中断响应。
  • 关中断时间长会影响效率
  • 不适用于多处理机，无法防止其他处理机调度其他进程访问临界区。因为关中断只对当前处理机生效，不会对其他处理机是否响应中断请求造成影响
  • 只是用于内核进程（该指令运行于内核态）
Test-And-Set指令

简称TS指令，也有些地方称为TestAndSetLock指令，或者TSL指令。TSL指令是用硬件实现的，执行的过程不允许被中断，属于原子操作。以下是用C语言描述的逻辑。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

//bool lock表示当前临界区是否被加锁
//true标识已加锁，false表示未加锁
bool TestAndSet(bool *lock){
    bool old;
    old=*lock;	//old用来存放lock原来的值
    *lock=true;	//无论之前是否加锁，都将lock设为true
    return old;	//返回lock原来的值
}

//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));	//“上锁”并“检查”是一个原子操作
critical section;	//临界区代码
lock=false;	//解锁
remainder section;	//剩余区代码

优点：实现简单，把“上锁”和“检查“通过硬件的方式变成原子操作；适用于多处理机环境。

缺点：仍然不满足让权等待原则（无法进入临界区时释放处理机）。 原因：暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致忙等。

swap指令

Swap指令，又叫XCHG指令，是用硬件实现的原子操作，执行的过程中不允许被中断。以下是C语言描述的逻辑

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Swap(bool *a,bool *b){
    bool tmp;
    tmp=*a;
    *a=*b;
    *b=tmp;
}

//以下是用Swap指令实现互斥的算法逻辑
//lock表示当前临界区是否被加锁
bool old=true;
while(old==true)
    Swap(&lock,&old);
//临界区代码...
lock=false;
//剩余区代码...

逻辑上和TSL一样，优缺点和TSL也一样，不满足让权等待。

信号量

信号量其实就是一个变量(可以是一个整数， 也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一一个初值为1的信号量。

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

原语是一种特殊的程序段，是原子操作。**原语是由关中断/开中断指令实现的。**软件解决方案的主要问题是由“进入区的各种操作不是原子的”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作步骤都成为一个原子操作就能避免问题。

wait、signal 原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为P(S)、V(S)

整形信号量

简而言之，就是使用整型变量作为信号量，用以表示系统中某种资源的数量。

在这里插入图片描述

记录型信号量

整型信号量的缺陷是存在“忙等”问题（自旋），因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

信号量实现进程的互斥
  1. 分析并发进程的关键活动，划定临界区(如:对临界资源打印机的访问就应放在临界区)
  2. 设置互斥信号量mutex，初值为1
  3. 在临界区之前执行P(mutex)
  4. 在临界区之后执行V(mutex)

注意:对不同的临界资源需要设置不同的互斥信号量。 P、V操作必须成对出现。 缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

在这里插入图片描述

信号量实现进程的同步
  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
  2. 设置同步信号量S,初始为0
  3. 在“前操作”之后执行V(S)
  4. 在“后操作”之前执行P(S)

在这里插入图片描述

具体实现

  • 若先执行到V(S)操作，则S++后S=1。之后当执行到P(S)操作时，由于S=1，表示有可用资源，会执行S–， S的值变回0，P2进程不会执行block原语，而是继续往下执行代码4。

  • 若先执行到P(S)操作，由于S=0，S– 后S=-1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码2，继而执行V(S)操作，S++， 使S变回0。由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了

    在这里插入图片描述

信号量机制实现进程的前驱关系（多个进程的同步）

进程P1中有句代码S1，P2中有句代码S2…P6中有句代码S6。这些代码要求按如下前驱图所 示的顺序来执行：其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)

因此：

  1. 要为每一对前驱关系各设置一个同步变量
  2. 在“前操作”之后对相应的同步变量执行V操作
  3. 在“后操作”之前对相应的同步变量执行P操作

在这里插入图片描述

管程

前面的信号量机制实现的进程同步与互斥，会使大量的同步操作分散在各个进程中，为了减少这一现象，我们就要引入——管程。

一个管程包含一个数据结构和能为并发进程所执行（在该操作系统上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程的组成
  • 一组局部变量
  • 对局部变量操作的一组过程
  • 对局部变量进行初始化的语句。
管程的特点
  • 局部数据变量只能被管程的过程访问，外部过程不可被访问
  • 一个进程通过调用管程的一个过程进入管程
  • 在任何时候都只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，等待管程变成可用的

条件变量

它是管程内部的一种同步机制。每个条件变量都表示一种等待原因，对应着一个等待队列。（这里这个等待队列中存的就是因为这个等待原因而阻塞的PCB

他可以执行wait和signal操作，并且应该置于wait和signal之前，就比如：x.wait, x.signal

  • Wait()
    • 将自己阻塞在等待队列中
    • 唤醒一个等待者或释放管程的互斥访问
  • Signal()
    • 将等待队列中的一个线程唤醒
    • 如果等待队列为空，则等同空操作

经典同步问题

生产者-消费者问题

单生产者-单消费者问题

问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区；消费者进程每次从临界缓冲区中取出一个产品并使用。生产者和消费者共享一个初始为空、大小为n的缓冲区。

  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
  • 只有缓冲区不空时，消费者才能从缓冲区中取出产品，否则必须等待。
  • 缓冲区是临界资源，各进程必须互斥的访问

问题分析

由于缓冲区是临界资源必须互斥使用，因此需要设置一个互斥信号量mutex，缓冲区有两种状态：进程正在访问和没有进程正在访问，因此可以给mutex赋初值为1。

缓冲区中的大小是生产者和消费者都可以进行操作的，当缓冲区满时，生产者要等待消费者取走产品，按一定次序访问这属于同步关系；当缓冲区空时，消费者要等待生产者生产产品，按一定次序访问这属于同步关系，因此需要设置两个同步信号量，full和empty;

1
2
3

Semaphore mutex = 1; //互斥信号量实现对缓冲区的互斥访问
Semaphore empty = n; //同步信号量，表示空闲缓冲区的数量，初值为有界缓冲区大小n
Semaphore full = 0;  //同步信号量，表示产品数量，也是非空缓冲区数量，初值为0

伪代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Producer(){
while (1)
  {
   生产一个产品; 
   P(empty);  //消耗一个空闲缓冲区,后操作前进行p操作
      P(mutex);
      把产品放入缓冲区; 
      V(mutex);
   V(full); //增加一个产品，前操作后进行v操作
  }
}

Consumer(){
while (1)
{
   P(full);  //消耗一个产品
      P(mutex);
      从缓冲区取出一个产品;
      V(mutex);
   V(empty); //增加一个空闲缓冲区，前操作后进行v操作
   使用产品;
  }
}

不能交换P操作顺序，否则会出现死锁

img

多生产者-多消费者问题

问题描述

桌子上有一个盘子，每次只能向其中放入一个水果。爸爸只向盘子中放苹果，妈妈只向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子为空时，爸爸妈妈才能往盘子里放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。

问题分析

盘子相当于一个初始为空，大小为1的缓冲区。爸爸妈妈分别可以看作生产者进程1、生产者进程2，儿子可以看作消费者进程1，女儿可以看作消费者进程2

互斥关系：(mutex = 1) 对缓冲区（盘子）的访问要互斥地进行

同步关系（一前一后）：

  • 父亲将苹果放入盘子后，女儿才能取苹果
  • 母亲将橘子放入盘子后，儿子才能取橘子
  • 只有盘子为空时，父亲或母亲才能放入水果

img

伪代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

semaphore mutex = 1;  //实现互斥访问盘子(缓冲区)
semaphore apple = 0;  //盘子中有几个苹果
semaphore orange = 0;  //盘子中有几个橘子
semaphore plate = 1;   //盘子中还可以放多少个水果
 
dad(){
   while(1){
  准备一个苹果;
  P(plate);
  P(mutex);
        把苹果放入盘子;
  V(mutex);
  V(apple);
     }
}
 
mom(){
   while(1){
  准备一个橘子;
  P(plate);
  P(mutex);
        把橘子放入盘子;
  V(mutex);
  V(orange);
     }
}
 
daughter(){
   while(1){
 
  P(apple);
  P(mutex);
        从盘子中取出苹果;
  V(mutex);
  V(plate);
  吃苹果
     }
}
 
son(){
   while(1){
  
  P(orange);
  P(mutex);
        从盘子中取出橘子;
  V(mutex);
  V(plate);
  吃掉橘子
     }
}

读者-写者问题

问题描述

有两组并发进程: 读者和写者,共享一组数据区。 读者/写者问题是指，保证一个写者进程必须与其他进程互斥访问共享对象的同步问题

  • 允许多个读者同时执行读操作
  • 不允许读者、写者同时操作
  • 不允许多个写者同时操作

问题分析

两类进程：写进程、读进程

互斥关系：写进程——写进程、写进程——读进程。读进程与读进程不存在互斥关系。

写进程和任何进程都要互斥，设置一个互斥信号量rw，在写者访问共享文件前后分别执行P、V操作，读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw进行P、V操作，但是如果所有读者进程在访问共享文件之前都进行P(rw)操作，那么会导致各个读进程之间也无法同时访问文件。该如何解决这个问题？

P(rw)和V(rw)其实就是对共享文件的加锁和解锁，既然各个读进程可以同时访问文件，而读进程和写进程需要互斥访问文件，那么就让第一个读进程对文件进行加锁，最后一个读进程对文件解锁，如何知道是还有几个读进程呢？就需要设置一个整形变量count来记录当前有几个读进程在在访问文件。

解决上述问题后，我们再来看这一种情况:

当两个读进程并发来访问文件时，有可能第一个进程还没来的及进行count++，第二个进程就就已经过了判断count是否为0的操作了，这个时候第二个进程也被阻塞在P(rw)，再次出现了上述问题，该如何解决？其实仔细分析可知道会出现这种情况在于对count的判断和赋值没办法保证一致性，即不是原语操作，为了解决这个问题我们要引入一个互斥信号量mutex来保证对count的判断和赋值是一个互斥的操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

semaphore rw = 1;  //用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件
int  count = 0;  // 记录当前有几个读进程在访问文件
semaphore mutex = 1;  //用于保证对count变量的互斥访问
 
writer(){
   while(1){
       P(rw); //写之前"加锁"
    	写文件
       V(rw);  //写之后"解锁"
     }
}

reader(){
  while(1){
    P(mutex);      //各进程互斥访问count
       if(count==0)
           P(rw);  //第一个读进程负责加锁
        count++;   //读进程+1
     V(mutex);    
        读文件
     P(mutex);        //各进程互斥访问count
    count--;          //访问文件的读进程数-1
    if(count == 0)     
    V(rw);            //最后一个读进程负责解锁
      V(mutex);
    }
}

在这个算法中，读进程是优先的，如果有一个读进程正在访问文件，这个时候来了一堆读进程和一个写进程，那么读进程一直在访问文件，写进程可能一直等待，发生”饿死“，如何解决这个问题？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

semaphore rw = 1;  //用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件
int  count = 0;  // 记录当前有几个读进程在访问文件
semaphore mutex = 1;  //用于保证对count变量的互斥访问
semaphore w = 1      // 实现写者优先
 
writer(){
   while(1){
       P(w);
       P(rw); //写之前"加锁"
    写文件
       V(rw);  //写之后"解锁"
       V(w);
 
     }
}
 
 
reader(){
  while(1){
    p(w);
    P(mutex);   //各进程互斥访问count
       if(count==0)
           P(rw);  //第一个读进程负责加锁
        count++;   //读进程+1
     V(mutex); 
    V(w);   
        读文件
     P(mutex);        //各进程互斥访问count
    count--;          // 访问文件的读进程数-1
    if(count == 0)     
    V(rw);             //最后一个读进程负责解锁
      V(mutex);
    }
}

加入互斥信号量w就可以解决写者饿死的问题了，当一个读者在读文件时此时w已经被解锁了，这个时候一个写者进程尝试访问文件，先对w进行加锁，然后阻塞在rw，此时读者进程再来就会被阻塞在w，等待写进程执行.

哲学家进餐问题

问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

五名哲学家相当于五个进程，每个进程只能访问“左右两边”的资源，且相邻的进程访问相同的资源，形成互斥关系。

  1. 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
  2. 整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
  3. 信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

伪代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

semaphore chopstick[5] = {1,1,1,1,1};
 
Philosopher i：
while (1)
{
    思考;
	P(chopstick[i]); // 拿左边的筷子
	P(chopstick[(i+1) % 5]); // 再拿右边的筷子
	进食;
	V(chopstick[i]); // 吃完后，放下左筷子
	V(chopstick[(i+1) % 5]);// 放下右筷子
}

这种解法会导致死锁，每个哲学家都拿一只筷子然后等待其他人放下筷子

为防止死锁发生还可采取的措施：

  1. 最多允许4个哲学家同时去拿左边的筷子；
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

Philosopher i：
while (1)
{
    思考;
    P(count); // 抢锁，直到第5个进程拿左筷子时阻塞
	P(chopstick[i]); // 拿左边的筷子
	P(chopstick[(i+1) % 5]); // 再拿右边的筷子
	进食;
	V(chopstick[i]); // 吃完后，放下左筷子
	V(chopstick[(i+1) % 5]);// 放下右筷子
	V(count);
}
  1. 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 记录型信号量法
semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;  //互斥的取筷子
             
Philosopher i：
    while (1)
   {
    思考;
    p(mutex);   
        P(chopstick[i]);          //取左
    	P(chopstick[(i+1) % 5]);  //取右
    V(mutex);
  	进餐;
    V(fchopstick[i]);          //放左
	V(chopstick[(i+1) % 5]);   //放右
                 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//AND信号量法
semaphore chopstick[5] = {1,1,1,1,1};
            
Philosopher i;
while (1)
{
    思考;
    Wait(chopstick[(i+1)%5]，chopstick[i]);
    进餐;          
    Signal(chopstick[(i+1) % 5],chopstick[i]);     
}
  1. 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

 // 记录型信号量法
semaphore chopstick[5] = {1,1,1,1,1};
         
Philosopher i：
        while (1)
   {
    思考;
    if(i % 2 == 1) {
         P(chopstick[i]);        //取左
         P(chopstick[(i+1) % 5]);  // 取右
    }else{
      P(chopstick[(i+1) % 5]);  // 取右
      P(chopstick[i]);        //取左  
    }
    进餐;
	V(chopstick[i]);    //放左
    V(chopstick[(i+1) % 5]);   // 放右     
}

如何处理死锁问题？

死锁概念

定义

所谓死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。

相似概念“饥饿”：在操作系统中，饥饿问题是指由于高优先级请求的不断涌入导致低优先级进程长时间被停滞，无法获得处理器或资源。通常情况下，当一个任务被无限期地推迟时，就会出现饥饿问题。

与死锁得区别在于：

  • 死锁发生后操作系统若不干预，那么陷入死锁的所有进程永远被阻塞；
  • 而饥饿发生，仅仅只是长时间没有被分配到处理机资源，但是还是有可能后面一段时间会被执行到，并没有永久阻塞。

死锁产生原因

  • 系统资源的竞争

    通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，多个进程在运行过程中会因争夺资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。

  • 进程推进顺序非法

    进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。信号量使用不当也会造成死锁。进程间相互等待对方发来的消息，结果也会造成某些进程间无法继续向前推进。

死锁产生得必要条件

产生死锁必须同时满足以下四个条件，只要其中任一个条件不成立，死锁就不会发生。

注意！！！

此处是必要条件，而非充要条件。四个条件都满足，但不一定发生死锁。

  • 互斥条件：进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占用。此时若有其他进程请求该资源，则请求进程只能等待。
  • 不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
  • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
  • 循环等待条件：存在一种进程资源的循环等待链，连中每一个进程已获得的资源同时被链中下一个进程所请求。

死锁处理策略

预防策略

所有进程运行起来之前采取的措施

破环互斥条件

方法

将只能互斥访问的资源改为同时共享访问，也就是将独占锁改为共享锁

注: 不是所有资源都能改成可共享的，某些资源无法通过这种方式达到解除死锁的目的

破坏不可剥夺条件

方法

请求新资源无法满足时，必须释放已有资源。由OS协助强制剥夺某进程持有的资源。

  • 实现复杂代价高
  • 此操作过多会导致原进程任务无法推进
破坏请求和保持条件

方法

  1. 进程开始运行时，一次性申请所有所需的资源，这样自身不会阻塞但是会：

    • 造成资源浪费
    • 其他进程会更加饥饿

  2. 阶段性请求和释放资源

    相较于前面一次性申请所有资源更好，每使用完一个资源，就释放它，可以避免长时间暂用而导致其他进程的饥饿问题

破坏循环等待条件

方法

避免出现资源申请环路，即对资源事先分类编号，按号分配。

  • 这种方式可以有效提高资源的利用率和系统吞吐量，但是增加了系统开销，增大了进程对资源的占用时间。
  • 对资源的编号应相对稳定，限制了新设备增加

避免策略

死锁避免：在使用前进行判断，只允许不会产生死锁的进程申请资源；

死锁避免是利用额外的检验信息，在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源。 两种避免办法：

  • 如果一个进程的请求会导致死锁，则不启动该进程
  • 如果一个进程的增加资源请求会导致死锁，则拒绝该申请。

img

银行家算法

避免死锁的具体实现通常利用银行家算法

银行家算法的实质就是**要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。**即没当进程提出资源请求且系统的资源能够满足该请求时，系统将判断满足此次资源请求后系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。

银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并假设系统拥有固定的资源总量。下面介绍银行家算法所用的主要的数据结构。

image-20230511143708450

img

img

死锁检测和解除

死锁检测

为了能对系统是否已发生了死锁进行检测，必须:

  • 用某种数据结构来保存资源的请求和分配信息:
  • 提供一种算法， 利用上述信息来检测系统是否已进入死锁状态。

在这里插入图片描述

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一 些阻塞的进程。

  • 如果按上述过程分析，最终能消除所有边， 就称这个图是可完全简化的。此时一定没有发生死锁(相当于能找到一个安全序列)

  • 如果最终不能消除所有边，那么此时就是发生了死锁。最终还连着边的那些进程就是处于死锁状态的进程。

死锁检测算法

  • 在资源分配图中，找出既不阻塞又不是孤点的进程Pi。即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如上图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源。消去它所有的请求边和分配边，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。

  • 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2 就满足这样的条件。根据中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的。

    在这里插入图片描述

死锁定理:如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁解除

一旦检测出死锁的发生，就应该立即解除死锁。

补充:并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要方法有:

  1. 资源剥夺法。挂起(新时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
  2. 撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源.这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
  3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。