操作系统(2)：处理机管理

这是《操作系统》课程的课程笔记系列。本文整理部分为“第2章：处理机管理”。

2.1 进程与线程

2.1.1 进程的概念和特征

• 进程的概念：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
  • 程序：是静态的，是存储的可执行文件，即一系列的指令集合
  • 进程：是动态的，是程序的一次执行过程
  • 进程实体（进程映像）：是静态的，由 PCB、程序段、数据段组成，反映了进程在某一时刻的状态
• 进程的特征：
  • 动态性：是最基本的特征，进程是程序的一次执行过程，是动态地产生、变化和消亡的
  • 并发性：内存中有多个进程实体，各进程可并发执行
  • 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
  • 异步性：各进程按各自独立的、不可预知的速度向前推进，可能导致运行结果的不确定性
  • 结构性：每个进程都会配置一个 PCB

2.1.2 进程的组成

• 进程控制块（PCB）：是进程存在的唯一标志，包含操作系统对进程管理所需的信息
  • 进程描述信息：
    • 进程标识符（PID）
    • 用户标识符（UID）
  • 进程控制和管理信息：
    • CPU、磁盘、网络流量使用情况统计等
    • 进程当前状态：就绪态 / 阻塞态 / 运行态等
  • 资源分配清单：
    • 正在使用哪些文件
    • 正在使用哪些内存区域
    • 正在使用哪些 I/O 设备
  • 处理机相关信息：如 PSW、PC 等寄存器的值（用于实现进程切换）
• 程序段：程序的代码（指令序列）
• 数据段：运行过程中产生的各种数据（如程序中定义的变量）

2.1.3 进程的状态与转换

• 进程的五种状态：
  • 运行态：占有 CPU，并在 CPU 上运行
    • 有 CPU 资源，有其他所需资源
  • 就绪态：已具备运行条件，但由于没有空闲 CPU，暂时不能运行
    • 无 CPU 资源，有其他所需资源
  • 阻塞态：因等待某一事件而暂时不能运行
    • 无 CPU 资源，无其他所需资源
  • 创建态：进程正在被创建，操作系统为进程分配资源、初始化 PCB
  • 终止态：进程正在从系统中撤销，操作系统回收进程拥有的资源、撤销 PCB
• 进程状态的转换：
  • 就绪态 --> 运行态：进程被调度
  • 运行态 --> 就绪态：时间片到，或 CPU 被其他高优先级的进程抢占
  • 运行态 --> 阻塞态：等待系统资源分配，或等待某事件发生（主动行为）
  • 阻塞态 --> 就绪态：资源分配到位，等待的事件发生（被动行为）
  • 创建态 --> 就绪态：系统完成创建进程相关的工作
  • 运行态 --> 终止态：进程运行结束，或运行过程中遇到不可修复的错误

  graph LR;
  A(创建态) -- 创建 --> B(就绪态);
  B -- 调度 --> C(运行态);
  C -- 时间到 --> B;
  C -- 退出 --> D(终止态);
  C -- 事件等待 --> E(阻塞态);
  E -- 事件发生 --> B;
  

• 进程的组织方式：
  • 链接方式：
    • 按照进程状态将 PCB 分为多个队列
    • 操作系统持有指向各个队列的指针
  • 索引方式：
    • 根据进程状态的不同，建立几张索引表
    • 操作系统持有指向各个索引表的指针

2.1.4 进程控制

• 进程控制：实现进程状态的转换
• 实现方式：用原语实现
  • 原语是一种特殊的程序
  • 原语的执行必须一气呵成，不可中断
  • 原语用关中断和开中断来实现
• 相关原语：
  • 进程的创建：
    • 创建原语：无 --> 创建态 --> 就绪态
      • 申请空白 PCB
      • 为新进程分配所需资源
      • 初始化 PCB
      • 将 PCB 插入就绪队列
    • 引起进程创建的事件：用户登录、作业调度、提供服务、应用请求
  • 进程的终止：
    • 撤销原语：就绪态 / 阻塞态 / 运行态 --> 终止态 --> 无
      • 从 PCB 集合中找到终止进程的 PCB
      • 若进程正在运行，立即剥夺 CPU，将 CPU 分配给其他进程
      • 终止其所有子进程
      • 将该进程拥有的所有资源归还给父进程或操作系统
      • 删除 PCB
    • 引起进程终止的事件：正常结束、异常结束、外界干预
  • 进程的阻塞：
    • 阻塞原语：运行态 --> 阻塞态
      • 找到要阻塞的进程对应的 PCB
      • 保护进程运行现场，将 PCB 状态信息设置为阻塞态，暂停进程运行
      • 将 PCB 插入相应事件的等待队列
    • 引起进程阻塞的事件：
      • 需要系统分配某种资源
      • 需要等待相互合作的其他进程完成工作
  • 进程的唤醒：
    • 唤醒原语：阻塞态 --> 就绪态
      • 在事件等待队列中找到 PCB
      • 将 PCB 从等待队列移除，设置进程为就绪态
      • 将 PCB 插入就绪队列，等待被调度
    • 引起进程唤醒的事件：等待的事件发生
  • 进程的切换：
    • 切换原语：运行态 --> 阻塞态 / 就绪态，就绪态 --> 运行态
      • 将运行环境信息存入 PCB
      • PCB 移入相应队列
      • 选择另一个进程执行，并更新其 PCB
      • 根据 PCB 恢复新进程所需的运行环境
    • 引起进程切换的事件：
      • 当前进程时间片到
      • 有更高优先级的进程到达
      • 当前进程主动阻塞
      • 当前进程终止

总结：控制原语要做的三类操作：

1. 更新 PCB 中的信息（修改进程状态、保存 / 恢复运行环境）
2. 将 PCB 插入合适的队列
3. 分配 / 回收资源

2.1.5 进程的通信

• 共享存储：
  • 设置一个共享内存区域，并映射到进程的虚拟地址空间
  • 要互斥地访问共享空间（通信进程负责实现，使用内核提供的同步互斥工具）
  • 两种方式：基于数据结构的共享（低级）、基于存储区的共享（高级）
• 消息传递：
  • 传递结构化的消息（包含消息头和消息体）
  • 系统提供发送 / 接收原语
  • 两种方式：
    • 直接通信方式：发送进程指明接收进程的 ID，消息直接挂到接接收进程的消息队列中
    • 间接通信方式：以“信箱”作为中间体进行消息传递
• 管道通信：
  • 设置一个特殊的共享文件（管道，本质上是一片内存缓冲区）
  • 一个管道只能实现半双工通信，实现双向同时通信要建立两个管道
  • 各进程要互斥访问管道（由操作系统负责实现互斥）
  • 管道写满时，写进程阻塞；管道读空时，读进程阻塞
• 信号：
  • 作用：用于通知进程某个特性事件发生（实现简单的进程间通信）
    • 也常作为异常处理的一种配套机制
  • 信号的发送：
    • 可以由一个进程给另一个进程发送信号
    • 可以由操作系统内核给进程发送信号
    • 一个进程也可以给自己发送信号
  • 信号的保存：在每个进程的 PCB 中，用两个 n bit 位向量表示待处理信号、被阻塞信号
  • 信号的处理：
    • 处理时机：当进程从内核态转为用户态时，例行检查是否有待处理信号，如果有，即处理信号
    • 如何处理：
      • 执行默认的信号处理程序：操作系统内核对每一种信号都有默认的处理程序
      • 执行用户定义的信号处理程序：允许进程通过系统调用，自定义某些信号的处理程序，覆盖操作系统的默认处理
  • 特点：
    • 不同的操作系统，对信号类型的定义各不相同
    • 重复收到的同类信号，将被简单地丢弃
    • 有些信号既不能被用户自定义处理函数，也不能被阻塞

2.1.6 线程和多线程模型

• 线程：是基本的 CPU 执行单元，也是程序执行流的最小单位
• 线程机制的作用：
  • 资源分配、调度：
    • 传统进程机制中，进程是资源分配、调度的基本单位
    • 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
  • 并发性：
    • 传统进程机制中，只能进程间并发
    • 引入线程后，各线程间也能并发，提升了并发度
  • 系统开销：
    • 传统的进程间并发，需要切换进程的运行环境，系统开销很大
    • 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
    • 引入线程后，并发所带来的系统开销减小
• 线程的属性：
  • 线程是处理机调度的单位
  • 多 CPU 计算机中，各个线程可占用不同的 CPU
  • 每个线程都有一个线程 ID、线程控制块（TCB）
  • 线程也有就绪、阻塞、运行三种基本状态
  • 线程几乎不拥有系统资源，同一进程的不同线程间共享进程的资源
  • 由于共享内存地址空间，同一进程中的线程间通信无需系统干预
  • 同一进程中的线程切换，不会引起进程切换；不同进程中的线程切换，会引起进程切换
  • 切换同进程内的线程，系统开销很小；切换进程，系统开销较大
• 线程的实现方式：
  • 用户级线程：从用户视角能看到的线程，由线程库实现
  • 内核级线程：从操作系统视角看到的线程，由操作系统实现
    • 内核级线程是处理机分配的单位
  • 组合方式：上述两种方式的组合
• 多线程模型：
  • 一对一模型：一个用户级线程映射到一个内核级线程
    • 优点：各个线程可分配到多核处理机并行执行，并发度高
    • 缺点：线程管理都需要操作系统支持，开销大
  • 多对一模型：多个用户级线程映射到一个内核级线程
    • 优点：线程管理开销小，效率高
    • 缺点：一个线程阻塞会导致整个进程都被阻塞，并发度低
  • 多对多模型：$n$ 个用户级线程映射到 $m$ 个内核级线程（$n \ge m$）
    • 融合了两者的优点
• 线程的状态与转换：与进程的就绪态、运行态、阻塞态的转换一致
• 线程的组织与控制：
  • 线程控制块（TCB）：每个线程对应一个 TCB
    • 线程标识符：TID，与 PID 类似
    • 运行环境：程序计数器 PC、其他寄存器、堆栈指针
    • 线程运行状态：运行态 / 就绪态 / 阻塞态
    • 优先级：线程调度、资源分配的参考
  • 线程表：多个 TCB 可组织成一张线程表

2.2 CPU 调度

2.2.1 调度的概念

• 调度的概念：按某种算法选择一个进程将处理机分配给它
• 调度的层次：
  • 高级调度（作业调度）：按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
  • 中级调度（内存调度）：按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
    • 挂起状态：暂时调到外存等待的进程状态，分为就绪挂起和阻塞挂起
  • 低级调度（进程调度）：按照某种规则，从就绪队列中选择一个进程为其分配处理机

graph LR;
A --> F(就绪挂起);
A(创建态) -- 创建 --> B(就绪态);
B -- 调度 --> C(运行态);
C -- 时间到 --> B;
C -- 退出 --> D(终止态);
C -- 事件等待 --> E(阻塞态);
E -- 事件发生 --> B;
B -- 挂起 --> F;
E -- 挂起 --> G;
G -- 激活 --> E;
G(阻塞挂起) -- 事件出现 --> F;
F -- 激活 --> B;
C --> F;

	调度发生的位置	发生频率	对进程状态的影响
高级调度	外存 --> 内存 （面向作业）	最低	无 --> 创建态 --> 就绪态
中级调度	外存 --> 内存 （面向进程）	中等	挂起态 --> 就绪态
低级调度	内存 --> CPU	最高	就绪态 --> 运行态

2.2.2 调度的实现

• 调度器（调度程序）：用于调度和分派处理机的组件，能使进程在就绪态和运行态之间转换

  • 决定：
    • 让谁运行：调度算法
    • 运行多久：时间片大小
  • 触发时机：即调度时机
    • 创建新进程
    • 进程退出
    • 运行进程阻塞
    • I/O 中断发生（唤醒某些阻塞进程）
  • 调度方式：
    • 非抢占式调度：只有运行进程阻塞或退出才触发调度程序工作
    • 抢占式调度：每个时钟中断或 k 个时钟中断会触发调度程序工作

• 调度的时机：

  • 需要进程调度的情况：
    • 主动放弃：
      • 进程正常终止
      • 运行过程中发生异常而终止
      • 主动阻塞（如等待 I/O）
    • 被动放弃：
      • 分给进程的时间片用完
      • 有更紧急的事情需要处理（如 I/O 中断）
      • 有更高优先级的进程进入就绪队列
  • 不能进行进程调度的情况：
    • 在处理中断的过程中
    • 进程在操作系统内核程序临界区中
    • 原子操作过程中（原语）

补充：

• 临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源
• 临界区：访问临界资源的代码段
• 内核程序临界区：一般用来访问某种内核数据结构，如进程的就绪队列
• 进程在操作系统内核程序临界区中不能进行调度和切换，因为其访问的临界资源可能影响到操作系统内核的其他管理工作，但在普通临界区中可以进行调度和切换

• 进程调度的方式：

  • 非剥夺调度方式（非抢占式）：只能由当前运行的进程主动放弃 CPU
  • 剥夺调度方式（抢占式）：可由操作系统剥夺当前进程的 CPU 使用权

• 闲逛进程：没有其他就绪进程时，运行闲逛进程

  • 优先级最低
  • 可以是零地址指令，指令周期末尾例行检查中断
  • 能耗低

• 调度的对象：

  • 不支持内核级线程：调度的对象是进程
  • 支持内核级线程：调度的对象是内核线程

2.2.3 调度的目标

1. CPU 利用率：

$$\text{利用率} = \frac{\text{有效工作时间}}{\text{有效工作时间} + \text{空闲等待时间}}$$

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

$$\text{系统吞吐量} = \frac{\text{总共完成了多少道作业}}{\text{总共花了多少时间}}$$

3. 周转时间：从作业提交到作业完成所经历的时间

   $$\text{周转时间} = \text{作业完成时间} - \text{作业提交时间}$$

   • 平均周转时间：多个作业周转时间的平均值

   $$\text{平均周转时间} = \frac{\text{各作业周转时间之和}}{\text{作业数}}$$

   • 带权周转时间：作业周转时间与作业实际运行时间的比值

   $$\text{带权周转时间} = \frac{\text{作业周转时间}}{\text{作业实际运行时间}}$$

   • 平均带权周转时间：多个作业带权周转时间的平均值

   $$\text{平均带权周转时间} = \frac{\text{各作业带权周转时间之和}}{\text{作业数}}$$

4. 等待时间：进程或作业等待被 CPU 服务的时间之和
   • 等待时间不包括等待 I/O 完成的时间
   • 平均等待时间：各个进程或作业等待时间的平均值
5. 响应时间：从用户提交到首次产生响应所用的时间

2.2.4 进程切换

• 切换和调度：
  • 狭义的进程调度：指从就绪队列中选中一个要运行的进程（刚刚被暂停的进程或另一个进程）
  • 进程切换：指一个进程让出处理机，由另一个进程占用处理机的过程
  • 广义的进程调度：包含了选择一个进程和进程切换两个步骤
• 进程切换的过程：
  1. 对原来运行进程各种数据的保存
  2. 对新的进程各种数据的恢复
  • 结论：进程调度和切换是有代价的，并不是调度越频繁，并发度就越高

2.2.5 CPU 调度算法

1. 先来先服务（FCFS, First Come First Service）

• 算法思想：从公平的角度考虑
• 算法规则：按作业或进程到达的先后顺序进行服务
• 调度层次：
  • 用于作业调度：考虑哪个作业先到达后备队列
  • 用于进程调度：考虑哪个进程先到达就绪队列
• 调度方式：非抢占式
• 优点：公平、算法实现简单
• 缺点：排在长作业后面的短作业等待时间长，带权周转时间大
  • 对长作业有利，对短作业不利
• 是否会导致饥饿：不会
  • 饥饿：进程或作业长期得不到服务

2. 短作业优先（SJF, Shortest Job First）

• 算法思想：追求最少的平均等待时间、平均周转时间、平均带权周转时间
• 算法规则：（服务时间）最短的作业或进程优先得到服务
• 调度层次：可用于作业调度及进程调度（短进程优先，SPF）
• 调度方式：非抢占式，但也有抢占式版本（最短剩余时间优先，SRTN）
  • 最短剩余时间优先：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列
  • 最短剩余时间优先算法的平均等待时间、平均周转时间最少
• 优点：最短的平均等待时间、平均周转时间（所有进程几乎同时到达时）
• 缺点：不公平
  • 对短作业有利，对长作业不利，可能产生饥饿现象
  • 作业或进程的运行时间由用户提供，不一定真实
• 是否会导致饥饿：会，如果源源不断地有短作业到来，可能使长作业长时间得不到服务

3. 高响应比优先（HRRN, Highest Response Ratio Next）

• 算法思想：要综合考虑作业或进程的等待时间和要求服务的时间
• 算法规则：在每次调度时先计算各个作业或进程的响应比，选择响应比最高的作业或进程为其服务

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

• 调度层次：既可用于作业调度，也可用于进程调度
• 调度方式：非抢占式，只有当前运行的作业或进程主动放弃处理机时，才需要调度
• 优点：
  • 综合考虑了等待时间和运行时间（要求服务时间）
    • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
    • 要求服务时间相同时，等待时间长的优先（FCFS 的优点〉
  • 对于长作业，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
• 是否会导致饥饿：不会

4. 优先级

• 算法思想：随着实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
• 算法规则：每个作业或进程有各自的优先级，调度时选择优先级最高的作业或进程
• 调度层次：既可用于作业调度，也可用于进程调度
• 调度方式：抢占式和非抢占式都有
  • 非抢占式：只在进程主动放弃处理机时进行调度
  • 抢占式：还要在就绪队列变化时，检查是否会发生抢占
• 优点：
  • 用优先级区分紧急程度、重要程度，适用于实时操作系统
  • 可灵活地调整对各种作业或进程的偏好程度
• 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
• 是否会导致饥饿：会
• 优先级的分类：
  • 静态优先级：创建进程时确定，之后一直不变
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级
    • 优先级调整策略：可以从追求公平、提升资源利用率等角度考虑
• 优先级的设置：
  • 系统进程优先级高于用户进程
  • 前台进程优先级高于后台进程
  • I/O 型进程优先级高于计算型进程
    • I/O 设备和 CPU 可以并行工作
    • 可以使得 I/O 设备尽早投入工作
    • 资源利用率、系统吞吐量都会得到提升

5. 时间片轮转（RR, Round-Robin）

• 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
• 算法规则：
  • 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片
  • 若进程未在一个时间片内执行完，则到夺处理机，将进程重新放到就绪队列队尾重新排队
• 调度层次：用于进程调度
  • 只有作业放入内存建立了相应的进程后，才能被分配处理机时间片
• 调度方式：抢占式，由时钟装置发出时钟中断来通知 CPU 时间片已到
• 优点：公平；响应快，适用于分时操作系统
• 缺点：高频率的进程切换有一定开销：不区分任务的紧急程度
• 是否会导致饥饿：不会
• 时间片大小的影响：
  • 时间片太大：退化为先来先服务调度算法，并且会增大进程响应时间
  • 时间片太小：导致进程切换过于频繁，实际用于进程执行的时间比例减少

6. 多级队列

• 算法规则：
  • 系统中按进程类型设置多个队列，进程创建成功后插入某个队列
  • 队列之间可采取固定优先级，或时间片划分
    • 固定优先级：高优先级空时，低优先级进程才能被调度
  • 各队列可采用不同的调度策略

7. 多级反馈队列

• 算法思想：对其他调度算法的折中权衡
• 算法规则：
  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  2. 新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时片，若用完时间片进程还未结束，则进程进入下一级队列队尾；如果此时已经是在最下级的队列，则重新放回该队列队尾
  3. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
• 调度层次：用于进程调度
• 调度方式：抢占式
  • 在 k 级队列的进程运行过程中，若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
• 优点：
  • 对各类型进程相对公平（FCFS 的优点）
  • 每个新到达的进程都可以很快就得到响应（RR 的优点）
  • 短进程只用较少的时间就可完成（SPF 的优点）
  • 不必实现估计进程的运行时间（避免用户作假）
  • 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程
    • 可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级
• 是否会导致饥饿：会

2.2.6 多处理机调度

• 调度目标：
  • 负载均衡：尽可能让每个 CPU 都同等忙碌
  • 处理机亲和性：尽量让一个进程调度到同一个 CPU 上运行，以发挥 CPU 中 Cache 的作用
• 公共就绪队列：
  • 调度规则：所有 CPU 共享同一个就绪进程队列，每个 CPU 运行调度程序，从公共就绪队列中选择一个进程运行
    • 每个 CPU 访问公共就绪队列时需要上锁，确保互斥
  • 优点：可以天然地实现负载均衡
  • 缺点：各个进程可能会频察地换 CPU 运行，亲和性不好
  • 提升处理机亲和性：
    • 软亲和：由进程调度程序尽量保证亲和性
    • 硬亲和：由用户进程通过系统调用，主动要求操作系统分配固定的 CPU，确保亲和性
• 私有就绪队列：
  • 调度规则：每个 CPU 有一个私有的就绪进程队列，每个 CPU 运行调度程序，从私有就绪队列中选择一个进程运行
  • 优点：可以天然地实现处理机亲和性
  • 实现负载均衡：
    • 推迁移：一个特定的系统程序周期性检查每个处理器的负载，如果负载不平衡，就从忙碌 CPU 的就绪队列中“推”一些就绪进程到空闲 CPU 的就绪队列
    • 拉迁移：每个 CPU 运行调度程序时，周期性检查自身负载与其他 CPU 负载。如果一个 CPU 负载很低，就从其他高负载 CPU 的就绪队列中“拉”一些就绪进程到自己的就绪队列

2.3 同步与互斥

2.3.1 同步与互斥的基本概念

• 进程同步：直接制约关系
  • 并发性带来了异步性，有时需要通过进程同步解决这种异步问题
  • 有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序
• 进程互斥：间接制约关系
  • 对临界资源的访问，需要互斥地进行，即同一时间段内只能允许一个进程访问该资源
  • 临界资源访问的过程：
    • 进入区：检查是否可进入临界区，若可进入，需要上锁
    • 临界区：访问临界资源的那段代码
    • 退出区：负责解锁
    • 剩余区：其余代码部分
  • 遵循的原则：
    • 空闲让进：临界区空闲时，应允许一个进程访问
    • 忙则等待：临界区正在被访问时，其他试图访问的进程需要等待
    • 有限等待：要在有限时间内进入临界区，保证不会饥饿
    • 让权等待：进不了临界区的进程，要释放处理机，防止盲等

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

1. 软件实现方法

1. 单标志法

• 算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程
  • 即每个进程进入临界区的权限只能被另一个进程赋予
  • 总结：在进入区只做“检查”，不“上锁”

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

// P0 进程：
while (turn != 0);  // 进入区
critical section;   // 临界区
turn = 1;           // 退出区
remainder section;  // 剩余区

// P1 进程：
while (turn != 1);  // 进入区
critical section;   // 临界区
turn = 0;           // 退出区
remainder section;  // 剩余区

• 主要问题：违背“空闲让进”原则

2. 双标志先检查法

• 算法思想：
  • 设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿
  • 每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区
  • 如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访向临区
  • 总结：在进入区先“检查"后“上锁”，退出区“解锁"

bool flag[2];      // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false;   // 刚开始设置为两个进程都不想进入临界区

// P0 进程：
while (flag[1]);    // 进入区
flag[0] = true;     // 进入区
critical section;   // 临界区
flag[0] = false;    // 退出区
remainder section;  // 剩余区

// P1 进程：
while (flag[0]);    // 如果此时 P0 想进入临界区，P1 就一直循环等待
flag[1] = true;     // 标记为 P1 进程想要进入临界区
critical section;   // 访问临界区
flag[1] = false;    // 访问完临界区，修改标记为 P1 不想使用临界区
remainder section;

• 主要问题：违背“忙则等待”原则
  • 原因：进入区的检查和上锁两个处理不是一气呵成的，中间可能发生进程切换

3. 双标志后检查法

• 算法思想：双标志先检查法的改版，先上锁后检查，避免两个进程同时进入临界区的问题
  • 总结：在进入区先“加锁“后“检查"，退出区"解锁"

// P0 进程：
flag[0] = true;     // 进入区
while (flag[1]);    // 进入区
critical section;   // 临界区
flag[0] = false;    // 退出区
remainder section;  // 剩余区

// P1 进程：
flag[1] = true;     // 标记为 P1 进程想要进入临界区
while (flag[0]);    // 如果 P0 也想进入临界区，则 P1 循环等待
critical section;   // 访问临界区
flag[1] = false;    // 访问完临界区，修改标记为 P1 不想使用临界区
remainder section;

• 主要问题：违背了“空闲让进”和“有限等待”原则
  • 会因各进程都长期无法访问临界资源而产生“饥饿”现象

4. Peterson 算法

• 算法思想：结合双标志法、单标志法的思想
  • 总结：在进入区“主动争取一主动谦让一检查对方是否想进、己方是否谦让”

bool flag[2];  // 表示进入临界区意愿的数组，初始值都是 false
int turn = 0;  // 表示优先让哪个进程进入临界区

// P0 进程：
flag[0] = true;                 // 进入区
turn = 1;                       // 进入区
while (flag[1] && turn==1);     // 进入区
critical section;               // 临界区
flag[0] = false;                // 退出区
remainder section;              // 剩余区

// P1 进程：
flag[0] = true;                 // 表示自己想进入临界区
turn = 1;                       // 可以优先让对方进入临界区
while (flag[1] && turn==1);     // 对方想进，且最后一次是自己谦让，那自己就循环等待
critical section;
flag[0] = false;                // 访问完临界区，表示自己已经不想访问临界区了
remainder section;

• 主要问题：未遵循“让权等待”原则，会发生“忙等”
  • 遵循了空闲让进、忙则等待、有限等待三个原则

2. 硬件实现方法

1. 中断屏蔽方法

• 实现方法：利用“开/关中断指令”实现（与原语的实现类似）
  • 即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换

关中断;
临界区;
开中断;

• 优点：简单、高效
• 缺点：
  • 不适用于多处理机
  • 只适用于操作系统内核进程，不适用于用户进程

2. TestAndSet 指令

• 实现方法：TS 指令（TSL 指令）是用硬件实现的，执行的过程不允许被中断，只能一气呵成
  • TS 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

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

// 以下是使用 TS 指令实现互斥的算法逻辑
while (TestAndSet (&lock)):  // “上锁”并“检查”
临界区代码段;
lock = false;                // “解锁”
剩余区代码段;

• 优点：
  • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
  • 适用于多处理机环境
• 缺点：不满足“让权等待”原则
  • 暂时无法进入临界区的进程会占用 CPU 并循环执行 TS 指令，从而导致“忙等”

3. Swap 指令

• 实现方法：Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成

// Swap 指令的作用是交换两个变量的值
Swap (bool *a, bool *b) {
  bool temp;
  temp = *а;
  *а = *b;
  *b = temp;
}

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

• 优点：同 TS 指令
• 缺点：同 TS 指令

2.3.3 互斥锁

• 互斥锁：解决临界区最简单的工具
• 获得锁：一个进程在进入临界区时调用 acquire() 函数，以获得锁
• 释放锁：一个进程在瑞出临界区时调用 release() 函数，以释放锁

acquire () {
  while (!available);  // 忙等待
  available = false;   // 获得锁
}
release () {
  available = true;   // 释放锁
}

• 实现方式：acquire() 和 release() 的执行必须是原子操作，因此互斥锁常采用硬件机制实现
• 自旋锁的缺点：忙等待（违背“让权等待”原则）
  • 当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()
• 适用场景：多处理器系统（一个核忙等，其他核照常工作，并快速释放临界区）
  • 等待期间不用切换进程上下文，多处理机系统中，若上锁的时间短，则等待代价很低

2.3.4 信号量

• 信号量：一个变量，用来表示系统中某种资源的数量
  • 可以使用 wait() 和 signal() 这一对原语操作（可简写为 P() 和 V()）
  • 用于实现进程互斥与同步问题
• 整型信号量：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
  • 对整型信号量的操作：初始化、P 操作、V 操作

  int S = 1; // 初始化整型信号量 S，表示当前系统中可用的资源数
  
  void wait (int S) {    // wait 原语，相当于进入区
    while (S <= 0);      // 如果资源数不够，就一直循环等待
    S = S - 1;           // 如果资源数够，则占用一个资源
  }
  
  void signal (int S) {  // signal 原语，相当于退出区
    S = S + 1;           // 使用完资源后，在退出区释放资源
  }

  // 进程P0：
  wait(S);       // 进入区，申请资源
  使用资源;       // 临界区，访问资源
  signal(S);     // 退出区，释放资源

  • 存在的问题：不满足“让权等待”原则
• 记录型信号量：用记录型数据结构表示的信号量，可以解决“忙等”问题
  • S.value 表示某种资源数，S.L 指向等待该资源的队列
  • P 操作：申请一个资源 S，如果资源不够就阻塞等待
    • 过程：先 S.value--，之后可能需要执行 block 原语
    • block 原语：使进程从运行态进入阻塞态，并把挂到信号量 S 的等待队列（即阻塞队列）中
  • V 操作：释放一个资源 S，如果有进程在等待该资源，则唤醒一个进程
    • 过程：先 S.value++，之后可能需要执行 wakeup 原语
    • wakeup 原语：唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
  • 作用：实现系统资源的申请和释放；实现进程互斥、进程同步

  /*记录型信号量的定义*/
  typedef struct {
    int value;           // 剩余资源数
    struct process *L;   // 等待队列
  }
  /*某进程需要使用资源时，通过 wait 原语申请*/
  void wait (semaphore S) {
    S.value--;
    if (S.value < 0) {
      block(S.L);
    }
  }
  /*进程使用完资源后，通过 signal 原语祥放*/
  void signal (semaphore S) {
    S.value++;
    if (S.value < 0) {
      wakeup (S.L);
    }
  }

• 实现进程互斥：在临界区前后分别 PV
  1. 分析并发进程的关键活动，划定临界区
  2. 设置互斥信号量 mutex，初值为 1
  3. 在进入区 P(mutex) 申请资源
  4. 在退出区 V(mutex) 释放资源

/*信号量机制实现互斥*/
semaphore mutex = 1;  // 初始化信号量

P1(){
  ...
  P(mutex);       // 使用临界资源前需要加锁
  临界区代码段...
  V(mutex);       // 使用临界资源后需要解锁
  ...
}

P2(){
  ...
  P(mutex);
  临界区代码段...
  V(mutex);
  ...
}

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

/*信号量机制实现同步*/
semaphore S = 0;  // 初始化同步信号量

// 要保证语句 y 必须在语句 x 之后执行
P1(){
  x;       // 执行语句 x
  V(S);    // 告诉进程 P2，语句 x 已经完成
  ...
}

P2(){
  ...
  P(S);   // 检查语句 x 是否运行完成
  y;      // 获得 x 的运行结果，执行语句 y
  ...
}

• 实现进程前驱：
  1. 分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
  2. 为每一对前驱关系各设置一个同步信号量，初值为 0
  3. 在“前操作”之后对相应的同步信号量执行 V 操作
  4. 在“后操作”之前对相应的同步信号量执行 P 操作

2.3.5 经典同步问题

PV 操作题目的解题思路：

1. 关系分析：找出题目中描述的各个进程，分析它们之间的同步、互斥关系
2. 整理思路：根据各进程的操作流程确定 P、V 操作的大致顺序
3. 设置信号量：设置需要的信号量，并根据题目条件确定信号量初值（互斥信号量初值一般为 1，同步信号量的初始值取决于对应资源的初始值）

1. 生产者-消费者问题

• 问题描述：
  • 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用
  • 生产者、消费者共享一个初始为空、大小为 n 的缓冲区
  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待
  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待
  • 缓冲区是临界资源，各进程必须互斥地访问
• 关系分析及信号量设置：
  • 同步关系 1：缓冲区没满 --> 生产者生产，设置信号量 empty
  • 同步关系 2：缓冲区不空 --> 消费者消费，设置信号量 full
  • 互斥关系：各进程必须互斥地访问缓冲区，设置信号量 mutex

semaphore mutex = 1;  // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;  // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0;   // 同步信号量，表示产品的数量，也即非空缓冲区的数量

producer (){
  while (1){
    生产一个产品;
    P(empty);        // 消耗一个空闲缓冲区
    P(mutex);
    把产品放入缓冲区;
    V(mutex);
    V(full);         // 增加一个产品
  }
}

consumer (){
  while (1){
    P(full);            // 消耗一个产品
    P(mutex);
    从缓冲区取出一个产品;
    V(mutex);
    V(empty);           // 增加一个空闲缓冲区
    使用产品;
  }
}

• 注意：
  • 实现互斥是在同一进程中进行一对 PV 操作
  • 实现两进程的同步是在其中一个进程中执行 P，在另一进程中执行 V
  • 实现互斥的 P 操作必须在实现同步的 P 操作之后，否则会发生死锁
  • 两个 V 操作的顺序可以交换，因为 V 操作不会导致进程阻塞

2. 多生产者-多消费者问题

• 问题描述：
  • 桌子上有一只盘子，每次只能向其中放入一个水果
  • 爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果
  • 只有盘子空时，爸爸或妈妈才可向盘子中放一个水果
  • 仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果
• 关系分析：
  • 互斥关系：对盘子的访问要互斥地进行，设置信号量 mutex
  • 同步关系 1：盘中有苹果 --> 取苹果，设置信号量 apple
  • 同步关系 2：盘中有橘子 --> 取橘子，设置信号量 orange
  • 同步关系 3：盘子为空 --> 放入水果，设置信号量 plate

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);
    从盘中取出苹果;
    V(plate);
    吃掉苹果;
  }
}

son (){
  while (1) {
    P(orange);
    从盘中取出橘子;
    V(plate);
    吃掉橘子;
  }
}

• 注意：本题可以不用互斥信号量，原因是盘子容量为 1，任何时刻最多只有一个进程的 P 操作不会被阻塞并进入临界区

3. 读者-写者问题

• 问题描述：复杂的互斥问题
  • 允许多个读者可以同时对文件执行读操作
  • 只允许一个写者往文件中写信息
  • 任一写者在完成写操作之前不允许其他读者或写者工作
  • 写者执行写操作前，应让已有的读者和写者全部退出

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

• 注意：
  • 设置 count 变量是为了允许多个读者同时读文件
  • 设置 mutex 互斥信号量的原因是对 count 变量的检查和赋值需要一气呵成
• 存在的问题：这种算法中，读进程是优先的，写进程可能被“饿死”
  • 原因：只要有读进程还在读，写进程就一直要阻塞等待
  • 解决方法：

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); 
    if (count == 0) 
      P(rw);
    count++;
    V(mutex);
    V(w);              // 增加
    读文件...
    P(mutex);
    count--; 
    if (count == 0)
      V(rw); 
    V(mutex);
  }
}

4. 哲学家进餐问题

• 问题描述：
  • 一张圆桌上坐着 5 名哲学家，每两个哲学象之间的桌上摆一根筷子，桌子的中间是一碗米饭
  • 哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人
  • 只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）
  • 如果筷子已在他人手上，则需等待
  • 饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考
• 问题关键：解决进程死锁，原因是每个进程需要同时持有两个临界资源
• 关系分析：5 位哲学家与左右邻居对其中间筷子的访问是互斥问题
• 信号量设置：定义互斥信号量数组 chopstick[5] = {1, 1, 1, 1, 1}，并对哲学家按 0 到 4 编号
  • 哲学家 $i$ 左边的筷子编号为 $i$，右边的筷子编号为 $(i + 1) \% 5$

semaphore chopstick[5] = {1,1,1,1,1};
Pi () {   // i 号哲学家的进程
  while (1) {
    P(chopstick[i]);          // 拿左 
    P(chopstick[(i+1)%5]);    // 拿右
    吃饭...
    V(chopstick[i]);          // 放左
    V(chopstick[(i+1)%5]);    // 放右
    思考...
  }
}

• 存在的问题：如果 5 个哲学家并发地拿起自己左手边的筷子，会发生循环等待，导致死锁
• 解决方法：对哲学冢进程施加一些限制条件
  • 最多允许四个哲学家同时进餐，这样保证至少有一个哲学家可以拿到左右两只筷子
  • 要求奇数号哲学家先拿左边的筷子，再拿右边的筷子，而偶数号哲学家相反
  • 仅当一个哲学家左右两只筷子都可用时才允许他拿起筷子

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;
Pi () {   // i 号哲学家的进程
  while (1) {
    P(mutex);
    P(chopstick[i]);          // 拿左 
    P(chopstick[(i+1)%5]);    // 拿右
    V(mutex);
    吃饭...
    V(chopstick[i]);          // 放左
    V(chopstick[(i+1)%5]);    // 放右
    思考...
  }
}

2.3.6 管程

• 引入管程的原因：信号量机制编程麻烦、易出错
• 管程的组成部分：
  • 管程的名称
  • 局部于管程内部的共享数据结构说明
  • 对该数据结构进行操作的一组过程（函数）
  • 对局部于管程内部的共享数据设置初始值的语句
• 管程的基本特征：
  • 局部于管程的数据只能被局部于管程的过程所访问
  • 一个进程只有通过管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程
• 互斥和同步的实现：
  • 各进程必须互斥访问管程的特性是由编译器实现的
  • 可在管程中设置条件变量及等待/唤醒操作以解决同步问题

2.4 死锁

2.4.1 死锁的概念

• 死锁的定义：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
• 死锁、饥饿、死循环的区别：
  • 死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
  • 饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
  • 死循环：可能只有一个进程发生死循环，死罐环的进程可上处理机
  • 死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
• 死锁产生的必要条件：
  • 互斥条件：对必须互斥使用的资源的争抢才会导致死锁
  • 不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺
  • 请求和保持条件：保持着某些资源不放的同时，请求别的资源
  • 循环等待条件：存在一种进程资源的循环等待链
    • 循环等待未必死锁，死锁一定有循环等待
• 死锁发生的原因：对不可剥夺资源的不合理分配
  • 具体原因：对系统资源的竞争、进程推进顺序非法、信号量使用不当
• 死锁的处理策略：
  • 预防死锁：破坏死锁产生的四个必要条件
  • 避免死锁：避免系统进入不安全状态（银行家算法）
  • 死锁检测和解除：允许死锁发生，系统负责检测出死锁并解除

2.4.2 死锁预防

• 破坏互斥条件：
  • 方案：将临界资源改造为可共享使用的资源（如 SPOOLing 技术）
  • 缺点：可行性不高，很多时候无法破坏互斥条件
• 破坏不剥夺条件：
  • 方案一：申请的资源得不到满足时，立即释放拥有的所有资源
  • 方案二：申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
  • 缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿
• 破坏请求和保持条件：
  • 方案：运行前分配好所有需要的资源，之后一直保持
  • 缺点：资源利用率低；可能导致饥饿
• 破坏循环等待条件：
  • 方案：给资源编号，必须按编号从小到大的顺序申请资源
  • 缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦

2.4.3 死锁避免

• 安全序列：指如果系统按照这种序列分配资源，则每个进程都能顺利完成
• 安全状态：只要能找出一个安全序列，系统处于安全状态
• 系统状态与死锁：
  • 如果系统处于安全状态，就一定不会发生死锁
  • 如果系统进入不安全状态，就可能发生死锁

银行家算法

• 核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态
  • 如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待
• 数据结构：假设系统中有 $n$ 个进程，$m$ 种资源
  • 长度为 $m$ 的一维数组 Available 表示还有多少可用资源
  • $n \times m$ 矩阵 Max 表示各进程对资源的最大需求数
  • $n \times m$ 矩阵 Allocation 表示已经给各进程分配了多少资源
  • Max $-$ Allocation $=$ Need 矩阵表示各进程最多还需要多少资源
  • 长度为 $m$ 的一维数组 Request 表示进程此次申请的各种资源数
• 银行家算法步骤：
  1. 检查此次申请是否超过了之前声明的最大需求数
  2. 检查此时系统剩余的可用资源是否还能满足这次请求
  3. 试探着分配，更改各数据结构
  4. 用安全性算法检查此次分配是否会导致系统进入不安全状态
• 安全性算法步骤：
  1. 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收
  2. 不断重复上述过程，看最终是否能让所有进程都加入安全序列

2.4.4 死锁检测和解除

• 资源分配图：
  • 两种结点：
    • 进程结点：对应一个进程
    • 资源结点：对应一类资源，一类资源可能有多个
  • 两种边：
    • 进程结点 --> 资源结点（请求边）：表示进程想申请几个资源（每条边代表一个）
    • 资源节点 --> 进程结点（分配边）：表示已经为进程分配了几个资源（每条边代表一个）
• 死锁检测算法：
  • 步骤：依次消除与不阻塞进程相连的边，直到无边可消
    • 不阻塞进程：其申请的资源数还足够的进程
  • 死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
• 解除方法：资源剥夺法、撤销进程法（终止进程法）、进程回退法