操作系统 考点总结

🌟 五星重要程度评价标准

星级 含义 应对策略
⭐ 了解即可，几乎不考 过一遍有个印象
⭐⭐ 可能考小题（选择/填空/判断） 记住关键结论
⭐⭐⭐ 常考小题，也可能出简答 熟记概念+会简单计算
⭐⭐⭐⭐ 高频考点，大题可能涉及 必须会做完整计算题
⭐⭐⭐⭐⭐ 期末必考大题！ 反复练习，直到烂熟于心

优先级：5星 > 4星 > 3星 > 2星 > 1星 —— 复习时按星级从高到低覆盖！

覆盖章节：Chp1 操作系统引论 | Chp2 进程的描述与控制 | Chp3 处理机调度与死锁 | Chp4 存储器管理 | Chp5 虚拟存储器 | Chp6 输入输出系统 | Chp7 文件管理 | Chp8 磁盘存储器的管理

含46道高质量考研408真题同型题与综合题，每题均配有可复核解析

📗 第一章 操作系统引论

1. 操作系统的目标与作用 ⭐

目标 说明
有效性 提高资源利用率和系统吞吐量
方便性 使计算机系统更易使用
可扩充性 采用新结构，易于增删改功能
开放性 统一开放环境，跨平台互通

OS的三重作用：

  1. 用户与硬件之间的接口（命令方式、系统调用方式、图形窗口方式）
  2. 计算机系统的资源管理者（处理机、存储器、I/O设备、文件）
  3. 对计算机资源的抽象（裸机 → 虚机器/扩充机器）

2. OS的发展过程 ⭐

阶段 特征 缺点/优点
人工操作 单用户单任务，CPU等人 人机矛盾，浪费CPU
单道批处理 监督程序，自动顺序处理 CPU仍等待I/O
多道批处理 多道并发，引入进程调度 平均周转时间长，交互性差
分时系统 时间片轮转，多终端交互 响应及时，交互性强
实时系统 任务在截止时间内完成 可靠性高，实时性强

多道批处理特征： 多道性、无序性、调度性
分时系统特征： 多路性、交互性、独立性、及时性
实时系统分类： 硬实时任务(HRT)、软实时任务(SRT)
实时 vs 分时： 实时可靠性>分时；交互性：分时>实时

3. OS的四大基本特征 ⭐⭐⭐

特征 说明 关键点
并发性 多事件在同一时间间隔内发生（宏观并行，微观交替） 是最基本特征，其他特征以并发为前提
共享性 互斥共享（临界资源）+ 同时访问（磁盘等） 并发与共享互为存在条件
虚拟性 时分复用技术（虚拟处理机）；空分复用技术 提高资源利用率
异步性 进程以不可预知的速度推进 每次执行结果应可再现

⚠️ 并行 vs 并发：并行 = 同一时刻；并发 = 同一时间间隔

4. OS的主要功能 ⭐⭐

功能 主要内容
处理机管理 进程控制、进程调度、进程同步、进程通信
存储管理 存储分配与回收、存储保护、地址映射、内存扩充
设备管理 缓冲管理、设备分配、设备处理
文件管理 存储空间管理、目录管理、文件读写管理与保护
用户接口 联机接口（命令行）、脱机接口（JCL）、图形接口

程序接口（系统调用） = 用户程序取得OS服务的唯一途径

5. OS的结构设计 ⭐

结构类型 特点
无结构OS 编码紧凑，维护难
模块化OS 模块-接口法，可并行开发；接口难确定，依赖关系复杂
分层式OS 单向依赖，易正确性保证；通信开销大，效率降低
微内核OS 内核只保留最基本功能；客户-服务器模式；可扩充性、可靠性、可移植性强；但多次上下文切换，运行效率降低

微内核基本功能： 进程/线程管理、低级存储器管理、中断和陷入处理

📝 第一章 典型例题

例1.1 用户态、内核态与系统调用 ⭐⭐⭐ 🎓 408真题同型改编

用户进程正在用户态运行。下列事件中，由用户程序主动发起，并通过陷入指令进入内核态的是（ ）
A. 时钟中断　B. 缺页异常　C. 执行 read()　D. 外设完成中断

答案：C

解析：

事件 发起者 类型 是否由当前用户程序主动请求
时钟中断 时钟硬件 外中断 否
缺页异常 CPU执行指令时发现页面不在内存 内异常 非程序显式请求
read() 用户程序 系统调用/陷入 是
外设完成中断 I/O设备 外中断 否

核心区分：系统调用是用户程序主动请求OS服务；中断通常来自当前指令流之外；异常由当前指令执行引起。

例1.2 多道程序设计与CPU利用率 ⭐⭐⭐ 🎓 408真题同型改编

某系统内存为2GB，操作系统占用512MB。每个进程驻留内存需384MB，且任一进程等待I/O的概率为0.6，各进程等待I/O相互独立。忽略调度开销，求系统可容纳的最大进程数及CPU利用率。

解：

  1. 可用于进程的内存：$2048-512=1536\text{MB}$
  2. 最大多道程序度：$n=1536/384=4$
  3. 仅当4个进程同时等待I/O时CPU空闲：
结论 结果
最大驻留进程数 4
理论CPU利用率 87.04%

易错点：公式中的$p$是“单个进程等待I/O的概率”，不是使用CPU的概率。

📘 第二章 进程的描述与控制

1. 前趋图 ⭐⭐

  • 前趋图(DAG，有向无环图)，描述进程执行的先后顺序
  • 结点 = 进程/程序段；有向边 = 前趋关系
  • 前趋图中不允许有循环！

程序顺序执行特征： 顺序性、封闭性、可再现性
程序并发执行特征： 间断性、失去封闭性、不可再现性

2. 进程的定义与特征 ⭐⭐⭐

进程的定义：

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立基本单位。

进程实体 = 程序段 + 数据段 + PCB

进程的四大特征：

特征 说明
动态性 进程有生命期（创建→调度→撤销），最基本特征
并发性 多进程同时驻留内存，并发执行
独立性 独立运行、获得资源、接受调度的基本单位
异步性 各进程以不可预知速度推进

程序 vs 进程：

  • 程序是静态的，进程是动态的
  • 程序可长期保存；进程有生命周期
  • 一个程序可对应多个进程；一个进程可包含多个程序

3. 进程的状态与转换 ⭐⭐⭐

三种基本状态：

  • 就绪态：已分配除CPU外所有资源，等待CPU
  • 执行态：正在CPU上运行（单处理机只有一个）
  • 阻塞态：因等待事件无法继续执行，让出CPU

五状态模型（加入创建态和终止态）：

1
2
3
新建 → 就绪 ←→ 执行 → 终止
              ↓↑
            阻塞

状态转换：

  • 就绪→执行：调度程序分配CPU
  • 执行→就绪：时间片到，被抢占
  • 执行→阻塞：等待事件（I/O等）
  • 阻塞→就绪：等待事件完成

4. 进程控制块 PCB ⭐⭐

PCB是进程在系统中存在的唯一标志，包含：

  • 进程标识符（PID）
  • 处理机状态（寄存器内容）
  • 进程调度信息（优先级、状态）
  • 进程控制信息（程序地址、资源清单）

进程控制的原语：

  • 进程创建原语：申请空白PCB → 填写信息 → 分配资源 → 插入就绪队列
  • 进程终止原语：清空PCB → 回收资源
  • 进程阻塞原语(block)：执行态 → 阻塞态
  • 进程唤醒原语(wakeup)：阻塞态 → 就绪态

5. 进程同步 ⭐⭐⭐⭐⭐

核心概念：

  • 临界资源：一次仅允许一个进程访问的资源（互斥共享）
  • 临界区：访问临界资源的代码段
  • 同步机制四准则： 空闲让进、忙则等待、有限等待、让权等待

整型信号量 vs 记录型信号量：

整型信号量 记录型信号量
特点 P操作忙等 不满足”让权等待” 阻塞自身入队 满足四准则
P(S) while(S≤0); S— S—; if(S<0) block(S.list)
V(S) S++ S++; if(S≤0) wakeup(S.list)

信号量含义：

  • S > 0：有 S 个可用资源
  • S = 0：无可用资源，无等待进程
  • S < 0：|S| 个进程在阻塞队列中等待

6. 信号量的应用 ⭐⭐⭐⭐⭐

互斥： mutex 初值通常为 1，P在临界区前，V在临界区后，成对出现
同步： 同步信号量初值通常为 0，一进程V（发信号），另一进程P（等信号）

⚠️ 关键规则：当P操作中既有同步P又有互斥P时，同步P必须在互斥P前面！

AND型信号量： 一次性申请所有资源，要么全分配要么全不分配，避免死锁

7. 经典同步问题 ⭐⭐⭐⭐⭐

生产者-消费者问题

1
2
3
4
5
6
7
信号量：
  Buffers = N    // 缓冲区空闲容量（同步）
  Products = 0   // 产品数量（同步）
  mutex = 1      // 互斥访问缓冲区

生产者：P(Buffers) → P(mutex) → 放产品 → V(mutex) → V(Products)
消费者：P(Products) → P(mutex) → 取产品 → V(mutex) → V(Buffers)

⚠️ P(Buffers)和P(mutex)不能交换顺序（会死锁）

读者-写者问题——三种策略详解 ⭐⭐⭐⭐⭐

基本约束：

  • 读者与写者、写者与写者不能同时访问缓冲区
  • 无写者时，各读者可同时访问缓冲区
① 读者优先

只要没有写者正在写，后续读者可直接进入读（即使有写者在等待），写者可能饥饿。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Semaphore mutex = 1;    // 互斥访问共享数据区
Semaphore mrc = 1;      // 互斥访问readcount
int readcount = 0;

Reader() {
    while(1) {
        P(mrc);
        readcount++;
        if(readcount == 1) P(mutex);  // 第1个读者锁住数据区
        V(mrc);
        Read;
        P(mrc);
        readcount--;
        if(readcount == 0) V(mutex);  // 最后1个读者释放数据区
        V(mrc);
    }
}

Writer() {
    while(1) {
        P(mutex);    // 写者独占数据区
        Write;
        V(mutex);
    }
}

💡 读者优先的后果： 一旦有读者进入，后续读者无需等待写者，可源源不断进入 → 写者可能长时间等待，产生饥饿。

② 读写公平（FCFS）

读者和写者按到达顺序排队，谁先到谁先服务。新增信号量rw实现FIFO排队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Semaphore mutex = 1;    // 互斥访问共享数据区
Semaphore rw = 1;       // FCFS排队信号量
Semaphore mrc = 1;      // 互斥访问readcount
int readcount = 0;

Reader() {
    while(1) {
        P(rw);           // ← 先排队! 防止越过等待中的写者
        P(mrc);
        if(readcount == 0) P(mutex);
        readcount++;
        V(mrc);
        V(rw);           // ← 排队完毕, 后续读者/写者可继续排队
        Read;
        P(mrc);
        readcount--;
        if(readcount == 0) V(mutex);
        V(mrc);
    }
}

Writer() {
    while(1) {
        P(rw);           // ← 写者也排队
        P(mutex);
        Write;
        V(mutex);
        V(rw);           // ← 释放排队位
    }
}

💡 关键理解： rw信号量的作用——无论是读者还是写者，都必须先P(rw)排队。读者拿到排队权后立即V(rw)释放，允许后续读者/写者继续排队；写者拿到排队权后不立即释放rw（持有rw直到写完V(rw)），阻止了新读者越过正在等待的写者。

③ 写者优先

当有写者等待时，后续读者被阻塞；读者和写者都等待时，写者优先访问缓冲区。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Semaphore w = 1;        // 写优先控制信号量
Semaphore mutex = 1;    // 互斥访问共享数据区
Semaphore mrc = 1;      // 互斥访问readcount
Semaphore mwc = 1;      // 互斥访问writecount
int readcount = 0;
int writecount = 0;

Reader() {
    while(1) {
        P(w);            // ← 写者优先的关键! 有写者在等→w=0→新读者阻塞
        P(mrc);
        readcount++;
        if(readcount == 1) P(mutex);  // 第1个读者锁住数据区
        V(mrc);
        V(w);            // ← 读者进入后释放w, 允许后续读者判断
        Read;
        P(mrc);
        readcount--;
        if(readcount == 0) V(mutex);
        V(mrc);
    }
}

Writer() {
    while(1) {
        P(mwc);
        if(writecount == 0) P(w);     // ← 第1个写者锁住w→阻止后续读者!
        writecount++;
        V(mwc);
        P(mutex);       // 写者独占数据区
        Write;
        V(mutex);
        P(mwc);
        writecount--;
        if(writecount == 0) V(w);     // ← 最后1个写者释放w→允许读者进入
        V(mwc);
    }
}

写者优先规则解读：

“读者和写者都等待时，写者优先访问缓冲区”意味着：有写者正在访问临界资源时（此时w=0），新来的读者A执行P(w)被阻塞；新来的写者B由于writecount≥1，不再执行P(w)而直接P(mutex)被阻塞。当正在写的写者撤出后V(mutex)唤醒写者B → 写者B先于读者A进入，实现了写者优先插队！

策略 核心信号量 读者行为 写者行为 谁可能饥饿
读者优先 mutex + mrc 不等待其他读者 等所有读者撤出 写者
读写公平 mutex + rw + mrc 先P(rw)排队 先P(rw)排队 无
写者优先 w + mutex + mrc + mwc P(w)可能被阻塞 writecount>0不P(w) 读者

⚠️ 考试关键区别： 读者优先 vs 写者优先的核心差异在于是否有一个信号量让写者”占位”。写者优先中第一个写者P(w)锁住入口，后续读者被挡在P(w)外面；而后续写者不需要再P(w)，可直接进入P(mutex)排队等数据区 → 实现写者插队。

哲学家就餐问题

死锁成因： 5人同时各拿左边筷子，均等右边筷子 → 循环等待死锁
解决方案：

  1. 最多允许4人同时吃（至少1人能拿到两根筷子）
  2. 奇数号先取左边，偶数号先取右边
  3. AND型信号量（推荐）：一次性申请两根筷子

哲学家问题四种解法对比：

解法 原理 并发度 实现复杂度
限制人数法 信号量room=4，先P(room)再取筷 中（4人可同时尝试） 简单
奇偶编号法 奇数先左后右，偶数先右后左 高（可5人同时） 简单
AND信号量法 Swait一次性申请两根筷子 高 需AND型支持
管程法 仅当两根筷子都可用时才分配 高 需管程支持

理发师问题 🏫 考研经典题

理发店有一名理发师、一把理发椅和n把等候椅。若无顾客，理发师睡觉；顾客到来若理发师睡着则唤醒他，若理发师忙则坐等候椅等待；若等候椅满则离开。用PV操作描述。

信号量 初值 含义
barber 0 理发师是否就绪（同步：顾客→理发师）
customers 0 是否有顾客在等待（同步：理发师→顾客）
mutex 1 互斥访问waiting计数器 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int waiting = 0;                     // 等待的顾客数
semaphore barber = 0, customers = 0, mutex = 1;

理发师进程：                         顾客进程：
while(1) {                          P(mutex);
    P(customers);  // 等顾客           if(waiting < n) {
    P(mutex);                          waiting++;
    waiting--;                         V(customers);   // 有顾客了
    V(barber);     // 理发师就绪        V(mutex);
    V(mutex);                          P(barber);      // 等理发师
    理发();                             理发();
}                                   } else {
                                        V(mutex);       // 等位满，离开
                                    }

💡 关键理解： customers信号量是理发师等顾客；barber信号量是顾客等理发师。两者构成双向同步。

8. 管程 ⭐⭐

  • 管程：共享资源的数据结构 + 对其操作的一组过程构成的资源管理模块
  • 特征： 模块化、抽象数据类型、信息封装、互斥性（任一时刻只有一个进程进入管程）
  • 条件变量： x.wait()（阻塞调用进程并释放管程）；x.signal()（唤醒阻塞在x上的进程）
  • 优点： 将同步机制集中在管程内，不分散；正确性更易验证

9. 进程通信 ⭐⭐

类型 方式 特点
低级通信 信号量机制 速度快，传送量小，不透明
共享存储器（高级） 申请共享内存区 高效，速度快
管道通信 pipe文件 单向，读写互斥，需同步
消息传递 直接通信/信箱通信 最广泛，透明，格式化消息
客户-服务器 套接字、RPC 网络环境主流

10. 线程 ⭐⭐

引入线程的原因： 将进程的”拥有资源”和”调度执行”两个属性分开，减少并发执行的时空开销

对比项 进程 线程
调度单位 无线程时是调度基本单位 引入线程后是调度基本单位
资源 拥有资源的独立单位 几乎不拥有资源，共享进程资源
独立性 进程间独立性高 同进程内线程独立性低
系统开销 创建/撤销/切换开销大 开销远小于进程

线程实现方式：

  • 用户级线程(ULT)： 管理在用户空间，内核不知道其存在；切换无需内核；一个线程阻塞导致整个进程阻塞
  • 内核支持线程(KST)： 内核管理；一个线程阻塞不影响其他线程；用户态-内核态切换开销大
  • 组合方式： 多对一、一对一、多对多（推荐，兼顾两者优点）

📝 第二章 典型例题

例2.1 进程状态转换综合判断 ⭐⭐⭐⭐ 🎓 408真题同型改编

单处理机系统中，进程P正在运行。依次发生：
① P执行时间片用完；② P再次获得CPU后请求磁盘读；③ 磁盘读完成。
写出P的状态转换序列，并指出哪一步必须由进程调度程序参与。

解：

事件 状态转换 原因
时间片用完 运行态 → 就绪态 被时钟中断抢占
再次获得CPU 就绪态 → 运行态 进程调度程序选择并分派
请求磁盘读 运行态 → 阻塞态 等待I/O事件
磁盘读完成 阻塞态 → 就绪态 I/O中断唤醒进程

状态序列：

1
运行 → 就绪 → 运行 → 阻塞 → 就绪

阻塞态不能直接变为运行态；I/O完成后先进入就绪队列，再等待调度。

例2.2 前趋关系的信号量实现 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

6个程序段的前趋关系为：
$S_1\rightarrow S_3$，$S_1\rightarrow S_4$，$S_2\rightarrow S_4$，
$S_3\rightarrow S_5$，$S_4\rightarrow S_5$，$S_4\rightarrow S_6$。
用信号量实现其同步关系。

解：

为每条前趋边设置一个初值为0的信号量：

1
2
3
4
5
6
7
8
9
10
11
semaphore a=0, b=0, c=0, d=0, e=0, f=0;

S1: 执行S1; V(a); V(b);          // 通知S3、S4
S2: 执行S2; V(c);                // 通知S4

S3: P(a); 执行S3; V(d);          // 通知S5

S4: P(b); P(c); 执行S4; V(e); V(f); // 同时等待S1、S2

S5: P(d); P(e); 执行S5;          // 同时等待S3、S4
S6: P(f); 执行S6;                // 等待S4

一个结点有几条入边，就必须等待几个同步信号；有几条出边，就要发送几个同步信号。

例2.3 批量生产中的隐藏死锁 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

多个生产者与多个消费者共享5个缓冲区。每个生产者必须一次放入2件产品，每个消费者每次取1件。若生产者直接连续执行两次 P(empty)，说明可能出现的死锁，并给出修正方案。

问题分析：

例如缓冲区初始为空，5个生产者并发执行：每个生产者都先成功执行第一次 P(empty)，使 empty 从5减到0；随后它们都在第二次 P(empty) 处阻塞。此时尚无生产者完成写入，full=0，消费者也全部阻塞，于是形成死锁。

修正：用批量预约互斥量保证一次性申请2个空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
semaphore empty = 5, full = 0, mutex = 1;
semaphore reserve2 = 1;   // 串行化“申请两个空位”的过程

Producer() {
    P(reserve2);
    P(empty);
    P(empty);
    V(reserve2);

    P(mutex);
    放入2件产品;
    V(mutex);

    V(full);
    V(full);
}

Consumer() {
    P(full);
    P(mutex);
    取出1件产品;
    V(mutex);
    V(empty);
}

更严格的实现可使用AND型信号量原子申请2个空位。关键是避免多个生产者各占一部分空位后相互等待。

例2.4 水果盘同步问题 ⭐⭐⭐⭐⭐ 🎓 408经典同步模型改编

桌上只有一个盘子。父亲只放苹果，母亲只放橘子；女儿只吃苹果，儿子只吃橘子。盘子空时父母才能放，盘中有对应水果时孩子才能取。用PV操作实现。

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
semaphore plate = 1;   // 盘子为空
semaphore apple = 0;   // 盘中有苹果
semaphore orange = 0;  // 盘中有橘子

Father() {
    while (1) {
        准备苹果;
        P(plate);
        放苹果;
        V(apple);
    }
}

Mother() {
    while (1) {
        准备橘子;
        P(plate);
        放橘子;
        V(orange);
    }
}

Daughter() {
    while (1) {
        P(apple);
        取苹果;
        V(plate);
        吃苹果;
    }
}

Son() {
    while (1) {
        P(orange);
        取橘子;
        V(plate);
        吃橘子;
    }
}

plate控制容量，apple和orange分别建立定向同步关系，不能只用一个“有水果”信号量。

例2.5 公平读者—写者问题 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

多个读者可同时读共享文件，写者必须独占。要求读者和写者按到达先后竞争，不能让写者长期饥饿。写出PV算法。

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
semaphore queue = 1;     // 到达次序闸门
semaphore rw = 1;        // 文件读写锁
semaphore rmutex = 1;    // 保护readCount
int readCount = 0;

Reader() {
    P(queue);
    P(rmutex);
    if (readCount == 0) P(rw);
    readCount++;
    V(rmutex);
    V(queue);

    读文件;

    P(rmutex);
    readCount--;
    if (readCount == 0) V(rw);
    V(rmutex);
}

Writer() {
    P(queue);
    P(rw);
    V(queue);

    写文件;

    V(rw);
}

queue使后来到达的读者不能越过已经等待的写者；同批读者仍可并发读取。

例2.6 用户级线程与内核级线程 ⭐⭐⭐⭐ 🎓 408真题同型改编

一个进程含3个线程。若采用多对一用户级线程模型，线程T1执行阻塞式系统调用；若改为一对一模型，结果分别如何？在双核处理器上，两种模型最多可有多少个该进程线程真正并行？

答案：

模型 T1阻塞后的影响 双核上最大真正并行数
多对一 内核只看到一个执行实体，整个进程阻塞 1
一对一 仅T1阻塞，T2、T3仍可运行 2

详细解释：

  1. 多对一模型为什么会整体阻塞？
    T1、T2、T3虽然在用户空间表现为3个线程，但它们共同映射到同一个内核线程。内核调度器只知道这个内核线程，并不知道其内部还有T1、T2、T3。T1执行阻塞式系统调用后，内核把这个唯一的内核线程置为阻塞态，因此同一进程中的T2、T3也失去了运行载体。

  2. 多对一模型为什么不能在双核上并行？
    真正被处理器调度的是内核线程。该进程只有1个内核线程，所以即使机器有2个CPU核心，同一时刻最多也只能有1个用户线程执行。用户线程之间只能在用户空间轮流切换，属于并发而非并行。

  3. 一对一模型为什么只阻塞T1？
    每个用户线程分别对应一个内核线程。T1对应的内核线程阻塞，不会改变T2、T3对应内核线程的就绪状态，内核仍可调度T2、T3。

  4. 一对一模型为何最多并行2个？
    可运行线程数为3，处理器核心数为2，真正并行数取二者较小值：

    若T1此时正因系统调用阻塞，则剩余的T2、T3恰好可以分别运行在两个核心上。

易错点：用户级线程“切换不进入内核”不等于“能利用多核”。能否多核并行，取决于内核可见的调度实体数量。

📙 第三章 处理机调度与死锁

1. 调度层次 ⭐⭐⭐

层次 别名 对象 频率 应用
高级调度 作业调度/长程调度 作业（外存→内存） 几分钟一次 多道批处理
中级调度 内存调度/中程调度 进程（换入/换出） 取决于内存 存储器管理
低级调度 进程调度/短程调度 进程（就绪队列→CPU） 10~100ms 所有OS

进程调度是最基本的调度，运行频率最高，算法不宜复杂

2. 调度算法 ⭐⭐⭐⭐⭐

先来先服务 FCFS

  • 按到达顺序调度
  • 有利于长作业/CPU繁忙型，不利于短作业
  • 简单，效率不高

短作业优先 SJF/SPF

  • 选CPU时间最短的作业/进程
  • 比FCFS改善了平均周转时间和吞吐量
  • 缺点：长作业可能饥饿；需预知执行时间

高响应比优先 HRRN ⭐⭐⭐⭐

响应比公式： R_p = (等待时间 + 服务时间) / 服务时间 = 1 + 等待时间/服务时间

  • 折中算法：既照顾短作业又不让长作业无限等待
  • 每次调度前计算响应比，增加系统开销

优先级调度 PSA

  • 静态优先级：进程创建时确定，不变；简单，低优先级进程可能饥饿
  • 动态优先级：随运行动态调整（如占用CPU越长降优先级）

时间片轮转 RR ⭐⭐⭐⭐

  • 所有就绪进程按FCFS排队，逐个分配时间片
  • 时间片太小：切换频繁，开销大
  • 时间片太大：退化为FCFS
  • 时间片选取：略大于一次典型交互所需的时间

多级反馈队列 MFQ ⭐⭐⭐⭐

  • 设多个优先级依次降低的就绪队列，优先级越高时间片越小
  • 新进程进第1队列（FCFS），时间片内未完成降入下一队列
  • 最低级队列采用RR
  • 高优先级队列有进程时，立即抢占低优先级队列的运行进程
  • 优点： 不需预知执行时间，满足多种类型进程需要

3. 调度算法性能指标 ⭐⭐⭐

周转时间 = 完成时间 - 到达时间

带权周转时间 = 周转时间 / 服务时间

4. 进程调度方式 ⭐⭐⭐

方式 说明 适用
非抢占方式 进程运行直到完成或阻塞才放弃CPU 批处理系统
抢占方式 根据某种原则强行剥夺CPU分配给其他进程 分时、实时系统

5. 死锁概述 ⭐⭐⭐⭐

死锁定义：

若一组进程中的每一个进程都在等待仅由该组内的其他进程才能引发的事件，则称该组进程是死锁的。

产生死锁的原因：

  1. 竞争不可抢占性资源（数量不足）
  2. 竞争可消耗性资源（通信消息）
  3. 进程推进顺序不当

产生死锁的四个必要条件 ⭐⭐⭐：

条件 说明
互斥条件 资源被排他性使用
请求和保持条件 占有资源的同时请求被其他进程占有的资源
不可抢占条件 资源只能由进程自主释放，不可被强行夺走
循环等待条件 存在进程-资源的循环等待链

四个条件同时成立才会产生死锁

6. 预防死锁 ⭐⭐⭐

通过破坏必要条件中的一个或多个（互斥条件是固有属性，不能破坏）：

破坏的条件 方法 优缺点
破坏请求和保持 ①全部资源一次分配；②获得部分后，需新资源时先释放已有资源 简单安全但资源浪费，易饥饿
破坏不可抢占 申请资源未满足时，释放已占资源 实现复杂，代价大，可能使前段工作失效
破坏循环等待 有序资源分配法（按序号递增申请） 利用率有改善；新增资源不便，编程不自由

7. 避免死锁——银行家算法 ⭐⭐⭐⭐⭐

核心思想： 动态分配资源时，先判断分配后系统是否仍处于安全状态，若安全则分配，否则等待。

安全状态： 系统能找到某种进程推进顺序（安全序列），使每个进程都能顺利完成。

数据结构（设n个进程，m类资源）：

数据结构 含义
Available[m] 各类可用资源数
Max[n][m] 各进程的最大需求
Allocation[n][m] 各进程已分配量
Need[n][m] 各进程还需要量

关系： Need[i][j] = Max[i][j] - Allocation[i][j]

银行家算法流程（进程Pi请求Request[i]）：

  1. Request[i] ≤ Need[i]，否则出错
  2. Request[i] ≤ Available，否则等待
  3. 假设分配（修改Available、Allocation、Need）
  4. 运行安全性算法检查是否安全
  5. 安全则真正分配；否则撤销假设，Pi等待

安全性算法：

  • Work = Available，Finish[i] = false
  • 找满足 Finish[i]=false 且 Need[i]≤Work 的进程i
  • 令 Work = Work + Allocation[i]，Finish[i] = true
  • 重复直到所有进程 Finish[i]=true（安全）或找不到（不安全）

8. 死锁的检测与解除 ⭐⭐⭐

死锁检测工具： 资源分配图

死锁定理： 系统处于死锁状态 ⟺ 资源分配图不可完全简化

简化步骤：

  1. 找到一个既非阻塞（能获得所需资源）又非孤立的进程结点
  2. 模拟其获得资源运行完毕，消去其请求边和分配边（成为孤立结点）
  3. 重复以上步骤，若能消去所有边则可完全简化（无死锁）

死锁解除方法：

  1. 结束所有进程，重启OS（简单但损失大）
  2. 抢占足够资源给死锁进程
  3. 终止所有死锁进程
  4. 逐个终止死锁进程，逐步回收资源（最常用）

9. 处理死锁方法对比 ⭐⭐⭐

方法 防范程度 资源利用率 进程阻塞频度
预防 最强 最低 高
避免（银行家） 较强 较高 较低
检测与解除 最弱 最高 最低

📝 第三章 典型例题

例3.1 最短剩余时间优先SRTF ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

进程到达时间和服务时间如下。采用SRTF，求调度序列、平均周转时间和平均带权周转时间。

进程 到达 服务
P1 0 8
P2 1 4
P3 2 3
P4 3 1

解：

调度序列：

1
0-1 P1 | 1-2 P2 | 2-3 P3 | 3-4 P4 | 4-6 P3 | 6-9 P2 | 9-16 P1
进程 完成 周转 带权周转
P1 16 16 2.00
P2 9 8 2.00
P3 6 4 1.33
P4 4 1 1.00

例3.2 时间片轮转RR ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

采用RR算法，时间片$q=2$。到达时刻恰好等于时间片结束时，新到达进程先进入队列，当前进程随后重新排队。

进程 到达 服务
P1 0 5
P2 1 3
P3 2 4

解：

1
2
0-2 P1 | 2-4 P2 | 4-6 P3 | 6-8 P1 |
8-9 P2 | 9-11 P3 | 11-12 P1
进程 完成 周转 带权周转
P1 12 12 2.40
P2 9 8 2.67
P3 11 9 2.25

平均周转时间：$\boxed{29/3\approx9.67}$
平均带权周转时间：$\boxed{2.44}$

例3.3 高响应比优先HRRN ⭐⭐⭐⭐ 🎓 408真题同型改编

非抢占式HRRN调度如下作业，求执行顺序和平均周转时间。

作业 到达 服务
J1 0 4
J2 1 3
J3 2 8
J4 3 2

解：

  • $t=0$：仅J1，运行至4。
  • $t=4$：$R_2=2$，$R_3=1.25$，$R_4=1.5$，选J2。
  • $t=7$：$R_3=1.625$，$R_4=3$，选J4。
  • 最后运行J3。

执行顺序：$\boxed{J1\rightarrow J2\rightarrow J4\rightarrow J3}$

作业 完成 周转
J1 4 4
J2 7 6
J4 9 6
J3 17 15

平均周转时间：$(4+6+6+15)/4=\boxed{7.75}$

例3.4 多级反馈队列行为分析 ⭐⭐⭐⭐ 🎓 408真题同型改编

某三级反馈队列：Q1时间片1ms，Q2时间片2ms，Q3采用FCFS。新进程进入Q1；用完时间片未结束则降一级；高优先级队列到达新进程时抢占低级队列。
P1在0ms到达，需6ms；P2在2ms到达，需1ms。写出0～7ms调度过程。

解：

1
2
3
4
5
0-1  P1(Q1)，剩5ms，降入Q2
1-2  P1(Q2)，此时P2到达Q1并抢占
2-3  P2(Q1)，完成
3-4  P1继续Q2剩余时间片，剩4ms，降入Q3
4-8  P1(Q3)，完成

P1在Q2只运行了1ms便被抢占，恢复后应继续使用该次尚未用完的1ms时间片；题目若另行规定“被抢占即重新获得完整时间片”，结果会不同。

例3.5 安全状态与安全序列 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

系统有3类资源，当前 Available=(1,1,2)：

进程 Allocation Need
P0 (1,0,0) (0,1,1)
P1 (0,1,1) (1,0,1)
P2 (1,1,0) (1,0,0)
P3 (0,0,1) (0,1,1)

判断系统是否安全，并给出一个安全序列。

解：

步骤 Work 可完成进程 完成后Work
1 (1,1,2) P0 (2,1,2)
2 (2,1,2) P2 (3,2,2)
3 (3,2,2) P1 (3,3,3)
4 (3,3,3) P3 (3,3,4)

安全序列之一：

安全状态不表示当前所有请求都能立即满足，而表示至少存在一种使全部进程完成的顺序。

例3.6 银行家算法资源请求 ⭐⭐⭐⭐⭐ 🎓 408经典模型改编

当前 Available=(3,3,2)，资源分配如下：

进程 Allocation Max
P0 (0,1,0) (7,5,3)
P1 (2,0,0) (3,2,2)
P2 (3,0,2) (9,0,2)
P3 (2,1,1) (2,2,2)
P4 (0,0,2) (4,3,3)

P1提出请求 (1,0,2)，能否立即分配？

解：

P1原Need为$(1,2,2)$，请求不超过Need和Available。试分配后：

  • Available=(2,3,0)
  • P1的 Allocation=(3,0,2)
  • P1的 Need=(0,2,0)

安全性检查可得到：

因此请求后系统仍安全，可以立即分配。

银行家算法必须先“试分配”，再执行安全性检查，不能仅凭 Request≤Available 就批准。

例3.7 同类资源的死锁临界值 ⭐⭐⭐⭐ 🎓 408真题同型改编

有5个进程竞争同一类资源，每个进程最多需要3个资源实例。至少配置多少个实例，才能保证无论资源怎样分配都不会死锁？

解：

最坏情况下，每个进程都先占有$3-1=2$个，再等待第3个。要保证至少有一个进程能再获得1个并完成：

若只有10个资源，可出现每个进程各占2个并继续请求1个的死锁状态。

通式：$n$个进程、每个最多需$m$个同类资源，保证不死锁的最小资源数为$n(m-1)+1$。

例3.8 死锁检测算法 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

当前 Available=(0,0,1)：

进程 Allocation Request
P0 (1,0,0) (0,1,0)
P1 (0,1,0) (1,0,0)
P2 (0,0,1) (0,0,0)

检测系统中的死锁进程。

解：

  1. Work=(0,0,1)，P2的请求为0，可完成并释放资源，得到 Work=(0,0,2)。
  2. P0仍需要1个B，P1仍需要1个A，而Work中A、B均为0。
  3. 再无进程可完成。

因此死锁进程集合为：

能完成的P2不是死锁进程；检测算法最终 Finish=false 的进程才属于死锁集合。

例3.9 时间片与上下文切换开销 ⭐⭐⭐⭐ 🎓 408真题同型改编

对一组长期运行的CPU密集型进程采用RR。每次上下文切换耗时0.2ms。忽略其他开销，分别计算时间片为5ms和0.5ms时CPU用于执行用户程序的比例。

解：

长期稳定时，每个周期约为“执行一个时间片+一次切换”：

时间片 利用率
5ms $5/(5+0.2)=\boxed{96.15\%}$
0.5ms $0.5/(0.5+0.2)=\boxed{71.43\%}$

时间片过小会显著增加切换开销；过大则使RR逐渐退化为FCFS，交互响应变差。

📒 第四章 存储器管理

1. 存储器的层次结构 ⭐⭐

层级 存储器 特点
1 CPU寄存器 速度最快，容量最小，价格最高
2 高速缓存(Cache) 速度快，容量小（KB~MB级），L1/L2/L3
3 主存(内存) 速度较快，容量中等（GB级）
4 磁盘缓存 利用主存空间暂存磁盘数据
5 固定磁盘 速度较慢，容量大（TB级）
6 可移动存储介质 速度最慢，容量大，可脱机

前四层属OS存储管理范畴，后两层属设备管理范畴
寄存器和主存称为可执行存储器

2. 程序的装入和链接 ⭐⭐⭐

用户程序处理三部曲：编译 → 链接 → 装入

程序的三种装入方式：

装入方式 特点 适用环境
绝对装入 编译时产生绝对地址代码 单道程序
可重定位装入（静态重定位） 装入时一次性完成地址变换 多道程序，但运行中不可移动
动态运行时装入 执行时才进行地址转换，需要重定位寄存器 支持程序移动、共享

程序的三种链接方式：

链接方式 时机 特点
静态链接 运行前 完整装入模块，不再拆开
装入时动态链接 装入内存时 边装入边链接，便于模块共享和更新
运行时动态链接 执行时才链接 节省内存，加快装入过程

3. 连续分配存储管理方式 ⭐⭐⭐⭐

方式 特点 优点 缺点
单一连续区分配 内存分系统区和用户区，只装一个程序 简单、易管理 不支持多道，空间浪费
固定分区分配 预先划分大小相等或不等分区 支持多道 产生内碎片
动态分区分配 按程序需要动态划分空间 无内碎片 产生外碎片
动态可重定位分区 通过紧凑消除外碎片 充分利用空间 紧凑开销大，需动态重定位

动态分区分配算法

算法 思想 特点
首次适应(FF) 按地址递增链，找第一个满足的空闲区 低地址处多碎片，高地址保留大空闲区
循环首次适应(NF) 从上次分配位置继续搜索 空闲区分布均匀，大空闲区难保留
最佳适应(BF) 按容量递增链，找最接近的 易产生难以利用的小碎片
最坏适应(WF) 按容量递减链，找最大空闲区 不易产生小碎片，大作业难运行
快速适应(QF) 按容量分类，各设链表 查找快，回收复杂，空间换时间
伙伴系统 大小均为2^k，伙伴合并 分配回收较高效
哈希算法 Hash函数快速定位 实现最佳分配策略

紧凑(拼接)： 通过移动程序将分散的小空闲区合并成大空闲区，需要动态重定位支持。

分区保护： 下界/上界寄存器，或 基地址+长度寄存器

4. 对换(Swapping) ⭐⭐

对换定义： 将阻塞进程换出到外存，腾出空间给就绪进程

对换类型 单位 用途
整体对换（进程对换） 以进程为单位 中级调度
部分对换（页/段对换） 以页或段为单位 虚拟存储

换出选择因素： 进程状态（阻塞优先）、优先级（低优先）、驻留时间（长优先）

5. 分页存储管理 ⭐⭐⭐⭐⭐

基本思想： 将进程地址空间分为固定大小的页，内存分为同样大小的物理块(页框)，进程的页离散装入物理块。

地址结构：

1
|  页号 P  |  页内偏移 W  |

若逻辑地址A，页面大小L，则：

  • 页号 $P = \lfloor A/L \rfloor$
  • 页内偏移 $W = A \bmod L$

页表： 每个进程一张页表，实现页号→块号的映射

地址变换机构：

有无快表 访问流程 EAT
无快表 访问页表(1次) → 访问数据(1次) 2t
有快表(TLB) 快表命中(快) → 访问数据(1次)；未命中→ 访问页表→访问数据 $a(t+\lambda)+(1-a)(2t+\lambda+\beta)$

两级/多级页表： 将页表再分页，外层页表管理离散的页表分页，解决大页表连续内存需求

反置页表： 每物理块一个表项（含页号和PID），减少页表空间。按物理块号排序，检索时需遍历。

📐 做题套路：如何推导页号位数和偏移量位数

题目不会直接告诉你“页号几位、偏移几位”，需要自己推导！

第一步：算偏移量位数（由页大小决定）

1
2
页大小 = 2ᵏ B → 偏移量 = k位
例：页大小=2KB=2048B=2¹¹ → 偏移量=11位 ✓

第二步：算总地址位数（由地址写法或题目暗示推断）

1
2
3
逻辑地址用N位十六进制给出 → 总地址 = 4N位
例：逻辑地址是 2825H（4位hex）→ 总地址=16位 ✓
例：逻辑地址是 0x12345（5位hex）→ 总地址=20位 ✓

第三步：页号位数 = 总地址位数 - 偏移量位数

1
例：总地址=16位，偏移=11位 → 页号=16-11=5位 → 最多支持2⁵=32个页 ✓

第四步：物理地址快速计算（十六进制直接替换法）

1
2
3
4
5
6
逻辑地址（hex）= [页号][偏移量]
物理地址（hex）= [块号][偏移量]   ← 只需把页号换成块号，偏移量不变！

例：逻辑地址=2825H，页号=5，查页表得块号=7
    2825H = [00101][00000100101]（二进制）
    把页号5换成块号7 → [00111][00000100101] = 3825H ✅

6. 分段存储管理 ⭐⭐⭐⭐

引入原因： 满足用户编程需求——方便编程、信息共享、信息保护、动态链接、动态增长

基本思想： 按程序逻辑关系分为若干段，每段独立编址，段内连续，段间可不连续

地址结构：

1
|  段号 S  |  段内地址 W  |

段表： 每个进程一张段表，表项含段基址和段长

分页 vs 分段

对比项 分页 分段
划分原则 固定大小（系统行为） 按逻辑功能（用户需求）
地址维度 一维地址空间 二维地址空间（段号+段内地址）
共享保护 按页共享（页不一定对应完整逻辑单位） 按段共享（段是完整逻辑单位）
碎片 页内碎片 段外碎片
越界检查 按页号是否≥页表长度 按段内偏移是否≥段长

7. 段页式存储管理 ⭐⭐⭐

基本思想： 将用户程序分段，每段再分页。兼顾分段（方便用户）和分页（提高内存利用率）的优点。

地址结构：

1
|  段号  |  段内页号  |  页内地址  |

地址变换： 段表（每段一个页表始址+页表长度）→ 页表（页号→块号）→ 物理地址
需要三次访存（段表一次+页表一次+数据一次），可用快表加速。

📝 第四章 典型例题

例4.1 分页地址变换 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

32位逻辑地址，页面大小4KB。逻辑地址为 0x00012345，页表中逻辑页18映射到物理块 0x2A。求页号、页内偏移和物理地址。

解：

4KB=$2^{12}$B，因此低12位为页内偏移。

项目 结果
页号 0x12 = 18
页内偏移 0x345 = 837
物理块号 0x2A
物理地址 $\boxed{\texttt{0x0002A345}}$

物理地址 = 物理块号左移12位，再拼接页内偏移。

例4.2 一级页表空间计算 ⭐⭐⭐⭐ 🎓 408真题同型改编

某系统采用32位虚拟地址、4KB页面、4B页表项。每个进程采用一级页表，完整页表占多少空间？

解：

  • 虚页数：$2^{32}/2^{12}=2^{20}$
  • 页表大小：$2^{20}\times4\text{B}=2^{22}\text{B}$

页表自身需要：

一级页表按整个虚拟地址空间配置，进程实际只使用很少页面时也会造成较大页表开销。

例4.3 两级页表地址拆分 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

32位逻辑地址采用10位页目录号、10位页表号、12位页内偏移。对地址 0xCAFEBABE，求三级字段的十进制值。

解：

1
| 页目录号10位 | 页表号10位 | 页内偏移12位 |

计算结果：

字段 值
页目录号 $\boxed{811}$
页表号 $\boxed{1003}$
页内偏移 $\boxed{0xABE=2750}$

每个二级页表含$2^{10}=1024$个页表项；每个二级页表可映射$1024\times4\text{KB}=4\text{MB}$虚拟空间。

例4.4 TLB有效访问时间 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

TLB查询时间10ns，主存访问时间100ns，TLB命中率90%。页表在内存中，忽略缺页。求有效访问时间。

解：

  • 命中：查TLB一次+访存一次，$10+100=110$ns
  • 未命中：查TLB一次+访问页表一次+访问数据一次，$10+100+100=210$ns

命中率公式必须结合题目给定的硬件访问流程；有的系统允许TLB与Cache并行查询，公式会不同。

例4.5 分段地址变换与保护 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

段表如下：

段号 基址 段长 权限
0 1000 400 R-X
1 4000 1200 RW-
2 800 300 R—

判断下列访问：①写 (1,1000)；②执行 (0,450)；③写 (2,120)。

解：

访问 结论
写(1,1000) 偏移合法且可写，物理地址$4000+1000=\boxed{5000}$
执行(0,450) $450\ge400$，发生越界异常
写(2,120) 偏移合法，但段2只读，发生保护异常

分段访问先做段号/段长检查，再做权限检查，最后才形成物理地址。

例4.6 段页式地址变换 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

页面大小1KB。逻辑地址表示为“段号+段内偏移”。段2长度为5000B，其页表中第3页映射到物理块9。求逻辑地址 (2,3500) 的物理地址。

解：

段内偏移3500小于段长5000，合法。

段页式必须先检查段内偏移是否越界，再把段内偏移拆成页号和页内偏移。

例4.7 动态分区分配算法对比 ⭐⭐⭐⭐⭐ 🎓 408经典模型改编

空闲分区按地址顺序为100、500、200、300、600KB。依次申请212、417、112、426KB。分别判断首次适应FF和最佳适应BF能否满足全部请求。

解：

首次适应FF：

1
2
3
4
212从500中分配→余288
417从600中分配→余183
112从288中分配→余176
426：失败

最佳适应BF：

1
2
3
4
212从300中分配→余88
417从500中分配→余83
112从200中分配→余88
426从600中分配→余174
算法 第4次请求
FF 失败
BF 成功

“总空闲空间足够”不代表一定能分配，动态分区还受外部碎片影响。

例4.8 稀疏地址空间的两级页表开销 ⭐⭐⭐⭐ 🎓 408真题同型改编

32位地址、4KB页面，两级页表按10/10/12划分，每个页目录和页表均恰占1页。某进程只连续使用从虚拟地址0开始的8MB空间，页表结构至少占多少页？

解：

一个二级页表可映射：

映射8MB需2个二级页表，再加1个页目录：

占用空间：

多级页表的优势在于只为实际使用的虚拟地址区间创建下级页表。

例4.9 共享代码页的物理块节省 ⭐⭐⭐⭐ 🎓 408真题同型改编

20个进程运行同一只读程序。每个进程需要3页只读代码和2页私有数据。若代码页可共享，最少需要多少页框？相比完全不共享节省多少页框？

解：

  • 共享代码：仅需3页
  • 私有数据：$20\times2=40$页

若不共享：

节省：

可共享页面通常必须是可重入、只读代码；可写数据页不能直接被所有进程共享。

例4.10 基址—限长寄存器地址保护 ⭐⭐⭐⭐ 🎓 408真题同型改编

某进程的基址寄存器为12000，限长寄存器为4096。分别访问逻辑地址3500和5000，给出结果。

解：

逻辑地址 检查 结果
3500 $3500<4096$ 合法，物理地址$12000+3500=\boxed{15500}$
5000 $5000\ge4096$ 越界异常

限长寄存器保存的是地址空间长度，而不是最大物理地址。

例4.11 页表项位数设计 ⭐⭐⭐⭐ 🎓 408真题同型改编

物理内存1GB，页面大小4KB，页表项固定为32位。页表项中至少需要多少位保存物理块号？其余最多可用于状态与保护信息多少位？

解：

物理块数：

因此块号至少需要$\boxed{18}$位。

剩余位数：

状态位通常包括有效位、修改位、访问位、保护位等；实际体系结构还可能要求对齐或保留位。

📕 第五章 虚拟存储器

1. 虚拟存储器概述 ⭐⭐⭐⭐⭐

定义： 具有请求调入和置换功能，能从逻辑上对内存容量进行扩充的存储器系统。

理论基础——局部性原理：

类型 含义 原因
时间局部性 刚执行的指令/刚访问的数据不久后可能再次被访问 程序中大量循环操作
空间局部性 刚访问单元附近的单元也可能被访问 程序顺序执行

虚拟存储器的三大特征：

特征 含义 与传统方式对比
多次性 进程分多次装入内存（最重要特征） 与传统”一次性”相对
交换性 运行时可在内外存间换入换出 与传统”驻留性”相对
虚拟性 逻辑上扩充内存容量（最重要目标） 核心价值

实现方式： 请求分页系统（最常用）、请求分段系统

2. 请求分页存储管理 ⭐⭐⭐⭐⭐

请求分页 = 基本分页 + 请求调页 + 页面置换

请求页表新增字段：

字段 含义
状态位P 该页是否已调入内存
访问字段A 被访问的频度/最近未访问时间
修改位M 调入后是否被修改过
外存地址 该页在外存上的盘块号

缺页中断特点：

  • 在指令执行期间产生（一般中断在指令执行完后检测）
  • 一条指令可能产生多次缺页中断

物理块分配策略：

组合策略 含义
固定分配局部置换 每个进程固定N块，缺页仅置换自己的页
可变分配全局置换 可用全部空闲块，可抢占其他进程的块
可变分配局部置换 进程块数可动态增减，但只置换自己的页

分配算法： 平均分配、按比例分配（b_i = S_i / ΣS × m）、考虑优先权分配

3. 页面置换算法 ⭐⭐⭐⭐⭐

算法 思想 特点
最佳置换(OPT) 置换未来最长时间不用的页 理论最优，无法实现，作为衡量标准
先进先出(FIFO) 置换驻留最久的页 简单，性能差，可能出现Belady异常
最近最久未用(LRU) 置换最长时间未被访问的页 性能好，需硬件支持（寄存器/栈）
最少使用(LFU) 置换被访问次数最少的页 不能真实反映使用情况
简单Clock(NRU) 循环检查访问位A=0的页置换 LRU近似算法，实现简单
改进型Clock 同时考虑访问位A和修改位M 优先置换(A=0, M=0)，减少写回开销
页面缓冲(PBA) 维护空闲链表和修改链表 显著降低换进换出频率

改进型Clock四类页面（淘汰优先级从高到低）：

  1. A=0, M=0 → 最佳淘汰候选
  2. A=0, M=1
  3. A=1, M=0
  4. A=1, M=1 → 最后淘汰

Belady异常： 为进程分配的物理块增加，缺页次数反而增加的现象（FIFO可能出现）

有效访问时间 EAT（$\lambda$=快表时间, $t$=访存时间, $a$=快表命中率, $f$=缺页率, $\varphi$=缺页处理时间）：

4. “抖动”与工作集 ⭐⭐⭐⭐

抖动(Thrashing)： 进程频繁缺页换进换出，CPU大部分时间用于页面置换而非有效工作，利用率急剧下降趋于0。

产生原因： 多道程序度过高，分配给每个进程的物理块太少

工作集： 某段时间间隔Δ内进程实际要访问的页面集合 w(t, Δ)。
窗口尺寸Δ越大，工作集越大：w(t, Δ) ⊆ w(t, Δ+1)

预防抖动的方法：

  • 局部置换策略（限制抖动影响范围）
  • 工作集算法融入调度（调入新作业前检查是否缺物理块）
  • L=S准则调节多道程序度（L=缺页平均间隔时间, S=平均缺页服务时间，两者相等时CPU和磁盘利用率最大）
  • 暂停某些进程

5. 请求分段存储管理 ⭐⭐⭐

在分段基础上增加请求调段和置换功能，以段为单位换入换出。

请求段表新增字段： 访问字段A、修改位M、存在位P、增补位（段是否动态增长）、外存始址、存取方式

分段保护方式：

  • 越界检查： 段号越界、段内偏移越界
  • 存取控制检查： R / R/W / E 权限
  • 环保护机构： 内环(低编号、高特权)可访问同环或外环；外环请求同环或内环服务

📝 第五章 典型例题

例5.1 FIFO、LRU与OPT缺页比较 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

3个页框，初始为空。页面访问串为：
7,0,1,2,0,3,0,4,2,3,0,3,2。
分别计算FIFO、LRU和OPT的缺页次数。

答案：

算法 缺页次数
FIFO $\boxed{10}$
LRU $\boxed{9}$
OPT $\boxed{7}$

逐步推演：

表中页框内容按固定槽位书写；F表示缺页，H表示命中。

访问页 FIFO页框/结果 LRU页框/结果 OPT页框/结果
7 [7,-,-] F [7,-,-] F [7,-,-] F
0 [7,0,-] F [7,0,-] F [7,0,-] F
1 [7,0,1] F [7,0,1] F [7,0,1] F
2 [2,0,1] F [2,0,1] F [2,0,1] F
0 [2,0,1] H [2,0,1] H [2,0,1] H
3 [2,3,1] F [2,0,3] F [2,0,3] F
0 [2,3,0] F [2,0,3] H [2,0,3] H
4 [4,3,0] F [4,0,3] F [2,4,3] F
2 [4,2,0] F [4,0,2] F [2,4,3] H
3 [4,2,3] F [4,3,2] F [2,4,3] H
0 [0,2,3] F [0,3,2] F [2,0,3] F
3 [0,2,3] H [0,3,2] H [2,0,3] H
2 [0,2,3] H [0,3,2] H [2,0,3] H

为什么三者结果不同？

  • FIFO只看“谁最早进入内存”。页面0在第5次刚被访问过，但到第7次缺页时仍可能因进入时间较早而被换出，所以它不利用近期访问规律。
  • LRU换出过去最长时间未访问的页面。例如访问3时，页1自装入后最久未被使用，因此换出页1；它利用了程序的时间局部性。
  • OPT观察未来访问串，换出未来最晚再用或不再使用的页面。例如访问4时，内存中[2,0,3]，未来2和3很快会访问，而0更晚才访问，因此换出0。

缺页统计可直接由表中的F计数得到：

易错点：命中时FIFO队列顺序不变；LRU则必须更新“最近使用时间”。OPT只能作为理论基准，实际系统无法预知未来访问串。

例5.2 CLOCK页面置换 ⭐⭐⭐⭐ 🎓 408真题同型改编

4个页框当前为 [1,2,3,4]，访问位为 [1,0,1,0]，指针指向页2所在页框。依次访问不在内存的页5、页6，写出置换结果。

解：

  1. 访问页5：指针处页2的访问位为0，直接淘汰页2。
    页框变为 [1,5,3,4]，访问位 [1,1,1,0]，指针移到页3。
  2. 访问页6：页3访问位为1，清0并前移；页4访问位为0，淘汰页4。
    最终页框为：

最终访问位为 [1,1,0,1]，指针指向页1。

例5.3 工作集计算 ⭐⭐⭐⭐ 🎓 408真题同型改编

页面访问序列为：2,3,2,1,5,2,4,5,3,2。在$t=10$时，工作集窗口$\Delta=5$，求工作集。

解：

最近5次访问为：

1
2, 4, 5, 3, 2

去重后：

工作集大小为$\boxed{4}$。

工作集是窗口内访问过的不同页面集合，不是最近$\Delta$个页面组成的序列。

例5.4 含缺页的有效访问时间 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

TLB查询10ns，内存访问100ns，TLB命中率95%；缺页率为$10^{-6}$，一次缺页处理平均8ms。忽略缺页后的重启开销，求近似有效访问时间。

解：

无缺页时：

考虑缺页：

极低的缺页率也可能显著影响性能，因为磁盘缺页服务时间比内存访问高多个数量级。

例5.5 Belady异常 ⭐⭐⭐⭐ 🎓 408经典真题模型

FIFO置换访问串：1,2,3,4,1,2,5,1,2,3,4,5。分别使用3个和4个页框，计算缺页次数。

答案：

页框数 FIFO缺页次数
3 $\boxed{9}$
4 $\boxed{10}$

页框增加后缺页反而增多，出现Belady异常。

逐步推演：

访问页 3个页框 结果 4个页框 结果
1 [1,-,-] F [1,-,-,-] F
2 [1,2,-] F [1,2,-,-] F
3 [1,2,3] F [1,2,3,-] F
4 [4,2,3] F [1,2,3,4] F
1 [4,1,3] F [1,2,3,4] H
2 [4,1,2] F [1,2,3,4] H
5 [5,1,2] F [5,2,3,4] F
1 [5,1,2] H [5,1,3,4] F
2 [5,1,2] H [5,1,2,4] F
3 [5,3,2] F [5,1,2,3] F
4 [5,3,4] F [4,1,2,3] F
5 [5,3,4] H [4,5,2,3] F

异常产生的原因：

FIFO维护的是页面进入内存的先后顺序，而不是页面最近是否被使用。增加页框后，页面的进入和淘汰节奏会发生变化，较大的页框集合并不保证在每一步都包含较小页框集合中的页面。

本题中：

  • 3个页框在访问1、2、5的后半段形成了较多命中；
  • 4个页框虽然前期少缺页，但装入5后，FIFO依次淘汰1、2、3、4，导致后续连续缺页；
  • 因此出现$10>9$的反常结果。

这说明FIFO不满足“栈包含性质”。对具有栈性质的LRU和OPT，增加页框后缺页次数只会减少或不变，不会出现Belady异常。

易错点：Belady异常不是“页框越多通常越差”，而是特定访问串和特定非栈算法下，页框增加反而使缺页次数增加。

例5.6 二维数组访问与空间局部性 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

int A[64][64] 按行存储，每个整数4B，页面大小256B，可供数组使用的页框为2个，初始为空。忽略代码和其他数据。分别计算按行遍历与按列遍历的缺页次数。

1
2
3
4
5
6
7
// 按行
for (i=0;i<64;i++)
    for (j=0;j<64;j++) sum += A[i][j];

// 按列
for (j=0;j<64;j++)
    for (i=0;i<64;i++) sum += A[i][j];

解：

每页可装$256/4=64$个整数，恰好一整行。

访问方式 缺页次数
按行 每行首次访问缺页一次，共$\boxed{64}$次
按列 连续访问64个不同页面，2个页框无法保留，几乎每次都缺页，共$\boxed{4096}$次

这是空间局部性在考研中的高频考法。

例5.7 缺页率控制PFF ⭐⭐⭐⭐ 🎓 408真题同型改编

系统采用缺页率控制，允许区间为5%～10%。测得P1缺页率12%，P2缺页率3%，当前没有空闲页框。应如何调整？

答案：

  • P1的缺页率高于上限，需要增加页框。
  • P2的缺页率低于下限，可回收部分页框。
  • 因无空闲页框，可将P2的一个或若干页框转移给P1。

详细解释：

缺页率控制法设置两个阈值：

1
2
3
缺页率 > 上限：页框偏少，应增加页框
缺页率 < 下限：页框可能富余，可回收部分页框
缺页率位于区间内：暂不调整

代入本题：

进程 实测缺页率 与允许区间比较 判断
P1 12% 高于10% 当前驻留集过小，频繁把仍会使用的页面换出
P2 3% 低于5% 当前页框可能多于维持局部性所需数量

由于系统没有空闲页框，不能直接给P1增加页框。合理操作是从P2逐步回收一个或少量页框转给P1，然后继续观察两个进程的缺页率：

  1. 从P2回收页框；
  2. 将页框分配给P1；
  3. 经过一个统计窗口后重新测量；
  4. 若P1仍高于上限且P2仍低于下限，可继续小幅调整；
  5. 一旦二者进入允许区间，停止转移。

不能一次性大量回收P2的页框，因为P2的工作集也可能随程序阶段变化；回收过多可能使P2从低缺页率突然变成高缺页率。

若所有进程缺页率都高于上限且没有空闲页框，说明系统总页框不足以容纳各进程当前工作集，此时应暂停或换出部分进程，降低多道程序度，否则进程间相互抢页会加剧抖动。

易错点：PFF调节的是进程驻留集大小，不是简单地“高缺页率进程抢低缺页率进程的全部页框”。

例5.8 工作集与抖动判断 ⭐⭐⭐⭐ 🎓 408真题同型改编

3个进程当前工作集大小分别为18、12、9页，系统可分配页框总数为36。判断是否具备发生抖动的条件，并给出处理建议。

解：

工作集总需求：

系统至少短缺$\boxed{3}$个页框，无法同时容纳全部进程的当前工作集，具备发生抖动的条件。

处理建议：

  1. 暂停或换出一个进程，降低多道程序度；
  2. 或增加可用页框；
  3. 不宜仅通过全局置换让进程相互抢占页面，否则会加剧抖动。

📓 第六章 输入输出系统

1. I/O系统概述 ⭐⭐

I/O系统基本功能：

功能 说明
隐藏物理设备细节 用户用统一的read/write命令
设备无关性 用逻辑设备名使用设备
提高CPU和I/O利用率 CPU和设备并行工作
设备控制 轮询、中断、DMA、通道等方式
正确共享 独占设备、共享设备的合理分配
错误处理 暂时性错误（重试）和持久性错误

I/O软件层次结构（自上而下）：

层次 功能
用户层I/O软件 产生I/O请求、格式化数据、Spooling
设备独立性软件 统一接口、设备命名/保护/分配/释放、缓冲
设备驱动程序 设置寄存器、检查状态、执行设备命令
中断处理程序 保护现场、中断处理、恢复现场
硬件 执行I/O操作

2. I/O设备和设备控制器 ⭐⭐

设备控制器功能： 接收CPU命令、数据交换、地址识别、差错检测、数据缓冲

I/O编址方式：

方式 特点
I/O端口独立编址 专用I/O指令(io-store)，需要两类指令
内存映像I/O（统一编址） 统一地址空间，一种store指令即可

I/O通道类型：

通道类型 特点 适用设备
字节多路通道 多个非分配型子通道，时间片轮转 低、中速设备
数组选择通道 一个分配型子通道，独占 高速设备（利用率低）
数组多路通道 多个非分配型子通道，按数组传输 高速设备（兼两者优点）

通道瓶颈解决： 采用多通路系统，增加设备与CPU之间的物理通路

3. 中断机构和中断处理程序 ⭐⭐

概念 含义
中断（外中断） 由CPU外部设备引起
陷入（内中断） CPU/内存内部产生（上溢、非法指令、地址越界等）

多中断源处理方式：

方式 特点
屏蔽中断 处理一个中断时屏蔽所有新中断，按序处理
嵌套中断 高优先级中断可抢占低优先级的处理机

中断处理流程： 测定未响应中断 → 保护CPU环境 → 分析原因转处理程序 → 具体处理 → 恢复现场退出

4. 设备驱动程序 ⭐⭐

驱动程序特点： 与硬件紧密相关、与I/O控制方式相关、部分需用汇编、应允许可重入

处理过程： 抽象→具体要求 → 检查合法性 → 检查设备状态 → 传送参数 → 启动I/O设备 → 自我阻塞等待中断

I/O控制方式（CPU干预程度递减）：

方式 CPU干预程度 适用
轮询方式 CPU不断循环检测状态（忙等） 简单系统
中断方式 每传送一字(符)中断一次 字符设备
DMA方式 一个数据块完成后中断一次 块设备
通道方式 整个I/O任务完成后中断一次 大/中型系统

5. 设备独立性软件 ⭐⭐⭐⭐

设备独立性： 应用程序不限于使用特定物理设备

逻辑设备名→物理设备名转换： 通过逻辑设备表(LUT)实现

主要功能：

  • 设备驱动程序统一接口
  • 缓冲管理（单缓冲/双缓冲/循环缓冲/缓冲池）
  • 差错控制（暂时性→重试；持久性→处理/报告）
  • 独占设备分配与回收
  • 提供独立于设备的逻辑数据块

独占设备分配考虑因素：

因素 内容
设备属性 独占设备（排他性分配）、共享设备（合理安排次序）
分配算法 FCFS、优先级高者优先
安全性 安全分配（请求后阻塞，避免死锁但进展慢）、不安全分配（继续运行，需安全检查）

分配流程： 分配设备(DCT) → 分配控制器(COCT) → 分配通道(CHCT)，三者全成功才算成功

6. 用户层I/O软件——SPOOLing系统 ⭐⭐⭐⭐

假脱机技术(SPOOLing)： 在多道程序下，利用通道和磁盘，在联机下实现脱机输入/输出的功能。

SPOOLing系统组成：

组成部分 位置 作用
输入井/输出井 磁盘 暂存输入/输出数据
输入缓冲/输出缓冲 内存 缓冲I/O设备与井之间的数据
输入进程/输出进程 内存 负责设备与井间的数据交换
井管理程序 内存 负责主机与井间的数据交换

SPOOLing特点：

  1. 提高了I/O速度：对低速设备操作变成对井操作
  2. 将独占设备改造为共享设备：如共享打印机
  3. 实现了虚拟设备功能：用户感觉独占，实际共享

SPOOLing系统是空间换时间的典型应用

7. 缓冲区管理 ⭐⭐⭐

引入缓冲的目的： 缓和CPU与I/O速度不匹配、减少中断频率、解决数据粒度不匹配、提高并行性

缓冲类型 特点 处理时间(块设备)
单缓冲 一个缓冲区 max(C,T)+M
双缓冲 两个缓冲区交替使用 max(C,T)
环形缓冲 多个缓冲区成环，三指针(nextg/nexti/Current) 更好地并行
缓冲池 系统公用，三个队列(emq/inq/outq)，四种工作缓冲区 最通用

T=磁盘→缓冲区时间，M=缓冲区→用户区时间，C=CPU计算时间

缓冲池四种工作方式：

  • 收容输入(hin)：emq→输入数据→inq
  • 提取输入(sin)：inq→提取数据→emq
  • 收容输出(hout)：emq→输出数据→outq
  • 提取输出(sout)：outq→输出数据→emq

8. 磁盘调度算法 ⭐⭐⭐⭐

磁盘访问时间：

s=磁臂启动时间, n=移动磁道数, m=常数(移动速度), r=每秒转数, b=读写字节数, N=每磁道字节数

调度算法比较：

算法 思想 特点
FCFS 按请求先后顺序 公平简单，寻道时间长
SSTF 选离磁头最近的磁道 每次寻道最短，可能饥饿
SCAN（电梯） 磁头来回扫描，沿途处理请求 防止饥饿，寻道性能好
CSCAN 单向循环扫描 等待时间更均衡
N-Step-SCAN 分N长度子队列，FCFS处理子队列，子队列内SCAN 防止磁臂粘着
FSCAN 当前队列+新请求队列双队列 防止磁臂粘着

⚠️ 磁臂粘着：若干进程反复请求同一磁道，磁臂停留不动、垄断设备

📝 第六章 典型例题

例6.1 中断驱动I/O与DMA ⭐⭐⭐⭐ 🎓 408真题同型改编

传输8MB数据，DMA每传完4KB产生一次中断。问DMA共引发多少次完成中断？与按字节由CPU搬运相比，DMA的主要优势是什么？

解：

DMA的主要优势：

  • 数据块在设备与内存之间直接传输；
  • CPU只需设置DMA参数并在块完成时处理中断；
  • 大幅减少CPU逐字节搬运和中断/查询次数。

DMA并非完全不需要CPU，通道初始化、异常处理和传输完成处理仍由CPU负责。

例6.2 双缓冲吞吐量 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

设备产生一块数据需8ms，CPU处理一块需5ms，共处理100块。忽略缓冲切换开销。分别计算无重叠单缓冲顺序处理和双缓冲流水处理的总时间。

解：

顺序处理：

双缓冲：

首次输入8ms；之后输入与处理重叠，稳定周期为$\max(8,5)=8$ms；最后一块再处理5ms。

双缓冲提高吞吐量，但单块延迟不一定等比例下降。

例6.3 磁盘调度综合计算 ⭐⭐⭐⭐⭐ 🎓 408经典真题模型

磁道号0～199，当前磁头在53。请求队列：
98,183,37,122,14,124,65,67。
SCAN和C-SCAN初始均向磁道号增大的方向移动。计算总寻道距离。

答案：

算法 服务顺序（关键点） 总移动磁道数
FCFS 按原顺序 $\boxed{640}$
SSTF 65,67,37,14,98,122,124,183 $\boxed{236}$
SCAN 向上至199，再向下至14 $\boxed{331}$
C-SCAN 向上至199，回0，再向上至37 $\boxed{382}$

详细计算：

① FCFS

按请求到达顺序服务：

1
53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

FCFS最公平、实现最简单，但请求顺序杂乱时磁头可能频繁长距离往返。

② SSTF

每次选择距离当前磁头最近的请求：

1
53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

各段距离：

例如在53处，最近的是65（距离12）；到65后，最近的是67（距离2）。SSTF通常能降低平均寻道距离，但远端请求可能长期得不到服务，存在饥饿风险。

③ SCAN

初始向磁道号增大的方向移动，沿途服务上方请求，走到端点199后反向：

1
2
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199
   → 37 → 14

上行距离可直接计算为$199-53=146$；反向从199走到14为$199-14=185$：

SCAN像电梯一样来回扫描，请求等待时间比SSTF更稳定。

④ C-SCAN

始终只沿磁道号增大的方向提供服务。到199后直接返回0，返回途中不服务，再从0继续向上：

1
2
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199
   → 0 → 14 → 37

C-SCAN使不同磁道位置的等待时间更均匀。本题把199回到0的物理移动距离计入总寻道距离。

易错点：SCAN必须到端点199后才反向；若只到该方向最远请求183就反向，那是LOOK。C-SCAN若只到183并跳到14附近，则属于C-LOOK。

📔 第七章 文件管理

1. 文件和文件系统 ⭐⭐

文件： 由创建者定义、具有文件名的一组相关元素（通常是记录）的集合。

文件系统层次结构（自上而下4层）：

层次 功能
逻辑文件系统 处理文件目录、按名存取、文件保护
基本I/O管理程序 完成逻辑地址→物理地址转换
基本文件系统 向驱动程序发送读写命令
I/O控制层 设备驱动+中断处理

文件分类：

分类标准 类型
按性质和用途 系统文件、用户文件、库文件
按数据形式 源文件、目标文件、可执行文件
按存取保护 只读、读写、只执行
按组织形式 普通文件、目录文件、特殊文件

文件基本操作： 创建/删除/读/写/设置读写位置、打开/关闭

2. 文件的逻辑结构 ⭐⭐

逻辑结构 特点 访问方式
无结构文件（流式文件） 以字节为单位 用读/写指针访问
有结构文件（记录式文件） 以记录为单位 按记录访问

有结构文件按组织方式分：

类型 特点
顺序文件 记录按某种顺序排列（串结构/顺序结构），适合批量存取
索引文件 为变长记录建索引表（关键字+记录地址+长度），提高检索速度
索引顺序文件 分组建索引，每组第一个记录建索引，溢出文件处理增删
直接文件（Hash文件） 由关键字通过Hash函数确定目录表位置，获得物理地址

顺序文件定长记录：Rptr = Rptr + L；变长记录：Rptr = Rptr + L_i + 1

3. 文件目录 ⭐⭐⭐

目录管理基本要求： 按名存取（最基本）、检索速度快、文件共享、允许重名

文件控制块FCB： 描述和控制文件的数据结构，是文件存在的唯一标志

FCB字段类别 内容
基本信息 文件名、物理位置（设备名+盘块号+长度）、文件结构
存取控制信息 文件主/核准用户/一般用户权限
使用信息 建立时间、修改时间、当前使用信息

索引结点(i-node，Unix/Linux)： 将文件名和文件描述信息分离，减少目录检索时的磁盘I/O次数。

对比项 传统FCB目录 i-node目录
目录项内容 文件名+全部FCB信息 文件名+i-node编号
目录项大小 大（64B~256B） 小（约16B）
检索速度 慢（一次读完一个目录项=多扇区） 快（一个磁盘块可存更多目录项）
i-node位置 — 独立存储区

目录结构演变：

结构 特点 缺点
单级目录 整个系统一张目录表 速度慢、不可重名、不便共享
两级目录 MFD主目录+UFD用户目录 允许不同用户重名，检索快
树形目录 多级目录，根目录+各级子目录 现代OS通用方案

目录查询方式： 线性检索法（顺序查找）、Hash方法

绝对路径 vs 相对路径：

  • 绝对路径：从根目录开始，如 /usr/ast/mbox
  • 相对路径：相对于当前工作目录，如 mbox（当前目录为 /usr/ast）

4. 文件共享 ⭐⭐

共享方式 原理 优缺点
基于索引结点 共享文件的多个目录项指向同一个i-node，共享计数count 文件主删除后其他用户无法访问
符号链(LINK) 建立含目标路径名的LINK文件 可跨网络共享，但多次读盘慢

5. 文件保护 ⭐

影响安全性的因素： 人为因素、系统因素、自然因素

存取控制方法：

方法 原理 特点
访问矩阵 按用户身份设置不同权限 需要较多存储
口令 创建时设口令，访问时核对 时空开销小，不够安全
密码 文件加密存储，访问时解密 保密性强，编解码耗时

📝 第七章 典型例题

例7.1 UNIX索引结点与最大文件 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

块大小4KB，块号指针4B。i-node含10个直接指针、1个一级间接指针和1个二级间接指针。
（1）最大文件大小是多少？
（2）访问逻辑块号2000（从0编号），若i-node已在内存，至少需几次磁盘访问？

解：

每个间接块可存：

最大数据块数：

最大文件大小：

逻辑块2000位于二级间接范围，需要读取：

  1. 一级索引块；
  2. 二级索引块；
  3. 数据块。

故至少$\boxed{3}$次磁盘访问。

例7.2 硬链接与符号链接 ⭐⭐⭐⭐ 🎓 408真题同型改编

文件 /a/f 的i-node链接计数初始为1。创建硬链接 /b/h 指向它，又创建符号链接 /c/s，其内容为路径 /a/f。随后删除 /a/f。说明链接计数及两种链接的可用性。

答案：

  1. 创建硬链接后，原文件i-node链接计数由1变为2。
  2. 创建符号链接会新建独立文件及独立i-node，不增加目标文件链接计数。
  3. 删除 /a/f 后，目标i-node链接计数降为1，数据仍存在。
  4. /b/h 仍可正常访问原数据。
  5. /c/s 保存的路径 /a/f 已不存在，因此成为悬空符号链接。

详细解释：

目录项可以理解为“文件名到i-node号的映射”。硬链接与原文件名只是两个不同目录项，但二者指向同一个i-node；符号链接则是一个独立的小文件，其数据内容保存目标路径字符串。

操作阶段 /a/f /b/h /c/s 原文件i-node链接计数
初始 指向原i-node 不存在 不存在 1
建立硬链接 指向原i-node 也指向原i-node 不存在 2
建立符号链接 指向原i-node 指向原i-node 指向独立的符号链接i-node，内容为/a/f 2
删除/a/f 目录项消失 仍指向原i-node 仍保存字符串/a/f 1

删除/a/f实际删除的是目录项，并把原i-node的硬链接计数减1。由于/b/h仍指向该i-node，链接计数不为0，所以原文件的数据块和i-node都不会被回收。

访问两种链接时：

  • 访问/b/h：目录查找直接得到原i-node，因此仍可读取原文件数据；
  • 访问/c/s：系统先读取符号链接内容/a/f，再按这个路径重新查找。由于/a/f目录项已经删除，路径解析失败，所以/c/s成为悬空链接。

只有当原文件的硬链接计数降为0，并且没有进程仍打开该文件时，文件数据才可以被真正回收。

易错点：符号链接本身也有i-node和链接计数，但它的创建不会增加“目标文件”的硬链接计数。

例8.1 位示图空间与定位 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

1TB磁盘，块大小4KB，每块用1位表示空闲状态。
（1）位示图大小是多少？
（2）若盘块从0编号，按32位字组织，盘块123456对应第几个字和字内第几位（均从0编号）？

解：

盘块数：

位示图大小：

定位：

例8.2 FAT表容量计算 ⭐⭐⭐⭐ 🎓 408真题同型改编

32GB分区，簇大小4KB。FAT表项按4B存放，系统保存两份FAT。求单份FAT及两份FAT共占空间。

解：

簇数：

单份FAT：

两份FAT：

表项理论上至少需要23位表示簇号，实际按4B对齐存储。

例8.3 多级索引最大文件 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

块大小4KB，指针4B。i-node有12个直接指针，以及一级、二级、三级间接指针各1个。求最大文件大小。

解：

每个索引块含1024个指针。

最大数据块数：

最大文件大小：

计算最大文件时只统计数据块容量；索引块自身也会占磁盘空间，但不计入文件逻辑长度。

例8.4 成组链接法分配过程 ⭐⭐⭐⭐⭐ 🎓 408真题同型改编

空闲块栈从左到右栈顶递增，当前 n=2，free=[80,120]，故120为栈顶。盘块80中保存下一组：n=3，free=[7,9,15]。连续分配3个盘块，写出分配序列和读盘次数。约定：弹出最后一个栈元素后，从该块读入下一组。

解：

  1. 弹出120，栈余 [80]。
  2. 弹出80，栈空；读取80号盘块中的下一组，装入 [7,9,15]。
  3. 弹出15，栈余 [7,9]。

分配序列：

为补充空闲块栈发生$\boxed{1}$次读盘。

组间连接块既可作为可分配空闲块，也保存下一组块号；分配它之前必须先取出其中的链接信息。

例8.5 RAID 5容量与小写代价 ⭐⭐⭐⭐ 🎓 408真题同型改编

RAID 5由6块4TB磁盘组成。求可用容量、可容忍同时故障的磁盘数；对一个未覆盖整条带的小块写，采用“读—改—写”通常需要多少次磁盘I/O？

解：

可用容量：

容错能力：可容忍$\boxed{1}$块磁盘故障。

小块写的读—改—写：

  1. 读旧数据；
  2. 读旧校验；
  3. 写新数据；
  4. 写新校验。

共$\boxed{4}$次磁盘I/O。

RAID 5提高可用性但不能替代备份；重建期间再次故障会造成阵列数据丢失。

📝 新题库索引与使用建议

本版共保留 46道编号例题，数量与原文一致。题干已全部重写，不逐字照录网络材料；以公开考研408历年常见命题模型为骨架，强化计算、推理、边界条件和易错点。

章节 题量 重点能力
第一章 操作系统引论 2 用户态/内核态、系统调用、多道程序度
第二章 进程与线程 6 状态转换、前趋同步、批量PV、读者写者、线程模型
第三章 调度与死锁 9 SRTF、RR、HRRN、反馈队列、银行家、检测与临界值
第四章 存储器管理 11 分页、分段、段页式、TLB、多级页表、动态分区与保护
第五章 虚拟存储器 8 页面置换、CLOCK、工作集、缺页EAT、局部性与抖动
第六章 I/O系统 3 DMA、缓冲、磁盘调度
第七章 文件管理 2 i-node、多级索引、硬链接与符号链接
第八章 磁盘空间管理 5 位示图、FAT、多级索引、成组链接、RAID
合计 46 —

建议刷题顺序

  1. 先独立完成题干，不看解析。
  2. 计算题必须写出中间状态：就绪队列、页框内容、Work向量、磁头路径等。
  3. PV题先列“资源约束”和“先后约束”，再决定信号量初值。
  4. 做错的题隔24小时重做，只记录错因，不背最终答案。
  5. 第二轮优先练五星题，并尝试修改参数自行出变式。

来源标记说明

  • 🎓 408真题同型改编：依据历年408反复出现的题型模型重新设计数据与问法。
  • 🎓 408经典模型改编：保留经典考法，但重新组织题干、参数和解析。
  • 所有答案均按本文采用的编号、队列入队规则和硬件假设计算；若其他资料的约定不同，应以题目明确条件为准。