BrushUP
返回

操作系统复习笔记

计算机科学与技术复习笔记

操作系统复习笔记

第一部分：重点题型与解法

银行家算法

题目 1

PixPin_2026-01-12_14-27-10.png

1. 基础数据准备

A. 计算 Need 矩阵 ($Need = Max - Allocation$)
B. 计算 Available 向量 ($Available = Total - \sum Allocation$)
  1. 已分配总量：
    • $R1 = 3 + 2 + 1 + 4 + \mathbf{3} = 13$
    • $R2 = 2 + 3 + 4 + 2 + \mathbf{2} = 13$
    • $R3 = 1 + 1 + 3 + 2 + \mathbf{1} = 8$
  2. 当前可用 (Available)：
    • $R1: 14 - 13 = \mathbf{1}$
    • $R2: 15 - 13 = \mathbf{2}$
    • $R3: 12 - 8 = \mathbf{4}$
    • 即 Available = (1, 2, 4)

2. 安全性检查（回答第 2 问）

我们要尝试找到一个安全序列。此时 Available = (1, 2, 4)。

步骤进程Work (可用)Need (需求)Allocation (已分配)Work + AllocationFinish
1P1(1, 2, 4)(1, 1, 3)(2, 3, 1)(3, 5, 5)True
2P2(3, 5, 5)(4, 2, 0)(1, 4, 3)资源不足，跳过False
3P4(3, 5, 5)(3, 2, 2)(3, 2, 1)(6, 7, 6)True
4P2(6, 7, 6)(4, 2, 0)(1, 4, 3)(7, 11, 9)True
5P3(7, 11, 9)(3, 1, 2)(4, 2, 2)(11, 13, 11)True
6P0(11, 13, 11)(1, 1, 6)(3, 2, 1)(14, 15, 12)True

结论：

存在安全序列（如 P1 -> P4 -> P2 -> P3 -> P0，序列不唯一）。

因此，系统处于安全状态。

3. 资源请求分配（回答第 3 问）

问题： 若 P4 请求资源 $Request_4 = (1, 2, 0)$，且此时 $P4$ 的分配变为 $(4, 4, 1)$。

根据算法，当 P4 已经变为 $(4, 4, 1)$ 时，我们需要先判断这个状态是否合法，再看请求：

  1. 检查请求是否超过需求：

    • 此时 $Need_4$（基于第二步计算）是 $(3, 2, 2)$。
    • $Request_4 = (1, 2, 0) \le (3, 2, 2)$，满足条件。

  2. 检查系统可用资源是否足够：

    • 此时由于 P4 已经是 $(4, 4, 1)$，我们需重新计算当前的 $Available$。
    • $\sum Allocation = (3+2+1+4+\mathbf{4}, 2+3+4+2+\mathbf{4}, 1+1+3+2+\mathbf{1}) = (14, 15, 8)$
    • $Available = (14-14, 15-15, 12-8) = \mathbf{(0, 0, 4)}$

  3. 判定：

    • $Request_4 = (1, 2, 0)$
    • $Available = (0, 0, 4)$
    • 由于 $1 > 0$ 且 $2 > 0$，即 $Request_4 \not\le Available$。

结论：

不能实施资源分配。 因为系统当前剩余资源（特别是 R1 和 R2）不足以满足 P4 的请求，P4 必须等待。

PV 操作

PixPin_2026-01-14_11-01-31.png

题目 1：吃水果

题目描述：

桌子上有一个能盛下 10 个水果的空盘子。爸爸不停地向盘中放苹果和橘子，儿子不停地从盘中取出橘子吃，女儿不停地从盘中取出苹果吃。规定 3 人不能同时向（从）盘子中放（取）水果。试用信号量机制实现爸爸、儿子和女儿 3 个进程之间的同步。请将信号量值和伪代码补充完整。

标准解法与分析

要解决这个问题，我们需要设置两类信号量：

  1. 互斥信号量：用于保证同一时刻只有一个进程访问盘子（临界资源）。
  2. 同步信号量：用于协调进程间的执行顺序（盘子空位、橘子数量、苹果数量）。
1. 信号量定义
2. 伪代码补充（填空答案）

根据图片中的编号，完整填空如下：

完整逻辑代码展示

semaphore empty = 10; // 盘子剩余空间
semaphore orange = 0; // 橘子数量
semaphore apple = 0;  // 苹果数量
semaphore mutex = 1;  // 互斥访问盘子

Dad() {
    while(1) {
        prepare fruit;
        P(empty);      // 等待盘子有空位
        P(mutex);      // 锁定盘子
        put fruit in plate;
        V(mutex);      // 释放盘子
        if (fruit == orange) 
            V(orange); // 提醒儿子来吃橘子
        else 
            V(apple);  // 提醒女儿来吃苹果
    }
}

Son() {
    while(1) {
        P(orange);     // 等待橘子
        P(mutex);      // 锁定盘子
        take orange;
        V(mutex);      // 释放盘子
        V(empty);      // 释放一个盘子空位
        eat orange;
    }
}

Daughter() {
    while(1) {
        P(apple);      // 等待苹果
        P(mutex);      // 锁定盘子
        take apple;
        V(mutex);      // 释放盘子
        V(empty);      // 释放一个盘子空位
        eat apple;
    }
}

重点提示： 在进程同步中，P(empty/orange/apple) 必须在 P(mutex) 之前，否则可能会导致死锁（例如：爸爸拿到了互斥锁但盘子满了，他会阻塞，而儿女因为拿不到互斥锁无法取水果释放空间）。

题目 2：哲学家进餐

题目描述

有 n(n>=3)名哲学家围坐在一张圆桌边，每名哲学家交替地就餐和思考。在圆桌中心有 m(m>=1)个碗，每两名哲学家之间有一根筷子。每名哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考，为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量 PV 操作描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

1. 信号量定义及初值含义

为了解决此问题，我们需要设置以下信号量：

信号量初值含义
bowl$m$资源信号量：表示圆桌中心可用碗的数量。
chopstick[n][1, 1, ..., 1]互斥信号量数组：chopstick[i] 表示第 $i$ 根筷子是否可用。
max_diners$min(n-1, m)$同步信号量：为了防止死锁，限制同时尝试去拿筷子的哲学家人数。必须小于总人数 $n$ 以打破循环等待条件。

2. 算法设计思路

3. PV 操作描述

设哲学家编号为 $i$（$0$ 到 $n-1$），其左侧筷子编号为 $i$，右侧筷子编号为 $(i+1) \bmod n$。

// 哲学家 i 的进程逻辑
Philosopher_i() {
    while(true) {
        think();                // 思考

        P(max_diners);          // 限制同时进餐的人数，防止死锁
        P(bowl);                // 取一个碗
        
        // 拿起两侧筷子的顺序可以根据策略调整，此处采用限制人数法
        P(chopstick[i]);                 // 拿起左侧筷子
        P(chopstick[(i + 1) % n]);       // 拿起右侧筷子

        eat();                  // 就餐

        V(chopstick[i]);                 // 放下左侧筷子
        V(chopstick[(i + 1) % n]);       // 放下右侧筷子
        V(bowl);                         // 将碗放回原位
        V(max_diners);                   // 释放进餐名额
    }
}

4. 关键点说明

  1. 为什么 max_diners 是 $min(n-1, m)$？

    • 为了防止死锁，同时去拿筷子的人数不能超过 $n-1$。
    • 由于碗只有 $m$ 个，同时能吃饭的人数也不能超过 $m$。
    • 结合两者，限制人数为这两者的最小值，既能保证资源最大化利用，又能绝对避免死锁。

  2. 资源获取顺序：在 P 操作中，先申请碗还是先申请筷子？通常建议先申请最稀缺或最容易导致死锁的资源。在本解法中，通过 max_diners 门限位，已经从逻辑上隔离了环路等待的风险。

题目 3 2022 统考真题

题目描述

某进程有 A、B、C、D、E 和 F 共 6 个操作，分别由两个线程并发执行，其中 T1 执行 A、E 和 F，T2 执行 B、C 和 D。下图表示上述 6 个操作的执行顺序所必须满足的约束：C 在 A 和 B 完成后执行、D 和 E 在 C 完成后执行、F 在 E 完成后执行。请使用信号量机制描述 T1 和 T2 之间的同步关系，并说明所用信号量的作用及其初值。

PixPin_2026-01-12_17-12-21.png

这道题目考查的是操作系统中进程（线程）同步的经典问题。我们需要使用信号量（Semaphore）的 $P$、$V$ 操作来确保操作 A 到 F 按照给定的前驱图顺序执行。

1. 信号量定义及初值

为了实现同步，我们需要为前驱图中每一条跨越线程的“箭头”设置信号量。在这个问题中，线程 T1 负责 {A, E, F}，线程 T2 负责 {B, C, D}。

跨线程的依赖关系如下：

  1. A → C: C 需要等待 A 完成。设置信号量 $S_{ac}$，初值为 0。
  2. C → E: E 需要等待 C 完成。设置信号量 $S_{ce}$，初值为 0。

注意：同一线程内部的顺序（如 B→C, C→D, E→F）可以通过代码的先后顺序自然实现，不需要额外信号量。但在严格的标准解答中，通常为所有依赖关系设置信号量以保证逻辑严密。

信号量含义初值
$S_{ac}$表示 A 操作是否完成，用于 T1 通知 T20
$S_{bc}$表示 B 操作是否完成（T2 内部同步，可选）0
$S_{ce}$表示 C 操作是否完成，用于 T2 通知 T10
$S_{cd}$表示 C 操作是否完成（T2 内部同步，可选）0
$S_{ef}$表示 E 操作是否完成（T1 内部同步，可选）0

2. 线程执行描述（伪代码）

线程 T1 (执行 A, E, F)
T1() {
    // 1. 执行 A
    执行 A 操作;
    V(Sac);       // 信号 A 已完成，通知 C

    // 2. 执行 E
    P(Sce);       // 等待 C 完成
    执行 E 操作;
    
    // 3. 执行 F
    // (由于 E、F 在同线程且顺序执行，此处不需要额外的 P/V)
    执行 F 操作;
}
线程 T2 (执行 B, C, D)
T2() {
    // 1. 执行 B
    执行 B 操作;

    // 2. 执行 C
    P(Sac);       // 等待 A 完成 (B 已在本线程前面完成)
    执行 C 操作;
    V(Sce);       // 信号 C 已完成，通知 E

    // 3. 执行 D
    // (由于 C、D 在同线程且顺序执行，直接执行)
    执行 D 操作;
}

3. 核心逻辑总结

PixPin_2026-01-14_11-15-12.png

题目 4 2020 年统考题

PixPin_2026-01-14_11-07-53.png

【一句话讲清楚 pv 操作，操作系统有救啦！】 https://www.bilibili.com/video/BV1fuUQYBEHL/ （讲的很通透）

内存分配与管理

逻辑地址 VS 物理地址

逻辑地址：是指程序在运行过程中使用的地址，也称为虚拟地址（VirtualAddress）。它是由 CPU 生成的，用于访问内存中的数据。逻辑地址的大小和位数取决于处理器的架构和操作系统的设计，通常是一个定长的二进制数值。在执行指令时，CPU 通过将逻辑地址转化为物理地址来获取数据。

物理地址：是指内存中实际的地址，也称为实地址（RealAddress）。物理地址表示内存模块中每个存储单元（通常是字节）的唯一标识符，因此具有唯一性，且直接与内存相关联。物理地址通常是一个以十六进制表示的数字，它确定了计算机中的实际内存位置。

地址转换

PixPin_2026-01-14_16-35-15.png PixPin_2026-01-14_16-59-53.png PixPin_2026-01-14_17-10-46.png

页面置换算法

  1. 最佳置换算法（OPT）（看将来）：置换那些不再使用或者长时内不再使用的页。
  2. 先进先出置换算法（FIFO）：置换先进入内存的页（淘汰在内存驻留时间最久的页
  3. 最近最久未使用置换算法（LRU）（从过去预测将来）置换过去最近，最长时间未使用的页

缺页次数：物理块空缺，发生置换

题目 1

PixPin_2026-01-14_19-37-01.png QQ_1768391292308.png PixPin_2026-01-14_20-12-47.png

【页面置换算法：先进先出置换算法，最佳置换算法，最近最久未使用置换算法#操作系统#期末周】 https://www.bilibili.com/video/BV1S43teEEfL/

磁盘与文件系统

磁盘调度算法，算法思想：

  1. 先来先服务算法：根据进程的请求顺序进行先后调度（就是题目中给的顺序）
  2. 最短寻道时间优先算法：选择最近的磁道进行访问。
  3. 扫描算法（电梯算法 SCAN，先向外）：既要考虑磁道与磁头的距离又要考虑方向。
  4. 循环扫描算法

解题步骤：

  1. 明确算法思想
  2. 根据算法思想写出访问顺序
  3. 根据访问顺序计算移动距离

PixPin_2026-01-15_00-13-10.png PixPin_2026-01-15_00-15-22.png PixPin_2026-01-15_00-18-16.png

第二部分：系统知识梳理

第一章 引论

操作系统的主要功能

  1. 处理机管理
  2. 存储器管理
  3. 设备管理
  4. 文件管理
  5. 接口管理

操作系统的特征

  1. 并发：两个或多个事件在同一时间间隔内发生。
  2. 共享：系统中的资源可供内存中多个并发执行的进程共同使用。
  3. 虚拟：把一个物理上的实体变为若干个逻辑上的对应物。
  4. 异步：在多道程序环境下，运行走走停停，以不可知的速度向前推进。

操作系统的基本类型

有实时操作系统、批处理操作系统及分时操作系统。

  1. 实时操作系统：优先处理紧急事务，实时性、可靠性。
  2. 批处理操作系统：多道批处理并发执行，提高资源利用率。
  3. 分时操作系统：允许用户直接与计算机进行交互。

第二章 进程的描述与控制

进程的状态转换

graph LR
    Create(创建态) --> Ready(就绪态)
    Ready --> Running(运行态)
    Running --> Terminate(终止态)
    Running -->|时间片到, CPU 被优先级高的抢占| Ready
    Running -->|等待系统资源分配, 等待事件发生| Blocked(阻塞态)
    Blocked -->|事件发生| Ready

进程通信的 3 种方式

共享存储器机制：

[     ]
[进程P]
[共享区] 
[进程Q]
[     ]

消息传递机制：

[消息头] --> 发送进程ID/接收进程ID
[消息体]

管道通信：

进程P --> [管道] --> 进程Q

线程

线程的实现方式：

graph TD
    subgraph 用户级线程
        A[线程] --> B[线程库]
        C[线程] --> B
        D[线程] --> B
        B --> E[进程]
    end
    
    subgraph 内核级线程
        F[用户线程] --> G[内核线程]
        H[用户线程] --> I[内核线程]
        J[用户线程] --> K[内核线程]
        G --> L[进程]
        I --> L
        K --> L
    end

第三章 处理机调度与死锁

进程调度方式

  1. 非抢占方式：进程一直运行完，才执行下一个进程。
  2. 抢占式：有更重要的进程需要处理机时，将处理机分配给重要的进程。

调度算法的指标

调度算法

1. 先来先服务 (FCFS)

(非抢占)

进程到达时间运行时间
P107
P224
P341
P454

调度顺序： 0 [P1] 7 [P2] 11 [P3] 12 [P4] 16

计算：

2. 短作业优先 (SJF)

2.1 非抢占式

进程到达时间运行时间
P107
P224
P341
P454

调度顺序： P1 -> P3 -> P2 -> P4 0 [P1] 7 [P3] 8 [P2] 12 [P4] 16

2.2 抢占式 (SRTF - 最短剩余时间优先)

进程到达时间运行时间
P107
P224
P341
P454

执行过程：

调度顺序： 0 [P1] 2 [P2] 4 [P3] 5 [P2] 7 [P4] 11 [P1] 16

3. 优先级调度

3.1 非抢占式

进程到达时间运行时间优先级
P1071
P2242
P3413
P4542

必须先约定“数字越小优先级越高”还是“数字越大优先级越高，一般题目会给出

情况 A：数字越小优先级越高（最常见约定）

非抢占调度应为：
0-7 P1, 7-11 P2, 11-15 P4, 15-16 P3（与你时间轴一致）

对应指标应是（按这个时间轴算）：

情况 B：数字越大优先级越高

则 7 时刻会先选 P3（优先级 3 最大），整体会变成
P1 -> P3 -> P2 -> P4，指标就会刚好和 SJF(非抢占)那组一样。

4. 高响应比优先 (HRRN)

非抢占式，选响应比最高的进程上机。

进程到达时间运行时间
P107
P224
P341
P454

相应比 = （等待时间+需要服务时间）/ 需要服务时间 = 1 + （等待时间 / 需要服务时间）

0 时刻只有 P1 → 运行 0-7

7 时刻计算响应比（等待=7-到达）

8 时刻（P3 完）

12 时刻只剩 P4 → 运行

调度顺序： P1 -> P3 -> P2 -> P4

死锁

银行家算法

1. 数据结构

2. 安全性算法 (1) 若找到 Finish[i] = FALSE 且 Need[i,j] <= Work[j] (2) Work[j] = Work[j] + Allocation[i,j] Finish[i] = TRUE (3) 所有进程满足 Finish[i] = TRUE，则为安全状态。

示例： Available: 3 3 2

进程Max (A B C)Allocation (A B C)Need (A B C)Available (A B C)
P07 5 30 1 07 4 33 3 2
P13 2 22 0 01 2 2
P29 0 23 0 26 0 0
P32 2 22 1 10 1 1
P44 3 30 0 24 3 1

3. 银行家算法步骤 (1) Request[j] <= Need[i,j] (2) Request[j] <= Available[j] (3) 试分配： Available[j] = Available[j] - Request[j] Allocation[i,j] = Allocation[i,j] + Request[j] Need[i,j] = Need[i,j] - Request[j] (4) 检查是否处于安全状态 (执行安全性算法)。

Example: P1 发出请求向量 Request(1, 0, 2) (1) Request(1,0,2) <= Need(1,2,2) (2) Request(1,0,2) <= Available(3,3,2) (3) 更新 Available(2,3,0), Allocation(3,0,2), Need(0,2,0) (4) 执行安全性算法 -> 处于安全状态，就一定不会发生死锁；不安全状态就可能发生死锁。

死锁的检测

PixPin_2026-01-12_10-27-23.png

找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。（从资源向进程的边减去，还有资源）。 上图未死锁，下图为死锁。

PixPin_2026-01-12_10-27-38.png

第四章 进程同步

进程同步与进程互斥

信号量机制

记录型信号量：

/* 记录型信号量的定义 */
typedef struct {
    int value; // 剩余资源数
    struct process *L; // 等待队列
} semaphore;

void wait(semaphore S) {
    S.value--;
    if (S.value < 0) block(S.L);
} // 可能进入阻塞

void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) wakeup(S.L);
} // 可能唤醒进程

用信号量实现进程互斥、同步

1. 进程互斥 (互斥信号量 mutex，初值为 1) 在进入区 P(mutex) —— 申请资源 在退出区 V(mutex) —— 释放资源

semaphore mutex = 1;
P1() {
    ...
    P(mutex);
    代码段;
    V(mutex);
    ...
}

2. 进程同步 (同步信号量 S，初值为 0) 在“前操作”之后执行 V(S) 在“后操作”之前执行 P(S) 设代码 1 在代码 4 之前执行：

semaphore S = 0;
P1() {            P2() {
    代码1;            代码3;
    代码2;            P(S);
    V(S);             代码4;
}                 }

3. 前趋关系

(图中有向无环图，S1 -> S2/S3, S2->S4/S5, S3->S6, S4->S6, S5->S6)

PixPin_2026-01-12_10-33-00.png

P1(){ ... S1; V(a); V(b); }
P2(){ P(a); S2; V(c); V(d); }
P3(){ P(b); S3; V(g); }
P4(){ P(c); S4; V(e); }
P5(){ P(d); S5; V(f); }
P6(){ P(e); P(f); P(g); S6; }

第五章 存储器管理

连续分配存储管理方式

  1. 单一连续分配：

PixPin_2026-01-12_10-34-29.png

  1. 固定分区分配：

PixPin_2026-01-12_10-34-42.png

  1. 动态分区分配：

PixPin_2026-01-12_10-35-40.png

PixPin_2026-01-12_10-35-52.png

  1. 首次适应算法：找到第一个能满足大小的。
  2. 最佳适应算法：优先使用更小的空闲区。
  3. 最坏适应算法：优先使用更大的空闲区。
  4. 邻近适应算法：从上次查找结束位置开始查找第一个空闲分区。

分页存储管理

计算：

地址变换机构：

Eg: 某作业的逻辑地址空间为 4 页(每页 2048 字节)。页面映像表如右图(0->2, 1->4, 2->6, 3->8)。求出逻辑地址 4865 对应的物理地址。

第六章 虚拟存储器 (图: image_695867.jpg, image_695886.jpg)

页面置换算法

1. 最佳置换算法 (OPT)

访问页面70120304…
内存 177722222
内存 20000444
内存 3111333
是否缺页√√√√√√

2. 先进先出置换算法 (FIFO) (图: image_695886.jpg)

3. 最近最久未使用置换算法 (LRU)

第七章 输入/输出系统 (图: image_695886.jpg)

磁盘调度算法

1. 先来先服务算法 (FCFS)

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

2. 最短寻找时间优先 (SSTF)

初始为 100。访问 55, 58, 39, 18, 90, 160, 150, 38, 184。

3. 扫描算法 (SCAN)

只有磁头移动到最外/内侧磁道的时候才能往内/外移动，移动到最内侧磁道的时候才能往外移动。(也叫电梯算法) 假设磁道为 0~200。访问同上。假设当前朝磁道号增加方向移动 (向外)。

4. 循环扫描算法 (C-SCAN)

规定只有磁头朝某个方向移动才能处理访问请求。 假设磁道为 0~200。访问同上。

3478658ebc694b9ca6e8993cc2a7aae41808719338 (1) image.png Uploading file...zi0tj image.png image.png image.png

第三部分：详细图解

计算机科学与技术复习笔记
分享本文到：
Share this post on X Share this post via Telegram Share this post via email
上一篇
操作系统基础知识总结
下一篇
【中学信息技术教学论】名词解释整合