操作系统课程笔记 | 小灰灰灰灰的博客

教材：《操作系统——精髓与设计原理第八版》 (opens new window)-- William Stallings

# 一操作系统概述

# 操作系统的目标和功能

操作系统：

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

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

功能：

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

# 操作系统的历史

# 串行处理

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

# 简单批处理系统

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

简单批处理系统

监控程序的功能：

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

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

# 多道批处理系统

多道批处理系统

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

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

硬件支持：

I/O中断
DMA
……

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

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

示例-信息

# 分时系统

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

分时系统：

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

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

比较	多道批处理系统	分时	实时系统
主要目标	充分利用处理器	减少响应时间
OS 指令源	作业提供命令（无交互）	终端键入命令（来自用户）
特征	多道性、调度性、无序性、无交互能力	多路性、独立性、及时性、交互性	可确定性、可响应性、用户控制、可靠性、故障弱化能力

第一个分时操作系统：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 为用户提供的接口。

# 进程创建

回忆进程创建的原因？

创建进程的流程：

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

# 进程切换

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

进程切换的时机

# 系统中断

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

普通终端和陷阱

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

# 模式切换

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

模式切换原因：

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

注意：

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

# 进程状态转换

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

进程切换步骤：

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

切换回来的步骤：

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

# 总结几个概念的关系

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

# 操作系统的执行

操作系统的执行

# Unix SVR4 的进程管理

# Unix SVR4 的进程状态图

Unix SVR4 的进程状态图

阻塞在 Unix SVR4 中被称为 Sleep。

# Unix SVR4 的进程创建

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

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

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

例题 1：

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

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

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

例题 2：

#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：

#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 测试结果如下：

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

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

#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`	4	5
`vari`	5	4

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

# 线程

# 线程与进程

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

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

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

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

多进程与多线程的例子

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

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

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

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

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

单进程和多进程模型

进程的优点：

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

调度和分派基于线程

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

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

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

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

单处理器上的多线程示例

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

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

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

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

# 线程分类

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

用户级线程和内核级线程

# 用户级线程 ULT

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

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

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

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

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

# 调度的类型

调度类型	操作	决策内容
长程调度	创建进程 `->` 挂起/就绪	把进程添加到当前活跃的进程集中
中程调度	挂起 `<->` 就绪/运行	把进程添加到（至少部分）已在内存且可被执行的进程集中
短程调度	就绪 `<->` 运行	下次执行哪个就绪进程

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

调度与状态图

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

调度的层次

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

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

# 长程调度

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

长程调度需考虑：

何时操作系统能够接纳进程
接纳哪个作业为之创建进程（先来先服务，或根据优先级、期望的执行时间、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{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}} = \frac{w+s}{s}

算法评价：

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

# 反馈调度法 Feedback

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

算法思想：

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

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

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

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

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

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

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

调度队列

重点掌握！！！

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

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

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

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

# 实时系统与实时调度

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

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

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

# 实时任务分类

按截止时间分：

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

按周期性分：

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

# 实时操作系统特点

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

# 实时调度的两个维度

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

# 调度方法分类

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

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

# 静态表驱动调度表

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

# 静态优先级抢占调度法

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

# 基于动态规划的调度法

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

# 动态尽力调度法

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

# 抢占方式分类

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

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

# 实时调度方法实例

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

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

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

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

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

在一个实时系统中，有两个周期性实时任务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话你知- 简书 (opens new window)

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

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

解决方案

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

# 并发的原理

日常生活现象

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

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

# 相关概念

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

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

忙等、饥饿和死锁

# 并发控制的产生

产生原因：

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

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

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

两端并行的 echo()

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

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

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

# 进程间的交互方式

进程间的关系：

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

# 进程间的竞争资源

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

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

# 进程间通过共享合作

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

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

# 进程间通过通信合作

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

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

# 互斥

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

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

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

# 互斥：软件方法

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

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

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

// 共享的全局变量
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 则进入临界区。

// 共享的全局变量,标志临界区是否可用
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，会死锁。当然，仍然存在忙等。

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，等一会后再改回来。

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

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 都让出去。

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

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 算法的显著优点是算法更简洁，对应的代码行数更短。

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

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

# 中断禁用

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

其缺点有：

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

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

# 专用机器指令

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

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

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

# compare & swap 指令

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

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 实现并发互斥的一个方案。

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 指令

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

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

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 可视为一个值为整数的变量。具有三个操作：

一个信号量可以初始化为非负数
semWait （Wait或P）操作使信号量的值减少1，若值变为负数，则阻塞执行 semWait 操作的进程
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 应作为原语 (opens new window)实现。即，任意时刻只能有一个进程用 P 和 V 来操作控制信号量。

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

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

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

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

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

# 生产者/消费者问题

生产者与消费者问题：

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

需解决同步问题：

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

-- Dijkstra

程序框图

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

/*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：表示产品资源量

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

注意：

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

可能出现死锁

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

// 错误的 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;

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

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

# 示例一

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

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

分析：

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

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 信号量，原因在示例一中提到了。

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。

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。

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 在该系统中，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改（读/写）其中某一条数据的情形。

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

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

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

# 读者优先

思想：

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

变量设置:

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

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 写的值。

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

R R R
W W W
R W
R R W
R R W R
W W R
W R R W

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

# 公平优先

这个就比之前的复杂了。

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

变量设置：

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

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互斥算术操作

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 才能进入。

设每个序列最右为队首：

R R W R
R R W
W R R W
W R R R R

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

# 写者优先改进

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

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操作来实现东西两端行人过桥问题。

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

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互斥算术操作

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 就行。

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把供等候理发的顾客坐的椅子。如果没有顾客，则理发师睡觉。当一个顾客到来时，他必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他就离开。

理发师和顾客工作流程

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

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

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

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

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 等。

# 管程的概念

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

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

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

# 管程的特点

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

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

# 用管程实现进程同步

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

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

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

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

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

# 管程的结构

管程的结构

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

/* 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 函数，则进入相应条件队列的进程将被永久阻塞。管程优于信号量之处在于，所有的同步机制都被限制在管程内部，因此不但易于验证同步的正确性，而且易于检测出错误。此外，若一个管程被正确地编写，则所有进程对受保护资源的访问都是正确的；而对于信号量，只有当所有访问资源的进程都被正确地编写时，资源访问才是正确的。

# 消息传递

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

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

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

# 消息传递的通信原语

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

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

# 消息格式

消息格式

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

# 消息传递问题中的同步

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

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

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

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

# 消息传递的三种同步方式

阻塞发送，阻塞接收：

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

不阻塞发送，阻塞接收：

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

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

不要求任何一方等待

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

# 直接寻址

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

# 间接寻址

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

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

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

# 使用消息传递实现互斥

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

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

/* 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。

Mayproduce	Mayconsume
该邮箱起初填满空消息（即允许生产的令牌）	生产者产生的数据作为消息发送到该信箱（即允许消费的令牌）
只要该邮箱有消息，生产者就可生产	只要该邮箱有数据消息，消费者就可消费
每次生产前取一条空消息，之后生产数据，并将数据作为消息发至mayconsume邮箱	每次消费前，取一条消息，消费后，向mayproduce发送一条空消息
消费者的每次消费使得该邮箱中的空消息数增加	生产者的每次生产使得该邮箱的消息数增加
类似于空间资源信号量	类似于产品资源信号量

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) 进程管理：进程死锁

生活中的死锁现象

# 死锁的原理

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

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阻塞时死锁发生。

资源分配图

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

循环等待

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

# 死锁的条件

死锁的必要条件：

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

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

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

# 死锁的解决方法

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

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

# 死锁的预防

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

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

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

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

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

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

系统把所有资源按类型进行线性排队，如 $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$ 的每一行。

先执行 P2。

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

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

最后执行 P4。

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

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

# 例二

不安全状态示例

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

# 思考

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

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

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

# 资源分配算法总结

算法的步骤如下：

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

资源分配算法伪代码

银行家算法伪代码

# 死锁避免总结

死锁避免的优点：

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

死锁避免的使用限制：

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

# 死锁检测与解除

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

# 死锁检测

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

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

# 死锁检测算法

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

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

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

标记在 $Allocation$ 矩阵中一行全为零的进程；
初始化一个临时向量 $W$ ，令 $W$ 等于 $Available$ 向量；
查找是否存在进程 $i$ ：当前未被标记，且满足 $Q$ 的第 $i$ 行小于等于 $W$ （即对所有的 $1 \leq k \leq m$ ， $Q_{ik} \leq W_k$ 。若找不到这样的行，终止算法；
若找到这样的行，标记进程 $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$ 量。

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

# 例题

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

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

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

资源分配图的化简示例

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

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

左图出现死锁右图未死锁

# 死锁的解除

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

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

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

# 死锁解决办法总结

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

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

# 哲学家就餐问题

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

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

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

哲学家就餐问题图

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

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]);  //放回右边的叉子
    }
}

显然，可能导致死锁。

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

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）的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。

# 资源分级方案一先低后高

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

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]); //先左后右
    }
}

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

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

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

# 方案四服务生方法

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

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型信号量解决哲学家就餐问题

# 管程解决方案

管程

monitor dining_controller;
cond ForkReady[5];
bool fork[5] = {1,1,1,1,1};

void get_forks(int pid)
{
    int left = pid;
    int right = (pid + 1) % 5;
    
    // 获取左边的叉子
    if (!fork[left])
        cwait(ForkReady[left]);
    fork[left] = false;

    //获取右边的叉子
    if(!fork[right])
        cwait(ForkReady[right]);
    fork[right] = false;
}

void release_forks(int pid)
{
    int left = pid;
    int right = (pid + 1) % 5;
    
    // 释放左边的叉子
    if (!empty(ForkReady[left])) //如果没有人在等待这个叉子
        fork[left] = true;
    else
        csignal(ForkReady[left]) // 让被阻塞在这里的进程继续

    // 释放右边的叉子
    if (!empty(ForkReady[right])) //如果没有人在等待这个叉子
        fork[right] = true;
    else
        csignal(ForkReady[right]) // 让被阻塞在这里的进程继续
}

void philosopher(int k)
{
    while (true)
    {
        think();
        get_forks(k);
        eat();
        release_forks(k);
    }
}

为什么采用管程方法不会发生死锁？因为在管程中被阻塞的进程会释放已有的资源，即不会出现抓着左叉子等右叉子的现象。

# 三(1) 内存管理：基本内存管理

计算机存储体系

# 程序的加载和链接

高级语言的源代码转化为进程的 3 个基本步骤：

编译：用户源代码 -> 经编译程序 (Compiler) -> 若干目标模块
链接：一组目标模块 + 它们需要的库函数 -> 经链接程序 (Linker) -> 完整的加载模块
加载（装入）：加载模块 -> 由加载程序 (Loader) -> 装入内存

简单的认为：

编译负责：模块内变量名 -> 逻辑地址
链接负责：模块间变量名 -> 逻辑地址
加载负责：程序逻辑地址 -> 物理地址（装入内存）

链接和加载场景

为表达清晰起见，首先介绍只涉及一个程序模块时的加载任务，因为这时不需要链接。介绍完加载后再聊多个模块的链接任务。

# 加载的任务

将可加载模块装入内存
地址重定位：将执行文件中的逻辑地址转化为内存物理地址的过程

# 加载方式分类（地址映射建立方式）

绝对加载方式：编译使用绝对地址
可重定位加载（静态重定位）方式：编译使用相对地址，加载时确定绝对地址
运行时加载（动态重定位）方式：执行时确定绝对地址

# 绝对加载方式

程序中的逻辑地址与实际内存地址完全相同，无需修改
在编译时就确定程序将驻留在内存中的具体位置
编译程序产生绝对地址的目标代码
为了便于程序的修改,对程序采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址

绝对加载方式示例

优点：

实现简单

缺点：

程序每次必须装入同一内存区
程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址
不适于多道程序系统（多个程序的绝对内存地址可能冲突）

# 可重定位加载方式（静态重定位）

编译时采用相对地址，即编译器假设是加载到从零开始的内存位置
加载程序根据加载的位置将逻辑地址转换为物理地址（重定位）
静态重定位技术：地址映射在程序加载时进行，以后不再更改程序地址

静态重定位加载方式示例

优点：易实现，无需硬件支持

缺点：程序重定位后不能移动，不能重新分配内存，不利于内存的有效利用

# 运行时加载（动态重定位）方式

程序的地址转换不是在加载时进行，而是在程序运行到相应代码时动态进行
需要硬件支持：重定位寄存器，用于保存程序在内存中的起始地址
通过重定位寄存器内的起始物理地址和指令/数据的逻辑地址计算其物理地址

运行时加载示例

优点：

程序不必连续存放在内存中，可分散存储，可移动
（如动态链接库 dll）便于共享
有利于紧凑、碎片问题的解决
主流方式

缺点：

需要硬件支持，对应的软件算法比较复杂
同一地址，可能多次转换

# 小结

绝对加载
- 编译时执行地址绑定
- 编译时就知道进程将在内存中的驻留地址，生成绝对代码。即在可执行文件中记录内存地址，加载时直接定位在该内存地址
- 如果将来开始地址发生变化，就必须重新编译代码
静态重定位加载
- 加载时执行静态地址重定位
- 系统根据内存当时的使用情况，决定将目标代码放在内存的什么位置
- 不允许程序在内存中移动
动态执行时加载
- 执行过程中执行动态地址重定位
- 支持执行时进程在内存中移动

# 链接的任务

一组目标模块 -> 一个包含完整程序和数据模块的加载模块，传递给加载器
地址重定位：在每个目标模块中，可能有到其他模块的地址访问。链接器创建一个单独的加载模块，它把所有目标模块逐个链接起来。

# 链接方式（链接的时机）

静态链接(Static linking)
加载时动态连接(Load-time Dynamic Linking)
运行时动态链接(Runtime Dynamic Linking)

# 静态链接

程序运行前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块（执行模块），以后不再拆开。

两个问题：

相对地址的修改：由编译程序产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，在链接成一个加载模块时修改模块的相对地址
变换外部引用地址：将每个模块中所用的外部调用符号也都变换为相对地址。

静态链接方式示意图

缺点：

不利于代码共享：每个应用都含有目标模块的拷贝（A、D 都需要 C 模块时，C 会在内存中出现两次）
不利于模块的独立升级：每次对某个目标模块的修改升级，都要打开整个加载模块
可能链接一些不会执行的模块，浪费存储空间和处理机时间。如 A 的代码为 if (cond) {call B;} else {call C;}，B、C 都会被链接，但不会被都执行。

# 加载时动态链接

待加载的模块在加载内存时，如果该模块中有到外部模块的引用，加载程序将查找这些模块并加载内存，并把这些引用修改为相对应用程序模块开始处的相对地址。

优点：

便于各个模块的独立升级
便于实现模块的共享

缺点

可能链接一些不会执行的模块，浪费存储空间和处理机时间（同静态链接）
模块加载后不能移动位置

# 运行时动态链接

在程序执行中需要某目标模块时，由操作系统去找到该模块并将之加载内存，随后把它链接到调用者模块上
如 Windows 的 DLL

优点：

凡在执行过程中未被用到的目标模块，不会被调入内存和被链接到加载模块上
- 不仅可加快程序的加载过程，而且可节省大量的内存空间
支持分段系统

# 总结

地址映射时间	加载方式	链接方式
加载前（编译/链接时）	绝对加载	静态链接
加载时	可重定位加载/静态重定位	加载时动态链接
运行时	运行时加载/动态重定位	运行时动态链接

讲了一通概念，乱乱的。这个似乎不是很重要，讲得不详细。主要是为后面铺路吧。

# 内存管理的需求

重定位
保护
共享
逻辑组织
物理组织

# 重定位

重定位 relocation（HTTP 的重定向是 redirect 233）

OS 需要把活动进程换入或换出内存，但进程换入时若要放置在与换出前相同的区域，会存在诸多困难。因此需要将进程重定位到内存的不同区域。

操作系统需要知道进程控制信息、栈和入口点位置
处理器需要处理程序内部的内存访问，处理跳转指令、数据访问指令的地址转换

# 保护

进程以外的其他进程中的程序不能未经授权地访问（进行读操作或写操作）该进程的内存单元
程序在内存中的位置不可预测
需要既支持重定位，也支持保护的机制
处理器硬件必须具备这个能力

# 共享

多个进程正在执行同一程序时，允许每个进程访问该程序的同一个副本，要比让每个进程有自己独立的副本更有利
需要既支持重定位也支持共享的机制

# 逻辑组织

内存被组织成线性（或一维）地址空间
与此同时，程序按模块组织
- 可以独立编写和编译模块
- 可以为不同的模块提供不同的保护级别（只读、只执行）
- 模块可以被多个进程共享，与用户看待问题的方式一致

分段可以满足该需求。

# 物理组织

在内存和外存之间完成移动信息的任务应该交给OS而不是程序员，因为：

不应让程序员负责管理内存
供程序和数据使用的内存可能不足
- 覆盖 (overlaying) 允许不同的模块占用相同的存储空间，但编程耗时
程序员不知道可用空间的大小和位置

# 内存分区

内存管理的主要操作是处理器把程序加载内存中执行

内存管理技术	使用
固定分区	IBM MFT
动态分区	IBM MVT
简单分页	没有使用，但为虚存分页的基础
简单分段	没有使用，但为虚存分段的基础
虚存分页	现代操作系统广泛实际使用
虚存分段	现代操作系统广泛实际使用

内存管理包含虚拟内存的复杂方案，基于分段和分页两种基本技术

# 固定分区

操作系统占据内存中某些固定部分，用户进程使用其余部分
分区数量固定
每个分区装入一个进程
两种划分方式：分区大小相等和分区大小不等，如图：

固定分区的两种划分方式

问题：

程序可能太大而不能放到一个分区中。此时，程序员必须使用覆盖技术设计程序，使得任何时候程序只需要有一部分放入内存
内存的利用率非常低：很小的程序也必须占据一个完整分区
由于装入的数据块小于分区大小，分区内部存在空间浪费，这种现象称作内部碎片

内部碎片 (internal fragmentation) 就是分区内部的碎片

分区大小不等可以缓解上述问题，使内部碎片更小。

但是，如果分区大小不等，就要考虑到放置算法，即把进程分配到分区的算法。

分区大小不等时的放置算法

最简单的方法是把每个进程分配到能够容纳它的最小分区中。在这种情况下，每个分区都需要维护一个调度队列，用于保存从这个分区换出的进程，如图 (a) 所示。这种方法的优点是，每个分区内部浪费的空间（内部碎片）最少。尽管从单个分区的角度来看这种技术是最优的，但从整个系统来看它却不是最佳的。如果某个时刻，系统中没有大小在 12MB 到 16MB 之间的进程。此时，即使系统中有一些更小的进程本可以分配到 16MB 的分区中，但 16MB 的分区将仍会保持闲置。因此，一种更可取的方法是为所有进程只提供一个队列，如图 (b) 。当需要把一个进程装入内存时，选择可以容纳该进程的最小可用分区。如果所有的分区都已被占据，则必须进行交换。

固定分区存在的问题：

分区的数量在系统生成阶段已经确定，因而限制了系统活动进程的数量
小作业不能有效地利用分区空间

# 动态分区

动态分区：分区大小和数量不固定；OS 总是分配与进程需求完全一致的空闲内存空间。

动态分区的效果

如上图，动态分区虽然更灵活，但是会导致分区之间产生很多狭小的外部碎片（如 (h) 图中出现了 2 个 6M 和 1 个 4M 的碎片）。

外部碎片 (external fragmentation) 就是分区外部的碎片

于是有了紧凑技术 Compaction（又称为压缩）：

解决外部碎片问题的技术
操作系统移动进程，使进程占用的空间连续、所有空闲空间连成一片
但是紧凑费时，浪费处理器时间

# 动态分区放置算法

# 首次匹配 First Fit

思想：从头开始扫描内存，选择大小足够的第一个可用块
实现：要求空闲分区以地址递增的顺序链接，从链首开始查找
评价：
- 简单，快速
- 为大作业分配大的内存空间创造条件
- 内存前端出现很多小的空闲分区，且每次查找都要经过这些分区

# 下次匹配/循环匹配 Next Fit

思想：从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块
实现：空闲分区按地址从低到高排列（链接）
评价：通常比首次匹配性能差
- 常常在内存末尾分配空间，能使空闲的分区分布均匀
- 缺少大的空闲块，需要更多次数紧凑

# 最佳匹配 Best Fit

思想：选择空间大小与需求最接近的空闲块分配
实现：空闲分区按容量从小到大链接
评价：通常性能是最差的
- 产生的外部碎片都很小
- 内存中形成很多小到无法满足任何分配需求的块
- 需要更频繁地紧凑

# 最差匹配 Worst Fit

思想：选择最大的空闲分区分配
实现：空闲分区按容量从大到小链接
评价：
- 每次分配留下的空闲空间较大，便于再次利用
- 大的空间不容易保留，对大作业不利

# 例题

固定分区中的内存分配示例

操作系统采用动态分区存储管理技术。操作系统在低地址占用了100KB的空间，用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为分配区。执行以下申请、释放操作序列：请求300KB、请求100KB、释放300KB、请求150KB、请求50KB、请求90KB。

采用首次适应算法时，主存中有哪些空闲分区？画出主存分布图，并指出空闲分区的首地址和大小。
采用最佳适应算法时，主存中有哪些空闲分区？画出主存分布图，并指出空闲分区的首地址和大小。
若随后又申请80KB，针对上述两种情况产生什么后果？说明了什么问题？

分区分配算法示例

# 伙伴系统

固定分区方案限制了活跃进程的数量。并且，如果分区大小与进程大小不匹配，则内存空间的利用率非常低
动态分区方案维护复杂，并且引入了紧凑的额外开销
折中方案：伙伴系统 Buddy System

提出者：Donald E. Knuth

# 原理

最初，可用于分配的空间被视为一个大小为 $2^U$ 的块。

每次分配的块的大小为 $2^K$ ， $L \leq K \leq U$ , 且

$2^L$ = 分配的最小块的大小
$2^U$ =分配的最大块的大小
通常， $2^U$ 是内存中整个可分配空间的大小

伙伴系统示例

释放 A 的时候，A 所在 64K 会和它的伙伴（从一个 128K 分裂出来的另一个 64K）进行合并，这就是所谓伙伴系统
释放的空间只能和自己的伙伴合并，即使另一个相邻空间也是同大小，也不会合并

伙伴系统的树状表示

# 评价

较为合理的折中方案，一定程度上克服了固定分区和动态分区的缺陷
是一种有效方案
UNIX 内核存储分配中使用了一种经过改进的伙伴系统

# 重定位

概念：

逻辑地址 Logical：与当前数据在内存中的物理分配无关的访问地址，执行前要转换成物理地址
相对地址 Relative：逻辑地址的特例，相对于某些已知点的存储单元
物理地址 Physical/Absolute：内存中的实际地址

重定位的硬件支持

首地址经过 Adder 以后，还要进入 Comparator 判断是否有越界访问。

# 分页（重点，敲黑板）

# 页和页框

将内存划分成大小固定、相等、相对较小的块
进程也划分成同样大小的块
页 Pages：进程中的块
页框 Frames：内存中的块
不会有外部碎片（回忆内部碎片、外部碎片是什么？）

将进程的页装入内存的页框

注意 D 进程是离散存放（相对地，A、B、C是连续存放）的！

由于存在离散存放的情况，地址转换需要操作系统提供页表支持。

# 页表

页表是一种数据结构
每个进程一个页表
保存进程中每个页对应的页框
处理器使用页表生成物理地址

页表示例

每个进程的页表中，左边是页号，右边是页框号。

# 逻辑地址

分页模式下，逻辑地址 = 页号 + 页内地址

32位机的分页存储系统逻辑地址结构示意图

从图中可以得出，页的大小为 4KB( $2^{12}$ B)。

逻辑地址转换示例

c 图是分段的内容，可以先不看。

转换的实际情况可以看地址转换。

若给定一个逻辑地址空间中的地址为 $A$ ，页面的大小为 $L$ ，则页号 $P$ 和页内地址 $d$ 有以下关系：

P=\lfloor \frac{A}{L} \rfloor, d = A \mod L

例题：某系统的页面大小为 1 KB，设 $A = 2170 B$ ，试计算其页号 $P$ 与页内地址 $d$ 。

P=\lfloor \frac{2170}{1024} \rfloor = 2, d = 2170 \mod 1024 = 122

逻辑地址到物理地址的转换

逻辑地址高位 => 页号
查页表，页号 => 页框号
页框号:逻辑地址低位 => 物理地址

# 页表的存储

页表存放在内存
PCB 保存有页表的起始地址（PCB 和页表都是每个进程一个）
页表寄存器存放当前运行进程的页表的起始地址

# 例题

例题 1：

一个系统，内存容量共256K，存储块的大小为1K，共256块，编号为0～255。
第0～4块为操作系统所使用；
现有2个用户作业，作业1和作业2，其逻辑地址空间分别占2k和2.5k；
进入系统后，按块的大小划分分别占2页和3页，分布如图。

分页情况

请完成作业 2 的 2500 的地址转换：

例题地址转换

示意图：

地址转换示意图

例题 2：

在普通分页存储管理系统中，逻辑地址的结构长度为18位，其中11~17表示页号，0~10位表示页内偏移量。若有一个作业的各页依次放入2、3、7号物理块，试问：逻辑地址1500应在几号页内?对应的物理地址是多少?

题解：

在页表中，有3个页表项，分别为(0,2)、(1,3)、(2,7)
$\text{页号}=int(1500/2^{11})=0$
$\text{页内偏移量}=1500 \mod 2^{11} = 1500$
$\text{物理地址}=2*2^{11}+1500=5596$

# 评价

分页存储管理的优点：

存在页内碎片，但碎片相对较小，内存利用率较高
实现了离散分配
无外部碎片

分页存储管理的缺点：

需要专门的硬件支持，尤其是快表
不支持动态链接，不易实现共享（动态链接、共享是以模块为单位，而分页以页为单位，不会考虑到模块）

后面讲虚存的时候还会提到分页

# 分段

emmm 汇编

一个程序可以划分成几个段 segments
- 段长度可以不等
- 每个段都从 0 开始编址，并占用一段连续的地址空间
- 有最大段长限制
逻辑地址两部分组成：段号+段内偏移量
分段类似动态分区：分段使一个程序可以占据多个分区，且不必连续
消除了内部碎片

# 分段的性质

分页对用户透明（用户不可见分页），分段对用户可见
分段给程序员提供了组织程序和数据更方便的手段
程序员或编译器将程序和数据划分到不同的段
为实现模块化程序设计，程序和数据可能会进一步被划分成多个段
不便：程序员或编译器需要清楚最大段长的限制

# 逻辑地址

分段模式下，逻辑地址 = 段号 + 段内偏移

分段的逻辑地址结构

一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是多少字节？

应为 $2^{32-8}B=4 MB$ 。

# 段表

段表记录逻辑段和物理段的对应情况。

# 逻辑地址转换示例

段的大小不等，导致逻辑地址和物理地址间没有简单的对应关系。地址转换需要经历以下步骤：

提取段号：逻辑地址最左侧的 n 位
以段号为索引，查找段表中该段的起始物理地址
逻辑地址最右侧 m 位为偏移量，偏移量与段长度比较，若偏移量>段长，则地址无效
物理地址：该段的起始物理地址+偏移量

逻辑地址转换示例

# 评价

分段存储管理的优点：

便于程序模块化设计
便于动态链接
便于保护和共享
无内部碎片

分段存储管理的缺点：

地址转换需要硬件的支持——段表寄存器
分段的最大尺寸受到主存可用空间的限制
有外部碎片

# 分页、分段对比

页是信息的物理单位，分页的目的是实现离散分配，减少内存的外部碎片，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

分页存储管理系统不易实现“共享”和“运行时动态链接”，而分段系统易于实现**“共享”**。

# 三(2) 内存管理：虚拟内存管理

虚存的前提：

分页或分段的硬件支持
操作系统必须有管理页或段在内存和辅存之间移动的软件

# 相关概念

虚拟内存：在存储分配机制中，辅存可被看作主存的一部分来完成寻址。程序使用的地址与内存物理存储的地址不同，程序生成的地址会自动转换为物理地址。虚拟存储的大小受计算机系统寻址机制和可用辅存容量的限制，而不受主存实际大小限制
虚拟地址：在虚拟内存中分配给某一位置的地址，它使得该位置可被访问，就好像是主存的一部分那样。有时也称为逻辑地址
虚拟地址空间：分配给进程的虚拟存储
地址空间：用于某进程的内存地址范围
实地址：内存中存储位置的地址

# 硬件和控制结构

分页和分段内存管理的两个基本特征：

进程中所有内存访问都是逻辑地址，这些逻辑地址会在运行时动态地转换为物理地址。
一个进程可划分为许多块（页和段），在执行过程中，这些块不需要连续地位于内存中

若上述特征存在，则在一个进程执行过程中，该进程不需要所有页或所有段都在内存中。

进程的执行过程：

操作系统仅读取包含程序开始处的一个或几个块进入内存
驻留集：任意时刻，进程驻留在内存的部分
访问一个不在内存中的逻辑地址时（称为内存失效），产生一个中断：
- 操作系统把被中断的进程置为阻塞状态
- 操作系统把该进程中包含引发内存失效的部分读入内存
- 操作系统产生一个磁盘 I/O 读请求
- 在执行磁盘 I/O 期间，操作系统调度另外一个进程运行
- 磁盘 I/O 完成后产生中断，操作系统将相应的进程置于就绪状态

提高系统资源利用率的方法：

内存中保留多个进程
- 每个进程仅装入了部分块
- 任何时刻内存中的进程至少有一个处于就绪状态
- 提高了处理器的利用率
进程可以比内存的全部空间还大
- 基于分页和分段的技术，操作系统和硬件只加载程序的一部分
- 程序员面对的是一个巨大内存，大小与磁盘存储器相关

实存储器（实存）	虚拟内存（虚存）
主存, 实际的物理内存	感觉更大的内存，且常分配在磁盘上
更有效地支持并发，并能减轻用户对内存的严格限制

使用和不使用虚存技术下分页和分段的特点

# 抖动和局部性原理

进程只有部分块在内存，这样可在内存中保留更多进程
操作系统必须“聪明”的管理这个方案
当内存空间几乎被进程块占据时，每读取一块，必须把另一块换出，如果出现抖动，处理器的大部分时间都用于交换而非执行指令
为了避免这种情况，操作系统试图根据最近的历史来猜测将来最可能用到的块

抖动：即将要用到的块被换出，系统又得很快将它取回，导致页面被频繁地换入换出，缺页率急剧增加

局部性原理：

存储器的访问呈簇性（簇 cluster：一组程序或数据的集合）
- 在很长一段时间内，使用的簇会发生变化
- 但在很短的时间内，处理器基本上只与固定的簇打交道
描述了进程中程序和数据引用的集簇倾向
在很短的时间内仅需要进程的一部分块
对将来可能会访问的块进行猜测，以避免抖动

局部性原理表明虚存方案是可行的。

# 分页

虚拟内存通常与使用分页的系统联系在一起
每个进程都有自己的页表
分页的虚存方案中，页表项变得更复杂

# 页表项

页表项

存在位 P：表明对应的页是否在内存
页框号：若页在内存，则有对应的页框号
修改位 M：表明相应页上次装入内存到现在是否修改过（若修改过，换出时要更新辅存上对应页；没修改就不用更新了）

# 地址转换

其实也就是前面分页的地址转换,只是这里加上了内存等硬件结构。

页表位于内存
进程运行时，一个寄存器保存页表的起始地址
虚拟地址的页号用于检索页表，查找对应页框号
页框号与虚拟地址的偏移量结合起来形成物理地址

地址转换过程

例：某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：

页号	物理块号
0	5
1	10
2	4
3	7

逻辑地址 0A5C(00010 1001011101) 对应的物理地址为：125C(0100 1001011101)。

# 二级页表

每个进程一个页表，如果进程的逻辑地址空间大，则页表庞大。

例如，在 Vax 机中，每个进程虚存空间可达 $2^{31}=2GB$ ，若每个页大小 $2^9=512B$ ，则需要 $2^{22}$ 个页表项。

显然，采用这种方法来放置页表的内存空间太大。为克服这个问题，大多数虚拟内存方案都在虚存（而非实存）中保存页表。这意味着页表和其他页一样都服从分页管理。

一个进程正在运行时，它的页表至少有一部分须在内存中，这一部分包括正在运行的页的页表项。

一些处理器使用两级方案来组织大型页表。在这类方案中有一个页目录，其中的每项指向一个页表。这种方案也称为二级页表。

示例：32位地址的两级页表

页尺寸为 4KB
虚拟地址空间为 4GB，由 $2^{20}$ 页组成
每个页表项 4 字节，可计算得页表大小总共需要 $4B \times 2^{20} = 4MB$
页表空间需 $4MB/4KB=2^{10}$ 页存储，因此可保留在虚存中，并建立根页表来索引根页表包含 $2^{10}$ 个页表项，占用 4KB 内存

32位地址的两级页表

两级分页的逻辑地址结构，及地址映射示意图

例题 1：某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 $2^{10}$ 字节，页表项大小为 $2$ 字节。逻辑地址空间大小为 $2^{16}$ 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是多少？

这类计算题需要注意的是几个等量关系：

第二级页表也是页，所以页大小既指后面存数据的页面的大小，也指存页表项的二级页表的大小

而页目录就不是页了

如果页目录的长度为 $X$ 项，且一个页表的最大长度为 $Y$ 页，则一个进程可以有 $XY$ 页

回到题目，这个题有两种解法：

解法 1：

一个二级页表能存的页表项数 = 页大小 / 一个页表项的大小 $= 2^{10}/2 = 2^9$ 个
所以，二级页表的总数 = 总逻辑页数 / 一个二级页表能存的页表项数 = $2^7$
页目录的表项数 = 二级页表的总数 = $2^7$

解法 2：

二级页表总的项数 = 总逻辑页数 = $2^{16}$
二级页表总的大小 = 总表项数 * 页表项大小 = $2^{17}$
二级页表的总数 = 总的大小 / 一个二级页表能存的大小（换言之，页大小） = $2^7$
页目录的表项数 = 二级页表的总数 = $2^7$

头晕的时候做这题就很容易晕掉。

两级分页中的地址转换：

虚拟地址（逻辑地址）结构中分离出根页表号（如图8.3例虚拟地址前10位）
检索根页表，查找关于用户页的页表项
如果不在内存，产生一次缺页中断
若在内存，用虚拟地址中间页号（如前例虚拟地址中间10位）检索用户页表，查找对应的页表项
得到页框号，和页内偏移量一起形成物理地址

二级页表地址转换示意图

例题 2：80x86 硬件分页地址，32位逻辑地址空间、4KB页面、4B页表项，如何将逻辑地址 0x20021406 转换为物理地址？

页面大小 4KB，所以最后 12 位为页内偏移量
一个二级页表的页表项数 = 页面大小/页表项大小 = 1KB，所以中间 10 位为页号
剩下前面的 32-10-12=10 位就是页表页号了

0x20021406 = 0010000000 0000100001 010000000110

顶级页表字段 0x80，用于选择顶级页表的第0x80表项，指向二级页表
二级页表字段 0x21，用于选择二级页表的第0x21表项，指向逻辑地址所在页框
页内偏移地址字段 0x406，逻辑地址在页框内的偏移量

例题 3 图

例题 3：在例题 2 和上面的表结构中，求逻辑地址 4197721 （注意没有 0x，是十进制）的物理地址？

$4197721 = 1024 * 2^{12} + 3417$
$1024 = 1 * 2^{10} + 0$

页目录号	页号	页内偏移
1	0	3417

顶级页表字段为 1，用于选择顶级页表的第 1 表项，指向二级页表 202
二级页表字段 0，用于选择二级页表的第 0 表项，指向逻辑地址所在页框 505 页内偏移地址字段 3417，逻辑地址在页框内的偏移量物理地址： $505 * 2^{12} + 3417 = 2071897$

# 多级页表

对于某些机器，二级页表也可能非常大；可采用多级页表，对外层页表再进行分页，如三级页表。

会增加额外的存储空间。
页表的级数越多，地址转换过程越复杂，转换的速度也越慢。

# 倒置页表

上面的页表均使用页号作为索引，也就是说，有多少项虚拟页，就需要多少页表项；每个进程都需要有这么多页表项（即，页表大小和虚拟页数成正比），而实际的物理存储页数并没有这么多，不需要这么多页表项，导致严重的空间浪费。

于是发明了倒置页表（倒排页表）。页表结构称为“倒排”的原因是，它使用页框号而非虚拟页号来索引页表项（如下图）。另外，所有进程共用一张表倒排页表，因此无论有多少进程、支持多少虚拟页，页表大小只与物理页数成正比，只需要实存中的一个固定部分。

虚拟地址的页号部分使用一个简单的散列函数映射到散列表中，哈希值指向倒排页表。

倒排页表结构

使用时，计算出的散列函数会和每一个页号匹配（啊这似乎有点慢），匹配到了的下标 $i$ 即是页框号。如果没匹配到，会通过链指针跳到下面一项。

# 转换检测缓冲区（快表）

对于一级页表，每次虚存访问都可能会引起两次物理地址访问：一次取相应的页表项，另一次取需要的数据。

为了克服这个问题，大多数虚拟内存方案都为页表项使用了一个特殊的高速缓存，称为转换检测缓冲区 TLB (translation lookaside buffer，快表)。TLB 包含最近用过的页表项。

具有快表的地址转换流程：

给定一个虚拟地址，处理器首先检查 TLB
若命中，即页表项在TLB中，检索页框号形成物理地址
若未命中，即页表项不在TLB中，检索进程页表，查找相应页表项
- 若“存在位”已置位，页位于内存，用页框号+偏移量形成物理地址
- 若“存在位”未置位，页不在内存，产生缺页中断 (page fault)，装入所需页，更新页表

上面的描述中有三种情况：

页表项在 TLB 中，此时数据一定在内存中（正确性如何证明？可能和后面的换出算法有关）
页表项不在 TLB 中，但数据在内存中
页表项不在 TLB 中，数据也不在内存中

具有快表的地址转换示意图

具有快表的地址转换流程图

页表更新后需要回到出错指令，可能是因为中断恢复以后需要执行指令。

注意到在地址转换示意图中，处理器对 TLB 的查询是同时进行多项匹配的，这叫关联映射，需要硬件支持。

更复杂的是 TLB 和 CPU 高速缓存协同的相关操作。

页表项：可能在TLB中，也可能在内存或磁盘中
被访问的字：可能在高速缓存中，也可能在内存或磁盘中

TLB 和 CPU 高速缓存协同

用页号查询 TLB 或页表，找到页框号
用页框号和偏移量组合成实地址，然后查询缓存或内存，得到值

# 页尺寸

页尺寸是一个重要的硬件设计决策，它需要考虑多方面的因素。
其中一个因素是内部碎片。显然，页越小，内部碎片的总量越少。为优化内存的使用，通常希望减少内部碎片；另一方面，页越小，每个进程需要的页的数量就越多，意味着更大的页表。对于多道程序设计环境中的大程序，这意味着活动进程有一部分页表在虚存而非内存中。因此，一次内存访问可能产生两次缺页中断：第一次读取所需的页表部分，第二次读取进程页。
另一个因素是基于大多数辅存设备的物理特性，希望页尺寸比较大，从而实现更有效的数据块传送。

两个有意思的图：

缺页率：发生缺页的次数与总访问次数的比值。 P：进程大小 W：工作集大小 N：进程的总页数

缺页率与分配页框数的关系（页尺寸一定）

上图表明，对固定的页尺寸，内存中的页框数增加时，缺页率下降。

这个很好理解，内存变大了能存下更多的东西，换出的频率会更低。

缺页率与页尺寸的关系

上图表明，页尺寸很小时，缺页率低；页尺寸增加时，缺页率增加；页尺寸较大时，缺页率下降。

前面一段是由于局部性原理，内存利用率高，换出少，缺页率会较低，当尺寸变大时，局部性原理被削弱（一页包含的单元可能很多都不是最近需要访问的了），换出多，缺页率增高；但当页尺寸大到一页包含整个进程时，不会发生缺页中断。

页尺寸示例

页尺寸的设计问题与物理内存的大小和程序大小有关。当内存空间变大时，应用程序使用的地址空间也相应增长。这在应用程序变得越来越复杂的个人计算机上最为明显。

大型程序中所用的当代程序设计技术可能会降低进程的局部性：

面向对象技术：对小程序和数据的引用会分散在不同的对象中
多线程应用：指令流会突然变化，引用分散在内存中

# 分段

# 内容回顾

分段：

允许程序员把内存视作由多个地址空间或段组成

段大小不等，可以动态变化

内存访问时：段号+段内偏移量

优点：
简化了对不断增长的数据结构的处理

允许程序独立地改变或重新编译

有助于进程间的共享

有助于保护

# 段表项

段表项类似于页表项，只是多了一个长度。

页表项

# 地址转换

逻辑地址=段号+段内偏移量，寄存器存储段表地址
根据段表地址和段号查找段表，找到相应段在内存中的基地址
得到物理地址=基地址+段内偏移量

分段和分页的地址转换类似。

地址转换

# 段页式

用户的地址空间被程序员划分为许多段，每段划分为许多固定大小的页：

分段：

对程序员可见
支持数据结构增长（段长可变）
支持共享和保护

分页：

对程序员透明
消除外部碎片
有效利用内存

结合二者，就出现了段页式。

# 段页式的逻辑地址

用户地址空间被程序员划分成若干段，每段划分成若干页
程序员的角度：逻辑地址 = 段号:段内偏移量
系统的角度：段内偏移量 = 页号:页内偏移量

# 段表和页表

每个进程一个段表
每个段一个页表
段表项：含段长和对应页表的起始地址
页表项：含页框号、存在位P、修改位M等

段表和页表

# 地址转换

虚拟地址（逻辑地址） = 段号 : 页号 : 偏移量

寄存器存放段表起始地址
根据段表起始地址和段号查找段表，得到对应段的页表起始地址
根据页表起始地址和页号查找页表，得到页框号
页框号和偏移量构成物理地址

段页式的地址转换

例题 1：32 位逻辑地址，段最大大小为 16 KB，页大小为 4KB，问地址中各部分长度。

段号 18 位 + 页号 2 位 + 偏移量 14 位

在段页式系统中（不考虑缓存、TLB 等），为了获得一条指令或数据，至少需访问几次内存？

第一次，访问段表，从中获得该段的页表首址；
第二次，访问页表，从中取出逻辑地址指定的页面所在的页框号，并将该页框号和页内偏移量相加，形成物理地址；
第三次，根据物理地址，取出对应存储单元的指令或数据。
所以至少三次（如果发生缺页中断，次数会大于三）

# 保护和共享

分段有助于实现保护和共享机制

保护：每个段都包括一个长度和一个基地址，可以控制非法访问
共享：一个段可以在多个进程的段表中被引用，实现共享

示例：

一个多用户系统，可同时接纳 40 个用户，每个都执行一个文本编辑程序 (Text Editor)。如果文本编辑程序有 160 KB 的代码和另外 40 KB 的数据区，则总共需有 8000KB 的内存空间来支持 40 个用户。如果 160 KB的代码是可重入的(Reentrant，即能被共享)，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为 1760 KB(40×40+160)，而不是 8000 KB。

分页中的共享：假定每个页面 4KB，160KB 的共享代码需要 40 个页面，每个进程需要 40 个页表项来存储相应信息。

分页中的共享

分段中的共享：共享部分作为一个段，每个进程仅需一个段表项来存放共享段信息。

分段中的共享

下图说明了这类系统能实现的保护关系的类型。

系统能实现的保护关系的类型

# 操作系统软件

内存管理设计的三个基本选择：

是否使用虚拟技术
使用分页还是分段，或二者同用
为各种存储管理特征采用的算法（本节主题）

为实现虚拟内存，操作系统需要考虑的策略（软件方面）：

读取策略
- 请求调页 (Demand Paging)
- 预调页 (Prepaging)
放置策略
- 驻留在内存中的位置
置换策略
- 基本算法
  - 最优 (OPT)
  - 最近最少使用 (LRU)
  - 先进先出 (FIFO)
  - 时钟 (CLOCK)
- 页缓冲
驻留集管理
- 驻留集大小
  - 固定
  - 可变
- 置换范围
  - 全局
  - 局部
清除策略
- 请求式清除 (Demand)
- 预约式清除 (Precleaning)
负载控制
- 多道程序度（系统并发度）

# 读取策略

决定某页何时进入内存。

请求调页（Demand Paging，按需调页）
- 仅在引用页面时，才把相应的页面调入内存
- 进程首次启动时，会发生很多缺页中断
- 局部性原则表明，大多数将来访问的页面都是最近读取的页面，一段时间后，缺页中断会降低到很低的水平。
预调页（Prepaging）
- 额外读取所缺页面以外的页面
- 考虑大多数辅助储设备的特性：寻道、旋转延迟等
- 若进程的页面连续存储在辅存中，则一次读取多个页面会更有效
- 如果额外读取的页面未使用，则低效

# 放置策略

确定进程驻留在内存中的位置
分段系统中的重要设计内容，如首次匹配、循环匹配等
分页或段内分页中，放置策略无关紧要，因为硬件以相同的效率执行地址转换功能
对于非一致存储访问 (NUMA，NonUniform Memeory Access, NUMA)，需要自动放置策略

# 置换策略（重点）

页面置换涉及的问题：具体淘汰哪个页面用以置换

置换策略 (Replacement policy)：读取新页时，如何选择内存中要淘汰的页面

目标：最近最不可能访问的页面
置换策略越精细，实现它的硬件和软件开销就越大

# 页框锁定

当页框被锁定时，当前存储在该页框中的页面不能被置换
操作系统内核和重要的数据结构保存在锁定的页框中
I/O缓冲区和时间要求严格的区域也可能保存在锁定的页框中
通过将锁定位与每个页框相关联来实现锁定

# 几种基本的置换算法

最佳 (Optimal, OPT，理想算法)
最近最少使用 (Least recently used, LRU)
先进先出 (First-in-first-out , FIFO)
时钟 (Clock)

评价置换算法的重要指标：

缺页率——给定时间内，发生缺页的次数与访问总次数的比值

# 最佳 (OPT)

置换下次访问距当前时间最长的页面
理想算法（不可实现），缺页率最少

OPT 算法示例

F表示所分配的页框在初始填满后产生缺页中断。

# 最近最少使用 (LRU)

置换内存中最长时间未引用的页面
根据局部性原理，这也是最近最不可能访问的页面
难以实施
- 每页添加最近访问时间戳——开销大
- 建立链表——开销大

LRU 算法示例

# 先进先出 (FIFO)

将分配给进程的页框视为循环缓冲区
页面以循环方式删除——简单的置换策略
置换驻留在内存中时间最长的页面

FIFO 算法示例

# 时钟 (CLOCK)

每个页框关联一个使用位
当页面首次加载到内存中或被引用时，使用位设置为1
用于置换的候选页框集视作一个循环缓冲区
发生缺页中断时，检查表针指向页面，如果使用位为 0，则新页面替换之,表针前移一个位置；如果使用位为 1，则清 0，表针前移一个位置。重复上述过程。
注意：命中时表针不移动，而是将根据第二条，将命中位的使用位设为 1

时钟算法图

这个算法类似于 FIFO，但不同的是，在时钟策略会跳过刚访问过的页框。

示例 1：页 727 进入内存前，需要选择一个页置换。
从指针当前位置开始，顺时针移动，最后选择页556置换。

时钟算法示例 1

时钟算法示例 2

图中 * 表示 use=1。注意第 5 步时，时钟实际上转了一圈，将所有点标记为 use=0 后，替换掉了第一个 2。

例题：假设系统为某进程分配了3个页框，其页面走向如下：7 0 1 2 0 3 0 4，求采用CLCOK页面淘汰算法，在初始3个页框装满后缺页中断的次数。

例题模拟

共三次缺页。

# 置换算法比较

几种置换算法比较（固定分配，局部置换）

# 改进 Clock 算法

在Clock算法基础上，优先置换最近未访问、未修改（如果这块内存被修改了，换出时就涉及到写硬盘操作）页面。

每个页框处于下列情形之一（u:访问位，m:修改位）：

1类(u=0, m=0)：最近未被访问，又未被修改，最佳淘汰页。
2类(u=0, m=1)：最近未被访问，但已被修改页。
3类(u=1, m=0)：最近已被访问，但未被修改。
4类(u=1, m=1)：最近已被访问且被修改，最不应淘汰页。

2 和 3 类选择谁先淘汰呢？其实先淘汰谁都是可以的。根据 LRU 的原则，我们优先选择 2 进行淘汰。

算法流程：

从指针当前位置开始扫描，这次扫描对使用位不作任何修改，选择遇到的第一个页框 (u=0,m=0) 置换；——会置换掉 u=0, m=0
若第 1 步失败，重新扫描，选择遇到的第一个 (u=0,m=1) 的页框置换。这一过程中，将使每个扫描过的页框u置0；——会置换掉 u=0, m=1
若第 2 步失败，则再次重新扫描，重复第 1 步；——会置换掉 u=1, m=0
若第 3 步失败，则再次重新扫描，重复第 2 步；——会置换掉 u=1, m=1

改进型时钟置换算法实现简单，性能比较理想，被广泛采用（如早期 Linux）。（后来 Linux 使用类 LRU 算法）

# 页缓冲

置换的页，如果被修改过，就得写回辅存，代价较大。
在内存中采用页缓冲，提高了分页性能，并允许使用更简单的页面替换策略（如 FIFO）。

置换的页面：

未修改，放入空闲页链表（由可用来存放读入页的一系列页框构成）尾部
已修改，放入修改页链表（已修改页按簇、成批写回磁盘会更快）尾部

页缓冲的一个作用是起了类似于磁盘的高速缓存的功能。若进程访问在页缓冲的页，该页就可以被直接放到驻留集中。

（可是为什么要拿一部分内存来作页缓冲，而不是直接把这部分内存加到进程里呢？可能是因为页缓冲是全局的，而不是每个进程都有一个）

除此之外，页缓冲的修改页链表还有一个作用，就是使已修改的页按簇写回，大大减少了 I/O。这便是和清除策略的联动。

# 置换策略和高速缓存大小

对于较大的高速缓存，替换页会对性能产生影响：如果选择替换的页在高速缓存中，则该高速缓存块及内存中所对应的页将失效。

在使用页缓冲的系统中，可以使用页缓冲区中的页放置策略来提高高速缓存性能。

大多数操作系统通过从页缓冲区中选择任意页框来放置高速缓存中需置换的页，但如果使用细致的页放置策略，能减少 10%~20% 的高速缓存失效。

具体的高速缓存结构、页放置策略超出了本书的范围。

# 驻留集管理

驻留集定义

# 分配和置换

驻留集管理设计到了分配和置换。

页框分配，即给每个活动进行分配多少个页框
- 分配给每个进程的内存越小，可以驻留在内存中的进程越多
- 若一个进程在内存中的页面少，则缺页率相对较高
- 给进程分配的页框数超出一定大小后，由于局部性原理，缺页率下降到稳定水平
置换范围，即计划置换的页集局限于产生缺页的进程本身，还是内存内的所有进程

分配和置换算法

固定分配：在内存中为每个进程提供固定数量的页框
可变分配：允许分配给每个进程的页框数在进程的生命周期内变化
局部置换：仅在该进程的驻留页中选择置换对象
全局置换：在整个内存中选择置换对象，只要不是锁定的页，都可以作为候选页

两两组合就有如下情况：

组合	局部置换	全局置换
固定分配	分配给进程的页框数固定；从分配给该进程的页框中选择被置换的页	此方案逻辑上不存在
可变分配	为了保存进程的工作集，分配给进程的页框数不时变化；从分配给该进程的页框中选择被置换的页	从内存中所有可用页框中选择被置换的页；进程驻留集大小不断变化

# 固定分配，局部置换

需要事先确定分配给一个进程的页框数量
如果给进程分配的数量太少，将会产生较高的缺页率
如果给进程分配的数量太多，内存中只有较少的程序，增加处理器空闲时间（时间用于交换）

# 可变分配，全局置换

最容易实现的方法，在很多操作系统里采用
操作系统维护一个空闲页框列表
当缺页中断发生时，一个空闲页框分配给缺页的进程
如果没有空闲页框，操作系统必须选择一个内存中的页框（没有锁定，没有被内核占用）作为置换对象
如果选择置换对象不当，将容易再次产生缺页中断，使用页缓冲可以缓解这个问题

# 可变分配，局部置换

当一个新进程装入内存时，分配一定数量的页框作为它的驻留集
当缺页中断发生时，从进程驻留集中选择一页用于置换
不时重新评估进程的页框分配情况，增加或减少分配的页框，以提高整体性能

这种组合的关键要素：

决定驻留集大小的原则
驻留集大小变化的时机

于是产生了工作集的概念。尽管真正的工作集策略很难实现，但它可作为比较各种策略的标准。

# 工作集

定义：进程在虚拟时刻为 $t$ 、参数为 $Δ$ 的工作集 $W(t, Δ)$ ，表示该进程在 $t$ 时刻，过去的 $Δ$ 个虚拟时间单位（即 $t-Δ+1, t-Δ+2, ..., t$ 时刻）被访问到的页的集合。

虚拟时刻的定义是靠进程访问内存的次数实现：例如进程一系列的内存访问为 $r(1),r(2),…r(i)$ ， $r(i)$ 表示第 $i$ 次对内存页的访问，对应的虚拟时间为 $1$ , $2$ ,… $i$ 。

$Δ$ 为给定的虚拟时刻时，进程的窗口大小。

显然，虚拟时刻窗口越大，则工作集越大。即：

W(t, \Delta+1) \supseteq W(t, \Delta)

如下为一个工作集的示例。

工作集示例

对于固定的 $Δ$ ，工作集大小随时间变化的情况：稳定阶段和快速变化阶段交替出现。这是因为局部性原理。

工作集大小随时间变化的情况

工作集的概念可用于指导有关驻留集大小的策略：

根据工作集来决定驻留集的大小
周期性的从驻留集中移去不在工作集中的页（近似 LRU）
只有驻留集包含工作集时，才执行进程

这种策略很有吸引力，因为它采用了一个公认的原理——局部性原理，并利用该原理设计了一个可以减少缺页中断的内存管理策略。遗憾的是，工作集策略仍然存在许多问题:

工作集大小随时间变化
给每个进程测量工作集不现实
$Δ$ 最优值未知

所以产生了近似工作集策略（代表性算法：PFF，VSWS）：

用缺页率指导驻留集
缺页率低于某个阈值时，减小驻留集
缺页率超过某个阈值时，增加驻留集

# 例题

设某计算机的逻辑地址空间和物理地址空间均为 64KB，按字节编址。若某进程最多需要 6 页存储空间，页的大小为 1KB。操作系统采用固定分配局部置换为此进程分配 4 个页框，如下表所示。

页表 & 时钟置换算法图

若该进程执行到 260 时刻时，要访问逻辑地址为 17CAH 的数据，请回答：

该逻辑地址对应的页号是多少？
若采用先进先出 (FIFO) 置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
若采用时钟 (CLOCK) 置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针沿着顺时针方向移动，且当前指向 2 号页框，所有页框 use 标志均为 1，如上图所示）

1KB 页号意味着 17CAH 的后十位为页内偏移地址，前 6 位（000101B，5）为页号（故需要置换）
FIFO 应该换掉最早装入的 7 号页框。故换入后，页框号为 7，物理地址为 7 拼接 17CAH 的后十位，为 1ECAH。
根据时钟算法，程序会查找一圈，将四个页框依次标记为 use=0；然后遍历到 2，淘汰掉 2 号页框并换入。物理地址为 2 拼接 17CAH 的后十位，为 0BCAH。

# 平均访问时间

若缺页率为 $p$ ，内存的访问时间为 $ma$ ，发生缺页时的访问时间为 $da$ ，则平均访问时间为：

(1-p)*ma+p*da

就是一个简单的已知概率算期望。

发生缺页时访问时间 $da$ 的构成：

缺页中断服务时间
页面写出时间（若需置换）
页面调入时间—— 20ms（寻道时间+旋转时间+数据传送时间）
重新访问内存指令时间

由于 $ma$ 很小（<10ns），因此很低的缺页率也会导致很大的平均访问时间。

例题 1：

假设内存的访问时间为 $10ns$ ，发生缺页的访问时间为 $21ms$ ，若因为缺页而出现的性能降低不超过 10%，则缺页率的最大数值为多少？

下降 10% 的有效访问时间应不超过 10*(1+10%)=11ns

11 \geq (1-p)*10+21*10^6*p

解得 $p \leq 5 \times 10^{-8}$ 。

可见很低的缺页率也会导致很大的平均访问时间。

例题 2：

请求分页管理系统中，假设某进程的页表内容如下：

某进程的页表

页面大小为 4 KB，一次内存的访问时间是 100ns，一次快表 (TLB) 的访问时间是 10ns，更新快表的时间为 20ns，处理一次缺页的平均时间为 $10^8$ ns (只更新页表，不更新快表)，进程的驻留集大小固定为 2，采用最近最少使用置换算法 (LRU) 和局部淘汰策略。假设：① TLB 初始为空；② 有效位为 0 表示页面不在内存。

设有虚地址访问序列 2BEAH、1CADH、2242H，问：

依次访问上述三个虚地址，各需要多少时间？
基于上述访问序列，虚地址 1CADH、2242H 的物理地址是多少？

页大小为 4 KB，故页内偏移占后 12 位。三次访问的页号分别为 2、1、2。

第一问计算访问时间，访问流程可参考转换检测缓冲区（快表）中的流程图，如下。

具有快表的地址转换流程图

访问第 2 页：访问 TLB + 访问页表（访问内存） + 更新 TLB + 访问页面（访问内存） = 230ns
访问第 1 页：访问 TLB + 访问页表（访问内存） + 处理缺页 + 访问 TLB + 访问页表（访问内存） + 更新 TLB + 访问页面（访问内存）= 100000340ns
再次访问第 2 页：访问 TLB + 访问页面（访问内存）= 110ns

第二问，在访问 1CADH 时发生缺页，根据 LRU 和局部淘汰策略，将把 0 页换出，故更新后，1 页的页框号将为 CA2H。1CADH 的物理地址为 CA2CADH；2242H 的物理地址为 B2F242H。

# 清除策略

清除策略用于确定何时将修改过的页写回辅存。

按需清除 (Demand cleaning)：只有当该页被置换时，才写回辅存。但缺页中断后，需进行两次页传送（写回原页 和 读入新页），降低处理器利用率
预清除 (Precleaning)：将修改的多页在被置换前，成批写回辅存。但预先写回辅存的页，在置换前可能又会被修改，使得预清除意义不大

一种较好的方法是结合页缓冲技术的按需清除：去掉了 写回原页 和 读入新页 的成对关系。当页被置换时，不立即将该页写回磁盘，而是加入页缓冲；页缓冲就负责在某个时刻将修改的页成批写回辅存。

# 加载控制

加载控制决定驻留在内存中的进程的数量，这称为多道程序度 (multiprogramming level，也称系统并发度)。

加载控制对于有效的内存管理来讲非常重要：

内存驻留的进程太少 -> 所有进程都阻塞的概率变大 -> 大量时间花在交换上
内存驻留的进程太多 -> 平均每个进程的驻留集变小 -> 不够用 -> 频繁缺页中断 -> 抖动

多道程序度对处理器利用率的影响

一种思路是 L=S 准则 (Denning 1980)：发生缺页的平均时间 L 等于处理缺页故障的平均时间 S，此时处理器的利用率最大。

（相当于处理完一个缺页后，刚好下一个缺页发生了）

另一种思路是监测 Clock 置换算法中指针扫描的速度：

速度低，缺页率低，增加多道程序度
速度高，缺页率高或多道程序度高，降低多道程序度

进程挂起系统并发度减小时，一个或多个当前驻留进程须被挂起 (换出)。可以有下面 6 种选择方式:

最低优先级进程
缺页中断的进程
最后被激活的进程
具有最小驻留集的进程
最大空间的进程
具有最大剩余执行时间的进程

# 四 I/O 管理与磁盘调度

# 五文件系统

# 概述

# 文件

文件是用户或系统创建的数据集。从用户的角度来看，文件是操作系统的重要组成部分

文件拥有的理想属性：

长期存在（文件存储在硬盘或其它辅存中，用户退出系统时文件不会消失）
可在进程间共享（文件有名字，具有允许受控共享的相关访问权限）
结构（文件可以组织成为层次结构或更复杂的结构，以反映文件之间的关系）

# 文件系统

文件系统是提供存储数据的手段，且提供一系列对文件进行操作的功能接口（创建、删除、打开、关闭、读、写等）。

文件系统还会为文件维护一组属性（所有者、创建时间、修改时间等）。

# 文件结构

讨论文件时通常要用到如下 4 个术语：

域：基本数据单元。包含一个值（如雇员的名字、日期、传感器读取的值），定长或变长
记录：域的集合，可视为应用程序的一个单元。如雇员记录，，其中包含域：名字、工作名、雇用日期等。
文件：一组相似记录的集合，可被用户和应用程序视为一个实体。文件通过名字访问，且访问控制通常在文件级实施
数据库：相关数据的集合，元素中存在明确关系。数据库供不同应用程序使用。

# 文件管理系统

文件管理系统需满足以下目标：

满足数据管理要求和用户需求
保证文件中的数据有效
优化性能
为各种类型的存储设备提供 I/O 支持
最大限度地减少丢失或破坏数据的可能性
为用户进程提供标准 I/O 接口例程集
在多用户系统中为多个用户提供 I/O 支持

第一条中，用户需求的最小范围应包含：

用户能够：

创建、删除、读取和修改文件
受控地访问其他用户的文件
允许进行哪些类型的访问
以适合问题的形式重组文件
在文件间移动数据
备份文件，且在文件遭到破坏时恢复文件
通过名字而非数字标识符访问自己的文件

# 文件系统架构

文件系统架构

设备驱动
- 最底层
- 直接与外围设备（或它们的控制器或通道）通信
- 负责启动设备上的 I/O 操作
- 处理 I/O 请求的完成
- 通常视为操作系统的一个组成部分
基本文件系统
- 称为物理 I/O 层
- 与计算机外部环境的基本接口
- 处理在磁盘间或磁带系统间的数据块
- 关注数据块在辅存的放置位置
- 关注数据块在内存缓冲区的放置位置
- 通常视为操作系统的一个组成部分
基本I/O管理程序
- 负责所有文件I/O的初始化和终止
- 维护处理设备I/O，调度和文件状态的控制结构
- 选择要执行I/O的设备
- 关注调度磁盘和磁带访问以优化性能
- I/O缓冲区的指定和辅存的分配
- 通常视为操作系统的一个组成部分
逻辑I/O
- 使用户和应用程序能够访问记录
- 提供一种通用的记录I/O能力
- 维护文件基本数据
访问方法
- 文件系统中与用户最近的一层
- 提供应用程序和文件系统以及保存数据的设备之间的标准接口
- 不同的访问方法反映了不同的文件结构以及访问和处理数据的不同方式

???

# 文件管理功能

用户和应用程序通过文件操作与文件系统交互，通过目录确定文件的位置。
授权用户以特定的方式访问特定的文件；
用户通过文件操作函数，基于字符流／或记录来操作文件；
系统对文件的I/O是以块为单位，基于块来完成输入／输出；
操作系统需要为文件在磁盘上分配空闲块，同时还需要管理空闲空间。

文件管理的要素

？？？

# 文件的组织和访问（重点）

文件组织 (file organization) 指文件中记录的逻辑结构，由用户访问记录的方式确定。

选择文件组织的 5 个重要原则：

快速访问
易于修改
节约存储空间
维护简单
可靠性

原则的优先级取决于使用文件的应用程序。

五种基本文件组织：

堆
顺序文件
索引顺序文件
索引文件
直接或散列文件

# 堆文件

最简单的文件组织形式
按照到达的顺序收集数据
每条记录由一串数据组成
目的是积累大量数据并保存
通过穷举查找方法检索记录

堆文件

# 顺序文件

最常见的文件组织形式
记录有固定的格式
所有记录的长度都相同：每个域的位置、长度等相同
每个记录中有一个关键域，唯一标识这个记录
记录按照关键域存储和排序
通常用于批处理应用中
可以很容易地存储在磁盘和磁带

顺序文件

# 索引顺序文件

保留顺序文件的关键特征：记录按照关键域组织
增加了支持随机访问的索引和溢出文件
索引提供快速接近目标的查找能力
溢出文件类似日志文件，要往文件中插入记录时，可以将其放在溢出文件中，并由主文件中它(即所插入记录)的前一个记用指针指向它
可按批处理方式合并溢出文件
索引可以有多级，类似于多级页表

索引顺序文件

索引文件：

只能通过索引访问记录
可以使用变长度记录
完全索引包含主文件中每条记录的索引项
部分索引只包含有感兴趣域的记录的索引项
主要用于信息及时性要求比较严格且很少对所有数据进行处理的应用程序

索引文件

# 直接文件或散列文件

直接访问磁盘中任意一个地址已知的数据块
使用基于关键字的散列
典型应用场景：
- 快速访问；
- 固定长度的记录
- 一次只访问一条记录
例子:
- 目录
- 价格表
- 调度
- 名字列表

# 文件目录

文件目录里每个文件项包含的信息：

基本信息
地址信息
访问控制信息
使用信息

# 硬链接

硬链接目录不允许目录链接，防止目录套娃（ggd）

# 一 操作系统概述

# 操作系统的目标和功能

# 操作系统的历史

# 串行处理

# 简单批处理系统

# 多道批处理系统

# 分时系统

# 实时系统

# 操作系统的主要成就

# 进程

# 内存管理

# 信息保护和安全

# 调度和资源管理

# 现代操作系统的特征

# 容错性

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

# 主流操作系统（略）

# 单体内核

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

# 什么是进程

# 进程状态

# 进程轨迹

# 进程的两状态模型

# 进程的创建和终止

# 进程的五状态模型

# 挂起

# 进程描述

# 进程控制

# 内核

# 执行模式

# 进程创建

# 进程切换

# 系统中断

# 模式切换

# 进程状态转换

# 总结几个概念的关系

# 操作系统的执行

# Unix SVR4 的进程管理

# Unix SVR4 的进程状态图

# Unix SVR4 的进程创建

# 线程

# 线程与进程

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

# 线程分类

# 用户级线程 ULT

# 内核级线程 KLT

# 混合方法

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

# 调度的类型

# 长程调度

# 中程调度

# 短程调度

# 调度的规则

# 相关概念

# 调度规则总结

# 优先级的使用

# 调度的决策模式

# 调度算法

# 概述

# 先来先服务 FCFS

# 时间片轮转 RR

# 短进程优先 SPN

# 剩余时间最短优先 SRT

# 响应比高者优先 SRRN

# 反馈调度法 Feedback

# 实时系统与实时调度

# 实时任务分类

# 实时操作系统特点

# 实时调度的两个维度

# 调度方法分类

# 静态表驱动调度表

# 静态优先级抢占调度法

# 基于动态规划的调度法

# 动态尽力调度法

# 抢占方式分类

# 实时调度方法实例

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

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

# 实例：周期性实时任务

# 实时系统处理能力限制

# 一操作系统概述