提桶跑路笔记

408操作系统—2.进程与线程

  • 进程和线程

    • 进程的概念、特征和组成

      • 组成

        • 进程控制块
        • 程序段
        • 数据段

      • 特征

        • 动态性
        • 并发性
        • 独立性
        • 异步性

    • 进程的状态与转换

      • 运行态
      • 就绪态
      • 阻塞态
      • 创建态
      • 结束态
      • 状态转换

    • 进程控制

      • 创建
      • 终止
      • 阻塞
      • 唤醒

    • 进程的通信

      • 共享存储
      • 消息传递
      • 管道通信

    • 线程和多线程模型

      • 线程的概念和组成

      • 线程的实现方式

        • 用户级线程
        • 内核级线程

      • 多线程模型

        • 多对一模型
        • 一对一模型
        • 多对多模型

  • CPU调度

    • 调度的概念

      • 作业调度
      • 内存调度
      • 进程调度

    • 调度的实现

      • 调度程序

        • 排队器
        • 分派器
        • 上下文切换器

      • 调度的时机、切换和过程

        • 调度时机

        • 能否进行进程切换判断

        • 进程切换过程

        • 进程调度方式

          • 抢占调度
          • 非抢占调度

        • 闲逛进程

        • 线程调度

    • 调度的目标

      • CPU利用率

      • 系统吞吐量

      • 周转时间

        • 平均周转时间
        • 带权周转时间
        • 平均带权周转时间

      • 等待时间

      • 响应时间

    • 进程切换

      • 上下文切换

    • 典型调度算法

      • 先来先服务（FCFS）
      • 短作业优先（SJF）
      • 高响应比优先
      • 时间片轮转（RR）
      • 优先级调度
      • 多级反馈队列

  • 同步与互斥

    • 同步与互斥的基本概念

    • 实现临界区互斥的基本方法

      • 软件方法
      • 硬件方法

    • 互斥锁

    • 信号量

      • 整型信号量
      • 记录型信号量
      • 利用信号量实现进程互斥
      • 利用信号量实现前驱关系

    • 经典同步问题

    • 管程

  • 死锁

    • 死锁的概念
    • 死锁预防
    • 死锁避免
    • 死锁检测和解除

进程和线程

进程的概念

  • 定义

    • 是程序（进程实体）的一次执行运行过程
    • 是具有独立功能的程序在一个数据集合上运行的过程
    • 是系统进行资源分配和调度的一个独立单位

  • 特征

    1. 动态性

      进程具有一定生命周期，能够创建活动暂停终止，动态性是其最基本特征

    2. 并发性

      多个进程能够在一段时间内同时运行

    3. 独立性

      进程是独立运行、独立获得资源、独立接受调度的基本单位

    4. 异步性

      进程的执行不是严格按照程序指定的顺序进行的，但是程序可以独立地、不连续地执行，而且执行的速度不由指令本身决定，通常受整个系统中资源调度和分配的影响

  • 组成

    1. 进程控制块（Process Control Block,PCB）

      进程存在的唯一标志，在进程创建时新建 PCB，进程结束时删除 PCB

      • PCB 包含信息：

        1. 进程描述信息

          • 进程标识符 PID：每个进程都有一个唯一的标识符
          • 用户标识符 UID：标识进程归属的用户，用于保护和共享服务

        2. 进程控制和管理信息

          • 进程当前状态
          • 进程优先级

        3. 资源分配清单

          • 有关内存地址空间或虚拟地址空间的信息
          • 打开文件的列表和所使用的 I/O 设备信息

        4. CPU 相关信息

          • CPU 中各寄存器的值

      • 组织 PCB：

        • 链接方式

          统一状态的 PCB 链成队列，如就绪队列阻塞队列，也可以将阻塞态进程 PCB 依据原因排成多个阻塞队列

        • 索引方式

          统一状态的进程组织在索引表中，如就绪索引表、阻塞索引表

    2. 程序段

      能够被进程调度程序调度到 CPU 执行的程序代码段，多个进程可以运行同一个程序，即程序是对象，进程是对象的实例

    3. 数据段

      进程对应程序加工处理的原始数据

      程序执行时产生的中间或最终结果

进程的状态与转换

进程的状态

  1. 运行态 Running

    该时刻进程占用 CPU

  2. 就绪态 Ready

    进程获得了除 CPU 外的一切所需资源，一旦得到 CPU，就可以立即运行

  3. 阻塞态 Blocked

    该进程正在等待某一事件发生（等待资源分配或等待 I/O）而暂停运行，即使具备 CPU 资源也无法运行

  4. 创建态 New

    进程正在被创建时的状态

  5. 结束态 Exit

    进程正在从系统中消失时的状态

其中 1、2、3 为基本状态，除此以外还有：

  • 挂起态

    当系统资源紧张时，某些优先级较低的进程会被设为挂起状态，并移到内存之外。在一段时间内，这些进程不会被执行。当条件允许时，操作系统会将它们重新调回内存，使其进入等待被执行的状态

    • 阻塞挂起态

      进程在外存等待某事件出现

      进程在等待某些条件满足，例如等待 I/O 操作完成或其他事件发生

    • 就绪挂起态

      进程在外存，但已被分配资源，只要进入内存即可运行

      进程已经准备好运行，但由于某些原因（例如内存不足），暂时无法被调度执行

状态的转换

​image​

  • 就绪态–>运行态

    • 进程被调度，获得 CPU 资源（分派 CPU 时间片）

  • 运行态–>就绪态

    • 时间片用完
    • 高优先级程序进程就绪时，调度程序将正在执行的进程转为就绪

  • 运行态–>阻塞态

    主动行为，进程以系统调用的方式请求 OS 提供服务，或等待某一事件发生

    • 进程请求某一资源的使用和分配
    • 等待某一事件发生（I/O 操作的完成）

  • 阻塞态–>就绪态

    被动行为，需要其他相关进程发送唤醒语句

    • 中断结束或 I/O 操作结束

进程控制

操作系统中使用原语控制进程的创建、终止、阻塞、唤醒

进程创建

  • 引起事件

    • 用户登录系统

    • 作业调度

    • 系统提供服务

    • 用户程序应用请求

    • 父进程创建子进程

      子进程可以继承父进程的资源，被撤销时返还资源

      父进程撤销，子进程也被撤销

  • 创建进程的过程

    1. 申请空白 PCB
    2. 向 PCB 填写控制和管理进程的信息，如唯一标识
    3. 为该进程分配运行所需资源
    4. PCB 插入就绪队列，等待调度运行

进程终止

  • 引起事件

    • 正常结束

    • 异常结束

      程序运行时发生了异常事件无法继续运行

      存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O 故障等

    • 外界干预

      进程应外界请求终止运行

      如操作员或操作系统干预、父进程请求和父进程终止

    在 Linux 中父进程被终止，则子进程成为**孤儿进程**

  • 进程终止的过程

    1. 查找需要终止进程的 PCB
    2. 若处于执行状态则立刻终止，释放其 CPU 资源
    3. 若具有子进程，子进程交给 1 号进程（kernel_init）接管，避免孤儿进程
    4. 进程拥有的全部资源归还
    5. 将 PCB 由队列删除

进程阻塞

  • 引起事件

    进程必须等待某一事件完成时，可以主动调用​阻塞语句使自身阻塞等待，一旦被阻塞等待，只能由其他进程唤醒

    • 当进程需要等待某事件完成时
    • 请求系统资源失败
    • 新数据尚未到达，或没有新任务

  • 阻塞进程的过程

    1. 找到被阻塞进程标识号对应的 PCB
    2. 若处于运行态，则保护现场并将其转换为阻塞态
    3. 将 PCB 加入到阻塞队列中

进程唤醒

  • 引起事件

    进程等待的事件完成后，由其他进程发送消息唤醒该进程，进程不可能自我唤醒

    • 由于等待 I/O 设备阻塞时，需要由释放该 I/O 设备的进程发送唤醒语句唤醒
    • 由于等待数据阻塞时，由提供数据的进程发送唤醒语句唤醒
    • …

  • 唤醒进程的过程

    • 在阻塞队列中找到需唤醒队列的 PCB
    • 移出阻塞队列，由阻塞态转换为就绪态
    • 插入就绪队列，等待调度

进程的通信

指进程之间的信息交换，低级通信方式使用 PV 操作，高级通信方式主要有三类

共享存储

两个通信进程之间存在一块可以直接访问的共享空间

进程对共享空间读写时，需要使用同步互斥工具控制共享空间读写

  • 低级共享：基于数据结构的共享
  • 高级共享：基于存储区共享

操作系统为通信进程提供可共享使用的空间和同步互斥工具，数据交换指令由用户使用读写指令完成

消息传递

若不能使用共享存储，则必须利用操作系统提供的消息传递实现进程通信

进程间数据交互以格式化的消息为单位，进程通过发送消息和接收消息两个原语进行数据交换

  • 特点

    • 隐藏了通信实现细节，实现由操作系统完成
    • 不存在中间部分，通信过程对用户透明，简化了通讯程序的设计

微内核与服务器之间的通信即采用了消息传递机制

​image​

管道通信

  • 定义

    管道是一个特殊共享文件（pipe 文件），管道中的数据先进先出

    管道不满，写进程即可一直写入数据；管道非空，读进程即可一直读取数据

  • 管道机制必须提供的协调能力

    1. 互斥：当一个进程对管道进行读写时，其他进程必须等待

    2. 同步：

      • 写进程写入一定量数据到管道后，写进程阻塞，直到读进程读取数据后将写进程唤醒
      • 读进程将管道数据读空后，读进程阻塞，直到写进程写入数据到管道后将读进程唤醒
      • 即读写进程相互轮流阻塞与唤醒

    3. 确定对方的存在

  • 优点

    1. 管道大小有所限制

      管道文件是固定大小的缓冲区，Linux 中为 4KB。缓冲区满时，下一个写操作将被阻塞，等待读操作腾出足够的空间

    2. 读进程可以比写进程写入的数据读取的更多

      当缓冲区数据读取完还有读操作没执行完，下一个读操作将被阻塞，等待写操作写入数据

    3. 管道只能由创建进程访问，由于管道属于文件，子进程可以继承父进程的资源，因此子进程也可以继承父进程的管道

      • 继承之后的管道关系如何

  • 注意

    • 普通管道仅允许单向通讯，若需要两个进程双向通信，则需要定义两个管道

      ​image​

线程和多线程模型

线程的概念与特征

  • 线程

    • 进程中的一条执行流程，一个基本的 CPU 执行单元
    • 是进程的一个实体，是被独立调度和分派的基本单位
    • 线程自己不拥有系统资源，与同属一个进程的其他线程共享进程的资源
    • 同一进程中的多个线程可以并发执行且共享相同的地址空间
    • 线程可以创建和撤销另一个进程
    • 线程具有三种基本状态：就绪运行阻塞，状态转换与进程基本一致

  • 线程的组成

    由线程 ID、程序计数器、寄存器集合、堆栈组成

引入线程的目的是为了减少程序在并发执行时所付出的时空开销，提高系统并发性能

引入线程后，线程作为 CPU 的分配单元，而进程作为除 CPU 外的其他系统资源分配单元

若线程切换发生在一个进程内部，则时空开销比进程切换少，使得更多线程能够参与并发

线程与进程的比较

进程 线程
调度 无线程系统的基本调度单位，每次调度都进行上下文切换 独立调度基本单位，进程内调度开销小，进程外调度开销大
是什么的单位 资源分配的基本单位 调度的基本单位
资源 系统种拥有资源的基本单位 不拥有资源，共享所属进程的资源
独立性 独立的地址空间和资源，不允许其他进程访问
 同进程的不同线程共享进程的地址空间和资源
不同进程的线程不可见
系统开销 创建撤销进程需要分配或回收 PCB 及其他资源 线程切换只需要保存和设置少量寄存器内容
多处理器系统的支持 进程只能运行在一个 CPU 上 多线程进程可将进程的多个线程分配到多个 CPU 中，各线程同时占用不同的 CPU，可缩短进程的处理时间
  • 什么是上下文切换

线程的组织与控制

  • 线程控制块（PCB）

    与进程类似，每个线程都有一个线程控制块 TCB，用于记录控制和管理线程的信息

    1. 线程标识符

    2. 一组寄存器

      包括程序计数器、状态寄存器、通用寄存器

    3. 线程运行状态

    4. 优先级

    5. 线程专有存储区

      线程切换时用于保存现场

    6. 堆栈指针

      过程调用时保存局部变量及返回地址等

  • 线程创建

  • 线程终止

线程的实现方式

  • 用户级线程（User-Level Thread, ULT）

    • 定义：由用户级线程库函数完成整个进程的管理和调度

    • 模型：多对一模型

    • 优点：

      1. TCB 由用户线程库函数维护，可用于不支持线程技术的 OS
      2. 无需用户态和内核态的切换，速度快

    • 缺点：

      1. 一个线程阻塞，整个进程都被阻塞
      2. 多线程执行时，实际上是由多个线程按照用户调度程序分配一个时间片，执行慢
      3. 跨进程切换线程需要内核参与

    • 其他：

      实质上就是由用户自己模拟实现的多线程，一个进程中的多个线程按照用户编写的调度程序分配一个时间片，因此进程中每次只能有一个线程执行，线程执行阻塞命令则整个进程被阻塞

  • 内核级线程（Kernel—Level Thread，KLT）

    • 定义：线程对应的 TCB 放在 OS 中，线程的管理和调度由 OS 负责

    • 模型：一对一模型

    • 优点：

      1. 内核线程发起系统调用被阻塞，不会影响其他内核线程，内核可以调度该进程的其他线程占用 CPU
      2. 发挥多 CPU 的优势，内核能同时调度同一进程中的多个线程并行执行
      3. 内核本身也可以采用多线程技术，提高系统的执行速度和效率

    • 缺点：

      1. 同一进程的线程切换需要从用户态转到核心态，系统开销较大 因为用户进程的线程在用户态运行，线程调度和管理在内核态

  • 组合方式

    • 定义：内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程
    • 模型：多对多模型

​image​

多线程模型

多对一模型 一对一模型 多对多模型
定义 多个 ULT 映射到一个 KLT 每个 ULT 映射到一个 KLT n 个 ULT 映射到 m 个 KLT，n>=m
优点 线程管理在用户空间进行，效率高 一个线程被阻塞，内核调度另一个线程运行，并发能力强 1. 克服了多对一模型的并发度不高的缺点
2. 克服了一对一模型一个用户进程占用太多内核线程开销大的缺点
缺点 1. 一个线程阻塞，其他线程都被阻塞
2. 任何时刻只有一个线程能访问内核
3. 多个线程不能同时在多个处理机上运行		 每创建一个用户线程，就要创建一个对应的内核线程，开销大

​image​

CPU 调度

CPU 调度的基本概念和分类

  • 调度的基本概念

    1. 调度是处理机进行分配，即从就绪队列中按照公平高效原则的算法选择一个进程并将处理器分配，以实现进程的并发执行
    2. 调度是多道程序 os 的基础，是 os 设计的核心问题

  • 调度层次分类

    ​image​

    1. 高级调度/作业调度

      • 内存与外存的调度，从后备队列中调度作业
      • 每个作业只在后备队列中调入调出一次
      • 通常存在于多道批处理系统，用户提交的作业都存在外存中，由作业调度按算法调入内存
      • 其他系统通常不需要

    2. 中级调度/内存调度

      • 目的是提高内存运用率和系统吞吐量

      • 将暂时不能运行的进程调到外存等待，设为挂起态

        • 阻塞挂起态

          进程在外存等待某事件出现

          进程在等待某些条件满足，例如等待 I/O 操作完成或其他事件发生

        • 就绪挂起态

          进程在外存，但已被分配资源，只要进入内存即可运行

          进程已经准备好运行，但由于某些原因（例如内存不足），暂时无法被调度执行

      • 是存储器管理中的对换功能

    3. 低级调度/进程调度

      • 从就绪队列中选取一个进程进入 CPU 运行，使用频率很高
      • 各种 OS 都必须配置这种调度

  • 三种调度的联系

    1. 作业调度为进程活动做准备
    2. 内存调度将暂时不能运行的进程挂起，处于另外两个调度之间
    3. 进程调度使得进程正常活动
    4. 调用频率：作业调度 < 内存调度 < 进程调度
    5. 进程调度是基本的，不可或缺

调度的实现

调度程序

用于调度和分派 CPU 的组件称为调度程序，由三部分组成

  • 排队器

    按策略给就绪进程排出一个或多个队列

  • 分派器

    从就绪队列中取出进程并分配给 CPU

  • 上下文切换器

    对处理机进行切换时，会发生两对上下文的切换操作

    1. 第一对，将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行
    2. 第二对，移出分派程序的上下文，将新选进程的 CPU 现场信息装入 CPU 的各个相应寄存器

在上下文切换时，需要执行大量 load 和 store 指令，以保存寄存器的内容，因此会花费较多时间

通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可

​image​

调度的时机、切换与过程

  • 调度的时机

    进程由一个状态到另一个状态变化时，就会触发一次调度

    1. 创建新进程后
    2. 进程正常结束后或者异常终止后，必须从就绪队列选择一个进程运行，若无则运行一个系统提供的闲逛进程
    3. 进程因 I/O 请求、信号量操作或其他原因而被阻塞时，必须调度其他进程运行
    4. 当原先等待事件发生的进程由阻塞态变为就绪态，需要决定是让中断发生时运行的进程继续执行，还是让新就绪进程运行
    5. 高优先级进程进入就绪队列时

  • 进程的切换

    • 不能进行调度与切换的过程

      1. 处理中断的过程中
      2. 进程在 OS 内核临界区中
      3. 其他需要完全屏蔽中断的原语中

      若在上述过程中发生了引起调度的条件，需要置上请求调度标志，待过程结束再进行

    • 可以进行调度与切换的过程

      1. 发生引起调度条件且当前进程无法继续执行下去时

      2. 中断结束处理或自陷处理结束后，被置上请求调度标志

      3. 进程结束时

      4. 创建新进程后

      5. 系统调用完成并返回用户态时

      6. 进程处于临界区时，不破坏临界资源的使用规则时

        • 临界资源

          一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问的资源叫做临界资源

        • 临界区

          访问临界资源资源的那段代码

  • 进程切换的过程

    进程切换要求保存原进程在断点的现场信息，恢复被调度进程的现场信息

    1. 原进程的信息推入到当前进程的内核堆栈中保存现场信息，更新堆栈指针
    2. 内核从新进程的内核栈中装入新进程的信息
    3. 内核更新当前运行的进程空间指针，重设 PC 寄存器后开始运行新的进程

  • 进程调度方式

    1. 非抢占调度方式（非剥夺方式）

      • 优点：实现简单，系统开销小，适合批处理系统
      • 缺点：紧急任务无法优先执行，不适合分时和大多数实时系统

    2. 抢占调度方式（剥夺方式）

      • 优点：有利于提高系吞吐率和响应效率
      • 缺点：必须遵循一定的准则（如优先级，短进程优先，时间片原则）

  • 闲逛进程

    PID 为 0 的优先级最低的进程，没有其他进程就绪，该进程就一直运行

    闲逛进程不需要 CPU 以外的资源，不会被阻塞

  • 两种线程的调度

    1. 用户级线程调度

      线程调度由用户控制，在同一进程中调度

    2. 内核级线程调度

      内核选择一个线程运行，不考虑线程所属进程，调度需要完整的上下文切换

调度的目标

  1. $CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU等待时间}$

  2. 系统吞吐量：单位时间内 CPU 完成作业的数量

  3. 周转时间

    • 周转时间：作业提交到完成所花费时间的总和
    • 平均周转时间：多个作业周转时间的平均值
    • 带权周转时间：作业周转时间与作业实际运行时间的比值
    • 平均带权周转时间：多个作业带权周转时间的平均值

  4. 等待时间：进程处于等待 CPU 的时间之和（调度算法优劣评价指标）

  5. 响应时间：用户提交请求到系统首次产生响应所用的时间（交互式系统的重要评价指标）

调度的最终目标要考虑的因素：特定用户需求 + 系统整体效率 + 调度算法开销

进程切换

  • 上下文切换

    切换 CPU 到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。

    进程上下文采用进程 PCB 表示，包括 CPU 寄存器的值、进程状态和内存管理信息等

    当进行上下文切换时，内核将旧进程状态保存在其 PCB 中，然后加载经调度而要执行的新进程的上下文

  • 上下文切换的消耗

    消耗大量的 CPU 时间，纳秒级别

    通过提供多个寄存器组，可以简单改变寄存器组指针来简单切换上下文

典型调度算法

FCFS SJF 高响应比 RR 多级反馈队列
简述 先来先服务算法，即按队列模式调度
往往对多个相同优先级进程按 FCFS 处理		 - 短作业优先算法（SJF）
- 短进程优先算法（SPF）
- 若不做特别说明即默认非抢占式		 - 前两者的总和平衡
- 等待时间越长响应比越高，响应比越高越优先
 - 时间片轮转算法
- 按 FCFS 排好队列后依次分配时间片，用完即换
- 时间片过大时即为 FCFS
- 时间片过小则开销大

 RR 和 FCFS 的综合与发展
动态调整进程优先级和时间片大小
可抢占其他 × √ √ √ 队列内算法不一定
不可被其他抢占 √ √ √ × 队列内算法不一定
特点&优点 1.公平
2.实现简单
3.利于长作业
4.利于 CPU 繁忙作业
 1.平均等待时间最少
2.平均周转时间最少
2.效率最高
 1.兼顾长短作业
2.满足短作业优先且不发生饥饿现象		 1.兼顾长短作业
2.绝对可抢占		 1.兼顾长短作业
2.有较好的响应时间
3.可行性强
缺点 1.不利于短作业
2.不利于 IO 繁忙作业		 1.可能产生长时间饥饿现象，不利长作业
2.估计时间不易确定
3.不能保证紧迫作业及时处理
 1.计算响应比开销大 1.平均等待时间最长
2.上下文切换浪费时间		 -
适用于 - 1.作业调度
2.批处理系统		 - 1.分时系统
2.人机交互系统		 通用
默认决策方式 非抢占式 非抢占式 非抢占式 抢占式 抢占式
  • 什么是饥饿现象

$响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}$

优先级调度算法

依据高优先极进程能否抢占正在进行的进程，可将调度算法划分为两种

  • 非抢占式优先级调度算法

    高优先级进程就绪时，等待正在运行的进程中断或者执行完成，再调度高优先级进程

  • 抢占式优先级调度算法

    高优先级进程就绪时，立刻暂停正在运行的进程，调度高优先级进程运行

依据进程创建后优先级是否改变划分两种优先级

  • 静态优先级

    创建进程时确定，整个运行期间不变，由进程类型、对资源的要求、用户要求确定

    • 优点

      • 简单易行
      • 用户开销小

    • 缺点

      • 不够精确
      • 可能导致优先级低进程长期得不到调度

  • 动态优先级

    创建时赋予优先级，随进程推进或等待时间增加而改变

通常而言，系统进程 > 用户进程，交互进程 > 非交互进程，I/O 型进程 > 非 I/O 型进程

多级反馈队列调度算法

实现思想如下：

  1. 设置多个就绪队列，每个队列赋予不同优先级

    第 1 级队列的优先级最高，其余队列的优先级逐个降低

  2. 各队列的进程运行时间片的大小不同

    在优先级越高的队列中，每个进程的时间片就越小

  3. 每个队列都采用 FCFS 算法

    新进程进入内存后，首先将它放入第 1 级队列的末尾，按 FCFS 原则等待调度

    当轮到该进程执行时，如它能在该时间片内完成，便可撤离

    若它在一个时间片结束时尚未完成，调度程序将其转入第 2 级队列的末尾等待调度，以此类推

    当进程最后被降到第 n 级队列后，在第 n 级队列中便采用时间片轮转方式运行

  4. 按队列优先级调度

    仅当第 1 级队列为空时,才调度第 2 级队列中的进程运行，以此类推

    若 CPU 正在执行第 i 级队列中的某个进程时，又有新进程进入任何一个优先级较高的队列，此时须立即将正在运行的进程放回到第 i 级队列的**末尾**，而将 CPU 分配给新到的高优先级进程

同步与互斥

同步与互斥的基本概念

  • 同步

    直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系

  • 互斥

    间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源

  • 临界资源

    一次仅允许一个进程使用的资源，如物理设备（打印机），共享变量等

    临界资源的访问必须互斥

  • 共享资源

    可被多个进程同时使用的资源，如可重入代码/纯代码，共享程序段，磁盘，非共享数据

  • 临界区

    能够访问临界资源的代码

  • 遵循准则

    1.2.3.必要，4非必须

    1. 空闲让进

    2. 忙则等待

    3. 有限等待

      对请求访问的进程，应保证能在有限时间内进入临界区，防止无限等待

    4. 让权等待

      进程不能进入临界区时，应立即释放处理器

实现临界区互斥的基本方法

软件方法

设置一些标志标明是否有进程在临界区中，进程离开时修改

  1. 单标志法

    设置一个公共变量turn，变量值表示允许进入临界区的进程编号

    ​image​

    • 缺陷：在变量允许a进入时，若a不需要进入，则b始终无法进入，违背空闲让进准则，资源利用不充分

  2. 双标志先检查法

    设置两个布尔标志flag，标记进程进入临界区的意愿，重复检查对方的意愿直到对方不想进入临界区，将自身置为想进入，进入临界区

    ​image​

    • 缺陷：若在检查对方后，修改自己前，发生了进程切换，则双方都会检查通过，同时进入临界区，违背忙则等待原则

  3. 双标志后检查法

    先设置自己的意愿，再检查对方的意愿，若对方不想进入，则进入

    ​image​

    • 缺陷：可能在设置想要进入后发生进程切换，导致在检查标志时，两个进程同时想要进入，导致都无法进入，违背空闲让进，长期无法访问导致饥饿现象，违背有限等待

  4. Peterson算法

    结合1.3的思想，flag解决互斥访问，turn解决饥饿现象。

    若两个进程同时想要进入，则依据turn的最终值决定进入的进程

    ​image​

硬件方法

  1. 中断屏蔽方法

    屏蔽中断以保证当前进程能够让临界区代码顺利执行完毕

    • 缺点

      1. 限制CPU交替执行程序的能力，明显降低系统效率
      2. 若进程无法开中断，系统可能终止运行
      3. 不适用于多处理器

  2. 硬件指令方法

    所有操作都由硬件完成，以下仅为功能描述

    • TestAndSet指令

      简称TS指令，为原子操作，用于读出共享布尔变量lock​的值，后将该标志设置为真

      相比软件方法，TS指令为无法中断的原子操作，但仍然无法实现让权等待

    • Swap指令

      每个临界资源都有一个布尔变量lock​，每个进程都有一个布尔变量key​

      先使用key​变量记录lock​原值，将lock​置为true​，若key​为false则进入临界区

    • 优点

      1. 简单、容易验证
      2. 适用于任意数目进程，支持多处理器
      3. 支持多个临界区

    • 缺点

      1. 等待进入临界区的进程会保持while循环，无法让权等待
      2. 可能导致饥饿现象

互斥锁

互斥锁（mutex lock）是解决临界区最简单工具

布尔变量available​表示锁可用性

​acquire()​获得锁，release()​释放锁，必须为原子操作，常使用硬件机制实现

主要缺点为忙等待

信号量

只能被wait()——P()，signal()——V()访问，简称P操作和V操作

  1. 整型信号量

    定义一个表示资源数目的整型量S，仅有初始化，P，V三种操作

    ​image

    若S始终不满足要求，会循环测试，不满足让权等待

  2. 记录型信号量

    定义一个表示资源数目的整型量value，进程链表L

    若有进程需要等待该资源，则加入进程链表排队等待

    ​image​

    ​image​

    当资源量不满足要求的时候，进程会加入等待队列，然后阻塞自身让出CPU资源，防止忙等，遵循让权等待

    当S.value小于0，说明仍然存在进程等待该资源，让出一个资源则需要唤醒一个进程

  • 利用信号量实现两个进程互斥

    使信号量表示表示一个资源量为1的互斥资源，由于资源需要互斥，所以初始值为1

    • 为1时表示没有进入临界区的资源
    • 为0时表示只有一个进程在使用临界区，没有进程在等待
    • 为-1时表示一个进程正在等待临界区而被阻塞

    这样便保证了两个进程不会同时访问某个临界资源

    • 注意

      1. 不同临界资源需要不同的互斥信号量
      2. 有多少资源初始值就是多少
      3. PV操作必须成对出现

  • 利用信号量实现两个进程同步

    进程同步需要两个进程有​次序​的相互配合推进

    设进程P1，进程P2，进程P1需要早于进程P2运行，设同步信号量，初值为0

    ​​

    若P2先运行，P操作执行发现信号量不足，阻塞直到P1运行V操作增加信号量

    若P1先运行，则P2也能顺利运行

  • 利用信号量实现前驱关系

    信号量也可用来描述程序或语句之间的前驱关系，每对前驱关系都是一个同步问题，为每对前驱关系设置一个同步信号量，初始值均为0，例如为保证S1→S2,S1→S3,S2→S4,S2→S5,S3→S6,S4→S6,S5→S6,需要分别设置同步信号量 a12，a13，a24，a25，a36，a46，a56

  • 分析进程同步与互斥问题的方法步骤

    1. 关系分析。找出问题中的进程数，并分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照例子中的经典范式改写
    2. 整理思路。找出解决问题的关键点，根据进程的操作流程确定P操作、V 操作的大致顺序
    3. 设置信号量。根据上面的两步，设置需要的信号量，确定初值，完善整理

信号量也是一种低级的进程通信语言

（待编辑）经典同步问题

管程

  • 管程定义

    管程定义了**共享数据结构和各种进程在该数据结构上的全部操作**，使得对共享资源的操作全部封装，防止单独实现同步时操作不当导致死锁，同时支持进程互斥和同步

    类似于面向对象编程思想

  • 管程组成

    1. 管程的名称
    2. 管程内部的共享数据结构或共享变量
    3. 对内部数据结构的操作函数或过程
    4. 对内部数据结构进行初始化的语句

  • 管程中设置的条件变量

    若进程进入管程后被阻塞，若不释放管程则其他进程在其阻塞解除前无法进入，因此将阻塞原因定义为**条件变量（condition）**

    由于阻塞原因多样，因此条件变量多个，每个条件变量保存一个等待队列

    定义条件变量x

    • x.wait()

      x条件不满足时，调用其，将自身插入x条件的阻塞队列，释放管程

    • x.signal()

      x对应条件发生变化，唤醒一个因x条件阻塞的进程，加入就绪队列中

    • 与信号量的相似点

      类似于PV操作，可以实现进程的阻塞、唤醒

    • 与信号量的不同点

      条件变量没有值，仅实现排队等待，管程中使用共享数据记录剩余资源数目

      信号量有值，信号量的值反映剩余资源数目

死锁

死锁概念

  • 死锁

    指多个进程因竞争资源而造成的一种僵局(互相等待对方手里的资源)，使得各个进程都被阻塞，若无外力干涉，则都无法推进

  • 死锁产生的充分条件

    每种资源只有一个，且资源请求出现了环路

    例如a占用打印机，b占用输入设备，此时a请求输入设备，b请求打印机，则ab进程将陷入死锁

  • 死锁产生的必要条件​

    1. 互斥条件

      多个线程不能同时使用同一个资源

    2. 不可剥夺条件

      进程使用资源结束前不能被其他进程获取

    3. 请求并保持条件

      进程持有资源1并请求被占用的资源2时，资源1不会被释放

    4. 循环等待条件

      两个线程获取资源的顺序构成环形链

  • 死锁产生的原因

    1. 系统资源的竞争

      系统拥有的不可剥夺资源不足以满足多进程运行需要

      只有对不可剥夺资源的竞争才可能产生死锁，可剥夺资源则不会

    2. 进程推进顺序非法

      请求和释放资源的顺序不当，以及信号量使用不当

  • 饥饿现象

    指进程在信号量内无穷等待

    • 产生原因

      资源分配时策略不公平，导致进程等待某种资源（可以是CPU）过久以至于给进程推进带来明显影响

  • 死锁与饥饿比较

    • 共同点

      1. 进程无法顺利向前推进的现象

    • 不同点

      1. 可以只有一个进程发生饥饿；死锁一定是两个以上的进程
      2. 饥饿进程可能处于就绪态，也可能处于阻塞态；死锁必然处于阻塞态

  • 死锁的处理策略

    1. 死锁预防
    2. 避免死锁
    3. 死锁的检测及解除

死锁预防

通过破坏死锁产生的四个必要条件之一预防死锁发生

  1. 破坏互斥条件

    将互斥资源改造为允许共享的资源

    通常不太可行，且为了系统安全必须保护某些互斥性

  2. 破坏不可剥夺条件

    当请求不到新的资源时，使进程必须释放保持的所有资源

    实现复杂。常用于状态易于保存和恢复的资源，如 CPU 的寄存器及内存资源

    容易增加系统开销，进而降低系统吞吐量

  3. 破坏请求并保持条件

    1. 采用预先静态分配法，即一次性获取所有资源

      实现简单，但容易严重浪费系统资源，容易导致饥饿现象

    2. 运行进程只获得运行初期所需的资源便可以开始运行，在运行过程中逐步释放使用完毕的资源，并获得剩余所需

  4. 破坏循环等待条件

    采用顺序资源分配法

（待编辑）死锁避免

死锁检测和解除

  • 资源分配图

    一个有向图，表示某时刻系统资源与进程之间的状态

    圆圈代表进程，框代表一类资源，进程->资源叫做请求边，资源->进程叫分配边

    ​image​

    资源点的出度表示已分配资源数量，当资源点数量大于等于资源点出度时表示存在剩余资源

  • 死锁定理

    S为死锁的条件是，当且仅当S状态的资源分配图是不可完全简化的

  • 死锁解除

    1. 资源剥夺法

      挂起死锁进程，抢占其资源，但应防止被挂起进程长时间得不到资源

    2. 撤销进程法

      强制撤销部分或全部死锁进程并剥夺资源，实现简单但代价可能很大

    3. 进程回退法

      让死锁进程回退到足以回避死锁的地步，回退时进程自愿释放资源

      方法要求系统保持进程的历史信息，设置还原点