考研冲刺前的总结 —— 操作系统

并发#

并发指的是两个或多个事件在同一时间间隔内发生，宏观上同时，微观上交替。

单处理机上也存在并发，靠的是进程调度和时间片轮转，所以并发不需要并行。

需要注意的是，并发是操作系统存在的基础，没有并发就退化成单道程序，也就不需要操作系统来调度了。

共享#

共享指的是系统中的资源可以被多个并发执行的进程共同使用，分为互斥共享和同时访问两种。

互斥共享的资源是临界资源，例如打印机、共享变量，一个进程用的时候另一个必须等；同时访问的资源例如磁盘文件，可以同时读。

需要注意，并发和共享互为存在条件：没有并发就谈不上共享，没有共享并发进程也无法协作。

虚拟#

虚拟是把一个物理实体变成若干个逻辑上的对应物，分为时分复用和空分复用。

时分复用的例子是虚拟处理器，多个进程轮流使用一个 CPU；空分复用的例子是虚拟存储器，每个进程都以为自己独占 4GB 的地址空间。

需要注意的是，虚拟技术的前提是每一路逻辑实体在宏观上都能推进，切换的代价要足够小，否则虚拟就没有意义。

异步#

异步指的是进程以不可预知的速度向前推进，走走停停。

原因在于进程共享资源、竞争 CPU，谁先拿到资源谁就继续执行，所以程序的执行顺序和执行时间都不确定。

需要注意的是，异步是并发带来的结果，也正是因为异步，才需要同步机制来约束进程之间的推进顺序。

辨析并行与并发与多任务#

对于多处理机，可以实现并行。

多任务指的是操作系统可以同时运行多个任务，并发就够了，不需要并行。

操作系统的功能与服务#

操作系统管四件事：进程管理（创建、调度、同步、通信）、内存管理（分配回收、地址变换、保护共享）、文件管理（目录、存取、保护）、设备管理（分配、驱动、缓冲）。

对上层提供的服务分两类：

• 面向用户的接口，也就是命令接口和图形界面，用户直接使用；
• 面向程序的接口，也就是系统调用，程序通过它请求内核服务。

此外操作系统还要负责资源分配、记账和出错处理。

需要注意，操作系统还有一个说法是“扩充机器”：它把裸机包装成一台功能更强、更好用的虚拟机，用户看到的是文件、进程这些概念，而不是磁盘块和寄存器。

手工操作与脱机 IO#

早期是手工操作，用户把纸带、卡片直接装进机器，独占 CPU，人机串行，效率极低。

脱机 IO 是为了解决 CPU 和慢速外设的矛盾：用一台卫星机把输入数据先写到磁带上，主机只和磁带打交道，主机和外设就能并行起来。

需要注意，脱机 IO 里的“脱机”指的是脱离主机，不是脱离设备。

批处理阶段#

单道批处理，内存里只有一道程序，CPU 和外设串行工作，利用率低。

多道批处理，内存里同时放多道程序，一道等 I/O 时切换另一道，CPU 和 I/O 可以并行，但交互性差，作业周转时间长。

主要的缺点为“无法实时交互”。

需要注意，多道批处理的两个关键支撑是中断和 DMA，没有它们就没法在 I/O 期间切换程序。

分时操作系统#

可以理解为 RR 调度。

多用户同时。

及时性不错，但不能保证截止时间，这一点要和实时系统区分开。

需要注意，分时系统把 CPU 按时间片轮流分给各终端用户，用户感觉自己独占机器，这就是“虚拟”的一种体现。

实时操作系统#

软实时和硬实时。

例如抢票系统属于软实时，而银行金融交易属于硬实时。

还需要注意，这个时间是规定时间，而不是具体的某个时间。

库函数与系统调用#

库函数一般是用户态的，但是系统调用是内核态的。

典型的例子有数学函数，例如 sin、cos 等。

即便是 malloc 也属于用户态，因为其本质是在堆区操作，而堆区是用户内存的一部分。

然而，库函数例如 scanf，需要进入内核态。但是，和 trap 指令类似的，它们也是在用户态进行的，只是委托操作系统完成。

内核态#

从虚拟存储系统的角度分析，假设一个 $4\text{ GB}$ 的地址空间，内核态可以访问全部的地址空间，而用户态只能访问 $3\text{ GB}$ 的地址空间。

例如内核态占据 3-4GB 的地址空间，用户态占据 0-3GB 的地址空间。虽然每个进程的虚拟地址都是独占的 4GB 地址空间，但是其中高地址的空间却是一样的，即从物理内核存储映射到了该逻辑地址。

内核态主要可以干 IO 操作，进程调度等，尤其需要注意：

open 和 read 操作都属于系统调用，属于内核态。

中断与异常#

其实这个概念来自于计组，异常又称内中断，中断又称外中断。

默认情况下，只说中断一般指的是外中断。

异常分为三种模式，陷阱、故障、终止。

陷阱也就是操作系统中最常用的，通过陷阱陷入内核态。

需要注意，是用户使用 trap 指令进入内核态。

这种情况下，处理完陷阱后，需要到下一条指令继续运行。

故障例如缺页、除以 0 等。

这种情况下，处理完故障后，需要回到当前指令重新运行。

终止是程序发生了严重错误，需要立即终止，不需要再执行后续的指令。

系统调用的过程#

用户程序执行一条陷入指令（trap、syscall），把系统调用号放在约定的寄存器里，参数按约定放在寄存器或栈上。

CPU 响应后从用户态切到内核态，根据系统调用号查系统调用表，找到对应的服务例程并执行，返回值放在约定的寄存器里。

最后执行中断返回指令，切回用户态，从陷入指令的下一条继续执行。

需要注意，系统调用是用户程序进入内核的唯一合法入口，用户程序不能直接执行特权指令，也不能直接访问内核地址空间。

系统调用的参数传递有三种方式：放寄存器、放用户栈再把栈地址传进去、指令里直接给参数。参数多于寄存器数量时用第二种。

分层#

一层一层调用，速度慢，但是易于调试。

模块化#

某个模块需要调另一个模块的功能，一个模块出错可能会影响另一个模块。

宏内核#

效率高，但是较为复杂。

微内核#

效率较低（因为很多功能都需要打断当前进程跑去请求内核完成）

可扩展性好。

外核#

冷门考点，但也需要知道是什么。

外核的思想是把物理资源（内存块、磁盘块）直接分配给用户进程，内核只负责资源的分配与保护，不负责抽象。

进程自己决定怎么用这些资源，比如自己实现文件系统、自己管理内存。这样省掉了内核的抽象层，灵活高效，但实现复杂、隔离性差。

第一类虚拟机#

硬件上划分出不同的区域跑不同的操作系统，即硬件之上是第一类虚拟机管理程序，在这之上分别运行了不同的操作系统。

第二类虚拟机#

宿主机运行虚拟化软件，虚拟化软件上运行另一个操作系统。本质上全是用户态进程。

需要辨析，虚拟化软件的代码量肯定小于一个操作系统。误解的原因是将系统镜像理解为虚拟化软件代码的一部分。

进程与程序#

进程是程序的一次执行过程，是系统进行资源分配的基本单位。

进程和程序的区别在于：程序是静态的指令集合，可以长期存在；进程是动态的，有创建、运行、消亡的过程，是暂时的。同一个程序运行多次就是多个进程，各自有独立的 PCB 和地址空间。

进程有四个特征：动态性（最基本）、并发性、独立性、异步性。

需要注意，进程与程序的对应关系是多对多：一个程序可以对应多个进程，一个进程也可以先后执行多个程序。

PCB 的辨析#

PCB 是程序在创建的时候，由程序创建原语创建的。

其是一个进程存在的标志，并且 PCB 是进程存在的唯一标志。

PCB 里面存有父程序，队列，当前进程状态等。

比较重要的是页表始址（采用多级页表的时候是页目录表始址）

假设一个进程的物理地址是 16GB，逻辑地址是 4GB，并且分配高 1GB 给内核区。

那么每一个进程的高 1GB 都是内核区物理映射过来的，都是相同的。

主存空间辨析#

假设逻辑主存空间有 4GB，高 1GB 内存是内核态，低 3GB 内存是用户态。

那么对于一个进程，其逻辑地址可以理解为：

代码本体 - 全局变量 - 堆区 - 共享区 - 栈区 - 局部变量 - 内核区

其中，代码本题是地址最低的，堆区从低地址向高地址增长，而栈区从高地址向低地址增长。

进程的三态#

在进程调度的时候，即操作其 PCB，例如把 PCB 插入就绪队列。

就绪态，运行态，阻塞态。

1
               ┌──────────────┐
2
               │    就绪态    │ <────────────────────────┐
3
               │ (Ready State)│                          │
4
               └──────────────┘                          │
5
                  │        ▲                             │
6
        获得CPU   │        │ 时间片用完                  │ 事件完成
7
       (进程调度) │        │ (超时中断)                  │ (I/O完成)
8
                  ▼        │                             │
9
               ┌──────────────┐         ┌──────────────┐ │
10
               │    运行态    │ ───────>│    阻塞态    │ ─┘
11
               │(Running State)│ 等待事件│(Blocked State)│
12
               └──────────────┘ (请求I/O)└──────────────┘

做这种题的时候，最重要的是注意辨析题目的要求是什么态转什么态。

三态模型是最简化的，实际系统里还有两个状态：新建态和终止态。

• 新建态：PCB 已经分配，但进程还没被放入就绪队列，资源还没准备好；
• 终止态：进程已经结束，但 PCB 还没被回收，等待父进程或系统回收资源。

需要注意，这两个状态都不能被调度，所以讨论调度时三态够用，讨论进程生命周期时要补上。

再进一步还有挂起状态。挂起是把进程的映像调出到外存，腾出内存，分为就绪挂起和阻塞挂起：

• 就绪挂起：进程在外存，一旦调入内存就可以运行；
• 阻塞挂起：进程在外存，且还在等某个事件。

挂起和阻塞的区别在于，阻塞是等事件、进程还在内存，挂起是被换出、进程不在内存。阻塞挂起必须先等事件发生变成就绪挂起，才能被激活回内存；而就绪挂起可以直接激活成就绪态。

对于七状态模型，只要记住两条主线：就绪、运行、阻塞之间的转换靠调度和事件；挂起相关的转换靠换入换出。

进程控制#

进程控制就是操作系统用原语来改变进程状态，原语的执行必须一气呵成，不能被中断。

• 创建：分配 PCB，填入 PID、优先级、入口地址等，分配资源，插入就绪队列；
• 终止：回收资源，撤销 PCB，如果是父进程终止还要处理子进程；
• 阻塞：进程主动调用，保存现场，把 PCB 插入对应事件的等待队列，转入阻塞态；
• 唤醒：事件发生时由系统或其他进程调用，把 PCB 从等待队列移入就绪队列；
• 切换：保存当前进程的现场到 PCB，恢复下一个进程的现场。

需要注意，阻塞是进程自己主动的行为，唤醒是别人（或系统）的行为，一个进程不能唤醒自己，也不能把自己阻塞后立刻醒来。

PCB 的组织方式有两种：链接方式，把同一状态的 PCB 用链接字串成队列；索引方式，按状态建立索引表，表项指向 PCB。

进程与线程的数据#

不同进程之间不共享数据，所以对于不同进程的全局变量，不会引发竞争。

然而，由于线程没有独立的地址空间，是基于进程而生的，所以线程之间共享进程的数据，从而同一个进程的不同线程之间会引发竞争。

线程的三种方式#

• 用户级线程：由应用程序的线程库在用户空间管理，操作系统内核完全感知不到。优点是线程切换极快（不需要切换到内核态）；缺点是一个线程阻塞会导致整个进程都阻塞，且无法直接利用多核 CPU。

• 内核级线程：由操作系统内核直接创建、调度和管理。优点是能真正利用多核并行执行，一个线程阻塞不会影响其他线程；缺点是线程的创建和切换开销比较大，需要频繁进出内核态。

• m 对 n 级线程：前两者的混合模式，将 m 个用户级线程映射到 n 个内核级线程（通常 m ≥ n）。优点是结合了前两者的长处，既保持了快速切换，又能发挥多核优势且避免全盘阻塞；缺点是系统的设计与调度实现极其复杂。

任何用户级进程都可以直接运行，不需要额外适配。

对于这类题需要注意的事情就是不要搞混用户级进程和内核级线程。

内核级线程与用户级线程的调度#

用户级线程的调度由线程库在用户态完成，内核根本不知道线程的存在，它只调度进程。所以一个线程阻塞会导致整个进程阻塞，也无法利用多核。

内核级线程由内核调度，调度单位和分配单位都是线程，所以一个线程阻塞不影响其他线程，也能真正并行。

需要注意，用户级线程切换快，是因为不陷入内核；但内核看不到它，信号处理和阻塞系统调用都会作用在整个进程上。

调度的目标#

调度要在几个互相冲突的指标之间做平衡：

• CPU 利用率：尽量让 CPU 不空闲；
• 系统吞吐量：单位时间内完成的作业数；
• 周转时间：从提交到完成的时间，越短越好；
• 等待时间：进程在就绪队列里等的时间，越短越好；
• 响应时间：从提交请求到首次响应的时间，交互系统最看重这个。

需要注意，批处理系统重吞吐量和周转时间，分时系统重响应时间，实时系统重截止时间，题目里说“某系统”时可以据此判断该选哪个算法。

三类调度辨析#

• 高级调度：即作业调度。从外存的后备队列中挑选作业调入内存并为其创建进程。发生频率最低。

• 中级调度：即内存调度。当内存不足时，将暂时不能运行的进程调到外存（挂起态）腾出内存空间；等内存充裕且条件满足时再调回内存。发生频率中等。

• 低级调度：即进程调度（CPU 调度）。从就绪队列中选取一个进程，将 CPU 分配给它运行。发生频率最高（几十毫秒一次）。

进程调度的时机以及优先级变化#

具体题目具体分析，最重要的是搞清楚每一类任务导致从什么态变成什么态。

关于优先级变化，需要注意刚上处理机的进程不可以立刻降低优先级。考虑这样一种情况，采用的是优先级抢占式调度，如这么做，会导致一个进程刚上处理机就被撤下来。

调度的时机只有几类：

• 进程正常结束或异常终止；
• 进程主动阻塞，例如请求 I/O、等待信号量；
• 进程被唤醒，从阻塞变就绪；
• 时间片用完，或者更高优先级的进程到达（抢占式）。

需要注意，有些时刻不能调度：中断处理过程中、内核临界区内部、原子操作执行中。这几处如果切走，内核的数据结构可能正处在不一致的中间状态。

还要知道闲逛进程（idle）：就绪队列为空时，内核跑一个优先级最低的进程，它什么也不干，只在有中断时醒来。作用是让 CPU 永远有指令可执行，顺便省电。

进程调度的方式与参数#

抢占式调度与非抢占式调度。

注意一些概念：

• 周转时间：从提交到完成经历的总时间，$T_i=C_i-S_i$，$C_i$ 是完成时间，$S_i$ 是提交时间。

• 平均周转时间：$T=\frac{1}{n}\sum_{i=1}^{n}T_i$。

• 带权周转时间：衡量作业相对等待程度的指标，$W_i=\frac{T_i}{R_i}$，$R_i$ 是实际运行时间。比值恒 $\ge 1$，越接近 1 越好。

• 平均带权周转时间：$W=\frac{1}{n}\sum_{i=1}^{n}W_i$。

需要注意，平均周转时间衡量的是“快不快”，平均带权周转时间衡量的是“公不公平”：短作业被拖得越久，带权周转时间越大，所以后者对交互式系统更有意义。

做这种题一样需要注意辨析清楚题目里到底要我们干什么，求什么东西。

上下文切换与模式切换#

• 模式切换：CPU 在用户态与内核态之间的权限切换。当前运行的进程并没有改变，只需保存和恢复少量的硬件寄存器状态（如处理系统调用或硬件中断），开销较小。

• 上下文切换：CPU 控制权从一个进程转移到另一个进程。需要保存当前进程的完整 CPU 现场与虚拟内存映射，并加载新进程的状态，开销较大。

• 两者关系：上下文切换必然包含模式切换（调度必须在内核态执行）；但模式切换不一定会引发上下文切换（比如进程只是发了个简单的系统调用读取时间，处理完后仍回到该进程继续执行）。

CPU 调度方式#

• 先来先服务（FCFS）：按作业到达的先后顺序进行调度，即按提交、到达的顺序。
• 短作业优先（SJF）：按作业的执行时间长短进行调度，即执行时间最短的作业优先。短作业优先可以是非抢占式的，也可以是抢占式的，默认是非抢占式的
• 高响应比优先（HRRN）：按作业的响应比高低进行调度，即响应比最高的作业优先。响应比为 $R=\frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}=1+\frac{\text{等待时间}}{\text{要求服务时间}}$ 等待越久响应比越高，所以长作业不会饿死，这是它比 SJF 强的地方。
• 优先级调度：按作业的优先级高低进行调度，即优先级最高的作业优先。优先级调度可以是非抢占式的，也可以是抢占式的。可以分为静态优先级和动态优先级。此外可以注意，系统一般大于用户，交互一般大于非交互，IO 一般大于计算，但是，这并不是绝对的
• 时间片轮转（RR）：一个绝对公平的算法，时间片选取需要取舍，因为切换进程也需要时间
• 多级队列调度：根据进程属性永久固定分配到不同优先级的队列中，进程不能在队列之间移动。
• 多级反馈队列调度：队列内的调度算法不一定是同一种算法。多个队列的优先级由高到低且时间片依次增大，未在规定时间片内完成的进程会被自动降入下一级队列，允许进程在不同队列间动态移动。

多处理机调度（偏冷的考点）#

SMP 的调度面临两个核心矛盾：处理器亲和性和负载平衡。

当一个进程从一个 CPU 迁移到另一个 CPU 上时，应将第一个 CPU 的缓存设置为无效，然后重新填充第二个 CPU 的缓存。这种操作的代价较高，因此系统应尽量避免将进程从一个 CPU 移到另一个 CPU，而应尽量让一个进程运行在同一个 CPU 上，这称为处理器亲和性。

对于 SMP 系统，应尽量保证所有 CPU 的负载平衡（也称负载均衡），以便充分利用多处理机的优势。否则，一个或多个 CPU 会空闲，而其他 CPU 会处于高负载状态，且有一些进程处于等待状态。负载平衡应设法将负载平均分配到 SMP 系统的所有 CPU 上。

然而，负载平衡通常会抵消处理器亲和性带来的好处：保持一个进程运行在同一个 CPU 上的好处是可以利用它在该 CPU 的缓存，而将进程从一个 CPU 迁移到另一个 CPU 会失去这个好处。因此，在某些系统中，只有当不平衡达到一定程度后，才会触发进程迁移。

多处理机调度可以分为以下两种：

方案一：公共就绪队列

系统中仅设置一个公共就绪队列，所有 CPU 共享该队列。这种方案能很好地实现负载平衡，因为 CPU 一旦空闲，就会立刻从公共就绪队列中选择一个进程运行。缺点是各进程可能频繁地在不同的 CPU 上切换，处理器亲和性不好。

提升处理器亲和性的方法有两种：① 软亲和，指由调度程序尽量将一个进程保持在某个 CPU 上运行，但这个进程也可以迁移到其他 CPU 上。② 硬亲和，指由用户进程通过系统调用，主动请求系统将其绑定到固定的 CPU 上。例如，Linux 系统实现了软亲和，也支持硬亲和的系统调用。

方案二：私有就绪队列

系统为每个 CPU 设置一个私有就绪队列，当 CPU 空闲时，便从其对应的私有就绪队列中选择一个进程运行。这种方案很好地实现了处理器亲和性，缺点是必须进行负载平衡。

平衡负载的方法通常有两种：① 推迁移，指由一个特定的系统程序周期性地检查各 CPU 的负载，若发现不平衡，则从超载 CPU 的就绪队列中“推”出部分进程，迁移到空闲 CPU 的就绪队列，以实现负载平衡。② 拉迁移，指当某个 CPU 负载很低时，主动从超载 CPU 的就绪队列中“拉”取部分进程到自己的就绪队列。在实际系统中，推迁移和拉迁移常被结合使用。

临界资源与临界区#

临界资源可以理解为操作系统中只能被一个进程访问的资源，例如打印机。

临界区则指的是“代码”，临界区是访问临界资源的代码。

所以，对于每个进程而言，如果执行的是自己的代码，那么他们拥有自己的临界区。

同步与互斥的辨析#

假设 A 需要 B 提供的资源，那么就需要通过同步关系。

互斥可以理解为，当一个进程在访问临界资源时，其他进程不能访问该资源。

需要注意，不可以用同步和互斥简单的来判断信号初始量，而是要具体题目具体分析。

空闲让进：临界区空闲无进程时，允许一个请求进入的进程立即进入。

忙则等待：临界区已有进程在访问时，其他试图进入的进程必须等待。

有限等待：对请求访问的进程，应保证其在有限时间内能进入，防止饥饿死等。

让权等待：当进程暂时不能进入临界区时，应立即释放 CPU 资源（进入阻塞态），避免白白消耗 CPU 进行忙等。

软件实现同步与互斥#

单标法：

1
// 进程 P0
2
while (turn != 0);       // 进入区：检查轮到谁
3
critical section;        // 临界区
4
turn = 1;                // 退出区：把权力转交给 P1
5
remainder section;       // 剩余区
6

7
// 进程 P1
8
while (turn != 1);       // 进入区：检查轮到谁
9
critical section;        // 临界区
10
turn = 0;                // 退出区：把权力转交给 P0
11
remainder section;       // 剩余区

• 解决了什么问题： 实现了基本的互斥访问。由于全局只有一个 turn 变量指示权限，任何时刻最多只能有一个进程通过循环判定，保证了“忙则等待”。
• 发现了什么问题： 违背“空闲让进”准则。该算法强制两进程必须严格交替进入。若 $P_0$ 退出后临界区已空闲，但 $P_1$ 短期内或永远不想进入临界区，则 turn 将永远保持为 1，$P_0$ 哪怕急需进入临界区也会被永远挡在外面，造成资源严重浪费。

双标志先检查法

1
// 进程 P0
2
while (flag[1]);         // ① 进入区：先检查对方想不想进
3
flag[0] = true;          // ③ 进入区：自己表示想进
4
critical section;        // 临界区
5
flag[0] = false;         // 退出区：自己用完了
6
remainder section;       // 剩余区
7

8
// 进程 P1
9
while (flag[0]);         // ② 进入区：先检查对方想不想进
10
flag[1] = true;          // ④ 进入区：自己表示想进
11
critical section;        // 临界区
12
flag[1] = false;         // 退出区：自己用完了
13
remainder section;       // 剩余区

• 解决了什么问题： 打破了算法一中“必须严格轮流交替”的束缚，允许同一个进程在临界区空闲时连续多次使用临界区。
• 发现了什么问题： 违背“忙则等待”准则。核心缺陷在于“检查”与“设置”操作不是原子的。如果发生并发调度顺序 ① $\rightarrow$ ② $\rightarrow$ ③ $\rightarrow$ ④，两个进程都先发现对方为 false，随后各自将标志置为 true 并同时冲入临界区，导致互斥机制彻底崩溃。

双标志后检查法

1
// 进程 P0
2
flag[0] = true;          // ① 进入区：先表达自己的意图
3
while (flag[1]);         // ③ 进入区：再检查对方想不想进
4
critical section;        // 临界区
5
flag[0] = false;         // 退出区：自己释放
6
remainder section;       // 剩余区
7

8
// 进程 P1
9
flag[1] = true;          // ② 进入区：先表达自己的意图
10
while (flag[0]);         // ④ 进入区：再检查对方想不想进
11
critical section;        // 临界区
12
flag[1] = false;         // 退出区：自己释放
13
remainder section;       // 剩余区

• 解决了什么问题： 解决了算法二中“两进程同时闯入临界区”的问题。因为是“先举手示意、后查看对方”，确保了绝不会出现同时进入临界区的情况。
• 发现了什么问题： 违背“空闲让进”与“有限等待”准则（导致死锁/饥饿）。若发生交错执行 ① $\rightarrow$ ② $\rightarrow$ ③ $\rightarrow$ ④，双方都先将自己的标志置为 true，随后都在 while 循环中检测到对方为 true，进而相互等待对方退出。此时临界区明明是空的，却没有进程进得去，导致两进程永久卡死在进入区。

Peterson 算法

1
// 进程 P0
2
flag[0] = true;                    // 表达进临界区的意愿
3
turn = 1;                          // 主动谦让，优先允许对方进
4
while (flag[1] && turn == 1);      // 只有“对方想进 且 轮到对方”时才等待
5
critical section;                  // 临界区
6
flag[0] = false;                   // 退出区
7
remainder section;                 // 剩余区
8

9
// 进程 P1
10
flag[1] = true;                    // 表达进临界区的意愿
11
turn = 0;                          // 主动谦让，优先允许对方进
12
while (flag[0] && turn == 0);      // 只有“对方想进 且 轮到对方”时才等待
13
critical section;                  // 临界区
14
flag[1] = false;                   // 退出区
15
remainder section;                 // 剩余区

• 解决了什么问题： 完美综合了算法一和算法三，同时满足了：
  1. 空闲让进：若对方不想进（flag[j] == false），自己可以直接进。
  2. 忙则等待：若双方同时请求，turn 的最终赋值必定有先后，后写入 turn 的进程会把优先权让给先写入的进程，确保同一时刻仅一人进入。
  3. 有限等待：彼此都有谦让机制，不会形成永久死锁与无限饥饿。
• 发现了什么问题： 违背“让权等待”准则。未获得执行权限的进程依然在 while 循环中不断空转判断（即“忙等待”，Busy Waiting），白白霸占 CPU 时钟周期而没有主动进入阻塞挂起状态。

硬件实现同步与互斥#

中断屏蔽方法

1
// 进程进入与退出临界区的典型模式
2
...
3
关中断;              // 进入区：禁止 CPU 响应中断，防止发生进程调度
4
临界区代码段;        // 临界区：保证独占执行
5
开中断;              // 退出区：恢复 CPU 响应中断的能力
6
剩余区代码段;        // 剩余区
7
...

• 解决了什么问题： 从根源上杜绝了因“时钟中断”或“外部事件”导致的进程切换。由于单 CPU 下进程切换必须依赖中断，关中断后当前进程就能一口气将临界区执行完毕，极为简单地保证了互斥执行（忙则等待）。
• 发现了什么问题：
  1. 不适用于多处理器系统（SMP）：关中断指令仅对当前执行指令的这颗 CPU 核心有效，其他 CPU 核心上的进程仍然可以正常并发执行并闯入同一临界区。
  2. 严重破坏并发与系统安全性：若临界区较长，关中断会显著降低系统的并发能力和响应效率；关中断属于特权指令，若误开放给用户态程序，恶意进程一旦关中断后陷入死循环，整个操作系统将直接瘫痪崩溃。

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

1
// TS 指令的功能示意（硬件底层实现为原子操作，不可被中断）
2
boolean TestAndSet(boolean *lock) {
3
    boolean old;
4
    old = *lock;     // 1. 读取 lock 的旧值
5
    *lock = true;    // 2. 将 lock 强制置为 true（加锁）
6
    return old;      // 3. 返回旧值
7
}
8

9
// 进程实际调用的加锁逻辑
10
// lock 为全局共享变量，初值为 false（表示无锁）
11
while (TestAndSet(&lock));  // 进入区：原子测试并加锁，返回 true 则一直在此忙循环等待
12
critical section;           // 临界区
13
lock = false;               // 退出区：解锁，释放临界资源
14
remainder section;          // 剩余区

• 解决了什么问题： 将软件算法中致命的“检查锁”与“设置锁”合二为一，由硬件电路直接打包成一条原子指令。在进入临界区时绝不可能发生进程切换导致两个进程同时拿到锁；且由于 lock 是内存中的共享变量（配合硬件总线锁定），该机制完全适用于多处理器系统。
• 发现了什么问题：
  1. 违背“让权等待”准则：未抢到锁的进程必须在 while 循环中死死空转（忙等待），极大地空耗 CPU 时钟周期。
  2. 可能导致“饥饿”现象（违背有限等待）：当锁释放的一瞬间，所有正在自旋等待的 CPU/进程凭硬件总线抢占能力再次竞争，调度顺序完全随机，可能导致某些倒霉进程长期抢不到锁。

Swap 指令（XCHG 指令）

1
// Swap 指令的功能示意（硬件底层实现为原子操作，不可被中断）
2
void Swap(boolean *a, boolean *b) {
3
    boolean temp = *a;
4
    *a = *b;
5
    *b = temp;
6
}
7

8
// 进程实际调用的加锁逻辑
9
// lock 为全局共享变量，初值为 false（表示无锁）
10
// key 为当前进程的私有局部变量
11
boolean key = true;         // 局部变量初始化为 true（代表手里拿着一把关着的锁）
12
while (key != false) {      // 进入区：只有通过交换拿到 false（开锁状态），循环才结束
13
    Swap(&lock, &key);      // 原子地交换 key 与 lock 的内容
14
}
15
critical section;           // 临界区
16
lock = false;               // 退出区：释放锁
17
remainder section;          // 剩余区

• 解决了什么问题： 与 TS 指令本质相同，利用硬件原子交换，巧妙地用进程私有的 key = true 把共享的 lock = false“换”出来。一旦自己手里的 key 变成了 false，说明原先锁是开的，且此时共享的 lock 已经被自己置换成了 true（自动上了锁），同样能跨多核 CPU 完美实现原子加锁与互斥访问。
• 发现了什么问题：
  1. 违背“让权等待”准则：只要 key 一直是 true，进程就会不眠不休地在 while 循环里不断执行 Swap，占用处理机资源造成忙等。
  2. 可能导致“饥饿”现象：与 TS 指令相同，锁被放开的瞬间各个等待进程地位均等且随机争夺，无法从机制上严格保证每个等待进程都能在有限时间内获得临界区。

互斥锁 / 自旋锁#

1
// 互斥锁的数据定义与操作（acquire 和 release 必须为原子操作）
2
boolean available = true; // 表示锁是否可用，初值为 true（开锁状态）
3
// 获取锁的操作
4
void acquire() {
5
    while (!available)
6
        ;                 // 进入区：若锁不可用则循环忙等待（自旋）
7
    available = false;    // 抢到锁，置为不可用
8
}
9
// 释放锁的操作
10
void release() {
11
    available = true;     // 退出区：释放锁，置为可用
12
}
13
// 进程典型使用流程
14
acquire();                // 申请锁
15
critical section;         // 临界区
16
release();                // 释放锁
17
remainder section;        // 剩余区

• 解决了什么问题： 提供了一种最直观、最简单的互斥同步工具。将底层的硬件原子操作（如 TS/Swap 指令）封装为标准的 acquire() 和 release() 接口，保证在任意时刻临界区内最多只有一个进程在执行，满足了“空闲让进”与“忙则等待”。在多处理器（SMP）系统中，若临界区执行时间极短，等待的线程省去了进程上下文切换的巨大开销，效率极高。

• 发现了什么问题：

  1. 违背“让权等待”准则：未抢到锁的进程不会休眠，而是在 acquire() 中持续死循环（忙等待/自旋），白白空耗 CPU 周期。
  2. 单 CPU 系统下极度低效：若在单 CPU 系统中，占用锁的进程被切换下台，等待锁的进程只会占着 CPU 空转直到时间片耗尽，没有任何积极意义。

需要注意，互斥锁仍然违背让权等待原则，真正不违背让权等待原则的是信号量。

互斥锁只具有 0 和 1，表达不了丰富的信息。

此外，互斥锁是霸占 CPU 等待，而信号量是直接阻塞。

信号量#

P（wait）操作与 V（signal）操作。

P 的语义是申请一个资源：信号量减 1，如果减完小于 0 就阻塞自己，挂到该信号量的等待队列上。

V 的语义是释放一个资源：信号量加 1，如果加完小于等于 0，说明还有进程在等，就唤醒一个。

需要注意，P 和 V 必须配对，同一个资源先 P 后 V，顺序写反就可能死锁。

整型信号量和记录型信号量的区别在“小于 0 之后怎么办”：

1
// 整型信号量：不满足就一直空转，违背让权等待
2
void P(int *S) {
3
    while (*S <= 0);
4
    (*S)--;
5
}
6

7
// 记录型信号量：不满足就阻塞，遵守让权等待
8
void P(semaphore *S) {
9
    S->value--;
10
    if (S->value < 0)
11
        block(S->list);   // 挂到等待队列并阻塞
12
}

需要注意，记录型信号量的 value 为负时，其绝对值就是等待队列里阻塞进程的个数，这个结论选择题很爱考。

整型信号量类似互斥锁，靠忙等；记录型信号量引入了等待队列，所以前者违背让权等待，后者才全部遵守。

经典的 3 个模型放在大题解析那块。

管程#

深入理解一下管程。

管程可以用于进程的同步互斥，本质是代码，封装了共享变量和对它们的操作。

可以粗略地理解为一个大 key，key 内部锁着一些变量，例如读者写者问题中的 cnt。

考虑这样一种情况，对于读者写者问题，读者可以同时读，但是每一个读者也只能互斥的访问 cnt。

所以要辨析清楚，读者可以同时读，这个“读”指的是同时读文件，而不是同时读 cnt。

所以，管程内部只能有一个进程执行。

需要注意，管程只保证互斥，不保证同步，同步要靠条件变量（condition variable）。

条件变量有两个操作：wait 和 signal。wait 把自己挂到该条件变量的等待队列上，并释放管程的锁；signal 唤醒一个等待者，如果没有等待者，signal 什么也不做，不会累积。

所以和信号量不同，条件变量的 signal 没有“记忆”，错过就没了，这也是管程题最容易错的地方。

管程里有几个条件变量，就有几条等待队列；而入口处只有一条互斥队列。

资源竞争与推进顺序非法#

死锁的起因主要有两个：资源竞争和推进顺序非法。

资源竞争是指资源不足，多个进程同时需要同一类资源；推进顺序非法是指资源够用，但申请和释放的顺序不合适，形成了循环等待。

需要注意，资源竞争不一定导致死锁，只有竞争不可剥夺资源且分配不当才会；推进顺序非法也不一定死锁，要正好构成环路。

死锁与饥饿#

饥饿指的是进程长时间无法获得所需资源，导致无法继续执行，然而在充分的时间里，还是可以获得资源的。

然而死锁指的是逻辑上已经不可以继续执行了。

死锁的四个条件#

• 互斥
• 不剥夺
• 请求并保持
• 循环等待

题目里很可能出这几个东西的辨析，尤其是关于不剥夺和请求并保持需要理解清楚。

不剥夺条件的意思是我申请到的资源不会被其他进程抢夺。

请求并保持的意思是我已经请求到了一个资源，我还需要另一个资源，我会在不释放我已经申请到的这个资源的前提下，申请另一个资源。

这俩要想清楚。

死锁预防#

死锁预防的方式是破坏四个条件。

• 破坏互斥条件：采用共享设备，然而很多设备都是独占的，所以很多时候并不可行。
• 破坏不剥夺条件：强行释放，一般不可取
• 破坏请求并保持条件：静态分配（一次性分配所有运行所需的）；动态释放（使用完的设备先释放）
• 破坏循环等待条件：设置资源有序分配法。

死锁避免#

典型的代表是银行家算法。

然而需要注意，其不是限制进程申请资源的顺序，而是在进程动态提出资源请求时，先进行安全性检测（试探性分配），若分配后系统仍能处于安全状态（即能找到安全序列）才予以分配，否则暂不分配让进程等待。

银行家算法要维护四个量：可利用资源 Available、最大需求 Max、已分配 Allocation、还需资源 Need，其中

安全性检测的过程是：找一个 Need 不超过 Available 的进程，假设它运行完并归还全部资源，把它加入安全序列，再继续找下一个；如果所有进程都能进入安全序列，说明存在安全序列，系统安全。

需要注意，安全状态一定不会死锁，不安全状态不一定死锁，只是可能死锁。银行家算法是分配前预判，属于死锁避免，不是死锁预防。

死锁检测#

注意要记得资源分配图。

资源分配图里，方框是资源，框里的点表示实例数；圆圈是进程；进程指向资源的边是请求边，资源指向进程的边是分配边。

化简方法是：找一个既不阻塞又非孤立的进程，把它的请求边和分配边都消掉（相当于它运行完归还资源），重复这个过程。能消掉所有边，图就是可完全化简的，没有死锁；如果最后还剩下有边的环路，就发生了死锁。

需要注意，图里有环不一定是死锁，因为同类资源有多个实例时，环上的进程可以等别人还资源；但每个资源类只有一个实例时，有环就是死锁。

死锁发生后，可以采用以下三种方式来解除：

• 资源剥夺
• 进程撤销
• 进程回退

一定要往经典模型去思考。

程序链接与装入#

编译 - 链接 - 装入

辨析一下链接的三种方式：

静态链接是运行前就把需要的库打包好，占磁盘空间，然后装入时一次性全转入

装入时动态链接意思是边装入边链接，但也是全都装入

运行时动态链接意思是需要的模块才链接。

需要辨析链接和装入的区别。

三种内存装入方式辨析

• 静态装入（绝对装入）：在编译或链接时就已经确定了绝对物理地址，指令中的地址直接写死，不需要任何重定位寄存器介入，仅适用于早期的单道程序环境。

• 可重定位装入（静态重定位）：装入程序在将模块载入内存时，根据分配的内存起始物理地址，通过纯软件方式一次性修改程序内的所有相对逻辑地址（加上起始基地址偏移量）。装入完成后物理地址就此固定，程序在运行期间不可在内存中移动。

• 动态运行时装入（动态重定位）：装入模块进入内存后依然保留相对逻辑地址，将地址转换推迟到 CPU 实际执行指令的那一刻才动态进行。在执行指令时，硬件（重定位寄存器）自动将逻辑地址与基地址相加得出物理地址，因此程序可以在内存中便捷地移动（支持紧凑以消除外部碎片）。

• 考点延伸辨析：在狭义的连续分配管理中（如动态重定位分区分配），每个进程仅依靠一个重定位寄存器，因此只能分配连续的物理地址，便于系统进行整体搬迁和碎片紧凑；而在更广义的现代内存管理中，“动态运行时装入”这一核心思想被直接拓展到了基本分页、请求分页及分段等非连续（离散）分配机制中（由单基址寄存器升级为页表基址寄存器 + 硬件 MMU 查表），从而彻底打破了物理地址必须连续的限制。

内存保护、共享与回收#

内存保护主要是通过重定位寄存器来判断，共享则是共享物理内存，将之映射到逻辑地址空间中。

具体有两种做法：

• 上下界寄存器：上界存起始地址，下界存末地址，访问时判断地址是否落在区间内；
• 基址寄存器加限长寄存器：访问时先加上基址，再判断偏移是否小于限长。

需要注意，越界检查必须由硬件在地址变换时完成，不能靠软件检查，否则用户态程序可以绕过。

共享是把同一块物理内存映射到多个进程的逻辑地址空间，只读的代码段共享最典型。写时复制是共享的一种延伸：fork 之后父子进程共享页面，谁先写谁复制一份。

分配和回收主要基于页式和段式管理：页式按页框分配，段式按段分配。

此外，硬件资源是昂贵的，所以对于整个 CPU 可能只有一个重定位寄存器，进程切换时要更新它，这也算上下文切换的一部分。

连续分配策略辨析#

• 单一连续分配

• 固定分区分配

  • 分区大小相等：其实还有应用，例如要管理 k 个相同的炼钢厂。
  • 分区大小不等

• 动态分区分配

  • 首次适应算法：每次匹配从头开始，找到第一个适配的空闲分区
  • 邻近适应算法：从上次分配结束的为止开始向后找到第一个可以适配的。
  • 最佳适应算法：每次都选择可以被容纳的最小的一块（需要注意重新排序），容易出现外碎片
  • 最坏适应算法：每次都选择最大的那一块（注意需要重新排序），大的装不进去

然而实际应用中，反而首次适应算法式最好的。

• 基于索引的算法
  • 快速适应算法：根据系统平时常用的，固定分几个不同大小的区，构成链表，然后找最小可以容纳的分配，缺点是实现复杂以及内碎片
  • 伙伴系统 (Buddy System)：所有可用空闲分区的大小均规定为 $2^k$（$k$ 为整数）。
    • 分配：为大小为 $S$ 的请求寻找能容纳它的最小 $2^i$ 分区；若当前无空闲 $2^i$ 块，则将更大的空闲块（如 $2^{i+1}$）对半切开分成两半（互为“伙伴”），重复折半直到切出合适的 $2^i$ 大小分配给进程。
    • 回收：当释放一块 $2^i$ 空间时，若其相邻的“伙伴块”也是空闲的，则立即合并为一个 $2^{i+1}$ 的大块，并可向上递归继续合并。这个伙伴块是唯一固定的，例如我是原来大空间的右边一半，那么我一定是找左边那一半；反之亦然
    • 评价：极大加快了查找与合并速度，有效减少了外部碎片，但会产生一定的内部碎片。
  • 哈希算法：以空闲区大小为关键字建立哈希表分配

基本分页管理#

• 基本分页管理的概念

  页面，页框，实页号，页号，物理页框等概念。

  以一个 $4\text{ GB}$ 的逻辑空间为例，如果页大小为 $4\text{ KB}=2^{12}\text{ B}$，那么页内地址占 12 位，页号占 $32-12=20$ 位。

• 基本地址变换

  如果越界中断，那么直接返回。如果没有越界，那么根据虚页号的前 20 位直接访问页表数组下标，得到物理页框号，物理页框号和原来的 12 位拼接，可以得到物理地址。

  需要注意，页表没有全相联、组相联之类的概念，硬要说的话，查页表时，像一维数组下标寻址，一对一直接索引（无需相联比较）；而物理块放置时，任意虚页可放入任意物理页框，本质映射策略是全相联。一定要区分页表和 TLB 的概念。

  页表类似数组 / 哈希表，而 TLB 才类似 cache（的组相联 / 全相联）！

• 基本分页的缺点

  页式管理容易产生内碎片。

含有 TLB 的页表#

在操作系统（这门课）里，TLB 不需要考虑组相联，仅需要考虑全相联，计组那块要考虑组相联。

TLB 存储的是 tag - 物理页框号，还有脏位等。

TLB 和 cache 类似，一定是要和页表做区分，具体如下：

TLB 命中时，地址变换不需要访存，加上取数据一共 1 次访存；TLB 未命中时要先查页表再取数据，一共 2 次，多级页表还要更多。

TLB 一般用全相联或组相联，替换算法用随机或 LRU，表项里除了 tag 和页框号，还有有效位、访问位和 ASID（区分进程，避免进程切换时整表刷新）。

辨析 TLB / 一页与页面置换算法#

在 TLB 里，才会有替换的概念，而在一页内，这个页仅是记录，而并不会发生缺失。只有这一整个页需要被替换掉的情况，也就是页面置换。

一页本身并没有一页的某一项被替换的概念。

二级页表 & 多级页表#

一级页表的问题是：页表必须是连续的，页表很大时会占掉一大片连续主存，而且进程可能只用几个页，却要把整张页表都建起来。

考虑采用二级页表：$4\text{ GB}$ 的地址空间，页面 $4\text{ KB}$ 占 12 位，剩下的 20 位页号再拆成两段，一级页号 10 位、二级页号 10 位。

地址变换时，先用前 10 位在一级页表（页目录）里查到二级页表的物理页框号，再用中间 10 位在二级页表里查到数据页的物理页框号，最后和 12 位页内偏移拼成物理地址。

需要注意，页目录必须常驻内存且必须连续；二级页表可以离散存放，也可以根本不存在（对应页目录项有效位为 0），这正是二级页表省内存的原因。

还有一点，页表尽量都不要超过 1 页，是为了让一次查表只访存一次；页表超过一页就要分级，访存次数也跟着增加。

还是要辨析清楚，号和具体内存地址的关系。号 / 块一定指的是以 xx 为基准的。

在答题的时候，经常会混淆以块为基准还是以具体地址为基准！

事实上，对于一级页表（仅一级），页表始址寄存器也只用存其物理页号，而不需要存具体的 0 号记录对应的地址，因为边界对齐。

段表#

段式管理容易产生外碎片，不利于内存的利用；有利于程序的动态链接（因为是按逻辑的）；

段号，段长，段内偏移量。

注意，段表寄存器里存的是段表长度和段表初始地址！

段表的逻辑是先取出段号，如果段号 >= 段表长度，那么越界中断（段表越界）。和页表类似的，一个进程对应一个段表，而不是全局进程对应一个段表。

第二步如果段内偏移量大于等于段长，那么发生段内越界中断。

一定要捋清楚地址对应的是什么，段表寄存器里存的是什么。

由于实际生活中分段已经几乎不使用了，所以考试也基本不大可能考大题。

段的长度不固定且段对用户不透明，程序员在指定的时候必须指定段号以及偏移量（是二维的）。

段可以共享，把物理段映射到不同的逻辑段。

段页式#

段页式即先分段再分页，本质是按页存储的。

在段页式存储中，每个进程仅有一张段表，但是可能有多个页表（每个段一张）

基本分页和请求分页#

基本分页就是得一次性装入，而请求分页可以按需装入，动态置换。

虚拟内存有三个特征：

• 多次性：作业可以分多次调入内存，不需要一次全装入；
• 对换性：作业运行中可以换入换出；
• 虚拟性：逻辑上扩充了内存容量，用户看到的空间大于实际物理内存。

实现虚拟内存要三个支撑：一定容量的外存、页表这类数据结构、缺页中断机构。所以虚拟内存的容量上限由地址位数决定，而不是由内存加外存的大小决定。

需要注意，虚拟内存建立在局部性原理上，如果程序没有局部性，缺页会频繁发生，虚拟内存反而比不分页更慢。

页表的机制#

请求分页的页表项比基本分页多几个字段：

• 状态位：该页是否在内存；
• 访问字段：最近是否被访问过，供置换算法使用；
• 修改位：调入后有没有被改过，决定换出时要不要写回；
• 外存地址：该页在外存的位置。

地址变换的顺序是：先查快表，不命中再查页表；页表项状态位为 0 就产生缺页中断，由操作系统调页；调页完成后更新页表项和快表，重新执行被中断的指令。

需要注意，缺页中断是内中断（异常），处理完要重新执行当前指令；而设备 I/O 完成中断是外中断，处理完执行下一条指令。

缺页率与有效访问时间#

设缺页率为 $p$，一次内存访问时间为 $t_a$，一次缺页处理时间为 $t_f$，其中包括磁盘 I/O 和操作系统开销，则有效访问时间为

如果再加一层快表，设快表命中率为 $q$，快表访问时间为 $t_b$，那么

需要注意，缺页率对 EAT 的影响是决定性的：$t_f$ 是毫秒级，$t_a$ 是纳秒级，差了五六个数量级，所以缺页率只要到百分之一，性能就掉得很惨。

影响缺页率的因素有页面大小、分配的页框数、置换算法、程序局部性和写回策略。页面太小页表会膨胀、缺页变多；页面太大内部碎片变多、单次调页的 I/O 时间变长，所以是折中。

页框分配与置换#

• 内存分配与置换策略

  这里的核心维度只有两个：

  • 分配策略：给一个进程的物理页框数是固定死的，还是动态可变的？
  • 置换策略：缺页要置换时，只能踢自己进程内部的页（局部），还是可以抢其他进程的页（全局）？

  三种合法组合：

  • 固定分配 + 局部置换：每个进程在运行前分配固定数量的物理块，运行期间总块数不变。发生缺页时，只能在自己分到的那几个块里挑一个踢出去。
  • 可变分配 + 全局置换：系统保留一个空闲物理块队列。进程缺页时，操作系统从空闲块队列里划拨一块给它；若空闲块用光了，系统可以强行剥夺其他进程的物理块分配给当前进程。
  • 可变分配 + 局部置换：根据进程缺页率的频繁程度，操作系统动态增加或减少分配给该进程的物理块数；但发生缺页置换时，仍然只能从该进程自己的块里挑一个踢掉。

• 为什么没有“固定分配 + 全局置换”？

  既然规定了“固定分配”，就要求每个进程拥有的物理块总数必须恒定不变。而“全局置换”允许从其他进程那里动态抢夺物理块，一旦抢了，被抢进程的块数减少，抢到进程的块数增加，两者的总块数都变了，直接打破了“固定”的前提！

• 调页时机

  • 预调页策略（Pre-paging）：
    • 何时发生：主要用于进程启动前（初始化时）。
    • 机制：利用空间局部性原理，预测进程接下来会用到哪些页，一次性把相邻的几个页提前调入内存。
    • 特点：靠预测，成功率只有 50% 左右，主要由程序员通过系统调用显式指定或用于大块数据批量加载。
  • 请求调页策略（Demand Paging）：
    • 何时发生：在进程运行过程中。
    • 机制：平时不调，只有当 CPU 访问该页发生缺页中断（Page Fault）时，才被动地从外存调入。
    • 特点：现代 OS 的通用标准策略，实现简单，但发生缺页时的 I/O 开销较大。

• 从何处调入页面？

  在外存（磁盘）中，空间被明确划分为两块：

  • 文件区：存放普通文件，追求离散存储以提高空间利用率，I/O 速度较慢。
  • 对换区（Swap 分区）：存放暂存的内存页面，采用连续分配方式，追求极致的 I/O 读写速度。

  页面调入的三种场景：

  • 对换区空间足够充足：
    • 进程运行前，把与该进程相关的所有数据从文件区全部预先复制到对换区。
    • 之后只要发生缺页，一律直接从高速的对换区调入；换出时也全部写回对换区。
  • 对换区空间不够充裕：
    • 没修改过的页（只读代码、未写过的数据）：换出时直接丢弃，无需写入外存；下次需要时直接去文件区重新读。
    • 被修改过的页（脏页，Dirty Page）：换出时必须写入对换区，下次缺页也从对换区调入。
  • UNIX 策略：
    • 与进程相关的代码段、数据段在第一次使用时，统一从文件区调入。
    • 只要这一页被调入过内存，一旦它未来被换出，一律写入对换区；下次如果再需要它，就改从对换区调入。
    • 和对换区空间不够的策略对比，对换区空间不够也是从文件去读入，不同点在于不充裕的时候，修改过的才放进对换区，而 UNIX 是只要访问过了就放对换区。

  “交换频繁而 CPU 很空闲”的现象，即抖动（颠簸）！

  本质原因：同时运行的进程数量过多（多道程序度过高），导致分配给每个进程的物理块数量少于其工作集（Working Set）的大小。进程大部分时间都在等磁盘 I/O 调页，CPU 反而被闲置。

  解决抖动：

  1. 减少多道程序度：挂起或杀死部分进程，把腾出来的物理页框集中分给剩下的进程，确保每个进程都能装下其工作集。
  2. 增加物理内存容量：给服务器插更多的物理内存条。
  3. 基于工作集算法进行动态调整：防止给进程分配的页面数低于下限。

• 置换算法

  • OPT（最佳置换算法，Optimal）
    • 淘汰规则：淘汰在未来最长时间内不再被访问的页面。
    • 评价：性能最好，缺页率最低。但操作系统无法预知未来，因此在物理上无法实现，通常仅作为衡量其他算法优劣的理论上限。
  • FIFO（先进先出置换算法）
    • 淘汰规则：淘汰最早进入内存的页面。
    • 评价：实现最简单（维护一个队列），但性能很差，没有考虑局部性。
    • 致命考点——Belady 异常：正常算法物理块越多缺页越少，但 FIFO 会出现为进程分配的物理块增加，缺页次数反而不减反增的怪异现象！
  • LRU（最近最少使用算法，Least Recently Used）
    • 淘汰规则：淘汰过去一段时间内最久未被访问的页面。
    • 实现机制：依靠硬件计数器或双向链表/软件堆栈，记录每个页面的上次访问时间。
    • 评价：性能最接近 OPT，且属于堆栈型算法，绝对不会产生 Belady 异常！但硬件维护代价和开销极高。
  • CLOCK 算法（时钟置换 / NRU 最近未使用）
    • 淘汰规则：把内存中的页面排成一个循环队列，每页设置一个访问位 $u$（0 或 1）。
      • 当页面被访问时，硬件将 $u$ 置为 1。
      • 置换时，指针开始循环扫描：
      • 若遇到 $u = 0$，直接选定淘汰！
      • 若遇到 $u = 1$，将该位的 $u$ 清零（给一次免死机会），指针向前移动继续找。
      • 评价：以极小的硬件代价（仅需 1 个 bit）近似模拟了 LRU 的性能。
  • 改进型 CLOCK 算法（综合考虑【访问位 $u$】与【修改位 $m$】）
    • 核心思想：被修改过的页面（$m=1$）换出时需要写回磁盘，I/O 开销很大！所以优先淘汰既没被访问、又没被修改过的页面！
    • 扫描四步法（最多转 4 轮）：
      • 第 1 轮：找 $(u=0, m=0)$。不修改任何标志位，找到即淘汰。
      • 第 2 轮：若第 1 轮未找到，找 $(u=0, m=1)$。本轮经过的所有页面的访问位 $u$ 必须全部清零！找到即淘汰。
      • 第 3 轮：若仍未找到，重复第 1 轮，找 $(u=0, m=0)$。
      • 第 4 轮：若仍未找到，重复第 2 轮，找 $(u=0, m=1)$，此时必定能命中淘汰项。

页框回收#

可以理解为回收页框的时候，将页框置入未被分配页框的末尾队列，然后如果后续还需要这个页，那直接从队尾拿回来就好了。（2012 真题）

内存映射文件#

将物理内存的某个文件映射到不同进程的逻辑地址空间，这个文件是共享的。

映射之后，读写这段内存就是读写文件，具体的磁盘 I/O 由操作系统在缺页时按需完成，写回由脏位和文件系统的同步策略控制。

好处是省掉了 read/write 的一次拷贝：普通 read 要经过“磁盘到内核缓冲区、内核缓冲区到用户缓冲区”两次搬运，映射之后用户直接操作页缓存。

多个进程映射同一个文件，就能共享同一份物理页，这也是共享内存通信的实现方式之一。

需要注意，映射文件的大小不要求是页的整数倍，最后一页多余的部分补零，写回时也只写文件本身的长度。

FCB 与索引节点 inode#

1. FCB 是操作系统中管理文件元信息的通用抽象结构，并非仅属于 FAT 系统；Unix 及 UFS 系统采用 FCB 分解法，将其拆分为目录项与 inode 两部分以减少目录检索时的磁盘读写次数。

2. 传统 FCB 中必须包含文件的物理地址以及权限等属性，文件的物理地址由 FCB 直接记录，但文件的具体数据内容存放在磁盘数据块中而非 FCB 中。

3. FAT 系统中的静态链表是 FAT 表即文件分配表，它位于磁盘卷的前端保留区，用于显式记录物理盘块的先后链接关系，其表项数量对应物理盘块数而非文件数。

4. FAT 系统中的 FCB 本质上就是目录项，它们并不集中在磁盘最前端，而是分散保存在各个目录文件的数据块中。

5. 在类 Unix 系统中，文件名不保存在 inode 中，而是与 inode 编号一同保存在目录项中；一个目录项就是文件名到 inode 编号的映射。

6. 文件的访问权限、文件主、文件大小以及用于寻址磁盘块的直接与间接物理索引指针，全部直接保存在 inode 内部，绝对不占用或保存在普通数据块中。

7. 类 Unix 系统在格式化时会预先在磁盘中分配固定数量的 inode 空间，因此磁盘中 inode 的最大数量确实决定了该文件系统能够创建的文件总数上限。

综上辨析一下 FCB 和 inode，只是说 FAT 系统使用了 FCB 方法，UFS 使用了 inode，并不是说 FCB 是 FAT 独占的。

目录结构#

现在考纲只剩下树形结构，命令按照 linux 命令理解即可。

目录项里存的是文件名和 inode 号（或者 FCB），所以按名查找的本质是在目录文件里顺序查找目录项。

目录的操作有创建、删除、重命名、查找、列出。删除非空目录要先递归删掉里面的内容；重命名只改目录项里的名字，不移动数据。

需要注意，绝对路径从根目录开始，相对路径从当前目录开始，路径解析每一步都要读一次目录文件，所以路径越深访盘次数越多。

可以注意“工作区”的概念，即以当前目录为新的根目录。

文件的物理结构#

• 连续分配

  • 对于单级目录（虽然已经从考纲中移除了），如果不需要对文件进行修改，可以使用。

• 链接分配

  • 隐式链接分配：每个结点的末尾有一小片区域用于存储下一个磁盘的块号
  • 显示链接分配：额外划分一块空间存储静态链表

• 索引分配

  • 单级索引分配
  • 多级索引分配
  • 混合索引

三种物理结构的取舍：

• 连续分配支持顺序访问和随机访问，速度最快，但有外部碎片，文件增长困难；
• 链接分配没有外部碎片，文件可以随时增长，但只能顺序访问，指针还要占空间；
• 索引分配支持随机访问，文件可以增长，但索引块本身占空间，大文件需要多级索引。

混合索引（UFS）是折中：inode 里放若干个直接指针，再加一级、二级、三级间接指针。小文件只用直接指针，一次访盘就能取到数据；大文件逐级用间接指针，用空间换容量。

具体的流程可以见大题分析。

文件的基本操作#

• 创建：在外存分配空间并建立 FCB/目录项，完成文件名到初始物理位置的绑定。

• 删除：释放文件占用的外存块，并在目录项中彻底抹去其记录。

• 读：根据读指针把外存/系统缓存里的数据搬运到进程的用户空间缓冲区。

• 写：把进程用户空间的数据写进外存/系统缓存，并更新文件指针与长度属性。

• 打开：把文件的 FCB 调入内存的打开文件表，并向进程返回一个数字代号（文件描述符）。

• 关闭：使文件打开引用计数减一，在进程打开表中注销该项，计数归零时清出系统表。

• 辨析 open 与 read：open 传入的参数是文件名，返回的是文件描述符；read 直接根据这个文件描述符去访问文件即可

• 辨析关闭和写入：关闭只是单纯的把文件（如果是最后一个关闭）从文件打开表删除，而在删除的过程中，文件并没有立刻写回磁盘，而是操作系统另外自行写回的。所以关闭和写回没有必然的强相关性。

• 辨析系统文件打开表和进程文件打开表：系统表全局仅一份、记录所有打开文件的物理信息与共享引用计数；进程表各进程独立持有一份、只记录本进程打开文件的描述符与指向系统表的偏移指针。

硬链接与软链接#

属于文件共享相关的。

• 硬链接：同一个 Inode 在不同目录项下的镜像别名，共享物理空间与链接计数，计数归零才真正释放数据。

• 软链接（符号链接）：一个独立的全新文件（拥有独立 Inode），内容仅为目标文件的路径字符串，目标失效即变“死链接”。

以文件 file.txt 为例，cnt = 1，假设硬链接出去，那么连接计数 cnt = 2，如果源文件软连接出去，那么新建一个 inode，该 inode cnt = 1。如果针对该 inode 再硬连接出去，那么该 inode cnt = 2。

删除源文件，那么源文件计数 cnt = 1，然后延伸出去的软连失效。

文件保护#

• 口令：文件本身没有加密，输入口令访问
• 密码：文件本身被加密，输入密码解密
• 文件访问控制表：需要注意假设有 4 个权限和 3 个用户，那么一定是 12 个，而不是按照二进制那样去存。因为需要存储所有信息，而不是一个。（2017 真题）

用户优先级和文件保护无关。

文件系统布局#

外存上的布局，从磁盘开头往后依次是：

• 主引导记录：磁盘第一个扇区，里面是引导代码和分区表；
• 引导块：分区里的第一个块，存放启动本分区操作系统的引导程序；
• 超级块：记录文件系统的类型、总块数、空闲块数、inode 数等全局信息，是文件系统的“户口本”；
• 空闲空间管理信息：位示图或者成组链接的索引块；
• inode 区：所有 inode 集中存放，数量在格式化时就已确定；
• 根目录与数据区：目录文件和数据块。

内存中的结构一般有四块：挂载表（记录每个已挂载文件系统的超级块）、目录缓存、活跃 inode 表（inode 缓存）、系统打开文件表。

可以结合 UFS 系统的例图来记忆。

需要注意，超级块和 inode 区的位置是固定的，而数据区里的块是离散的，这就是为什么文件系统需要空闲空间管理。

文件系统空间管理#

• 空闲表法：为所有连续的空闲区建立登记表，记录每个空闲分区的起始块号与长度，适合连续分配策略。
• 空闲链表法：
  • 空闲盘块法：把所有未分配的单个盘块通过指针串成一条总链，分配和回收逐块进行，适合离散分配但链条极长。
  • 空闲盘区法：把连续的空闲块作为一个盘区，盘区头记录长度并用链表串联各盘区，兼顾了分配速度与连续性。
• 位示图法：用连续的二进制比特位（0 与 1）直接映射整块磁盘每个盘块的占用与空闲状态，体积极小可常驻内存且便于快速计算块号。查找高效，但需要空间存储。
• 成组链接法：把空闲块按固定数量分组成栈并层层链挂，栈顶块记录下一组所有块号，兼具链表的扩展性与栈的批量高速存取性能（UNIX）。注意利用空闲盘块栈存储。

可以注意，文件系统空间这里指的是外存空闲区管理。

虚拟文件系统#

即 VFS。内核在内存中建立的面向对象的抽象接口层，用来屏蔽各类异构底层文件系统的物理差异，向上提供统一的系统调用。

• 超级块对象：代表一个已挂载的具体文件系统，负责记录该文件系统的全局控制信息与挂载元数据。
• V 结点对象：代表一个确切的物理文件本身，负责统管文件的访问权限、物理块映射及底层驱动函数指针（不存文件名）。
• 目录项对象：代表路径上的某一级目录或具体文件名，在内存中把字符串名字与对应的 V 结点绑定并构建路径缓存树。
• 文件对象：代表某个进程正打开的一个文件交互上下文，负责维护该进程当前独享的读写指针位置、访问模式及引用计数。

文件系统挂载#

可以理解为以某个目录为根目录，然后挂载到另一个目录上。

比如说 openlist 挂在夸克网盘，以某文件夹为根结点，或者以 webDAV 的形式挂载到本地。

设备分类#

• 字符设备：例如鼠标和键盘，不具备存储功能，通过缓冲区输入
• 块设备：使用 DMA 方式
• 网络设备：比如网卡

I/O 接口与端口#

I/O 接口指的是设备和主机之间的连接器，端口指的是设备内部的寄存器。

寄存器最重要的三个：数据寄存器，控制寄存器与状态寄存器。

编址分为独立编址和统一编址。

I/O 控制方式#

需要注意，I/O 相关全是内核态。

三种方式：轮询方式，中断方式，DMA 方式。

• 轮询：CPU 一直查设备状态寄存器，简单但白白占用 CPU；
• 中断：设备就绪后发中断，CPU 响应后由程序搬数据，适合低速、随机到达的设备；
• DMA：DMA 控制器直接在主存和设备之间搬数据块，CPU 只在开始和结束时参与，适合高速、成块的设备。

需要注意，中断方式每传一个字都要中断一次，DMA 是整块传完才中断一次，所以高速设备用 DMA 效率高得多。

其实还有通道控制，但是考研不考（因为这个级别是要到神威·太湖之光的）。

I/O 层次架构#

用户层软件 - 设备独立性软件 - 设备驱动程序 - 中断处理程序 - 硬件。

这类题特别爱考选择题辨析，尤其要注意：

用户层软件是把用户的操作发送给设备独立性软件，设备独立性软件根据是什么设备，翻译成这个设备的指令，发送给设备驱动程序，而设备驱动程序是把设备的指令翻译成控制设备的寄存器硬件指令，设备驱动程序直接向硬件（设备控制器寄存器）写入指令启动硬件，硬件干完活才反向触发中断处理程序。

也就是很多时候并非是从上至下，例如 scanf，是上到下一会儿，下到上一会儿，然后最后再上。

输入/输出应用程序接口#

按设备类型分三种接口：

• 字符设备接口：以字节流为单位，例如键盘、打印机，通常不支持随机访问；
• 块设备接口：以块为单位，支持随机访问，通常配合内存映射和 DMA；
• 网络设备接口：以报文或套接字为单位，协议栈在操作系统内部实现。

按调用方式分阻塞与非阻塞：

• 阻塞 I/O：调用后进程阻塞，直到数据就绪并复制完成才返回，编程简单但并发度低；
• 非阻塞 I/O：调用后立即返回，数据没就绪就返回一个错误码，进程自己轮询重试。

需要注意，阻塞 I/O 的阻塞点可能在“等数据”和“复制数据”两处，所以后来又有多路复用（select / poll）和异步 I/O。

缓冲区#

• 单缓冲
• 双缓冲
• 循环缓冲
• 缓冲池

这个就具体题目具体分析了。

不过可以注意的是，有时候不需要采用后两者，采用双缓冲就够了

还可以注意高速缓存和缓冲区是不同的概念，前者是数据副本，目的是提高重复访问效率，后者是真实传输的数据。

单缓冲的时间要算清楚：设一块数据从磁盘读入缓冲区的时间为 $T$，从缓冲区送到用户区的时间为 $M$，CPU 处理这块数据的时间为 $C$，那么处理一块数据的平均时间为

双缓冲是两个缓冲区交替使用，一块在装数据、另一块在处理，平均时间变成

需要注意，双缓冲的前提是 $T$ 和 $C+M$ 能重叠，如果 CPU 很快而磁盘很慢，瓶颈就在磁盘，加缓冲没有用。

循环缓冲适合输入输出速度相差不大、需要连续处理的场景；缓冲池把多个缓冲区统一管理，分成空缓冲队列、装满输入数据的队列和装满输出数据的队列。

设备分配与回收#

几个概念：设备控制表（DCT），控制器控制表（COCT），通道控制表（CHCT），系统设备表（SDT）

一个系统一个 SDT，简单来说就是先登记系统设备表，然后自下而上地被分配。

设备属性：独占设备，共享设备，虚拟设备。可以注意共享设备必须是可随机寻址。

设备分配算法：FCFS，高优先级分配

逻辑设备 - 物理设备，可以采用两种方式，一个系统一张 / 一个用户一张。

Spooling 技术#

• Spooling 技术的基本部件

  输入井与输出井：开辟在外存（磁盘）上的两块专用大容量存储区。

  输入井：模拟脱机输入的磁带，暂存输入设备传来的海量作业数据。

  输出井：模拟脱机输出的磁带，暂存用户作业产生的海量输出数据。

  输入缓冲区与输出缓冲区：开辟在内存中的暂存区。负责在“内存”与“外存井”之间进行块级高速中转，抹平系统内部总线与磁盘的速度差。

  • 输入进程与输出进程（预设系统级软件）：
    • 输入进程：模拟脱机输入时的外围控制机，负责把输入数据打入输入井。
    • 输出进程：模拟脱机输出时的外围控制机，负责把输出井中的数据顺序拉取并喂给慢速物理外设。
  • 井管理程序：负责维护作业表项、排队状态及外存块指针。

• Spooling 技术的基本流程

  • 阶段一：逻辑申请（用户作业发起）

    • 用户进程向操作系统申请使用打印机；
    • 系统不分配真实打印机，而是由系统在内存中为该作业分配一个逻辑设备控制块，并在外存输出井中划定专用存储区域；
    • 用户进程通过系统调用，将待打印数据写入内存输出缓冲区。

  • 阶段二：井内暂存与用户释放

    • 缓冲区数据成块写入外存输出井；

    • 数据完全写入外存井后，操作系统直接给用户进程返回“I/O 已完成”信号；

    • 用户进程解除阻塞继续前行或正常终止退出，系统将该打印任务挂入“打印请求等待队列”。

  • 阶段三：后台守护调度（真正的物理输出）

    • 物理打印机空闲时，系统的 SPOOLing 输出进程 从打印队列中取出下一个就绪作业；
    • 输出进程从外存输出井将数据分批调入内存输出缓冲区；
    • 驱动物理打印机，将数据从缓冲区逐字/逐行发送至打印设备；
    • 打印彻底完毕后，输出进程释放该任务在外存井中所占用的所有物理磁盘块。

所以可以发现，用户在申请的时候是用户态，而真正后台守护调度使用的是内核态。

• 缓冲区也可以是内存，为什么 Spooling 技术需要外存支持

  考虑这样一种情况，假设打印的东西是 GB 级别的，那么内存会直接撑爆。

  内存缓冲区（Buffer）：主要用于匹配 CPU 与外设的速度差，生命周期短，容量极小（KB~MB 级），易失性，无法应对海量、长时间的数据积压。

  外存支持（井技术）：SPOOLing 面对的是极端慢速的机械/独占设备（如打印机），且多进程并发产生的数据量极其庞大（GB 级），数据滞留时间以“小时”甚至“天”计。

  容量瓶颈：若无外存的“输入/输出井”托底，海量输出数据将瞬间挤爆物理内存，导致系统发生内存耗尽（OOM）崩溃。

  驻留周期：慢速外设消费数据极慢，若长期霸占物理内存，会严重降低内存利用率与多道程序并发度。

  数据安全性：外存具备非易失性，可有效避免突发断电导致排队作业丢失。

设备驱动#

将上层命令转换成设备操作参数 - 检查合法性 - 发出 I/O 命令 - 响应中断。

设备驱动程序接口就是驱动向上层提供的一组标准函数，一般是一张函数表，里面是 open、read、write、ioctl 这类入口。

设备独立性软件通过这张表调用具体设备，换一块同类型的网卡，只要换驱动，上层的代码不用改，这就是设备独立性的含义。

磁盘管理#

磁盘初始化：低级格式化（建立逻辑块到物理扇区的初始映射，CRC 校验） - 分区（例如分 C 盘，D 盘） - 高级格式化（建立文件系统）。

通常按簇来给单个文件，簇是一组连续的扇区，所以文件占用的空间是簇的整数倍，最后一簇用不完就产生内部碎片。

引导块存放启动该分区的引导程序；坏块的处理有两种：在 FAT 里标记为坏，或者把它们集中到保留区，用备用扇区替换。

需要注意，低级格式化会丢失磁盘上所有数据，出厂时才做；高级格式化只重建文件系统，数据理论上还能恢复，所以真正的清除要覆写。

磁盘调度#

这一块主要就是不要脑子抽想错了。

• 减少寻道时间的思路

  • 先来先服务
  • 最短寻道
  • 扫描（SCAN）算法：先向一个方向，直到边缘，然后反向，直到边缘。
  • 循环扫描（C-SCAN）算法：先一个方向，然后移动到开始，重复这个方向

  注意，最后两个都是要移动到边缘（也就是 0 和最大的）

  但是，考试的时候得看具体语境，如果很确定没给具体信息，那么可能指的是 LOOK 和 C-LOOK 算法。

  先把磁盘的访问时间写清楚：

  $$T_{\text{访问}}=\text{寻道时间}+\text{旋转延迟}+\text{传输时间}$$

  平均旋转延迟是转一圈时间的一半，传输时间等于要读的字节数除以传输率。

  四种算法的区别可以这样记：

  • FCFS：按请求顺序服务，公平但寻道距离长；
  • SSTF：每次选离当前磁头最近的请求，寻道最短，但可能饿死远处的请求；
  • SCAN（电梯算法）：沿一个方向服务到磁盘边缘再反向；
  • LOOK：沿一个方向服务到该方向最后一个请求就反向，不走到边缘；
  • C-SCAN：只在一个方向服务，到头直接快速返回起始端；
  • C-LOOK：只在一个方向服务，返回时只回到最靠里的请求处。

  需要注意，SCAN 和 C-SCAN 要走到边缘，LOOK 和 C-LOOK 只走到最后一个请求，题目没说“到边缘”时优先按 LOOK 理解。

• 减少延迟时间的思路：

  • 扇区的交替编号
  • 重叠起来上下扇区不一致（盘面相关）

• 提高磁盘 IO

  • 高速缓存
  • 请求顺序
  • 提前读
  • 延迟写
  • 优化物理块分布
  • 虚拟盘
  • 磁盘阵列 RAID（计组那块知识）

SSD#

和计组那块是一样的。

SSD 的读写以页为单位，擦除以块为单位，所以随机写要先读整块、改完再写回，写放大就是这么来的。

磨损均衡分动态和静态：动态只在新写入时优先挑擦除次数少的块，静态还会在后台把冷数据搬走，让各块的擦除次数更均匀。静态的代价是有额外的后台 I/O，但寿命更长。

需要注意，SSD 没有寻道和旋转延迟，所以磁盘调度算法对 SSD 没有意义。

简单同步互斥问题#

这类题比较简单，但是需要注意进程和线程的区别。

做题方法是绘制调用关系图，用拓扑排序的方法解，并且为每一个入度都添加一个信号量（注意进程和线程）

生产者消费者问题#

利用咸鱼的模板。

1. 找出所有的进程
2. 写出所有进程的动作，并且判断需不需要 while
3. 判断每个动作需要 P 什么，有 P 必然有 V，先 P 后 V
4. 判断是否需要 mutex，并且确认 semaphore 初值
5. 检查连续的 P 操作是否可能导致死锁，如果是，尝试调整顺序
6. 誊写并检查

根据经验，一般小资源申请在前，大资源申请在后可能会导致死锁。

此外可以注意，对于生产者而言，只有生产出来的东西被放进了缓冲区，才可以说是生产了。

哲学家进餐问题#

对这类题，思想是一次拿走所有的资源，然后一次释放所有的资源。

以 int 变量记录正在进餐的人数，再用一个信号量 mutex 保护这个变量的访问。

这么做的原理是破坏请求并保持条件：要么一把拿到左右两只叉子，要么一只都不拿，不存在“拿着一只等另一只”的状态。

如果改成破坏其他条件：

• 破坏互斥：叉子只能一个人用，做不到；
• 破坏不剥夺：要求已经拿到叉子的哲学家在拿不到另一只时主动放下，这其实就是一次性申请；
• 破坏循环等待：给叉子编号，规定每个哲学家先拿编号小的、再拿编号大的，这样不会形成环。

读者写者问题#

主要是注意理解经典模型和非经典模型的差别。

• 经典模型：多读者一写者读优先

1
semaphore rw_mutex = 1;  // 互斥访问共享数据区
2
semaphore mutex = 1;     // 互斥修改 read_count
3
int read_count = 0;
4

5
void reader() {
6
    while (1) {
7
        P(&mutex);
8
        read_count++;
9
        if (read_count == 1) {
10
            P(&rw_mutex); // 第一个读者锁住写者
11
        }
12
        V(&mutex);
13

14
        // --- 读操作 ---
15

16
        P(&mutex);
17
        read_count--;
18
        if (read_count == 0) {
19
            V(&rw_mutex); // 最后一个读者释放写者
20
        }
21
        V(&mutex);
22
    }
23
}
24

25
void writer() {
26
    while (1) {
27
        P(&rw_mutex);
28
        // --- 写操作 ---
29
        V(&rw_mutex);
30
    }
31
}

• 经典模型：多读者一写者写优先

1
semaphore rw_mutex = 1;  // 互斥访问共享数据区
2
semaphore mutex = 1;     // 互斥修改 read_count
3
semaphore write_gate = 1;// 写者用来封堵后续读者的门禁
4
int read_count = 0;
5

6
void reader() {
7
    while (1) {
8
        P(&write_gate);  // 检查是否有写者插队封锁
9
        P(&mutex);
10
        read_count++;
11
        if (read_count == 1) {
12
            P(&rw_mutex); // 封锁写操作
13
        }
14
        V(&mutex);
15
        V(&write_gate);
16

17
        // --- 读操作 ---
18

19
        P(&mutex);
20
        read_count--;
21
        if (read_count == 0) {
22
            V(&rw_mutex);
23
        }
24
        V(&mutex);
25
    }
26
}
27

28
void writer() {
29
    while (1) {
30
        P(&write_gate);  // 抢先占住门禁，阻止新的读者进来
31
        P(&rw_mutex);    // 等待正在读的读者全部退出
32

33
        // --- 写操作 ---
34

35
        V(&rw_mutex);
36
        V(&write_gate);  // 释放门禁
37
    }
38
}

• 非经典模型：多读者多写者读优先

1
semaphore rw_mutex = 1;  // 读者与写者、写者与写者之间的共享区互斥锁
2
semaphore r_mutex = 1;   // 互斥修改 read_count
3
int read_count = 0;
4

5
void reader() {
6
    while (1) {
7
        P(&r_mutex);
8
        read_count++;
9
        if (read_count == 1) {
10
            P(&rw_mutex); // 第一个读者卡死所有写者
11
        }
12
        V(&r_mutex);
13

14
        // --- 读操作 ---
15

16
        P(&r_mutex);
17
        read_count--;
18
        if (read_count == 0) {
19
            V(&rw_mutex); // 最后一个读者放行写者
20
        }
21
        V(&r_mutex);
22
    }
23
}
24

25
void writer() {
26
    while (1) {
27
        P(&rw_mutex); // 多个写者互相竞争这把唯一的大锁
28

29
        // --- 写操作 ---
30

31
        V(&rw_mutex);
32
    }
33
}

• 非经典模型：多读者多写者写优先

1
semaphore rw_mutex = 1;   // 真正的数据区访问互斥
2
semaphore read_lock = 1;  // 阻止读者进来的大门
3
semaphore r_mutex = 1;    // 互斥修改 read_count
4
semaphore w_mutex = 1;    // 互斥修改 write_count
5
int read_count = 0;
6
int write_count = 0;
7

8
void reader() {
9
    while (1) {
10
        P(&read_lock);   // 检查是否有写者封门
11
        P(&r_mutex);
12
        read_count++;
13
        if (read_count == 1) {
14
            P(&rw_mutex); // 读者卡死数据区
15
        }
16
        V(&r_mutex);
17
        V(&read_lock);
18

19
        // --- 读操作 ---
20

21
        P(&r_mutex);
22
        read_count--;
23
        if (read_count == 0) {
24
            V(&rw_mutex);
25
        }
26
        V(&r_mutex);
27
    }
28
}
29

30
void writer() {
31
    while (1) {
32
        P(&w_mutex);
33
        write_count++;
34
        if (write_count == 1) {
35
            P(&read_lock); // 第一个写者立刻把读者的大门锁死！
36
        }
37
        V(&w_mutex);
38

39
        P(&rw_mutex);      // 获取数据操作权（等待读完或写完）
40
        // --- 写操作 ---
41
        V(&rw_mutex);
42

43
        P(&w_mutex);
44
        write_count--;
45
        if (write_count == 0) {
46
            V(&read_lock); // 所有写者都退出了，才给读者开门
47
        }
48
        V(&w_mutex);
49
    }
50
}

• 非经典模型：多读者多写者公平

1
semaphore rw_mutex = 1;  // 数据区互斥
2
semaphore queue = 1;     // 排队锁，保证先来后到
3
semaphore r_mutex = 1;   // 互斥修改 read_count
4
int read_count = 0;
5

6
void reader() {
7
    while (1) {
8
        P(&queue);       // 进入先来先服务队列
9
        P(&r_mutex);
10
        read_count++;
11
        if (read_count == 1) {
12
            P(&rw_mutex); // 第一个读者锁定写者
13
        }
14
        V(&r_mutex);
15
        V(&queue);       // 释放排队锁，允许下一个（读者或写者）排队
16

17
        // --- 读操作 ---
18

19
        P(&r_mutex);
20
        read_count--;
21
        if (read_count == 0) {
22
            V(&rw_mutex); // 最后一个读者退出
23
        }
24
        V(&r_mutex);
25
    }
26
}
27

28
void writer() {
29
    while (1) {
30
        P(&queue);       // 拿到排队号
31
        P(&rw_mutex);    // 等待当前读者/写者完成
32
        V(&queue);       // 释放排队锁
33

34
        // --- 写操作 ---
35

36
        V(&rw_mutex);
37
    }
38
}

阶段一：第一次执行指令与虚地址切分#

1. CPU 解析逻辑地址 0x0040312C，将其转换为 32 位二进制： 0000 0000 0100 0000 0011 0001 0010 1100
2. 硬件自动将其拆解为三部分：
   • 一级页号 P1（前 10 位）：0000 0000 01，即十进制 1 号目录项。
   • 二级页号 P2（中 10 位）：00 0000 0011，即十进制 3 号页表项。
   • 页内偏移 D（后 12 位）：0001 0010 1100，即十六进制 0x12C。
3. 虚页号 VPN 为前 20 位组合：0000 0000 0100 0000 0011，即十六进制 0x00403。

阶段二：查询 TLB（发生 Miss）#

1. CPU 硬件拿着 20 位虚页号 0x00403 去和 TLB 中所有条目的 Tag 进行全相联并行匹配。
2. 判定：由于 TLB 初始为空，Tag 匹配失败（TLB Miss）。
3. 动作：按照设定，硬件转向内存开始查询二级页表。

阶段三：两级页表漫游与触发缺页#

1. 查一级页目录表：
   • 硬件根据页表基址寄存器 + (P1 × 4B)，找到 1 号页目录项。
   • 检查该项有效位为 1，从中读出对应的二级页表所在的物理页框号。
2. 查二级页表：
   • 硬件根据二级页表基地址 + (P2 × 4B)，找到 3 号页表项。
   • 检查该页表项：发现其有效位（Valid Bit）为 0！说明该目标数据页不在内存中。
3. 触发异常：
   • 硬件立即终止当前地址变换，产生【缺页异常（Page Fault）】，CPU 进入核心态。

阶段四：操作系统介入（缺页中断服务程序）#

1. 操作系统挂起当前触发缺页的进程，保存当前指令的上下文（PC 依然指向这条引发缺页的 LOAD 指令）。
2. 从空闲物理页框列表中分配一个空闲页框（假设分配到的物理页框号为 0x5A88）。
3. 根据页表项中记录的外存地址，发出磁盘 I/O 请求，把外存中的数据页面读入到 0x5A88 页框中。
4. 页面调入完成后，操作系统修改该二级页表项的内容：
   • 将物理页框号写入 0x5A88。
   • 将有效位从 0 改为 1。
5. 中断处理结束，CPU 退出核心态。

阶段五：异常返回与“重读重执”#

1. 重点特性：与普通的外部 I/O 中断不同，缺页异常处理完成后，CPU 恢复现场，返回到【刚刚发生缺页的那条原指令】重新开始执行，而不是执行下一条指令。
2. CPU 再次发射这条 LOAD [0x0040312C] 指令。

阶段六：第二次执行指令与 TLB 更新#

1. CPU 再次切分地址，得到虚页号 0x00403。
2. 先查 TLB：因为操作系统刚刚调页并不会直接主动写 TLB，此时 TLB 里仍然没有这个项，再次发生 TLB Miss。
3. 再次查两级页表：
   • 查页目录项（有效）。
   • 查二级页表项：这次读取时，有效位已经是 1 了！顺利读出物理页框号 0x5A88。
4. 写入快表：硬件（或软故障处理）将映射关系【Tag = 0x00403, 物理页框号 = 0x5A88】写入全相联 TLB 中，以便下次极速访问。

阶段七：最终物理地址拼接与访存#

1. 物理地址生成：
   • 高位取物理页框号：0x5A88（二进制占对应物理位宽）。
   • 低 12 位直接复制逻辑地址的页内偏移：0x12C。
   • 最终物理地址合成完毕：0x5A8812C。
2. CPU 将该物理地址送上地址总线，从主存中正确读出数据，装入寄存器，整条指令顺利执行完毕！

页表项的长度#

页表项至少要能存下物理页框号，所以最少需要 $\lceil\log_2(\text{页框数})\rceil$ 位，再按字节向上取整。

例如物理内存 $4\text{ GB}$、页大小 $4\text{ KB}$，页框数为 $2^{20}$，页框号需要 20 位，向上取整到 3 字节，实际一般做成 4 字节，方便对齐和访问。

需要注意，页表项里还要放状态位、保护位、脏位等，所以实际长度通常比理论最小值大；题目如果说“页表项占 4B”，那这些额外的位就都算在这 4B 里。

辨析要访问主存多少次#

需要分析 TLB / cache 是否存在，如果 TLB 不命中（或者不存在），那么肯定要访问一次主存即访问页表；

如果 cache 存在，那么就不需要去访问主存（得到指令）。

所以，总共最少可以访问 0 次主存，但是其他时候要具体情况具体分析，尤其是不要忽略了 cache 可能不命中导致的访问主存。

以 FAT 系统为例，访问 ./A/B/C#

在 FAT 系统中，FAT 表开机即载入并常驻内存，目录也是文件，FCB 即目录项。

• open 阶段：获取 C 的元数据，在内存中登记并返回文件描述符 fd
  • 读取 A：根据块号，读磁盘将目录文件 A 的盘块读入内存。在 A 中遍历查找目录项 B，获得 B 的起始物理块号。
  • 读取 B：根据块号，读磁盘将目录文件 B 的盘块读入内存。在 B 中遍历查找目录项 C
• read 阶段：从 C 的 FCB 中拿到起始块号。因为 FAT 表完全在内存中，系统在内存的 FAT 表中顺着指针链条追踪（做 1047 次链表跳转），即可在内存中瞬间计算出第 1048 块的真实物理块号。根据算出的物理块号，读磁盘 1 次，将第 1048 块的数据内容送入用户缓冲区。

open 访问磁盘：2 次。

read 访问磁盘：1 次。

以 UFS 系统为例，访问 ./A/B/C#

• open 阶段
  • 读 A 的 inode：根据 inode 编号去磁盘的 inode 区读出 A 的 inode。
  • 读 A 的目录项：根据 A 的 inode 里的直接指针，读出 A 的目录数据块。在其中匹配得到 B 的 inode 编号。
  • 读 B 的 inode：根据 B 的 inode 编号去磁盘的 inode 区读出 B 的 inode。
  • 读 B 的目录项：根据 B 的 inode 里的直接指针，读出 B 的目录数据块。在其中匹配得到 C 的 inode 编号。
  • 读 C 的 inode：根据 C 的 inode 编号去磁盘的 inode 区读出 C 的 inode。
• read 阶段
  • 此时 C 的 inode 已经在内存中。我们需要判断第 1048 块（逻辑块号 1047，若按 1-based 算则是第 1048 块）落在哪里：
    • 直接索引：第 $0 \sim 11$ 块（共 12 块）。
    • 一级间接索引：第 $12 \sim 12 + 1024 - 1 = 1035$ 块（共 1024 块）。
    • 二级间接索引：第 $1036 \sim 1036 + 1024 \times 1024 - 1$ 块。
    • 因此，第 1048 块必定落在二级（双重）间接索引中
  • 读入第一层索引块
  • 读入第二层索引块
  • 读入数据

open：5 次。 read：至少 1 次，按照本题设置的情景为 3 次。