操作系统 · 参考目录

一、基本概念

操作系统的作用
操作系统的体系结构
- 内核概念
处理器状态
- 用户态
- 核心态
系统调用
中断和异常

二、进程管理

进程与线程
- 基本概念
- 进程 / 线程状态及转换
CPU 进程调度算法
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 最短剩余时间优先（SRTN）
- 高响应比优先（HRRN）
- 时间片轮转
- 优先级调度
- 多级反馈队列
进程同步与互斥
- 信号量机制
- 生产者 - 消费者模型
- 读者 - 写者问题
- 哲学家进餐问题
进程通讯机制
死锁
- 死锁产生的条件
- 死锁预防与避免
- 死锁检测与恢复

三、内存管理

基本概念
- 内存
- 内存管理
- 地址空间
覆盖与交换
内存分配与回收
- 连续内存分配
  - 单一连续分配
  - 内存碎片
  - 分区
    - 固定分区分配
    - 动态分区分配
- 非连续内存分配
  - 分段存储管理
  - 分页存储管理
  - 页表
  - 二级页表
  - 多级页表
  - 反向页表
  - 地址变换机构
    - 基本
    - 基于快表
  - 段页式存储管理
- 虚拟内存（非连续内存分配）
  - 基本概念
  - 局部性原理
  - 实现
    - 请求分段存储管理
    - 请求分页存储管理
    - 请求段页式存储管理
  - 页面置换算法
    - 最佳置换算法（OPT，理想置换算法）
    - 先进先出置换算法（FIFO）
    - 最近最久未使用置换算法（LRU）
    - 时钟置换算法（CLOCK）
    - 第二次机会算法
  - 页面分配策略

四、文件管理

基本概念
- 文件系统
- 文件
  - 逻辑结构
  - 物理结构
- 目录
- 文件描述符
文件操作

五、磁盘管理

磁盘结构
磁盘调度算法
- 先来先服务（FCFS）
- 最短寻找时间优先算法（SSTF）
- 扫描算法（SCAN，经典电梯调度算法）
- 循环扫描算法（CSCAN）

六、设备管理

基本概念
- I/O 设备
- I/O 设备分类
I/O 控制
缓冲区管理

引论

操作系统（Operating System）有四个特征：并发、共享、虚拟与异步。其中，并发与共享是两个最基本的特征，互为条件。

特权、中断与系统调用

处理器内有一个名为PSW（Program Status Word，程序状态字寄存器）的特别寄存器，通过二进制的模式位标识当前程序处于用户态还是内核态（注：PSW不仅包含模式位，还包括条件码、优先级位等其他控制位，在x86处理器中该模式位名为CPL，在ARM中则名为CPSR.M）。如果即将执行的指令是特权指令，但CPU在检查PSW后发现自身处于用户态时、即当前程序为应用程序而非内核程序时，处理器会立即停止执行当前程序指令并产生一个特殊内中断信号，操作系统内核将处理这一中断。

从内核态转为用户态需要执行一条特权指令以改变PSW标志位，意味着操作系统将处理器交由应用程序使用；从用户态转为内核态则能且只能通过中断触发，并在触发后由硬件自动地切换至内核态。

现代CPU特权级别分为Ring 0、Ring 1、Ring 2与Ring 3，其中Ring 0即内核态，Ring 3即用户态。但实际上，现代操作系统很少使用Ring 1与Ring 2。

中断（Interrupt）是程序需要处理器打断当前正在执行的代码以便内核程序及时接管并处理事件的请求。

如果中断请求与当前执行的指令有关、中断信号源于处理器内部，则称为内中断，也被称为异常。
1. trap：程序需要申请系统调用时，会执行一条非特权指令——trap指令，该指令会引发一个trap中断信号。
2. fault：故障中断。内核程序可能可修复的故障，并且会在修复故障后恢复现场，例如缺页故障。
3. abort：终止中断。由内核程序所不能修复的致命错误引起，处理器一般会终止该应用程序，例如应用程序试图进行除数为0的除法运算时，会产生除零中断。
相反地，如果中断请求与当前执行的指令无关、中断信号源于处理器外部并通过中断控制器传递，则称为外中断，这也是狭义上的中断。

例如来自晶振的时钟中断与来自其他设备的I/O中断。

现代处理器会在指令流水线阶段间隙检查是否有需要处理的外中断。

发生中断后，处理器将查询中断向量表（IVT），并根据中断类型从中找到并跳转至能够处理相应中断的内核程序。

中断还分为可屏蔽中断与不可屏蔽中断。例如，原语程序能够通过清除RFLAGS/PSW寄存器中的IF标志位暂时关闭可屏蔽中断响应，使处理器在操作完成前记录但不响应此类中断，待原语完成后再通过中断控制器处理记录在案的可屏蔽中断。电源中断与硬件错误中断则是典型的不可屏蔽中断，必须立即响应。通常可屏蔽中断由中断控制器管理，不可屏蔽中断则由专用引脚触发，具有最高优先级。

USB键盘和鼠标就是通过中断向操作系统传递输入的。

补充：除了PSW外，CPU内还有些其他的特别寄存器，

IR（Instruction Register，指令寄存器）
SP（Stack Pointer，堆栈寄存器），SP分为用户态SP与内核态SP
PC（Program Counter，程序计数器），存储下一条指令的地址
SR（Status Register，状态寄存器），一共有32bit但一般只使用6bit，分别存储：

非特权位：
- Z(zero)：一般情况下，在程序出错时返回非零值
- V(overflow)：是否溢出
- N(negative)：是否为负值
内核特权位，只有内核程序有权限修改：
- I(Interrupt)：是否为中断指令
- S(System mode)：标识CPU处于用户态还是内核态
- P(Paging)：是否启用分页相关功能与权限
PTR（Page Table Register，页表寄存器），存储页表的物理基址和长度，直接参与地址转换过程
SR（Segment Register，段寄存器），存储段的物理基址和长度，直接参与地址转换过程

凡是与共享资源有关的操作，例如存储分配、I/O操作与文件管理，均必须通过系统调用的方式向操作系统内核提出服务请求，并在内核接受后由内核代为完成，从而确保资源访问的原子性和安全性。

系统调用的过程：用户态下的应用程序将系统调用所需的参数存入处理器的寄存器（如果有），然后执行trap指令，触发trap中断，此时处理器进入内核态，内核将接管处理器。

体系结构、引导与虚拟机

其中，原语程序（Primitive）是操作系统中不可分割的最小功能单元，由若干条机器指令组成，用于完成特定关键操作（如进程同步、资源分配等）。其核心特征是原子性——要么完整执行，要么完全不执行，执行过程不可被中断。

典型的宏内核：Linux，UNIX

典型的微内核：Mach

典型的混合内核：Windows NT，macOS

宏内核性能最高，执行应用程序时不需要频繁地切换处理器状态，但结构复杂、更难维护。混合内核则将部分对性能要求较高的服务集成在内核中，例如设备驱动、进程通信等。

操作系统引导（boot）的传统流程BIOS+MBR：

处理器从一个特定的主存地址读取指令，并执行ROM中的引导程序（自举程序），进行硬件自检等操作。在现代计算机中ROM通常为BIOS芯片，存储BIOS或UEFI固件。
位于磁盘上第一扇区（512字节）的MBR（Master Boot Record，主引导记录）被读入内存的0x7C00地址，其中包含磁盘引导程序与分区表，处理器将执行446字节的磁盘引导程序并扫描分区表以便后续加载活动分区的PBR。
磁盘上的活动分区上除了MBR以外，还包含PBR（Partition Boot Record，引导记录）、根目录与其他空间。接下来，处理器将从活动分区上读取PBR，执行相应程序。
最后，处理器读取根目录上的完整操作系统初始化程序——启动管理器并执行。

在UEFI+GPT的引导流程中，无需依赖MBR代码的链式引导，计算机能够直接加载ESP分区下的EFI应用程序启动系统；同时，使用GPT（GUID分区表）代替MBR分区表，支持大于2TB的磁盘和最多128个主分区。

进程与线程

进程与线程的状态

进程与程序是不同的概念。进程是被存放在磁盘上的静态的可执行文件，是一系列指令的集合，而进程则是动态的，是程序的一次执行过程。

操作系统在创建进程时，会为进程赋予一个唯一的PID（Process ID）。当然也会记录UID、资源分配情况、进程运行情况等，这些信息都会被记录在PCB（Process Contorl Block，进程控制块）中。在Linux bash/zsh中可以通过ps aux | grep "Google"查询操作系统中所有进程并过滤特定字符串。

内存中的进程实体被称为进程映像，由PCB、程序段与数据段组成。

进程的状态转换：

创建态
就绪态
运行态
阻塞态
终止态

IPC（Inter-Process Communication，进程间通信）指两个进程间的数据交互。

进程是独立运行与独立获得资源的基本单位，内核级线程是独立接受调度的基本单位——如果该操作系统支持内核级线程的话，否则调度的基本单位也是进程。区分子进程与线程。

线程（thread）分为用户级线程与内核级线程。类似进程的PCB，线程也有相应的TCB，内容包括了TID、线程运行状态、优先级，还有PC、SP以及其他寄存器上的数据，其中TCB存储寄存器上的数据是为了在线程切换时保存或恢复现场。多个TCB可以组织为一张线程表。

进程通信与同步

这部分内容来自DeepSeek-R1的整理。

进程通信方式

管道（Pipe）
- 匿名管道
  
  定义：单向通信的半双工机制，仅适用于父子进程或兄弟进程等具有亲缘关系的进程。
  
  特点：通过pipe()系统调用创建，数据按先进先出（FIFO）顺序传输，需手动同步读写操作。
  
  缺点：仅支持单向通信，且缓冲区大小有限（如4KB）。
- 命名管道（FIFO）
  
  定义：具有文件名标识的管道，允许无关进程通信。
  
  优点：突破了亲缘关系限制，适用于长期存在的通信需求。
消息队列（Message Queue）

定义：由内核维护的消息链表，支持进程以格式化的数据块（消息）传递信息。

优点：
- 支持不同类型消息的优先级管理。
- 允许无关进程通信，无需同步机制（由内核实现同步）。
缺点：消息复制需消耗CPU时间，不适合高频或大数据量场景。
共享内存（Shared Memory）

定义：多个进程将同一块物理内存映射到各自的虚拟地址空间，直接读写数据。

优点：无需数据复制，传输效率最高。

缺点：
- 需额外同步机制（如信号量）避免读写冲突。
- 仅适用于同一主机内的进程。
信号量（Semaphore）

定义：基于整型变量的同步机制，通过P()（等待）和V()（信号）操作控制资源访问。

用途：主要用于进程互斥与同步，而非直接传输数据。

分类：
- 公用信号量：用于多进程互斥访问共享资源。
- 私有信号量：用于特定进程间的同步。
套接字（Socket）

定义：网络通信接口，支持不同主机上的进程通信。

特点：
- 支持面向连接（TCP）和无连接（UDP）模式。
- 适用于分布式系统和跨网络通信。
文件（File）

定义：通过读写文件间接实现数据交换。

场景：一个进程将数据写入文件，另一进程读取该文件。

缺点：效率低，需处理文件锁与并发访问冲突。

进程同步方法

进程同步（Synchronization），是指让并发的进程按要求有序地推进。

信号量（Semaphore）

原理：通过原子操作P()和V()控制资源计数，实现互斥与同步。

应用：
- 互斥锁（Mutex）：信号量初始化为1，保证单进程访问临界区。
- 资源池管理：信号量初始化为N，限制并发访问数。
管程（Monitor）

定义：结构化同步机制，将共享数据和操作封装为模块，仅通过接口访问。

特点：
- 自动处理互斥，程序员无需手动同步。
- 通过条件变量（cwait()和csignal()）实现复杂协作。
互斥量（Mutex）

定义：内核对象，确保同一时间仅一个线程/进程访问临界资源。

优点：支持跨进程同步，适用于多进程共享资源场景。

与信号量的区别：互斥量是信号量的特例（资源数=1）。
临界区（Critical Section）

定义：用户态同步机制，限制代码段仅能被单线程执行。

特点：
- 仅适用于同一进程内的线程同步。
- 速度快，无内核切换开销。
事件（Event）

定义：通过通知机制唤醒等待线程，常用于线程间协作。

场景：生产者-消费者模型中，生产者完成数据生成后触发事件通知消费者。

调度与调度算法

在原语操作、处理中断以及进程位于操作系统内核程序临界区中时，不能进行进程调度与切换。普通临界区的临界资源虽然要求各进程互斥地访问，但存在进程调度与切换。

在大多数时候，现代计算机都在执行idel进程。idel进程优先级最低，执行HLT等指令让CPU进入低能耗状态，此时CPU通过中断控制器持续监听中断信号。在许多操作系统设计中，idel进程的PID为0。

调度算法评价指标：

CPU利用率
系统吞吐量：单位时间内完成作业数量
（平均）周转时间：从作业被提交开始，到作业被完成的（平均）时间开销

周转时间包括四个部分：
1. 高级调度时间（作业在外存后备队列上等待作业调度的时间）
2. 低级调度时间（进程在就绪队列上等待进程调度的时间）
3. 进程在CPU上的执行时间
4. 进程等待I/O操作完成的时间
2、3、4可能发生多次。

（平均）带权周转时间：(作业完成时间 - 作业提交时间) / 作业实际运行时间
（平均）等待时间：对于进程而言，等待时间是（平均）低级调度时间；对于作业而言，等待时间是高级调度与低级调度（平均）时间之和
（平均）响应时间：从用户提交请求到计算机首次产生响应的时间

常见的批处理操作系统调度算法：

先来先服务（FCFS）
- 按照作业或进程到达的先后顺序进行服务。
  - 用于作业调度时，先到达后备队列的作业先调度。
  - 用于进程调度时，先到达就绪队列的进程先调度。
- 非抢占式算法：只有当前运行的进程主动放弃处理机时（正常完成、异常完成或主动阻塞），才需要进行调度。
- 优点：公平，算法实现简单，不会产生长作业的饥饿现象
- 缺点：带权周转时间极大，对长作业有利，对短作业不利
短作业优先（SJF），短进程优先（SPF）
- 根据作业/进程的运行时间的长短，最短的作业/进程先得到服务。
- 非抢占式算法，但存在抢占式的版本——最短剩余时间优先（SRTN），当有新进程加入就绪队列时，如果新到达的进程剩余时间比当前运行进程的剩余时间更短，则由新进程抢占处理机，当前进程回到就绪队列。
- 优点：当所有进程几乎同时到达时，该算法的平均等待时间与平均周转时间最短；SRTN可忽略这一前提条件。即使前提不成立，SJF的平均等待时间与平均周转时间开销仍然相对较低。
- 缺点：不公平，对短作业有利，对长作业不利，存在长作业的饥饿现象；同时，因为作业/进程的具体运行时间事先是未知的，只能参考用户提供预估数据。
高响应比优先（HRRN）
- 综合考虑作业/进程的等待时间与要求服务的时间，每次调度时计算各作业/进程的响应比，选择响应比最高的作业/进程提供服务。相应比至少为1，计算公式为：(等待时间 + 要求服务时间) / 要求服务时间。
- 非抢占式算法
- 综合了二者的优缺点。

以上算法不关心响应时间，也不考虑任务紧急程度，不适合作为交互式系统的调度算法。FCFS常常结合其他算法应用，在今天仍然是很重要的算法。

常见的分时操作系统调度算法：

时间片轮转（RR）
- 公平、轮流地为各个进程服务，一般只用于进程调度
- 抢占式算法，调度发生在时钟中断时
- 优点：公平，响应快、及时；不会导致饥饿。
- 缺点：没有区分任务的紧急程度。
RR需要合理选取时间片大小。如果时间片足够大、进程都能在一个时间片内完成执行，则RR退化为FCFS，同时增加进程响应时间；时间片也不能太小，因为进程的切换也需要花费时间。一般而言，让切换进程的时间开销占总时间开销不超过1%是比较合理的设计。
优先级调度
- 根据优先级最高的作业/进行调度，除了作业调度与进程调度外，还可以用于I/O调度
- 抢占式算法或非抢占式算法
- 优点：考虑了优先级，灵活调整进程被服务的机会。
- 缺点：存在饥饿现象。
多级反馈队列
- 对其他调度算法的折中权衡，详情见下图。
- 常见抢占式的实现
- 综合了若干调度算法的优点，但可能导致饥饿。

忙等待互斥与锁

一段时间内只允许一个进程使用的资源被称为临界资源（Critical Resources），许多硬件设备如打印机都属于临界资源。对于临界资源的访问必须互斥（Mutual Exclusion）地进行。

访问临界资源的代码，逻辑上可以分为进入区、临界区、退出区与剩余区四个部分。在进入区上锁，在退出区让出锁。

为保证系统整体的性能，对临界资源的互斥访问，应遵循：

空闲让进：临界区空闲时，应允许一个进程申请进入临界区的请求
忙则等待：如果临界区正在被一个进程访问，则其他试图访问临界区的进程必须等待
有限等待：应保证在等待的进程能在有限的时间内访问临界区，避免饥饿现象
让权等待：如果进程不能访问临界区，应立即释放处理机，避免进程忙等待

常见的进程互斥软件实现方法：

单标志法

使用一个变量turn标识临界区访问权，每个进程访问临界区的权限只能被另一个进程赋予，进程在访问完临界区后需要把临界区权限交由另一个进程。
问题：不满足“空闲让进”，进程必须轮流访问临界区。也就是说，如果进程A访问完临界区后将权限交由进程B、但进程B并未访问临界区，则进程A需要再次访问临界区时必须等待进程B访问后再移交权限。

/* 初始状态 */
int turn = 0;

/* 进程A */
while(turn != 0) {
    critical section;
    turn = 1;
    remainder section;
}

/* 进程B */
while(turn != 1) {
    critical section;
    turn = 0;
    remainder section;
}

双标志先检查
- 使用一个布尔型数组flag标识各进程访问临界区的意愿，每个进程在试图访问临界区前先检查是否存在其他进程也希望访问临界区，如果没有则将自身对应的flag标志设为true再访问临界区。
- 问题：多进程并发运行时，先检查再上锁可能不满足“忙则等待”，因为检查与上锁不是一个原子操作，进而导致多个进程同时访问临界区。如果能利用硬件解决这一问题，则该实现方法是完全可行的。
1
2
3
4
5
6
7
8
9
10
11
12
/* 初始状态 */
bool flag[2];
flag[0] = false;
flag[1] = false;

/* 进程A */
while(flag[1]) {
flag[0] = true;
critical section;
flag[0] = false;
remainder section;
}
双标志后检查
- 使用一个布尔型数组flag标识各进程访问临界区的意愿，先将自身对应的flag标志设为true，再检查是否存在其他进程也希望访问临界区。
- 问题：有可能不满足“空闲让进”与“有限等待”。当同时存在两个进程上锁时，容易造成活锁或死锁。
1
2
3
4
5
6
7
8
9
10
11
12
/* 初始状态 */
bool flag[2];
flag[0] = false;
flag[1] = false;

/* 进程A */
flag[0] = true;
while(flag[1]) {
critical section;
flag[0] = false;
remainder section;
}

Peterson算法

结合了单标志法与双标志法的思想。Peterson算法使用一个布尔型数组flag标识各进程访问临界区的意愿，同时使用变量turn标识优先让其他有意愿访问临界区的进程进行访问。当一个进程尝试访问临界区时，首先将自身对应的flag标志设为true，然后对turn变量赋值以表示优先让其他进程访问临界区（若两个进程同时声明意愿，turn的最终值取决于最后一次写入，由此保证“忙则等待”）。此时检查是否不存在来自其他进程的访问意愿并且turn变量未被覆盖，如果是，则该进程访问临界区；否则等待正在访问临界区的进程或覆盖turn变量的进程结束访问，该进程再访问临界区。
问题：不满足“让权等待”，造成进程忙等待，浪费处理机的计算资源。相比另外三种软件实现方法，Peterson算法保证了安全性（“空闲让进”、“忙则等待”、“有限等待”），但存在忙等待导致处理器的性能浪费，不适合大规模或高负载场景。

/* 初始状态 */
int turn = 0;
bool flag[2];
flag[0] = false;
flag[1] = false;

/* 进程A */
flag[0] = true;
turn = 1;
while(flag[1] && turn==1) {
    critical section;
    flag[0] = false;
    remainder section;
}

常见的进程互斥硬件实现方法：

中断屏蔽
- 在进程开始访问临界区前使用特权指令修改处理器的中断使能位，让处理器暂时不处理可屏蔽中断与进程切换，直到进程结束访问临界区以后再执行指令，让处理器恢复中断使能位，类似原语。
- 优点：实现简单且高效，耗时极短，适用于对实时性要求高的短临界区操作。
- 缺点：由于涉及特权指令，只适用于操作系统的内核进程；不适合多处理机情景，因为特权指令只在一个处理机上执行，不能保证其他处理机上正在运行的进程不会在同一时间访问临界区。同时，长时间的中断屏蔽可能引发设备数据丢失或死锁。
TSL指令（TestAndSetLock或TestAndSet）
- 该指令是一个原子指令，通过锁住内存总线或缓存行以保证原子性，能够将内存字读取到寄存器并设置内存地址为非零值（读旧值+写新值）。通过TSL指令，能够保证双标志法中的检查与上锁成为一个原子操作：要么同时成功，要么同时失败。
- 优点：实现简单，而且适用于多处理机环境
- 缺点：不满足“让权等待”，造成进程忙等待（不断执行TSL指令），浪费处理机的计算资源。
1
2
3
4
5
6
7
/* TSL指令逻辑 */
bool TSL(bool* lock) {
bool old;
old = *lock;
*lock = true;
return old;
}
Swap指令，也被称为Exchange指令
- 该指令是一个原子交换指令，在x86 CPU上称为XCHG，能够直接交换两个操作数的值，例如交换寄存器与内存中的数据，或是两个寄存器之间的值（直接交换值）。与TSL指令类似地，能够保证双标志法中的检查与上锁成为一个原子操作。
- 优缺点与TSL指令的实现相同。

引用自tsl和cas：

TSL是Test and Set Lock的缩写，是CPU提供的一个原子指令，其工作如下所述：它将一个存储器字读到一个寄存器中，然后在该内存地址上存一个非零值。读数和写数操作保证是不可分割的——即该指令结束之前其他处理机均不允许访问该存储器字。执行TSL指令的CPU将锁住内存总线（实际是锁缓存）以禁止其他CPU在本指令结束之前访问内存。操作系统的Mutex的加锁过程就是基于TSL指令实现的。

CAS是Compare and Swap的缩写，是CPU提供的另一个原子指令，它需要三个参数：内存地址，旧值、新值。指令首先比较内存地址中保存的值与旧值，若相同，则把新值写入内存地址；若不同，则指令执行失败。指令的执行过程是原子的，不可被中断的。

TSL和CAS的区别：

TSL实际上只操作一个比特位，而CAS操作的是由32个比特构成的字，因而相比CAS，TSL指令需要更少的寄存器且执行速度更快；

基于TSL指令（加锁）和CAS指令（解锁）实现的Mutex在上锁和解锁时进程要从用户态切换到内核态，并可能伴随有线程的调度、上下文切换等，开销比较重，而进程调用CAS指令则无须从用户态切换到内核态。

解决临界区实现问题的最简单办法就是使用互斥锁（Mutex Lock）：进程在开始访问临界区时调用acquire()获得锁（如果锁可用的话），结束访问时调用release()释放锁。每个互斥锁都有一个布尔变量available，表示该锁是否可被获得、可用。当一个互斥锁被一个进程获得但尚未释放时，另一个进程尝试获得锁将被阻塞，直到锁被原先进程释放，另一个进程获得锁。获得锁与释放锁操作必须是原子的，因此通常采取硬件机制实现。

通过忙等待实现互斥的锁被称为自旋锁（Spin Lock），即如果存在进程正在访问临界区，其他尝试访问临界区的进程需要不断地循环调用acquire()直到获得锁。单标志法与基于TSL指令、swap指令的双标志法均属于自旋锁。

自旋锁的特点：

不满足“让权等待”。
尽管如此，由于等待期间不需要切换进程上下文，因此如果上锁时间短，则在多核CPU系统中自旋的代价并不大。
常用于多核CPU系统，因为当一个进程在一个核的时间片上忙等待时，若其他核上访问临界区的进程释放了锁，则该进程能立刻获得锁。
不适合单核CPU系统，因为一个线程在忙等待的过程中，另一个线程不可能释放锁，那么这次忙等待的时间片就被浪费掉了。

信号量机制

前文中提到的所有进程互斥解决方案，均不能实现“让权等待”。1965年，Dijkstra提出了信号量机制，有效解决了这一问题。

在计算机科学中，信号量（Semaphore） 是一种变量或抽象数据类型，用于通过多线程控制对公共资源的访问，并避免多任务操作系统等并发系统中的临界区问题。信号量属于同步原语（synchronization primitive）的一种。

一个简单的信号量可以是一个普通变量，其值根据程序员定义的条件（例如递增、递减或切换）进行修改。

利用由操作系统提供的原语操作信号量，可以方便地实现进程的互斥与同步。

用C语言描述使用信号量实现“让权等待”进程互斥的逻辑：

/* 一种信号量定义，假设为可用打印机数 */
typedef struct {
    int value;          // 剩余可用打印机数量
    Struct process* L;  // 等待进程队列
} semaphore;

/* P操作：进程需要使用资源时，通过 wait 原语申请 */
void wait(semaphore printer) {
    printer.value--;
    if(printer.value < 0) {
        block(printer.L);  // 如果没有可用打印机，调用 block 原语主动阻塞
    }
}

/* V操作：资源使用完毕，通过 signal 原语释放 */
void signal(semaphore printer) {
    printer.value++;
    if(printer.value <= 0) {
        wakeup(printer.L);  // 如果等待队列中存在等待资源的进程，则唤醒等待队列中的一个进程
    }
}

用C语言描述使用信号量实现进程同步与前驱的逻辑（所谓“前V后P”）：

void process1() {
    Code c1;
    V(S);  // 进程 process1 释放资源，如果进程 process2 阻塞，则唤醒
    Code c2;
}

void process2() {
    P(S);  // 必须在进程 process1 释放资源、修改信号量后，进程 process2 才能继续执行，否则主动阻塞
    Code c3;
}

生产者-消费者问题

生产者-消费者问题（Producer–Consumer Problem）是多进程/线程同步与互斥的经典模型。

生产者-消费者问题的场景描述：生产者和消费者共享一个固定大小为n的缓冲区。生产者负责生成数据并放入缓冲区，消费者从中取出数据并使用。需满足以下条件：

缓冲区满时，生产者必须等待（同步 1：无法继续生产）
缓冲区空时，消费者必须等待（同步 2：无法继续消费）
缓冲区是临界资源，同一时刻只能有一个生产者或消费者访问（互斥）

解决生产者-消费者问题的经典办法是利用信号量机制，可以使用三个整型信号量empty、full与mutex分别表示缓冲区剩余容量、缓冲区内非空数据量与互斥访问标记。其中，empty与full是同步信号量，mutex是互斥信号量。初始情况下，empty = n，full = 0，mutex = 1。

通过分析，不难用C语言描述通过信号量实现生产者-消费者模型的逻辑：

/**
 * @brief 相应的V操作将唤醒相应的P操作
 * @note 阻塞发生在P操作，V操作唤醒被相应P操作阻塞线程
 */

/* 生产者 */
void producer() {
    while(true) {
        produce();  // 在临界区外生产一个产品
        P(empty);   // P：生产者申请使用一个空闲缓冲区（确保“无法继续生产”条件）
        P(mutex);   // P：生产者申请互斥访问缓冲区（确保“互斥”条件）
        put();      // 将产品投入缓冲区
        V(mutex);   // V：访问结束，唤醒等待互斥访问的线程
        V(full);    // V：缓冲区内数据量增加，唤醒消费者继续消费
    }
}

/* 消费者 */
void consumer() {
    while(true) {
        P(full);    // P：消费者申请使用一个载有数据的缓冲区（确保“无法继续消费”条件）
        P(mutex);   // P：消费者申请互斥访问缓冲区（确保“互斥”条件）
        take();     // 取走一个产品
        V(mutex);   // V：访问结束，唤醒等待互斥访问的线程
        V(empty);   // V：缓冲区剩余容量增加，唤醒生产者继续生产
        consume();  // 在临界区外消费一个产品
    }
}

该模型中同步与互斥的关系特点：

互斥由同一进程中的一对PV操作实现，即互斥的PV操作需在同一线程/进程的临界区代码块内完成，确保任意时刻至多只有一个线程访问缓冲区。
同步由不同进程中的P操作与V操作实现，对于信号量empty与full，在一个进程中执行P操作，在另一个进程中执行相应的V操作。
不可更换相邻P操作的次序，否则造成死锁。实现互斥的P操作必须在实现同步的P操作后。
可以更换相邻V操作的次序，因为V操作不会导致进程阻塞。
产品生产produce()与产品消费consume()可以置于PV操作之间，但会增加临界区代码长度，降低代码性能。
通过信号量的阻塞机制，实现了“让权等待”。

从代数的角度分析：

同步信号量是互斥信号量的前驱条件，“先同步后互斥”构成一组偏序关系。
强行调换P操作次序后，资源请求路径形成有向环图，触发循环等待的代数结构。
V操作构成交换群，交换次序不改变结果。

读者-写者问题

读者-写者问题（Readers–Writers Problem）是另一个多进程/线程同步与互斥的经典模型，相比生产者-消费者问题，读者-写者问题更关注互斥的实现。

读者-写者问题的场景描述：现有读者进程与写者进程这两组进程需要共享一个数据区，其中读者进程仅读取数据、不会修改共享资源，写者进程需修改数据、必须独占访问共享资源。需满足以下基本要求：

多读不互斥：允许多个读者同时访问数据。
写写互斥：同一时间仅允许一个写者操作。
读写互斥：任何一个写者工作时禁止任何读者或其他写者访问。
无饥饿与公平性：应尽量避免某一类进程长时间无法访问资源。

如果要用信号量机制解决读者-写者问题，可以使用信号量计数器count判断当前进程是否为第一个读者或最后一个读者，进而根据采取的策略做出不同的行为，同时使用其他优先级信号量与队列信号量实现互斥访问。可选解决方案：

读者优先策略：第一个读者获取写锁（阻止写者），最后一个读者释放写锁。

int readcount = 0;          // 当前读者数
semaphore rmutex = 1;       // 保护 readcount 的互斥锁
semaphore wmutex = 1;       // 写操作的互斥锁

void reader() {
    P(rmutex);              // 申请修改 readcount
    if (readcount == 0) P(wmutex);  // 第一个读者阻塞写者
    readcount++;
    V(rmutex);
    // 执行读操作
    P(rmutex);
    readcount--;
    if (readcount == 0) V(wmutex);  // 最后一个读者释放写者
    V(rmutex);
}

void writer() {
    P(wmutex);              // 写者独占资源
    // 执行写操作
    V(wmutex);
}

可能导致写者饥饿。

写者优先策略：写者到达时通过优先级信号量阻止新读者，确保写者尽快执行。

int writecount = 0;         // 当前写者数
semaphore prior = 1;        // 优先级控制信号量
semaphore wmutex = 1;       // 写操作互斥锁

void writer() {
    P(prior);               // 申请优先级
    P(wmutex);              // 写者独占资源
    // 执行写操作
    V(wmutex);
    V(prior);               // 释放优先级
}

void reader() {
    P(prior);               // 新读者需等待写者完成
    // 执行读操作（需额外信号量保护 readcount）
    V(prior);
}

可能导致读者饥饿。

公平读写策略

semaphore S = 1;            // 公平队列信号量
semaphore rmutex = 1;       // 保护 readcount
int readcount = 0;

void reader() {
    P(S);                   // 进入公平队列
    P(rmutex);
    if (readcount == 0) P(wmutex);
    readcount++;
    V(rmutex);
    V(S);                   // 允许后续进程加入队列
    // 执行读操作
    P(rmutex);
    readcount--;
    if (readcount == 0) V(wmutex);
    V(rmutex);
}

void writer() {
    P(S);                   // 进入公平队列
    P(wmutex);
    // 执行写操作
    V(wmutex);
    V(S);
}

解决了饥饿问题，但加剧锁的竞争。

哲学家进餐问题

哲学家进餐问题（Dining Philosophers Problem）最初由Dijkstra提出，同样是一个经典的多进程/线程同步与互斥模型。

哲学家进餐问题的描述：五位哲学家围坐在同一圆桌旁共进晚餐。每位哲学家面前均设有独立餐盘，相邻餐盘之间放置一把共用餐叉。桌上供应的菜品为意大利面，其食用需同时使用左右两侧的餐叉。每位哲学家的行为模式被严格限定为交替执行思考与进餐两种状态。根据规则约束，哲学家仅当同时持有左侧和右侧两把餐叉时方可进行进食。此条件隐含：只有当该哲学家左右两侧相邻个体均处于思考状态（而非进餐状态）时，两把餐叉才同时处于可用状态。当某位哲学家完成进食后，必须立即释放所持有的两把餐叉。

问题的核心挑战在于设计一种并发调度机制，确保所有哲学家均不会陷入饥饿状态——即每个个体均可无限次地交替执行进食与思考行为。此设计需满足“不完全信息”约束条件：假设所有哲学家均无法预知其他个体何时产生进餐或思考的意图。

该问题的特点是每个哲学家进程需要持有两份不同的餐叉临界资源才能进餐，否则阻塞，同时需要避免死锁。当每位哲学家都持有一份餐叉并且都希望从同一侧哲学家处再获得一份餐叉时，将形成死锁。

可以通过多种方案解决哲学家进餐问题中的死锁现象，例如：

限制并发数量：设置信号量限制最多允许4位哲学家同时拿筷子。
制定资源获取规则：按哲学家编号的奇偶，规定偶数哲学家先从左侧获取餐叉，奇数哲学家先从右侧获取餐叉。
AND型信号量：要求哲学家同时申请两根筷子，若无法同时获得则阻塞。

管程

先前使用信号量机制解决了生产者-消费者模型中的同步与互斥问题，该问题实际上还可以利用管程解决。

管程（Monitor）是由以下四部分组成的资源管理模块：

名称：标识管程的唯一性（如ProducerConsumer）。
共享数据结构：定义需保护的共享资源（如缓冲区、计数器）。
操作过程：封装对共享资源的一组操作函数（如insert()、remove()）。
初始化代码：对共享数据设置初始值（如缓冲区大小）。

管程通过编程语言的编译器保证每次仅允许一个进程进入执行内部过程，自动实现互斥访问。

管程的核心特征：

互斥性：管程通过入口队列自动实现互斥：任何进程必须通过调用管程的入口函数进入，且同一时刻仅允许一个进程执行内部过程。例如生产者调用insert()时，消费者无法同时调用remove()。
条件变量：条件变量用于排队等待，解决进程间的同步问题，其操作包括
- x.wait()：进程因条件x不满足被阻塞，释放管程锁并进入条件队列等待。
- x.signal()：唤醒条件x队列中的一个进程，使其重新竞争管程锁。
模块化与信息隐藏
- 模块化：管程是独立编译的基本程序单位，便于代码复用和维护。
- 信息隐藏：共享数据仅能被管程内部的过程访问，外部进程无法直接操作，避免数据不一致。

特性	管程	信号量
实现方式	封装共享数据与操作，自动管理互斥	需手动使用P/V操作控制临界区
同步机制	条件变量（`wait`/`signal`）	整型变量（`semaphore`）
编程复杂度	低（由编译器保证互斥）	高（需程序员处理锁与同步逻辑）
死锁风险	较低（条件变量避免部分资源占用）	较高（PV操作顺序错误易导致死锁）
适用场景	复杂同步问题（如读写锁、线程池）	简单互斥或资源计数场景

例如，Java中的synchronized关键字就是通过管程机制实现的，其具体实现涉及到Java编译器与JVM的设计。

死锁

死锁（Deadlock）指在并发系统中，多个进程因争夺共享资源而陷入相互等待的状态，导致所有相关进程均无法推进。

死锁的发生必须满足以下四个条件：

互斥条件（Mutual Exclusion）：资源需互斥使用，即同一时间仅允许一个进程独占（如打印机使用权、临界区代码）。
占有且等待（Hold and Wait）：进程已持有至少一个资源，同时请求其他资源且不释放已占资源。
不可剥夺（No Preemption）：进程已获得的资源在未使用完毕前，不能被系统或其他进程强行剥夺（如内存资源）。
循环等待（Circular Wait）：存在进程集合，其中等待占有的资源，等待占有的资源……等待占有的资源，形成循环依赖链。

死锁的解决方案可以分为三类：预防、避免与检测死锁并恢复。

死锁预防（Prevention）

要达到预防死锁的目的，就需要从死锁的四个条件入手并破坏条件，阻止死锁的产生。
- 破坏互斥条件
  
  将独占资源改造为共享资源（如SPOOLing技术虚拟化打印机）。
  
  局限性：仅适用于可共享设备（如磁盘），无法应用于必须互斥的资源（如临界区）。
- 破坏占有且等待
  - 静态分配：进程启动前申请全部所需资源。
  - 资源释放策略：若请求新资源失败，释放所有已持有资源并重新申请。
  缺点：资源利用率低，易引发饥饿。
- 破坏不可剥夺
  
  允许系统强制回收资源（如CPU调度中的抢占机制）。
  
  局限性：适用于内存、处理器等易恢复状态的资源，对不易恢复状态的资源应用该策略并不合适。
- 破坏循环等待
  
  资源有序分配法：为每类资源编号，进程必须按顺序申请资源，打破环形依赖。这样，在任何一个时刻，总存在一个编号最大的进程能够获取到所有的资源。
  
  缺点：设计和编程繁琐，而且不方便增加新的资源，新增资源时需要重新编号。此外，由于要求进程必须按顺序申请资源，因此存在系统资源浪费。
死锁避免（Avoidance）

通过动态评估资源分配的安全性，确保系统不进入不安全状态。实现死锁避免最经典的算法是Dijkstra提出的银行家算法。

模拟资源分配后是否存在安全序列（即所有进程可依次完成），若存在则分配资源，否则拒绝请求。银行家算法的核心步骤：

Ⅰ. 进程声明最大资源需求；

Ⅱ. 分配前检查剩余资源是否满足后续进程需求；

Ⅲ. 仅当存在安全序列时执行分配。
死锁检测与恢复（Detection and Recovery）

利用死锁定理检测系统是否存在死锁：当且仅当系统状态的进程-资源分配图不可完全简化时，系统处于死锁状态。换言之，若通过一系列化简操作无法将所有进程变为孤立节点，则存在死锁。

系统在检测到死锁后，可以想办法恢复、处理死锁。在通用操作系统中，例如Linux、Windows，由于死锁概率低、用户级死锁影响有限，并且处理死锁的成本很高，这些系统对于用户级死锁往往会采取鸵鸟策略——就算发现了死锁，也不会主动处理死锁。但对于一些实时系统，由于死锁后果严重，死锁一旦发现则必须处理。对于数据库系统，由于有维护回滚日志，因此可以方便地回滚事务以解决死锁，恢复死锁的代价相对较低，通常会选择自动处理死锁。

内存与内存管理技术

内存的概念及覆盖与交换

内存覆盖技术具有明显的缺点：必须在程序设计时被显式声明再在运行时由操作系统完成覆盖，增加程序设计的负担，现在以及很少见了。

内存交换技术在今天仍然常见。

覆盖技术、交换技术与虚拟存储技术均属内存空间扩充的方案。虚拟存储技术是三者中最先进的技术。

连续分配管理方式

连续分配（Contiguous Memory Allocation）是指为用户进程所分配的必须是连续的内存空间。

单一连续分配

该方案只支持单道程序。不存在外部碎片，存在内部碎片。
固定分区分配

该方案支持多道程序。不存在外部碎片，存在内部碎片。
动态分区分配

该方案支持多道程序。不存在内部碎片，存在外部碎片，但外部碎片可以通过“紧凑”技术解决。所谓“紧凑”技术，是一种通过重新排列内存中的进程物理地址空间来合并外部碎片的方法，其核心目标是将分散的空闲内存区域整合为连续的大块，从而满足大内存请求需求。

常用的经典动态分区分配算法有首次适应算法、最佳适应算法、最坏适应算法与邻近适应算法。

分页存储管理与多级页表

分页存储（Paging Storage）是一种非连续内存管理技术，该技术将进程的逻辑地址空间和物理内存划分为固定大小的块（称为页和页框），并通过页表实现逻辑地址到物理地址的映射。分页存储是实现虚拟内存的基础，让程序“以为”自己运行在一块连续的内存上，从而实现动态运行时装入这一现代操作系统技术。

逻辑页（Page）：进程的逻辑地址空间被划分为等大小的页（如4KB），页号从0开始编号。
物理页框（Frame）：物理内存被划分为与逻辑页等大小的块，块号从0开始编号。

核心数据结构：

页表（Page Table）：记录进程逻辑页与物理页框的映射关系，每个进程独立维护一张页表。页表通常被存储在PCB中。
页表项（PTE）：包含物理块号、保护位（权限控制）信息。对于请求分页存储管理方式，其页表项还包含有效位（标识页是否在内存）、修改位（标识页是否被修改）等信息。值得注意的是，PTE存储物理块号但不显式存储页号，因为页号蕴含在了索引中。
位示图/空闲链表：管理物理内存的分配状态，标记哪些页框空闲或已占用。

地址转换关键机制：逻辑地址由页号（P）和页内偏移（W）组成。当已知逻辑地址与页面大小时，按照最直观的思考逻辑，应该按如下公式计算页号P与页内偏移W，进而计算物理地址：

P = 逻辑地址 / 页面大小
W = 逻辑地址 % 页面大小
物理地址 = 在页表中查询P对应的页面在内存中的起始地址（即物理块号） + W

但由于二进制除法与取模运算的特性，当页面大小恰为2的整数幂个内存单元时，计算机并不需要按上述逻辑逐步计算P与W，而是可以直接利用硬件从逻辑地址中通过无符号左移/右移的位运算分别截取出P与W。完整的地址转换过程依赖于地址变换机构的具体实现，但关键机制如上所述。

例如当页面大小为4KB时，在32位逻辑地址中高20位为P、低12位为W；在64位逻辑地址中高40位为P、低24位为W。实际上，如果页面大小为B，则低位为W、剩余数字为P。

推论：

如果W有位，则该系统中页面大小为内存单元。
如果P有位，则该系统中一个进程最多拥有个页面。这是为什么32位操作系统不能直接允许超过4GB内存占用程序的原因。

上文中提到的页表均为单级页表，并未进一步拆分虚拟地址。多级页表是一种分层的页表结构，用于解决单级页表占用过大连续内存空间的问题。它将页表分解为多个层级的子表（如页目录表、二级页表等），通过动态加载所需部分，减少内存占用。实质上多级页表是“以时间换空间”的技术，如果未命中快表缓存，n级页表需要进行n+1次查询。尽管如此，结合快表与大页技术，综合来看使用多级页面技术是利大于弊的。

单级页表的缺陷

在32位系统中，单级页表需要存储数百万个页表项（如4GB虚拟地址空间 + 4KB页大小 → 1M项），占用4MB连续内存。
进程切换时需加载完整页表，导致内存浪费（尤其当进程仅使用部分虚拟地址时）。

多级页表的优化

仅需加载当前使用的页表部分，未使用的子表无需分配内存（如页目录表中未引用的二级页表）。
支持按需动态分配页表，避免一次性占用大块连续内存。

多级页表的思想是对页表进行进行分组。例如页面大小为4KB、每个页表项大小大小为4B时，每个页面能够存放1024个页表项，那么这1024个连续的页表项被归为一组，每组恰占用一个物理页框。接着，为每组页表再建立一张表，这张表被成为页表目录，或外层页表、顶层页表。与之相应地，需要拆分虚拟地址以同时记录多级页号。以32位系统上的二级页表为例，虚拟地址可以被分为三部分：高10位为页表目录，中间10位为二级页表，低12位为页内偏移。此时，地址转换流程为：

通过CR3寄存器获取页表目录基址（假设为x86架构CPU），通过虚拟地址中的高10位在页表目录中索引页目录项（PDE），得到二级页表的物理地址。
用虚拟地址的中间10位索引二级页表项（PTE），得到物理页框号。
物理地址 = (物理页框号 << 12) | 页内偏移

这样就解决了单级页表必须连续存放、页表很大时必须占用多个连续页框的问题，因为二级页表不必连续存放，可以通过一级页表进行离散地索引。

对于第二个问题：如何实现页表动态加载，这依赖于虚拟存储技术，在后文中将会重点解释。简单来讲，可以在页表项中增加一个标志位，标识该页面是否已“真的”调入内存。如果试图访问的页表并不在内存中，则产生缺页中断，操作系统内核需要介入将目标页面从外存调入内存。

分页存储的地址变换机构

地址变换机构（Address Translation Mechanism）是现代计算机系统中实现虚拟内存的核心机制，负责将程序使用的虚拟地址转换为物理内存中的物理地址。根据是否利用了快表，可以将地址变换机构简单分为基本地址变换机构与基于快表的地址变换机构两类。

基本地址变换机构

基本地址变换机构需借助PTR（页表寄存器）。当进程存在但未处于运行态时，页表的物理基址（物理起始地址）与长度被存储在内核空间内的PCB中；当进程被调度至运行态时，操作系统将把页表的物理基址与长度存储在PTR中，以便根据页表的物理基址与长度进行越界检查等操作。
基于快表的地址变换机构

利用快表，可以改进基本地址变换机构，使其性能得到显著的提升。我们知道，寄存器的周期与CPU时钟是同步的，但造价十分昂贵；尽管内存的访问速度相较于磁盘已经很快了，但远不能满足CPU强大的计算能力。为了平衡这一矛盾，我们需要快表以加速内存的地址变换。

快表（TLB，Translation Lookaside Buffer）是一种高速缓存，与CPU缓存同属SRAM，速度较之DRAM有数量级上的差距。作为一种硬件，TLB被集成在MMU（Memory Management Unit，内存控制单元）中。如今的CPU常常将MMU集成在内部，但应注意TLB与CPU缓存的区别，这是两种完全不同的硬件。

TLB通过缓存最近访问的页表项副本，利用局部性原理加速地址变换的速度。相应地，内存中的页表也被称为慢表。

这里解释一下何为局部性原理。局部性原理（Principle of Locality）描述了程序在运行过程中对数据和指令访问的集中性规律，主要分为时间局部性原理和空间局部性原理两类。
- 时间局部性：程序在短时间内倾向于重复访问相同的数据或指令。
  
  造成时间局部性的原因是程序中包含大量的循环结构与函数调用。如果程序执行了一个代码块，那么在未来程序更可能再次运行该代码块；如果一个函数被程序调用，那么在未来该函数将更可能被再次调用。
- 空间局部性：程序倾向于访问邻近的数据或指令。
  
  造成空间局部性的原因是程序中包含大量的数组顺序访问与文件顺序读取。如果程序访问了数组中的一个数据，那么在未来程序更可能访问数组中与该数据相邻的数据；如何一个文件被程序读取，那么在未来与该文件相邻的文件更可能被读取。
尽管TLB容量往往很小，但由于局部性原理的存在，其缓存命中率极高，通常能够达到95%以上，极大加速了地址变换的速度。如果缓存未命中，则处理机需要查询内存中的慢表。相比之下，基本地址变换机构中处理机只能访问内存中的慢表进行地址变换，效率很低。

最后，简要对比两种地址变换机构：

分段存储管理方式

分段存储管理方式借助寄存器SR。SR的作用类似于分页存储管理方式中的PTR。

段页式存储管理方式

分页存储管理方式与分段存储管理方式不是相互对立的，而是可以结合使用、综合两者之长的。

虚拟内存与页面置换算法

虚拟内存（Virtual Memory）的实现建立在离散内存管理技术的基础之上。要实现虚拟内存，应该为离散内存管理技术扩展请求调用与页面置换的功能。

请求分页存储管理方式

一般的分页存储管理方式中的（单级）页表是一个线性表，主要存储物理块号与保护位两个字段。

在请求分页存储管理中，为了实现请求调用，请求分页存储管理的页表除了物理块号这一字段外，还需要存储状态位、访问字段、修改位与外存地址这几个字段。其中，状态位用以标记该页面是否已调入物理内存，访问字段记录页面一段时间内的访问次数或上次访问时间以供页面置换算法参考，修改位标记该页面自从被调入物理内存后是否存在变动，外存地址指向页面在外存中的地址。这里需要解释一下设计修改位的动机：当页面被置换算法选中而调出内存时，如果该页面在外存中存在原始副本且页面在被调入内存期间相较原始副本并未发生修改，则没有必要将页面再次写入外存。这一设计与HTTP请求中的304状态码Not Modified是如出一辙的。

缺页中断机构

请求调用通过中断实现。

在请求分页存储管理方式中，如果要访问的页面在物理内存中不存在便会触发缺页中断，随后由操作系统内核中的缺页中断处理程序处理该中断。这个过程中缺页的进程被阻塞，进入阻塞进程队列，直到调页完成后再被唤醒，回到就绪进程队列。

在调页时，如果内存中存在空闲的物理块，则内核会为进程分配一个空闲的物理块并将所缺页面调入该块，同时修改页表中相应的页表项；如果内存中不存在空闲的物理块，则需要由页面置换算法选择一个页面调出内存，为缺页进程腾出内存空间。

缺页中断属于故障（fault），是内核能够尝试修复的异常。同时，缺页中断是在程序运行期间产生的，因此缺页中断还是一种内中断。一条指令在执行期间有可能产生多次缺页中断，例如将页面A的数据复制至页面B，页面A与页面B有可能都不在物理内存当中，有可能发生两次缺页中断。

页面置换算法

最佳置换算法（OPT）

该算法在每次选择淘汰的页面时，将选择以后永不访问或最长时间内不被访问的页面。

最佳置换算法是最优秀的页面置换算法，具有最低的缺页率。然而在实际的实践中，我们无从得知哪些页面在未来永不访问或在最长时间内不被访问（毕竟我们还不能预测未来），因此该算法是理论上最优但不能或很难实现的算法，一般只用作评估其他页面置换算法好坏的标尺。
先进先出置换算法（FIFO）

该算法在每次选择淘汰的页面时，将选择最早被调入内存的页面。

该算法实现简单但性能很差，导致较高的缺页率，而且存在Belady异常：为进程分配的物理块增多时，缺页次数不降反增。
最近最久未使用置换算法（LRU）

该算法在每次选择淘汰的页面时，将选择最近的最久未使用页面。

该算法性能很好，十分接近最佳置换算法，但实现复杂较高（特别是在没有硬件支持的情况下），并且存在额外的空间开销与潜在的性能开销。
时钟置换算法、最近未使用算法（CLOCK、NRU）

页面分配策略

根据分配固定还是可变、置换是局部的还是全局的，可以得到三种页面分配策略。

内存映射文件

文件

文件的概念

文件是在计算机存储设备上记录数据的资源。

文件的属性有文件名、标识符、类型、位置、大小、创建时间等等。其中，操作系统一般允许不同目录下的相同文件名文件的存在，但在操作系统的内部，每个文件都具有一个唯一的标识符。对用户而言标识符没有实际意义，只是操作系统区分各文件的内部名称。

按照文件的组织方式，可以分为流式文件与记录式文件。流式文件是无结构的，由一些二进制数据或字符流组成；记录式文件是有结构的，由一些相似的记录组成，例如数据库的表。这里的记录是指一组相关数据项的集合。每条记录一般有一个数据项作为标识不同记录的关键字。

操作系统作为最接近硬件层面的软件，应当提供文件操作相关的系统调用。常见文件相关的基本系统调用有：

create系统调用：创建文件
delete系统调用：删除文件
read系统调用：读文件
write系统调用：写文件
open系统调用：打开文件，在读写文件前应当先打开文件
close系统调用：关闭文件，文件读写结束后应当关闭文件

在使用编程语言对文件进行操作时，open与close就会向操作系统发出相应的系统调用请求。

文件被存储在外存中。和内存管理方式一样，操作系统与磁盘（包括机械硬盘、固态硬盘）也将外存划分为一个个物理块。每个块大小相等，一个块通常包含2的整数幂个地址。文件的逻辑地址也可以被划分为逻辑块号与块内地址，操作系统需要将逻辑地址转换为外存的物理地址。在读写文件时，操作系统与磁盘会以块为单位操作数据——即使最后程序只使用了其中一个比特的数据，操作系统也会取出外存中的一整个块。

和内存管理一样地，文件与外存也涉及逻辑地址与物理地址。举一个简单的例子，在任何高级编程语言中我们都可以打开一个无结构的文本文件（通常为标准库提供的fopen或open），然后使用下标读取指定位置的数据——在C语言中通过fseek(filePtr, k, SEEK_SET);定位、fgetc(filePtr)读取，在Java中通过RandomAccessFile对象的.seek(k)方法定位、.readByte()方法读取，在Go中通过file.Seek(k, io.SeekStart);定位、file.Read(make([]byte, 1))读取，在Python中通过f.seek(k)定位、通过f.read(1)读取……总而言之，从用户的角度来看，就算是再大的文件似乎都是连续存储的。然而，文件在外存中可能是连续的（连续分配方式），也可能是离散的（隐式链接分配方式、显式链接分配方式、索引分配方式）。这里的k就是逻辑地址，用户不需要关心文件在物理上到底是如何存储的、每份数据究竟位于哪一个物理地址上。

既然有逻辑地址与物理地址的关系，自然就有逻辑结构与物理结构的关系。逻辑结构是由用户自行设计的逻辑上的结构，而物理结构则是文件在外存中实际的存储方式，逻辑结构与物理结构可以在遵守文件系统设计约束的前提下自由组合（例如FAT32仅支持链分配，不支持索引分配）。

文件的逻辑结构

何为文件的逻辑结构与文件的物理结构？简而言之，文件的逻辑结构是在用户看来文件内部的数据是如何组织的；文件的物理结构则指在操作系统看来文件内部的数据是如何组织的。比如，线性表是一种逻辑结构，可以通过顺序数组或链表等若干物理结构分别实现，对应不同特点的线性表。本小节重点讨论有结构文件。

记录式文件的记录可以是定长的，也可以是可变长的，其中可变长记录是最常见的。

有结构文件的逻辑结构根据记录在逻辑上如何组织，可以分为顺序文件、索引文件与索引顺序文件三类。

顺序文件：文件中的记录在逻辑上一个接一个地顺序排列，记录可以是定长的或变长的。在物理上，记录可以是顺序存储的，也可以是链式存储的。

按照顺序文件的顺序是否与关键字有关，又可以分为：
- 串结构：记录之间的顺序与关键字无关。常见按记录存入的时间决定记录顺序。
- 顺序结构：记录之间的顺序与关键字有关。
如果顺序文件采用链式存储，则无法实现随机存取。

如果顺序文件采用顺式存储且记录是可变长的，则无法实现随机存取。

如果顺序文件采用顺式存储且记录是定长的，则可以实现随机存取。如果是串结构，则无法快速根据关键字定位记录，但增加或删除记录容易实现；如果是顺序结构，则可以快速根据关键字定位记录，但增加或删除成本较高。
索引文件：索引文件利用索引表加速了可变长记录文件的访问速度。索引表本身是一种定长记录的顺序文件，支持随机存取，记录了每个记录的数据长度与指针——文件的每个记录都有相应的索引表项。有了索引表，文件中的记录就可以在物理上离散地存放了，因为可以通过索引表中记录的指针访问文件的全部记录。如果关键字是按顺序排列的，则索引文件还支持按关键字折半查找。

索引表需要随文件记录的增删而进行相应的维护。由于索引文件具有较快的检索速度，因此常被用于对信息处理的及时性要求比较高的场合。

可以对同一个文件建立多个索引表，比如各数据库引擎均支持这一操作。
索引顺序文件：由于索引文件中的每个记录都对应一个索引表项，因此索引文件的索引表会产生较高的空间开销。索引顺序文件结合了顺序文件与索引文件的优点：为文件建立一张索引表，但与索引文件不同的是并非每个记录都对应一个索引表项，而是一组记录对应一个索引表项。

文件目录

在Linux中，操作系统的索引结点就是inode——或者说靠inode实现，因此除非特别指明，否则下文不会刻意区分索引结点与inode这两个术语。为加速对目录的访问，Linux的目录项（Directory Entry）仅包含文件名与inode号的映射，inode则存储了除文件名与文件内容以外的所有元信息。

文件的物理结构

文件的物理结构，即文件分配方式、文件数据存在在外存中的方式，可分为连续分配、链接分配与索引分配三类，其中链接分配又分为隐式链接与显式链接。

连续分配方式

该分配方式要求每个文件在磁盘上占有一组连续的物理块，FCB上应当记录文件的物理基址（起始块号）与长度（占用块数）。这样，当用户给出要访问的逻辑块号时，操作系统能够通过FCB查找到外存上的物理基址，将其与逻辑块号相加后得到物理块号。访问任何磁盘块时，操作系统均仅需进行1次磁盘I/O。

优点：不难推导出，连续分配方式的优点是支持顺序访问和随机访问。同时，对于HDD而言，由于顺序读写连续分配的文件时所访问的磁盘块相邻，因此磁头移动的时间短，无机械寻道延迟；对于SSD而言，主控可通过预读和并行通道一次性处理多个连续数据块（如4KB页或更大单元）以减少内部寻址和闪存颗粒的切换开销，提升较之随机读写几倍的访问速度。

缺点：追加写入文件时可能会由于连续物理块的限制而必须整体迁移文件。同时，磁盘利用率低下，将产生许多难以利用的磁盘碎片，尽管可以通过“紧凑”技术处理碎片，但需要付出相当大的代价。
隐式链接分配方式

该分配方式中，除文件占用的最后一个磁盘块以外，每个被文件占用的磁盘块都保存了指向下一个磁盘块的指针，类似链表，因此FCB上应当记录文件的起始块号与结束块号。要访问第k个磁盘块，操作系统需要进行k+1次磁盘I/O。

优点：追加写入文件方便，并且不会产生磁盘碎片、外存利用率高。

缺点：只支持顺序访问，不支持随机访问，查找效率低下，并且存储指针需要额外的空间开销。
显式链接分配方式

该分配方式将所有磁盘块指向下一个磁盘块的指针按物理块号的顺序显式地存放在被称为FAT（File Allocation Table，文件分配表）的表中（如果一个磁盘块是文件的最后一个磁盘块或没有被任何文件占用，则该磁盘块在FAT中的值应当用特殊值标记）。可以使用一个指针数组作为简易的FAT，数组中的第k位存储第k+1个磁盘块的地址。如果使用这种分配方式，则在FCB中只需要额外记录文件的起始块号。一个磁盘至多应只设置一个FAT，在开机时将FAT读入内存并使其常驻内存。查询FAT的过程不涉及磁盘I/O，因此在显式链接分配方式中，对于任何磁盘块的访问，操作系统均只需进行1次磁盘I/O。

磁盘的FAT32分区格式就利用了FAT技术。不过，在FAT32分区格式中存在两张FAT以达到主备冗余的目的。

优点：追加写入文件方便，不会产生磁盘碎片、外存利用率高，并且支持随机访问，文件访问效率比隐式链接分配方式高。

缺点：FAT需要占用一定的存储空间（以空间换时间）。
索引分配方式

该分配方式中，操作系统会为每个文件单独建立一张索引表，并在表中记录文件的各个逻辑块对应的物理块。存放索引表的磁盘块被称为索引块，存放文件数据的磁盘块被称为数据块。可以看出，索引表的功能类似内存管理中的页表。如果使用这种分配方式，则在FCB中只需要额外记录文件的索引块。

优点：追加写入文件方便，不会产生磁盘碎片、外存利用率高，并且支持随机访问，文件访问效率比隐式链接分配方式高。

缺点：索引表需要占用一定的存储空间（以空间换时间）。

如果一个文件足够大导致一个索引块不能记录下文件的全部逻辑块与物理块的映射关系，则需要考虑如何联合多个索引块。以下是一些解决方案：
- 链接方案：让逻辑块中的最后一个索引项指针指向下一个逻辑块的第一个索引项。
  
  缺点：只能顺序读取逻辑块，效率低下。
- 多层索引方案：该方案的原理类似内存管理中的多级页表，使第级索引块指向第级的若干索引块。假设共有级的索引块，一个磁盘块的大小为，一个磁盘块可以存放个索引项，则级索引块支持的文件大小最多为；当顶级索引表未调入内存时，对于任何磁盘块的访问，操作系统均需要进行次磁盘I/O。
  
  缺点：当文件很小却采用了多层索引方案时，读取文件占用的某个磁盘块仍需要多次磁盘I/O。
- 混合索引方案：该方案在多层索引方案的基础上，允许索引表中同时包含直接地址索引与间接索引。

文件存储空间管理

文件的结构与分配方式关注的是对文件存储的管理，也就是对被文件占用的、非空闲磁盘块的管理，而文件存储空间管理则关注操作系统对空闲磁盘的管理。

文件的共享与保护

操作系统为用户提供文件共享的功能，让多个用户能够共享使用一个文件。

文件共享分为两种方式：

基于索引结点的共享（硬链接，Hard Link）

硬链接方式通过在目录项中让多个文件名对应的索引结点指针指向同一个索引结点实现，最终由该索引结点再指向磁盘上的同一个文件。
基于符号链的共享（符号链接、软链接，Symbolic Link）

符号链接本身是一种特殊类型的文件，功能是充当目标文件或目录的路径别名。符号链接文件本身仅存储目标文件的路径字符串或目录的路径字符串（而非目标数据文件或目标目录文件的内容），当用户访问符号链接时，操作系统会自动解析该路径并重定向到目标文件。

符号链接是一个独立文件，以Linux为例，符号链接文件拥有自己的inode和文件权限。即使删除符号链接，也不会影响目标文件；但若目标文件被移动或删除，符号链接会变为“悬空链接”（Dangling Link），导致访问失败。符号链接自身的权限信息通常不影响对目标文件的访问。

硬链接通过目录项直接引用了同一inode、使多个索引结点指针指向同一索引结点，因此必须在同一文件系统内创建（以保证inode号在文件系统中的唯一性），不能跨文件系统创建。但符号连接在被使用时才由操作系统内核解析并重定向，因此符号连接支持跨文件系统或磁盘分区创建，例如从Linux的ext4分区链接到Windows的NTFS分区。

一个现实的场景是：现有文件A与文件B两个文件，如果文件B通过硬链接的方式链接到文件A，那么网盘系统无法区分这两个文件的内容——在系统看来两个文件具有相同的内容，因此在网盘系统中无论选择上传文件A还是文件B，所上传的文件没有本质上的不同；但如果文件B是通过符号链接的方式链接到文件A的，由于符号B本身是一个软链接文件，仅保存了文件A的路径，这时在网盘系统中上传文件B就不能达到备份文件A的目的（如果该网盘系统不会忽略符号链接的话）。

文件保护的若干方式：

口令保护：口令是访问文件时需要提供的“通行证”，通常被明文存放于FCB或索引结点。

优点：保存口令所需的空间开销少，验证口令的时间开销少——因为操作系统访问文件时本来就需要先获得文件的FCB或索引结点。

缺点：口令被明文存储，安全性很低。
加密保护：使用加密算法对文件加密并存储加密后的文件，用户需要提供正确的密钥才能正确解密被加密的文件。

优点：安全性高。

缺点：编码译码需要额外的时间。
访问控制：由操作系统提供权限控制。通常操作系统会在每个文件的FCB或索引结点中添加权限控制表（ACL，Access-Control List）以记录各用户对文件的各操作权限。为降低多用户环境下ACL的空间开销，可以考虑精简访问列表：将若干用户划分为数量更少的组，以组为单位划分权限。

优点：实现灵活，可以实现更复杂更精细的权限控制。

I/O

操作系统作为系统资源的管理者，不仅需要对软件进行管理，还需要对硬件进行管理。本章主要讨论操作系统对外围设备的管理。

UNIX和类UNIX系统的设计思想是“万物皆文件”，因此会将外部设备抽象为特殊的文件，用户可以使用与文件操作相同的方式操作外部设备。

按照信息交换的单位，可以将I/O设备分为块设备与字符设备。块设备传输速度快，可寻址，支持随机读写，例如磁盘；字符设备传输速度慢，不可寻址，不支持随机读写，例如USB键盘与USB鼠标，常采用中断驱动I/O控制方式。

I/O控制器

CPU不能直接控制I/O设备的机械部件，因此I/O设备需要一个电子部件作为CPU与I/O设备间的中介以实现CPU对I/O设备的控制。这一电子部件就是I/O控制器，又名设备控制器，CPU可以控制I/O控制器，I/O控制器控制设备的机械部件。

I/O控制器主要有四个功能：

接收并识别来自CPU的命令：I/O控制器中存在控制寄存器，用于存放来自CPU的命令与参数。
向CPU报告设备状态：I/O控制器中存在状态寄存器，用于记录I/O设备的当前状态。
数据交换：I/O控制器中存在数据寄存器。设备输入时，数据寄存器暂存CPU发来的数据，随后I/O控制器将这些数据传递给I/O设备；设备输出时，数据寄存器暂存来自设备的数据，随后CPU从数据寄存器读取数据。
地址识别：通过为I/O控制器内的各寄存器编址，根据CPU的命令准确操作具体的寄存器。

I/O控制方式

I/O控制方式主要有四种：

程序直接控制（轮询）
中断驱动
DMA
通道控制

程序直接控制（轮询）

CPU通过轮询（Polling）设备状态寄存器的方式主动检测I/O设备是否就绪。若设备未就绪，CPU持续循环检查，直到数据传输完成。

流程：

CPU发出I/O指令启动设备，设备状态设为“未就绪”
CPU不断轮询设备状态寄存器，直到设备就绪
设备完成数据传输后，CPU将数据从设备寄存器拷贝至内存

特性：

CPU干预频率：极高，CPU全程需轮询检查，每个字（节）的读写都需要CPU的全程介入。
数据单位：单字（节）传输
数据流向：I/O设备 ↔︎ CPU寄存器 ↔︎ 内存

优点：实现简单，仅需循环检查指令，是比较早期的实现方式。

缺点：CPU与设备串行工作，CPU长期忙等待，利用率极低。

中断驱动

引入中断机制，设备完成I/O操作后主动通过中断信号通知CPU，减少轮询开销。

流程： 1. CPU启动I/O操作后，挂起/阻塞当前进程，执行其他任务。 2. 设备就绪后触发中断，CPU保存当前进程上下文，处理中断。 3. CPU从设备寄存器读取单字数据存入内存，恢复原进程。

特性：

CPU干预频率：每次I/O操作前后介入，等待期间可并行其他任务，每个字（节）的在I/O设备与内存间传输仍然需要CPU全程介入。
数据单位：单字（节）传输
数据流向：I/O设备 ↔︎ CPU寄存器 ↔︎ 内存

优点：CPU与设备并行，利用率显著提升。

缺点：每次传输需中断处理，高频中断增加CPU开销，并且仍然只能单字（节）传输。由于中断涉及保存现场与恢复现场，存在一定的时间开销，因此触发中断的频率不能过分高，否则将降低系统性能。

DMA

DMA技术（Direct Memory Access）借助DMA控制器直接在I/O设备与内存间进行数据传输，CPU仅干预传输的起始和结束。DMA控制器是一种特殊的I/O控制器，其大致构成见下图。

流程：

CPU初始化DMA控制器：设置内存地址、数据块大小等参数。
DMA控制器接管总线，直接完成整块数据传输，无需CPU参与。
传输完成后，DMA控制器通过中断通知CPU。

特性：

CPU干预频率：CPU只需要在块传输开始和结束时介入，数据块在I/O设备与内存间直接传输的过程中不需要CPU干预。
数据单位：块（连续数据块）
数据流向：I/O设备 ↔︎ 内存（不再经过CPU寄存器）

优点：进一步减少了CPU的干预，提升了数据传输效率，支持高速设备批量传输。

缺点：仅支持连续块传输，离散数据则需多次操作。

通道控制

通过专用硬件通道执行通道程序，独立管理I/O操作。通道（Channel）是一种专门硬件，是一类专用的、任务特化的处理器，能够识别并执行一系列通道指令。与CPU相比，通道能执行的指令十分单一。同时，通道与CPU共享内存，通道程序一般在主机内存中运行。

流程：

CPU向通道发送I/O指令，指明通道程序位置和设备。
通道执行内存中的通道程序，完成一组数据块传输。
任务完成后，通道发送中断通知CPU。

特性： - CPU干预频率：极低，仅需初始化和最终中断处理。 - 数据单位：一组数据块（可以离散的，也可以是连续的） - 数据流向：设备 ↔︎ 内存（通道控制）

优点：CPU、通道、设备完全并行，资源利用率很高。

缺点：需专用通道硬件支持，硬件成本较高。

I/O软件层次结构与接口

SPOOLing

假脱机技术，也被称为SPOOLing（Simultaneous Peripheral Operation On-Line），通过软件模拟脱机技术用磁盘替代磁带以实现I/O操作的“逻辑脱离”，其核心目标是将独占设备虚拟化为共享设备（如共享打印机）。

要理解假脱机技术，应该首先了解何为脱机技术。脱机技术是早期计算机为解决CPU与慢速I/O设备速度不匹配问题而提出的解决方案，通过引入外围机作为中介从而将I/O操作与主机解耦，实现数据处理的并行化。例如，外围机将数据从慢速输入设备卡片阅读机预先传输到高速存储介质磁带上，主机直接从磁带读取数据，避免直接等待卡片阅读机的读取。

基于这一思想，SPOOLing通过软件模拟脱机技术输入进程与输出进程。SPOOLing系统由以下组件构成：

输入井与输出井：在磁盘上开辟的存储区域，分别用于缓存输入设备的原始数据和待输出的计算结果。
输入/输出缓冲区：在内存中的临时存储区，用于协调磁盘与I/O设备的速度差异。
输入/输出进程：软件模拟的外围控制机，负责管理数据在设备、缓冲区、磁盘之间的传输。
井管理程序：控制作业与磁盘之间的数据交换，确保任务有序执行。

SPOOLing最典型的应用是虚拟化设备与异步操作：将原本只允许各进程串行使用的物理独占设备“改造”为在逻辑上允许各进程能够同时使用的共享设备，支持多进程并发使用。来自用户进程的多个对物理独占设备的使用请求将被存入输出井，由井管理程序生成请求表加入队列；待物理独占设备空闲时，输出进程按队列顺序从输出井读取数据并传递给设备。如此这般，以逻辑共享的方式实现了让每个用户进程感知自己“独占”了只支持串行使用的设备。