教材：《操作系统——精髓与设计原理 第八版》– William Stallings

一 操作系统概述

操作系统的目标和功能

操作系统：

• 控制应用程序执行的程序
• 应用系统和计算机硬件之间的接口

目标：方便、有效、扩展能力

功能：

• （作为用户/计算机接口的）OS 提供的服务：
  • 程序开发
  • 程序运行
  • I/O设备访问
  • 文件访问控制
  • 系统访问
  • 错误检测和响应
  • 记账 Accounting
• （作为资源管理器的）操作系统负责
  • 资源管理，控制数据的移动、存储、管理

操作系统的历史

串行处理

• 无 OS
• 控制台、输入设备（卡片机阅读器）

简单批处理系统

• 监控程序
• 对一批作业自动处理
• 内存中只能存放一道作业

简单批处理系统

监控程序的功能：

• 作业的自动续接
• 内存保护
• 定时器（防止作业独占）
• 特权指令（内核模式下）
• 中断

运行模式：用户模式、内核模式

多道批处理系统

多道批处理系统

多道批处理系统：简单批处理系统的改进

• 内存中同时存放多个作业
• 作业可并发执行
• 作业调度程序

硬件支持：

• I/O中断
• DMA
• ……

特征：多道性、调度性、无序性、无交互能力

如下，系统可用内存250MB，三个作业可同时处理：

示例-信息

分时系统

产生原因：人机交互、共享主机、方便上机

分时系统：

• 采用多道程序设计技术处理多个交互作业
• 多个用户共享处理器
• 多个用户通过不同终端同时访问系统

特征：多路性、独立性、及时性、交互性

第一个分时操作系统：CTSS (Compatible Time-Sharing System)

CTSS 内存占用示例

实时系统

系统能够及时（即时）响应外部事件的请求，在规定的时间内开始或完成对该事件的处理，并控制所有实时任务协调一致地运行。

应用领域：

• 航空航天
• 军事
• 工业控制
• 事务系统
  总之家用电脑不需要

特征：可确定性、可响应性、用户控制、可靠性、故障弱化能力

操作系统的主要成就

这部分是一个概述，具体的定义和实现在后面都会有讲。

进程

进程：一个正在处理器执行的程序

为什么会有进程

进程的组成：

• 可执行程序
• 相关数据
• 程序的执行上下文（execution context）
  • 进程状态
  • 操作系统用来管理和控制进程所需的所有数据（处理器寄存器的内容、进程优先级、是否在等待I/O事件、在内存中的位置……）

如下，正在执行的 B 进程切换到 A 时，需要保存 B 的上下文：

典型的进程实现

内存管理

任务：

• 进程隔离
• 自动分配和管理
• 支持模块化程序设计
• 保护和访问控制
• 长期存储

文件系统：实现了长期存储
文件：一个有名称的对象，访问控制和保护的基本单元

虚拟存储：

• 以逻辑方式访问存储器，不考虑物理内存可用的空间数量
• 满足多作业F同时驻留内存的要求
• 换入、换出机制
• 分页机制（进程大小不同）
• 每个作业部分驻留（检测到缺页时载入）

分页机制：

• 页：若干个固定大小的块，组成进程
• 虚地址（virtual address）：由页号和页内偏移量组成
• 虚地址和内存中实地址（real address，物理地址）之间的动态映射机制

虚存寻址

信息保护和安全

OS 的 4 类典型安全问题：

• 可用性
• 保密性
• 数据完整性
• 认证

调度和资源管理

调度策略需要考虑：

• 公平性
• 有差别的响应性
• 有效性

  

  多道程序环境中涉及进程调度和资源分配的主要组件

现代操作系统的特征

• 微内核：只给内核分配基本功能（地址空间、进程间通信 IPC、基本的调度）
  • 优点：简化实现、灵活、适合分布式
• 多线程
  • 线程：可分派的工作单元。包括上下文、数据区域
  • 进程：一个或多个线程和相关系统资源的集合
• 对称多处理：多处理器架构，且每个处理器地位相同
  • 多个进程/线程可以并行
  • 多处理器对用户透明
  • OS 负责调度、同步
  • 优点：性能、可用性、渐增性、扩展性
• 分布式
• 面向对象
  • 给小内核增加模块化扩展、定制操作系统

容错性

操作系统相关技术：

• 进程隔离
• 并发控制
• 虚拟机
• 检测点和回滚机制

多处理器和多核操作系统考虑因素

关键问题：

• 并发进程或线程
• 调度
• 同步
• 内存管理
• 可靠性、容错性

多核系统潜在的并行能力有三个层次

• 应用程序以多线程形式执行能力
• 多处理器的多线程程序执行能力
• 核内部硬件并行、指令集并行

OS 常用策略：

• 应用层并行
• 虚拟机

主流操作系统（略）

单体内核

• 单体内核：在一大块代码中包含了所有的操作系统功能，作为单个进程运行，具有唯一的地址空间
• 所有的功能部件都可以访问内核数据结构和例程
• Linux 虽然是单体内核，但是采用了模块化结构

二(1) 进程管理：进程描述与控制

什么是进程

进程：一段代码执行的时候就称为进程

进程 = 代码 + 相关数据

进程由以下元素表征：

进程的元素

• 上下文数据（狭义，图中的“上下文数据”即是狭义）：CPU寄存器
  • 广义：图中全部数据
• 记账信息：统计信息（CPU 时长等）

进程控制块 Process Control Block, PCB

• 各操作系统不同
• 用于中断进程后恢复进程

进程控制块

进程特征：

• 动态性（存在生命周期，本质特征）
• 并发性（重要特征）
• 独立性
• 异步性：按各自独立的、不可预知的速度向前推进
  • 为什么速度不可预知？——存在中断等等

进程与程序比较：

• 进程：正在运行的程序实例
• 进程 = 进程控制块 + 程序 + 相关数据
• 引入进程概念为并发作铺垫
• 程序静态，进程动态
• “程序-进程”不是一对一
  • 反例 1：一个进程可以对应多个程序（一个进程调用 DLL 等，也算是多个程序）
  • 反例 2：一个程序可以对应多个进程

进程状态

进程轨迹

进程轨迹：进程执行的指令序列，用来描述单个进程的行为

处理器的行为可以用多个进程交替执行的轨迹来描述，如下图。

示例

进程的两状态模型

进程的两状态模型

简单易懂。

进程的两状态模型的排队图

进程的创建和终止

进程创建的原因：

• 提交批处理作业后，准备处理新的批处理作业
• （终端用户）交互登陆
• 为提供服务而由操作系统创建
• 由现有进程派生
  • 相关的进程称为父进程和子进程

记忆方法：可以由操作系统、用户、父进程创建，其中操作系统可以因为新的作业或提供系统服务而创建。

进程终止：

终止的原因

进程的五状态模型

将 Not Running 细分为就绪（等 CPU）和阻塞（等 I/O 之类的），得到了五状态模型：

进程的五状态模型

进程的五状态模型的排队图

排队模型如上图。除此之外，还有下列几种变形：

• 多阻塞队列
• 多就绪队列（优先级不同）
• 退出状态（保留记账信息等）

进程的五状态模型的排队图（多阻塞队列）

挂起

挂起的进程：

• 原因：内存资源紧张、无就绪进程（进程全阻塞等待 I/O）
• 交换：把内存的一个进程的部分或全部移到磁盘中（挂起状态），然后从挂起队列取一个进程/接纳一个新进程
• 挂起状态：将内存中处于阻塞、就绪、甚至是执行状态的进程放到外存，不再参与 CPU 的竞争

六状态模型

为区分两种挂起，便有了七状态的挂起状态图（重点）：

七状态模型

挂机进程特征：

• 不能立即执行
• 可能在等待事件
• 需要被一个代理（自身、父进程或 os）挂起
• 需要被代理取出

进程挂起的原因：

进程挂起的原因

进程描述

进程的三种情况

操作系统的控制结构

内存表：用于跟踪内存和外存

• 分配给进程的内存
• 分配给进程的外存
• 内存块或外存块的保护属性，如为哪些进程所共享
• 管理外存所需要的信息
• 注：外存使用虚拟存储或交换机制

I/O 表：

• I/O 的状态
• 源/目标的内存单元

文件表：

• 是否存在
• 在外存中的位置
• 当前状态
• 其他属性

进程表：

• 用于管理进程
• 表中有内存、I/O、文件的引用
• 表能被 OS 访问
• OS 需要知道：进程的位置、属性
  • 位置包含：程序、数据、（调用）栈
  • 属性即 PCB
  • 程序、数据、栈和属性构成进程映像

PCB 中的信息：

• 进程标识信息
  • 进程的唯一标识符 ID，构成索引
  • 父进程 ID
  • 用户 ID
• 处理器状态信息
  • 被设计为程序状态字 PSW 寄存器
  • 由寄存器内容组成
    • 用户可见寄存器
    • 控制、状态寄存器
    • 栈指针
• 进程控制信息
  • 调度和状态信息（进程状态、优先级、调度相关信息、等待事件的标识）
  • 数据结构（用队列、环等链接到其他进程）
  • 进程间通信（两个进程通信的相关信息）
  • 进程特权
  • 存储管理（进程虚存的段表、页表的指针）
  • 进程所有权、使用情况（打开的文件、使用历史）

记忆上，进程控制信息的六点可以按照章节名来记：调度和状态信息（对应进程调度）、进程通信（对应进程同步）、存储管理（对应第三章）、进程使用情况（对应 I/O、文件），外加数据结构和进程特权（对应内核模式）。

进程表 = n * 进程映像的指针
进程映像 = 程序 + 数据 + 栈 + 属性(PCB)
PCB = 进程标识信息 (三个 ID) + 处理器状态信息 (PSW) + 进程控制信息

进程控制

内核

内核 kernel：操作系统的核心

• 操作系统中的重要系统功能
• 常驻内存
• 功能：
  • 资源管理：进程管理、存储管理、I/O 设备管理（文件管理放在核外）
  • 支撑功能：中断处理、时钟管理、记账功能

中断处理既是内核的基本功能，也是整个操作系统赖以活动的基础，操作系统的一切重要活动最终都依赖于中断。

执行模式

大多数处理器至少支持用户模式和内核模式。

• 用户模式
  • 优先权较少
  • 运行用户程序
• 系统模式/内核模式/控制模式
  • 优先权更高
  • 运行内核
  • 某些指令、内存只能在特权模式下运行/访问，如：
    • 读取/修改 PSW 等控制寄存器
    • 原始 I/O 指令
    • 内存管理相关

记忆上，用户模式和系统模式是一一对应的。系统模式的特权可以分为三个方面：寄存器、内存、I/O。

区分用户模式和内核模式的原因：保护 OS 和重要操作系统表不受程序干扰

内核模式的实现方案：

• IA-64 处理器的 PSWR 中存在指示执行模式的位
• 当用户调用操作系统服务或中断促发系统例程时，相关位被置为内核模式
• 当从系统服务返回用户进程时，执行模式置为用户模式

系统调用 system call 是 OS 为用户提供的接口。

进程创建

回忆进程创建的原因？

创建进程的流程：

1. 分配 ID
2. 分配内存
3. 初始化 PCB（标识信息、处理器状态信息、控制信息）
4. 建立相关指针、引用（如将其插入就绪或就绪/挂起链表）
5. 建立/扩充其他数据结构

进程切换

下均指用户模式下的进程切换。

进程切换的时机

系统中断

系统中断：普通中断和陷阱对比。

普通终端和陷阱

• 内存失效：缺页等
• 中断不一定导致进程切换（getpid() 系统调用引发中断，但没有进程切换）

模式切换

模式切换：用户模式和内核模式之间的相互转换。

模式切换原因：

• 系统调用
• 中断
  • 中断出现时，会将程序计数器置为中断处理程序的开始地址（汇编基础 hhh）
  • 需要从用户模式切换到内核模式，以便中断处理能执行特权指令

注意：

• 模式切换不一定导致进程切换（getpid() 系统调用引发中断，但没有进程切换）
• 进程切换一定会有模式切换（进程切换一定要在内核模式下进行）

进程状态转换

• 模式切换不一定有进程状态转换
• 进程切换一定有进程状态转换（就绪、阻塞等）

进程切换步骤：

• 保存处理器上下文（寄存器）
• 更新当前进程的 PCB（状态、数据结构等变化）
• 将 PCB 的指针移至相应队列（就绪、阻塞、挂起等）
• 选择另一进程执行

切换回来的步骤：

• 更新该进程的 PCB
• 更新内存管理数据结构
• 恢复被选择进程的上下文

总结几个概念的关系

1. 中断、模式切换 --不一定--> 进程切换、进程状态转换（反例均为 getpid()）
2. 进程切换 --一定--> 模式切换、进程状态转换

操作系统的执行

操作系统的执行

Unix SVR4 的进程管理

Unix SVR4 的进程状态图

Unix SVR4 的进程状态图

• 阻塞在 Unix SVR4 中被称为 Sleep。

Unix SVR4 的进程创建

• 内核系统调用 fork()，在内核模式下完成

1. 在进程表中为新进程分配一个空项
2. 为子进程分配一个唯一的 ID
3. 复制父进程的进程映象，但共享内存除外
4. 增加父进程所拥有的文件的计数器，反映另一个进程现在也拥有这些文件的事实
5. 将子进程设置为就绪态
6. 将子进程的 ID 号返回给父进程，将 0 值返回给子进程

• fork() 的返回值：-1（出错）、0（无子进程）、正值（子进程的 ID）
• 进程创建后，可能发生：
  • 控制权：父进程，执行点：调用 fork 的位置
  • 控制权：子进程，执行点：调用 fork 的位置
  • 控制权：其他进程（即使当前父子进程处于就绪态）
• 最终父进程和子进程均会在下一条语句上继续运行

例题 1：

1
2
3
4
5
6
7
8
9

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>

void main(void) {
  printf("Hello");
  fork(); 
  printf("Bye");
}

输出 HelloByeBye，但父/子进程输出 Bye 的先后顺序未知。

例题 2：

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>
#include <unistd.h>
int main()
{
  int i;
  for (i=0;i<3;i++)
    fork();
  printf("hello, world\n");
  return 0;
}

输出 8 个 hello, world。

例题 3：

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

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<string.h>

void main(void)
{
  int i;
  static char buffer[10];
  if (fork()==0)     
    strcpy(buffer, "Child\n");
  else
    strcpy(buffer, "Parent\n");

  for (i=0; i < 5; ++i)
  {
    sleep(1);
    write(1, buffer, sizeof(buffer));
  }
}

该程序的运行无法保证输出顺序，输出顺序依赖于内核所用的调度算法。
在 Ubuntu 20.04 LTS 测试结果如下：

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

$ gcc test.c -o test
$ ./test
Parent
Child
Parent
Child
Parent
Child
Parent
Child
Parent
Child
$

例题 4：下面代码执行后，问父子进程的 global 和 vari 变量值。

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

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>

int global = 4;
void main(void) {
  int pid; 
  int vari = 5;
  printf("before fork\n");
  if ((pid = fork()) < 0) {
    printf("fork error\n");
    exit(0);
  } else if (pid == 0) {
    global++;
    vari--;
  }
  printf("global=%d,vari=%d\n", global, vari);
}

运行后，父进程的 (global, vari) = (4,5)；子进程的 (global, vari) = (4,5)。

这个例子说明，子进程的内存是父进程 (global, vari) = (4,5) 的复制下（而不是引用），子进程进行 global++; vari--; 完全不影响父进程的变量。

线程

线程与进程

进程的两个属性（拥有资源、调度/执行的基本单位）是独立的，OS 应该能独立处理它们，为此引入线程。

• 调度并分派的单位通常称为线程（或轻量级进程 LWP）
• 资源所有权的单位通常称为进程

多线程 multithreading：操作系统在单个进程内支持多个并发路径的能力。

单线程：每个进程中只有一个线程在执行（在多线程出现之前，还没有线程这个概念；显然这是在多线程出现之后才给出的定义）。

多进程与多线程的例子

多线程环境中，与进程相关的资源和保护：

• 容纳进程映像的虚地址空间（回忆进程映像
• 受保护的访问：
  • 处理器
  • 其他进程（进程间通信时，以进程为单位）
  • 文件
  • I/O 资源

一个进程中可能有多个线程，每个线程有：

• 执行状态（运行、就绪等）
• 未运行时保存的线程上下文（寄存器值）
• 执行栈（过程调用）
• 用于局部变量的静态存储空间
• 与进程内其他线程共享的内存和资源访问

如下图，多线程模式中，几个线程的 PCB 和内存地址空间是共享的，而每个线程有自己的 TCB、用户栈和内核栈。进程控制块 Thread Control Block 较 PCB 会简单很多，其内容如上点。

单进程和多进程模型

进程的优点：

• 创建线程快于创建进程（因为 TCB 简单）
• 终止线程快于终止进程（同上）
• （同一进程内）线程切换快于进程切换（上下文、数据结构少）
• 线程提高了不同执行程序间通信的效率（线程间通信）

调度和分派基于线程

• 大多数与线程相关的信息保存在线程级的数据结构中
• 挂起一个进程 == 挂起内部所有线程
• 终止一个进程 == 终止内部所有线程

线程主要状态：运行、就绪、阻塞（类似于进程三状态模型）
和线程状态变化相关的基本操作：派生、阻塞、解除阻塞、结束

使用线程的远程过程调用示例

如上，即使是在单核 CPU 上运行，多线程技术在 I/O 密集型程序中能显著提高效率。

单处理器上的多线程示例

需要线程同步的原因：一个进程中的所有线程共享一个地址空间和进程所拥有的资源，一个线程对其的修改将影响其他线程。

多线程，多进程，多核相关概念

多线程，多进程，多核的概念令人迷惑，不过知乎上有篇总结贴可以参考。

1. CPU 的线程数 == 可以同时并行的线程数量 == 操作系统看到的核数（可使用任务管理器或 htop 等）
2. 进程是系统资源（内存、显卡、磁盘）的分配单位，线程是调度（可以理解为 CPU 资源）的分配单位
3. 同进程下的线程共享该进程的资源，不同进程的线程如果想要共享资源，需要在 OS 层面上通信，效率低
4. 对于计算密集型进程，进程线程数 == CPU线程数 时能充分利用 CPU 资源，进程线程数 > CPU线程数 时会因为 CPU 频繁进程切换导致效率反而变低
5. 对于 IO 密集型进程，由于进程会被频繁阻塞，进程线程数 > CPU线程数 能够提高 CPU 利用率，提高效率
6. Python 是一个特例，由于 Global Interpreter Lock (全局解释器锁) 的存在，一个 Python 进程中只能同时有一个线程执行

线程分类

• 用户级线程 User-Level Thread, ULT
• 内核级线程 Kernel-Level Thread, KLT

用户级线程和内核级线程

用户级线程 ULT

ULT 下，线程由库函数实现，线程的创建、销毁全部由库函数实现。而内核不知道用户级线程的存在，依旧按照进程为单位进行调度。

ULT 下进程状态和线程状态的关系

如上图，ULT 下，会出现一些比较神奇的情况：

1. (a) 图是正常运行的状态
2. 线程 2 等待 I/O，导致进程 B 被阻塞，此时线程 1、2 均未被 CPU 运行，但线程 2 的数据结构中仍被标记为运行，如图 (b)
3. I/O 事件到达，进程 B 被置为就绪，此时线程 1、2 均未被 CPU 运行，但线程 2 的数据结构中仍被标记为运行，如图 (c)
4. 进程 B 运行过程中，线程 2 等待线程 1 的事件，此时线程 2 被置为阻塞，线程 1 被置为运行，进程 B 仍为运行

用户级线程优点：

• 线程切换不需要内核模式
• 调度策略因应用程序不同而不同
• 可以运行在任何操作系统上

缺点：

• 当用户级线程执行系统调用时，不仅阻塞当前线程，还将引起同一进程中的其他线程阻塞
• 采用 ULT 策略，不能利用多处理器技术（ULT 下，内核按进程分配处理器）

解决方法：

• 将应用程序写成多进程程序而不是多线程
• Jacketing（套管）技术：将一个可能产生阻塞的系统调用转换成一个非阻塞的系统调用

一种解决线程阻塞问题的方法是，使用一种称为“套管”(jacketing) 的技术。“套管”的目标是把一个产生阻塞的系统调用转化为一个非阻塞的系统调用。例如，替代直接调用一个系统 I/O 例程，让线程调用一个应用级的 I/O 套管例程，这个套管例程中的代码用于检查并确定 I/O 设备是否忙。如果忙，该线程进入阻塞态并把控制权传送给另一个线程。这个线程重新获得控制权后，套管例程会再次检查I/O设备。

内核级线程 KLT

纯 KLT 软件中，管理线程的所有工作均由内核完成。应用级没有线程管理代码，只有一个到内核线程设施的应用编程接口 API。 Windows是这种方法的一个例子。

优点：

• （解决了纯 ULT 的两个痛点）一个进程的多个线程可以调度到多处理器上
• 当一个线程阻塞时，内核可以调度同一进程内的其他线程
• 此外，内核本身也可以是多线程的
  缺点：
• 从一个线程切换到相同进程内的另一个线程时，需要切换到内核模式

线程和进程操作执行时间（µs）

• Null Fork: Fork 以后什么都不做
• Signal Wait: 一个进程/线程发出信号到另一个进程/线程收到信号
• KLT 下操作涉及到模式切换；进程操作涉及到共享空间等

混合方法

在混合系统中，

• 线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行
• 一个应用程序中的多个用户级线程会被映射到一些（小于等于用户级线程数）内核级线程上（程序员还可以调节 KLT 的数量）

优点：

• 同一个进程中的多个线程可利用多处理器
• 引起阻塞的系统调用不会阻塞整个进程

设计正确时，这种方法可结合纯 ULT 方法和纯 KLT 方法的优点，并克服它们的缺点。Solaris操作系统是使用混合方法的很好例子。

二(2) 进程管理：进程调度

如果有多个进程（线程）竞争 CPU，需要选择下一个要运行的进程（线程）。OS 中完成这部分工作的程序称为调度程序 scheduler。调度程序使用的算法称为调度算法 scheduling algorithm。

调度的目的：满足系统目标（响应时间、吞吐量、处理器效率）的方式，把进程分配到一个或多个处理器上执行

调度的类型

下图为三种调度和状态图的关系。

调度与状态图

下图为三种调度的层次关系。

调度的层次

注意三种调度的关系不是包含，而是嵌套。

具有三种调度的调度队列模型

长程调度

• 决定哪个程序可以进入系统中处理
• 控制系统并发度
  • 创建的进程越多，每个进程执行的时间比例越小
  • 可能限制并发的度给当前进程集提供满意的服务

长程调度需考虑：

1. 何时操作系统能够接纳进程
2. 接纳哪个作业为之创建进程（先来先服务，或根据优先级、期望的执行时间、I/O 需求）

中程调度

中程调度是交换功能的一部分，是否换入取决于系统并发度的需求。在不使用虚存的系统中，换入决策还需考虑换出进程的存储需求。

短程调度

• 又称分派程序
• 执行最频繁
• 决定下次执行哪个进程
• 当前进程阻塞或被抢占时，调用短程调度程序
  • 事件：时钟中断、I/O 中断、系统调用、信号等

调度的规则

相关概念

• 响应时间：从用户提交一个请求开始，到接收响应之间的时间间隔
  • 响应时间 = 输入传送时间 + 处理时间 + 响应传送时间
• 截止时间：某任务必须开始执行/必须完成的最迟时间
• 吞吐量：在单位时间内，系统完成的进程数
• 处理器利用率：处理器处于忙状态的时间百分比
• 周转时间：进程从提交到完成的时间
  • 周转时间 = 等待资源的时间 + 执行时间
  • 等待资源的时间 = 就绪 + 阻塞 + 就绪/挂起 + 阻塞/挂起
  • 注意“周转时间”和“响应时间”针对的主体不同，前者是进程，后者是用户
• 平均周转时间：多个进程周转时间的平均值
• 平均带权周转时间：多个进程带权周转时间的平均值
  • 带权周转时间 $= T/S \geq 1$，其中 $T$ 为周转时间，$S$ 为服务时间（执行时间）
  • 若 $T/S=1$ 说明进程来了立即被调用，没有等待

调度规则总结

短程调度的主要目标：以优化系统某些方面为目的，分配处理器时间

• 面向用户，与性能相关：周转时间、响应时间、 最后期限（截止时间）
• 面向用户，与性能无关：可预测性
• 面向系统，与性能相关：吞吐量、 处理器利用率
• 面向系统，与性能无关：公平性、强制优先级、平衡资源

优先级的使用

下图为多优先级队列的一个例图。总是先执行优先级最高的进程（RQ0）。

优先级的使用

考虑进程优先级可能导致饥饿（低优先级进程迟迟无法运行），可以采用动态优先级方案（如根据等待时间变化优先级，等待时间过长后提高优先级）。

调度的决策模式

调度的决策模式：

• 非抢占（非剥夺）：执行进程只有在执行完毕，或因申请 I/O 或请求某些操作系统服务而阻塞自己时，才释放处理器。OS 不会主动中断进程。
• 抢占（剥夺）：执行进程可能被操作系统中断，并转换为就绪态

抢占可能发生在：

• 新进程到达
• 中断发生后把一个阻塞进程置为就绪态
• 周期性的时钟中断

调度的选择函数：

• 决定下次选择哪个就绪进程执行
• 可基于优先级、资源需求、进程的执行特性
• 基于执行特性时的基本参数：
  • w = 在系统里已经等待 waiting 的时间
  • e = 在系统里已经执行 execution的时间
  • s = 进程所需的总服务 service 时间，需要估计或由用户提供
  • e-s = 进程还需要执行的时间

调度算法

• 系统的资源分配策 -> 资源分配算法
• 对于不同的系统目标，采用不同的调度算法

常见（短程）调度算法：

• 先来先服务 First Come First Served, FCFS
• 时间片轮转 Round Robin, RR
• 短进程优先 Shortest Process Next, SPN
• 剩余时间最短优先 Shortest Remaining Time, SRT
• 响应比高者优先 Highest Response Ratio Next, HRRN
• 反馈 Feedback
• ……

概述

概述

先来先服务 FCFS

• 算法：First-Come-First-Served, FCFS，也称为 FIFO
• 选择就绪队列中存在时间最长的进程运行 max[w]
• 即按请求 CPU 的顺序使用 CPU

示例

算法评价：

• 非抢占调度
• 有利于 CPU 繁忙型的进程（非抢占，能一直利用 CPU），而不利于 I/O 繁忙型的进程（需要反复排队 太惨了）
• 不适合直接用于单处理器系统,通常与其它调度算法混合使用
• 平均周转时间长
• 对长进程有利，不利于短进程

时间片轮转 RR

• 算法：Round Robin, RR
• 每个进程被分配一个时间片，周期性产生时钟中断，中断时当前进程进入就绪队列末尾，基于 FCFS 选择下一个作业运行
• 如果进程在时间片内阻塞或结束，则立即切换 CPU
• RR 算法在通用的分时系统或事务处理系统中特别有效

示例

图中 q 为时间片长度，下同。

注意，D 到达的同时 C 调度时间片结束，此时优先级： D > C。

算法评价：

• 抢占
• 常用于分时系统或事务处理系统
• 时间片与性能、响应时间相关
  • 时间片太短——进程切换频繁，降低 CPU 效率
  • 时间片太长——短交互请求的响应时间变长
  • 时间片最好略大于一次典型交互的时间
• 对 CPU 密集型进程有利，对 I/O 型密集型进程不利（用不完一个时间片）

针对最后一点的改进：Virtural RR 算法

• 增加一个辅助队列，接收 I/O 阻塞完成的进程
• 调度优先于就绪队列
• 但占用的处理器时间小于就绪队列
• 类似于超市的快速结账通道
• VRR 算法比 RR 算法公平

短进程优先 SPN

算法: Shortest Job(Process) First(Next), SJF/SPF/SPN

• 短进程或短作业优先调度 min[s]
• 前提：预知执行时间

示例

算法评价：

• 非抢占
• 长进程饥饿
• 有利于短进程，减小了平均周转时间
• 缺少剥夺机制，不适用于分时系统/事务处理环境
• 用户估计不准时，算法不一定能真正做到短作业优先调度

剩余时间最短优先 SRT

算法: Shortest Remaining Time, SRT

• 选择预期剩余时间最短的进程 min[s-e]
• 当一个新进程加入就绪队列时，如果它比当前运行的进程具有更短的剩余时间，就抢占当前正在运行的进程
• 在 SPN 的基础上增加了剥夺机制，抢占型

示例

算法优点：

• 既不像 FCFS 偏爱长进程，也不像 RR 算法产生很多中断（因时间片而产生），减少了开销
• 周转时间方面，比 SPN 好：只要就绪，短作业可以立即被执行

算法缺点：

• 需要估计预期的服务时间 s
• 存在长进程饥饿现象
• 必须记录进程的已服务时间

响应比高者优先 SRRN

算法: Highest Response Ratio Next, HRRN

• 当前进程执行完毕或需要阻塞时，选择就绪队列中响应比 $R_p$ 最高的进程投入执行，其中

$$R_p = \frac{等待时间+要求服务时间}{要求服务时间} = \frac{w+s}{s}$$

示例

算法评价：

• 非抢占
• 动态优先权调度算法
• 算法说明了进程的年龄
• 是 FCFS 和 SJF 的结合，既照顾了短进程，又考虑了作业到达的先后次序，不会使长进程长期得不到服务
• 但每次调度之前，都须先做响应比的计算，会增加系统开销；且难以准确计算

反馈调度法 Feedback

SPN、SRT、SRRN 采用了“奖励短进程”的思想。虽然性能较好，但均基于进程的预期执行时间。

算法思想：

• 采用惩罚运行时间较久的进程的思想
• 关注已经执行的时间 e
• 抢占（但是只在时间片结束时抢占）
• 动态优先级
• 采用多级队列区别对待的方法——惩罚长进程
• 多个独立的、优先级不同的就绪队列，优先调度优先级高的队列
• 进程执行过程中会降级
• 算法有多个变种（根据抢占机制不同而不同）

（基于时间片轮转的）反馈调度算法：Feedback, FB

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

• 第一队列优先级最高，依次递减
• 优先级越高的队列，进程执行的时间片越小

2. 新进程进入时，首先放入第一个队列尾 $RQ0$，按 FCFS 原则排队
3. 如果进程在当前队列的时间片内完成则退出
4. 一般而言，从队列 $i$ 中调度的进程允许执行 $q=2^i$ 的时间，然后才能被抢占
5. 当且仅当进程被抢占时，会被降一级优先级

• 如果时间片到达而没有被抢占（无其他进程需调度），则当前进程继续运行且暂时不降级。此后，一旦新进程出现，原进程会被立即抢占（无视时间片）并降一级

6. 到达最低优先级队列后，不再降级
7. 仅当第一队列空闲时，才调度第二队列中的进程，依次类推

调度队列

重点掌握！！！

示例

注意在下面的调度图中，第 6 时刻 D 到达，此时 B 在第 2 队列，但没有被立即抢占。必须等 B 的时间片用完后才会进行抢占。

评价：多级反馈队列调度算法具有较好的性能，能较好地满足各种类型用户的需要。

• 终端型作业：有利（常为短作业，能在第一队列内完成）
• 短作业：有利（能在前几个队列内完成）
• 长进程：将依次在第 1, 2, …, n 个队列中运行，随着优先级下降，分配的时间片长度增加，减少了抢占次数

问题：当不断有新进程到来时，长进程仍可能饥饿

实时系统与实时调度

实时系统：系统能够及时（即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。对于实时系统而言，系统的正确性不仅取决于计算的结果，而且还依赖于产生结果的时间。

实时系统 = 实时控制系统 + 实时信息处理系统

• 实时任务：具有及时性要求的、常常被重复执行的特定进程。在实时系统中习惯称为任务
• 截止时间
• 开始截止时间：任务在某时间以前必须开始执行
• 完成截止时间： 任务在某时间以前必须完成

实时任务分类

按截止时间分：

• 硬实时任务（必须在截止时间前开始/完成）
• 软实时任务（可以稍微延迟一些）

按周期性分：

• 周期性实时任务（如每五秒就绪一次）
• 非周期性实时任务

实时操作系统特点

• 可确定性(determinism)：关注的是从设备中断到系统获知中断的时间
• 可响应性(responsiveness)：关注的是系统获知中断后，为中断提供服务的的时间
• 用户控制(user control)：需要用户能够区分软、硬实时任务，并控制任务优先级
• 可靠性(reliability)：要求高于非实时系统
• 失效弱化(fail-soft operation)：故障时尽可能多地保存性能和数据，尽可能减少损失

实时调度的两个维度

• 调度方法：下次调度哪个任务
• 抢占方式：调度时采用什么抢占方式（在什么时候抢占）

调度方法分类

调度方法方面，大概分为四类：

1. 静态表驱动调度法
2. 静态优先级抢占调度法
3. 基于动态规划的调度法
4. 动态尽力调度法

静态表驱动调度表

• 用于调度周期性实时任务
• 按照任务信息（周期到达的时间、执行时间、完成截止时间以及任务的优先级），制订调度表，调度实时任务
• 例：最早截止时间优先 EDF
• 此类算法不灵活，任何任务的调度申请改动都会引起调度表的修改

静态优先级抢占调度法

• 此类算法多用于非实时多道程序系统
• 优先级的确定方法很多，例如在分时系统中，可以对 I/O 密集型和 CPU 密集型的进程赋予不同的优先级
• 实时系统中一般根据任务的时间约束赋予优先级，例如速率单调调度算法 RMS 即是根据任务周期长度为实时任务赋予静态优先级。

基于动态规划的调度法

• 当实时任务到达以后，系统为新到达的任务和正在执行的任务动态创建一张调度表
• 在当前执行进程不会错过其截止时间的条件下，如果也能使新到达任务在截止时间内完成，则立即调度执行新任务

动态尽力调度法

• 实现简单，广泛用于非周期性实时任务调度
• 当任务到达时，系统根据其属性赋予优先级，优先级高的先调度。例如最早截止时间优先 EDF 调度算法就采用了这种方法。这种算法总是尽最大努力尽早调度紧迫任务，因此称为“最大努力调度算法”
• 缺点在于，当任务完成，或截止时间到达时，很难知道该任务是否满足其约束时间

抢占方式分类

抢占方式分为以下四类，见表：

抢占方式	抢占/非抢占	抢占时间点	响应时间	应用	图
基于时间片的轮转调度	抢占	进程时间片用完	秒级	分时系统及一般实时处理系统
基于优先级的非抢占调度	非抢占	进程阻塞或完成	数百毫秒至数秒	多道批处理系统及不太严格的实时系统
基于优先级的抢占点抢占调度	抢占	剥夺点（时间中断）到来时	几毫秒至几十毫秒	一般实时系统
立即抢占式调度	抢占	立即	微秒至毫秒级	苛刻的实时系统

实时调度方法实例

近年来，人们提出了许多关于实时任务调度的合适方法，这些方法都基于每个任务的额外信息。
最常见的信息包括：

• 就绪时间
• 启动的限期 starting deadline
• 完成的限期 completion deadline
• 处理的时间：任务执行到完成的时间
• 资源需求：任务执行过程中所需的资源集
• 优先级：度量任务的相对重要性
• 子任务结构：一个任务可分解为一个必须执行的子任务和一个可选执行子任务，前者有硬截止时间 hard deadline

实时调度需要考虑的两个问题：

1. 下次调度哪个任务？——选择 deadline 最早的任务
2. 使用什么抢占方式？——对于启动限期明确的任务，采用非抢占方式；对于具有完成限期的实时系统，采用抢占策略（这合理吗？）

实例：有完成限期的周期性实时任务

在一个实时系统中，有两个周期性实时任务A和B

• A：周期：20ms，执行时间：10ms
• B：周期：50ms，执行时间：25ms

不同执行策略和效果

可见，在这个例子中，按“最早完成截止时间优先” Earliest Deadline First, EDF 的抢占模式能够使得所有任务都能在 deadline 之前执行完成。

实例：有开始限期的非周期性实时任务

• 此类任务是非周期性的，不可预测的，若采用 EDF 算法，存在危险性
• 若在任务就绪前，预先知道任务的开始截止时间，则可以采用允许 CPU 空闲的 EDF 调度算法 Earliest Deadline with Unforced Idle Times
• 优先调度截止时间最早的合格任务，并让该任务运行完毕
  • 合格任务可以是还未就绪，但是事先知道其开始截止时间的任务
• 尽管 CPU 的利用率不高，但这种调度算法可以保证系统中的任务都能按要求完成

A、B、C、D、E五个非周期性进程，到达时间、执行时间和开始截止时间如下：

五个实时任务的执行信息

不同执行策略和效果

允许 CPU 空闲、优先调度 deadline 最早的（可能还未就绪的）合格任务，使得其能完成 B 任务。

实例：周期性实时任务

• Rate Monotonic Scheduling, RMS
• 周期性任务
• 任务速率：任务周期（单位：秒）的倒数，以赫兹为单位
• 任务速率用于优先级的确定
  • 任务周期越短，优先级越高
  • 优先级函数是任务速度的单调递增的函数
• 系统按任务优先级的高低进行调度

实时系统处理能力限制

假定系统中有 $m$ 个周期性的硬实时任务，任务 $i$ 的处理时间为 $C_i$，周期为 $P_i$，则在单处理机情况下，必须满足下面的限制条件：

$$\sum_{i=1}^m \frac{C_i}{P_i} \leq 1$$

即系统中各个任务的处理器利用率总和不能超过 1（CPU的利用率 = 任务执行时间 / 任务周期）。

优先级反转

高优先级任务被低优先级任务阻塞，导致高优先级任务迟迟得不到调度。但其他中等优先级的任务却能抢到CPU资源。– 从现象上来看，好像是中优先级的任务比高优先级任务具有更高的优先权。——信号量优先级反转（翻转）与优先级继承– kummer话你知- 简书

• 可能发生于任何基于优先级的可抢占的调度方案中
• 已在火星探路者中发生

例子

解决方案是，使用优先级继承：优先级较低的任务继承任何与其共享同一资源的优先级较高的任务的优先级。

解决方案

二(3) 进程管理：进程同步

并发的原理

日常生活现象

多道程序设计为什么需要同步？

• 进程是计算机中的独立个体，且具有异步性、并发性
• 资源是计算机中的稀缺个体，需共享，如CPU、内存、I/O设备
• 进程之间可能需要协作完成任务

相关概念

这些概念后面会经常用到，很重要。

• 原子操作：由一个或多个指令序列实现的动作或函数，对外不可见，一组指令要么都执行，要么都不执行。（数据库并发中的事务也有原子性）
• 临界资源：不可同时访问，必须互斥访问的资源，如打印机
• 临界区：访问临界资源的代码，任意时刻只能由一个进程在这段代码中运行
• 互斥：当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问共享资源的情形
• 忙等现象：当一个进程等待进入临界区时，它会继续消耗处理器的时间
• 活锁：两个或两个以上的进程为响应其他进程而持续改变自己状态，但是不做有用工作的情形
• 死锁：两个或两个以上的进程因等待其他进程做完某些事而不能继续执行的情形
• 竞争条件：多个进程或线程读写共享的数据时，结果取决于多个进程的指令执行顺序
• 饥饿：一个具备执行条件的进程，被调度程序无限期的忽视而不能调度的情形

忙等、饥饿和死锁

并发控制的产生

产生原因：

• 单处理器的交替执行和多处理器的重叠执行
  • 二者表达的是同样的问题——进程的相对执行速度不可预测，其取决于：
    • 其他进程的活动
    • 操作系统处理中断的方式
    • 操作系统的调度策略
• 进程执行的相对速度不可预测，给并发带来了困难
  • 资源共享充满了危险性
  • 操作系统需要优化管理资源的分配
  • 定位程序的设计错误很困难

如，两个进程共享 echo() （如下）可能会出现问题：

1
2
3
4
5
6
7

char chin;
void echo()
{
  chin = getchar()
  chout = chin;
  putchar(chout);
}

两端并行的 echo()

如图，设 chin、chout 均为全局变量。P1 程序输入 x，但由于 chin 被 P2 改变，P1 输出的是 y。

解决方法：控制对共享资源的访问，使得一个进程的功能和输出结果与执行速度无关。

于是，我们需要从进程的交互方式入手。不同的交互方式，并发控制问题不一样。

进程间的交互方式

进程间的关系：

• 竞争
• 通过共享合作
• 通过通信合作

进程间的竞争资源

• 进程间不知道彼此的存在
• 进程竞争使用同一资源时，它们之间会发生冲突
• 这类资源如：I/O设备、存储器、处理器、时钟

进程竞争资源时，并发控制面临三个问题：互斥、死锁、饥饿

进程间通过共享合作

• 多个进程共享一个变量、共享文件或数据库
• 一个进程的结果可能取决于从另一个进程获得的信息
• 进程知道其他进程也可能共享同一个数据，因此必须合作

进程通过共享合作时，并发控制面临四个问题：互斥、死锁、饥饿、数据一致性（比上面多一个数据一致性）

进程间通过通信合作

• 进程间通过通信完成同步和协调彼此活动
• 一个进程的结果可能取决于从另一个进程获得的信息
• 通信可由各种类型的消息组成，发送或接收消息的原语由操作系统或程序设计语言提供
• 不涉及对共享资源的访问

进程通过通信合作时，并发控制面临两个问题：死锁、饥饿

互斥

互斥的要求（访问临界区的原则）

• 空闲让进：如临界区空闲，则有进程申请就立即进入
• 忙则等待：每次只允许一个进程处于临界区（互斥）
• 有限等待：保证进程在有限时间内能进入临界区(不会死锁或饥饿)
• 让权等待：进程在临界区不能长时间阻塞等待某事件

本课程将从五个方面介绍互斥的实现，分别为软件方法、硬件方法、信号量、管程、消息传递。

互斥：软件方法

• 通过在进入区设置、检查一些标志来判断是否有进程在临界区
• 若已有进程在临界区，则在进入区通过循环检查进行等待
• 进程离开临界区后在退出区修改标志

初步设想——轮换使用临界区

使用 turn 变量实现轮换使用临界区。

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

// 共享的全局变量
int turn = 0;

// 进程 P0 的代码
P0()
{
  do {
    while (turn != 0);    //进入区
    // 进程P0的临界区代码;  //临界区
    turn = 1;             //退出区
    // 进程P0的其它代码    //剩余区
  } while (true);
}

//进程 P1 的代码
P1 ()
{
  do {
    while (turn != 1);    //进入区
    // 进程P1的临界区代码;  //临界区
    turn = 0;             //退出区
    // 进程P1的其它代码    //剩余区
  } while (true);
}

• 严格轮换，实现了互斥访问
• 在临界区外出错/被终止也会影响其他进程的执行
• 忙等（一切需要 while(true) 的代码均是忙等）
• 违反了“空闲让进”原则

看不懂加粗词的读者请往上搜索其定义。

第一次改进——设置临界区状态标志

使用 flag[2] 标记临界区的状态标志，发现对方的 flag 为 false 则进入临界区。

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

// 共享的全局变量,标志临界区是否可用
bool flag[2] = {false, false};       

// 进程 P0 的代码
P0()
{
  do {
    while (flag[1]);      //进入区
    flag[0] = true;
    // 进程P0的临界区代码;  //临界区
    flag[0] = false;      //退出区
    // 进程P0的其它代码    //剩余区
  } while (true);
}

//进程 P1 的代码
P1 ()
{
  do {
    while (flag[0]);      //进入区
    flag[1] = true;
    // 进程P1的临界区代码;  //临界区
    flag[1] = false;      //退出区
    // 进程P1的其它代码    //剩余区
  } while (true);
}

• 忙等
• 违反了“忙则等待”原则，互斥访问未实现（如果两段代码同时执行各自的 while 和各自的 flag[i]=true，二者会同时进入临界区）

第二次改进——预先表明进入临界区的态度

仍然使用 flag[2] 标记临界区的状态标志，但先修改自己的 flag，再查询对方的 flag，最后进入临界区。

这个方法实现了互斥，但如果双方同时执行到 while，会死锁。当然，仍然存在忙等。

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

boolean flag[2] = {false, false};   //共享的全局变量

// 进程P0
do {
    flag[0] = true;                 //进入区
    while (flag[1]);                //进入区
    // 进程P0的临界区代码；           //临界区
    flag[0] = false;                //退出区
    //进程P0的其它代码               //剩余区
} while (true);

// 进程P1
do {
    flag[1] = true;                 //进入区
    while (flag[0]);                //进入区
    // 进程P1的临界区代码；           //临界区
    flag[1] = false;                //退出区
    //进程P1的其它代码               //剩余区
} while (true);

第三次改进——谦让

上面的问题是因为修改了自己的 flag 然后死等对方的 flag，等不到就一直等，结果两个人互等。

这次改成，等不到就暂时释放自己的 flag，等一会后再改回来。

这个方案实现了互斥，且未死锁，但是有长时间僵持的可能性（这是因为可能相互谦让）。

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

boolean flag[2] = {false, false};    //共享的全局变量

//进程P0
do {
    flag[0] = true;                 
    while (flag[1]) {              
        flag[0] = false;             //谦让
        //随机延迟一小段时间；
        flag[0] = true;
    }
    //进程P0的临界区代码；             //临界区
    flag[0] = false;                 //退出区
    //进程P0的其它代码                 //剩余区
} while (true);

//进程P1
do {
    flag[1] = true;                 
    while (flag[0]) {              
        flag[1] = false;             //谦让
        //随机延迟一小段时间；
        flag[1] = true;
    }
    //进程P1的临界区代码；             //临界区
    flag[1] = false;                 //退出区
    //进程P1的其它代码                 //剩余区
} while (true);

Dekker 互斥算法—— flag 冲突时根据 turn 裁定

为回避刚才相互谦让的问题，Dekker 算法使用 turn 来裁定，当双方的 flag 冲突的时候，应该谁先访问。同时，当一方访问完临界区后，需将 turn 和 flag 都让出去。

这个算法实现了互斥、无死锁，但仍然为忙等。

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

boolean flag[2] = {false, false};   //共享的全局变量
int turn = 1;                       //共享的全局变量

// 进程P0
do {
    flag[0] = true;                 //进入区
    while (flag[1]) {
       if (turn == 1) {
            flag[0] = false;
            while  (turn == 1) ;     //等待
            flag[0] = true;
        }
     }                              //进入区
    // 进程P0的临界区代码；           //临界区
    turn = 1;                       //将 turn 让出去
    flag[0] = false;                //退出区
    // 进程P0的其它代码              //剩余区
} while (true);

// 进程P1
do {
    flag[1] = true;                 //进入区
    while (flag[0]) {
       if (turn == 0) {
            flag[1] = false;
            while  (turn == 0) ;     //等待
            flag[1] = true;
        }
     }                              //进入区
    // 进程P1的临界区代码；           //临界区
    turn = 0;                       //将 turn 让出去
    flag[1] = false;                //退出区
    // 进程P1的其它代码              //剩余区
} while (true);

Peterson 互斥算法——先把 turn 让给对方

Dekker 在 flag 冲突时才使用 turn 裁定，而 Peterson 互斥算法，就是在开始的时候直接先把 turn 让给对方，再判断对面是不是拥有 turn==i 和 flag[i] 二者。

Peterson 算法较 Dekker 算法的显著优点是算法更简洁，对应的代码行数更短。

这个算法实现了互斥、无死锁，但仍然为忙等。

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

boolean flag[2] = {false, false};      //共享的全局变量
int turn;                              //共享的全局变量
//进程P0
do {
    flag[0] = true;                    //进入区
    turn = 1;                          //进入区
    while (flag[1] && turn == 1);     //进入区
    // 进程P0的临界区代码；             //临界区
    flag[0] = false;                   //退出区
    // 进程P0的其它代码                //剩余区
} while (true);

//进程P0
do {
    flag[1] = true;                    //进入区
    turn = 0;                          //进入区
    while (flag[0] && turn == 0);     //进入区
    // 进程P1的临界区代码；             //临界区
    flag[1] = false;                   //退出区
    // 进程P1的其它代码                //剩余区
} while (true);

总结

对于软件方法：

• 始终不能解决“忙等”现象
• 实现互斥比较困难
• 通常能实现两个进程的互斥，很难控制多进程互斥
• 算法设计需非常小心，否则可能出现死锁、互斥失败等

以上算法中，Dekker 和 Peterson 算法都较好地在软件方法上实现了两进程互斥。

互斥：硬件方法

硬件方法如下：

• 中断禁用
• 机器指令
  • compare & swap
  • Exchange

中断禁用

中断禁用（屏蔽中断）可用于单处理器系统。通过禁用中断，避免进程切换，简单粗暴地实现了互斥访问。

其缺点有：

• 无法响应其他外部请求，且无法切换进程，执行效率明显下降
• 在多处理器环境不能实现互斥（多个进程在多个处理器下并行执行）

1
2
3
4
5
6

while (true) {
    disable interrupt    //屏蔽中断
    critical section     //临界区
    enable interrupt     //启用中断
    remainder            //其余部分
}

专用机器指令

在多处理器环境中，几个处理器共享访问公共主存。处理器表现出一种对等关系，不存在主/从关系（对称多处理器）。

处理器之间没有支持互斥的中断机制。因此，处理器的设计者提出了一些机器指令，用于保证两个动作的原子性（如在一个周期中对一个存储器单元的读和写）。

这些动作在一个指令周期中执行，不会被打断，不会受到其他指令的干扰。

compare & swap 指令

比较和交换指令 compare & swap 用于比较一个内存单元的值和一个测试值，如果相等，则发生交换。

1
2
3
4
5
6

int compare_and_swap(int *word, int testval, int newval)
{
    int oldval = *word;
    if(oldval == testval) *word = newval;
    return oldval;
}

该指令总是返回旧内存值。因此，如果返回值与测试值相同，则表示该内存单元已被更新。

这个原子指令由两部分组成：比较内存单元值和测试值；值相同时产生交换。整个比较和交换功能按原子操作执行，即它不接受中断。

这个指令的另一个版本返回一个布尔值：交换发生时为真，否则为假。几乎所有处理器家族（x86、IA64、sparc 和 IBMz 系列等）都支持该指令的某个版本，且多数操作系统都利用该指令支持并发。

下面是操作系统使用 compare_and_swap 实现并发互斥的一个方案。

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

int bolt;

void P(int i)
{
    while (true)
    {
        // 一共只有一个 0，所有进程可以用手里的 1 尝试换 0 。哪个进程抢到了 0 就该谁执行
        while(compare_and_swap(&bolt, 0, 1) == 1); // 进入区
        // 临界区代码
        bolt = 0; //退出区
        // 剩余区代码
    }
}

void main()
{
    bolt = 0;
    parbegin(P(1), P(2), ..., P(n)); // 阻塞主程序，初始化并行过程 P1, P2, ..., Pn；全部终止之后，才恢复主程序的执行
}

Exchange 指令

1
2
3
4
5
6
7

procedure exchange(var r: register; var m: memory);
    var temp;
    begin
        temp := m;
        m := r;
        r := temp;
    end

下面是操作系统使用 exchange 实现并发互斥的一个方案。

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

int bolt;

void P(int i)
{
    while (true)
    {
        int keyi = 1;
        // 一共只有一个 0，所有进程可以用手里的 1 尝试换 0 。哪个进程抢到了 0 就该谁执行
        do exchange (&keyi, &bolt)
        while (keyi == 1);
        // 临界区代码
        bolt = 0; //退出区
        // 剩余区代码
    }
}

void main()
{
    bolt = 0;
    parbegin(P(1), P(2), ..., P(n)); // 阻塞主程序，初始化并行过程 P1, P2, ..., Pn；全部终止之后，才恢复主程序的执行
}

信号量

信号量、管程 都是提供互斥的方案。

引言

交通信号灯：红灯停，绿灯行

信号量实现互斥与同步的基本原理：

两个或多个进程可以通过传递信号进行合作：迫使进程在某个位置暂时停止执行（阻塞），直到它收到一个可以“向前推进”的信号（被唤醒）。

实现信号灯作用的变量被称为信号量。

定义

信号量 Semaphore 可视为一个值为整数的变量。具有三个操作：

1. 一个信号量可以初始化为非负数
2. semWait （Wait或P）操作使信号量的值减少1，若值变为负数，则阻塞执行 semWait 操作的进程
3. semSignal（Signal或V）操作使信号量的值增加1，若值小于等于零，则被 semWait 阻塞的进程解除阻塞

除了这三个操作外，没有其他方法可以检查或操作信号量。

顺便，P 和 V 并称为 PV 操作。

分类

信号量分为二元信号量（信号量的值只能是0或1）和计数信号量（非二元信号量/一般信号量）

二元信号量的定义及semWait和semSignal原语操作

一般信号量的定义及semWait和semSignal原语操作

上述二者都使用队列来组织等待信号量的进程。

• 强信号量：进程以FIFO方式从队列里移除
• 弱信号量：未规定阻塞进程从队列里移除的顺序

(强)信号量机制示例：设进程A、B、C依赖于进程D的结果，s初始为1，表示D的一个结果可用

(强)信号量机制示例

信号量解决互斥问题

使用信号量能解决互斥问题，只需要给需要互斥的区域加一个信号量 s，访问前 P，访问后 V 即可。

信号量解决互斥问题

例：进程A、B、C访问受信号量lock保护的共享资源

进程A、B、C访问受信号量lock保护的共享资源

信号量的实现

P 和 V 应作为原语实现。即，任意时刻只能有一个进程用 P 和 V 来操作控制信号量。

一种方案是用硬件或固件实现。另一种方案是采用硬件指令支持来保证进程互斥使用 P 和 V 操控信号量。

信号量的两种可能实现（左为compare&swap，右为中断禁用）

上例中，共享资源数量为 1。进一步地，可扩展为共享资源数量为多个或共享资源允许多个进程同时访问的情况：

在任何时候，信号量里 count 值可以解释如下：

• s.count ≥ 0 时，s.count 表示执行 P(s) 操作而不被阻塞的进程数（可看作可用资源数）。这种情形信号量可支持同步与互斥。
• s.count < 0时，s.count 表示阻塞在 s.queue 队列上的进程数。

四大经典同步问题

• 生产者/消费者
• 理发师
• 读/写者
• 哲学家就餐

生产者/消费者问题

生产者与消费者问题：

• 一个或多个生产者产生数据并放入缓冲
• 每次只能有一个消费者从缓冲中取出数据（互斥）
• 任何时候只能由一个生产者或消费者访问缓冲（互斥）

需解决同步问题：

• 保证缓冲区满时，生产者不会往缓冲区中增加数据
• 保证缓冲区空时，消费者不能从缓冲区中取走数据

– Dijkstra

程序框图

生产者/消费者问题使用信号量的一个实现如下：

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

/*program bounded_buffer*/
const sizeofbuffer =…;   /*  缓冲区大小  */
var s : semaphore(:= 1); /* 用以互斥的信号量s，初始化为1 */
    n : semaphore(:= 0); /* 表示资源的信号量n，表征数据单元数量，初始化为0 */ 
    e : semaphore(:= sizeofbuffer); /* 表示资源的信号量e，表征空存储单元数量 */

procedure producer ;                procedure consumer ;
begin                               begin      
    repeat                              repeat 
        /*produce a item*/                  semWait(n);
        semWait(e);                         semWait(s);
        semWait(s);                         /*get a item*/； 
        /*store a item*/                    semSignal(s); 
        semSignal(s);                       semSignal(e);
        semSignal(n)；                      /*consume a item*/
    forever                             forever
end;                                end;

begin    /* 主程序 */
    parbegin   producer ; consumer ; parend
end.

上段代码使用了三个信号量：

• s：表示生产者、消费者之间的互斥
• e：表示空间资源量（放满了产品，就没有空间了）
• n：表示产品资源量

很有意思的是，生产者、消费者是对偶的关系。生产者需要空间，生产产品；消费者需要产品，“生产”空间。所以最简单的生产者/消费者问题中，二者的代码是很类似的。

注意：

1. 应先申请资源信号量，再申请互斥信号量，顺序不能颠倒，否则可能导致死锁！（由于所有生产者、消费者共用一个互斥信号量，拿到了就得赶紧用，不然别人都会等你。或者说，互斥信号量应该是最后申请的信号量）

可能出现死锁

2. 释放信号量的顺序应该是“先申请的后释放”。如果 producer 改为先释放 n 再释放 s，被阻塞在 P(n); 的消费者接收到 n 以后可能会被再次阻塞在 P(s)。

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

// 错误的 producer 示例
procedure producer ;                procedure consumer ;
begin                               begin      
    repeat                              repeat 
        /*produce a item*/                  semWait(n);
        semWait(e);                         semWait(s); 
        semWait(s);                         /*get a item*/； 
        /*store a item*/                    semSignal(s); 
        semSignal(n);                       semSignal(e);
        semSignal(s)；                      /*consume a item*/
    forever                             forever
end;                                end;

3. 对于同一个信号量的 wait 与 signal 操作，既可以出现在同一个进程中，也可以出现在不同进程中（如 n 和 e）。
4. 但是，对任何信号量的 wait 与 signal 操作必须配对。
5. wait与signal语句不能颠倒顺序，wait语句一定先于signal语句执行，对吗？

不对，应为：在进入临界区前必须先执行wait操作，退出临界区后必须执行signal操作。对于同步信号量而言，既有可能先执行wait操作，也有可能先执行signal操作。

示例一

• 桌子上有一只盘子，最多可以放入 N (N>0) 个水果；
• 爸爸随机向盘中放入苹果或桔子。儿子只吃盘中的桔子，女儿只吃盘中的苹果；
• 只有盘子中水果数目小于 N 时，爸爸才可以向盘子中放水果；
• 仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果；
• 每次只能放入或取出一个水果，且不允许多人同时使用盘子。

用信号量机制实现爸爸、儿子和女儿之间的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

分析：

• 一个生产者和两个消费者被连接到大小为 N 的缓冲区上；
• 盘子是一互斥资源（不能同时访问），故设置访问盘子的互斥信号量 mutex；
• 爸爸、儿子因为桔子的放入与取出而同步，设置产品资源信号量orange；
• 爸爸、女儿因为苹果的放入与取出而同步，设置产品资源信号量apple；
• 爸爸、儿子、女儿因为共享盘子空间，设置空间资源信号量empty。

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

semaphore mutex = 1;                       //盘子操作互斥信号量
semaphore apple = 0, orange = 0;           //苹果、桔子放入、取出的资源信号量
semaphore empty = N;                       //盘子中可放入的水果数目

father()
{
    while (true) {
        result=prepare_fruit();            //准备水果，result为水果类型
        P(empty);                          //盘子中可放入的水果数目减1
        P(mutex);                          //互斥访问盘子
        put a fruit on the plate();        //将一个水果放入盘子
        V(mutex);                          //恢复访问盘子
        if (result == apple)               //准备的水果为苹果
            V(apple);                      //允许女儿取苹果
        else                               //准备的水果为桔子
            V(orange);                     //允许儿子取桔子
    }
}

son() {
    while (true) {
        P(orange);                         //判断是否可取桔子
        P(mutex);                          //互斥访问盘子
        get an orage from plate();         //取桔子
        V(mutex);                          //恢复访问盘子
        V(empty);                          //盘子中可放入的水果数目加1
    }
}

daughter() {
    while (true) {
        P(apple);                          //判断是否可取苹果
        P(mutex);                          //互斥访问盘子
        get an apple from plate();         //取苹果
        V(mutex);                          //恢复访问盘子
        V(empty);                          //盘子中可放入的水果数目加1
    }
}

P() 等价于 wait()，V() 等价于 signal()，后面就使用 P 和 V 了。

有意思的是，如果将原题的 N 改为 1，即盘子只有一个容量，就不需要 mutex 互斥信号量了，因为不会出现一边爸爸在放水果，另一边儿子/女儿在吃的情况。

下面的例二就是这种情况，可以省下一个 mutex 信号量。

示例二

• 桌子上有一只盘子，爸爸负责向盘中放苹果，妈妈负责向盘中放桔子；
• 儿子只吃盘中的桔子，女儿只吃盘中的苹果；
• 只有盘子为空时，爸爸或妈妈才可以向盘子中放入一个水果；
• 仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果。

请用信号量机制实现爸爸、妈妈、儿子和女儿之间的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

分析：

• 两个生产者和两个消费者被连接到大小为1的缓冲区上；
• 盘子是一互斥访问的空间资源，故设置资源信号量plate；
• 爸爸、女儿因为苹果的放入与取出而同步，设置产品资源信号量apple；
• 妈妈、儿子因为桔子的放入与取出而同步，设置产品资源信号量orange。
• 这里不需要 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
35

semaphore plate = 1;                       //是否允许向盘子放入水果
semaphore apple = 0, orange = 0;           //盘子中是否有苹果、桔子

dad() {
    while (true) {
        prepare an apple;
        P(plate);                          //互斥向盘子放水果
        put an apple on the plate;         //将苹果放入盘中
        V(apple);                          //允许取苹果
    }
}
mom() {
    while (true) {
        prepare an orange;
        P(plate);                          //互斥向盘子放水果
        put an orange on the plate;        //将桔子放入盘中
        V(orange);                         //允许取桔子
    }
}

son() {
    while (true) {
        P(orange);                         //互斥取水果
        get an orange from the plate;      //从盘中取出桔子
        V(plate);                          //允许向盘中放入水果
    }
}

daughter() {
    while (true) {
        P(apple);                          //互斥取水果
        get an apple from the plate;       //从盘中取出苹果
        V(plate);                          //允许向盘中放入水果
    }
}

示例三

• 桌子上有一只盘子，最多可以放入2个水果；
• 爸爸负责向盘中放苹果，妈妈负责向盘中放桔子，女儿负责取出并消费水果；
• 放入者和取出者不允许同时使用盘子（两个生产者可以同时访问盘子）；
• 当且仅当盘子中同时存在苹果和桔子时，女儿才从盘子中取出并消费水果。

请用信号量机制实现爸爸、妈妈和女儿之间的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

分析：

由题意，盘子上最多只能出现一个苹果（要是出现两个苹果，那就没地方放桔子了）和一个桔子。因此，可以把盘子“分为”两个盘子，一个是用来放苹果的盘子，一个是用来放桔子的盘子。

这样做以后，又可以省下 mutex 信号量，其原因和示例二省下 mutex 的原因相同。

• 两个生产者和一个消费者被连接到大小为2的缓冲区上
• 盘子中是否可以放入苹果，设置空间资源信号量empty_apple；
• 盘子中是否可以取出苹果，设置产品资源信号量apple；
• 盘子中是否可以放入桔子，设置空间资源信号量empty_orange；
• 盘子中是否可以取出桔子，设置产品资源信号量orange。

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

semaphore apple = 0, orange = 0;                //盘子中是否有苹果、桔子
semaphore empty_apple = 1, empty_orange = 1;    //盘子是否可放入苹果、桔子

dad(){
    while (true) {
        prepare an apple;
        P(empty_apple);                         //盘子中是否可放入苹果
        put an apple on the plate;              //将一个苹果放入盘子
        V(apple);                               //允许女儿取苹果
    }
}
mom(){
    while (true) {
        prepare an orange;
        P(empty_orange);                        //盘子中是否可放入桔子
        put an orange on the plate;             //将一个桔子放入盘子
        V(orange);                              //允许女儿取桔子
    }
}


daughter() {
    while (true) {
        P(apple);                               //盘子中是否有苹果
        P(orange);                              //盘子中是否有桔子
        get an apple and an orange from plate();//取水果
        V(empty_apple);                         //盘子中可以放入苹果
        V(empty_orange);                        //盘子中可以放入桔子
    }
}

示例四

女儿负责画画，爸爸、妈妈负责欣赏。女儿在白板上画完一幅画后，请爸爸、妈妈均欣赏过一遍后，再创作新画，依次重复。请用信号量机制实现女儿、爸爸和妈妈之间的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

另一种描述方法：一个生产者进程和两个消费者进程共享大小为1的缓冲，当且仅当缓冲为空时，生产者进程负责放入数据，当且仅当缓冲有数据时，消费者读数据，只有当两个消费者都读取数据后，生产者才能删除原有数据并继续生产下一个数据。

分析：

此题和示例三类似：示例三中，两个生产者的产品被一个消费者同时消费后才能继续生产；此题中，一个生产者的产品同时被两个消费者消费后才能继续生产。

解决的方案也类似，将这幅画“分为”给爸爸看的话和给妈妈看的画，分别设置空间资源量和产品资源信号量。

• 爸爸是否欣赏过，设置空间资源信号量empty_dad；
• 爸爸是否可以欣赏，设置产品资源信号量full_dad；
• 妈妈是否欣赏过，设置空间资源信号量empty_mom；
• 妈妈是否可以欣赏，设置产品资源信号量full_mom。

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

semaphore empty_dad = 1, empty_mom = 1;         //爸爸、妈妈是否已看过女画的新画
semaphore full_dad = 0, full_mom = 0;           //是否存在可供爸爸、妈妈看的新画


daughter(){
    while (true) {
        P(empty_dad);                           //爸爸是否看过
        P(empty_mom);                           //妈妈是否看过
        draw a new picture on the whiteboard;   //画一幅新画
        V(full_dad);                            //爸爸可以看了
        V(full_mom);                            //妈妈可以看了
    }
}


dad() {
    while (true) {
        P(full_dad);                            //白板上是否存在没有看过的画
        enjoy the picture on the whiteboard;    //看画
        V(empty_dad);                           //爸爸已看过新画
    }
}

mom() {
    while (true) {
        P(full_mom);                            //白板上是否存在没有看过的画
        enjoy the picture on the whiteboard;    //看画
        V(empty_mom);                           //妈妈已看过新画
    }
}

读者/写者问题

问题描述：

多个进程访问一个共享数据区（可为文件、内存空间、寄存器）。其中若干读进程只能读数据，若干写进程只能写数据。

为数据库、文件、内存区及一组寄存器等的数据访问问题建立了一个通用模型。
示例——联网售票系统、12306
在该系统中，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改（读/写）其中某一条数据的情形。

• 问题的三种角色：
  • 读进程
  • 写进程
  • 共享数据
• 问题的三个条件：
  • 同时读
  • 同时写
  • 互斥读写

读者/写者问题和生产者/消费者问题的区别：

1. 读/写者的数据可多次读，生产/消费者的数据消费完后就没有了
2. 读者彼此不互斥，消费者彼此互斥

读者优先

思想：

• 一旦有读者正在读数据，则允许随后的读者进入读数据
• 只有当全部读者退出，才允许写者进入写数据
• 导致写者饥饿

变量设置:

• wsem：互斥信号量，用于Writers间互斥、Writers和Readers互斥
• readcount：统计正在同时读数据的Readers个数
• x：对变量readcount互斥算术操作

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

int readcount=0；
semaphore x = 1, wsem=1;
void reader() { 
    while (1) {
        P(x);
        readcount++;
        if (readcount==1) P(wsem); // 思考：这句 if 能不能放到下一行的 V(x) 之后？
        V(x);
        READ;
        P(x);
        readcount--;
        if (readcount==0) V(wsem);
        V(x);
    }
}
void writer() {
    while (1) {
        P(wsem);
        WRITE;
        V(wsem);
    }
}

算法核心：wsem 就像是一道防线，每次只会放一个人进去。所有的 Writers 会受其控制；但对于 Readers，仅当里面没有 Readers 的时候才会受其控制。

思考：不可以。对 readcount 的读写操作都需要拿到互斥量。反例就是，如果进程 A 写完 readcount 以后释放 x，准备读 readcount 时被 OS 中断，OS 转而调度 B 进程修改了 readcount，之后 A 进程读到的值就不是原先 A 写的值。

考虑如下进程序列(设序列中从右到左为进程先后到达顺序)，哪种情况下可能存在写者饥饿

1. R R R
2. W W W
3. R W
4. R R W
5. R R W R
6. W W R
7. W R R W

第五个存在写者饥饿，因为由于 W 前正在读操作，W 后的 R 可以插队到 W 之前。

公平优先

这个就比之前的复杂了。

这个算法的核心思想是：连续的 Reader 可以同时读，但是 Reader 不允许插队到 Writer 之前（读者优先就是读者插队导致了写着饥饿）。

变量设置：

• wrsem：互斥信号量，确定Writer 、Reader请求顺序
• wsem：互斥信号量，用于Writers间互斥，Reader互斥Writers
• readcount：统计同时读数据的Readers个数
• x：对变量readcount互斥算术操作

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

int readcount=0, semaphore x=l, wrsem=1, wsem=l;

void reader() {
    while (true) {
        P(wrsem);
        P(x);
        readercount++;
        if (readercount == 1) P(wsem);
        V(x);
        V(wrsem);     // 思考 1：这句能放在第五行 P(wrsem) 之后吗？
        READ;
        P(x);
        readercount--;
        if (readercount == 0) V(wsem);
        V(x);
    }
}

void writer() {
    while (true) {
        P(wrsem);
        P(wsem);
        WRITE;
        V(wsem);
        V(wrsem);      // 思考 2：这句不能放在 WRITE 之前吗？
    }
}

• 第一道防线：wrsem，W、R均要排队，保证公平
• 第二道防线：wsem（拦所有 W 和第一个 R）
• 系统保证，一、二道防线之间最多只有一个人
• 当某 R 进入第一道防线后，若第二道防线内没人或只有 R，则可以进入，否则需 P(wsem)
• 当某 W 进入第一道防线后，仅若第二道防线内没人，才可以进入，否则需 P(wsem)
• 当某 R 进入第二道防线后，会把第一道防线打开
• 当某 W 进入第二道防线后，不会打开第一道防线；只有当 W 走的时候才会打开两道防线

思考 1：不可以。否则如果这个 R 后面是一个 W，W 可能（由于系统调度的原因）抢先完成 P(wrsem) P(wsem) 并开始写，之后 R 开始执行 if (readercount == 1) P(wsem);，最后就是结果这个 W 比 R 先做任务。

思考 2：从原理上说是可以的。原算法中，某 W 进入第二道防线后，不会打开第一道防线；修改以后，W 进入第二道防线以后就会打开第一道防线。但考虑到接下来进入第一道防线的 W/R 仍然需要等待第二道防线，和修改之前没有区别，修改后还会导致这个 W/R 被二次阻塞，所以从效率上说，不推荐修改。

考虑从右到左先后到达顺序的进程序列：R, R, W, R, R……

写者优先

这个似乎比上面那个还复杂。

这个算法的思想是，当 Writers 正在写时，其他 W 可以插队到 R 之前排队。

变量设置：

• wsem：互斥信号量，用于Writers间互斥，Reader互斥Writers
• readcount：统计同时读数据的Readers个数
• x：对变量readcount互斥算术操作
• rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据。
• 第一个写者受rsem影响，一旦有第一个写者，后续写者不受rsem其影响。但是读者需要在rsem上排队。
• writecount：用于控制rsem信号量
• y：对变量writecount互斥算术操作

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

int readcount = 0, writecount = 0;
semaphore x=1, y=1, wsem=1, rsem=1;

void reader( ) {
    while (1) {
        P(rsem);
        P(x);
        readcount++;
        if (readcount==1) P(wsem);
        V(x);
        V(rsem)；
        READ;
        P(x);
        readcount--;
        if (readcount==0) V(wsem);
        V(x);
    }
 }

void writer( ) {
    while (1) {
        P(y);
        writecount++;
        if (writecount==1) P(rsem);
        V(y);
        P(wsem);
        WRITE;
        V(wsem);
        P(y);
        writecount--;
        if (writecount==0) V(rsem);
        V(y);
    }
}

• 第一道防线：rsem，拦所有 R 和第一个 W
• 第二道防线：wsem，拦所有 W 和第一个 R
• 当某 W 进入第一道防线，后面的 W 均可进入第一防线，所有 R 均被拦住
• 当某 R 进入第一道防线，如果是进入的第一个 R 则需要拿到 wsem 不让后面的 W 写；随后放开第一道防线 rsem，让后面的 W/R 进入
  • 如果进入的是 R，则可以进入第二道防线，一起读，顺便释放 rsem 再放一个人进来；
  • 如果进入的是 W，则之后的 W 均不需要等待第一道防线；对于第二道防线，需要等待最后一个 R wsem 才能进入。

设每个序列最右为队首：

1. R R W R
2. R R W
3. W R R W
4. W R R R R

对于第四个，即使是写者优先，W 仍然需要等待四个 R 读完才能写。

写者优先改进

于是，又提出了写者优先改进，其在写者优先的基础上只加了第六行 P(z); 和第十三行 V(z);。

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

int readcount = 0, writecount = 0;
semaphore x=1, y=1, wsem=1, rsem=1;

void reader( ) {
    while (1) {
        P(z);
        P(rsem);
        P(x);
        readcount++;
        if (readcount==1) P(wsem);
        V(x);
        V(rsem)；
        V(z);
        READ;
        P(x);
        readcount--;
        if (readcount==0) V(wsem);
        V(x);
    }
 }

void writer( ) {
    while (1) {
        P(y);
        writecount++;
        if (writecount==1) P(rsem);
        V(y);
        P(wsem);
        WRITE;
        V(wsem);
        P(y);
        writecount--;
        if (writecount==0) V(rsem);
        V(y);
    }
}

z 只对 reader 起作用，使得只能有一个 R 在 rsem 上排队（而这个 R 手上拿了 z），其余 R 均需在 z 上排队；这样，在 rsem 上排队的 W 前面最多只会出现一个 R，而避免了在 rsem 上形成长队列（指 R 的长队列）。

示例一

有一座东西方向的独木桥，每次只能有一人通过，且不允许行人在桥上停留。东、西两端各有若干行人在等待过桥。请用P、V操作来实现东西两端行人过桥问题。

这个例子只允许一个人在桥上，即所有人都是写者。就是一个最基础的人人之间均互斥。

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

semaphore s = 1;            //互斥信号量

void east_west( )
{
    while (true) {
        P(s);               //互斥其他人过桥
        //行人从东向西过桥
        V(s);               //允许其他人过桥
    }
}

void west_east( )
{
    while (true) {
        P(s);               //互斥其他人过桥
        //行人从西向东过桥
        V(s);               //允许其他人过桥
    }
}

示例二

有一座东西方向的独木桥，同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待。桥上没有行人过桥时，任何一端的行人均可上桥。请用 PV 操作来实现东西两端人过桥问题。

同方向行人可连续过桥，可以把这群人看做读者。那么，哪个方向是读者呢？谁先上谁就是读者，妙啊！

• x：互斥信号量，用于读者互斥写者
• countA、countB：统计读者数目（同时在桥上的行人数目）
• mutexA、mutexB：对变量countA、countB互斥算术操作

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

int countA=0, countB=0；
semaphore x=1, mutexA=1, mutexB=1;

void east_west() { 
    while (1) {
        P(mutexA);
        countA++;
        if (countA==1) P(x); 
        V(mutexA);
        walk across the bridge from east to west;
        P(mutexA);
        countA--;
        if (countA==0) V(x);
        V(mutexA);
    }
}

void west_east() { 
    while (1) {
        P(mutexB);
        countB++;
        if (countB==1) P(x); 
        V(mutexB);
        walk across the bridge from west to east;
        P(mutexB);
        countB--;
        if (countB==0) V(x);
        V(mutexB);
    }
}

只有当一个人是这个方向上第一个上桥的人，他才需要等待 x，就能保证第一个上桥的那个方向的其他人也能上桥，而反方向的人就得等这些人走完桥。

示例三

有一座东西方向的独木桥，同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待。桥上没有行人过桥时，任何一端的行人均可上桥。出于安全考虑，独木桥的最大承重为4人，即同时位于桥上的行人数目不能超过4。请用 PV 操作来实现东西两端人过桥问题。

这个简单，在示例四中加一个初始化为 4 的信号量 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
28
29
30
31
32
33
34

int countA=0, countB=0；
semaphore x=1, mutexA=1, mutexB=1, count=4;

void east_west() { 
    while (1) {
        P(mutexA);
        countA++;
        if (countA==1) P(x); 
        V(mutexA);
        P(count);
        walk across the bridge from east to west;
        V(count);
        P(mutexA);
        countA--;
        if (countA==0) V(x);
        V(mutexA);
    }
}

void west_east() { 
    while (1) {
        P(mutexB);
        countB++;
        if (countB==1) P(x); 
        V(mutexB);
        P(count);
        walk across the bridge from west to east;
        V(count);
        P(mutexB);
        countB--;
        if (countB==0) V(x);
        V(mutexB);
    }
}

理发师问题

理发店有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。如果没有顾客，则理发师睡觉。当一个顾客到来时，他必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他就离开。

理发师和顾客工作流程

就是注意各种状态的信号量，按照流程图话就完事了。

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

int n_customer= 0;      //店里的顾客,含正在理发的人数
semaphore mutex = 1;    //waiting的互斥信号量
semaphore bchair = 1;   //理发椅的个数
semaphore wchair = 5;   //空椅子的个数
semaphore ready = 0;    //是否有顾客准备好
semaphore finish = 0;   //理发师是否完成理发

main() { cobegin baber(); customer(); coend }

void baber()            //理发师进程
{
    while (true)
    {
        P(ready);       //有顾客准备好了
        // 理发
        V(finish);      //允许其他顾客理发
    }
}
void customer()
{
    P(mutex);           //互斥waiting变量的操作
    if (n_customer < 6) //店里顾客数没达上限
    {
        n_customer++;   //店里顾客数增1
        V(mutex);       //允许waiting变量的操作
        P(wchair);      //找一个空椅子坐下
        P(bchair);      //再找理发椅坐下
        V(wchair);      //释放一个空椅子
        V(ready);       //该顾客准备好了
        P(finish);      //等待理发师完成理发
        V(bchair);      //离开理发椅
        P(mutex);       //互斥waiting变量的操作
        n_customer--;   //等待顾客数减1
        V(mutex);       //允许waiting变量的操作  
    }
    else
    {
        // 离开
        V(mutex);
    }
}

理发师睡觉问题的类似问题：

某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

1
2
3
4

cobegin{    
    process 顾客i{从取号机上获取一个号码; 等待叫号; 获取服务; }
    process 营业员{while (true){叫号; 为顾客服务; }}
}

请添加必要的信号量和 PV 操作，实现上述过程中的互斥与同步。要求写出完成的过程，说明信号量的含义并赋初值。

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

semaphore mutex = 1;    //互斥使用取号机的信号量
semaphore empty = 10;   //空座位的数量信号量
semaphore full = 0;     //已占座位的数量信号量
semaphore service = 0;  //等待叫号信号量

process 顾客i
{
    P(empty);
    P(mutex);
    //从取号机获得一个号；
    V(mutex);
    V(full);
    P(service);         //等待叫号
}

process 营业员
{
    while (true) {
        P(full);
        V(empty);
        V(service);     //叫号
        //为顾客服务;
    }
}

都比较简单，较之前的生产者/消费者和读者/写者问题简单了很多。

管程

信号量、管程 都是提供互斥的方案。

管程的引入

信号量可以高效的实现进程间互斥与同步，但是信号量的 PV 操作可能分散在整个程序中，使用难度高。

管程 monitor 是一个程序设计语言结构，采用了集中式的进程同步方法，提供了与信号量同样的功能，但更易于控制。

很多程序设计语言都支持管程，如 Pascal、Java 等。

管程的概念

一个管程定义了一个共享数据结构和能为并发进程所执行（在该数据结构上）的一组操作/过程，这组操作能同步进程、改变管程中的数据。

共享数据结构是对系统中共享资源的抽象。对该共享数据结构的操作则定义为一组过程，通过调用这些过程实现对共享资源的申请、释放和其它操作

管程 = 局部数据 + 过程 + 初始化序列

管程的特点

1. 局部数据变量只能被管程的过程访问，任何外部过程都不能访问
2. 一个进程通过调用管程的一个过程进入管程
3. 在任何时候，只能有一个进程在管程中执行（互斥），调用管程的任何其它进程都被阻塞，以等待管程可用。
4. 若由于某种原因，一个正在管程中执行的进程必须阻塞，该如何处理？——释放管程，供其它进程使用

如果管程内的数据结构代表了共享资源,则通过管程提供了对资源的互斥访问机制。

用管程实现进程同步

管程通过使用条件变量提供对进程同步的支持。条件变量包含在管程中，只能在管程中访问。

操作条件变量的两个函数：

1. cwait(c)：调用进程的执行在条件 c 上阻塞，管程可供其它进程使用。
2. csignal(c)：恢复在条件 c 上阻塞的一个进程，若不存在阻塞进程，则什么都不做。

这里的 cwait 和 csignal 作用于条件变量,与作用于信号量的 wait 和 signal 不同。

所以条件变量是什么呢？继续往后看。

管程的结构

管程的结构

生产者/消费者问题的管程解决方法

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
51
52

/* program producerconsumer */
monitor boundedbuffer;
char buffer [N];                        /* space for N items */
int nextin, nextout;                    /* buffer pointers */
int count;                              /* number of items in buffer */
cond notfull, notempty;                 /* condition variables for synchronization */

void append (char X)
{
    if (count == N) cwait(notfull);     /* buffer is full; avoid overflow */
    buffer[nextin] = x;
    nextin = (nextin + 1) % N;
    count++;                            /* one more item in buffer */
    csignal(notempty);                 /* resume any waiting consumer */
}

void take (char x)
{
    if (count == 0) cwait(notempty);    /* buffer is empty; avoid underflow */
    x = buffer[nextout];
    nextout = (nextout + 1) % N;
    count--;                            /* one fewer item in buffer */
    csignal(notfull);                   /* resume any waiting producer */
}

/* monitor body */
{
    nextin = 0; nextout = 0; count = 0; /* buffer initially empty */
}

void producer()
{
    char x;
    while (true)  {
        produce(x); 
        append(x);
    }
}

void consumer
{
    char x;
    while (true) {
        take(x);
        consume(x);     
    }
}

void main
{
    parbegin (producer, consumer);
}

看完以后还没有弄懂 hhhh 所以就照搬教材上的话了：

生产者可以通过管程中的过程 append 向缓冲区中增加字符，它不能直接访问 buffer。该过程首先检查条件 notfull，以确定缓冲区是否还有可用空间。如果没有，执行管程的进程在这个条件上被阻塞。其他的某个进程(生产者或消费者)现在可以进入管程。此后，当缓冲区不再满时，被阻塞进程可以从队列中移出，重新激活并恢复处理。向缓冲区中放置一个字符后，该进程发送 notempty 条件信号。对消费者函数也可以进行类似的描述。
这个例子表明，与信号量相比较，管程担负的责任不同。对于管程，它构造了自己的互斥机制：生产者和消费者不可能同时访问缓冲区；但是，程序员必须把适当的cwait和csignal原语放在管程中，以防止进程向一个满缓冲区中存放数据项，或从一个空缓冲区中取数据项。而在使用信号量的情况下，执行互斥和同步都是程序员负责。
注意在图5.16中，进程执行csignal函数后立即退出管程，若在过程最后未发生csignal，建议发送该信号的进程被阻塞，从而使管程可用，并放入队列中直到管程空闲。此时，一种可能是把阻塞进程放到入口队列中，这样它就必须与其他还未进入管程的进程竞争。但是，由于在 csignal 函数上阻塞的进程已在管程中执行了部分任务，因此使它们优先于新进入的进程是很有意义的，这可通过建立一条独立的紧急队列来实现，如图5.15 所示。并发 Pascal 是使用管程的一种语言，它要求 csignal 只能作为管程过程中执行的最后一个操作出现。
若没有进程在条件 x 上等待，csignal(x)的执行将不会产生任何效果。

而对于信号量，在管程的同步函数中可能会产生错误。例如，若省略 boundedbuffer 管程中的任何一个 csignal 函数，则进入相应条件队列的进程将被永久阻塞。管程优于信号量之处在于，所有的同步机制都被限制在管程内部，因此不但易于验证同步的正确性，而且易于检测出错误。此外，若一个管程被正确地编写，则所有进程对受保护资源的访问都是正确的；而对于信号量，只有当所有访问资源的进程都被正确地编写时，资源访问才是正确的。

消息传递

进程交互时，需要满足两个基本要求：

1. 同步：为实现互斥，进程间需要同步
2. 通信：为实现合作，进程间需要交换信息

消息传递提供了上述两方面的功能，并可工作在分布式系统、共享内存的多处理器和单处理器系统中。

消息传递的通信原语

消息传递有两条通信原语：

• Send(destination,message)：进程以消息的形式给指定的进程（目标）发送信息
• Receive(source,message)：进程通过接收原语receive接收消息，接收原语中指明源进程和消息

消息格式

消息格式

有点像计算机网络中的报文。

消息传递问题中的同步

只有发送进程发送消息，接收进程才能收到消息。

发生进程调用发送原语时，有两种可能：发送进程发送消息后，要么阻塞直到这个消息被目标进程收到；要么不阻塞。

当一个进程调用接收原语时，也两种可能：若已经有消息到达，则接收者接收消息并继续执行；若没有消息到达，接收者要么阻塞等待，要么放弃接收，继续执行。

基于发送者/接收者的两种策略的组合，就产生了消息传递的三种同步方式，如下。

消息传递的三种同步方式

阻塞发送，阻塞接收：

• 发送者和接受者都阻塞，直到完成消息投递
• 有时被称为会合 rendezvous
• 考虑了进程间的紧密同步

不阻塞发送，阻塞接收：

• 发送者不阻塞，但是接收者阻塞直到请求的消息到达
• 最有效的一种组合
• 允许发送者可以尽快的向目的发送一条或多条消息
• 例如，如一个服务进程给其他进程提供服务或资源

不阻塞发送，不阻塞接收：

• 不要求任何一方等待

通信原语确定来源、目标的方式

直接寻址

• Send 原语包含目标进程的标识号
• Receive 原语有两种处理方式：显式的指明源进程，对于处理并发进程的合作有效；或不可能指定源进程，如打印机服务进程，采用隐式寻址，接收到消息时将源地址保存下来。

间接寻址

1. 消息被发送到一个共享的数据结构，该结构由暂存消息的队列（被称为信箱）构成
2. 发送进程往信箱发送消息，接收进程从信箱取走消息

这种方法提供了对消息使用的灵活性。

间接寻址发送者和接收者之间的关系

使用消息传递实现互斥

• 多个并发执行的发送进程和接收进程共享一个邮箱 box，且 box 的初始状态为仅包含一条“空消息”（进入临界区的令牌）；
• 采用“不阻塞发送，阻塞接收”方式传递消息；
• 若邮箱中存在一条消息，则允许一个进程进入临界区。
• 若邮箱为空，则表明有一个进程位于临界区，其它试图进入临界区的进程必须阻塞。
• 只要保证邮箱中最多只有一条消息，就能保证只允许一个进程进入临界区，从而实现进程互斥使用临界资源。

有点像信号量的 PV 操作。 或者说，消息传递可以实现信号量。

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

/* program mutualexclusion */
const int n = /*  进程数  */;

void main()
{
    create_mailbox(box);        /* 创建邮箱 */
    send(box, null);            /* 初始化，向邮箱发送一条空消息 */
    parbegin(P(1), P(2), …, P(n));
}

void P(int i)
{
    message msg;
    while (true) {
        receive(box, msg);      /* 从邮箱接收一条消息 */
        <临界区>;
        send(box, msg);         /*　将消息发回到邮箱　*/
        <其余部分>
    }
}

使用消息传递实现生产者/消费者问题

既然消息传递可以实现信号量，那么就可以按照信号量的方式实现生产者/消费者问题。

使用两个邮箱 mayconsume 和 mayproduce，大小均为 capacity。

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

const int capacity　=  /* 缓冲区容量  */;

void main() {
    create_mailbox(mayproduce); 
    create_mailbox(mayconsume);
    for (int i = 1; i <= capacity; i++)
        send(mayproduce, null); //初始化信箱     
    parbegin(producer, consumer);
}

void producer() {
    message pmsg;
    while (true) {
        receive(mayproduce, pmsg); 
        pmsg  = produce();
        send(mayconsume, pmsg);    
    }
}

void consumer {
    message cmsg;
    while (true) {
        receive(mayconsume, cmsg);
        consume(cmsg);
        send(mayproduce, null);     
    }
}

和前面的代码一对比才发现，这里并没有实现互斥信号量 n。emmm 可能是在 produce() 函数里手动或自动实现了互斥吧，或者这里并不要求生产者彼此互斥。

二(4) 进程管理：进程死锁

生活中的死锁现象

死锁的原理

下面两个进程并行可能导致死锁：

1
2
3
4
5
6
7
8

void _P()       void _Q()
{               {
    P(A);           P(B);
    P(B);           P(A);
    //...           //...  
    V(B);           V(A);
    V(A);           V(B);
}               }

下图为描述该过程的示意图：

死锁的定义

死锁定义：一组相互竞争系统资源或进行通信的进程间的永久阻塞。

• 当一组进程中的每个进程都在等待某事件，而只有同组进程中阻塞的其他进程能够促发该事件时，死锁发生
• 死锁是永久性的，且无有效的解决方案

资源的分类

• 一次仅供一个进程安全使用且不因使用而耗尽的资源，如处理器、I/O通道、内存和外存、设备，以及诸如文件、数据库和信号量之类的数据结构之类的
• 可消耗资源是指可被创建（生产）和销毁（消耗）的资源，如中断、信号、消息和I/O缓冲中信息

死锁的示例

两个进程竞争可重用资源示例

竞争可重用资源可能引起死锁

例中，P1和P2请求主存，假设可分配的空间为200KB。P1和P2执行到第二条语句时死锁发生。

竞争可消耗资源可能引起死锁

例中，当Receive阻塞时死锁发生。

资源分配图

用资源分配图表示死锁。其中圆形为进程，方形为资源，方形中的黑点数为资源数。

循环等待

存在进程和资源的环（循环等待），导致死锁。

死锁的条件

死锁的必要条件：

• 互斥：一次只有一个进程可以使用一个资源
• 占用且等待：当进程等待其他资源时，继续占有已经分配的资源
• 不可抢占：不能强行抢占进程已经占有的资源

死锁的充分条件（其他教材上说这是第四个必要条件）：

• 循环等待：存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源

死锁的解决方法

针对这些条件，解决办法有：

• 死锁预防：禁止四个条件的任意一个条件发生
• 死锁避免：允许前三个条件，进行动态检查
• 死锁检测与解除：不限制资源访问或约束进程行为，而是检测死锁的存在并尝试解除

死锁的预防

我们分析死锁的四个条件，并尝试禁止任意一个发生：

1. 互斥：不能禁止（OS：亲，必须互斥的）
2. 占有且等待：要求进程一次性请求所有资源，并阻塞这个进程直到所有资源请求能够满足

• 低效：进程可能会阻塞很长时间（实际上，只要有一部分资源，它就能够执行）；分配给进程的另一部分资源可能很长时间内不会被使用
• 可能事先不知进程所需的全部资源

3. 不可抢占：占有资源的进程申请其他资源时若被拒绝，则释放最初的资源；或操作系统要求另一个进程释放资源

• 只有在资源状态容易保存和恢复情况下，这种方法才实用

4. 循环等待：定义一个请求资源的顺序

• 系统把所有资源按类型进行线性排队，如 $R_i, R_j, R_k (i<j<k)$
• 所有进程对资源的请求必须严格按资源序号递增的顺序提出（即，如果同时需要 $R_1, R_3$，必须先申请 $R_1$）
• 低效，原因类似于“占有且等待”（进程可能有了 $R_3$ 能继续执行，但它必须先申请 $R_1$ 才能申请 $R_3$）

死锁的避免

死锁避免允许三个必要条件，并进行动态检查：

• 检查进程的资源申请
• 若分配后系统可能发生死锁，则不予分配（阻塞）
• 需要预知资源的请求

有两种拒绝方法：

• 资源分配拒绝：不允许该资源分配
• 进程启动拒绝：不启动该进程

资源分配拒绝——银行家算法

• 银行家算法（类似于银行决定是否允许贷款的原理），由 Dijkstra 提出

• 思想：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分配这些资源；否则，暂时不分配，阻塞进程。

• 系统状态：当前给进程分配资源的情况

• 安全状态指至少有一个资源分配序列（Px, Py, …, Pz，安全序列）不会导致死锁，所有进程Px, Py, …, Pz 能够运行结束

例

矩阵的定义：

• Claim matrix $C$：每个进程提前声明需要的资源量。进程执行中申请的资源量不得超过 C。
• Allocation matrix $A$：已分配给每个进程的资源量。
• $C-A$：每个进程还可以申请的资源量。
• Resource vector $R$：OS 总的资源量。
• Available vector $V$：OS 目前的剩余资源量。也等于 $R$ 减去 $A$ 的每一行。

图1

先执行 P2。

图2

这一步以后 P1、P3、P4 均可被执行。这里选择执行 P1。

图3

这一步选择执行 P3。当然 P4 也是可以的。

周4

最后执行 P4。

由上可得，该例的一个安全序列为：P2、P1、P3、P4。

需要注意的是，这个过程是系统预先模拟出来的，而不是真实分配以后得到的。只有模拟出了安全状态，OS 才会真正进行分配。

例二

不安全状态示例

如图，在 (a) 的状态下，P1 请求 $(1, 0, 1)$。如果系统分配了，系统将进入不安全状态。

思考

1. 安全序列是否唯一？否
2. 安全状态是否一定没有死锁发生？

若系统处于安全状态，且按照某个安全序列分配资源，则一定不会出现死锁。
并非所有不安全状态都是死锁状态（比如前例中 P1 释放 1 个 R1 和 R3，后来再次需要这些资源，系统变成安全状态）但是这句话的逻辑似乎有点奇怪
当系统进入不安全状态以后，便可能进入死锁状态

3. 避免死锁的实质在于：如何避免系统进入不安全状态

资源分配算法总结

算法的步骤如下：

1. 判断需求的合理性（若 $allocated$ + $request$ > $claim$ 则不合理）
2. 尝试分配，定义新状态
3. 判断新状态的安全性（银行家算法）
4. 若安全则分配；若不安全则阻塞进程并还原状态

资源分配算法 伪代码

银行家算法 伪代码

死锁避免总结

死锁避免的优点：

• 无须进行（死锁预防中的）抢占和回滚进程
• 比起死锁预防，限制少

死锁避免的使用限制：

• 必须事先声明每个进程请求的最大资源
• 进程必须是独立的，它们执行顺序没有同步的要求
• 分配资源的数量必须是固定的
• 占有资源时，进程不能退出（进程退出会导致计算结果失效）

死锁检测与解除

死锁预防策略很保守：强加约束限制访问资源。而死锁检测则相反：只要有可能，就给进程分配其所请求的资源。

死锁检测

对死锁的检测可以频繁的发生在每次资源请求时；也可以少检测，如定时检测，或系统资源利用率下降时检测，具体取决于死锁发生的可能性。

优点：可尽早检测死锁；算法相对简单。
缺点：频繁检测会消耗处理器时间。

死锁检测算法

死锁检测算法在银行家算法的变量基础上增加了：

• Request matrix $Q$：$Q_{ij}$表示进程 $i$ 请求 $j$ 类资源的数量

算法步骤：为未死锁的应用打标记。（约定资源种数用 $m$ 表示）

1. 标记在 $Allocation$ 矩阵中一行全为零的进程；
2. 初始化一个临时向量 $W$，令 $W$ 等于 $Available$ 向量；
3. 查找是否存在进程 $i$：当前未被标记，且满足 $Q$ 的第 $i$ 行小于等于 $W$（即对所有的 $1 \leq k \leq m$，$Q_{ik} \leq W_k$。若找不到这样的行，终止算法；
4. 若找到这样的行，标记进程 $i$，并把 $Allcation$ 矩阵中的相应行加到 $W$ 中，即对所有 $1 \leq k \leq m$, 令 $W_k = W_k+A_{ik}$。然后返回 3。

当且仅当最终有未标记进程时，才存在死锁，未标记的进程都是死锁的。

看起来很像是银行家算法！

• 银行家算法在 $C-A$ 矩阵中寻找是否小于当前资源量 $currrent\_available$ 的行向量，如果有则将进程加入安全序列，并使 $currrent\_available$ 增加该进程的 $Allocation$ 量。
• 死锁检测在 $Q$ 矩阵中寻找是否小于当前资源量 $W$ 的行向量，如果有则标记进程，并使 $W$ 增加该进程的 $Allocation$ 量。

区别在于，银行家算法是按进程可能申请的最多资源进行计算，所以能避免死锁发生，对应的资源分配策略会很严格；
死锁检测算法是对进程正在申请的资源进行计算，所以检测的是死锁，对应的资源分配策略会比较松。

例题

1. 先标记还未分配的 P4；
2. 令 $W = A = (0,0,0,0,1)$；
3. 注意到 Q 的第三列小于 $W$，标记 P3，并更新 $W=(0,0,0,1,1)$；
4. P1、P2 无法被标记，死锁。

通过化简资源分配图进行死锁检测

1. 在资源分配图中，找出其全部请求都能满足的进程节点 $P_i$，消去 $P_i$ 所有的请求边和分配边，使之成为孤立的结点。
2. 重复步骤 1，直至无法化简为止。

资源分配图的化简示例

可完全简化图：能消去图中所有的边，使所有的进程结点都成为孤立结点的资源分配图（如上图、右下图）。

当资源分配图是不可完全化简时，存在死锁（如左下图）。

左图出现死锁 右图未死锁

死锁的解除

检测到死锁后，需要按照某种可能的策略来解除。给出以下三个方法，以及三个方法下的不同策略。

1. 撤消进程：撤消所有死锁进程，或连续撤消死锁进程直到不再存在死锁
2. 回退：把进程回退到前面定义的某些检查点，并重新启动所有进程
3. 抢占：连续抢占资源直到不再存在死锁

取消哪些进程、抢占哪些进程的资源呢？——选择原则：目前为止消耗处理器时间少，或输出少，或分配资源少，或剩余时间长，或优先级最低的进程

死锁解决办法总结

死锁解决办法总结（英文）

死锁解决办法总结（中文）

哲学家就餐问题

1965年，Dijkstra出了一道同步考试题：假设有五台计算机都试图访问五份共享的磁带驱动器。后来，这个问题被Hoare重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。

Dijkstra 怎么这么强（捶桌）.jpg

• 5 个哲学家围坐一张餐桌
• 5 只餐叉间隔摆放
• 思考或进餐
• 进餐时必须同时拿到两边的餐叉
• 思考时将餐叉放回原处
• 两个哲学家不能同时使用同一把叉子
• 避免死锁和饥饿

哲学家就餐问题图

方案一 先左后右，可能死锁

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

semaphore fork[5] = {1, 1, 1, 1, 1};

void main()
{
    cobegin {philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4);}coend;
}

void philosopher(int i)
{
    while(true) {
        think;                  //思考
        wait(fork[i]);          //拿起左边的叉子
        wait(fork[(i+1)%5]);    //拿起右边的叉子
        eat();
        signal(fork[i]);        //放回左边的叉子
        signal(fork[(i+1)%5]);  //放回右边的叉子
    }
}

显然，可能导致死锁。

方案二 先左后右，失败后随机等待一段时间，可能活锁

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

semaphore fork[5] = {1, 1, 1, 1, 1};

void main()
{
    cobegin {philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4);}coend;
}

void philosopher(int i)
{
    while(true) {
        think;                              //思考
        wait(fork[i]);                      //拿起左边的叉子
        timeout(wait(fork[(i+1)%5], [0, T]) //若右边的叉子被占用，则放下左边叉，等待一段随机时间后再拿
        eat();
        signal(fork[i]);                    //放回左边的叉子
        signal(fork[(i+1)%5]);              //放回右边的叉子
    }
}

方案三 资源分级

就是死锁预防中打破循环等待的方法。

为资源（这里是餐叉）分配一个偏序（partial order）或者分级（hierarchy）的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。

资源分级方案一 先低后高

• 为餐叉编号
• 就餐前，先取用编号较低的餐叉，再取用编号较高的餐叉
• 就餐毕，先放下编号较高的餐叉，再放下编号较低的餐叉

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

semaphore fork[5] = {1, 1, 1, 1, 1};
void main()
{
    cobegin {philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4);}coend;
}
void philosopher(int i)
{
    while(true)
    {
        think();  //思考
        if (i != 4)
            wait(fork[i]); wait(fork[(i+1)%5]);     //先左后右
        else
            wait(fork[(i+1)%5]); wait(fork[i]);     //先右后左
        eat(); 
        if (i != 4)
            signal(fork[(i+1)%5]); signal(fork[i]); //先右后左
        else
            signal(fork[i]); signal(fork[(i+1)%5]); //先左后右
    }
}

资源分级方案二 奇先左偶先右

• 为哲学家编号
• 奇数号的哲学家必须首先拿左边的餐叉
• 偶数号的哲学家必须首先拿右边的餐叉

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

semaphore fork[5] = {1, 1, 1, 1, 1};
void main()
{
    cobegin {philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4);}coend;
}
void philosopher(int i)
{
    while(true)
    {
        think();  //思考
        if (i % 2 != 0)
            wait(fork[i]); wait(fork[(i+1)%5]);        //先左后右
        else
            wait(fork[(i+1)%5]); wait(fork[i]);
        eat(); 
        signal(fork[(i+1)%5]);                         //先右后左
        signal(fork[i]);   
    }
}

方案四 服务生方法

• 教授需要经过服务生允许以后才能吃饭
• 只允许有四个人同时进餐

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

semaphore fork[5] = {1, 1, 1, 1, 1}, room = 4;
void main()
{
    cobegin {philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4);}coend;
}
void philosopher(int i)
{
    while(true)
    {
        think;                   //思考
        wait(room);              //占据就餐位置
        wait(fork[i]);           //拿起左边的叉子
        wait(fork[(i+1)%5]);     //拿起右边的叉子
        eat();
        signal(fork[i]);         //放回左边的叉子
        signal(fork[(i+1)%5]);   //放回右边的叉子
        signal(room);            //释放就餐位置
    }
}

引申：And 型信号量集（不做要求）

哲学家就餐问题的引申：And型信号量集
在一个原语中申请需要的多个临界资源，要么全部分，要么一个都不分配。
AND型信号量集P原语为Swait(Simultaneous Wait)，V原语为Ssignal(Simultaneous Signal)。
Swait(S1, S2, …, Sn)
Ssignal(S1, S2, …, Sn)
思考：采用and型信号量解决哲学家就餐问题

管程解决方案

管程

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