第1章 操作系统引论

1.1 操作系统（OS）的定义与作用

定义：OS是配置在硬件资源上的第一层软件，是对硬件系统的首次扩充。
核心作用：

1. 作为计算机资源的管理者：负责处理机管理、存储器管理、文件管理、设备管理。
2. 作为用户与计算机硬件系统的接口：用户通过OS使用计算机硬件资源。
3. 作为扩充机器：无软件的计算机称为“裸机”，OS将裸机改造为功能更强、更易使用的“虚拟机”。

1.2 操作系统的发展历程

人工操作方式 → 脱机I/O方式 → 单道批处理系统 → 多道批处理系统 → 分时系统 → 实时系统 → 嵌入式操作系统

• 脱机I/O：事先将用户程序和数据通过纸带输入磁带，CPU需用时从磁带高速调入内存，减少CPU等待时间。
• 单道批处理系统：内存中仅保持一道作业，连续处理；缺点：I/O请求时CPU处于等待状态，利用率低。
• 多道批处理系统：用户作业先存于外存后备队列，由作业调度程序选若干作业调入内存，共享CPU和系统资源，提升CPU利用率。
• 分时系统：核心满足人机交互，支持多用户共享主机，让每个用户感觉独占主机（无其他用户干扰）。
• 实时系统：分为硬实时（如导弹制导系统，必须严格按时完成）和软实时（如火车订票系统，允许轻微延迟）。

1.3 操作系统的基本特征

1. 并发：一段时间内，宏观上有多个程序同时运行（微观上CPU分时切换执行）。
2. 共享：系统资源被多个进程共同使用，分为两种：
   • 互斥共享：临界资源，一段时间内仅允许一个进程访问（如打印机）。
   • 同时共享：允许多个进程同时访问（如硬盘）。
3. 虚拟：通过时分复用、空分复用技术，将一个物理实体转化为多个逻辑对应物（如虚拟内存、虚拟CPU）。
4. 异步：进程以不可预知的速度向前推进，OS通过PCB协调，保证进程最终完成。

1.4 操作系统内核

内核是OS中与硬件紧密相关、最基本、最核心的软件，常驻内存；作用：保护核心软件，提高OS运行效率。
内核两大核心功能：

1.4.1 支撑功能

• 中断处理、时钟管理、原语操作。
• 原语：由若干条指令组成，完成特定功能的过程，具有原子性（要么全做、要么不做，执行过程不可中断）。
• 原子操作：不可分割的基本操作单位，是原语的核心特性。

1.4.2 资源管理功能

• 进程管理：进程状态管理、进程调度与分配、PCB的创建与撤销。
• 存储器管理：内存空间分配与回收、内存保护、地址映射、内存扩充。
• 设备管理：缓冲区管理、设备分配与回收。

1.5 处理机的两种工作模式

• 用户态（目态，0态）：用户程序运行的模式，仅能执行非特权指令（不会损害系统）。
• 内核态（管态、系统态，1态）：OS内核运行的模式，可执行特权指令（如修改内存地址、控制设备）。
• 切换方式：用户程序通过系统调用，从用户态切换到内核态，请求OS内核完成特定功能。
• 系统调用：应用程序请求OS内核完成某一功能的特殊过程调用，是用户程序与OS内核交互的唯一途径。

1.6 中断和异常

1.6.1 中断（外中断）

引入目的：支持CPU与设备的并行操作。
定义：来自CPU执行指令以外的事件（与当前指令无关），如I/O结束中断、时钟中断。
不同计算机的中断（指外中断）处理过程各具特色，就其多数而论，中断处理流程如下图所示。各阶段处理流程的描述如下：
1）关中断。
2）**保存断点。**为保证中断服务程序执行完毕后能正确地返回到原来的程序，必须将原来的程序的断点（即程序计数器 PC）保存起来。
3）**引出中断服务程序。**其实质是取出中断服务程序的入口地址送入程序计数器 PC。
4）**保存现场和屏蔽字。**进入中断服务程序后，首先要保存现场，现场信息一般是指程序状态字寄存器 PSWR 和某些通用寄存器的内容。
5）**开中断。**允许更高级中断请求得到响应。
6）**执行中断服务程序。**这是中断请求的目的。
7）**关中断。**保证在恢复现场和屏蔽字时不被中断。
8）**恢复现场和屏蔽字。**将现场和屏蔽字恢复到原来的状态。
9）**开中断、中断返回。**中断服务程序的最后一条指令通常是一条中断返回指令，使其返回到原程序的断点处，以便继续执行原程序。
以上是多重中断的流程，其中，1~3 步是由硬件（中断隐指令）完成的；4-9 步是由中断服务程序完成的。

1.6.2 异常（内中断、例外、陷入）

引入目的：处理CPU执行指令本身出现的问题。
定义：源自CPU执行指令内部的事件，分为两类：

• 出错事件：如非法操作码、地址越界、算术溢出、缺页异常。
• 用户请求：如系统调用。
  特点：处理依赖当前程序运行现场，不可被屏蔽。

1.7 操作系统的主要功能

1. 处理机管理：进程控制、进程同步、进程通信、死锁处理、处理机调度。
2. 存储器管理：核心是提高内存利用率，包括内存分配与回收、地址映射、内存保护与共享、内存扩充。
3. 文件管理：计算机中信息以文件形式存在，负责文件的创建、删除、读写、保护等。
4. 设备管理：完成用户I/O请求，方便用户使用设备，提高设备利用率。
5. 接口管理：包括用户接口（如图形界面、命令行）和程序接口（如系统调用）。

1.8 操作系统的结构

1. 简单式结构
2. 模块化结构
3. 分层式结构
4. 微内核结构：仅保留OS最基本功能（如进程通信、中断处理），体积小、可扩展性强。
5. 外核结构

第2章 进程的描述与控制

2.1 前趋图

2.1.1 前趋图示意

有向无环图（DAG），用于描述进程间执行的先后顺序（如A进程完成后，B进程才能执行）。

2.1.2 程序的执行方式

1. 顺序执行：特征为顺序性、封闭性（独占全机资源）、可再现性（多次执行结果一致）。
2. 并发执行：特征为间断性（CPU分时切换）、失去封闭性（共享资源）、不可再现性（多次执行结果可能不同）。

2.1.3 进程的描述

1. 进程的定义

进程是程序的执行过程，是系统进行资源分配和调度的独立单位；创建进程的实质是创建其对应的PCB（进程控制块）。

2. 进程的特征

• 动态性：由创建产生、调度执行、撤销消亡。
• 并发性：可与其他进程并发执行。
• 独立性：是资源分配和调度的独立单位。
• 异步性：以不可预知的速度推进。

3. 进程的状态及转化

• 三大基本状态：就绪态（等待CPU调度）、执行态（占用CPU运行）、阻塞态（等待某事件完成，如I/O）。
• 补充：具有挂起操作的状态转换（挂起就绪、挂起阻塞），核心是将进程从内存移至外存，释放内存资源。
  

2.1.4 进程控制块（PCB）

1. PCB的作用

（1） 作为进程独立运行的基本标志：创建进程即创建其PCB，PCB存在则进程存在。
（2）实现间断式运行：进程中断时，CPU现场信息（如寄存器、程序计数器）保存在PCB中，再次调度时恢复。
（3） 提供进程管理所需信息：OS通过PCB实现对进程的控制和管理。
（4）提供进程调度所需信息：供调度算法选择下一个执行的进程。
（5）实现进程间的同步与通信：通过PCB中的相关信息（如等待队列指针）协调进程交互。

2. PCB包含的核心信息

1. 进程标识信息：PID（进程唯一ID）、父进程ID、用户ID、进程名称、优先级。
2. 进程状态信息：记录当前状态（新建、就绪、运行、阻塞、终止），用于调度判断。
3. 处理机上下文（核心）：程序计数器（PC，记录下一条要执行的指令地址）、通用寄存器、程序状态字（PSW）；用于进程切换时保存/恢复现场。
4. 进程调度信息：调度优先级、时间片大小、等待队列指针、调度算法所需参数。

3. PCB的组织方式

操作系统中，系统会把所有PCB集中管理，主要三种组织方式：

1. 线性表方式（顺序表）
   把所有PCB连续存放在一个数组中，不管进程状态统一排列。 优点：结构简单、实现容易。缺点：查找、增删效率低，进程多的时候开销大。

2. 链表方式（最常用）
   按照进程状态分类，分别形成多条链表： 就绪队列：所有就绪等待CPU的进程。 运行队列：当前正在运行的进程（单CPU只有1个）阻塞/等待队列：等待某事件（I/O、信号）的进程。优点：增删进程速度快，调度方便，分类清晰。缺点：查找指定进程较慢。

3. 索引表方式
   建立若干索引表（就绪索引表、阻塞索引表等）。索引表中存放对应状态PCB的地址指针，PCB本体集中存放。优点：兼顾查找速度与动态管理，适合进程数量多的系统。

2.1.5 进程创建，终止，阻塞和唤醒

1. 引起进程创建的事件

用户登录、作业调度（批处理）、进程请求创建子进程、提供服务（系统主动创建服务进程）。

2. 进程创建过程

• 申请空白PCB；
• 为新进程分配其运行所需的资源；
• 初始化PCB（程序状态、优先级、程序计数器等）；
• 将新进程插入就绪队列。

3. 引起进程终止的事件

进程正常运行结束、进程运行异常终止、外界强制干预终止进程。

4. 进程终止过程

• 撤销进程的相关链接
• 释放进程占用的各类资源
• 回收进程控制块PCB

5. 引起进程阻塞的事件

发起I/O请求、等待特定事件发生、等待获取临界资源。

6. 进程阻塞过程

当前进程放弃CPU，修改PCB状态为阻塞，移入对应阻塞队列，调度其他进程执行。

7. 引起进程唤醒的事件

进程等待的事件完成，如I/O结束、资源释放、等待信号到达。

8. 进程唤醒过程

将进程从阻塞队列移出，修改PCB状态为就绪，插入就绪队列等待系统调度。

2.2 进程通信的类型

低级通信

仅传递少量控制信息，效率低、数据传输能力弱。

1. 共享变量
2. 信号量、信号

高级通信

可大批量传输数据，方便高效，分为三类：

1. 共享存储器：开辟共享内存空间，进程直接读写交换数据。
2. 消息传递：将通信的数据封装在消息中，以消息为单位收发数据，分为直接通信、间接通信。
3. 管道通信：利用管道文件（用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件），实现父子进程或亲缘进程单向数据传输。

2.7 线程

2.7.1 线程的定义

线程是进程内的一个执行单元，是进程中独立的调度和执行实体；一个进程可包含多个线程，共享进程的地址空间与资源，线程自身仅拥有少量私有资源。进程是资源分配的基本单位，线程是调度的基本单位。

2.7.2 线程的基本特征

• 轻型实体：线程自身资源极少，创建与销毁开销远小于进程。
• 共享资源：同一进程内所有线程共享进程内存、文件、设备等资源。
• 独立调度：线程是操作系统调度和分派的基本单位。
• 并发执行：同一进程内多线程可并发运行，提升程序执行效率。
• 依附进程：线程不能独立存在，进程消亡则所属所有线程随之终止。

2.7.3 线程与进程的区别

1. 资源分配单位
   进程：是系统资源分配的基本单位，拥有独立完整的地址空间与系统资源。
   线程：仅拥有少量私有资源，共享所属进程的全部资源，无独立地址空间。每个线程中有线程控制块TCB（Thread control block）

2. 调度执行单位
   进程：早期OS以进程为调度单位，切换开销大。
   线程：现代OS以线程为调度单位，切换仅需保存少量上下文，开销极小。

3. 开销成本
   进程：创建、撤销、切换开销大，系统负担重。
   线程：创建、撤销、切换速度快，系统开销低。

4. 通信方式
   进程：进程间地址空间隔离，需依靠高级通信机制（管道、消息、共享内存）完成通信。
   线程：同进程内线程共享地址空间，可直接读写全局变量实现通信，简单高效。

5. 独立性与稳定性
   进程：各进程相互独立，一个进程崩溃不会影响其他进程。
   线程：同一进程内线程高度耦合，单个线程异常崩溃，会导致整个进程终止。

6. 地址空间
   进程：拥有独立的虚拟地址空间，相互隔离。
   线程：同进程内所有线程共用同一地址空间。

2.7.4 线程的实现方式

1. 用户级线程（ULT）
   线程管理全部由用户空间的线程库完成，操作系统内核感知不到线程存在，仅能识别进程；线程切换在用户态完成，无需内核介入，不用切换状态，切换开销小。缺点：单进程内多个用户级线程无法利用多核CPU，一个线程阻塞会导致整个进程阻塞。

2. 内核级线程（KLT）
   线程的创建、调度、管理由操作系统内核实现，内核可直接感知线程；线程切换需陷入内核态，支持多核并行执行，某一线程阻塞不影响同进程其他线程。缺点：线程切换、创建销毁开销相对更大。

3. 混合实现方式
   结合用户级线程与内核级线程的优势，采用多对一、一对一、多对多映射模型；既保留用户级线程低开销的特点，又可借助内核级线程实现多核调度与阻塞隔离，是当前主流操作系统常用方案。

2.7.5 进程和程序的区别

1. 程序是永存的；进程是暂时的，进程是程序的一个实例，是程序的一次执行过程。
2. 程序是静态的观念，进程是动态的观念；
3. 程序是进程的代码部分；
4. 进程在内存中，程序在外存中；
5. 进程和程序不是一 一对应的： 一个程序可对应多个进程即多个进程可执行同一程序； 一个进程可以执行一个或几个程序。

第3章 处理机调度和死锁

3.1 处理机调度的层次

3.1.1 三层调度

• 高级调度：外存 → 内存（选作业）
• 中级调度：内存 ↔ 外存（换进程）
• 低级调度：就绪 → 运行（抢CPU）

1. 高级调度（长程调度/作业调度）

• 对象：外存后备作业
• 功能：从外存作业队列中挑选作业调入内存，为其创建进程、分配资源，放入就绪队列。
• 频率：最低，分钟/小时级调度。
• 作用：决定多少作业进入系统，调控系统负载。

2. 中级调度（内存调度）

• 对象：挂起进程
• 功能：负责进程的挂起与激活，在内存和外存之间调换进程，缓解内存紧张。
• 频率：中等。
• 作用：提高内存利用率与系统吞吐量，实质是存储器管理的对换功能。

3. 低级调度（进程调度/短程调度）

• 对象：内存就绪进程/线程
• 功能：从作业的就绪队列选中一个进程，分配CPU使其运行。
• 频率：最高，毫秒级，最频繁。
• 作用：直接决定CPU的实时分配，是最核心的调度。

3.2 作业和作业调度

1. 作业

作业是比程序更为广泛的概念，是用户提交给操作系统的完整任务单位，包含程序、数据、作业控制指令，是用户请求系统完成的一项完整工作。

• 存在位置：未运行时存放在外存后备队列；
• 组成：程序+原始数据+作业说明书；
• 关系：作业调入内存后，为每个作业设置了一个作业控制块（JCB）, 会为其创建对应进程。

2. 作业调度（高级调度、长程调度）

作业调度是处理机三层调度中的高级调度，是操作系统按照一定算法，从外存后备作业队列中选取合适作业调入内存，分配必要资源、创建进程，并加入进程就绪队列的过程。

• 调度对象：外存中的后备作业；
• 核心任务：决定哪些作业可以进入内存参与竞争CPU；
• 调度频率：最低，执行速度慢；
• 适用场景：多道批处理系统为主，分时、实时系统一般无高级调度。

3.3 进程调度任务

1. 进程调度任务

• 保存CPU现场信息：保存当前运行进程的**CPU现场信息，便于进程再次调度时恢复执行。
• 按某种算法选择进程：按照预设调度算法，从就绪队列中选择一个就绪进程。
• 将CPU分配给进程：将CPU使用权分配给选中进程，恢复其运行现场，使其投入运行。

2. 进程调度机制

1. 排队机制：系统将所有就绪进程按规则组织为就绪队列，统一管理。
2. 分派机制：调度程序选中目标进程后，完成上下文切换，分配CPU资源。
3. 切换机制：保存旧进程上下文、加载新进程上下文，完成进程切换。

进程调度通过调度程序实现，核心包含排队器、分派器、上下文切换器三个机制：排队器将就绪进程按策略组织成队列以提升调度效率；分派器从就绪队列中取出选定进程；上下文切换器则通过保存/恢复进程的CPU现场信息（如寄存器内容）完成进程切换，将CPU分配给新进程运行。为降低切换开销，现代计算机常采用多组寄存器的硬件方案来减少切换耗时。

对应示意图：

3. 进程调度方式

（1）抢占式调度（剥夺式）

当有更高优先级进程到达、或当前进程时间片用完时，立即暂停正在运行的进程，强行剥夺其CPU资源，调度新进程执行。

• 优点：响应速度快、系统实时性强、公平性好。
• 缺点：进程切换频繁，系统开销较大。
• 适用：分时系统、实时系统。

（2）非抢占式调度（非剥夺式）

一旦进程获得CPU，就会一直运行，直到进程主动放弃CPU（运行结束、主动阻塞），才进行调度切换。

• 优点：调度简单、切换开销小。
• 缺点：系统响应慢、紧急任务无法及时处理。
• 适用：早期批处理系统。

（二）处理机调度算法

一、调度算法目标

处理机调度是合理分配CPU资源，在多进程/多线程并发场景下高效利用处理器，不同场景核心目标如下：

1. 资源利用率：最大化CPU使用率，减少空闲等待时间。
2. 系统吞吐量：单位时间内完成进程数量越多，系统效率越高。
3. 响应时间：交互式系统中，缩短用户请求的等待响应时长。
4. 周转时间：批处理系统核心，缩短进程从提交到完成的总耗时。
5. 公平性：合理分配资源，保证各进程公平占用CPU，避免饥饿。
6. 实时性：实时系统中，确保紧急任务按时限完成。

二、常见处理机调度算法

1. 先来先服务（FCFS）

• 规则：按进程到达顺序依次调度，非抢占式。
• 特点：实现简单，长进程会阻塞短进程，短作业不利，适合批处理。

2. 短作业优先（SJF）

• 规则：优先调度 预计运行时间最短的进程， 即短作业，分抢占式/非抢占式。
• 特点：吞吐量高、平均周转时间短；易导致长进程饥饿，需预估运行时长，无法实现人机交互。

3. 时间片轮转（RR）

• 规则：按到达顺序排队，每个进程分配固定时间片，时间耗尽则切换进程。
• 特点：抢占式，响应快，适配分时交互系统；时间片大小影响系统性能。

4. 优先级调度算法

• 规则：按进程优先级分配CPU，每个进程都有一个优先数，默认小的优先数优先级高，高优先级优先执行，分抢占/非抢占。
• 特点：可保障紧急任务；低优先级进程易饥饿，可通过动态优先级调整优化。

5. 多级反馈队列调度

• 规则：设置多个优先级队列，优先级越高的队列，时间片越短；新进程入高优先级队列，时间片用完降级，转入下一级队列，I/O进程优先级提升。
• 特点：综合多种算法优势，无需预知进程运行时长，是操作系统默认主流调度算法，兼顾交互与批处理。

6. 高响应比优先（HRRN）

• 规则：引入响应比 = (等待时间+运行时间)/运行时间，即响应时间/运行时间，每次调度选响应比最高进程。
• 特点：兼顾短作业与长作业，当等待时间相同，则运行时间短的作业先执行，此时类似SJF，当运行时间相同，则等待时间短的作业先运行，此时类似FCFS，避免饥饿，平衡等待时间与运行时长，不过，调度前计算进程的响应比会增加系统开销。

7. 最早截止时间优先算法（EDF）

适用于实时系统，抢占式动态调度。
调度规则：优先选择截止时间最早的任务投入运行。
特点：动态调度，资源利用率高，能有效保证实时任务按时完成，是经典实时调度算法。

8. 最低松弛度优先算法（LLF）

适用于实时系统。
松弛度公式：松弛度 = 截止时间 - 当前时间 - 剩余运行时间
调度规则：每次选择松弛度最低的进程优先执行。
特点：实时性强，临近超时任务会被优先调度，防止任务错过截止时间。

(三）进程死锁定义，必要条件，处理方法

一、定义：
指多个进程在并发执行中，各自占有部分资源，又互相等待对方所持有的资源，导致所有进程都无法继续推进、无限阻塞的僵持状态。
简单理解：
你拿着我需要的资源，我拿着你需要的资源，双方都不放手、互相等待，谁都无法运行。

二、死锁产生的四个必要条件（缺一不可）

1. 互斥条件：资源同一时刻仅允许一个进程使用；
2. 请求与保持：进程已占有资源，又申请新资源且不释放已有资源；
3. 不可抢占：已分配的资源不能被强行抢占，只能进程主动释放；
4. 循环等待：进程间形成循环等待资源的闭环。

三、死锁处理方法

1. 死锁预防
   破坏三个必要条件中任意一个，互斥条件不能改变，从根源杜绝死锁发生。
   （1）破坏“请求和保持”条件：规定所有进程必须一次性申请全部所需资源，从而破坏‘“请求”条件。只要有一种资源不能满足进程的要求，即使其他资源空闲，也不分配给该进程而是让其等待，从而破坏了“保持”条件。
   （2）破坏“不可抢占”条件：当一个进程保持了某些不可抢占资源，而又提出新的资源请求，必须释放已经保持的所有资源，待以后需要时再重新申请。
   （3）破坏 “循环等待” 条件：对系统所有资源进行统一编号排序，规定所有进程必须严格按照资源编号递增顺序申请资源，杜绝循环等待的环路形成。

2. 死锁避免
   不强制破坏必要条件，动态判断资源分配安全性，银行家算法为典型代表，合理分配资源规避死锁。避免死锁实质在于，使系统在进行资源分配前不进入不安全状态。
   ** 银行家算法 **
   主要思想是避免系统进入不安全状态，在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先试行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样就保证系统始终处于安全状态，从而避免死锁现象的发生。

3. 死锁检测与解除
   允许死锁自发发生，系统不提前限制资源申请；定期检测系统是否存在死锁，若检测到死锁，通过终止进程、抢占回收资源等方式解除死锁。
   资源分配图：
   由进程结点、资源结点、请求边、分配边组成，用来直观描述进程与资源的占用、申请关系。
   资源分配图的完全简化
   若能消去图中所有的边，使所有的进程节点都成为孤立的节点，则称该图为可完全简化。
   死锁定理
   资源分配图不可完全简化，是系统产生死锁的充分必要条件。
   
   终止死锁进程的方法：
   （1） 一次性终止全部死锁进程
   直接杀死所有陷入死锁的进程，彻底破除死锁环路。
   优点：操作简单、快速解除死锁；
   缺点：系统开销大，进程已完成的工作全部作废，数据丢失严重。
   （2）逐个终止死锁进程（依次撤销）
   按照一定策略，每次只终止一个死锁进程，回收其资源；
   不断检测，直到死锁完全解除。
   常用选择策略：
   - 优先终止优先级低的进程
   - 优先终止运行时间短、代价小的进程
   - 优先终止占用资源少的进程

4. 忽略死锁（鸵鸟策略）
   默认死锁发生概率极低，不做任何处理，主流操作系统普遍采用。

什么是饥饿？与死锁有什么差别？

等待时间给进程推进和响应带来明显影响时成为进程饥饿。
饥饿并不代表系统已经死锁，但至少有一个程序的执行被无限期地推迟。
差别：
① 进入饥饿的进程可以只有一个，但是死锁必须大于等于两个；
② 出于饥饿状态的进程可以是一个就绪进程，但是死锁状态的进程必定是阻塞进程。

（四）进程资源分类

一、按可否抢占划分

1. 可抢占资源
   可强行从进程收回，不会造成破坏。
   例：CPU、内存。

2. 不可抢占资源
   不能强行抢占，只能由进程主动释放。
   例：打印机、磁带机。

二、按使用方式划分

1. 临界资源（独占资源）
   同一时刻仅允许一个进程使用，需要互斥访问。
   例：打印机、摄像头、临界数据。

2. 共享资源
   可同时被多个进程并发访问。
   例：只读文件、公共内存区域。

三、按资源实例数量划分

1. 单实例资源：系统仅有一个
2. 多实例资源：系统存在多个可用

第四章 进程同步

一、进程同步基本概念

1. 两种制约关系

1. 间接相互制约（互斥）
   多个进程竞争临界资源，因资源独占性产生制约；
   同一时刻仅允许一个进程访问，属于互斥关系。
   例：多个进程竞争打印机、全局变量。

2. 直接相互制约（同步）
   进程间存在执行先后次序约束，为完成协作任务形成等待-唤醒关系；
   一个进程执行依赖另一个进程的运行结果，属于同步关系。
   例：生产者写完数据，消费者才能读取数据。

2. 临界资源与临界区

• 临界资源：一次仅允许一个进程使用的独占型共享资源（硬件/软件）。
  例：打印机、磁带机、全局变量、缓冲区。
• 临界区：每个进程中访问临界资源的那段代码片段,多个进程的临界区代码必须互斥执行。
• 事件 Event：允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。事件分为手
  动重置事件和自动重置事件。手动重置事件被设置为激发状态后，会唤醒所有等待的线程，而且
  一直保持为激发状态，直到程序重新把它设置为未激发状态。自动重置事件被设置为激发状态
  后，会唤醒一个等待中的线程，然后自动恢复为未激发状态。

二、同步机制四条准则（重点）

1. 空闲让进
   临界资源空闲时，允许请求进入临界区的进程立即进入，提高资源利用率。
2. 忙则等待
   临界资源已被占用，其他请求进程必须等待，保证临界区互斥访问。
3. 有限等待
   等待进入临界区的进程，等待时间必须有限，避免永久阻塞、饥饿问题。
4. 让权等待
   进程无法进入临界区时，主动放弃CPU，转入阻塞态，不忙等、不浪费处理机资源。

三、实现临界区互斥的方法

1. 软件实现

• 单标志法、双标志先检查、双标志后修改、Peterson算法
• 特点：纯代码逻辑实现，无需硬件支持；逻辑复杂，易出错。

2. 硬件实现

• 关闭中断：进入临界区关中断，退出开中断，简单粗暴，粒度大。
• 硬件原子指令：Test-And-Set、Swap指令，硬件保证操作原子性。

3. 信号量机制（主流）

利用信号量PV操作，高效实现同步与互斥。
互斥量 Mutex： 互斥量是内核对象，只有拥有互斥对象的线程才有访问互斥资源的权限。因为互斥对象只有一个，所以可以保证互斥资源不会被多个线程同时访问；当前拥有互斥对象的线程处理完任务后必须将互斥对象交出，以便其他线程访问该资源；比如P(mutex)与V(mutex)在临界区前后成对使用。
信号量 Semaphore： 信号量对象保存了最大资源计数和当前可用资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就减1，如P(Semaphore), 只要当前可用资源计数大于0，就可以发出信号量信号，如果为0，则将线程放入一个队列中等待。线程处理完共享资源后，应在离开的同时将当前可用资源数加1, 如V(Semaphore),。如果信号量的取值只能为0或1，那么信号量就成为了互斥量；

四、信号量机制

1. 整型信号量

定义整型变量S，仅能通过P、V原语操作：

• P操作（申请资源）：S--，若S＜0，进程阻塞等待。
• V操作（释放资源）：S++，若S≤0，唤醒一个阻塞进程。
  缺点：不满足让权等待，存在忙等。

2. 记录型信号量（常用）

包含：信号量值value + 阻塞等待队列。

• value > 0：空闲资源数量
• value = 0：资源刚好占用完毕
• value < 0：等待进程的数量
  完全满足同步四大准则，让权等待，无忙等。

3. 信号量分类

• 互斥信号量：初值=1，用于临界区互斥访问。
• 同步信号量：初值=0或资源数，控制进程执行先后顺序。
• 资源信号量：初值为系统可用资源总数。

五、经典同步互斥问题

1. 生产者-消费者问题

问题描述

一组生产者进程负责往缓冲区写入数据，一组消费者进程从缓冲区取出数据；
缓冲区大小有限，两者并发执行，需满足：

1. 缓冲区满：生产者阻塞
2. 缓冲区空：消费者阻塞
3. 缓冲区同一时刻仅允许一个进程访问（互斥）

核心信号量设置

• empty：同步信号量，初值=n（空闲缓冲区数量）
• full：同步信号量，初值=0（已存数据缓冲区数量）
• mutex：互斥信号量，初值=1（保护缓冲区临界区）

代码：

核心逻辑

• 生产者：P(empty) → P(mutex) → 写入数据 → V(mutex) → V(full)
• 消费者：P(full) → P(mutex) → 取出数据 → V(mutex) → V(empty)

易错点

同步信号量P操作必须放在互斥信号量P操作之前，防止死锁。

2. 哲学家进餐问题

核心矛盾：竞争左右筷子（临界资源），易循环等待引发死锁。
解决思路：

1. 最多允许4位哲学家同时进餐
2. 奇数号先拿左筷、偶数号先拿右筷
3. 一次性申请两只筷子，破坏循环等待条件

3. 读者-写者问题

读-读不互斥，读-写互斥，写-写互斥。

• 第一类读者写者：读者优先，读进程可并发，写进程易饥饿。
• 第二类读者写者：写者优先，保证写操作及时执行，实时性更强。

六、管程

1. 定义

管程是一种高级同步机制，将共享数据、操作数据的过程、同步控制封装为一个整体；
仅允许管程内过程访问共享数据，自动保证互斥，弱化底层PV操作难度。

2. 组成

• 共享数据结构
• 操作数据的过程
• 条件变量（实现等待/唤醒，解决同步）

3. 优势

无需手动编写PV操作，自动实现临界区互斥，代码可读性强、不易出错。

七、AND型信号量 & 信号量集

1. AND型信号量
   一次性申请进程所需全部资源，要么全部分配、要么全不分配，破坏请求与保持，预防死锁。

2. 信号量集
   一次性申请多个同类资源，设定下限阈值，提升资源分配灵活性。

第5章 存储器管理

存储器管理的对象是内存

5.1 存储器的层次结构

5.1.1 存储器的多层结构

在存储层次中，层次越高（越靠近CPU）,存储介质的访问速度越快，价格也越高，所配置的容量也越小。
寄存器和主存储器又被称为可执行存储器，进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问，但对辅存的访问则需要通过I/O设备实现。

1. 寄存器

寄存器是CPU中的一些小型存储区域，暂存参与运算的指令、数据和运算结果等内容。访问速度最快，和处理机同速。

2. 高速缓存

缓和CPU和内存速度不匹配的矛盾，介于寄存器和内存之间，将内存中常用的数据备份到高速缓存中，以减少处理机对内存的访问次数。这样，当CPU访问一组特定信息时，首先检查它是否在高速缓存中，如果在，就直接取出并使用，以避免访问内存。

3. 主存储器

主存储器，简称主存或内存，用于保存进程运行时的程序或数据。通常，处理机都会从内存中取得指令和数据，将指令放入指令寄存器，将数据放到数据寄存器，或者，进行相反操作，将寄存器中的数据存入内存。

4. 辅助存储器

简称辅存，属于外部存储器，远离 CPU，访问速度最慢、单位价格最低、存储容量最大。用于长期存放暂不运行的程序、海量数据、文件资料等信息，断电后数据不会丢失。CPU 不能直接存取辅存内容，必须先通过 I/O 操作调入主存（内存）后，才能被 CPU 调用（因此，内存也可看作是辅存的高速缓存），常见类型有硬盘、U 盘、光盘、移动硬盘等。

5.2 程序的装入和链接

5.2.1 将用户程序变为可在内存中执行的程序的步骤

1. 编译：由编译程序将用户源代码编译成若干目标模块。
2. 链接：由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。
3. 装入：由装入程序将装入模块装入内存中运行。
   

5.2.2 程序的链接方式

1. 静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开。
2. 装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。

• 便于修改和更新：只需单独修改对应目标模块，无需重新编译链接整个程序，修改后重新装入即可生效，维护便捷。
• 便于实现对目标模块的共享：多个应用程序可共用同一个目标模块，内存中仅留存一份副本，大幅节省内存空间。

3. 运行时动态链接：知道程序运行过程中需要一些模块时，才对这些模块进行链接。

5.2.3 程序的装入方式

程序的装入方式是指何时将逻辑地址（相对地址）转变为物理地址（绝对地址）。

1. ** 绝对装入：编译完成就产生物理地址**。在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。
2. ** 可重定位装入（静态重定位）：装入时产生物理地址**。根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。
3. ** 动态运行装入：运行时产生物理地址**。允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。

存储器管理的功能

存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故应具有以下功能：

• 内存的分配和回收：实施内存的分配，回收系统或用户释放的内存空间。
• 地址变换：将逻辑地址转换成物理地址。
• 扩充内存：借助于虚拟存储技术，为用户提供比内存空间大的地址空间，从逻辑上扩充内存。
• 存储保护：保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。

5.3 对换与覆盖

覆盖技术和对换技术用于内存“扩充”，并不指增加系统的物理内存，而是指在现有的物理内存的基础上扩大内存的使用效率，常用的内存扩充技术还包括紧凑和虚拟存储器。

5.3.1 对换技术

把内存中暂时不能运行的进程或暂时不用的程序和数据移到外存中去，以便腾出必要的内存空间，将具备运行条件的进程或进程所需的程序和数据存入内存，实现所谓的“对换”。

1. 对换的类型
   （1）整体对换 ：以进程为单位的对换。
   （2）页面（分段）对换：以进程的一个“页面”或“分段”为单位的对换。
2. 对换区管理
   在具有对换功能的OS中，通常把磁盘空间划分为文件区和对换区两部分。
   （1）文件区管理的主要目标：提高文件存储空间的利用率，才是提高对文件的访问速度。对文件区应采用离散分配存储管理。
   （2）对换区管理的主要目标：提高进程换入和换出的速度，然后才是提高文件存储空间的利用率。对对换区应采取连续分配存储管理。

5.3.2 进程的换入和换出

1. 选择被换出的进程：优先选择处于阻塞或休眠状态的进程，当有多个这样的进程时，优先选择优先级最低的进程。
2. 换出进程：只能换出非共享的程序和数据段。
3. 选择换入进程：优先选择就绪队列中优先级高、等待时间久、迫切需要运行的进程。
4. 换入进程：将外存中就绪状态的进程程序与数据，调入内存空闲分区，分配内存空间，修改进程相关状态信息，使其进入就绪队列等待调度执行。

5.3.3 覆盖技术

在内存中保留那些在任何时候都需要的指令和数据，程序其余的部分（即那些不会同时执行的程序段），则根据它们自身的逻辑结构，使它们共享同一块内存区域。

• 覆盖技术的优点：不需要OS的特别支持。用户通过简单的文件结构将文件读入内存，并执行所读指令，即可实现完全覆盖。
• 覆盖技术的缺点： 覆盖结构的程序设计很复杂，需要程序员对程序结构、数据结构有完全的了解。

覆盖技术和对换技术区别：

1. 与覆盖技术相比，对换技术不要求程序员给出的程序段之间的覆盖结构；
2. 对换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行；对换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行；
3. 覆盖技术只能覆盖于覆盖程序段无关的程序段，对换进程由换出和换入两个过程组成。覆盖技术只能覆盖于覆盖程序段无关的程序段，对换进程由换出和换入两个过程组成。

5.4 内存连续分配存储管理方式

5.4.1 单一连续分配

内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区仅装有一道用户程序，为用户提供的，整个内存的用户区由该程序独占。这种方式无需进行内存保护。
这种方式的优点是简单、无外部碎片，可以釆用覆盖技术，不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。

5.4.2 固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区，如此循环。固定分区分配在划分分区时，有两种不同的方法。

1. 分区大小相等：用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。
2. 分区大小不等：划分为含有多个较小的分区、适量的中等分区及少量的大分区。

5.4.3 动态分区分配

动态分区分配又称为可变分区分配，是一种动态划分内存的分区方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。

动态分区分配算法

在进程装入或换入主存时，如果内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略，考虑以下几种算法：

1. 基于顺序搜索的动态分区分配算法

将系统中的空闲分区链接成一个链，依次搜索空闲分区链上的空闲分区，以寻找一个大小能满足要求的分区。

• 首次适应( First Fit )算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。这会导致低地址区域被不断划分。留下很多碎片。
• 循环首次适应（邻近适应(Next Fit)）算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次找到的空闲分区的下一个空闲分区开始查找。
• 最佳适应( Best Fit )算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。
• 最坏适应(Worst Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。

2. 基于索引搜索的动态分区分配算法

该类算法不再顺序遍历空闲分区链表，而是建立空闲分区索引表，按分区大小分组建立索引，通过索引快速定位符合条件的空闲分区，查找效率远高于顺序搜索，适合内存分区数量多、分配频繁的场景。

• 快速适应算法：将空闲分区按容量大小分类，为每一类大小的空闲分区单独建立一条空闲链表，同时设置一张分区大小索引表，记录各类分区的大小与对应链表首地址。分配流程： 根据进程所需内存大小，直接查询索引表，定位匹配容量类别的空闲分区链表；从对应链表头部取出分区分配，无需逐个遍历所有空闲分区。
• 伙伴系统算法: 将整个内存空间统一划分为2的整数次幂大小的内存块（伙伴块），互为成对、大小相等、地址相邻的两块内存称为伙伴。
• 哈希算法: 以空闲分区大小为哈希关键字，构建哈希表，把相同或相近大小的空闲分区映射到同一哈希桶中。通过哈希函数直接计算目标分区存储位置，快速查找满足条件的空闲分区。

5.4.4 动态重定位分区分配

1. 紧凑：将内存中的所有作业进行移动，使它们全部相邻接，把原来分散的多个小分区拼接成一个大分区，这时就可以把一个作业装入该分区了。但在每次紧凑后，都必须对移动后的 程序或数据进行重定位。
2. 动态重定位：重定位寄存器存内存起始地址，真正访问的内存地址由相对地址与重定位寄存器中的地址相加形成，程序运行时才把逻辑地址转为物理地址。
3. 动态重定位分区分配算法：在这种分配算法中增加了“紧凑”功能。当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有小的空闲分区的容量总和大于或等于用户的要求，则此时便对内存进行“紧凑”，否则，返回分配失败信息。

5.5 分页存储管理方式

5.5.1 分页存储管理基本方法

把进程分成若干个逻辑“页”（页面），把内存也分成大小相等的物理块（页框），逻辑地址 = 页号 + 页内偏移页内偏移大小固定，决定页面大小，设置一张页表，用来记录页号 → 物理块号，实现逻辑地址转物理地址。

5.5.2 地址变换机构

1. 基本的地址变换机构（无快表）：

• 地址分解：当进程访问某个逻辑地址时，地址变换机构自动将逻辑地址分为两部分：页号（p） 和 页内地址（偏移量，d）。

• 越界检查：硬件将页号与页表长度进行比较。如果页号大于或等于页表长度，说明地址越界，系统会触发越界中断，终止本次访问。

• 计算页表项位置：若未越界，将页表起始地址与「页号 × 页表项长度」相加，得到该页号对应的页表项在内存中的位置。

• 获取物理块号：根据计算出的地址，访问内存中的页表，从中读取该页对应的物理块号（b）。

• 合成物理地址：将物理块号送入物理地址寄存器的高位，同时将页内地址送入物理地址寄存器的低位（块内地址字段），拼接得到最终的物理地址，完成地址变换。
  注：该过程每次访问内存数据都需要两次内存访问：第一次查页表（页表放在内存中），第二次读写数据，访存效率降低约50%。

2. 具有快表（TLB）的地址变换过程
   为了解决两次访存的效率问题，系统引入快表（TLB，联想寄存器），存放当前常用的页表项，快表的作用：利用程序的局部性原理，缓存最近访问的页表项，大幅提升地址变换效率。
   地址变换过程如下：

• 地址分解：CPU给出逻辑地址后，硬件自动将其分解为页号和页内地址。

• 快表查找：同时进行两项操作：将页号送入快表，并行查找是否存在匹配的页表项，同步准备对页表的访问（防止快表未命中）。

• 快表命中：若快表中找到匹配项（命中），直接从中取出物理块号，与页内地址拼接成物理地址，直接访问内存数据，仅需1次内存访问。

• 快表未命中：若快表中未找到（未命中），则继续执行基本地址变换流程。

快表TLB 有效访问时间

公式

$$EAT=h\cdot (t_{tlb}+t_{mem})+(1-h)\cdot (t_{tlb}+2t_{mem})$$

• $h$：TLB命中率
• $t_{tlb}$：查快表时间
• $t_{mem}$：访问主存时间
• 命中：查TLB+访内存
• 未命中：查TLB+访页表+访数据

3. 两级页表和多级页表：
   解决页表太大、占内存过多。单层页表整个放进内存，空间浪费严重。只把用到的二级页表调入内存，不用的放外存，实现页表分页，支持大地址空间，适配大容量虚拟地址，适合 32/64 位系统，虽然两级页表相比单级页表节省内存，多访 1 次内存，速度稍慢。
4. 反置页表：
   不以虚拟页号建表，而是以物理页框号为索引建立页表，一页物理框对应一条表项。能够极大缩减页表大小，页表项数量 = 物理内存页框数，不再和虚拟地址空间挂钩，解决大虚存下单级 / 多级页表臃肿问题。节省主存空间。物理内存远小于虚拟地址空间，页表体量大幅下降。

5.6 分段存储管理方式

5.6.1 分段存储管理方式的引入

为什么要分段？

一方面由于通常的程序都可分为若干段，如主程序段，子程序段，每个段大多是一个相对独立的逻辑单位；另一方面便于段的共享与保护，不同进程可共用同一逻辑段，也能按段设置访问权限，便于动态增长，数据段、堆栈段运行中可按需扩充。

段表

相比页表多了一个段长表示，并且段长并不相同。

5.6.2 分页和分段的区别

1. 页是信息的物理单位，段是信息的逻辑单位，分页是系统的行为，对用户是不可见的，而分段更多是为了满足用户的需要。
2. 页大小固定而页大小不固定：页的大小固定且由系统决定，而段的大小不固定，取决于用户所编写的程序。
3. 分页的用户程序地址空间是一维的：分页的用户程序地址空间是一维的，只需一个地址编号即可寻址；分段地址空间为二维，由段号 + 段内偏移两部分组成。

5.7段页式存储管理方式

5.7.1 基本原理

分段和分页的结合，分段后再把每段分页，段表的内容和分段系统不同，它不再是内存起始地址和段长，而是页表起始地址和页表长度。

5.7.2 地址变换过程

逻辑地址拆分为：段号 + 页号 + 页内偏移，分三次访问内存，第一次凭段号访问段表，得到对应页表起始地址；第二次凭页号访问页表，获取物理块号，物理块号拼接页内偏移，生成最终物理地址；打三次才是真正从所访问地址中取出指令和数据。

第6章 虚拟存储器

6.1 虚拟存储器

6.1.1 常规存储器管理方式

常规存储器管理方式特征

1. 一次性：作业必须一次性装入内存，才能开始运行。
2. 驻留性：作业被装入内存，其中任何部分都不会被换出，直至作业运行结束。

局部性原理

在一段较短的时间内，程序的执行仅局限于某个部分，它所访问的存储空间也局限于某个区域。皮特·邓宁提出了下列论点：

1. 程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况下是顺序执行的。
2. 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域。但经研究发现，过程调用的深度在大多数情况下都不会超过5。
3. 程序中存在许多循环结构，这些结构虽然只由少数指令构成，但是它们将会被多次执行。
4. 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。

局限性又表现在下述两个方面：

1. 时间局限性：如果程序中的某条指令被执行，则不久以后该指令可能会被再次执行；如果某数据被访问过了，则不久以后该数据可能会被再次访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
2. 空间局限性: 一旦程序访问了某个存储单元，不久之后，其附近的存储单元也将会被访问，即程序在一段时间内所访问的地址可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

6.1.2 虚拟存储器定义和特征

基于局部性原理可知：在运行应用程序之前，没有必要将之全部装入内存，而仅须将当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。

1. 虚拟存储器的定义

当用户看到自己的程序能在系统中正常运行时，会认为系统的内存容量比实际大得多，这种用户感受到的虚的、逻辑上的大容量内存，就是虚拟存储器。它是一种具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的存储系统, 逻辑容量 = 内存容量 + 外存容量, 运行速度接近于内存, 每位成本又接近于外存。

2. 虚拟存储器的特征

（1）多次性
多次性是相对于传统存储器管理方式的一次性而言的，是指一个作业中的程序和数据，无须在作业运行时一次性地全部调入内存，而是允许被分成多次调入内存运行，即只须将当前运行的那部分程序和数据装入内存即可开始运行。以后当要运行到尚未调入的那部分程序时，再将它调入即可。
（2）对换性
对换性是相对于传统存储器管理方式的驻留性而言的，是指一个作业中的程序和数据，无须在作业运行时一直常驻内存，而允许它们在作业运行时进行换入、换出；亦即，在进程运行期间，允许将那些暂不使用的代码和数据从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换入）。
（3）虚拟性
虚拟性是指能够从逻辑上扩大内存容量，使用户所看到的内存容量远大于实际内存容量。这样，就可以在小的内存中运行大的作业，或者能提高多道程序度。它不仅能有效改善内存利用率，还能提高程序执行的并发度，从而可以增加系统吞吐量。
虚拟性是以多次性和对换性为基础的，或者说，仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至外存时，才有可能实现虚拟存储器；而多次性和对换性，显然又必须建立在离散分配方式的基础上。

6.1.3 虚拟存储器的实现方法

1. 请求分页系统

请求分页系统将内存划分为固定大小的页框，程序运行时只需载入部分页面，运行过程中访问未载入页面便触发缺页中断，再通过页面置换策略调入对应页面完成地址访问，该方式内存碎片少，地址管理流程简洁，普遍应用于日常程序运行与数据存储场景。

2. 请求分段系统

请求分段系统依据程序逻辑功能划分独立片段，仅把当前运行需要的段加载进内存，访问缺失段落时触发缺段中断并动态分配内存空间，能够便捷实现程序模块共享与访问权限管控，缺点是容易产生外部碎片，多用于模块化程序开发与资源隔离场景。

3. 请求段页式系统

请求段页式系统融合分段与分页的管理优势，先按照逻辑划分程序段，再在每个段内部划分页面，依靠段表与页表两级结构完成地址转换，可同时满足逻辑管理与内存高效利用需求，仅地址转换存在一定开销，适合大型复杂程序与多任务系统使用。

6.2 请求分页存储管理方式

6.2.1 请求分页中的硬件支持

1. 请求页表机制

页表如下：

状态位P：指示该页是否调入内存
访问字段A: 记录本页在一段时间内被访问的次数或者最近一次没被访问的时间，用于后续的页面置换算法。
修改位M：该页在内存中是否被修改过，如果没有被修改过，就无须再将该页写回外存。

2. 缺页中断机构

缺页中断是中断的一种，但又与一般的中断有所不同：
（1）缺页中断是在指令执行期间，产生和处理中断信号，与CPU通常在指令执行完毕后才处理中断不同。
（2）一条指令在执行期间，可能会产生多次缺页中断，比如某条指令本身跨了两个页面。

3. 地址变换机构

CPU收到访页请求后，首先判断页号是否越界，越界则触发越界中断；未越界就查询CPU快表，命中则直接修改页表访问位与修改位、生成物理地址完成地址变换；快表未命中便访问内存页表，若页表显示目标页在内存，更新快表与页表标识后生成物理地址结束流程；若页面不在内存则触发缺页中断，系统先保留CPU现场，从外存查找缺页，判断内存是否已满：未满时直接命令CPU启动I/O将页面调入内存、修改页表；内存已满则选取一页置换，若被换页面已修改，先写回外存再调入新页并更新页表，页面装入内存后重回地址变换流程继续执行。

6.2.2 请求分页中的内存分配

1. 最小物理块数的确定

最小物理块是指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数小于最小物理块数，进程将无法运行。
随着为每个进程分配的物理块数的减少，进程在执行过程中的缺页率会上升。

2. 内存分配策略

（1）固定分配局部置换：为每个进程分配固定的物理块，进程运行期间不再改变。局部置换指进程运行时发生缺页，只能选择进程自己的物理块进行置换。
（2）可变分配全局置换：为每个进程分配一定数目的物理块，在进程运行期间可增减。（如果进程频繁地发生缺页中断，则可增加物理块数。）全局置换指可以将os保留的空闲物理块分配给缺页进程，也可将别的进程持有的物理块置换到外存，再分配给缺页进程。
（3）可变分配局部置换：为每个进程分配一定数目的物理块，在进程运行期间可增减。同样的，进程运行时发生缺页，只能选择进程自己的物理块进行置换。
注：没有固定分配全局置换这种策略。

3. 物理块分配算法

（1）平均分配法：将系统中的可供分配的物理块平均的分给每个进程。
（2）按比例分配法：按照进程大小按比例分配物理块。
（3）考虑优先权的分配算法：为高优先权的进程适当地增加其分配的物理块数。

6.2.3 页面调入策略

1. 何时调入

（1）预调入：运行前调入。
（2）请求调入：运行时调入。

2. 从何处调入

（1）系统拥有足够的对换区空间：从对换区调入全部所需页面。在进程运行前，将进程所有的文件从文件区复制到对换区。
（2）系统缺少足够的对换区空间：从文件区调入不会被修改的文件。
（3）UNIX方式：未运行过的页面从文件区调入，运行过但被换出到对换区的页面，从对换区调入。

3. 页面调入过程

程序访问页面不在内存（存在位为0），触发缺页中断。
先保留CPU现场并判定中断类型，随后查询页表获取缺页外存地址，判断内存空间，空间充足则直接调入页面并更新页表，空间已满便按置换算法选出淘汰页，修改过的页面先写回磁盘，未修改则直接丢弃，再将缺页载入内存，修改页表与快表信息，最后依据页表生成物理地址访问数据。
简易流程：
访问页面不在内存 → 产生缺页中断 → 保护现场 → 中断处理
查询页表获取外存地址，内存空闲：直接调入页面 → 更新页表；内存占满：选定置换页面→页面已修改→写回磁盘→调入新页→更新页表、快表→最终生成物理地址，访问内存数据。

4. 缺页率

（1）计算公式

• 进程逻辑页数：$n$
• 分配内存物理块数：$m(m\le n)$
• 页面访问成功次数：$S$
• 缺页失败次数：$F$

总访问次数：
$$A=S+F$$

缺页率：
$$\mathbf{f}=\frac{\mathbf{F}}{\mathbf{A}}$$

（2）缺页率影响因素
页面大小：页面划分越大，缺页率越低；页面越小，缺页率越高
分配物理块数：分配块数越多，缺页率普遍越低
页面置换算法：算法性能直接决定缺页次数，缺页率是算法核心评判指标
程序局部性：程序局部性越强，缺页次数越少，缺页率越低

（3） 缺页中断平均处理时间

• 页面被修改概率：$\beta$
• 已修改页面中断处理耗时：$t_a$
• 未修改页面中断处理耗时：$t_b$

平均处理时间公式：
$$\mathbf{t}=\mathbf{\beta }\cdot {\mathbf{t}}_{\mathbf{a}}+(1-\mathbf{\beta })\cdot {\mathbf{t}}_{\mathbf{b}}$$

6.3 页面置换算法

6.3.1 最佳页面置换（OPT）算法

将未来最长一段时间内不会被使用的页面换出，因为无法预估未来最长一段时间内哪个页面不会被使用，所以这是一种理论算法，实际无法实现。

6.3.2 先进先出页面置换（FIFO）算法

该算法总是换出最先进入内存的页面。

6.3.3 最近最久未使用页面置换（LRU）算法

该算法赋予每个页面一个访问字段，记录该页面自上次访问以来所经历的时间 t , 选择 t 值最大的页面淘汰。

6.3.4 最少使用页面置换（LFU）算法

在采用最少使用（least frequently used, LFU）页面置换算法时，每次访问某页面时，便将该移位寄存器的最高位置1，再每隔一定时间右移一次，使用最少的页面将是$\sum R_i$最小的页面，换出。

6.3.5 Clock页面置换算法

1. 简单Clock页面置换算法（第二次机会页面置换算法）

为每页设置一个访问位，当某页被访问时，其访问位被置1。选择访问位是0的页面换出，如果访问位是1，则将其置0，给予该页第二次驻留内存的机会，再按照FIFO页面置换算法检查下一个页面。

2. 改进型Clock页面置换算法

为页面设置两个标记位，访问位和修改位。

• 第1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
• 第2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
• 第3类（A=1，M=0）：表示该页最近已被访问，但未被修改，该页有可能再被访问。
• 第4类（A=1，M=1）：表示该页最近已被访问且被修改，该页有可能再被访问。
  执行过程：
  （1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个此类页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
  （2）如果第一步失败，即查找一轮后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，并将所遇到的第一个此类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
  （3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，即寻找A=0且M=0的第一类页面，如果仍失败，则必要时再重复第二步，寻找A=0且M=1的第二类页面，此时一定能找到可被淘汰的页。

6.3.4 页面缓冲算法

在页面置换算法的基础上，增加已修改页面链表（实际是一个空闲物理块链表），每次将已修改的页面的物理块挂到修改页面链表的末尾，达到一定数目后，再一起换出至磁盘，可以极大的减少页面换出开销。

6.3.4 请求分页系统的内存有效访问时间

6.4 抖动 P187

6.4.1 抖动的原因

系统中进程数过多，导致每个进程的物理块不足，频繁缺页、大量时间都花在页面换入换出上，几乎无法做有效工作，CPU利用率暴跌，这就是抖动的核心原因。
解释：
产生“抖动”的根本原因是，同时在系统中运行的进程太多，导致分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时会频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面换入/换出的进程数量增加。显然，对磁盘的有效访问时间也会随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降而趋于0的情况。我们称此时的进程处于“抖动”状态。

抖动导致：

1. CPU利用率低下
2. OS认为需要增加道程序设计的道数
3. 系统中再增加一个进程 → 进一步加剧抖动

6.4.2 工作集

所谓工作集，是指在某段时间间隔Δ中进程实际要访问页面的集合。皮特·邓宁指出，虽然程序只需要少量的几页在内存中便可运行，但为了较少地产生缺页，应使程序的全部工作集装入内存中。然而我们无法事先预知程序在不同时刻将访问哪些页面，故仍只有像页面置换算法那样，将程序在过去某段时间内的行为作为程序在将来某段时间内行为的近似。具体来说，把某进程在时间 t 的工作集记为$w(t,\Delta )$，其中的变量Δ称为工作集的窗口尺寸（windows size）。

工作集$w(t,\Delta )$是二元函数，即在不同时间t的工作集大小不同，所含的页面数也不同，与窗口尺寸Δ有关。工作集大小是窗口尺寸Δ的非降函数（non-decreasing function）。

6.4.3 “抖动”的预防方法

1. 采取局部置换策略

在页面分配和置换策略中，如果采取的是可变分配方式，则为了预防发生“抖动”，可采取局部置换策略。根据这种策略，当某进程发生缺页时，只能在分配给它的内存空间内进行置换，而不允许从其他进程的内存空间中去获得新的物理块。这样，即使该进程发生了“抖动”，也不会对其他进程产生影响，于是可把该进程“抖动”所造成的影响限制在较小的范围内。该方法虽然简单易行，但效果不是很好，因为在某进程发生“抖动”后，它还会长期地处在磁盘I/O的等待队列中，使队列的长度增加，这会延长其他进程缺页中断的处理时间，也就是会延长其他进程对磁盘的访问时间。

2. 把工作集算法融入处理机调度中

当调度程序发现处理机的利用率低下时，它将试图从外存调一个新作业进入内存，以改善处理机的利用率。如果在调度中融入了工作集算法，则在调度程序从外存调入作业之前，必须先检查每个进程在内存中的驻留页面是否足够多。如果都已足够多，则此时便可从外存调入新的作业，而不会因新作业的调入而导致缺页率的增加；如果有些进程的内存页面不足，则应首先为那些缺页率居高的作业增加新的物理块，此时将不再调入新作业。

3. 利用 “L=S” 准则调节缺页率

L是缺页之间的平均时间，S是平均缺页服务时间，即用于置换一个页面所需的时间。如果L远比S大，则说明很少发生缺页，磁盘的能力尚未得到充分利用；如果L比S小，则说明频繁发生缺页，缺页的速度已超过磁盘的处理能力。只有当L与S接近时，磁盘和处理机才可达到它们最大的利用率。理论和实践都已证明，利用“L=S”准则，对于调节缺页率是十分有效的。

4. 选择暂停的进程

基于某种原则选择暂停某些当前活动的进程，将它们调出到磁盘上，以便腾出内存空间并将其分配给缺页率偏高的进程。系统通常会采取与调度程序一致的策略，即首先选择暂停优先级最低的进程，若需要，则再选择暂停优先级较低的进程。当内存还显拥挤时，还可进一步选择暂停一个并不十分重要但却较大的进程（以便释放出较多的物理块）或者剩余执行时间最多的进程等。

6.5 请求分段存储管理方式

在分页基础上建立的请求分页式虚拟存储器系统，是以页面为单位进行换入/换出的。而在分段基础上所建立的请求分段式虚拟存储器系统，则是以分段为单位进行换入/换出的。它们在实现原理以及所需要的硬件支持上都是十分相似的。在请求分段系统，程序运行之前只需要先调入少数几个分段（不必调入所有分段），便可启动运行。当所访问的段不在内存中时，可请求OS将所缺的段调入内存。像请求分页式虚拟存储器系统一样，为实现请求分段存储管理方式，同样需要一定的硬件支持和相应的软件。

6.5.1 请求分段中的硬件支持

为了实现请求分段存储管理，应在系统中配置多种硬件机构，以支持快速完成请求分段功能。与请求分页系统相似，在请求分段系统中所需的硬件支持有：请求段表机制，缺段中断机构，以及地址变换机构。

1. 请求段表机制

在请求分段存储管理中所需的主要数据结构是请求段表。该段表中除了具有请求分页机制中所具有的访问字段A、修改位M、存在位P和外存地址这4个字段外，还增加了存取方式和增补位这2个字段。这些字段供程序在换入/换出时参考。下面所示为请求段表的段表项。

在段表项中，除了段名（号）、段长、段在内存中的起始地址外，还增加了以下字段。
（1）存取方式。由于在应用程序中的段是信息的逻辑单位，可根据该信息的属性对它实施保护，故在段表中增加了存取方式字段。如果该字段为两位，则存取属性可以是只执行、只读或允许读写。
（2）访问字段A。其含义与请求分页的相应字段相同，用于记录该段被访问的频繁程度。其可供页面置换算法在选择换出页面时参考。
（3）修改位M。用于表示该段在进入内存后是否已被修改过，供置换段时参考。
（4）存在位P。用于表示该段是否已调入内存，供程序访问时参考。
（5）增补位。增补位是请求分段存储管理中所特有的字段，用于表示该段在运行过程中是否做过动态增长。
（6）外存地址。用于表示该段在外存中的起始地址，即起始盘块号。

2. 缺段中断机构

在请求分段系统中，采用的是请求调段策略。每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一个缺段中断信号，进入OS后，由缺段中断处理程序将所需的段调入内存。与缺页中断机构类似，缺段中断机构同样需要在一条指令的执行期间产生和处理中断，同时，在一条指令执行期间也可能会产生多次缺段中断。但是，由于分段是信息的逻辑单位，因此不可能出现一条指令被分割在两个分段中以及一组信息被分割在两个分段中的情况。因此对缺段中断的处理要比对缺页中断的处理复杂。