📊 考点权重（基于课件结构）整理分析

🗺️ 考点路线图 整理导图

第 1 章 · 操作系统概述（Lect01）

1.1 什么是操作系统？

操作系统是介于应用软件与硬件之间的特殊软件层，提供：

• 方便的抽象：隐藏复杂硬件设备细节
• 受保护的资源访问：管理共享资源的隔离与分配
• 安全与认证：控制谁可以访问什么
• 通信机制：逻辑实体间的通信

1.2 OS 的三个角色

1.3 OS 历史简谱

• Multics → AT&T Unix → BSD Unix → Ultrix, SunOS, NetBSD, FreeBSD
• Mach (微内核) + Unix BSD → NextStep → XNU → macOS / iOS
• MINIX → Linux → Android, Chrome OS, Ubuntu, Fedora, Debian
• CP/M → QDOS → MS-DOS → Windows 3.1 → NT → ... → Windows 10/11

第 2 章 · OS 四大核心概念（Lect02）

2.1 四个基本概念

2.2 Base and Bound（基址-界限保护）

简单的地址翻译机制：

• 物理地址 = 虚拟地址 + Base（基址寄存器）
• 如果虚拟地址 ≥ Bound（界限寄存器）→ 越界异常
• 保护 OS 和进程间隔离，不需要重定位加载器

第 3 章 · 线程与进程（Lect03）

3.1 线程（Thread）

• 定义：OS 提供的并发单元，每个线程代表一个任务
• 动机：处理多任务、网络服务器、并行程序、UI 响应、隐藏 I/O 延迟
• 三状态：RUNNING（运行中）、READY（就绪）、BLOCKED（阻塞等待 I/O）
• 共享状态：内存内容（全局变量、堆）、I/O 状态（文件描述符、网络连接）
• 私有状态：TCB（线程控制块）、CPU 寄存器（含 PC）、执行栈

3.2 并发 vs 并行

3.3 多处理 vs 多道程序

• Multiprocessing：多个 CPU/核
• Multiprogramming：多个作业/进程
• Multithreading：多个线程/进程

3.4 pthreads API

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine)(void*), void *arg);
void pthread_exit(void *value_ptr);
int pthread_join(pthread_t thread, void **value_ptr);

3.5 进程（Process）

• 定义：具有受限权限的执行环境 = 地址空间 + 一个或多个线程
• 拥有文件描述符、网络连接等资源
• 进程间互相保护；OS 保护不受进程侵害
• 在现代 OS 中，内核之外的一切都在进程中运行

3.6 进程管理 API

3.7 fork() 关键特性

• fork() 后父进程和子进程的地址空间（内存）、文件描述符等全部复制
• 但两者独立运行，调度顺序不确定（竞态）
• 不要在 fork() 后直接做复杂操作而不 exec()（多线程进程中尤其危险——其他线程会消失）

3.8 进程 vs 线程

3.9 竞态条件（Race Condition）

第 4 章 · 文件与 I/O（Lect04）

4.1 "Everything is a File" 哲学

Unix/POSIX 中，磁盘文件、设备、网络 Socket、管道等使用统一接口：open()、read()、write()、close()。

4.2 文件系统抽象

• 文件：命名的数据集合（字节序列），含元数据（大小、修改时间、所有者）
• 目录：包含文件和子目录的"文件夹"，层次命名（路径）
• 绝对路径（/home/ff/pkuos）vs 相对路径（./, ../, ~/）

4.3 I/O 层次（自底向上）

1. 磁盘 / Flash / 控制器 / DMA
2. I/O 驱动（命令与数据传输）
3. 文件系统（文件/目录/索引）
4. Open File Description（syscall 层）
5. 文件描述符（低层 I/O）
6. Streams（高层 I/O, FILE*）

4.4 文件描述符（Low-Level I/O）

标准描述符：STDIN_FILENO (0)、STDOUT_FILENO (1)、STDERR_FILENO (2)

4.5 FILE* 流（High-Level I/O）

• FILE* 结构包含：文件描述符 + 用户态缓冲区 + 锁
• fopen/fclose、fread/fwrite、fprintf/fscanf、fseek/ftell
• 三个预定义流：stdin、stdout、stderr
• 缓冲原因：系统调用比函数调用昂贵得多；内核不理解格式化

4.6 fork() 与文件描述符

第 5 章 · IPC、管道与 Socket（Lect05）

5.1 进程间通信（IPC）

进程间天然隔离；通信需要在保护墙上"打洞"。两种方式：

• 文件：持久存储，但昂贵（需写磁盘）
• 内核内存队列：通过系统调用实现的管道 / Socket

5.2 Unix 管道（Pipe）

• int pipe(int fileds[2])：fileds[0] 读端，fileds[1] 写端
• 实现为固定大小队列（有界缓冲区）
• 写满则阻塞（生产者睡眠），读空则阻塞（消费者睡眠）
• 单向、单机、需通过 fork() 继承文件描述符

5.3 Socket（套接字）

• 通信端点，外观类似文件 I/O（有文件描述符）
• 双向（两个队列，每个方向一个）
• 进程可在不同机器上，无需共同祖先
• 同一抽象适用于本地、TCP/IP、UDP/IP

5.4 管道 vs Socket

5.5 Socket 客户端-服务器模式

服务器端：socket() → bind() → listen() → accept() → read/write → close()

客户端：socket() → connect() → write/read → close()

TCP 连接由 5 元组标识：(源IP, 源端口, 目的IP, 目的端口, 协议)

5.6 并发服务器设计模式

第 6 章 · 并发与同步基础（Lect06）

6.1 进程控制块（PCB）

• 内核中每个进程/线程的表示结构
• 包含：状态（running/ready/blocked）、寄存器状态、PID、优先级、执行时间、内存空间等

6.2 线程/进程生命周期

状态转换：new → ready → running → waiting（等待事件）→ ready → ... → terminated

6.3 上下文切换（Context Switch）

6.4 调度循环（Dispatch Loop）

Loop {
    RunThread();
    ChooseNextThread();     // 调度策略
    SaveStateOfCPU(curTCB); // 保存上下文
    LoadStateOfCPU(newTCB); // 恢复上下文
}

6.5 内部事件 vs 外部事件

6.6 同步核心定义

第 7 章 · 锁与信号量（Lect07）

7.1 锁的基本操作

• Lock.acquire() — 等待直到锁空闲，然后标记为忙
• Lock.release() — 标记锁为空闲
• 只有持有锁的线程才能释放锁

7.2 信号量（Semaphore）

7.3 信号量的两种模式

7.4 生产者-消费者（有界缓冲区）

Semaphore fullSlots = 0;
Semaphore emptySlots = bufSize;
Semaphore mutex = 1;

Producer(item) {
    P(&emptySlots);    // 等待空位
    P(&mutex);         // 获取互斥
    Enqueue(item);     // 临界区
    V(&mutex);
    V(&fullSlots);     // 通知消费者
}

Consumer() {
    P(&fullSlots);     // 等待数据
    P(&mutex);         // 获取互斥
    item = Dequeue();  // 临界区
    V(&mutex);
    V(&emptySlots);    // 通知生产者
    return item;
}

第 8 章 · 原子指令与管程（Lect08）

8.1 锁的实现：禁用中断

8.2 原子 Read-Modify-Write 指令

硬件负责在单处理器和多处理器上的正确性。

8.3 基于 test&set 的简单锁（忙等）

int value = 0;
Acquire() { while (test&set(value)); }  // 忙等
Release() { value = 0; }

问题：忙等浪费 CPU；可能导致优先级反转；多处理器上引起缓存乒乓效应。

8.4 管程（Monitor）

8.5 条件变量操作

• Wait(&lock)：原子性地释放锁并睡眠；返回前重新获取锁
• Signal()：唤醒一个等待者（如果有）
• Broadcast()：唤醒所有等待者
• 规则：进行条件变量操作时必须持有锁

8.6 Mesa vs Hoare 管程

8.7 信号量 vs 条件变量

第 9 章 · 读者-写者问题（Lect09）

9.1 问题定义

共享数据库，两类用户：

• 读者（Readers）：只读，不修改。允许多个读者同时访问。
• 写者（Writers）：读写。同一时间只能有一个写者，且不能有读者。

9.2 正确性约束

1. 没有写者时，读者可以访问数据库
2. 没有读者或写者时，写者可以访问数据库
3. 同一时间只有一个线程操作状态变量

9.3 状态变量

两个条件变量：okToRead、okToWrite。所有状态变量由一个锁保护。

9.4 读者代码

Reader() {
    acquire(&lock);
    while ((AW + WW) > 0) {     // 有写者存在 → 等待
        WR++;
        cond_wait(&okToRead, &lock);
        WR--;
    }
    AR++;
    release(&lock);
    AccessDatabase(ReadOnly);    // 实际读操作
    acquire(&lock);
    AR--;
    if (AR == 0 && WW > 0)      // 最后一个读者，唤醒写者
        cond_signal(&okToWrite);
    release(&lock);
}

9.5 写者代码

Writer() {
    acquire(&lock);
    while ((AW + AR) > 0) {     // 有活跃用户 → 等待
        WW++;
        cond_wait(&okToWrite, &lock);
        WW--;
    }
    AW++;
    release(&lock);
    AccessDatabase(ReadWrite);   // 实际写操作
    acquire(&lock);
    AW--;
    if (WW > 0)                 // 优先给写者
        cond_signal(&okToWrite);
    else if (WR > 0)            // 否则唤醒所有读者
        cond_broadcast(&okToRead);
    release(&lock);
}

第 10 章 · 经典调度策略（Lect10）

10.1 CPU Burst 模型

程序在 CPU Burst（使用 CPU）和 I/O Burst（等待 I/O）之间交替。CPU Burst 倾向于小 Burst。每次调度决策是关于下一个 CPU Burst给哪个作业。

10.2 调度目标

10.3 经典调度策略对比

10.4 Round Robin 关键参数

• 时间片 q：q 太大 → 接近 FCFS；q 太小 → 上下文切换开销主导
• n 个进程，最大等待 ≤ (n-1)q
• 典型值：10-100ms

10.5 SRTF 是最优的

第 11 章 · 高级调度（Lect11）

11.1 Lottery Scheduling（彩票调度）

• 给每个作业分配彩票票数；每次时间片随机抽取中奖票
• 平均 CPU 时间与票数成正比
• 近似 SRTF：短作业多给票；每个作业至少 1 票（无饥饿）
• 优点：负载变化时优雅地调整比例

11.2 Multi-Level Feedback Queue (MLFQ)

• 多队列，不同优先级；高优先级 = "前台"任务
• 每队列有独立调度算法（前台 RR，后台 FCFS）
• 量子指数增长（1ms, 2ms, 4ms, ...）
• 调整规则：作业从最高优先级开始；用完时间片 → 降级；主动放弃 CPU（I/O） → 升回
• 结果：近似 SRTF——CPU 密集型作业快速降级，I/O 密集型作业留在顶部

11.3 Linux CFS（完全公平调度器）

• 追踪每个线程的 CPU 时间；选择 CPU 时间最小的线程运行
• 近似"理想"多任务处理器（公平队列）
• O(log N) 使用堆实现
• 目标延迟：每个进程在此周期内获得服务（如 20ms）
• 最小粒度：最小时间片长度（如 1ms）——防止过度上下文切换
• 睡眠线程不推进 CPU 时间 → 醒来时获得提升（自动交互性）

11.4 EDF（最早截止时间优先）

• 实时调度：优先级基于绝对截止时间 D_abs = D_old + P_i
• 总是调度绝对截止时间最近的活动任务
• 可行性测试：Σ(C_i / D_i) ≤ 1

11.5 饥饿 vs 死锁

11.6 优先级反转与优先级捐赠

高优先级任务被低优先级任务阻塞（因为锁）。中等优先级任务饥饿高优先级任务。

解决：优先级捐赠/继承——高优先级线程临时将优先级授予低优先级锁持有者。

著名案例：Mars Pathfinder 因优先级反转导致系统重置，启用优先级捐赠后修复。

11.7 调度策略选择指南

第 12 章 · 死锁（Lect12）

12.1 死锁的定义

线程 A 持有资源 1，等待资源 2；线程 B 持有资源 2，等待资源 1 → 循环等待。

12.2 死锁的四个必要条件

12.3 资源分配图

• 节点：线程 (T) 和资源类型 (R, 含 W_i 个实例)
• 请求边：T_i → R_j（线程请求资源）
• 分配边：R_j → T_i（资源分配给线程）
• 有环不一定死锁（如果有多实例）；环是必要条件不是充分条件

12.4 死锁的四种处理方式

12.5 Banker's 算法

• 提前声明最大资源需求
• 允许线程继续当且仅当：(available - requested) ≥ 任何线程可能需要的最大剩余量
• 如果结果为无死锁，则批准请求；否则拒绝
• 保持系统在安全状态

12.6 死锁检测算法

[Avail] = [FreeResources]
UNFINISHED = 所有节点
do {
    done = true
    For each node in UNFINISHED {
        if ([Request_node] <= [Avail]) {
            remove node from UNFINISHED
            [Avail] = [Avail] + [Alloc_node]
            done = false
        }
    }
} until(done)
// UNFINISHED 中剩余的节点 → 死锁

12.7 哲学家（律师）就餐问题

• 5 根筷子、5 个哲学家，需要 2 根才能吃
• 如果所有人同时拿左边 → 死锁
• 修复：不允许拿最后一根筷子（除非某饥饿哲学家已有另一根）

第 13 章 · 现代系统调度（Lect13）

13.1 ZygOS（SOSP'17）— FCFS 启发

• 问题：数据中心中微秒级 RPC 的尾延迟
• 洞察：单队列模型因瞬态负载不平衡在 SLO 上有更好的吞吐
• 方案：工作窃取（Work-Stealing）在数据平面中实现工作守恒
• 结果：比 Linux 快 1.63×，99 分位延迟降低 3.68×

13.2 Shinjuku（NSDI'19）— RR 启发

• 问题：微秒级抢占调度以实现低尾延迟
• 方案：5μs 一次的抢占、专用调度核、硬件虚拟化支持快速抢占

13.3 Tiresias（NSDI'19）— SJF/SRTF/MLFQ 启发

• 问题：无完整作业信息的 GPU 集群管理器
• 方案：二维基于年龄的调度（2DAS）——按已执行的 GPU 时间优先调度最短作业
• 结果：平均 JCT 比 YARN-CS 提升 5.5×

13.4 Dominant Resource Fairness (DRF)

• 问题：多资源类型的公平共享（用户需求异构）
• 主导资源：用户份额最大的资源
• 主导份额：主导资源被分配的比例
• 对主导份额应用 max-min 公平
• 属性：份额保证 ✓、策略证明 ✓、帕累托效率 ✓、无嫉妒 ✓

13.5 经典与现代映射

互动自测（打分）DeepSeek 生成

优缺点对比总结 课件整理

以下内容均来自课件中的对比讨论，帮助快速记忆各方案/机制的优劣。

🧵 进程 vs 线程

📡 管道 vs Socket

🔒 同步机制对比

🏗️ 锁实现方式对比

🏫 Mesa vs Hoare 管程

⏱️ 调度策略对比

💀 死锁处理方式对比

🖥️ 并发服务器模式对比

⚛️ 信号量 vs 条件变量

📂 高层 I/O (FILE*) vs 低层 I/O (fd)

考前速查表 整理速查

🔑 同步机制对比

🔄 调度策略速查

⚠️ 死锁四大条件与对策

📋 Mesa vs Hoare 管程

📝 fork() vs exec() vs wait()

🧵 线程共享 vs 私有