• 本篇文章是在准备 2026 年考研时，对《王道计算机考研 操作系统》的所有笔记进行汇总，方便学习和复习时查看。对于期末考试也可以食用。如果有错误的地方请留言…
• 本篇笔记课程来源：王道计算机考研 操作系统
• 另外也放上单章笔记的传送门：
  • 【操作系统】第一章：操作系统概述
  • 【操作系统】第二章：进程管理（上）
  • 【操作系统】第二章：进程管理（中）
  • 【操作系统】第二章：进程管理（下）
  • 【操作系统】第三章：内存管理
  • 【操作系统】第四章：文件管理
  • 【操作系统】第五章：设备管理（上）
  • 【操作系统】第五章：设备管理（下）
• 其他 408 科目：
  • 《数据结构与算法》笔记汇总（超详细合集）
    

第一章：操作系统概述

一、操作系统的概念

• 操作系统（Operating System，OS）是指控制和管理整个计算机系统 硬件和软件 资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件更加方便的接口和环境 ；它是计算机系统中最基本的系统软件 。
• 概念中所提到的分别是：
  1. 负责管理协调硬件、软件等计算机资源的工作
  2. 为上层用户、应用程序提供简单易用的服务
  3. 是一种系统软件

二、操作系统的功能和目标

功能简记：处（处理机管理）存（存储器管理）备（设备管理）文（文件管理）用（用户接口）

1. 作为系统资源的管理者

• 需要提供的功能有：
  1. 处理机（CPU）管理：例如程序运行的进程
  2. 存储器（存储）管理：例如程序运行时的数据
  3. 文件管理：例如文件存放
  4. 设备管理：例如键盘鼠标摄像头

2. 向上层提供服务

• 可以理解为：操作系统把一些难以理解的硬件功能封装成简单易用的服务，使用户能更方便地使用计算机，用户无需关心底层硬件的原理，只需要对操作系统发出命令即可。
• 提供的功能：
  • 图形化界面（GUI）：用户可以使用形象的图形界面进行操作，而不需要记忆复杂的命令、参数。
  • 用户接口：命令接口、程序接口

接口类型		特点
命令接口	联机命令接口 / 交互式命令接口	说一句做一句，类似于终端命令行
	脱机命令接口 / 批处理命令接口	说一堆做一堆，类似于 .bat 批处理文件
程序接口		可以在程序中进行系统调用来使用程序的接口，类似于函数调用

• 在提供的功能中，GUI 和 命令接口用户可以直接使用；程序接口只能通过程序间接使用。

3. 对硬件的拓展

• 操作系统需要实现对硬件机器的拓展。
• 没有任何软件支持的计算机称为裸机。
• 经过操作系统的包装，裸机便以虚拟机的形式呈现给用户。与裸机相比，虚拟机更易于理解和使用。通常把覆盖了软件的机器称为扩充机器，也称之为虚拟机。

三、操作系统的四个特征

• 四个特征分别是：并发性、共享性、虚拟性、异步性。其中：
  • 并发性和共享性是 最基本的特征，且 互为存在条件
  • 没有并发和共享，就谈不上虚拟和异步

1. 并发性

• 并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。
• 另一个概念——并行：指两个或多个事件在同一时刻同时发生。

---

• 所以操作系统的并发性，是指计算机系统中 “同时” 运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。
• 操作系统就是伴随着 “多道程序技术” 而出现的。因此，操作系统和程序并发是一起诞生的。

---

• 需要注意⚠️⚠️⚠️重要

  • 单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行
  • 多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行

• 如果一个四核CPU需要 “同时” 运行四个以上的程序（核处理不过来），那么并发性依然是必不可少的，因此并发性是操作系统一个最基本的特性。

2. 共享性

• 共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。
• 两种资源共享方式：
  • 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。
  • 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程 “同时” 访问该资源。
• 所谓的 “同时” 往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问（即分时共享）

---

• 并发和共享的关系‼️：互为存在条件。
  • 并发性，指计算机系统中 “同时” 存在着多个运行着的程序。
  • 共享性，指系统中的资源可供内存中多个并发执行的进程共同使用。
  • 如果失去并发性，则系统中只有一个程序正在运行，则共享性失去存在的意义；
  • 如果失去共享性，则多个进程不能同时访问硬盘资源，就无法实现并发。

3. 虚拟性

• 虚拟是指把一个物理上的实体变成若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上对应物是用户感受到的。
• 比如日常使用计算机，一个程序需要放入内存并给它分配CPU才能执行
  • 虚拟存储器技术——空分复用技术：实际只有4GB的内存，在用户看来似乎远远大于4GB
  • 虚拟处理器技术——时分复用技术：实际只有一个单核CPU，在用户看来似乎有多个CPU在同时运行。
  • 上面的有个印象即可，后面会说。
• 如果失去并发性，则一个时间段内系统只需运行一道程序，那么就失去了实现虚拟性的意义。因此，没有并发性，就谈不上虚拟性。

4. 异步性

• 异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限（进程会争取使用系统资源），进程的执行不是一贯到底的，而是走走停停。
• 以不可预知的速度向前推进，就是进程的异步性。
• 如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。因此，只有系统拥有并发性，才有可能导致异步性。

四、操作系统的发展与分类

1. 手工操作阶段

• 主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低。
  • 人机操作和机器速度之间的矛盾
  • CPU和IO设备之间速度不匹配的矛盾

2. 单道批处理系统

• 为了解决人机矛盾和CPU与IO设备之间速度不匹配的矛盾，出现了单道批处理系统。
• 单道批处理系统，引入 脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出。

---

• 主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。
• 主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待 I/O 完成，资源利用率依然很低。

3. 多道批处理系统

• 为了进一步提高计算机系统的利用率，出现了多道程序设计的思想。把批处理系统和多道程序系统相结合，就形成了多道批处理系统。
• 多道程序设计思想：在内存中同时存放若干道用户作业，这些作业交替地运行。

---

• 主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。
• 主要缺点：用户响应时间长，没有人机交互功能（无法调试程序/无法在程序运行过程中输入一些参数）。

4. 分时操作系统

• 在多道批处理系统中，作业运行时用户无法干预，交互能力很弱，由此出现了分时系统。
• 分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。

---

• 主要优点：用户请求可以被及时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。（例如 UNIX）
• 主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

5. 实时操作系统

• 主要特点：及时性、可靠性。
• 主要优点：能够优先响应一些紧急任务，某些紧急任务不需要时间片排队。
• 在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。

分类	特点	案例
硬实时系统	必须在绝对严格的规定时间内完成处理	导弹控制系统、自动驾驶系统
软实时系统	能接受偶尔违反时间规定	12306火车订票系统

6. 其他操作系统

• 网络操作系统（Windows NT）：伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享（如文件共享）和各台计算机之间的通信。
• 分布式操作系统：主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由他们并行、协同完成这个任务。
• 个人计算机操作系统：如 Windows XP、Mac OS，方便个人使用。

五、操作系统的运行机制

• 程序运行的过程实际上是CPU执行一条一条（二进制）机器指令的过程。
• 指令：是处理器（CPU）能识别、执行的最基本命令。

1. 两类程序

• 程序可以分为应用程序和内核程序：
  1. 应用程序：普通程序员写的大多是应用程序
  2. 内核程序：很多内核程序组成了 “操作系统内核”，或简称 ”内核“。内核是操作系统最重要最核心的部分，也是最接近硬件的部分。
• 操作系统的功能未必都在内核中。因此：操作系统 > 内核。

2. 两类指令

• 指令可以分为特权指令和非特权指令：
  1. 特权指令：只允许 “管理者” （内核）使用，影响重大。
  2. 非特权指令：应用程序只能使用非特权指令，如加法指令。
• CPU在设计和生产的时候就划分了特权指令和非特权指令，因此CPU执行一条指令前就能判断出其类型。

3. 两种处理器状态

• CPU有两种状态：内核态和用户态：
  1. 内核态：也称为 核心态、管态。处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
  2. 用户态：也称为目态。处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令。
• CPU中有一个寄存器叫 程序状态字寄存器（PSW），其中有个二进制位，1表示“内核态”，0表示“用户态”

4. 内核态和用户态的切换

• 刚开机时，CPU为 内核态，操作系统内核程序先上CPU运行

1. 内核态转用户态：执行一条特权指令——修改PSW的标志位为用户态，这个动作意味着操作系统将主动让出CPU使用权。
2. 用户态转内核态：由“中断”引发，硬件自动完成变态过程，触发终端信号意味着操作系统将强行夺回CPU的使用权。
   • CPU检测到中断信号后，会立即变为核心态；
   • 停止运行当前的应用程序，转而运行处理终端信号的内核程序；
   • 处理完引发中断的事件后，再把CPU使用权交给别的应用程序。
   • 但凡需要操作系统介入的地方，都会触发终端信号。

六、中断和异常

1. 中断的作用

• 中断是让操作系统内核夺回CPU使用权的唯一途径
• 使CPU从用户态转为内核态
• 如果没有中断机制，那么一旦应用程序上CPU运行，CPU就会一直运行这个应用程序。

2. 中断的类型

1. 内中断：与当前执行的指令有关，中断信号来源于CPU内部

   • 常被称为 异常、例外。

   • 陷入（trap）：应用程序 主动 将CPU控制权还给操作系统内核，会执行陷入指令，该指令会引发一个中断信号。

   • 故障（fault）：由错误条件引起的，可能被内核程序修复。修复后 会归还 CPU使用权。

   • 终止（abort）：由致命错误引起，内核程序无法修复该错误。不会归还 CPU使用权。若当前执行的指令是非法的（用户态执行特权指令、除数为0），则会引发一个中断信号。

   • 检查中断信号：CPU在执行指令时会检查是否有异常发生。

2. 外中断：与当前执行的指令无关，中断信号来源于CPU外部

   • 常被称为 中断（狭义）
   • 时钟中断：实现多道程序并发，时钟部件每隔一个时间片会给CPU发送一个时钟中断信号。
   • I/O中断：当 IO 任务完成时，向CPU发送中断信号。
   • 检查中断信号：每一条指令执行结束后，CPU都会例行检查是否有外中断信号需要处理

3. 中断机制的基本原理

• 不同的中断信号，需要用不同的中断处理程序来处理。
• 当CPU检测到中断信号后，会根据中断信号的类型去查询 中断向量表，以此来找到相应的中断处理程序在内存中的存放位置。
• 中断处理程序一定是内核程序，需要运行在内核态。

七、系统调用

1. 系统调用概念

• 在 2-2 （操作系统的功能——向上层提供服务）中说到：程序接口只能通过程序间接使用。程序就是系统调用。
• 系统调用，是操作系统提供给应用程序（编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务。

2. 系统调用的作用

• 当同一资源被不同进程访问时，进程需要通过系统调用向操作系统内核发出请求。内核会对各个请求进行协调处理
• 系统中的各种共享资源都由操作系统内核统一管理，因此凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。
• 保证系统的稳定性和安全性，防止用户进行非法操作。

---

3. 系统调用和库函数的区别

• 在使用C语言时，会使用一些库函数，例如 math、stdio 中的库函数。

由下向上：

1. 裸机
2. 操作系统：向上提供系统调用，使上层程序能请求内核的服务
3. 编程语言：向上提过库函数。会将系统调用封装成库函数。
4. 普通应用程序：可直接进行系统调用，也可使用库函数。

由此可见，有的库函数设计系统调用，有的不涉及。因此，库函数 > 系统调用。

• 设计系统调用的库函数：创建一个新文件 fopen
• 不涉及系统调用的库函数：取绝对值 abs

4. 系统调用的分类

• 系统调用按功能分类

功能	说明
设备管理	完成 设备 的 请求、释放、启动 等功能
文件管理	完成 文件 的 读写、创建、删除 等功能
进程管理	完成 进程 的 创建、撤销、阻塞、唤醒 等功能
进程通信	完成 进程之间 的 信息传递、信号传递 等功能
内存管理	完成 内存 的 分配、回收 等功能

5. 系统调用的过程

• 过程：
  1. 应用程序调用库函数（封装了系统调用的库函数）
  2. 传递系统调用参数
  3. 执行陷入指令，引发中断信号（用户态）
  4. 操作系统内核处理中断事件，执行相应的请求内核程序处理系统调用（核心态）
  5. 返回应用程序

截图来源于 P7 1.3_3_系统调用 09:52

• 陷入指令，也称之为 trap指令、访管指令。

注意⚠️⚠️

• 陷入指令是在用户态执行的，执行陷入指令后立即引发一个内中断，使CPU进入核心态。
• 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。

八、操作系统体系结构

1. 操作系统的内核

• 内核是操作系统最基本、最核心的部分。实现操作系统内核功能的那些程序就是内核程序。
• 操作系统内核与硬件关联较紧密的模块：时钟管理、中断处理、原语。
• 不直接涉及硬件、更多的是对数据结构的操作：进程管理、存储器管理、设备管理等。

截图来源于 P8 1.4_1_操作系统体系结构（上） 02:11

• 内核设计方法有大内核、微内核等。
• 变态（CPU状态的转换）的过程是有成本的，要消耗不好时间，频繁地转换会降低系统性能。

2. 大内核

• 大内核，也叫宏内核、单内核。
• 大内核将操作系统的主要功能模块（上图中内核所示的两层）都作为系统内核，运行在核心层。
• 优点：高性能；
• 缺点：内核代码庞大、结构混乱、难以维护；
• 常见的大内核操作系统有 Linux、UNIX。

截图来源于 P8 1.4_1_操作系统体系结构（上） 06:18

3. 微内核

• 只把最基本的功能（与硬件关联较紧密的模块）保留在内核。
• 优点：内核功能少、结构清晰、方便维护；
• 缺点：需要频繁地在核心态和用户态之间切换，性能低。
• 常见的微内核操作系统有 Windows NT。

截图来源于 P8 1.4_1_操作系统体系结构（上） 06:18

4. 分层结构

• 最底层是硬件，最高层是用户接口
• 每层只能调用更低一层

截图来源于 P8 1.4_1_操作系统体系结构（下） 01:09

5. 模块化

• 模块化设计方法也称为 模块-接口法。
• 模块化是操作系统按功能划分为若干个具有一定独立性的模块。
• 每个模块具有某方面的管理功能，并规定好各模块之间能通过接口进行通信。
• 还可以进一步将各模块细分为若干个具有一定功能的子模块，同样也规定好各子模块之间的接口。

截图来源于 P8 1.4_1_操作系统体系结构（下） 06:55

6. 外核

• 内核负责进程调度、进程通信等功能；外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全。

截图来源于 P8 1.4_1_操作系统体系结构（下） 14:00

7. 六种体系结构总结

体系结构	特性、思想	优点	缺点
大（宏）内核	所有的系统功能都放在内核里（大内核结构的OS通常也采用了“模块化”的设计思想）	★ 性能高，内核内部各种功能都可以直接相互调用	★ 内核庞大，功能复杂，难以维护
			★ 大内核中某个功能模块出错，就可能导致整个系统崩溃
微内核	只把中断、原语、进程通信等核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态	★ 内核小，功能少，易于维护，内核可靠性高	★ 性能低，需要频繁地切换用户态/核心态。
		★ 内核外的某个功能模块出错不会导致整个系统崩溃	★ 用户态下的各功能不可以直接相互调用，只能通过内核的“消息传递”来间接通信
分层结构	内核分多层，每层可单向调用更低一层提供的接口	★ 便于调试和验证，自底向上逐层调试验证	仅可调用相邻低层，难以合理定义各层的边界
		易扩充和易维护，各层之间调用接口清晰固定	★ 效率低，不可跨层调用，系统调用执行时间长
模块化	★ 将内核划分为多个模块，各模块之间相互协作。 内核=主模块+可加载内核模块 主模块：只负责核心功能，如进程调度、内存管理； 可加载内核模块：可以动态加载新模块到内核，而无需重新编译整个内核	模块间逻辑清晰易于维护，确定模块间接口后即可多模块同时开发	模块间的接口定义未必合理、实用
		★ 支持动态加载新的内核模块（如：安装设备驱动程序、安装新的文件系统模块到内核），增强OS适应性
			模块间相互依赖，更难调试和验证
		★ 任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高
外核	★ 内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全	★ 外核可直接给用户进程分配“不虚拟、不抽象”的硬件资源，使用户进程可以更灵活的使用硬件资源	降低了系统的一致性
		★ 减少了虚拟硬件资源的“映射层”，提升效率	使系统变得更复杂

九、操作系统引导（Boot）

• 操作系统引导：开机的时候，让操作系统在电脑上运行起来。

• 一个磁盘包含：

  1. 主引导记录（MBR）：包含磁盘引导程序、分区表
  2. C、D、E、F等盘

• 一般情况下，C盘是这个磁盘的活动分区，安装了操作系统。C盘包含：

  1. 引导记录（PBR）：负责找到“启动管理器”
  2. 根目录
  3. 其他

• 完整的操作系统初始化程序（即 启动管理器）可在根目录下找到；

  • Windows操作系统完整的开机初始化程序在 “根目录/Windows/Boot” 下

• 操作系统引导步骤：

  1. CPU从一个特定主存地址开始，取指令，执行ROM中的引导程序（先进行硬件自检，在开机）
  2. 将磁盘的第一块（主引导记录）读入内存，执行磁盘引导程序，扫描分区表
  3. 从活动分区（又称主分区，即安装了操作系统的分区）读入分区引导记录，执行其中的程序
  4. 从根目录下找到完整的操作系统初始化程序（即启动管理器）并执行，完成“开机”的一系列动作

十、虚拟机

• 传统的计算机，一台物理机器上只能运行一个操作系统。

• 虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机起（Virtual Machine，VM），每个虚拟机都可以独立运行一个操作系统。

• 同义术语：虚拟机管理程序 / 虚拟机监控程序 / Virtual Machine Monitor / Hypervisor。

• 虚拟机分类：

  1. 直接运行在硬件上
     

  2. 运行在宿主机操作系统上
     

• 两类虚拟机管理程序（VMM）对比

  • Host OS：宿主操作系统；Guest OS：客户操作系统。
  • 支持虚拟化的CPU通常分更多指令等级：Ring 0 表示 0环。

截图来源于 P11 1.6_虚拟机 16:15

对比项	第一类VMM	第二类VMM
对物理资源的控制权	直接运行在硬件之上，能直接控制和分配物理资源	运行在 Host OS 之上，依赖于 Host OS 为期分配物理资源
资源分配方式	在安装 Guest OS 时，VMM 要在原本的硬盘上自行分配存储空间，类似于“外核”的分配方式，分配未经抽象的物理硬件	Guest OS 拥有自己的虚拟硬盘，该盘实际上是 Host OS 文件系统中的一个大文件。Guest OS 分配到的内存是虚拟内存
性能	性能更好	性能更差，需要 Host OS 作为“中介”
可支持的虚拟机数量	更多，不需要和 Host OS 竞争资源，相同的硬件资源可以支持更多的虚拟机	更少，Host OS 本身需要使用物理资源，Host OS 上运行的其他进程也需要物理资源
虚拟机的可迁移性	更差	更好，只需导出虚拟机镜像文件即可迁移到另一台 Host OS 上，商业化应用更广泛
运行模式	运行在最高特权级（Ring 0），可以执行最高特权的指令	部分运行在用户态，部分运行在内核态。Guest OS 发出的系统调用会被 VMM 截获，并转化为 VMM 对 Host OS 的系统调用

第二章：进程管理

一、进程的概念

1. 概念

程序和进程的区别：

• 程序：是静态的，就是个存放在磁盘中的可执行文件，是一系列的指令集合。
• 进程：是动态的，是程序的一次执行过程。
• 同一个程序多次执行会对应多个进程。

在引入进程实体的概念后，可把进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

• 一个进程被调度，就是指操作系统决定让这个进程上CPU运行。

2. 组成

进程是动态的，进程实体（进程映像）是静态的；可以理解为进程实体是进程在动态执行的过程中某一时刻的状态、快照。
一个进程实体（进程映像）由 PCB、程序段、数据段 组成。

• PCB是给操作系统用的；
• 程序段、数据段是给进程自己用的
• 同一个程序执行多次，它们的PCB、数据段各不相同，但程序段的内容是相同的。

---

PCB（Process Control Block）：是一个保存进程信息的数据结构，也是进程存在的唯一标志，即进程控制块。当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB：

• 当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的进程ID（Process ID）PID。
• 操作系统记录基本的进程描述信息，可以让操作系统区分各个进程。记录包括PID、进程所属用户ID（UID）
• 操作系统实现对资源的管理，记录分配的资源（内存、IO设备、文件资源等）
• 操作系统实现对进程的控制和调度，记录进程的运行情况（CPU使用时间、磁盘使用情况、网络流量使用情况等）
• 记录处理机相关信息，如PSW（程序状态字寄存器）、PC（程序计数器）等各种寄存器的值（用于实现进程切换）

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中。

---

程序段：

• 包含程序指令，即程序的代码（指令序列）

---

数据段：

• 包含运行过程中产生的各种数据（如：定义的变量）

3. 特征

程序时静态的，进程是动态的，相比于程序，进程拥有以下特征

特征	说明	备注
动态性	进程是程序的一次执行过程，是动态地产生、变化和消亡的	动态性是进程最基本的特征
并发性	内存中有多个进程实体，各进程可并发执行
独立性	进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性	各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题	异步性会导致并发程序执行结果的不确定性
结构性	每个进程都会配置一个PCB。结构上看，进程由PCB、程序段、数据段组成

二、进程的状态与转换、组织

1. 进程的状态

进程的整个生命周期中，大部分时间都处于运行态、就绪态、阻塞态，因此它们是进程的三种基本状态。

• 单核CPU同一时刻只会有一个进程处于运行态，多个CPU可能有多个进程处于运行态。
• 在PCB中，会有一个变量state来表示进程的当前状态。

状态	表示	说明
创建态 / 新建态	New	进程正在被创建，操作系统为进程分配资源、初始化PCB
就绪态	Ready	（CPU❌其他所需资源✅）已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
运行态	Running	（CPU✅其他所需资源✅）占有CPU，并在CPU上运行
阻塞态 / 等待态	Waiting / Blocked	（CPU❌其他所需资源❌）因等待某一事件而暂时不能运行
终止态 / 结束态	Terminated	进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

1. 创建态

   • 当进程正在被创建时，它的状态是“创建态”。
   • 在这个阶段操作系统会为进程分配资源、初始化PCB。

2. 就绪态

   • 当进程创建完成后，便进入“就绪态”。
   • 处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，暂时不能运行。
   • 系统中可能会有很多个进程处于就绪态。

3. 运行态

   • 当CPU空闲时，操作系统就会选择一个就绪进程，让它上处理机运行。
   • 如果一个进程此时在CPU上运行，那么这个进程处于“运行态”。CPU会执行该进程所对应的程序（执行指令序列）

4. 阻塞态

   • 在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或等待其他进程的响应）。
   • 在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”。

5. 终止态

   • 一个进程可以执行 exit 系统调用，请求操作系统终止该进程，此时进程会进入”终止态“。
   • 操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。

2. 进程状态间的转换

转换	情况
创建态 → 就绪态	系统完成创建进程相关的工作
就绪态 → 运行态	进程被调度
运行态 → 就绪态	时间片到，或CPU被其他高优先级的进程抢占
运行态 → 阻塞态	等待系统资源分配，或等待某事件发生（“系统调用”的方式，主动行为）
阻塞态 → 就绪态	资源分配到位，等待的事件发生（不是进程自身能控制的，被动行为）
运行态 → 终止态	进程运行结束，或运行过程中遇到不可修复的错误

不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态。（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）

截图来源于 P13 2.1_2_进程的状态与转换、进程的组织 09:48

3. 进程的组织

为了对同一状态下的各个进程进行统一的管理，操作系统会将各个进程的PCB组织起来。

组织方式有：链接方式（常用）、索引方式。

1. 链接方式

   • 按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针。
   • 执行指针指向当前处于运行态的进程
   • 就绪队列指针指向当前处于就绪态的进程，通常会吧优先级高的进程放在队头
   • 阻塞队列指针指向当前处于阻塞态的进程。某些操作系统会根据阻塞原因不同，再分为多个阻塞队列。

2. 索引方式

   • 根据进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针。

三、进程控制

1. 概念

• 进程控制的主要功能：对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

• 简化理解：进程控制就是要实现进程状态转换。

2. 如何实现进程控制

• 使用 ”原语“ 实现进程控制
  • 原语：是一种特殊的程序，它的执行具有原子性。即程序执行过程必须一气呵成，期间不允许被中断。
  • 如果不能一气呵成，就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作。
• 使用 ”关中断指令“ 和 ”开中断指令“ 这两个特权指令实现原子性。
  • CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。
  • 关中断、开中断之间的指令序列不可被中断，这就实现了原子性。

3. 进程控制相关的原语

1. 进程的创建：操作系统创建一个进程时使用 创建原语
   • 状态转换：创建态 → 就绪态
   • 过程：
     1. 申请空白PCB
     2. 为新进程分配所需资源
     3. 初始化PCB
     4. 将PCB插入就绪队列
   • 引起进程创建的事件
     1. 用户登录：分时系统中，用户登录成功，系统会为其建立一个新的进程
     2. 作业调度：多道批处理系统中，有新的作业放入内存时，会为其创建一个新的进程
     3. 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
     4. 应用请求：由用户进程主动请求创建一个子进程

---

2. 进程的终止：终止一个进程时使用 撤销原语
   • 状态转换：就绪态 / 阻塞态 / 运行态 → 终止态 → 无
   • 过程：
     1. 从PCB集合中找到终止进程的PCB
     2. 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
     3. 终止其所有子进程：进程间的关系是树形结构
     4. 将该进程拥有的所有资源归还给父进程或操作系统
     5. 删除PCB
   • 引起进程终止的事件：
     1. 正常结束：进程自己请求终止（exit 系统调用）
     2. 异常结束：整数除以0、非法使用特权指令
     3. 外界干预：用户杀掉进程

---

3. 进程的阻塞：阻塞原语 必须和唤醒原语成对使用。
   • 状态转换：运行态 → 阻塞态
   • 过程：
     1. 找到要阻塞的进程对应的PCB
     2. 保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
     3. 将PCB插入相应事件的等待队列
   • 引起进程阻塞的事件
     1. 需要等待系统分配某种资源
     2. 需要等待相互合作的其他进程完成工作

---

4. 进程的唤醒：唤醒原语 必须和阻塞原语成对使用。
   • 状态转换：阻塞态 → 就绪态
   • 过程：
     1. 在事件等待队列中找到PCB
     2. 将PCB从等待队列中移除，设置进程为就绪态
     3. 将PCB插入就绪队列，等待被调度
   • 引起进程唤醒的事件：
     1. 等待的事件发生

---

5. 进程的切换：切换原语
   • 状态转换：运行态 → 阻塞态 / 就绪态、就绪态 → 运行态
   • 过程：
     1. 将运行环境信息存入PCB
     2. PCB移入相应队列
     3. 选择另一个程序执行，并更新其PCB
     4. 根据PCB恢复新进程所需的运行环境
   • 引起进程切换的事件：
     1. 当前进程时间片到
     2. 有更高优先级的进程到达
     3. 当前进程主动阻塞
     4. 当前进程终止

四、进程通信

1. 概念

• 进程间通信（Inter-Process Communication，IPC）：是指两个进程之间产生数据交互。
• 进程通信需要操作系统支持 —— 进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。为了保证安全，一个进程不能直接访问另一个进程的地址空间。
• 进程通信的方式有很多，这里写三个：共享存储、消息传递、管道通信。

2. 共享存储

• 共享存储通过操作系统在内存中开辟共享存储区，进程访问共享存储区实现进程通信。
• 为避免出错，各个进程对共享空间的访问应该是互斥的（只能有一个进程访问共享空间）；各个进程可使用操作系统内核提供的同步互斥工具（如 P、V 操作）。
• 在 Linux 中，实现共享存储：
  1. 通过 shm_open 系统调用，申请一片共享内存区
  2. 通过 mmap 系统调用，将共享内存区映射到自己的地址空间
• 共享存储的方式：基础数据结构的共享、基于存储区的共享
  1. 基于数据结构的共享：比如共享空间内只能放一个长度为 10 的数组。这种共享方式速度慢、限制多，是一种低级通信方式。
  2. 基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度快，灵活性高，是一种高级通信方式。

3. 消息传递

• 消息传递：进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的 “发送消息 / 接收消息” 两个原语进行数据交换。

  • 格式化的消息包括：消息头和消息体，消息头包括发送进程ID、接受进程ID、消息长度等格式化的信息。
  • 发送原语 send、接收原语 receive。

• 消息传递的方式：直接通信方式、间接通信方式

  1. 直接通信方式，消息发送进程要指明接受进程的ID。发送进程使用发送原语后，操作系统内核会将消息挂载（复制）到接收进程的PCB消息队列中，接收进程使用接收原语将消息复制到它的地址空间中。
  2. 间接通信方式，也称 “信箱通信方式”，以 “信箱” 作为中间实体进行间接地通信。可以多个进程往同一个信箱 send 消息，也可以多个进程从同一个信箱中 receive 消息。

4. 管道通信

• “管道” 是一个特殊的共享文件，又名 pipe 文件。其实是在内存中开辟一个大小固定的内存缓冲区（理解为循环队列）。
• 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
• 各进程要互斥地访问管道（由操作系统实现）
• 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
  当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
• 只要管道没空，读进程就可以从管道读数据；
  只要管道美满，写进程就可以往管道写数据。
• 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，不同操作系统有不同的解决方案：
  1. 一个管道允许多个写进程，一个读进程（一般选这个）
  2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据

五、线程

1. 概念

• 有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
• 线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

2. 引入线程的变化

引入线程机制后，带来的变化

1. 传统的进程是程序执行流的最小单位，引入线程后，线程成为了程序执行流的最小单位。
2. 资源分配、调度：
   • 传统进程机制中，进程是资源分配、调度的基本单位
   • 引入线程后，进程是资源分配的基本单位（除CPU之外的系统资源的分配单元），线程是调度的基本单位
3. 并发现：
   • 传统进程机制中，只能进程间并发
   • 引入线程后，各线程间也能并发，提高了并发度
4. 系统开销：
   • 传统的进程间并发，需要切换进程的运行环境，系统开销很大
   • 引入线程后，线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销减小

3. 线程属性

1. 线程是处理机调度的单位，但线程几乎不拥有系统资源，系统资源几乎分配给进程
2. 多核CPU计算机中，各个线程可占用不同的CPU
3. 每个线程都有一个线程ID、线程控制块（TCB）
4. 线程也有就绪、阻塞、运行三种基本状态
5. 同一进程的不同线程间共享进程的资源（IO设备、内存地址空间），由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
6. 同一进程中的线程切换，不会引起进程切换，因此系统开销小；不同进程中的线程切换，会引起线程切换，系统开销大。

4. 线程的实现方式

线程实现方式有两种，分别是用户级线程和内核级线程。用户级线程中的”线程“由线程库实现（操作系统依然只支持进程）。内核级线程由操作系统支持，此时线程才成为处理机分配的单位。

1. 用户级线程（User-Level Thread，ULT）
   • 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
   • 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预
   • 在用户看来，是由多个线程。但是在操作系统内核看来，并意识不到线程的存在。用户级线程就是从用户视角看能看到的线程。
   • 优点： 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
   • 缺点： 当一个用户级线程阻塞后，整个线程都会被阻塞，并发度不高，多个线程不可在多个处理机上并行运行，
2. 内核级线程（Kernel-Level Thread，KLT，又称“内核支持的线程”），大都数现代操作系统都实现了内核级线程，如 Windows，Linux。
   • 内核级线程的管理工作由操作系统内核完成。
   • 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
   • 操作系统会为每个内核级线程建立相应的 TCB（Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程” 就是“从操作系统内核视角看能看到的线程”
   • 优点： 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可在多核处理机上并行执行。
   • 缺点： 一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

5. 多线程模型

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系（引入线程库），可以划分为多种多线程模型。

1. 一对一模型：

   • 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
   • 优点： 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
   • 缺点： 一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
     

2. 多对一模型：

   • 多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程（更像用户级线程）。
   • 优点： 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
   • 缺点： 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
     

3. 多对多模型：

   • n个用户及线程映射到 m 个内核级线程 （n >= m）。每个用户进程对应 m 个内核级线程。
   • 优点： 集二者之所长，克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点；也克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞）
   • 可以理解为：用户级线程是 ”代码逻辑“ 的载体，内核级线程是 ”运行机会“ 的载体。一段 ”代码逻辑“ 只有获得了 ”运行机会“ 才能被执行。
     

6. 线程的状态与转换

• 线程的状态与转换 与 进程的状态与转换 类似。
• 线程的状态只需关注 就绪态、运行态、阻塞态。
  

7. 线程的组织与控制

• 给各个线程建立的数据结构，就是线程控制块（TCB）。每个 TCB 包括

名词	解释
线程标识符	TID，与PID类似
程序计数器PC	线程目前执行到哪里
其他寄存器	线程运行的中间结果
堆栈指针	堆栈保存函数调用信息、局部变量等
线程运行状态	运行 / 阻塞 / 就绪
优先级	线程调度、资源分配的参考

其中 程序计数器、其他寄存器、堆栈指针 是线程切换时要保存 / 恢复的数据。

• 按照需求，多个线程的 TCB 可组织成一张线程表（Thread Table）
• 线程的控制，就是让线程在各个状态间切换。与进程类似。

六、处理机调度

1. 概念

• 当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。
• 调度：以某种规则来决定处理这些任务的顺序。

2. 层次

调度分为三个层次：高级调度、中级调度、低级调度。

层次	要做什么	调度发生在	发生频率	对进程状态的影响
高级调度 (作业调度)	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存→内存 (面向作业)	最低	无→创建态→就绪态
中级调度 (内存调度)	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存→内存 (面向进程)	中等	挂起态→就绪态 (阻塞挂起→阻塞态)
低级调度 (进程调度)	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存→CPU	最高	就绪态→运行态

1. 高级调度（作业调度）

   • 作业：指一个具体的任务。
     用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序（来处理一个具体的任务）
   • 高级调度：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。（好几个程序需要启动，到底先启动哪个）
   • 每个作业之调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB。

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

   • 内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态，被挂起的进程 PCB 会被组织成 挂起队列。
   • 中级调度：按照某种策略决定将哪个处于挂起状态的进程重新调度内存。
   • 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

3. 低级调度（进程调度 / 处理机调度）

   • 低级调度：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
   • 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
   • 进程调度的频率很高，一般几十毫秒一次。

3. 补充：进程的挂起态与七状态模型

• 暂时调到外存等待的进程状态为 挂起状态（挂起态，suspend）
• 挂起态又可以进一步细分为 就绪挂起、阻塞挂起 两种状态。
• 挂起和阻塞的区别：两种状态都是暂时不能获得 CPU 的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

七、进程调度的时机与方式

1. 进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

• 需要进行进程调度与切换的情况：
  1. 当前运行的程序主动放弃处理机：
     包括：进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞（如 等待 I/O）
  2. 当前运行的程序被动放弃处理机：
     包括：分给进程的时间片用完、有更紧急的事需要处理（如 I/O 中断）、有更高优先级的进程进入就绪队列
• 不能进行进程调度与切换的情况：
  1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
  2. 进程在操作系统内核程序临界区中。
     临界资源：指一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
  3. 在原子操作过程中（原语）。原子操作不可中断，要一气呵成。

2. 进程调度的方式

分为非剥夺调度方式和剥夺调度方式：

1. 非剥夺调度方式，又称非抢占方式。只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
   • 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
2. 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
   • 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。

八、进程的切换与过程

• 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
• 进程调度分为狭义和广义：
  • 狭义的进程调度指从就绪队列中选中一个要运行的进程。
  • 广义的进程调度包含了狭义的进程调度和进程切换。
• 进程切换的过程：
  1. 对原来运行进程各种数据的保存（保存到PCB）
  2. 对新的进程各种数据的恢复
• 重要结论：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在进程切换上，而真正用于执行进程的时间减少。

九、调度器和闲逛进程

1. 调度器

• 调度器，也叫调度程序（scheduler），调度程序决定：
  • 让谁运行？—— 调度算法
  • 运行多长时间？—— 时间片大小
  • 调度时机 —— 什么事件会触发 ”调度程序”
    1. 创建新进程
    2. 进程退出
    3. 运行进程阻塞
    4. IO中断发生（可能唤醒某些阻塞进程）
• 不同策略触发调度器
  • 非抢占式调度策略中，只有运行进程阻塞或退出才触发调度程序工作
  • 抢占式调度策略中，每个时钟中断或 k 个时钟中断会触发调度程序工作
• 不支持内核级线程的操作系统，调度程序的处理对象是进程；支持内核级线程的操作系统，调度程序的处理对象是线程。

2. 闲逛进程

• 没有其他就绪进程时，调度程序会运行闲逛进程（idle）
• 闲逛进程的特性：
  • 优先级最低
  • 可以是 0 地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
  • 能耗低

十、调度算法的评价指标

1. CPU利用率

• CPU利用率：指CPU“忙碌”的时间占总时间的比例。
• 计算：$$利用率=\frac{忙碌的时间}{总时间}$$

2. 系统吞吐量

• 系统吞吐量：单位时间内完成作业的数量。
• 计算：$$系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间}$$

3. 周转时间

• 周转时间：指从作业提交给系统开始，到作业完成为止的这段时间间隔。周转时间越小越好。
• 周转时间内包括四个部分
  1. 作业在外存后备队列上等待作业调度（高级调度）的时间
  2. 进程在就绪队列上等待进程调度（低级调度）的时间
  3. 进程在CPU上执行的时间
  4. 进程等待 IO 操作完成（阻塞）的时间
• 作业周转时间：$$周转时间=作业完成时间-作业提交时间$$
• 平均周转时间：$$平均周转时间=\frac{各作业周转时间之和}{作业数}$$
• 带权周转时间：$$带权周转时间=\frac{作业周转时间}{作业实际运行的时间}=\frac{作业完成时间-作业提交时间}{作业实际运行的实际}$$
• 平均带权周转时间：$$平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$$
• 对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被被服务的时间更多，带权周转时间更小，用户满意度更高。
• 对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。

4. 等待时间

• 等待时间：指进程 / 作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
• 进程和作业的等待时间计算不同：
  1. 对于进程来说：等待时间就是指进程建立后等待被服务的时间之和，在等待 IO 完成的期间其实进程也是被服务的，所以不计入等待时间。
  2. 对于作业来说：不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

5. 响应时间

• 响应时间：指从用户提交请求到首次产生相应所用的时间。

十一、调度算法

适用于早期的批处理系统，不区分任务的紧急程度，交互性差：FCFS、SJF（SPF）、HRRN。

适用于交互式系统：RR、优先级调度、多级反馈队列。

1. 先来先服务（FCFS）

• 先来先服务（FCFS，First Come First Serve）。在每次调度时选择一个等待时间最长的作业（进程）为其服务。

  	说明
  算法思想	主要从“公平”的角度考虑
  算法规则	按照作业 / 进程到达的先后顺序进行服务
  用于作业/进程调度	用于作业调度时，考虑的是哪个作业先到达后备队列
  	用于进程调度时，考虑的是哪个进程先到达就绪队列
  是否可抢占	非抢占式
  优缺点	优点：公平、算法实现简单
  	缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。 即：FCFS算法对长作业有利，对短作业不利
  是否会导致饥饿	不会

2. 短作业优先（SJF）

• 短作业优先（SJF，Shortest Job First）。选择一个执行时间最短的作业为其服务。

	说明
算法思想	追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
算法规则	服务时间最短的作业 / 进程优先得到服务
用于作业/进程调度	用于作业调度时，为“短作业优先算法”（SJF, Shortest Job First）
	用于进程调度时，为“短进程优先算法”（SPF, Shortest Process First）
是否可抢占	非抢占式算法：SJF、SPF
	抢占式算法：最短剩余时间优先算法（SRTN, Shortest Remaining Time Next)
优缺点	优点：（不严谨）“最短的”平均等待时间、平均周转时间
	缺点：不公平。对短作业有利，对长作业不利。
是否会导致饥饿	会。长作业/进程可能产生饥饿或饿死。

• 最短剩余时间优先的平均等待时间、平均周转时间最少。

• 在所有进程同时可运行时，或所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少

3. 最高响应比优先（HRRN）

• 高响应比优先（HRRN，Highest Response Ratio Next）。在每次调度时选择一个响应比最高的作业（进程）为其服务。
• 响应比计算方式：$$响应比=\frac{等待时间+要求服务时间}{要求服务时间}$$

	说明
算法思想	综合考虑作业 / 进程的等待时间和要求服务的时间
算法规则	在每次调度时先计算各个作业 / 进程的响应比，选择响应比最高的作业 / 进程为其服务
用于作业/进程调度	既可用于作业调度，也可用于进程调度
是否可抢占	非抢占式。只有调度时才需要计算响应比
优缺点	综合考虑了等待时间和运行时间（要求服务时间）
	等待时间相同时，要求服务时间段的优先（SJF的优点）
	要求服务时间相同时，等待时间长的优先（FCFS的优点）
	对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
是否会导致饥饿	不会

4. 时间片轮转（RR）

• 时间片轮转（RR, Round-Robin）
• 时间片不能太大，也不能太小
  • 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为FCFS调度算法，并且会增大进程响应时间。
  • 如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减小。

	说明
算法思想	公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则	按照各进程到达就绪队列的顺序，轮流为各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度	用于进程调度（只有作业放入内存建立相应的进程后，才能被分配处理机时间片）
是否可抢占	抢占式。由时钟装置发出时钟中断来通知CPU时间片已到
优缺点	优点：公平；响应快，适用于分时操作系统
	缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
是否会导致饥饿	不会

5. 优先级调度

• 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
  • 静态优先级：创建进程时确定，之后一直不变
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
• 如何合理地设置各类进程的优先级：
  • 系统进程优先级高于用户进程
  • 前台进程优先级高于后台进程
  • 操作系统更偏好 IO 型（ IO 繁忙型）进程。与 IO 型进程相对的是计算型进程（CPU繁忙型进程）
• 如果采用动态优先级，什么时候应该调整：
  • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
  • 如果某进程占用处理机运行了很长时间，则可以适当降低其优先级
  • 如果发现一个进程频繁地进行IO操作，则可适当提升其优先级

	说明
算法思想	需要根据任务的紧急程度来决定处理顺序
算法规则	调度时选择优先级最高的作业 / 进程
用于作业/进程调度	既可用于作业调度，也可用于进程调度。还可用于 IO 调度
是否可抢占	非抢占式只需在进程主动放弃处理机时进行调度即可
	抢占式还需在就绪队列变化时，检查是否会发生抢占
优缺点	优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业 / 进程的偏好程度。
	缺点：若源源不断地由高优先级进程到来，则可能导致饥饿。
是否会导致饥饿	会

6. 多级反馈队列

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

7. 多级队列调度

• 系统中按进程类型设置多个队列（如系统进程队列、交互式队列、批处理队列），各个队列优先级不相同，进程创建成功后插入某个队列。
• 队列之间可采取固定优先级，或时间片划分
  • 固定优先级：高优先级空时低优先级进程才能被调度
  • 时间片划分：如三个队列分配时间 50%、40%、40%
• 各队列可采用不同的调度策略（如系统进程队列采用优先级调度、交互式队列采用RR、批处理队列采用 FCFS）

十二、进程同步和互斥

1. 进程同步

• 进程具有异步性的特征。各并发执行的进程以各自独立的、不可预知的速度向前推进。
• 同步又称直接制约关系，指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2. 进程互斥

• 临界资源：一个时间段内只允许一个进程使用的资源（比如摄像头、打印机）。对临界资源的访问，必须互斥地进行。
• 进程互斥：指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源。
• 对临界资源的互斥访问，逻辑上分为四个部分：
  1. 进入区：负责检查是否可进入临界区，若可进入，则应设置 正在访问临界资源的标志（上锁），以防止其他进程同时进入临界区
  2. 临界区：也称为临界段，负责访问临界资源
  3. 退出区：负责解除 正在访问临界资源的标志（解锁）
  4. 剩余区：做其他处理

• 为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
  1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
  2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
  3. 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）。
  4. 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

十三、进程互斥的软件实现方法

1. 单标志法

• 算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

int turn = 0;

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

• 该算法可以实现 “同一时刻最多只允许一个进程访问临界区”
• 但是违背 “空闲让进” 原则

2. 双标志先检查

• 算法思想：设置一个布尔值数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿（比如flag[0]=true意味着0号进程P0现在想进入临界区）
• 每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对于的标志 flag[i]设为true，之后开始访问临界区。

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

// P0进程                   // P1进程
while (flag[1]);           while (flag[0]);      // 进入区 —— 检查
flag[0] = true;            flag[1] = true;       // 进入区 —— 上锁
critical section;          critical section;     // 临界区
flag[0] = false;           flag[1] = false;      // 退出区
remainder section;         remainder section;    // 剩余区

• 该算法在进入区的检查和上锁两个处理不是一气呵成的。检查后，上锁前可能发生进程切换。因此，违反 “忙则等待” 原则。

3. 双标志后检查

• 算法思想：是双标志先检查的改版。
  • 双标志先检查是 先检查后上锁
  • 双标志后检查是 先上锁后检查

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

// P0进程                   // P1进程
flag[0] = true;            flag[1] = true;       // 进入区 —— 上锁
while (flag[1]);           while (flag[0]);      // 进入区 —— 检查
critical section;          critical section;     // 临界区
flag[0] = false;           flag[1] = false;      // 退出区
remainder section;         remainder section;    // 剩余区

• 该算法虽然解决了 “忙则等待” 的问题，但是违背了 “空闲让进” 和 “有限等待” 原则，会因各进程都长期无法访问临界资源而产生 “饥饿” 现象。

4. Peterson算法

• 算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。

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

// P0进程                        // P1进程
flag[0] = true;                 flag[1] = true;                  // 进入区 —— 主动争取
turn = 1;                       turn = 0;                        // 进入区 —— 主动谦让
while (flag[1] && turn == 1);   while (flag[0] && turn == 0);    // 进入区 —— 检查
critical section;               critical section;                // 临界区
flag[0] = false;                flag[1] = false;                 // 退出区
remainder section;              remainder section;               // 剩余区

• Peterson 算法遵循了空闲让进、忙则等待、有限等待三个原则，但是依然违背了让权等待的原则。

十四、进程互斥的硬件实现方法

1. 中断屏蔽方法

• 利用 “开/ 关中断指令” 实现。与原语实现思想相同。
• 优点：简单、高效。
• 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程。

2. TestAndSet（TS指令 / TSL指令）

• TestAndSet 指令，也可称为 TestAndSetLock 指令，简称 TS 指令或 TSL 指令。
• TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
• 优点：实现简单，无需严格检查是否会有逻辑漏洞；适用于多处理机环境；
• 缺点：不满足让权等待原则。

3. Swap指令（XCHG指令）

• Swap 指令，也称为 Exchange 指令，简称 XCHG 指令。
• Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
• 优点和缺点同 TSL 指令。

4. 互斥锁

• 互斥锁（mutex lock）；需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock）。
• 每个互斥锁有一个布尔变量 available，表示锁是否可用。
• 函数 acquire 获得锁，release 释放锁。都必须是原子操作，所以互斥锁通常采用硬件机制实现。

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

• 优点：等待期间不用切换进程上下文，多处理机系统中，若上锁时间短，则等待代价很低；因此常用于多处理机系统。
• 缺点：违反让权等待，不适用于单处理机系统。

十五、信号量机制

1. 信号量

• 信号量：是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量。（比如：系统中只有一台打印机，就可以设置一个初值为1的信号量）
• 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而实现进程互斥、进程同步。
  • 一对原语：wait(S) 原语和 signal(S) 原语，函数调用时传入参数信号量S；
  • wait、signal 原语常简称为 P、V 操作（荷兰语 proberen 和 verhogen）。因此也可以写为 P(S)、V(S)

2. 整型信号量

• 整形信号量：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

int S = 1;               // 初始化整形信号量S，表示当前系统中可用的资源数

void wait(int S) {　　　　//　wait 原语，相当于 进入区
	while (S <= 0);      // 如果资源数不够，就一直循环等待
	S = S - 1;           // 如果资源数够，则占用一个资源
}

void signal(int S) {     // signal 原语，相当于 退出区
	S = S + 1;           // 使用完资源后，在退出区释放资源
}

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

• 存在的问题：不满足让权等待原则。

3. 记录型信号量‼️ ⚠️

• 记录型信号量：用记录型数据结构表示的信号量。

typedef struct {
	int value;            // 剩余资源数
	struct process *L;    // 等待队列
} semaphore;

void wait(semaphore S) {
	S.value--;
	if (S.value < 0) {
		// 如果剩余资源数不够，使用 block 原语使进程从运行态进入阻塞态
		// 并把进程挂到信号量 S 的等待（阻塞）队列中
		block(S.L);
	}
}

void signal(semaphore S) {
	s.value++;
	if (S.value <= 0) {
		// 释放资源后，若还有别的进程在等待这种资源，则使用 wakeup 原语
		// 唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
		wakeup(S.L);	
	}
}

• 该机制遵循了让权等待原则。
• 对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，当该类资源已分配完毕，进程应调用 block 原语进行自我阻塞。
• 对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，若释放后依然有进程在等待该类资源，应调用 wakeup 原语唤醒等待队列中的第一个进程。

4. 信号量机制实现进程互斥

• 步骤
  1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
  2. 设置互斥信号了 mutex，初值为 1
  3. 在进入区 P(mutex) —— 申请资源
  4. 在退出区 V(mutex) —— 释放资源
• 注意：
  • 在不同的临界资源需要设置不同的互斥信号量；
  • P、V 操作必须成对出现。

semaphore mutex = 1;   // 初始化信号量

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

5. 信号量机制实现进程同步

• 进程同步：要让各并发进程按要求有序地推进。
• 步骤：
  1. 分析什么地方需要实现 “同步关系”，即必须保证 “一前一后” 执行的两个操作
  2. 设置同步信号量 S，初始为 0
  3. 在 “前操作” 之后执行 V(S) —— 前 V
  4. 在 “后操作” 之前执行 P(S) —— 后 P
• 信号量 S 代表 “某种资源”，刚开始是没有这种资源的。P2 需要使用这种资源，只能由 P1 产生这种资源。

semaphore S = 0;  // 初始化同步信号量，初始值为 0

P1() {
	...
	V(S);
	...
}
P2() {
	...
	P(S);
	...
}

6. 信号量机制实现进程的前驱关系

• 步骤：
  1. 要为每一对前驱关系各设置一个同步信号量
  2. 在 “前操作” 之后对相应的同步信号量执行 V 操作
  3. 在 “后操作” 之前对相应的同步信号量执行 P 操作
• 本质上是多级同步问题。

十六、进程同步 / 互斥问题

1. PV操作题目解题思路

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

2. 生产者消费者问题

• 问题描述：
  1. 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品并使用。
  2. 生产者、消费者共享一个初始为空、大小为 n 的缓冲区。
  3. 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
  4. 只有缓冲区不空时，消费者才能从缓冲区取出产品，否则必须等待。
  5. 缓冲区是临界资源，各进程必须互斥地访问。
• 解决问题：

  semaphore mutex = 1;       // 互斥信号量，实现对缓冲区的互斥访问
  semaphore empty = n;       // 同步信号量，表示空闲缓冲区的数量
  semaphore full = 0;        // 同步信号量，表示产品的数量，也即非空缓冲区的数量
  
  produce() {
  	while (1) {
  		生产一个产品;
  		P(empty);          // 消耗一个空闲缓冲区
  		P(mutex);          // 互斥 上锁
  		把产品放入缓冲区;
  		V(mutex);          // 互斥 解锁
  		V(full);	       // 增加一个产品
  	}
  }
  
  consumer() {
  	while (1) {
  		P(full);            // 消耗一个产品（非空缓冲区）
  		P(mutex);
  		从缓冲区取出一个产品;
  		V(mutex);
  		V(empty);           // 增加一个空闲缓冲区
  		使用产品;	
  	}
  }
  

• 实现互斥是在同一进程中进行一对 PV 操作
• 实现同步是在两个进程中分别进行 PV 操作
• 注意：
  • 实现互斥的 P 操作一定要在实现同步的 P 操作之后 ，否则会发生死锁。
  • V 操作不会导致进程阻塞，因此两个 V 操作顺序可以互换。

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

• 问题描述：
  1. 桌子上有一个盘子，每次只能向其中放入一个水果。
  2. 爸爸专向盘子中放苹果，妈妈专向盘子中放橘子；儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。
  3. 只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
• 解决问题：

  semaphore mutex = 1;      // 实现互斥访问
  semaphore apple = 0;      // 盘子中有多少个苹果
  semaphore orange = 0;     // 盘子中有多少个橘子
  semaphore plate = 1;      // 盘子中还可以放多少个水果
  
  dad() {
  	while (1) {
  		准备一个苹果;
  		P(plate);
  		P(mutex);
  		把苹果放入盘子;
  		P(mutex);
  		V(apple);
  	}
  }
  
  mom() {
  	while (1) {
  		准备一个橘子;
  		P(plate);
  		P(mutex);
  		把橘子放入盘子;
  		P(mutex);
  		V(orange);
  	}
  }
  
  daughter() {
  	while (1) {
  		P(apple);
  		P(mutex);
  		从盘中取走苹果;
  		V(mutex);
  		V(plate);
  		吃掉苹果;
  	}
  }
  
  son() {
  	while (1) {
  		P(orange);
  		P(mutex);
  		从盘中取走橘子;
  		V(mutex);
  		V(plate);
  		吃掉橘子;
  	}
  }
  

• 在该问题中，如果缓冲区大小为 1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。

4. 吸烟者问题

• 问题描述：
  1. 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。
  2. 三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。
  3. 供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料在桌上
  4. 这个过程一直重复，让三个抽烟者进程轮流地抽烟。
• 解决问题：

  semaphore offer1 = 0;        // 桌上组合一的数量
  semaphore offer2 = 0;        // 桌上组合二的数量
  semaphore offer3 = 0;        // 桌上组合三的数量
  semaphore finish = 0;        // 抽烟是否完成
  int i = 0;                   // 用于实现三个抽烟者轮流抽烟
  
  provider() {
  	while (1) {
  		if (i == 0) {
  			将组合一放桌上;
  			V(offer1);		
  		} else if (i == 1) {
  			将组合二放桌上;
  			V(offer2);
  		} else if (i == 2) {
  			将组合三放桌上;
  			V(offer3);
  		}
  		i = (i + 1) % 3;
  		P(finish);
  	}
  }
  
  smoker1() {
  	while (1) {
  		P(offer1);
  		从桌上拿走组合一；卷烟；抽掉；
  		V(finish);	
  	}
  }
  
  smoker2() {
  	while (1) {
  		P(offer2);
  		从桌上拿走组合二；卷烟；抽掉；
  		V(finish);	
  	}
  }
  
  smoker3() {
  	while (1) {
  		P(offer3);
  		从桌上拿走组合三；卷烟；抽掉；
  		V(finish);	
  	}
  }
  

5. 读者写者问题

• 问题描述：
  1. 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。
  2. 允许多个读者可以同时对文件执行读操作
  3. 只允许一个写者往文件中写信息
  4. 任一写者在完成写操作之前不允许其他读者或写者工作
  5. 写者执行写操作前，应让已有的读者和写者全部退出
• 解决问题

  semaphore rw = 1;           // 用于实现对共享文件的互斥访问
  int count = 0;              // 记录当前有几个读进程在访问文件
  semaphore mutex = 1;        // 用于保证对 count 变量的互斥访问
  semaphore w = 1;            // 用于实现读写公平
  
  writer() {
  	while (1) {
  		P(w);               // 防止源源不断的读进程
  		P(rw);              // 写之前 “加锁”
  		写文件;
  		V(rw);              // 写完了 “解锁”
  		V(w);	
  	}
  }
  
  reader() {
  	while (1) {
  		P(w);               // 如果正在读，则不允许再有写进程
  		P(mutex);           // 各读进程互斥访问 count，对 count 变量的检查和赋值一气呵成
  		if (count == 0) {   // 由第一个读进程负责
  			P(rw);	        // 读之前 “加锁”
  		}
  		count++;            // 访问文件的读进程数 + 1
  		V(mutex);
  		V(w);
  		读文件;
  		P(mutex);
  		count--;            // 访问文件的读进程数 - 1
  		if (count == 0) {   // 由最后一个读进程负责
  			V(rw);	        // 读完了 “解锁”
  		}
  		V(mutex);
  	}
  }
  

• 在这种算法中，采用了相对公平的 FCFS 原则，也可以称为 “读写公平法”。
• 核心思想在于设置了一个计数器 count 用来记录当前访问共享文件的读进程数。可以用 count 的值来判断当前进入的进程是否是第一个 (加锁) / 最后一个 (解锁) 读进程，从而做出不同的处理。

6. 哲学家进餐问题

• 问题描述：
  1. 一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家们思考，并不影响他人。
  2. 只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。
  3. 如果筷子已在他人手上，则需等待。
  4. 饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
• 解决方法：
  1. 最多允许四个哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
  2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子；偶数号哲学家刚好相反。
  3. 仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子。

十七、管程

1. 管程的引入

• 管程是一种高级同步机制，在程序设计语言 Pascal 中首次引入。
• 为解决信号量机制存在的编写程序困难、易出错问题，管程机制让程序呀在写程序时不需要再关注复杂的 PV 操作。

2. 管程的定义

• 管程是一种特殊的软件模块，由以下部分组成：
  1. 局部于管程的共享数据结构说明；
  2. 对该数据结构进行操作的一组过程；
  3. 对局部于管程的共享数据设置初始值的语句；
  4. 管程有一个名字。
• 管程类似于类；过程类似于函数或方法。

3. 管程的基本特征

1. 局部于管程的数据只能被局部于管程的过程所访问；
   • 需要在管程中定义共享数据
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
   • 需要在管程中定义用于访问共享数据的 “入口” —— 过程（函数）
   • 只有通过这些特定的入口才能访问共享数据
   • 管程的互斥特性是由编译器负责实现的
3. 每次仅允许一个进程在管程内执行某个内部过程
   • 管程有很多入口，但每次只能开放其中一个入口，并且只能让一个进程或线程进入
   • 可以管程中设置条件变量和等待 / 唤醒操作，以解决同步问题。

4. 管程解决生产者消费者问题

伪代码：

monitor ProducerConsumer
	condition full, empty;          // 条件变量用来实现同步（排队）
	int count = 0;                  // 缓冲区中的产品数
	
	void insert(Item item) {。      // 把产品 item 放入缓冲区
		if (count == N)
			wait(full);
		count++;
		insert_item(item);
		if (count == 1)
			signal(empty);	
	}

	Item remove() {                 // 从缓冲区中取出一个产品
		if (count == 0)
			wait(empty);
		count--;
		if (count == N - 1)
			signal(full);
		return remove_item();	
	}
end monitor;

调用：

// 生产者进程
producer() {
	while (1) {
		item = 生产一个产品；
		ProducerConsumer.insert(item);	
	}
}
// 消费者进程
consumer() {
	while (1) {
		item = ProducerConsumer.remove();
		消费产品item;
	}
}

十八、死锁

1. 死锁的概念

• 什么是死锁？
  • 在并发环境下，各进程因竞争资源而造成的一种 互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进 的现象，就是 “死锁”。
  • 发生死锁后，若无外力干涉，这些进程都将无法向前推进。

---

• 死锁、饥饿、死循环的区别
  • 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。至少有两个或两个以上的进程同时发生死锁。
  • 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。可能只有一个进程发生饥饿。
  • 死循环：某进程执行过程中一直跳不出某个循环的现象。可能只有一个进程发生死循环。死锁和饥饿时管理者（操作系统）的问题，死循环是被管理者的问题。

---

• 产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生：
  1. 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。
  2. 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
  3. 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  4. 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
• 注意：发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）

---

• 什么时候会发生死锁：
  1. 对系统资源的竞争。各进程对不可剥夺的资源的竞争可能引起死锁，对可剥夺的资源的竞争是不会引起死锁的。
  2. 进程推进顺序非法。
  3. 循环等待条件信号量的使用不当也会造成死锁。
• 总是：对不可剥夺资源的不合理分配，可能导致死锁。

---

• 死锁的处理策略：
  1. 预防死锁：破坏死锁产生的四个必要条件中的一个或几个。
  2. 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）。
  3. 死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

2. 死锁的处理策略 —— 预防死锁

1. 破坏互斥条件：
   • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。
   • 破坏：如果把只能互斥使用的资源改造成允许共享使用，则系统不会进入死锁状态。（比如：SPOOLing 技术。操作系统可以采用 SPOOLing 技术吧独占设备在逻辑上改造成共享设备）
   • 缺点： 并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候无法破坏互斥条件。

---

2. 破坏不剥夺条件：
   • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
   • 破坏：
     1. 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。
     2. 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级。
   • 缺点：
     1. 实现起来比较复杂
     2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU。
     3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
     4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

---

3. 破坏请求和保持条件：
   • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
   • 破坏：采用静态分配方法。即进程在运行前一次申请完它所需要的全部资源，在它的资源为满足之前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源。
   • 缺点：有些进程可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。且该策略也有可能导致某些进程饥饿。

---

4. 破坏循环等待条件：
   • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
   • 破坏：采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
     • 原理：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
   • 缺点：
     1. 不方便增加新的设备，因为可能需要重新分配所有的编号
     2. 进程实际使用的资源的顺序可能和编号递增顺序不一致，会导致资源浪费
     3. 必须按规定次序申请资源，用户编程麻烦

3. 死锁的处理策略 —— 避免死锁

• 安全序列：指如果系统按照这种序列分配资源，则每个进程都能顺利完成。
• 安全序列、不安全状态、死锁的联系：
  • 只要能找出一个安全序列，系统就是安全状态。安全序列可能有多个。
  • 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可鞥所有进程都无法顺利的执行下去。
  • 如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过在分配资源之前总要考虑到最坏的情况。
  • 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁。（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）
• 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是 “银行家算法” 的核心思想。

---

• 银行家算法：在进程提出资源请求时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
• 银行家算法数据结构：
  1. 长度为 m 的一位数组 Available 表示还有多少可用资源
  2. n * m 矩阵 Max 表示各进程对资源的最大需求数
  3. n * m 矩阵 Allocation 表示已经给各进程分配了多少资源
  4. Max - Allocation = Need 矩阵表示各进程最多还需要多少资源
  5. 用长度为 m 的一位数组 Request 表示进程此次申请的各种资源数
• 银行家算法步骤：
  1. 检查此次申请是否超过了之前声明的最大需求数；否则认为出错
     $$Reques{t}_i[j]\le Need[i,j]（0\le j\le m）$$
  2. 检查此时系统剩余的可用资源是否还能满足这次请求；否则尚无足够资源，进程 $P_i$ 必须等待
     $$Reques{t}_i[j]\le Available[j]（0\le j\le m）$$
  3. 试探着分配，更改各数据结构
     $$\begin{array}{rl}& Available=Available-Request;\\ & Allocation[i,j]=Allocation[i,j]-Reques{t}_i[j];\\ & Need[i,j]=Need[i,j]-Reques{t}_i]j];\end{array}$$
  4. 用安全性算法检查此次分配是否会导致系统进入不安全状态
     
     
• 安全性算法步骤：
  1. 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
  2. 不断重复步骤一，看最终是否能让所有进程都加入安全序列。

4. 死锁的处理策略 —— 检测和解除

• 死锁检测算法数据结构，保存资源的请求和分配信息（资源分配图）：
  • 两种结点：
    1. 进程结点：对应一个进程
    2. 资源结点：对应一类资源，一类资源可能有多个
  • 两种边：
    1. 请求边（进程结点 → 资源结点）：表示进程想申请几个资源（每条边代表一个）
    2. 分配边（资源结点 → 进程结点）：表示已经为进程分配了几个资源（每条边代表一个）
       
• 死锁检测算法（依次消除与不阻塞进程相连的边，直到无边可消）：
  1. 在资源分配图中，找出既不阻塞又不是孤点的进程 $P_i$ （即一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量），消去它所有的请求边和分配边，使之成为孤立的结点。
  2. 进程 $P_i$ 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。
  3. 若能消去图中所有边，则称该图是可完全简化的，此时一定没有发生死锁。如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

---

• 并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的进程就是死锁进程。
• 解除死锁的方法：
  1. 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
  2. 撤销进程法（终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。
  3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
• 从以下方面考虑处理哪个死锁进程：
  1. 进程优先级（先终止低优先级的）
  2. 已执行时间（先终止时间短的）
  3. 还要多久完成（先终止还要很长时间才能完成的进程）
  4. 进程已经使用了多少资源（先终止资源更多的进程）
  5. 交互式还是批处理（先终止批处理进程）

第三章：内存管理

一、内存管理的基本概念

1. 基本概念

• 内存：可存放数据。程序执行前，需要先放到内存中才能被 CPU 处理 —— 缓和 CPU 与硬盘之间的速度矛盾。
• 编译：由编译程序将用户源代码编译成若干个目标模块（把高级语言翻译为机器语言）
• 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块和逻辑地址
• 装入模块：可理解为 可执行文件（*.exe）
• 装入（装载）：由装入程序将装入模块装入内存运行，装入后形成物理地址。

2. 存储单元

• 内存中划分成了一个一个的存储单元，每个存储单元对应一个内存地址。
• 存储单元的大小：
  • 如果计算机 “按字节编码”，则每个存储单元大小为 1 字节（1B）
  • 如果计算机 “按字编码”，字长 16 位，则每个存储单元大小为 1 个字，每个字的大小为 16 个二进制位

3. 内存地址

• 地址分类：
  • 逻辑地址：也叫相对地址，程序经过编译、链接后生成的指令中指明的是逻辑地址。
  • 物理地址：也叫绝对地址，数据在内存中实际存放的地址。

4. 装入方式（地址转换）

将指令中的逻辑地址转换为物理地址，三种装入方式：

1. 绝对装入
   • 概念：在编译时，如果知道程序将放在内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。
   • 特点：灵活性低，只适用于单道程序环境。
2. 静态重定位
   • 概念：又称可重定位装入。根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对内存进行 “重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。
   • 特点：用于早期的多道批处理操作系统。一个作业在装入内存时，必须分配其要求的全部空间，如果没有足够的内存，就不能转入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
3. 动态重定位
   • 概念：又称动态运行时装入。把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器（存放装入模块的起始地址）的支持。
   • 特点：用于现代操作系统。允许程序在内存中发生移动。并且可将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

5. 链接方式

1. 静态链接：在程序运行之前，先将各目标模块以及它们所需的库函数链接成一个完整的可执行文件（装入模块），之后不再拆开。
2. 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。优点是便于修改和更新，便于实现对目标模块的共享。

二、内存管理的作用

1. 分配与回收

• 操作系统负责 内存空间的分配与回收

2. 内存扩展

• 操作系统需要提供某种技术（虚拟技术）从逻辑上 对内存空间进行扩充
• 虚拟技术也是操作系统的虚拟性

3. 地址转换

• 操作系统需要提供 地址转换功能 ，负责程序的逻辑地址与物理地址的转换
• 为了使编程更方便，程序员写程序时只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换（地址重定向）应该由操作系统负责。
• 三种装入方式：绝对装入、可重定位装入、动态运行时装入

4. 内存保护

• 操作系统需要提供 内存保护 功能。保证各进程在各自存储空间内运行，互不干扰。
• 内存保护可采取的方式：
  1. 在 CPU 中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU 检查是否越界。
  2. 采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。重定位寄存器中存放进程的起始物理地址，界地址寄存器存放进程的最大逻辑地址。

三、覆盖与交换

• 内存空间的扩充包括了覆盖技术、交换技术、虚拟存储技术。这节主要记录覆盖技术和交换技术。

1. 覆盖技术

• 引入原因：早起的计算机内存很小，因此经常会出现内存大小不够的情况。于是引入了覆盖技术，用来解决“程序大小超过物理内存总和“的问题。
• 思想：
  • 将程序分为多个段（多个模块），内存中分为一个”固定区“和若干个”覆盖区“。
  • 需要常驻内存的段放在”固定区“中，调入后就不再调出（除非运行结束），不常用的段放在“覆盖区”，需要用时调入内存，用不到时调出内存。
• 缺点：对用户不透明，增加了用户编程负担。必须由程序员声明覆盖结构，操作系统完成自动覆盖。只用于早期的操作系统中。

2. 交换技术

• 思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
• 中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。
  • 暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）
  • 挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
• 实现：
  1. 通常把磁盘空间氛围文件区和对换区两部分。
     • 文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式
     • 对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。
     • 总之，对换区的IO速度比文件区的更快。
  2. 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。（如果发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程）
  3. 可优先换出阻塞进程、优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，还会考虑进程在内存的驻留时间
  4. PCB会常驻内存，不会被换出内存

3. 两种技术的区别

1. 覆盖技术是在同一个程序或进程中的
2. 交换技术是在不同进程（或作业）之间的

四、连续分配管理方式

• 连续分配：指为用户进程分配的必须是一个连续的内存空间
• 内部碎片：分配给某个进程的内存区域中，如果有些部分没有用上。
• 外部碎片：内存中的某些空闲分区由于太小而难以利用。

1. 单一连续分配

• 内存被分为系统区和用户区。
  • 系统区通常位于系统的低地址部分，用于存放操作系统相关数据
  • 用户区存放用户进程相关数据
• 内存中只能有一道用户进程，用户进程独占整个用户区空间
• 优点：实现简单，无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护
• 缺点：只能用于单用户、单任务的操作系统中，有内部碎片；存储器利用率低。

2. 固定分区分配

• 将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。
• 固定分区分配分为：分区大小相等、分区大小不等
  1. 分区大小相等：缺乏灵活性，但是很适合用于一台计算机控制多个相同对象的场合
  2. 分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分
• 分区说明表：
  • 操作系统需要建立分区说明表，来实现各个分区的分配与回收。
  • 每个表项对应一个分区，通常按分区大小排列。
  • 每个表项包括对应分区的大小、起始地址、状态（是否已分配）
• 优点：实现简单，无外部碎片
• 缺点：当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但又会降低性能；会产生内部碎片，内存利用率低。

3. 动态分区分配

• 动态分区分配又称为可变分区分配，这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
• 记录内存的使用情况有两种常用的数据结构：
  1. 空闲分区表：每个空闲分区对应一个表项。表项中包括分区号、分区大小、分区起始地址等信息。
  2. 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息。
• 把一个作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。
• 相邻的空闲区间需要合并，分区分配和回收的四种情况：
  1. 回收区之后有相邻的空闲分区
  2. 回收区之前有相邻的空闲分区
  3. 回收区前、后都有相邻的空闲分区
  4. 回收区前、后都没有相邻的空闲分区
• 动态分区分配没有内部碎片，但是有外部碎片。可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。

五、动态分区分配算法

1. 首次适应算法（First Fit）

• 算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
• 算法实现：空闲分区以地址递增的次序排序。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

2. 最佳适应算法（Best Fit）

• 算法思想：尽可能多地留下大片的空闲区，优先使用更小的空闲区。
• 算法实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
• 缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种算法会产生很多的外部碎片。

3. 最坏适应算法（Worst Fit）

• 有称最大适应算法（Largest Fit）
• 算法思想：每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
• 算法实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
• 缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用。

4. 邻近适应算法（Next Fit）

• 算法思想：对首次适应算法的改进，每次都从上次查找结束的位置开始检索，以减少查找开销。
• 算法实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

5. 四种算法比较

算法	算法思想	分区排列顺序	优点	缺点
首次适应算法	从头到尾找适合的分区	以地址递增次序排序	综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序
最佳适应算法	优先使用更小的分区，以保留更多大分区	以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应算法	优先使用更大的分区，以防止产生太小的不可用的碎片	以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程；算法开销大
邻近适应算法	以首次适应演变而来，每次从上次查找结束位置开始查找	以地址递增次序排列（可排成循环链表）	不用每次都从低地址的小分区开始检索，算法开销小	会使高地址的大分区也被用完

六、非连续分配管理方式

• 连续分配：为用户进程分配的必须是一个连续的内存空间
• 非连续分配：为用户进程分配的可以是一些分散的内存空间

1. 基本分页存储管理

1️⃣ 基本概念

• 分页存储概念：
  • 将内存空间分为一个个大小相等的分区，每个分区就是一个页框（也称为页帧、内存块、物理块、物理页面）
  • 每个页框有一个编号，即页框号（也称为页帧号、内存块号、物理块号、物理页号）。页框号从 0 开始。
  • 将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页（也称为页面）。每个页面的编号叫页号，页号从 0 开始。
  • 操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。
• 页表：
  • 为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。
  • 页表通常存在 PCB 中。一个进程对应一张页表，进程的每个页面对应一个页表项，每个页表项由页号和块号组成，页表记录进程页面和实际存放的内存块之间的映射关系。

计算机中内存块的数量 → 页表项中块号至少占多少字节
假设某系统物理内存大小为 4GB，页面大小为 4KB，则每个页表项至少应该为多少字节？

1. 页面大小 = 内存块大小 = 4KB = $2^{12}$B
2. 4GB 的内存总共会被分为 $2^{32}$ / $2^{12}$ = $2^{20}$ 个内存块
3. 内存块号的范围应该是 0 ~ $2^{20}$ - 1
4. 内存块号至少要用 20 bit 来表示
5. 至少要用 3B 来表示块号（3 * 8 = 24 bit）

页表项中的页号不占用存储空间。假设页表中的各页表项从内存地址为 X 的地方开始连续存放，则 i 号页表项的存放地址 = X + 3 * I。存储整个页表至少需要 3 * (n+1) B。

• 在上题中，页表项长度为 3B 即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多字节，使得每个页面恰好可以装得下整数个页表项。（例如 4B）
• 分页存储管理的逻辑地址结构为 页号P + 页内偏移量W
  • 如果由 K 位表示页内偏移量，则说明系统中一个页面的大小是 $2^K$ 个内存单元。
  • 如果由 M 位表示页号，则说明系统中一个进程最多允许有 $2^M$ 个页面。

• 逻辑地址转物理地址
  1. 进程在内存中连续存放时，物理地址 = 进程在内存中的起始地址 + 偏移量（目标逻辑地址）
  2. 将进程地址空间分页之后，物理地址 = P 号页面在内存中的起始地址 + 页内偏移量 W
     • 确定逻辑地址A对应的页号P
     • 找到P号页面在内存中的起始地址（需要查页表）
     • 确定逻辑地址A的页内偏移量W

在某计算机系统中，页面大小是 50B。某进程逻辑地址空间大小为 200B，则逻辑地址 110 对应的页号、页内偏移量是多少？

1. 页号 = 逻辑地址 / 页面地址 （取整）= 110 / 50 = 2
2. 页内偏移量 = 逻辑地址 % 页面长度（取余）= 110 % 50 = 10

---

如果每个页面大小为 $2^k$ B，用二进制数表示逻辑地址，则末尾 k 位即为页内偏移量，其余部分为页号。

2️⃣ 基本地址变换机构

• 基本地址变换机构：就是在基本分页存储管理中，用于实现逻辑地址到物理地址转换的一组硬件机构。
• 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
• 通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。
• 进程未执行时，页表的起始地址和页表长度放在PCB中，当进程被调度时，操作系统内核会把他们放到PTR中。

设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下：

1. 计算页号P和页内偏移量W（P=A/L, W=A%L)；
2. 比较页号P和页表长度M，若 P $\ge$ M，则产生越界中断，否则继续执行；
3. 页表中页号P的页表项地址 = 页表起始地址F + 页号P * 页表项长度，取出该页表项内容b，即为内存块号；
4. 计算 E = b * L + W，用得到的物理地址E区访存。
   

若页面大小L为 1K 字节，页面2对应的内存块号 b = 8，将逻辑地址 A = 2500 转换为物理地址E。
（等价描述：某系统按字节寻址，逻辑地址结构中，页内偏移量占10位，页号2对应的内存块号 b = 8，将逻辑地址 A = 2500 转换为物理地址E。）

1. 计算页号、页内偏移量：
   页号P = A / L = 2500 / 1024 = 2
   页内偏移量W = A % L = 2500 % 1024 = 452
2. 根据题中条件可知，页号2没有越界，其存放的内存块号 b = 8
3. 物理地址E = b * L + W = 8 * 1024 + 425 = 8644

由上可知，页面管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动算出页号、页内偏移量两个部分。

3️⃣ 具有快表的地址变换机构

• 在基本地址变换机构的基础上，引入快表。
• 快表：又称联想寄存器（TLB，translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（TLB不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与之对应，内存中的页表常称为慢表。

引入快表后，地址的变换过程：

1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存。（在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）

• 局部性原理
  1. 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能再次执行；如果某个数据被访问过，不久之后该数据很有可能再次被访问。（因为程序中存在大量的循环）
  2. 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问，（因为很多数据在内存中都是连续存放的）
• TLB和普通Cache区别：TLB中只有页表项的副本，普通Cache中可能会有其他各种数据的副本。

4️⃣ 两级页表

• 单级页表的问题：
  1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
  2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面
• 在解决页表很大的情况时，可将页表进行分组，使每个内存块刚好可以放入一个分组。为离散分配的页表在建立一张页表，称为页目录表，也称为外层页表、顶层页表。

实现地址变换：
将逻辑地址（0000000000，0000000001，111111111111）转换为物理地址，用十进制表示。

1. 按照地址结构将逻辑地址拆分成三部分
2. 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查表，找到最终想访问的内存块号
4. 结合页内偏移量得到物理地址（应该是4*4096+4095=20479）
   

• 要解决问题2，可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。若想访问的页面不在内存中，则产生缺页中断（内中断），然后将目标页面从外存调入内存。
• 注意细节：
  1. 若采用多级页表机制，则各级页表的大小不能超过一个页面。（否则会跨页面存储）

  某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用（　）级页表，页内偏移量为（　）位。

  1. 页面大小 = 4KB = $2^{12}$B，按字节编址，因此页内偏移量为 12 位
  2. 页号 = 40 - 12 = 28 位
  3. 页面大小 = $2^{12}$B，页表项大小 = 4B，则每个页面可存放 $2^{12}$ / 4 = $2^{10}$ 个页表项
  4. 因此各级页表最多包含 $2^{10}$ 个页表项，需要 10 位二进制位才能映射到 $2^{10}$ 个页表项，因此每一级的页表对应页号应为 10 位。总共 28 位的页号至少要分为 3 级。

  2. 多级页表的访存次数（假设没有快表机制），则 N 级页表访问一个逻辑地址需要 N+1 次访存。

2. 基本分段存储管理

• 与“分页”最大的区别是，离散分配时所分配地址空间的基本单位不同
• 分段：
  • 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址。
  • 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
  • 逻辑地址结构由段号（段名）和段内地址（段内偏移量）组成。
    段号的位数决定了每个进程最多可以分几个段。
    段内地址位数决定了每个段的最大长度是多少。
• 段表：
  • 每个进程建立一张段映射表，简称“段表”，能从物理内存中找到各个逻辑段的存放位置。
  • 每个段对应一个段表项，其中记录了该段在内存中的起始位置（基址）和段的长度。
  • 各个段表项的长度是相同的，且段号可以是隐含的，不占存储空间。
    
• 地址转换
  
• 分段、分页管理的对比：
  1. 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
     段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组术语一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
  2. 页的大小固定且由系统决定。段的长度不固定，由用户编写的程序决定。
  3. 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
     分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
  4. 分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的，可修改的代码是不能共享的。
• 访存次数：两次 —— 第一次查内存中的段表，第二次访问目标内存单元。也可以引入快表机构，即可少访问一次。

3. 段页式管理方式

• 分页、分段的优缺点

	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片	不方便按照逻辑模块实现信息的共享和保护
分段管理	很方便按照逻辑模块实现信息的共享和保护	如果段长过大，为其分配很大的连续空间会很不方便。会产生外部碎片

• 段页式管理的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成
  • 段号的位数决定了每个进程最多可以分几个段
  • 页号的位数决定了每个段最大有多少页
  • 页内偏移量决定了页面大小、内存块大小是多少
• 段页式管理的地址结构是二维的。分段对用户是可见的，各段分页对用户是不可见的。
  • 每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。每个段表项长度相等，短号是隐含的。
  • 每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。
• 地址转换
  
• 访存次数：三次 —— 第一次查内存中的段表，第二次查页表，第三次访问目标内存单元。引入快表机构后，用短号和页号作为查询快表的关键字，若命中则仅需一次访存。

七、虚拟内存

1. 基本概念

• 传统存储管理方式的缺点：
  1. 一次性：作业必须一次性全部装入内存后才能开始运行。这回造成两个问题：① 作业很大时，不能全部装入内存，导致大作业无法运行；② 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业运行，导致多道程序并发度下降。
  2. 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。
• 局部性原理： 时间局部性、空间局部性、高速缓存技术。
• 虚拟内存的定义：
  • 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
  • 请求调页、请求调段：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
  • 页面置换、段置换：若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
  • 在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，就是虚拟内存。
• 虚拟内存的主要特征：
  • 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
  • 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
  • 虚拟性：在逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
• 虚拟内存的实现需要建立在离散分配的内存管理方式基础上：
  • 基本分页存储管理 $\stackrel{请求调页、页面置换}{\to }$ 请求分页存储管理
  • 基本分段存储管理 $\stackrel{请求调段、段置换}{\to }$ 请求分段存储管理
  • 基本段页式存储管理 $\to$ 请求段页式存储管理

2. 请求分页管理方式

• 请求分页存储管理与基本分页存储管理的主要区别：
  1. 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需要的信息从外存调入内存，然后继续执行程序。
  2. 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
• 请求页表：
  1. 内存块号
  2. 状态位：是否已调入内存
  3. 访问字段：可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
  4. 修改位：页面调入内存后是否被修改过
  5. 外存地址：页面在外存中的存放位置
• 缺页中断机构：
  1. 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
  2. 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
  3. 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
     如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。为修改过的页面不用写回外存。
• 缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。一条指令在执行期间，可能产生多次缺页中断。
• 地址变换机构新增步骤：
  1. 请求调页（查到页表项时进行判断）
  2. 页面置换（需要调入页面，但没有空闲内存块时进行）
  3. 需要修改请求页表中新增的表项
     
• 地址变换补充：
  1. 快表中有的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面。
  2. 只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。以减少访存次数。
  3. 和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
  4. 换入 / 换出页面都需要启动慢速的 IO 操作，可见，如果换入 / 换出太频繁，会有很大的开销。
  5. 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。所以地址变换步骤是：查快表（未命中）→ 查慢表（发现未调入内存）→ 调页（调入的页面对应的表项会直接加入快表）→ 查快表（命中）→ 访问目标内存单元

3. 页面置换算法

• 页面的换入、换出需要磁盘 IO，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

1️⃣ 最佳置换算法（OPT）

• 最佳置换算法（OPT，Optimal）：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。（淘汰最后一个出现的页面）
• 最佳置换算法最佳置换算法在实际应用中无法实现。

2️⃣ 先进先出置换算法（FIFO）

• 先进先出置换算法（FIFO，First In First Out）：每次选择淘汰的页面是最早进入内存的页面。
• 实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面。队列的最大长度取决于系统为进程分配了多少个内存块。

• 只有 FIFO 算法会产生 Belady 异常。
  • Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

• FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因此先进入的页面也有可能最经常被访问。因此算法性能差。

3️⃣ 最近最久未使用置换算法（LRU）

• 最近最久未使用置换算法（LRU，Least Recently Used）：每次淘汰的页面时最近最久未使用的页面。（淘汰逆向扫描过程中最后一个出现的页号）
• 实现方法：赋予每个页面对应的页面项中，用访问字段记录该页面自上次被访问以来所经历的时间 t。当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面。
• 最近最久未使用置换算法需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。

4️⃣ 时钟置换算法（CLOCK）

• 时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，Not Recently Used）。
• 实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

1. 当某页被访问时，其访问位置为1。
2. 当需要淘汰一个页面时，只需检查页的访问位。如果是 0，就选择该页换出；如果是 1，则将它直为 0，暂不换出，继续检查下一个页面。
3. 若第一轮扫描中所有页面都是 1，则将这些页面的访问位依次置为 0 后，再进行第二轮扫描（因此简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）

5️⃣ 改进型的时钟置换算法

• 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就需要执行 IO 操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
• 算法思想：在其他条件都相同时，优先淘汰没有修改过的页面，避免 IO 操作。
• 实现方法：设置一个修改位，修改位为 0 表示没有被修改过，为 1 表示被修改过。

用（访问位，修改位）的形式表示个页面状态，如（1，1）表示一个页面近期被访问过，且被修改过。

1. 第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
2. 第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为 0
3. 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
4. 第四轮：若第三轮扫描失败，则重新扫描。查找第一个（0，1）的帧用于替换。

因此改进型 CLOCK 置换算法选择一个淘汰页面最多会进行四轮扫描。依次淘汰的是（0，0）、（0，1）、（1，0）、（1，1）

6️⃣ 五种算法比较

算法名称	算法规则	优点	缺点
最佳置换算法（OPT）	优先淘汰最长时间内不会被访问的页面	缺页率最小，性能最好	无法实现
先进先出置换算法（FIFO）	优先淘汰最先进入内存的页面	实现简单	性能很差，可能出现Belady异常
最近最久未使用置换算法（LRU）	优先淘汰最近最久没访问的页面	性能很好	需要硬件支持，算法开销大
简单时钟置换算法（CLOCK、NRU）	循环扫描各页面 第一轮淘汰访问位为 0 的，并将扫描过的页面访问位改为 1。 若第一轮没选中，则进行第二轮扫描。	实现简单，算法开销小	未考虑页面是否被修改过
改进型CLOCK（改进型NRU）	若用（访问位，修改位）的形式表述，则 第一轮：淘汰（0，0） 第二轮：淘汰（0，1），并将扫描过的页面访问位置为 0 第三轮：淘汰（0，0） 第四轮：淘汰（0，1）	算法开销小，性能也不错

4. 页面分配策略

• 驻留集：指请求分页存储管理中给进程分配的物理块的集合。
  • 在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的大小，且应该选择一个合适的驻留集大小
  • 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少
  • 若驻留集太大，会导致多道程序并发度下降，资源利用率降低。
• 工作集：指在某段时间间隔内，进程实际访问页面的集合。
  • 操作系统通常用“窗口尺寸”算出工作集，且工作集大小可能小于窗口尺寸。
    
  • 一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
• 抖动（颠簸）：刚刚换出的页面马上又要换出内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。
  • 产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）

---

• 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
• 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
• 局部置换：发生缺页时只能选进程自己的物理块进行置换
• 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

三种分配策略：

1. 固定分配局部置换：
   • 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。
   • 若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后在调入需要的页面。
   • 缺点：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。
2. 可变分配全局置换：
   • 刚开始会为每个进程分配一定数量的物理块。
   • 操作系统会保持一个空闲物理块队列，当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。
   • 采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
3. 可变分配局部置换：
   • 刚开始会为每个进程分配一定数量的物理块。
   • 当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。
   • 如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度。反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

---

何时调入页面：

1. 预调页策略（运行前调入）：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。所以这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。
2. 请求调页策略（运行时调入）：进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘 IO 操作，因此 IO 开销较大。

---

外存（磁盘）中包括：

• 对换区：读写速度更快，采用连续分配方式
• 文件区：读写速度更慢，采用离散分配方式

从何处调入页面：

1. 系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
2. 系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
3. UNIX方式：运行之前进程有关的数据全部放在文件区，所以未使用过的页面，都可从文件区调入。若被使用过的页面需要换出到外存，则写回对换区，下次需要时从对换区调入。

5. 内存映射文件

• 内存映射文件（Memory-Mapped Files）：操作系统向上层程序员提供的功能（系统调用）
• 作用：
  1. 方便程序员访问文件数据
  2. 方便多个进程共享同一个文件
• 特性：
  1. 进程可使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间
  2. 以访问内存的方式读写文件
  3. 进程关闭文件时，操作系统负责将文件数据写会磁盘，并解除内存映射
  4. 多个进程可以映射同一个文件，方便共享
• 优点：
  1. 程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可
  2. 文件数据的读入/写出完全由操作系统负责，IO 效率可以有操作系统负责优化

第四章：文件管理

一、文件管理概念

• 文件：一组有意义的信息 / 数据集合。
• 一个文件的属性：
  1. 文件名：同一目录下不允许有重名文件。
  2. 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
  3. 类型；
  4. 位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
  5. 大小；
  6. 创建时间、上次修改时间；
  7. 文件所有者信息；
  8. 保护信息：对文件进行保护的访问控制信息。
• 文件的逻辑结构：
  1. 无结构文件：如文本文件，由一些二进制或字符流组成，又称 “流式文件”。
  2. 有结构文件：如目录、数据库表，由一组相似的记录组成，又称 “记录式文件”
• 操作系统向上层提供的功能：
  1. 创建文件：调用 create 系统调用
  2. 读文件：read 系统调用
  3. 写文件：write 系统调用
  4. 删除文件：delete 系统调用
  5. 打开文件：open 系统调用
  6. 关闭文件：close 系统调用
• 文件的物理结构：
  • 外存由一个个存储单元组成，每个存储单元可以存储一定量的数据。每个存储单元对应一个物理地址
  • 外存被分为一个个 “块 / 磁盘块 / 物理块”，每个磁盘块大小相等，每块一般包含2的整数幂个地址。文件的逻辑地址分为（逻辑块号，块内地址），块内地址的位数取决于磁盘块的大小
  • 操作系统以 “块” 为单位为文件分配存储空间，外存中的数据读入内存同样以块为单位。

二、文件的逻辑结构

1. 无结构文件

• 文件内部的数据是一系列二进制流或字符流组成。又称 “流式文件”。
• 没有明显的结构特性，因此不需要探讨无结构文件的逻辑结构。

2. 有结构文件

• 由一组相似的记录组成，又称 “记录式文件”。每条记录由若干个数据项组成。
• 根据各条记录的长度（占用的存储空间）是否相等，又可分为 定长记录 和 可变长记录 两种。
• 根据有结构文件中的各条记录在逻辑上如何组织，可分为三类：顺序文件、索引文件、索引顺序文件 。

1️⃣ 顺序文件

• 顺序文件 ：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的 或可变长的。
• 各个记录在物理上可以顺序存储 或链式存储 ：
  • 顺序存储：逻辑上相邻的记录物理上也相邻（类似于顺序表）
  • 链式存储：逻辑上相邻的记录物理上不一定相邻（类似于链表）
• 根据记录是否按照关键字排列，顺序文件分为串结构和顺序结构：
  • 串结构：记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序，增加 / 删除一个记录相对简单。
  • 顺序结构：记录之间的顺序按关键字顺序排列。缺点是增加 / 删除一个记录比较困难。
• 能否实现随机存取：
  • 结论：定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）。
  • 链式存储：无论是定长 / 可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找。
  • 顺序存储：
    • 可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找
    • 定长记录：可实现随机存取，记录长度为 L，则第 i 个记录存放的相对位置上 i * L
      • 若采用串结构，无法快速找到某关键字对应的记录
      • 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）

2️⃣ 索引文件

• 索引文件 ：为加快检索可变长记录，每个文件建立一张索引表，以加快文件检索速度。每条记录对应一个索引项。
• 索引表 本身是定长记录的顺序文件，因此可以快速找到第 i 个记录对应的索引项。
• 可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。也可用不同的数据项建立多个索引表。
• 每当要增加 / 删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
• 缺点：每个记录对应一个索引表项，因此索引表可能会很大。

3️⃣ 索引顺序文件

• 索引顺序文件 ：是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项 。
• 索引顺序文件的索引表是一个定长记录的串结构顺序文件，索引项不需要按关键字顺序排列，这样可以极大地方便新表项的插入。
• 为进一步提高检索效率，可以为顺序文件建立多极索引表 。

三、文件目录

1. 文件控制块

• 文件控制块（FCB）：
  • FCB中包含了文件的基本信息（文件名、物理地址 、逻辑结构、物理结构等）、存取控制信息（是否可读 / 可写、禁止访问的用户名单等）、使用信息（文件的建立时间、修改时间）
  • 目录文件中的一条记录就是一个文件控制块。
  • FCB的有序集合称为 “文件目录”，一个FCB就是一个文件目录项。
  • FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现 ”按名存取“。
• 目录本身是一种有结构文件，由一条条记录组成。每条记录对应一个放在该目录下的文件。
• 需要对目录进行的操作：
  1. 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
  2. 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
  3. 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
  4. 显示目录：用户可以请求现实目录的内容，如显示该目录中的所有文件及相应属性
  5. 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如文件重命名）

2. 目录结构

• 单级目录结构
  • 早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
  • 单级目录实现了 ”按名存取“，但是不允许文件重名。
  • 单级目录结构不适用于多用户操作系统。
• 两级目录结构
  • 早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User File Directory）。
  • 主文件目录记录用户名及相应用户文件目录的存放位置。用户文件目录由该用户的文件FCB组成。
  • 允许不同用户的文件重名，也可以在目录上实现访问限制。但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类。
• 多级目录结构
  • 又称树形目录结构。
  • 用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用 “/” 隔开。从根目录出发的路径称为绝对路径。
  • 很多时候，用户会连续访问同一目录内的多个文件，如果每次都从根目录开始查找，是很低效的。因此可以设置一个 “当前目录”。从当前目录出发的路径为相对路径。
  • 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是树形结构不便于实现文件的共享。
• 无环图目录结构
  • 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。
  • 可以用不同的文件名指向同一个文件，也可以指向同一个目录（共享同一目录下的所有内容）
  • 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB，并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点。
  • 共享文件不同于复制文件，在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

3. 索引结点

• 索引结点是FCB的改进，通过减少目录项大小，实现减小磁盘启动次数，可以提高查找效率。
• 查找各级目录时只需要文件名，因此把除了文件名之外的文件描述信息都放到索引结点。当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据存放位置即可找到文件。
• 存放在外存中的索引结点称为磁盘索引结点，当索引结点放入内存后称为内存索引结点。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

四、❗文件的物理结构❗

1. 文件块、磁盘块

• 类似于内存分页，磁盘中的存储单元也会被分为一个个 “块 / 磁盘块 / 物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。
• 内存与磁盘之间的数据交换（即读写操作、磁盘IO）都是以块为单位进行的。
• 在内存管理中，进程的逻辑地址空间被分为一个一个页面，同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件块，于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

2. 文件分配方式——连续分配

• 连续分配方式要求每个文件在磁盘上占有一组连续的块。
• 连续分配时，文件目录中记录存放的起始块号和长度（总共占用几个块）
• 用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）计算出物理块号，且需要检查用户提供的逻辑块号是否合法$$物理块号=起始块号+逻辑块号$$
• 优点：支持顺序访问和直接访问（即随机访问），连续分配的文件在顺序读 / 写时速度最快。
• 缺点：不方便拓展；存储空间利用率低，会产生难以利用的磁盘碎片。（可以用紧凑来处理碎片，但是需要耗费很大的时间代价）

3. 文件分配方式——链接分配

• 链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

1️⃣ 隐式链接

• 在FCB中记录了文件存放的起始块号和结束块号，也可以增加一个字段来表示文件的长度。
• 除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的。
• 若要读入 i 号逻辑块，总共需要 i+1 次磁盘IO。
• 优点：方便文件拓展，不会有碎片问题，外存利用率高。
• 缺点：只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

2️⃣ 显式链接

• 文件分配表（FAT，File Allocation Table）：把用于链接文件各物理块的指针显式地存放在一张 FAT 表中。
• 显式链接中，一个磁盘只会建立一张文件分配表，开机时文件分配表放入内存，并常驻内存。
• 优点：方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
• 缺点：文件分配表需要占用一定的存储空间。

4. 文件分配方式——索引分配

• 索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块。
• 在显式链接中，FAT是一个磁盘对应一张。在索引分配中，索引表是一个文件对应一张。
• 优点：方便文件拓展，支持随机访问。
• 缺点：索引表需要占用一定的存储空间。
• 若每个磁盘 1KB，一个索引表项 4B，则一个磁盘块只能存放 256 个索引项，如果一个文件的大小超过了 256 块，那么一个磁盘块是装不下文件的整张索引表的，可采用链接方案、多层索引、混合索引

1️⃣ 链接方案

• 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
• 缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0～i-1 号索引块，这就导致磁盘 IO 次数过多，查找效率低下。

2️⃣ 多层索引

• 多层索引：建立多层索引（类似于多级页表），使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
• 若采用多层索引，则各层索引表大小不能超过一个磁盘块。
• 采用 K 层索引结构，且顶级索引表为调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作。
• 缺点：即使是小文件，访问一个磁盘块依然需要 K + 1 次读磁盘。

3️⃣ 混合索引

• 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表），还包含两级间接索引（指向两层索引表）。
• 优点：对于小文件来说，访问一个磁盘块所需的读磁盘次数更少。

五、文件存储空间管理

1. 存储空间的划分与初始化

• 划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）。有的系统支持将多个物理磁盘组成一个文件卷。
• 初始化：将各个文件卷划分为目录区、文件区。
  • 目录区：主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息
  • 文件区：用于存放文件数据

2. 存储空间管理——空闲表法

• 空闲表中记录第一个空闲盘块号和空闲盘块数，类似于内存动态分区分配。适用于物理结构是连续分配方式。
• 如何分配磁盘块：为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
• 如何回收磁盘块：四种情况，和动态分区分配的四种情况类似。回收时注意表项的合并问题。

3. 存储空间管理——空闲链表法

1️⃣ 空闲盘块链

• 空闲盘块链：以盘块为单位组成一条空闲链。
  • 空闲盘块中存储着下一个空闲盘块的指针。
  • 操作系统会保存着链头、链尾指针。
• 如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。
• 如何回收：回收的盘块依次挂在链尾，并修改空闲链的链尾指针。
• 适用于离散分配的物理结构，为文件分配多个盘块时可能要重复多次操作。

2️⃣ 空闲盘区连

• 空闲盘区连：连续的空闲盘块组陈一个空闲盘区。
  • 以盘区为单位组成一条空闲链。
  • 空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针。
  • 操作系统会保存着链头、链尾指针。
• 如何分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
• 如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
• 离散分配、连续分配都适用，相比于空闲盘块链，为一个文件分配多个盘块时效率更高。

4. 存储空间管理——位示图法

• 位示图：每个二进制位对应一个盘块。例如：0 代表盘块空闲，1 代表盘块已分配。
• 位示图一般用连续的 “字” 来表示，因此可以用（字号，位号）/（行号，列号）对应一个盘块号。
• 若盘块号、字号、位号从 0 开始，n 表示字长，（字号，位号）=（i，j），则
  $$盘块号b=ni+j$$$$b号盘块对应的字号i=b/n，位号j=b\%n$$
• 如何分配：若文件需要 K 个块
  1. 顺序扫描位示图，找到 K 个相邻或不相邻的 0
  2. 根据字号、位号算出对应的盘块号，将相应盘块分配给文件
  3. 将相应位设置为 1
• 如何回收：
  1. 根据回收的盘块号计算出对应的字号、位号
  2. 将相应二进制位设为 0
• 连续分配、离散分配都适用。

5. 存储空间管理——成组链接法

• 理解即可。
• 空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX 系统中采用了成组链接法对磁盘空闲块进行管理。
• 文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存。并且内存与外存中的超级块数据一致。

六、文件的基本操作

1. 创建文件

• 调用 create 系统调用
• 需要提供的主要参数：
  1. 所需的外存空间大小
  2. 文件存放路径
  3. 文件名
• 主要做两件事：
  1. 在外存中找到文件所需的空间（结合空闲表法、空闲链表法、位示图法等管理策略，找到空闲空间）
  2. 根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

2. 删除文件

• 调用 delete 系统调用
• 需要提供的主要参数：
  1. 文件存放路径
  2. 文件名
• 主要做：
  1. 根据文件存放路径找到相应的目录文件，从目录中 找到文件名对应的目录项
  2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息， 回收文件占用的磁盘块。
  3. 从目录表中删除文件对应的目录项。

3. 打开文件

• 调用 open 系统调用
• 需要提供的主要参数：
  1. 文件存放路径
  2. 文件名
  3. 要对文件的操作类型（只读、读写等）
• 主要做：
  1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限。
  2. 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。之后用户进程A再操作文件就不需要每次都重新查目录，加快文件的访问速度。
• 打开文件表有 进程的打开文件表 和 系统的打开文件表
  • 进程的打开文件表记录了读写指针（记录该进程对文件的读写操作进行到的位置）、访问权限、系统表索引号（也称文件描述符）
  • 系统的打开文件表整个系统只有一张，记录了打开计数器（此时有多少个进程打开了次文件）、外存地址。

4. 关闭文件

• 调用 close 系统调用
• 主要做：
  1. 将进程的打开文件表相应表项删除
  2. 回收分配给该文件的内存空间等资源
  3. 系统打开文件表的打开计数器减 1，若计数器为 0，则删除对应表项。

5. 读文件

• 调用 read 系统调用
• 需要提供的主要参数：
  1. 指明是哪个文件（在支持 “打开文件” 操作的系统中，只需要提供文件在打开文件表的索引号即可）
  2. 需要读入多少数据
  3. 读入的数据要放在内存中的什么位置
• 主要做：
  1. 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中

6. 写文件

• 调用 write 系统调用
• 需要提供的参数：
  1. 指明是哪个文件
  2. 需要写出多少数据
  3. 写回外存的数据放在内存中的什么位置
• 主要做：
  1. 从用户指定的内存区域中，将指定大小的数据写回指针指向的外存。

七、文件共享

• 多个用户共享同一个文件，意味着系统中只有一份文件数据，并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

1. 基于索引结点的共享方式（硬链接）

• 索引结点：是一种文件目录的瘦身策略。由于检索文件时只需用到文件名，因此可以将除文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针。
• 索引结点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。
• 删除文件：
  • 当 count > 0 时，说明还有别的用户要使用该文件，只会把用户目录中与该文件对应的目录项删除，count - 1
  • 当 count = 0 时，系统负责删除文件。否则会导致指针悬空。

2. 基于符号链的共享方式（软链接）

• 新建一个 link 类型的文件，记录文件的存放路径，类似于 windows 中的快捷方式。
• 操作系统根据路径一层层查找目录，最终找到共享文件，因此会有多次磁盘 IO，软链接访问速度比硬链接更慢。
• 软链接指向的共享文件已被删除，Link 型文件依然存在，只是会查找失败。

八、文件保护

1. 口令保护

• 口令一般存放在文件对应的 FCB 或索引结点中，用户访问文件前需要先输入口令，操作系统会将用户提供的口令与 FCB 中存储的口令进行对比，如果正确，则允许该用户访问文件。
• 优点：保存口令的空间开销不多，验证口令的时间开销也小。
• 缺点：正确的口令存放在系统内部，不够安全。

2. 加密保护

• 使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密。
• 优点：保密性强，不需要再系统中存储密码
• 缺点：编码 / 译码（加密 / 解密）要花费一定时间

3. 访问控制

• 再每个文件的 FCB 或索引结点中增加一个访问控制列表（Access-Control List，ACL），该表中记录了各个用户可以对该文件执行哪些操作。
• 访问类型包括：读、写、执行、添加、删除、列表清单
• 如果用户过多，访问控制列表可能会很大，可以用精简的访问列表解决这个问题。
  • 精简的访问列表：用 “组” 为单位，标记各组用户可以对文件执行哪些操作。
• 如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制。
• 优点：实现灵活，可以实现复杂的文件保护功能。

九、文件系统的层次结构

1. 用户接口（六、文件的基本操作）：文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求（read、write、open、close等系统调用）
2. 文件目录系统（三、文件目录）：用户通过文件路径来访问文件，因此这一层需要根据用户给出的文件路径找到相应的 FCB 或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如：管理活跃的文件目录表、管理打开文件表等。
3. 存取控制模块（八、文件保护）：为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能。
4. 逻辑文件系统与文件信息缓冲区（二、文件的逻辑结构）：用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址。
5. 物理文件系统（四、文件的物理结构）：这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址。
6. 辅助分配模块（五、文件存储空间管理）：负责文件存储空间的管理，即负责分配和回收存储空间。
7. 设备管理模块（第五章设备管理中的磁盘管理）：直接与硬件交互，负责和硬件直接相关的一些管理工作。如：分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等。
   

十、文件系统的全局结构（布局）

• 原始磁盘：磁盘出厂时里面没有扇区。
• 物理格式化：即低级格式化，划分扇区，检测坏扇区，并用备用扇区替换坏扇区。
• 逻辑格式化：即高级格式化，会把磁盘分为一个个分区（分卷 Volume）。完成各分区的文件系统初始化。

---

• 文件系统在内存中的结构：
  • 近期访问过的目录文件会缓存在内存中，不用每次都从磁盘读入，这样可以加快目录检索速度。
    

十一、虚拟文件系统

• 普通文件系统：在一个操作系统中，不同的文件系统可能会用不同的函数名或参数列表。
  
• 虚拟文件系统（VFS）特点：
  1. 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异。
  2. VFS 要求下层的文件系统必须实现某些规定的函数功能，如：open / read / write。一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统 VFS 的要求。.
  3. 每打开一个文件，VFS 就在主存中新建一个 vnode（ v 结点），并将文件信息复制到 vnode 中，用统一的数据结构表示文件，无论该文件存储在哪个文件系统。vnode 的功能指针指向具体文件系统的函数功能。
     • vode：虚拟文件系统中的索引结点，只存在于主存中。
     • inode：磁盘文件系统的索引结点，既会被调入主存，也会在外存中存储。
       

十二、文件系统挂载（安装）

• 文件系统挂载（mounting），即文件系统安装 / 装载，负责将一个文件系统挂载到操作系统中。
• 主要做：
  1. 在 VFS 中注册新挂载的文件系统。内存中的挂载表（mount table）包含了每个文件系统的相关信息，包括文件系统类型、容量大小等。
  2. 新挂载的文件系统，要向 VFS 提供一个函数地址列表
  3. 将新文件系统加到挂载点（mount point），也就是将新文件系统挂载在某个父目录下。

第五章：设备管理

一、I/O设备的基本概念和分类

• IO设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件设备。由机械部件和电子部件（IO控制器、设备控制器）组成。
  • 机械部件：主要用来执行具体 IO 操作，如看得见摸得着的鼠标键盘的按钮
  • 电子部件：通常是一块插入主板扩充槽的印刷电路板。
• UNIX 系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。
  • write 操作：向外部设备写出数据
  • read 操作：从外部设备读入数据
• 按使用特性分类：
  1. 人机交互类外部设备：数据传输速度慢，用于人机交互，例如鼠标、键盘等
  2. 存储设备：数据传输速度快，用于数据存储，例如硬盘、光盘等
  3. 网络通信设备：数据传输速度介于中间，用于网络通信，例如调制解调器
• 按传输速率分类：
  1. 低速设备：传输速率为每秒几个到几百字节，例如鼠标、键盘等
  2. 中速设备：传输速率为每秒数千至上万个字节，例如激光打印机
  3. 高速设备：传输速率为每秒数千字节至千兆字节的设备，例如磁盘
• 按信息交换的单位分类：
  1. 块设备：数据传输的基本单位是块，传输速率较高，可寻址（可随机读写任一块），例如磁盘
  2. 字符设备：数据传输的基本单位是字符，传输速率较慢，不可寻址，在 IO 时常采用中断驱动方式，例如鼠标、键盘等

二、I/O控制器

• CPU 无法直接控制 IO 设备的机械部件，因此 IO 设备还要有一个电子部件作为 CPU 和 IO 设备机械部件之间的中介，用于实现 CPU 对设备的控制。这个电子部件就是 IO 控制器，又称设备控制器。CPU 可控制 IO 控制器，又由 IO 控制器来控制设备的机械部件。

1. IO 控制器的功能：

1. 接受和识别 CPU 发出的命令，如 CPU 发出的 read / write 命令，IO 控制器中会有相应的控制寄存器来存放命令和参数
2. 向 CPU 报告设备的状态，IO 控制器中会有相应的状态寄存器，用于记录 IO 设备的当前状态，如 1 表示空闲，0 表示忙碌
3. 数据交换：IO 控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存 CPU 发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后 CPU 从数据寄存器中取走数据。
4. 地址识别：类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的地址。IO 控制器通过 CPU 提供的地址来判断 CPU 要读写的时哪个寄存器。

2. IO 控制器的组成：

1. CPU与控制器的接口：用于实现 CPU 与控制器之间的通信。CPU 通过控制线发出命令；通过地址线知名要操作的设备；通过数据线来取出（输入）数据，或放入（输出）数据。
2. IO 逻辑：负责接收和识别 CPU 的各种命令（如地址译码），并负责对设备发出命令
3. 控制器与设备的接口：用于实现控制器与设备之间的通信。
   • 传送输入 / 输出数据
   • 设备要反馈状态（忙碌 / 空闲）
   • 控制器向设备发出控制信息
     

• 小细节：
  1. 一个 IO 控制器可能会对应多个设备
  2. 数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制 / 状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便 CPU 操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像 IO；另一些计算机则采用 IO 专用地址，即寄存器独立编址。
     • 内存映像 IO：控制器中的寄存器与内存地址统一编址。优点是简化了指令。可以采用对内存进行操作的指令来对控制器进行操作。
     • 寄存器独立编址：控制器中的寄存器使用单独的地址。缺点是需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号。

三、IO 控制方式

1. 程序直接控制方式

• 关键词：轮询
• 完成一次读 / 写操作的流程（以读操作为例）
  1. CPU 向控制器发出读指令。于是设备启动，并且状态寄存器设为 1（未就绪）
  2. 在设备没有准备好数据之前，CPU 一直轮询检查控制器的状态（不断地执行程序的循环，若状态为一直是 1，说明设备还没准备好要输入的数据，于是 CPU 会不断地轮询）
  3. 输入设备准备好数据后将数据传给控制器，并报告自身状态。
  4. 控制器将输入的数据放到数据寄存器中，并将状态改为 0（已就绪）
  5. CPU 发现设备已就绪，即可将数据寄存器中的内容读入 CPU 的寄存器中，再把 CPU 寄存器中的内容放入内存
  6. 若还要继续读入数据，则 CPU 继续发出读指令
     
• CPU 干预频率：很频繁，IO 操作开始之前、完成之后需要 CPU 介入，并且在等待 IO 完成的过程中 CPU 需要不断地轮询检查。
• 数据传送的单位：每次读写一个字
• 数据的流向
  1. 读操作（数据输入）：IO 设备 → CPU → 内存
  2. 写操作（数据输出）：内存 → CPU → IO 设备
• 优点：实现简单。在读写指令之后，加上实现循环检查的一系列指令即可（因此才被称为 “程序直接控制方式”）
• 缺点：CPU 和 IO 设备只能串行工作，CPU 需要一直轮询检查，长期处于 “忙等” 状态，CPU 利用率低

2. 中断驱动方式

• 引入中断机制。

• 执行流程：

  1. 由于 IO 设备速度很慢，因此在 CPU 发出读写命令后，可将等待 IO 的进程阻塞，先切换到别的进程执行。
  2. 当 IO 完成后，控制器会向 CPU 发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断
  3. 处理中断的过程中，CPU 从 IO 控制器读一个字的数据传送到 CPU 寄存器，再写入主存。
  4. CPU 恢复等待 IO 的进程（或其他进程）的运行环境，然后继续执行。
     

• 注意：

  1. CPU 会在每个指令周期的末尾检查中断
  2. 中断处理过程中需要保存、恢复进行的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能。

• CPU 干预频率：每次 IO 操作开始之前、完成之后需要 CPU 介入。等待 IO 完成的过程中 CPU 可以切换到别的进程执行。

• 数据传送的单位：每次读写一个字

• 数据的流向

  1. 读操作（数据输入）：IO 设备 → CPU → 内存
  2. 写操作（数据输出）：内存 → CPU → IO 设备

• 优点：与程序直接控制方式相比，在中断驱动方式中，IO 控制器会通过中断信号主动报告 IO 已完成，CPU 不再需要不停地轮询。CPU 和 IO 设备可并行工作，CPU 利用率得到明显提升。

• 缺点：每个字在 IO 设备与内存之间的传输，都需要经过 CPU。而频繁的中断处理会消耗较多的 CPU 时间。

3. DMA 方式

• DMA方式（Direct Memory Access，直接存储器存取）

• 执行流程：

  1. CPU 指明此次要进行的操作（如：读操作），并说明要读入多少数据、数据要存放在内存的什么位置、数据在外部设备上的地址（如：在磁盘上的地址）
  2. 控制器会根据 CPU 提出的要求完成数据的读写工作，整块数据的传输完成后，才向 CPU 发出中断信号。
     

• CPU 干预频率：仅在传送一个或多个数据块的开始和结束时，才需要 CPU 干预。

• 数据传送的单位：每次读写一个或多个块（每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的）

• 数据的流向（不再经过 CPU）

  1. 读操作（数据输入）：IO 设备 → 内存
  2. 写操作（数据输出）：内存 → IO 设备

• DMA 控制器

  • 和 IO 控制器类似，由 主机-控制器接口、IO 控制逻辑、块设备-控制器接口 组成。
  • 主机-控制器接口包括：DR（Data Register，数据寄存器）、MAR（Memory Address Register，内存地址寄存器）、DC（Data Counter，数据计数器）、CR（Command Register，命令 / 状态寄存器）
    

• 优点：数据传输以“块”为单位，CPU 介入频率进一步降低。数据的传输不再需要先经过 CPU 再写入那内存，数据传输效率进一步增加。CPU 和 IO 设备的并行性得到提升。

• 缺点：CPU 每发出一条 IO 指令，只能读写一个或多个连续的数据块。如果要读写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU 要分别发出多条 IO 指令，进行多次中断处理才能完成。

4. 通道控制方式

• 通道：一种硬件，可以理解为是“阉割版的CPU”。通道可以识别并执行一系列通道指令
• 执行流程：
  1. CPU 向通道发出 IO 指令，指明通道程序在内存中的位置，并指明要操作的是哪个 IO 设备。之后 CPU 就切换到其他进程执行了。
     • 通道程序：可以理解为是任务清单。
  2. 通道执行内存中的通道程序（其中指明了要读入 / 写出多少数据，读写的数据应放在内存的什么位置等信息）
  3. 通道执行完规定的任务后，向 CPU 发出中断信号，之后 CPU 对中断进行处理
     
• CPU 干预频率：极低，通道会根据 CPU 的指令执行相应的通道程序，只有完成一组数据块的读写后才需要发出中断信号，请求 CPU 干预。
• 数据传送的单位：每次读写一组数据块
• 数据的流向（在通道的控制下进行）
  1. 读操作（数据输入）：IO 设备 → 内存
  2. 写操作（数据输出）：内存 → IO 设备
• 优点：CPU、通道、IO 设备可并行工作，资源利用率极高
• 缺点：实现复杂，需要专门的通道硬件支持。

5. 四种方式对比

	完成一次读 / 写的过程	CPU 干预频率	每次 I/O 的数据传输单位	数据流向	优缺点
程序直接控制方式	CPU 发出 I/O 命令后需要不断轮询	极高	字	设备 → CPU → 内存 内存 → CPU → 设备	每一个阶段的优点都是解决了上一阶段的最大缺点。 总的来说，整个发展过程就是要尽量减少 CPU 对 I/O 过程的干预，把 CPU 从繁杂的 I/O 控制事务中解脱出来，以便更多地去完成数据处理任务。
中断驱动方式	CPU 发出 I/O 命令后可以做其他事，本次 I/O 完成后设备控制器发出中断信号	高	字	设备 → CPU → 内存 内存 → CPU → 设备
DMA 方式	CPU 发出 I/O 命令后可以做其他事，本次 I/O 完成后 DMA 控制器发出中断信号	中	块	设备 → 内存 内存 → 设备
通道控制方式	CPU 发出 I/O 命令后可以做其他事。通道会执行通道程序以完成 I/O，完成后通道向 CPU 发出中断信号	低	一组块	设备 → 内存 内存 → 设备

四、IO 软件层次结构

• 软件层次依次为
  • 用户层软件：假脱机技术（SPOOLing技术）
  • IO 系统（IO 核心子系统），属于操作系统的内核部分：
    • 设备独立性软件：也称为系统调用处理层，主要功能有 IO 调度、设备保护、设备分配与回收、缓冲区管理
    • 设备驱动程序、中断处理程序。
• 硬件设备：由机械设备和电子设备组成（IO 控制器）。
• 每一层会利用其下层提供的服务，实现某些功能，并屏蔽实现的具体细节，向高层提供服务（封装思想）
• 直接设计到硬件具体细节、且与中断无关的操作肯定是在设备驱动程序层完成的；没有涉及硬件的、对各种设备都需要进行的管理工作都是在设备独立性软件层完成的。
  

1. 用户层软件

• 用户层软件实现了与用户交互的接口，用户可直接使用该层提供的、与 IO 操作相关的库函数对设备进行操作。
  • 比如：printf("123")
• 用户层软件将用户请求翻译成格式化的 IO 请求，并通过“系统调用”请求操作系统内核的服务
  • 比如：printf("123") 会被翻译成等价的 write 系统调用，用户层软件也会在系统调用时填入相应参数。
• Windows 操作系统向外提供的一系列系统调用，但是由于系统调用的格式严格，使用麻烦，因此在用户层上封装了一系列更方便的库函数接口供用户使用（Windows API）

2. 设备独立性软件

• 设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能都在这一层实现。
• 主要实现的功能：
  1. IO 调度：用某种算法确定一个好的顺序来处理各个 IO 请求。如：磁盘调度、打印机。
  2. 向上层提供统一的调用接口（如 read / write 系统调用）
  3. 设备保护
     • 原理类似于文件保护。设备被看作是一种特殊的文件，不同用户对各个文件的访问权限是不一样的，同理，对设备的访问权限也不一样。
  4. 差错处理
     • 设备独立性软件需要对一些设备的错误进行处理
  5. 设备的分别与回收
  6. 数据缓冲区管理
     • 可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异
  7. 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序
     • 用户或用户层软件发出 IO 操作相关系统调用的系统调用时，需要指明此次要操作的 IO 设备的逻辑设备名
     • 设备独立性软件需要通过“逻辑设备表（LUT，Logical Unit Table）”来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序。
     • 操作系统可以采用两种方式管理逻辑设备表（LUT）：
       1. 第一种方式，整个系统只设置一张 LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统。
       2. 第二种方式，为每个用户设置一张 LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登陆时为其建立一个用户管理进程，而 LUT 就存放在用户管理进程的 PCB 中。

3. 设备驱动程序

• 驱动程序一般会以一个独立进程的方式存在。
• 主要负责对硬件设备的具体控制，将上层发出的一系列命令（如 read / write）转化成特定设备 “能听得懂” 的一系列操作。包括设置设备寄存器、检查设备状态等。
• 不同的 IO 设备由不同的硬件特性，具体细节只有设备的厂家才知道。因此厂家需要根据设备的硬件特性设计并提供相应的驱动程序。

4. 中断处理程序

• 当 IO 任务完成时，IO 控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。
• 中断处理程序的处理流程：

五、I/O 应用程序接口

• 用户层的应用程序无法用一个统一的系统调用接口来完成所有类型设备的 IO。
• I/O 应用程序接口可分为 字符设备接口、块设备接口、网络设备接口。处于用户层IO软件和设备独立性软件之间。
  

1. 字符设备接口

• 例如 键盘、打印机，不可寻址
• 使用 get / put 系统调用：向字符设备读 / 写一个字符。

2. 块设备接口

• 例如 磁盘，可寻址
• 使用 read / write 系统调用：向块设备的读写指针位置读写多个字符
• 使用 seek 系统调用：修改读写指针位置

3. 网络设备接口

• 例如 网络控制器（网卡）
• 又称网络套接字（socket）接口
  • 网络套接字：申请一片内核存储空间，这片空间用于接收和发生数据。
• 使用 socket 系统调用：创建一个网络套接字，需指明网络协议（TCP、UDP）
• 使用 bind 系统调用：将套接字绑定到某个本地端口
• 使用 connect 系统调用：将套接字连接到远程地址
• 使用 read / write 系统调用：从套接字读写数据
  

4. 阻塞 IO / 非阻塞 IO

• 阻塞 IO：应用程序发出 IO 系统调用，进程需转为阻塞态等待。
  • 比如：字符设备接口 —— 从键盘读一个字符 get
• 非阻塞 IO：应用程序发出 IO 系统调用，系统调用可迅速返回，进程无需阻塞等待。
  • 比如：块设备接口 —— 往磁盘写数据 write

六、设备驱动程序接口

• 设备驱动程序接口位于设备独立性软件和设备驱动程序之间。
• 若各公司开发的设备驱动程序接口不统一，则操作系统很难调用设备驱动程序。
• 操作系统规定好设备驱动程序的接口标准，各厂商必须按要求开发设备驱动程序。
  

七、假脱机技术（SPOOLing技术）

• 假脱机技术，又称 SPOOLing 技术，是用软件的方式模拟脱机技术。因此在用户软件层实现。
• SPOOLing 技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

1. 脱机技术

• 脱机输入 / 输出技术：脱离主机的控制进行的输入 / 输出操作。
• 手工操作阶段：主机主要从 IO 设备获得数据，由于设备速度慢，主机速度快，人机速度矛盾明显，主机要浪费很多时间来等待设备。
• 脱机技术优点：
  1. 缓解了 CPU 与慢速 IO 设备的速度矛盾，实现预输入、缓输出。
  2. 即使 CPU 在忙碌，也可以提前将数据输入到磁带；
  3. 即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。

2. 输入井和输出井

• 输入井和输出井：是系统在磁盘上开辟出的两个存储区域。
• 输入井：模拟脱机输入时的磁带，用于收容 IO 设备输入的数据
• 输出井：模拟脱机输入时的磁带，用于收容用户进程输出的数据

3. 输入进程和输出进程

• 要实现 SPOOLing 技术，必须要有多道程序技术的支持。系统会建立 “输入进程” 和 “输出进程”
• 输入进程：模拟脱机输入时的外围控制机
• 输出进程：模拟脱机输出时的外围控制机

4. 输入缓冲区和输出缓冲区

• 操作系统会在系统中开辟输入缓冲区和输出缓冲区，作为输入输出时的中转站
• 输入缓冲区：在输入进程的控制下，输入缓冲区用于暂存从输入设备输入的数据，之后再转存到输入井中。
• 输出缓冲区：在输出进程的控制下，输出缓冲区用于暂存从输出井送来的数据，之后再传送给输出设备上。

5. 共享打印机原理分析

• 独占式设备：只允许各个进程串行使用的设备。
• 共享设备：允许多个进程 “同时” 使用的设备（宏观上同时使用，微观上可能是交替使用）。
• 共享打印机：使用 SPOOLing 技术实现，当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
  1. 在磁盘输出井为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打印的数据送入其中；
  2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。
• 当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。

八、设备的分配与回收

• 在设备独立性软件层实现。

1. 设备分配时应考虑的因素

1. 设备固有属性：独占设备、共享设备、虚拟设备
   • 独占设备：一个时段只能分配给一个进程（如打印机）
   • 共享设备：可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用
   • 虚拟设备：采用 SPOOLing 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用
2. 设备分配算法：先来先服务、高优先级优先、短任务优先
3. 设备分配的安全性：安全分配方式
   • 安全分配方式
     • 为进程分配一个设备后就将进程阻塞，本次 IO 完成后才将进程唤醒。即 一个时段内每个进程只能使用一个设备
     • 优点：破坏了请求和保持条件，不会死锁
     • 缺点：对于一个进程来说，CPU 和 IO 设备只能串行工作
   • 不安全分配方式
     • 进程发出 IO 请求后，系统为其分配 IO 设备，进程可继续执行，之后还可以发出新的 IO 请求。只有某个 IO 请求得不到满足时才将进程阻塞。即 一个进程可以使用多个设备
     • 优点：进程的计算任务和 IO 任务可以并行处理，使进程迅速推进
     • 缺点：有可能发生死锁

2. 静态分配和动态分配

• 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源（破坏“请求和保持”条件，不会发生死锁）
• 动态分配：进程运行过程中动态申请设备资源。

3. 设备分配管理中的数据结构

• 设备、控制器、通道 之间的关系： 一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。
  
• 设备控制表（DCT）：系统为每个设备配置一张 DCT，用于记录设备情况：
  • 设备类型：如打印机、扫描仪等
  • 设备标识符：物理设备名，系统中的每个设备的物理设备名唯一
  • 设备状态：忙碌 / 空闲 / 故障 等
  • 指向控制器表的指针：每个设备由一个控制器控制，该指针可找到相应控制器的信息
  • 重复执行次数或时间：当重复执行多次 IO 操作后仍不成功，才认为此次 IO 失败
  • 设备队列的队首指针：指向正在等待该设备的进程队列（由进程 PCB 组成队列）
• 控制器控制表（COCT）：每个设备控制器都会对应一张 COCT，操作系统根据 COCT 的信息对控制器进行操作和管理：
  • 控制器标识符：各个控制器的唯一 ID
  • 控制器状态：忙碌 / 空闲 / 故障 等
  • 指向通道表的指针：每个控制器由一个通道控制，该指针可找到相应通道的信息
  • 控制器队列的队首指针、队尾指针：指向正在等待该控制器的进程队列
• 通道控制表（CHCT）：每个通道都会对应一张 CHCT。操作系统根据 CHCT 的信息对通道进行操作和管理。
  • 通道标识符：各个通道的唯一 ID
  • 通道状态：忙碌 / 空闲 / 故障 等
  • 与通道链接的控制器表首址：可通过该指针找到该通道管理的所有控制器相关信息（COCT）
  • 通道队列的队首指针、队尾指针：指向正在等待该通道的进程队列
• 系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。每个表目记录设备的设备类型、设备标识符、DCT、驱动程序入口。

4. 设备分配的步骤

1. 根据进程请求的物理设备名查找 SDT（系统设备表）
2. 根据 SDT（系统设备表） 找到 DCT（设备控制表），若设备忙碌则将进程 PCB 挂到设备等待队列，不忙碌则将设备分配给进程
3. 根据 DCT（设备控制表）找到 COCT（控制器控制表），若控制器忙碌则将进程 PCB 挂到控制器等待队列，不忙碌则将控制器分配给进程
4. 根据 COCT（控制器控制表）找到 CHCT（通道控制表），若通道忙碌则将进程 PCB 挂到通道等待队列，不忙碌则将通道分配给进程

• 只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动 IO 设备进行数据传送
• 缺点：
  1. 用户编程时必须使用物理设备名，底层细节对用户不透明，不方便编程
  2. 若换了一个物理设备，则程序无法允许
  3. 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

5. 设备分配步骤的改进

• 改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需要提供逻辑设备名
• 步骤：
  1. 根据进程请求的逻辑设备名查找 SDT （系统设备表），用户编程时提供的逻辑设备名就是设备类型
  2. 查找 SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项
  3. 三四步 和前面一样
• 逻辑设备表（LUT）建立了逻辑设备名和物理设备名之间的映射关系。
• 如果用户进程通过相同的逻辑设备名请求使用设备，则操作系统通过 LUT 即可知道用户进程实际要使用的是哪个物理设备，并且也能知道该设备的驱动程序入口地址。

九、缓冲区管理

1. 缓冲区概念

• 缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
  • 使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如快表）
  • 一般情况下，更多的是利用内存作为缓冲区，设备独立性软件的缓冲区管理就是要组织管理好这些缓冲区。

2. 缓冲区作用

1. 缓和 CPU 与 IO 设备之间速度不匹配的矛盾
2. 减少对 CPU 的中断频率，放宽对 CPU 中断相应时间的限制
3. 解决数据粒度不匹配的问题
4. 提高 CPU 与 IO 设备之间的并行性

3. 单缓冲

• 单缓冲：假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（一个缓冲区的大小一般就是一个块）
• 注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
• 设 T 为数据从设备到缓冲区的时间，C 为 CPU 处理时间，M 为数据从缓冲区到工作区（内存）的时间，则处理一块数据平均耗时：$$平均耗时：Max(C,T)+M$$
• 若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输。

4. 双缓冲

• 双缓冲：假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区
• 采用双缓冲策略，处理一个数据块的平均耗时为$$平均耗时：Max(T,C+M)$$
• 若两个相互连通的机器设置双缓冲区，在同一时刻可以实现双向的数据传输。

5. 循环缓冲区

• 将多个大小相等的缓冲区链接成一个循环队列。
• 系统会定义两个指针：
  1. in 指针：指向下一个可以冲入数据的空缓冲区
  2. out 指针：指向下一个可以取出数据的满缓冲区

6. 缓冲池

• 缓冲池：由系统中共用的缓冲区组成。
• 这些缓冲区按使用状况可以分为
  1. 空缓存队列
  2. 装满输入数据的缓冲队列（输入队列）
  3. 装满输出数据的缓冲队列（输出队列）
• 根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：
  1. 用于收容输入数据的工作缓冲区（hin）
  2. 用于提取输入数据的工作缓冲区（sin）
  3. 用于收容输出数据的工作缓冲区（hout）
  4. 用于提取输出数据的工作缓冲区（sout）
• 输入输出步骤：
  1. 输入进程请求输入数据：从空缓冲队列中取出一块作为收容输入数据的工作缓冲区（hin）。充满数据后将缓冲区挂到输入队列队尾
  2. 计算进程想要取得一块输入数据：从输入队列中取得一块充满输入数据的缓冲区作为提取输入数据的工作缓冲区（sin）。缓冲区读空后挂到空缓冲区队列
  3. 计算进程想要将准备好的数据冲入缓冲区：从空缓冲队列中取出一块作为收容输出数据的工作缓冲区（hout）。数据充满后将缓冲区挂到输出队列队尾
  4. 输出进程请求输出数据：从输出队列中取得一块冲满输出数据的缓冲区作为提取输出数据的工作缓冲区（sout）。缓冲区读空后挂到空缓冲区队列

十、磁盘的结构

1. 磁盘、磁道、扇区

• 磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。
• 磁盘的盘面被划分为一 “圈圈” 磁道。
• 一个磁道被划分为一个个扇区，每个扇区就是一个磁盘块。各个扇区存放的数据量相同（如1KB），因此最内侧磁道上的扇区面积最小，数据量最大。
• 磁盘分类，根据磁头是否可移动分为：
  1. 磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道。
  2. 磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头。
• 磁盘分类，根据盘片是否可更换分为：
  1. 盘片可以更换的称为可换盘磁盘
  2. 盘片不可更换的称为固定盘磁盘

2.盘面、柱面

• 一个盘片可能会有两个盘面
• 每个磁盘对应一个磁头
• 所有的磁头都是连在同一个磁臂上的，因此所有磁头只能 “共进退”
• 所有盘面中相对位置相同的磁道组成柱面
• 可用磁盘的物理地址：（柱面号，盘面号，扇区号）定位任意一个磁盘块。

3. 根据地址读取 “块”

1. 根据柱面号移动磁臂，让磁头指向指定柱面
2. 激活指定盘面对应的磁头
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对应扇区的读 / 写。

十一、磁盘调度算法

1. 一次磁盘读 / 写操作需要的时间

• 寻找时间（寻道时间）$T_s$：在读 / 写数据前，将磁头移动到指定磁道所花的时间。
  1. 启动磁头臂耗时为 s；
  2. 移动磁头，假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。
  3. 则：寻道时间 $T_s=s+m\times n$
• 延迟时间 $T_R$：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。
  1. 设磁盘转速为 r（单位：转/ 秒，或转 / 分）
  2. 转一圈需要的时间：$T_R=\frac{1}{r}$
  3. 则平均所需的延迟时间 $T_R=\frac{1}{2}\times \frac{1}{r}=\frac{1}{2r}$
• 传输时间$T_t$：从磁盘读出或向磁盘写入数据所经历的时间。
  1. 设磁盘转速为 r，此次读 / 写的字节数为 b，每个磁道上的字节数为 N；
  2. 则传输时间 $T_t=\frac{1}{r}\times \frac{b}{N}=\frac{b}{rN}$
• 总的平均存取时间：$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$
• 延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。

2. 先来先服务算法（FCFS）

• 算法：根据进程请求访问磁盘的先后顺序进行调度。
• 优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过得去。
• 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，性能很差，寻道时间长。

假设磁头的初始位置是 100 号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 45+3+19+21+72+70+10+112+146=498个磁道
• 平均寻道长度：响应一个请求平均需要移动 498/9=55.9 个磁道

3. 最短寻找时间优先（SSTF）

• 算法：优先处理的磁道是与当前磁头最近的磁道。
• 可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）
• 优点：性能较好，平均寻道时间短
• 缺点：可能产生饥饿现象，磁头可能在一个小区域内来回移动

假设磁头的初始位置是 100 号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (100-18)+(184-18)=248 个磁道
• 平均寻道长度：响应一个请求平均需要移动 248/9=27.5 个磁道

4. 扫描算法（SCAN）

• 由于磁头移动的方式很想电梯，因此也成为 电梯算法。
• 算法：对 SSTF 算法的改进，只有磁头移动到最外侧磁道的时候才往内移动，移动到最内侧磁道的时候才往外移动。
• 优点：性能较好，平均寻道时间最短，不会产生饥饿现象
• 缺点：
  1. 只有到达最边上的磁道时才能改变磁头移动方向
  2. 对于各个位置磁道的响应频率不平均

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (200-100)+(200-18)=282 个磁道
• 平均寻道长度：响应一个请求平均需要移动 282/9=31.3 个磁道

5. LOOK 调度算法

• 算法：对 SCAN 算法（针对第一个缺点）的改进，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动变观察，因此叫 LOOK）
• 优点：比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (184-100)+(184-18)=250 个磁道
• 平均寻道长度：响应一个请求平均需要移动 250/9=27.5 个磁道

6. 循环扫描算法（C-SCAN）

• 算法：对 SCAN 算法（针对第二个缺点）的改进，规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
• 优点：比起 SCAN 来，对于各个位置磁道的响应频率很平均
• 缺点：只有到达最边上的磁道时才能改变磁头移动方向。比起 SCAN 算法平均寻道时间更长。

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (200-100)+(200-0)+(90-0)=390 个磁道
• 平均寻道长度：响应一个请求平均需要移动 390/9=43.3 个磁道

7. C-LOOK 调度算法

• 算法：对 C-SCAN 算法的改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
• 优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (184-100)+(184-18)+(90-18)=322 个磁道
• 平均寻道长度：响应一个请求平均需要移动 322/9=35.8 个磁道

十二、减少磁盘延迟时间的方法

• 延迟时间概念
  • 延迟时间：将目标扇区转到磁头下面所花的时间
  • 磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的延迟时间。
• 方法一：交替编号 —— 让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。
• 方法二：错位命令 —— 让相邻盘面的扇区编号 “错位”。与交替编号的原理相同。
• 读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构：在读取地址连续的磁盘块时，不需要移动磁头，可以减少磁头移动消耗的时间。

十三、磁盘的管理

1. 磁盘初始化

1. 进行 低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。
   • 一个扇区通常分为头、数据区域（如512B大小）、尾三个部分组成。
   • 管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验山区中的数据是否发生错误）
2. 将磁盘分区，每个分区由若干柱面组成（即分为 C、D、E盘）
3. 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表等）

2. 引导块

• 计算机开机时需要进行一系列初始化的工作，这些初始化工作时通过执行初始化程序（自举程序）完成的。
  • 初始化程序（自举程序）将很小一部分存放在 ROM 中，ROM 中的数据在出厂时就写入了，并且以后不能再修改。
  • 完整的自举程序放在磁盘的启动块（即引导块 / 启动分区）上，启动块位于磁盘的固定位置。
• 开机时计算机先运行 “自举装入程序”，通过执行该程序就可找到引导块，并将完整的 “自举程序” 读入内存，完成初始化
• 拥有启动分区的磁盘称为启动磁盘或系统磁盘（如 C盘）

3. 坏块的管理

• 坏块：坏了、无法正常使用的扇区就是坏块。
• 这属于硬件故障，操作系统无法修复。应该把坏块标记出来，一面错误地使用到它。
• 对于简单的磁盘，可以在逻辑格式化时对整个磁盘进行坏块检查，标明哪些扇区是坏扇区（如：在 FAT 表上标明），坏块对操作系统不透明
• 对于复杂的洗盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时九江坏块链进行初始化。会保留一些 “备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

十四、固态硬盘 SSD

• 原理：基于闪存技术（Flash Memory），属于电可擦除 ROM，即 EEPROM
• 组成
  1. 闪存翻译层：负责翻译逻辑块号，找到对应页（Page）
  2. 存储介质：多个闪存芯片（Flash Chip），每个芯片包含多个块（block），每个块包含多个页（page）
• 读写性能特性
  • 以页（page）为单位读 / 写 —— 相当于磁盘的扇区
  • 以块（block）为单位擦除，擦干净的块，其中的每页都可以写一次，读无限次
  • 支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址
  • 读快、写慢。要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的（擦除过的）块中，再写入新的页
• 与机械硬盘相比的特点
  1. SSD 读写速度快，随机访问性能高，用电路控制访问位置；机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
  2. SSD 安静无噪音、耐摔抗震、能耗低、造假更贵
  3. SSD 的一个块被擦除次数过多（重复写同一个块）可能会坏掉，机械硬盘的扇区不会因为写的次数太多而坏掉
• 磨损均衡技术
  • 思想：将擦除平均分布在各个块上，以提升使用寿命
  • 动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块
  • 静态磨损均衡：SSD 监测并自动进行数据分配、迁移，让老旧的闪存块承担以读为主的储存任务，让较新的闪存块承担更多的写任务。