Modern Operating Systems 第五版学习:操作系统第一章

计算机由很多复杂的硬件组成——处理器、内存、硬盘、键盘、显示器……如果每个程序员都要直接和这些硬件打交道，编程会极其困难。操作系统（Operating System，OS）就是夹在硬件和用户程序之间的一层软件，它的作用是：1.2 内核模式 vs 用户模式计算机通常有两种运行模式：模式英文权限运行的软件内核模式Kernel Mode最高，可执行任何指令操作系统核心用户模式User Mode受限，禁

虾球xz

120人浏览 · 2026-05-07 19:07:18

虾球xz · 2026-05-07 19:07:18 发布

教材：Modern Operating Systems (Tanenbaum)
本笔记覆盖第一章全部内容，力求通俗易懂，含图示、代码示例与公式说明。

1. 什么是操作系统

1.1 基本概念

计算机由很多复杂的硬件组成——处理器、内存、硬盘、键盘、显示器……如果每个程序员都要直接和这些硬件打交道，编程会极其困难。
操作系统（Operating System，OS） 就是夹在硬件和用户程序之间的一层软件，它的作用是：

为应用程序提供简洁、统一的接口（屏蔽硬件复杂性）
管理和分配计算机的各种资源（CPU、内存、磁盘等）
用一句话概括：操作系统把难看的硬件变成漂亮的抽象。

                  +------------------+
                  |   用户应用程序    |  (浏览器、邮件、音乐播放器...)
                  +------------------+
                  |    操作系统      |  ← 我们研究的对象
                  +------------------+
                  |      硬件        |  (CPU、内存、磁盘...)
                  +------------------+

1.2 内核模式 vs 用户模式

计算机通常有两种运行模式：

模式	英文	权限	运行的软件
内核模式	Kernel Mode	最高，可执行任何指令	操作系统核心
用户模式	User Mode	受限，禁止I/O等特权指令	普通应用程序

为什么要区分两种模式？
防止应用程序误操作或恶意操作硬件（比如直接读写其他程序的内存）。
用户程序如何请求操作系统服务？
通过 系统调用（System Call），它会触发一次特殊的"陷阱"（trap），切换到内核模式，执行完毕后再切回用户模式。

/* 一个简单的系统调用示例（Linux x86-64 汇编风格，用 C 内嵌汇编演示） */
#include <stdio.h>
#include <unistd.h>
int main(void) {
    /* write() 就是一个系统调用
     * 参数：文件描述符1(标准输出), 字符串, 长度
     * 内部会执行 syscall 指令，切换到内核模式
     * 内核完成写操作后，切回用户模式并返回 */
    write(1, "Hello, OS!\n", 11);
    return 0;
}

https://godbolt.org/z/nPTjc767Y

2. 操作系统的两大功能

2.1 功能一：提供抽象（自顶向下视角）

硬件接口极其复杂。例如，一块SATA硬盘的编程手册超过 450页！没有人愿意直接操作它。
操作系统通过 抽象层 解决这个问题：

硬件层面（丑陋）            操作系统抽象（漂亮）
--------------------        --------------------
磁盘扇区、磁头、柱面  →    文件（File）
内存地址、TLB、页表   →    进程地址空间
网卡寄存器、DMA       →    套接字（Socket）

文件就是最经典的抽象：你只需要 open()、read()、write()、close()，完全不用关心数据究竟存在哪个磁道第几个扇区。

2.2 功能二：资源管理（自底向上视角）

当多个程序同时运行时，谁来决定谁用CPU？谁用内存？操作系统就是这个"仲裁者"。
资源复用有两种方式：

时分复用（Time Multiplexing）

同一资源，不同程序轮流使用。

时间轴：
|--进程A--|--进程B--|--进程C--|--进程A--|--进程B--|-->
         ↑        ↑        ↑
       切换     切换     切换

典型例子：CPU 调度（每个进程每次只用一小段时间）、打印机队列。

空分复用（Space Multiplexing）

同一资源，不同程序各占一部分。

内存布局示例：
地址高   +-----------+
         |  进程 C   |
         +-----------+
         |  进程 B   |
         +-----------+
         |  进程 A   |
地址低   +-----------+
         | 操作系统  |
         +-----------+

典型例子：内存分区、磁盘分区。

3. 操作系统的发展历史

3.1 第一代（1945–1955）：真空管

没有操作系统
程序员直接用插线板（plugboard）连接电路编程
同一批人设计、建造、编程、操作、维护机器

工作流程：
程序员在排班表上登记时间
→ 来到机房，把插线板插入计算机
→ 希望20000个真空管在运算过程中不会烧坏
→ 完成后取走结果

3.2 第二代（1955–1965）：晶体管与批处理系统

晶体管使计算机变得可靠，出现了专业分工：设计者、构建者、操作员、程序员各司其职。
批处理系统（Batch System） 的工作流程如下：

程序员写程序（FORTRAN/汇编）
→ 打成卡片
→ 交给操作员
→ 操作员在 IBM 1401 上把一批作业读入磁带
→ 把磁带搬到 IBM 7094 运行
→ 输出写到另一盘磁带
→ 搬回 IBM 1401 打印输出
→ 程序员取走结果

典型作业卡片格式（FMS 系统）：

$JOB, 10, 7710802, ADA LOVELACE   ← 最大运行时间10分钟，账号，姓名
$FORTRAN                           ← 加载FORTRAN编译器
（FORTRAN源程序卡片）
$LOAD                              ← 加载编译好的程序
$RUN                               ← 运行
（数据卡片）
$END                               ← 结束

3.3 第三代（1965–1980）：集成电路与多道程序设计

IBM System/360 的贡献

IBM 推出 System/360，试图用一个系列的机器满足所有客户，但导致操作系统 OS/360 极其庞大，有数百万行汇编代码，Bug 数不胜数。
一个有趣的类比来理解 OS 代码量：
$\text{代码量} = 50,000,000 \text{ 行}$
$\text{每本书页数} = 1,000 \text{ 页，每页 } 50 \text{ 行}$
$\text{需要书籍数} = \frac{50,000,000}{1,000 \times 50} = 1,000 \text{ 本}$
$\text{每个书架放 20 本，共需书架} = \frac{1,000}{20 \times 7} \approx 7 \text{ 个书柜}$
连微软自己的程序员也没人完全理解 Windows 的全部代码！

多道程序设计（Multiprogramming）

问题：程序等待I/O时，CPU闲置，浪费资源（商业场景中I/O等待可占90%时间）。
解决方案：把多个作业同时放在内存里，一个等I/O时，另一个用CPU。

时间线（无多道程序设计）：
进程A: [运行][等I/O...........][运行][等I/O....]
CPU:   [忙  ][   空 闲        ][忙  ][  空闲  ]
时间线（多道程序设计）：
进程A: [运行][等I/O...........][运行]
进程B:       [运行][等I/O.....][运行]
进程C:             [运行][等I/O...  ]
CPU:   [忙  ][忙  ][忙  ][忙  ][忙  ]   ← CPU 几乎不闲置

假脱机（Spooling）

Spooling = Simultaneous Peripheral Operation On Line
将输入/输出数据先缓存到磁盘，避免设备成为瓶颈。

分时系统（Time-Sharing）

多道程序的变种，每个用户有一个在线终端，CPU轮流服务。
代表作：MIT 的 CTSS（Compatible Time Sharing System）。

MULTICS 与 UNIX 的诞生

MULTICS（MULTiplexed Information and Computing Service）：MIT、Bell Labs、GE 联合开发，目标宏大但商业上不成功。
Ken Thompson（Bell Labs）在一台无人用的 PDP-7 上写出了简化版本，后来发展为 UNIX。
Linus Torvalds 受 MINIX 启发，写出了 Linux（最初运行在 MINIX 上）。

3.4 第四代（1980–至今）：个人计算机

关键事件时间线：

1974  Intel 8080 → Gary Kildall 开发 CP/M
1981  IBM PC 发布，MS-DOS 成为主力操作系统
      （Bill Gates 以 ~$75,000 购入 DOS 后授权给 IBM）
1984  Apple Macintosh → 图形界面普及
1985  Windows 1.0（运行在 DOS 上的图形外壳）
1995  Windows 95（独立操作系统）
1993  Windows NT（32位，David Cutler 主导）
2001  Windows XP
2007  iPhone → iOS
2008  Android（基于 Linux）
2021  Windows 11

图形界面（GUI）的来历：
Doug Engelbart（斯坦福）发明了鼠标和 GUI → Xerox PARC 实现 → Steve Jobs 参观后将其用于 Macintosh。Xerox 错失商机，被称为"史上最大战略失误之一"。

3.5 第五代（1990–至今）：移动设备

智能手机操作系统演变：

Symbian（Nokia主导）
→ BlackBerry OS（2002，商务市场）
→ iOS（2007，iPhone）
→ Android（2008，Google，基于Linux，开源）
→ Android 成为全球主导（市场份额第一）

4. 计算机硬件基础

4.1 处理器（CPU）

CPU 的基本工作循环（取指-译码-执行）：

/* CPU 工作循环的伪代码（C语言描述）*/
#include <stdio.h>
/* 假设指令类型 */
typedef unsigned int Instruction;
typedef unsigned int Address;
/* 模拟 CPU 执行循环 */
void cpu_execute_loop(Address start_address) {
    Address program_counter = start_address; /* 程序计数器，指向下一条指令 */
    Instruction instruction;
    while (1) {
        /* 1. 取指（Fetch）：从内存中读取指令 */
        instruction = memory_read(program_counter);
        /* 2. 译码（Decode）：分析指令类型和操作数 */
        DecodedInstr decoded = decode(instruction);
        /* 3. 执行（Execute）：执行指令 */
        execute(decoded);
        /* 4. 更新程序计数器（PC），指向下一条指令 */
        program_counter += instruction_length(decoded);
        /* 某些指令（如跳转）会直接修改 PC */
    }
}

CPU 中的重要寄存器

寄存器	作用
程序计数器（PC）	存储下一条指令的内存地址
栈指针（SP）	指向当前栈顶
程序状态字（PSW）	保存条件码、CPU优先级、当前模式（内核/用户）等
通用寄存器	存放变量和临时结果

流水线（Pipeline）

现代CPU不是一条一条顺序执行指令，而是同时处理多条：

无流水线（低效）：
时间:  1  2  3  4  5  6  7  8  9
指令1: F  D  E
指令2:          F  D  E
指令3:                   F  D  E
三级流水线（高效）：
时间:  1  2  3  4  5  6  7
指令1: F  D  E
指令2:    F  D  E
指令3:       F  D  E
指令4:          F  D  E
F=取指, D=译码, E=执行

流水线大幅提升了CPU吞吐量，但也给操作系统带来了复杂性（如条件分支预测失败时的处理）。

超标量（Superscalar）CPU

多个执行单元并行工作，指令可能乱序执行：

取指单元 → 译码单元 → 保持缓冲区 → 整数执行单元
                                  → 浮点执行单元
                                  → 逻辑执行单元

多核与多线程

超线程（Hyperthreading）：一个物理核心模拟两个逻辑CPU，在纳秒级别切换线程状态。
多核（Multicore）：一块芯片上有多个完整的CPU核心（现代处理器可达50核以上）。
操作系统的视角：一个4核、每核2线程的CPU，操作系统看到的是 8个CPU。
$\text{逻辑CPU数} = \text{物理核心数} \times \text{每核线程数}$
例：Intel Core i9 (8核16线程) $\Rightarrow$ 操作系统看到16个逻辑CPU。

4.2 内存层次结构

内存设计的矛盾：越快越贵越小。解决方案是分层：

速度快 ↑    寄存器      < 1 ns     < 1 KB     （CPU内部）
容量小 ↑    L1 缓存     1-8 ns     ~32 KB×2   （CPU内部）
           L2 缓存     10-50 ns   4-8 MB     （CPU上/旁）
           主内存(RAM)  ~100 ns    16-64 GB   
容量大 ↓    SSD         ~100 us    几TB       
速度慢 ↓    机械硬盘     ~10 ms     几TB

缓存工作原理

/* 缓存命中/未命中的逻辑（伪代码，C风格）*/
#include <stdint.h>
#include <stdbool.h>
#define CACHE_LINE_SIZE 64     /* 缓存行大小：64字节 */
#define CACHE_LINES     4096   /* 缓存行数量 */
/* 检查地址是否在缓存中 */
bool cache_lookup(uint32_t address, uint8_t *data_out) {
    /* 用地址的第6~17位作为缓存索引 */
    uint32_t cache_index = (address >> 6) & (CACHE_LINES - 1);
    uint32_t byte_offset = address & (CACHE_LINE_SIZE - 1);
    if (cache[cache_index].valid &&
        cache[cache_index].tag == (address >> 18)) {
        /* 缓存命中（Cache Hit）：直接从缓存读取，几个时钟周期 */
        *data_out = cache[cache_index].data[byte_offset];
        return true;  /* 命中 */
    }
    /* 缓存未命中（Cache Miss）：需要访问主内存，几十~几百个时钟周期 */
    return false;
}

缓存对性能的影响很大。假设：

缓存命中率为 $h$
缓存访问时间为 $t_c = 5\text{ ns}$
主内存访问时间为 $t_m = 100\text{ ns}$
则平均内存访问时间为：
$T_{avg} = h \cdot t_c + (1 - h) \cdot t_m$
例：命中率 $h = 0.95$ ：
$T_{avg} = 0.95 \times 5 + 0.05 \times 100 = 4.75 + 5 = 9.75 \text{ ns}$
相比无缓存的 $100\text{ ns}$ ，性能提升约 10倍。

虚拟内存（Virtual Memory）

允许程序使用比物理内存更大的地址空间，通过 MMU（内存管理单元） 在运行时将虚拟地址映射为物理地址。

程序看到的地址（虚拟地址）
       |
       v
   [ MMU ]  ← CPU内部的硬件单元
       |
       v
实际物理地址（RAM中的位置）
       |
    如果不在RAM中，则触发缺页中断，从磁盘/SSD加载

4.3 非易失存储

类型	特点	用途
机械硬盘（HDD）	便宜、大容量，但慢（~10ms随机访问）	大量数据存储
固态硬盘（SSD）	快（~100μs），无机械运动，价格适中	系统盘、常用数据
持久内存（如Intel Optane）	接近RAM速度（~ns级），掉电不丢失	高性能数据库

磁盘结构（HDD）：

磁盘物理结构（俯视）：
    同心圆轨道（Track）
    ↓
  ====外圆柱面
  ====
  ====
  ====  ← 磁头臂可在此移动（寻道）
  ====内圆柱面
每个Track分成若干Sector（扇区，通常512字节）
所有盘片在同一臂位置上的Track集合 = Cylinder（柱面）

磁盘访问时间计算：
$T_{disk} = T_{seek} + T_{rotation} + T_{transfer}$
$T_{seek} \approx 5\text{~}10\text{ ms（寻道时间）}$
$T_{rotation} \approx \frac{0.5}{RPM/60} \text{（平均旋转等待，转一圈时间的一半）}$
例：7200 RPM硬盘的旋转延迟：
$T_{rotation} = \frac{0.5}{7200/60} = \frac{0.5}{120} \approx 4.2\text{ ms}$

4.4 I/O 设备与中断

每个I/O设备由两部分组成：

控制器（Controller）：芯片，接受OS命令
设备本体：实际的物理设备
设备驱动程序（Device Driver）：操作系统和控制器之间的软件接口，由厂商提供。

I/O 的三种方式

方式一：忙等待（Busy Waiting / Polling）

/* 忙等待方式（效率低，CPU一直在循环） */
void busy_wait_io(void) {
    start_device_operation(); /* 启动设备 */
    /* CPU 不停轮询设备状态寄存器，等待完成 */
    while (device_status_register() != DONE) {
        /* 什么都不做，空转 */
    }
    read_data_from_device(); /* 读取结果 */
}

方式二：中断驱动（Interrupt-Driven）

/* 中断驱动方式（推荐）*/
/* 主程序：启动设备后去做其他事 */
void start_io_with_interrupt(void) {
    start_device_operation(); /* 启动设备，让它完成后发中断 */
    do_other_work();          /* CPU 去执行其他进程，不空转 */
}
/* 中断处理程序（设备完成时自动被调用）*/
void interrupt_handler(void) {
    /* 1. 保存当前被打断程序的寄存器状态（CPU程序计数器、PSW等） */
    save_context();
    /* 2. 读取中断向量表，找到对应设备的处理函数 */
    int device_id = read_interrupt_vector();
    /* 3. 处理设备完成事件（读取数据、更新状态等）*/
    handle_device_completion(device_id);
    /* 4. 恢复被打断程序的寄存器，继续执行 */
    restore_context();
}

中断处理流程图：

设备完成I/O
    |
    v
控制器 → 发信号给中断控制器芯片
    |
    v
中断控制器 → 拉高CPU的中断引脚
    |
    v
CPU 完成当前指令后响应中断
    |
    v
把 PC 和 PSW 压入栈
    |
    v
查中断向量表，找到对应中断处理程序地址
    |
    v
跳转到中断处理程序执行
    |
    v
处理完成，恢复 PC 和 PSW，返回被打断的程序

方式三：DMA（直接内存访问）

不用DMA（CPU全程参与数据搬运）：
磁盘 → [CPU搬运每个字节] → 内存
       CPU 完全被占用！
用DMA（CPU只需发出命令）：
CPU 告诉 DMA 芯片：
  "把磁盘地址X的N个字节搬到内存地址Y"
                  ↓
DMA 芯片自主完成数据传输（CPU可以去做其他事）
                  ↓
DMA 完成后，向 CPU 发中断
                  ↓
CPU 收到中断，知道数据已经在内存里了

4.5 总线结构

现代PC的总线结构（简化图）：

+--------+    DDR4     +--------+
|  CPU   |<----------->|  RAM   |
| Cores  |             |  内存  |
| Cache  |             +--------+
+--------+
    |
   PCIe            PCIe = 高速串行总线
    |
+---+---+          速度对比：
| 显卡  |          PCIe 4.0 x16 ≈ 256 Gbps
+-------+
    |
   DMI（平台控制器集线器）
    |
+---+-----+--------+--------+
|         |        |        |
SATA      USB      以太网   PCIe插槽
(硬盘)  (键鼠等)  (网卡)   (扩展卡)

USB（通用串行总线）演进

版本	速度
USB 1.0	12 Mbps
USB 2.0	480 Mbps
USB 3.0	5 Gbps
USB 3.2	20 Gbps
USB 4	40 Gbps

4.6 计算机启动过程

旧式 BIOS 启动流程

按下电源按钮
    |
    v
主板等待电源稳定
    |
    v
CPU 从 Flash 中固定地址（Reset Vector）执行 BIOS 代码
    |
    v
BIOS 检测并初始化硬件（RAM、芯片组、中断控制器）
    |
    v
扫描 PCI/PCIe 总线，初始化设备
    |
    v
从 CMOS 中读取启动设备顺序（U盘？硬盘？）
    |
    v
读取启动设备第一个扇区（MBR，主引导记录，512字节）
    |
    v
MBR 中的程序检查分区表，找到活动分区
    |
    v
加载该分区的次级引导程序（Bootloader，如 GRUB）
    |
    v
Bootloader 加载操作系统内核
    |
    v
操作系统查询 BIOS 获得硬件信息，加载驱动程序
    |
    v
初始化内部表，创建后台进程，显示登录界面

新式 UEFI 启动

UEFI（Unified Extensible Firmware Interface）改进了旧式BIOS：

对比项	旧式 BIOS	UEFI
分区表	MBR（最大2TB）	GPT（最大8 ZiB = $\times 2^{70}$ 字节）
文件系统	不支持	支持 FAT-12/16/32（ESP分区）
安全启动	无	支持 Secure Boot
启动速度	慢	快
架构依赖	强（x86）	弱（多平台）

$\text{ ZiB} = 2^{70} \text{ 字节} \approx 1.18 \times 10^{21} \text{ 字节}$

5. 操作系统的种类

各类操作系统特点对比

类型	典型系统	关键特点
大型机	Z/OS	高I/O吞吐量，批处理+事务+分时
服务器	Linux, FreeBSD	多用户，网络服务，高稳定性
个人电脑	Windows 11, macOS	图形界面，单用户友好
智能手机	Android, iOS	触控，低功耗，传感器支持
嵌入式/IoT	RIOT, TinyOS	超小内存（可低至10KB），实时性
硬实时	VxWorks, QNX	严格时间保证，不能错过截止期
软实时	Android（部分）	偶尔错过截止期可接受
智能卡	Java Card	极度资源受限，部分用JVM

实时系统详解

硬实时（Hard Real-Time）：必须在截止时间前完成，否则系统失败。
例：汽车装配线上的焊接机器人，飞行控制系统。
软实时（Soft Real-Time）：偶尔错过截止时间可以接受。
例：音频/视频播放（偶尔卡顿），智能手机界面响应。

总结：核心概念速查

概念	简单理解
操作系统	硬件和应用之间的管理软件
内核模式	操作系统运行的特权模式，可访问所有硬件
用户模式	应用程序运行的受限模式
系统调用	用户程序请求OS服务的机制（触发模式切换）
抽象	OS将复杂硬件封装成简单接口（如文件）
多道程序设计	内存中同时有多个程序，CPU轮流服务
分时系统	多道程序 + 每个用户有终端，快速切换
时分复用	资源（如CPU）轮流给不同程序用
空分复用	资源（如内存）分区给不同程序用
缓存	把常用数据放在更快的存储层
虚拟内存	用磁盘模拟更大内存，MMU做地址转换
中断	设备完成后主动通知CPU的机制
DMA	设备与内存之间直接传数据，不占用CPU
BIOS/UEFI	开机时初始化硬件、引导OS的固件
批处理	收集一批作业统一运行，无交互
假脱机(Spooling)	输入/输出数据先缓存到磁盘
流水线	CPU同时处理多条指令的不同阶段
超标量	多个执行单元并行，指令可乱序执行

操作系统第一章笔记（下）

覆盖 1.5 操作系统概念 / 1.6 系统调用 / 1.7 操作系统结构 / 1.8 C语言世界

1. 操作系统的核心概念

1.1 进程（Process）

进程是什么？
进程 = 正在运行的程序。一个程序文件（.exe 或可执行文件）只是存在磁盘上的死代码；一旦被加载并运行，它就成了一个"进程"——有了生命。
进程包含哪些内容？

进程 = 地址空间（内存）+ 进程表项（状态信息）
地址空间里有：
  +-----------+  高地址
  |   栈 Stack |  ← 函数调用、局部变量
  |     ↓     |
  |   (空隙)  |
  |     ↑     |
  |  数据 Data |  ← 全局变量、堆
  |  代码 Text |  ← 可执行指令
  +-----------+  低地址（0x0000）
进程表项里有：
  程序计数器（PC）、寄存器、打开的文件列表、
  信号处理设置、进程ID（PID）、父进程ID...

进程树（Process Tree）
进程可以创建子进程，形成树形结构：

进程挂起与恢复
当操作系统暂停一个进程时，必须完整保存其所有状态，以便后续精确恢复。这个保存的状态存在进程表（process table） 里，每个进程占一个表项（一个结构体）。
信号（Signal）
信号是操作系统通知进程的机制，类似于"软件中断"。
例如：定时器到期 → OS向进程发送 SIGALRM → 进程暂停当前工作 → 执行信号处理函数 → 恢复原来的工作。
UID 与 GID

每个用户有一个 UID（User IDentification），每个进程携带启动它的用户的 UID。
用户可以属于组，每个组有 GID（Group IDentification）。
特殊用户 root（UNIX）/ Administrator（Windows） 拥有超级权限，可绕过大多数保护规则。

1.2 地址空间（Address Space）

问题：多个程序同时在内存中运行时，如何防止它们互相破坏？
解决方案：给每个进程一个独立的地址空间，从地址 0 开始，到某个最大值。进程只能访问自己的地址空间。
虚拟内存：程序的地址空间可以比物理内存更大。操作系统把暂时不用的部分放到磁盘/SSD上，需要时再换入内存。这样，一个需要 $4\text{ GB}$ 内存的程序也能在只有 $1\text{ GB}$ 物理内存的机器上运行（虽然会慢）。
地址位数决定可寻址空间大小：

32位地址：最大寻址 $2^{32} = 4,294,967,296$ 字节 $4\text{ GB}$
64位地址：最大寻址 $2^{64} \approx 1.8 \times 10^{19}$ 字节（理论上的天文数字）
$\text{32位地址空间} = 2^{32} \text{ B} = 4 \text{ GB}$
$\text{64位地址空间} = 2^{64} \text{ B} \approx 1.8 \times 10^{19} \text{ B}$

1.3 文件（File）

文件系统是操作系统最重要的抽象之一，它把复杂的磁盘操作变成简单的"创建、读、写、删除"。
目录层次结构
类似一棵树，根目录（/）在最顶端：

/
├── Faculty/
│   ├── Prof.Brown/
│   │   └── Courses/
│   │       ├── CS101
│   │       └── CS105
│   ├── Prof.Green/
│   │   └── Grants/
│   └── Prof.White/
│       └── Papers/
│           └── SOSP
└── Students/
    ├── Robbert/
    ├── Matty/
    └── Leo/

路径名

绝对路径：从根目录 / 开始，如 /Faculty/Prof.Brown/Courses/CS101
相对路径：从当前工作目录开始，如 Courses/CS101（当前目录是 /Faculty/Prof.Brown 时）
Windows 用反斜杠 \，UNIX/Linux 用正斜杠 /
文件描述符（File Descriptor）
打开文件后，系统返回一个小整数（文件描述符 fd），后续的读写操作都用这个 fd 来引用文件：

#include <stdio.h>
#include <fcntl.h>   /* open() 的标志定义 */
#include <unistd.h>  /* read(), write(), close() */
int main(void) {
    int fd;          /* 文件描述符，一个小整数 */
    char buf[128];
    int n;
    /* 打开文件，O_RDONLY 表示只读
     * 成功返回非负整数（文件描述符），失败返回 -1 */
    fd = open("myfile.txt", O_RDONLY);
    if (fd < 0) {
        /* 打开失败 */
        return 1;
    }
    /* 读取最多127个字节到buf
     * 返回实际读到的字节数，0表示文件结束，-1表示出错 */
    n = read(fd, buf, 127);
    if (n > 0) {
        buf[n] = '\0'; /* 补上字符串结束符 */
        write(1, buf, n); /* fd=1 是标准输出 */
    }
    /* 关闭文件，释放文件描述符 */
    close(fd);
    return 0;
}

https://godbolt.org/z/sbj4WbnW7
文件挂载（Mount）
UNIX 中，可以把另一个文件系统"挂载"到目录树的某个节点上，从而把U盘、外置硬盘等无缝集成到同一棵目录树里：

挂载前：                    挂载后（U盘挂载到 /b）：
根文件系统    U盘             根文件系统（含U盘内容）
/            /               /
├── a        ├── x           ├── a
└── b        └── y           └── b      ← 原目录b被"遮住"
                                 ├── x  ← U盘上的x
                                 └── y  ← U盘上的y

特殊文件（Special File）
UNIX 把 I/O 设备也抽象成文件，放在 /dev/ 目录下：

块设备文件（block special file）：磁盘、SSD 等，可随机寻址
字符设备文件（character special file）：键盘、打印机等，按字符流读写
例如：/dev/sda 是第一块硬盘，/dev/lp 是打印机。
管道（Pipe）
管道是连接两个进程的"伪文件"，进程A写入管道，进程B从管道读取，实现进程间通信：

进程A ──写──> [管道 Pipe] ──读──> 进程B
Shell 中的管道示例：
cat file1 file2 | sort > output.txt
解读：
  cat 把两个文件内容输出 → 通过管道 → sort 接收并排序 → 写入 output.txt

1.4 Shell（命令解释器）

Shell 不是操作系统的一部分，但它大量使用操作系统提供的系统调用，是用户和操作系统交互的主要界面。
Shell 的工作原理（简化版）：

/* 一个极度简化的 Shell，展示 fork/execve/waitpid 的用法 */
/* 编译：gcc -o myshell myshell.c */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>   /* fork, execve, getpid */
#include <sys/wait.h> /* waitpid */
#include <string.h>
#define MAX_CMD 256
#define MAX_ARGS 64
/* 简单解析命令行，按空格分割成参数数组 */
int parse_command(char *line, char *argv[]) {
    int argc = 0;
    char *token = strtok(line, " \t\n");
    while (token != NULL && argc < MAX_ARGS - 1) {
        argv[argc++] = token;
        token = strtok(NULL, " \t\n");
    }
    argv[argc] = NULL; /* execve 要求最后一个参数为 NULL */
    return argc;
}
int main(void) {
    char command[MAX_CMD];
    char *argv[MAX_ARGS];
    int status;
    pid_t pid;
    while (1) {
        /* 显示提示符，$ 符号 */
        printf("$ ");
        fflush(stdout);
        /* 从标准输入读取一行命令 */
        if (fgets(command, MAX_CMD, stdin) == NULL) {
            break; /* 读到 EOF（Ctrl+D），退出 */
        }
        /* 解析命令行 */
        if (parse_command(command, argv) == 0) {
            continue; /* 空行，继续 */
        }
        /* 内置命令：exit */
        if (strcmp(argv[0], "exit") == 0) {
            break;
        }
        /* fork() 创建子进程
         * 返回值：
         *   在父进程中：返回子进程的 PID（> 0）
         *   在子进程中：返回 0
         *   出错：返回 -1 */
        pid = fork();
        if (pid < 0) {
            /* fork 失败 */
            perror("fork failed");
            continue;
        }
        if (pid == 0) {
            /* ===== 这里是子进程执行的代码 ===== */
            /* execve 用指定程序替换当前进程的映像
             * 参数1：可执行文件路径
             * 参数2：参数数组（argv[0] 是程序名）
             * 参数3：环境变量（NULL 表示不传）
             * 如果成功，execve 不会返回；失败则返回 -1 */
            execvp(argv[0], argv); /* execvp 会自动在 PATH 中搜索 */
            /* 只有 exec 失败才会执行到这里 */
            perror("exec failed");
            exit(1); /* 子进程退出 */
        } else {
            /* ===== 这里是父进程执行的代码 ===== */
            /* waitpid 等待指定子进程结束
             * 参数1：要等待的子进程 PID
             * 参数2：保存退出状态的地址
             * 参数3：选项（0 = 阻塞等待）*/
            waitpid(pid, &status, 0);
            /* 子进程结束后，父进程继续循环，等待下一条命令 */
        }
    }
    printf("Bye!\n");
    return 0;
}

https://godbolt.org/z/3zGd5K175
Shell 的重要特性：

# 输入/输出重定向
date > file          # 将 date 命令的输出写入 file（标准输出重定向）
sort < file1 > file2 # 从 file1 读入，排序后写入 file2
# 管道（|）：将前一个命令的输出作为后一个命令的输入
cat file1 file2 file3 | sort > /dev/lp
# 后台运行（&）：不等待命令完成，立即返回提示符
cat file1 | sort > output.txt &

1.5 “个体发育重演系统发育”

作者借用生物学概念说明：每一代新型计算机（大型机→小型机→个人电脑→嵌入式→智能卡）都会重演前辈走过的路——从汇编语言编程开始，逐渐发展出高级语言、保护机制、文件系统、虚拟内存……

技术/概念	首次出现	消失	复活
汇编语言编程	第一代计算机	高级语言出现后	每代新硬件初期都复活
单道程序设计	早期所有平台	保护硬件出现后	嵌入式系统中依然存在
单级目录	早期磁盘系统	多级目录出现后	某些简单设备
微程序	IBM 360	RISC 兴起后	CPU 漏洞修复时复活

2. 系统调用详解

2.1 系统调用执行的完整流程

以 read(fd, buffer, nbytes) 为例，展示从用户程序到内核再回来的全过程（共11步）：

用户程序                    C库(read函数)              操作系统内核
----------                  -------------              ----------------
1. 准备参数：
   nbytes → RDX寄存器
   buffer → RSI寄存器
   fd     → RDI寄存器
2. call read(库函数调用)
                             3. 把系统调用号
                                放入 RAX 寄存器
                                (read = 0号)
                             4. 执行 SYSCALL 指令
                                (陷入内核，切换到内核模式)
                                                    5. 根据 RAX 查
                                                       系统调用表
                                                    6. 跳转到 read
                                                       处理函数
                                                    7. 执行 read 操作
                                                       (可能阻塞等待数据)
                                                    8. 操作完成，
                                                       返回值放 RAX
                             9. 从内核模式切回用户模式
                            10. 返回 count 给调用者
11. 用户程序继续执行

ASCII 图解（参考教材图1-17）：

内存地址高端
  0xFFFFFFFF
  +-----------------------------------+
  |         内核空间（操作系统）        |
  |  +----------------------------+   |
  |  | 系统调用分发表             |   |
  |  | [0] = read_handler         |   |
  |  | [1] = write_handler        |   |
  |  | ...                        |   |
  |  +----------------------------+   |
  +-----------------------------------+
  |         用户空间               |
  |  +----------------------------+   |
  |  | C库的 read() 函数           |   | ← 步骤4: SYSCALL指令在此
  |  +----------------------------+   |
  |  | 用户程序 (main等)          |   | ← 步骤1-3: 准备参数并调用
  +-----------------------------------+
  0x00000000
内存地址低端

2.2 POSIX 主要系统调用

进程管理

系统调用	作用	返回值
`fork()`	创建子进程（完整复制父进程）	父进程得到子PID，子进程得到0
`waitpid(pid, &stat, opts)`	等待子进程结束	子进程PID
`execve(name, argv, envp)`	用新程序替换当前进程映像	成功不返回，失败返回-1
`exit(status)`	终止进程，返回状态码	不返回

fork() 的独特之处：

/* fork 演示：一次调用，两处返回 */
/* 编译：gcc -o fork_demo fork_demo.c */
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
int main(void) {
    pid_t pid;
    int x = 10; /* 父子进程各有自己的副本（写时复制） */
    printf("fork 之前，x = %d\n", x);
    pid = fork(); /* 从这里开始，同时有两个进程在运行 */
    if (pid < 0) {
        /* fork 失败 */
        perror("fork");
        return 1;
    } else if (pid == 0) {
        /* 子进程执行这里：pid == 0 */
        x = 20; /* 修改子进程的 x，不影响父进程 */
        printf("子进程: PID=%d, x=%d\n", getpid(), x);
        return 0; /* 子进程退出 */
    } else {
        /* 父进程执行这里：pid == 子进程的PID */
        waitpid(pid, NULL, 0); /* 等子进程结束 */
        printf("父进程: PID=%d, x=%d (x未变)\n", getpid(), x);
        return 0;
    }
}
/* 运行结果示例：
   fork 之前，x = 10
   子进程: PID=1235, x=20
   父进程: PID=1234, x=10 (x未变)
*/

https://godbolt.org/z/4jr49cf8x
写时复制（Copy-on-Write）：fork后父子进程共享同一份物理内存，只有当某一方修改内存时，操作系统才复制被修改的那一小块。这大大减少了fork的开销。

文件管理

系统调用	作用
`fd = open(file, how)`	打开文件，返回文件描述符
`close(fd)`	关闭文件
`n = read(fd, buf, nbytes)`	从文件读数据到缓冲区
`n = write(fd, buf, nbytes)`	从缓冲区写数据到文件
`pos = lseek(fd, offset, whence)`	移动文件读写指针
`stat(name, &buf)`	获取文件信息（大小、权限等）

/* lseek 演示：随机访问文件 */
/* 编译：gcc -o lseek_demo lseek_demo.c */
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
int main(void) {
    /* 假设文件内容是: 2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4
     *                 位置: 0  1  2  3  4  5  6  7  8  9  10 */
    int fd;
    unsigned char buf[4];
    int i;
    fd = open("data.bin", O_RDONLY);
    if (fd < 0) { perror("open"); return 1; }
    /* SEEK_SET = 从文件开头算起
     * 跳到第3个字节的位置（0-based，即第4个字节）*/
    lseek(fd, 3, SEEK_SET);
    /* 读4个字节：位置3, 4, 5, 6
     * 文件内容：8, 2, 8, 1 */
    read(fd, buf, 4);
    printf("读取结果：");
    for (i = 0; i < 4; i++) {
        printf("%d ", buf[i]);
    }
    printf("\n"); /* 输出: 8 2 8 1 */
    close(fd);
    return 0;
}

https://godbolt.org/z/qYfcv9hnx

目录管理

系统调用	作用
`mkdir(name, mode)`	创建目录
`rmdir(name)`	删除空目录
`link(name1, name2)`	为文件创建硬链接（同一文件，两个名字）
`unlink(name)`	删除目录项
`mount(special, name, flag)`	挂载文件系统
`umount(special)`	卸载文件系统

i-node（索引节点）与 link 的工作原理：

UNIX 文件系统的核心数据结构：
目录（就是一张表）：
  i-number | 文件名
  ---------+---------
     16    | mail
     81    | games
     70    | memo     ← 执行 link 前只有这一项指向 i-node 70
执行 link("/usr/jim/memo", "/usr/ast/note") 后：
ast 的目录里新增：
     70    | note     ← 也指向 i-node 70（同一个物理文件！）
i-node 70 的内容：
  - 文件大小
  - 磁盘块位置
  - 链接计数 = 2  ← 有两个目录项指向我
  - 所有者、权限...
只有当链接计数变为0，文件才真正被删除。

权限保护

UNIX 文件权限用 9个二进制位 表示，分三组（owner / group / others），每组3位（rwx）：

权限字符串示例：rwxr-x--x
拆解：
  rwx   r-x   --x
  |||   |||   |||
  |||   |||   ||+-- others 可执行（x）
  |||   |||   |+--- others 不可写（-）
  |||   |||   +---- others 不可读（-）
  |||   ||+-------- group 可执行（x）
  |||   |+--------- group 不可写（-）
  |||   +---------- group 可读（r）
  ||+-------------- owner 可执行（x）
  |+--------------- owner 可写（w）
  +---------------- owner 可读（r）
八进制表示：
  rwx = 111 = 7
  r-x = 101 = 5
  --x = 001 = 1
  所以 rwxr-x--x = 0751
chmod("file", 0644) 设置为：
  rw-r--r-- 即 110 100 100
  owner可读写，其他人只读

数值计算：
$\text{权限数值} = r \times 4 + w \times 2 + x \times 1$
例：rwx = $\times 4 + 1 \times 2 + 1 \times 1 = 7$ ，r-x = $\times 4 + 0 \times 2 + 1 \times 1 = 5$

UNIX 与 Windows API 对比

UNIX 系统调用	Windows API	说明
`fork()` + `execve()`	`CreateProcess()`	Windows 合并了创建+执行
`waitpid()`	`WaitForSingleObject()`	等待进程/事件
`exit()`	`ExitProcess()`	退出进程
`open()`	`CreateFile()`	打开/创建文件
`read()`	`ReadFile()`	读文件
`write()`	`WriteFile()`	写文件
`lseek()`	`SetFilePointer()`	移动文件指针
`link()`	无	Windows 不支持硬链接（老版本）
`mount()`	无	Windows 不支持挂载概念
`kill()`	无	Windows 无信号机制
`chmod()`	无（NT有独立安全机制）	权限模型不同

Windows 编程模型与 UNIX 的根本区别：

UNIX 程序：顺序执行，主动调用系统调用
Windows 程序：事件驱动，等待事件（鼠标点击、键盘输入等），调用事件处理函数

3. 操作系统的内部结构

3.1 整体式结构（Monolithic / 宏内核）

最常见、最简单的结构：整个操作系统是一个大程序，运行在内核模式。所有函数都可以互相调用。

宏内核结构：
+------------------------------------------+
|           操作系统内核（内核模式）          |
|  +--------+  +--------+  +-----------+   |
|  |进程管理|  |内存管理|  | 文件系统   |   |
|  +--------+  +--------+  +-----------+   |
|  +--------+  +-------------------+       |
|  |I/O管理 |  | 设备驱动程序(全部)|       |
|  +--------+  +-------------------+       |
|  所有组件都在同一地址空间，可互相直接调用   |
+------------------------------------------+
|           用户空间（用户模式）              |
|  应用程序 A  |  应用程序 B  |  应用程序 C  |
+------------------------------------------+

宏内核的三层内部组织：

第一层（顶层）：主程序（main procedure）
              ↕  接收系统调用请求
第二层（中层）：服务程序（service procedures）
              每个系统调用对应一个服务函数
              ↕  调用辅助功能
第三层（底层）：工具程序（utility procedures）
              被多个服务程序共用的通用功能

优点：效率高（直接函数调用，无消息传递开销）
缺点：任何一个组件崩溃会拖垮整个系统；庞大复杂，难以维护
DLL（动态链接库）：Windows 的 .dll 文件，Linux 的 .so（共享库），是可以动态加载的内核扩展模块。

3.2 分层结构（Layered）

Dijkstra 在 1968 年设计的 THE 系统首创此方法。每一层只能调用其下层的服务：

层次  功能
-----+------------------------------------------
  5  |  操作员（用户）
  4  |  用户程序
  3  |  输入/输出管理
  2  |  操作员-进程通信（控制台）
  1  |  内存与磁鼓管理（虚拟内存雏形）
  0  |  处理器分配与多道程序设计（CPU调度）

优点：结构清晰，每层只需关注自己的职责
缺点：层间调用有开销；实际系统很难严格分层

3.3 微内核（Microkernel）

核心思想：内核只做最少的事，其他全部放到用户空间的进程里。
内核只保留：进程调度、进程间通信（消息传递）、基本内存管理，约 15,000 行 C 代码（MINIX 3）。
内核外（用户模式进程）：文件系统、设备驱动、网络栈……

微内核结构：
+---------------------------------------------------------------+
|                        用户模式                               |
|  +--------+  +--------+  +--------+  +--------+  +--------+  |
|  | 文件   |  | 进程   |  | 磁盘   |  | 终端   |  | 网络   |  |
|  | 服务器 |  | 管理器 |  | 驱动   |  | 驱动   |  | 驱动   |  |
|  +--------+  +--------+  +--------+  +--------+  +--------+  |
|                     通过消息传递通信                            |
+---------------------------------------------------------------+
|                      微内核（内核模式）                         |
|         进程调度  |  消息传递  |  基本内存管理                   |
+---------------------------------------------------------------+

优点：

单个组件崩溃不会蔓延（如音频驱动崩溃，只是没声音，系统不崩）
更安全：每个驱动只有最小权限（POLA = Principle of Least Authority，最小权限原则）
MINIX 3 甚至能自动检测并替换崩溃的驱动（"自愈"系统）
缺点：消息传递比直接函数调用慢
机制（Mechanism）与策略（Policy）的分离：

例子：CPU调度

机制（在内核）：找到优先级最高的可运行进程，运行它

策略（在用户态）：如何给进程分配优先级
这样内核可以非常小，策略可以灵活修改。

3.4 客户端-服务器模型（Client-Server）

微内核的变体。进程分为两类：

服务器（Server）：提供某种服务（文件服务、打印服务…）
客户端（Client）：通过发消息请求服务
这个模型可以推广到网络上：客户端和服务器可以在不同机器上，客户端只管发请求，不需要知道服务器在哪里。

网络上的客户端-服务器模型：
[用户PC（客户端）] --- 网络 ---> [文件服务器]
                                 [进程服务器]
                                 [Web服务器]
用户PC浏览网页：
  PC 发送 HTTP 请求 ──────────────────> Web服务器
  Web服务器返回 HTML ←──────────────────
  PC 只管显示，不关心服务器在哪台机器上

3.5 虚拟机（Virtual Machine）

核心思想：在一台真实硬件上模拟出多台完整的计算机。
起源：IBM 的 VM/370 系统（1970年代），现代版本是 z/VM。
VM/370 的结构：

+------------------+  +------------------+  +------------------+
|   虚拟机 1       |  |   虚拟机 2       |  |   虚拟机 3       |
|  (运行 OS/360)   |  |  (运行 CMS)      |  |  (运行 Linux)    |
+------------------+  +------------------+  +------------------+
|         VM/370 虚拟机监控程序（Hypervisor）                    |
|         在真实 IBM 370 硬件上运行                              |
+------------------------------------------------------------------+

每个虚拟机是真实硬件的完整副本，可以运行任何操作系统。
Hypervisor 的两种类型：

类型1 Hypervisor（裸机型）：         类型2 Hypervisor（托管型）：
+----------+ +----------+            +----------+ +----------+
| Guest OS | | Guest OS |            | Guest OS | | Guest OS |
+----------+ +----------+            +----------+ +----------+
|     Hypervisor        |            |     Hypervisor        |
|   直接运行在硬件上     |            |  运行在宿主OS上        |
+------------------------+           +------------------------+
|        硬件            |           |      宿主操作系统      |
+------------------------+           +------------------------+
                                     |        硬件            |
                                     +------------------------+
例：VMware ESXi, Xen                  例：VirtualBox, VMware Workstation
    Microsoft Hyper-V                      QEMU（用户模式）

容器（Container）vs 虚拟机：

比较项	虚拟机	容器（如 Docker）
隔离级别	完全独立，有自己的内核	共享宿主机内核
启动时间	分钟级	秒级
资源开销	大（每个VM有完整OS）	小
安全隔离	强	较弱（内核共享）
可运行异种OS	可以（Linux上跑Windows）	不能（必须与宿主同内核）

JVM（Java虚拟机）：一种特殊的虚拟机，不是模拟整台计算机，而是模拟一个"Java专用CPU"。Java代码编译成字节码，可以在任何有JVM的平台上运行。

3.6 外核（Exokernel）与单内核（Unikernel）

外核（Exokernel）：不做资源抽象，只做资源分配和保护。每个虚拟机直接管理分配给它的原始硬件资源（磁盘块0-1023给虚拟机1，1024-2047给虚拟机2…）。减少了虚拟机监控程序的映射层，效率更高。
单内核（Unikernel）：将操作系统库（LibOS）和应用程序链接成一个单一的可执行文件，只包含应用程序需要的功能，在虚拟机上运行。极度轻量，只有一个应用，无需进程间保护。

对比各种OS结构：
宏内核：  [所有OS组件] 在内核空间，一个大程序
分层：    [层5][层4][层3][层2][层1][层0]，严格层次
微内核：  [极小内核] + [用户态服务器群]
虚拟机：  [Hypervisor] + [多个完整OS实例]
外核：    [只做分配的小内核] + [LibOS in 用户VM]
单内核：  [LibOS + 应用] 合为一体，跑在虚拟机上

4. C语言与操作系统开发

4.1 C 语言的关键特性

操作系统为什么用 C 而不是 Java/Python？

特性	C	Java/Python
垃圾回收	无（程序员手动管理内存）	有
指针	有（直接访问内存地址）	无
运行时	直接在硬件上执行	需要虚拟机/解释器
可预测性	高（无GC暂停）	低（GC随时可能暂停）
内存控制	完全	有限

操作系统需要在中断发生后的几微秒内响应，垃圾收集器随机暂停是不可接受的。
C 的指针：

/* 指针基础演示 */
/* 编译：gcc -o pointer_demo pointer_demo.c */
#include <stdio.h>
int main(void) {
    char c1, c2;
    char *p;         /* p 是一个指针，存放某个 char 变量的地址 */
    c1 = 'c';        /* c1 保存字符 'c' 的 ASCII 码（99）*/
    p = &c1;         /* & 是"取地址"运算符，p 现在指向 c1 */
    c2 = *p;         /* * 是"解引用"运算符，读取 p 指向的内容 */
                     /* 等价于 c2 = c1 */
    printf("c1 = %c, 地址 = %p\n", c1, (void*)&c1);
    printf("p  = %p（存放的是c1的地址）\n", (void*)p);
    printf("*p = %c（p指向的内容）\n", *p);
    printf("c2 = %c\n", c2); /* 输出: c */
    return 0;
}

https://godbolt.org/z/8v3frxhGq

4.2 头文件与预处理

/* 头文件使用示例：演示宏定义和条件编译 */
/* 常量宏：编译时替换，节省内存，增加可读性 */
#define BUFFER_SIZE 4096   /* 不要写成魔法数字 4096 */
/* 带参数的宏（类似内联函数，但没有类型检查）*/
#define MAX(a, b)  ((a) > (b) ? (a) : (b))
/* 注意：参数要加括号，防止运算符优先级问题 */
/* MAX(j, k+1) 展开为 ((j) > (k+1) ? (j) : (k+1)) */
/* 条件编译：根据目标平台选择不同代码 */
#ifdef X86
    void intel_int_ack(void); /* 只在x86平台编译这个函数声明 */
#endif
#ifdef ARM
    void arm_int_ack(void);   /* 只在ARM平台编译 */
#endif

4.3 大型项目的编译流程

操作系统有数百万行代码，每次修改都重新编译所有文件是不可接受的。make 工具通过 Makefile 追踪依赖关系，只重新编译必要的文件。

编译流程（以有3个.c文件的项目为例）：
defs.h ──┐
         ├──> C预处理器 ──> C编译器 ──> main.o ──┐
main.c ──┘                                      |
                                                 ├──> 链接器 ──> a.out（可执行文件）
mac.h ──┐                                       |
         ├──> C预处理器 ──> C编译器 ──> help.o ──┤
help.c ──┘                                      |
                                                 |
other.c ──────────────> C编译器 ──> other.o ──┤
                                                |
libc.a（C标准库）──────────────────────────────┘

各步骤说明：

C预处理器：处理 #include、#define、#ifdef 等指令，展开宏，合并头文件
C编译器：把 .c 文件编译成 .o 目标文件（机器码，但还没有完整地址）
链接器（linker）：把所有 .o 文件和库文件合并，解析跨文件的函数引用，生成最终可执行文件

4.4 进程的内存布局（运行时模型）

/* 演示三段内存布局 */
/* 编译：gcc -o mem_layout mem_layout.c */
#include <stdio.h>
#include <stdlib.h>
/* 全局变量：存放在数据段（.data / .bss）*/
int global_var = 42;      /* 已初始化，在 .data 段 */
int uninitialized;        /* 未初始化，在 .bss 段，自动清零 */
/* 函数代码：存放在代码段（.text），只读 */
void func(int param) {    /* param 在栈上 */
    int local = 10;       /* local 在栈上 */
    /* 栈向低地址方向增长（大多数架构）*/
    printf("  参数地址: %p\n", (void*)&param);
    printf("  局部变量地址: %p\n", (void*)&local);
}
int main(void) {
    int *heap_var = malloc(sizeof(int)); /* 堆，向高地址增长 */
    *heap_var = 99;
    printf("代码段（函数main的地址）: %p\n", (void*)main);
    printf("数据段（全局变量地址）:   %p\n", (void*)&global_var);
    printf("堆（malloc分配的地址）:   %p\n", (void*)heap_var);
    printf("栈（main的局部变量地址）: %p\n", (void*)&heap_var);
    printf("调用 func:\n");
    func(5);
    free(heap_var); /* 必须手动释放！C没有GC */
    return 0;
}

https://godbolt.org/z/q3We5PPM3
进程地址空间布局（典型 Linux x86-64）：

地址高（0xFFFFFFFFFFFFFFFF）
  +------------------+
  |  内核空间（OS）   |  ← 用户不可访问
  +------------------+
  |  栈 (Stack)       |  ← 向下增长（局部变量、函数参数、返回地址）
  |     ↓            |
  |   （空隙）        |
  |     ↑            |
  |  堆 (Heap)        |  ← 向上增长（malloc动态分配）
  +------------------+
  |  数据段 (Data)    |  ← 全局/静态变量
  +------------------+
  |  代码段 (Text)    |  ← 程序指令（只读）
  +------------------+
地址低（0x0000000000000000）

5. 度量单位

操作系统领域有两套单位系统：
存储容量（内存/硬盘）：二进制（ $2$ 的幂次）

符号	名称	实际大小
1 KB	千字节	$2^{10} = 1,024$ 字节
1 MB	兆字节	$2^{20} = 1,048,576$ 字节
1 GB	吉字节	$2^{30} \approx 10^9$ 字节
1 TB	太字节	$2^{40} \approx 10^{12}$ 字节

网络速率/时钟频率：十进制（ $10$ 的幂次）

符号	含义
1 Kbps	$10^3 = 1,000$ bits/s
1 Mbps	$10^6$ bits/s
1 Gbps	$10^9$ bits/s

$\text{ KB（存储）} = 2^{10} \text{ B} = 1,024 \text{ B} \neq 1,000 \text{ B}$
$\text{ Kbps（速率）} = 10^3 \text{ bps} = 1,000 \text{ bps}$
常用时间单位：

单位	大小	用途
ms（毫秒）	$10^{-3}$ 秒	磁盘寻道时间（~5ms）
μs（微秒）	$10^{-6}$ 秒	SSD访问时间（~100μs）
ns（纳秒）	$10^{-9}$ 秒	内存访问时间（~100ns），CPU时钟周期
ps（皮秒）	$10^{-12}$ 秒	CPU内部时序

UNIX 时间戳问题（Y2K38 问题）：
UNIX 时间从 1970 年 1 月 1 日 00:00:00 开始计秒。32位有符号整数最大值：
$2^{31} - 1 = 2,147,483,647 \text{ 秒}$
从 1970 年算起：
$\frac{2,147,483,647}{3600 \times 24 \times 365} \approx 1970 + 68 = 2038 \text{ 年}$
即 2038 年 1 月 19 日，32 位 UNIX 系统将发生溢出。解决方案：使用 64 位时间戳。
$2^{63} - 1 \approx 9.2 \times 10^{18} \text{ 秒} \approx 2920 \text{ 亿年后溢出}$

6. 课后习题解析

习题 4：为什么要缓存整行而不是单个字节？

缓存整行（通常 64 字节）的好处：

空间局部性：程序访问地址 X 后，很可能访问 X+1、X+2……，整行已经在缓存中
减少总线通信次数：一次传输 64 字节，比 64 次传输 1 字节效率高很多
预取效果：循环访问数组时，下一次迭代需要的数据可能已经在同一缓存行

习题 12：磁盘计算

题目：255-GB 磁盘，65536 个柱面，每个磁道 255 个扇区，每个扇区 512 字节。平均寻道 11ms，平均旋转延迟 7ms，读取速率 100 MB/s。计算读取 100 KB 所需时间。
首先验算磁盘容量：
$\text{总容量} = 65536 \times (\text{磁头数}) \times 255 \times 512 \text{ B}$
$\text{ GB} = 255 \times 2^{30} \approx 2.74 \times 10^{11} \text{ B}$
$\text{磁头数} = \frac{255 \times 2^{30}}{65536 \times 255 \times 512} = \frac{255 \times 2^{30}}{65536 \times 255 \times 512}$
$\frac{2^{30}}{65536 \times 512} = \frac{2^{30}}{2^{16} \times 2^9} = \frac{2^{30}}{2^{25}} = 2^5 = 32 \text{ 个磁头（16 张盘片双面）}$
读取 100 KB 的时间：
$T = T_{seek} + T_{rotation} + T_{transfer}$
$T_{transfer} = \frac{100 \text{ KB}}{100 \text{ MB/s}} = \frac{100 \times 1024 \text{ B}}{100 \times 10^6 \text{ B/s}} = \frac{102400}{10^8} \approx 1.024 \text{ ms}$
$T_{total} = 11 \text{ ms} + 7 \text{ ms} + 1.024 \text{ ms} \approx 19 \text{ ms}$

习题 15：四级流水线

每级 1 ns，流水线满载后，每个时钟周期（1 ns）完成一条指令：
$\text{吞吐量} = \frac{1}{1 \text{ ns}} = 10^9 \text{ 条/秒} = 1 \text{ GIPS（每秒十亿条指令）}$
注意：流水线不减少单条指令的延迟（仍需 4 ns），但提高了吞吐量。

习题 16：分层存储系统的平均访问时间

缓存命中率： $h_c = 0.95$ ，访问时间 $t_c = 2 \text{ ns}$
主内存命中率（缓存未命中后）： $h_m = 0.99$ ，访问时间 $t_m = 10 \text{ ns}$
磁盘访问时间： $t_d = 10 \text{ ms} = 10,000,000 \text{ ns}$
平均访问时间计算（三级层次）：
$T_{avg} = h_c \cdot t_c + (1 - h_c) \cdot [h_m \cdot t_m + (1 - h_m) \cdot t_d]$
代入数值：
$T_{avg} = 0.95 \times 2 + 0.05 \times [0.99 \times 10 + 0.01 \times 10,000,000]$
$\times [9.9 + 100,000]$
$\times 100,009.9$
$\approx 5002 \text{ ns} \approx 5 \text{ μs}$
关键教训：磁盘未命中哪怕只有 0.05%，也会主导平均访问时间。

习题 23：多路复用类型

资源	时分复用	空分复用
CPU	是（进程轮流使用）	否（CPU本身不可分割，但多核可以）
内存	否（通常同时分配）	是（每个进程占不同区域）
磁盘/SSD	是（I/O请求排队）	是（不同文件占不同块）
网卡	是（数据包轮流发送）	否（但可以用VLAN分割）
打印机	是（打印任务排队）	否
键盘	是（当前焦点窗口）	否
显示器	是（窗口切换）	是（多个窗口同时显示）

总结：操作系统结构全景

核心概念速查（本章下半部分）

概念	一句话理解
进程	正在运行的程序，包含代码、数据、状态
进程表	内核保存所有进程状态信息的数组
fork	创建子进程，父子进程是几乎完全一样的副本
execve	用新程序替换当前进程的内存映像
信号	软件中断，异步通知进程发生了某个事件
UID/GID	用户/组标识符，用于权限控制
地址空间	每个进程独有的虚拟内存范围，互相隔离
写时复制	fork后父子共享物理内存，只有写操作时才真正复制
文件描述符	打开文件后系统返回的整数，代表那个打开的文件
i-node	UNIX文件的元数据节点，链接计数降为0才删除
硬链接	多个目录项指向同一个i-node，同一个文件
挂载	把一个文件系统接入另一个目录树的某个节点
管道	连接两个进程的伪文件，用于进程间通信
系统调用	用户程序请求内核服务的机制（陷阱指令触发）
宏内核	OS整体在内核态，一个大程序，效率高但脆弱
微内核	内核最小化，驱动等放用户态，可靠但慢一点
Hypervisor	虚拟机监控程序，管理多个虚拟机
容器	共享内核的轻量级进程隔离，比虚拟机开销小
POLA	最小权限原则，每个组件只有做自己工作所需的最小权限

操作系统第二章笔记：进程与线程

覆盖 2.1 进程 / 2.2 线程（用户级与内核级）
力求通俗易懂，含完整可运行 C 代码、ASCII 图示、Mermaid 图

1. 进程的基本概念

1.1 为什么需要进程？

现代计算机同时做很多事：Web服务器响应请求的同时，后台有杀毒软件、邮件接收程序、打印任务……这些事情需要同时推进，但 CPU 在任一时刻只能执行一条指令。
操作系统用进程这个抽象来解决这个问题：让每个任务都以为自己独占一个CPU（虚拟CPU），实际上操作系统在快速切换。

1.2 进程 vs 程序

这是最容易混淆的概念，一个比喻帮你彻底搞清楚：

程序  =  菜谱（存在书架上，不动）
进程  =  厨师按照菜谱做菜的过程（有状态：切到哪步了，锅在哪里...）
CPU   =  厨师（处理器）
同一份菜谱可以同时有两个厨师在做（两个进程运行同一个程序）
厨师突然去处理蜜蜂蜇伤（切换到更高优先级的进程）：
  保存当前进度（保存进程状态）→ 拿急救手册（新程序）→ 处理完毕
  → 回来继续做蛋糕（恢复之前的进程状态）

关键区别：

程序：磁盘上的静态代码文件，不做任何事
进程：程序的一次运行实例，有程序计数器、寄存器、变量、状态
同一个程序运行两次 = 两个独立的进程（各自有独立的状态）。

1.3 伪并行（Pseudoparallelism）

单 CPU 在多个进程间快速切换（每次几十~几百毫秒），给人"同时运行"的错觉：

时间轴（单CPU，多进程切换）：
进程A: |==运行==|       |===运行===|          |=运行=|
进程B:          |=运行=|           |===运行===|
进程C:                                                 |=运行=|
时间:  0       10ms    20ms       30ms        40ms    50ms
人的感觉：A、B、C 好像同时在跑
实际上：每一时刻只有一个进程在 CPU 上运行

与之对比的是真并行（True Parallelism）：多核CPU，多个进程同时在不同核上运行。

2. 进程的创建

2.1 四种触发进程创建的情形

1. 系统启动（booting）
   → 操作系统自动创建很多后台进程（守护进程 daemon）
2. 运行中的进程执行"创建进程"的系统调用
   → 例如：shell 执行你输入的命令
3. 用户主动请求创建
   → 双击图标、在终端输入命令
4. 批处理作业的启动
   → 大型机上的任务队列

守护进程（Daemon）：后台运行、不与用户直接交互的进程。例如：

邮件接收进程（sendmail）
Web 服务器（httpd/nginx）
打印服务（cupsd）
查看进程的方法：
UNIX/Linux：ps aux 或 top
Windows：任务管理器（Task Manager）

2.2 UNIX 创建进程：fork + execve

UNIX 创建进程是两步走：

步骤1：fork()
  父进程 ──fork()──> 子进程（父进程的完整副本）
  父子进程有相同的：内存映像、环境变量、打开的文件
步骤2：execve()（在子进程里调用）
  子进程 ──execve("sort",...)──> 用 sort 程序替换自己的内存映像
  子进程现在运行 sort，已经不是父进程的副本了

为什么要两步走？因为在 fork 和 execve 之间，子进程可以重定向文件描述符（实现 <、> 重定向和管道 |）。

/* 演示 fork + execve：简单的命令执行器 */
/* 编译：gcc -o process_create process_create.c */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>    /* fork, execve, getpid */
#include <sys/wait.h>  /* waitpid, WEXITSTATUS */
int main(void) {
    pid_t pid;
    int status;
    printf("父进程 PID = %d\n", getpid());
    /* fork() 创建子进程
     * 返回值含义：
     *   > 0  → 当前是父进程，返回值是子进程PID
     *   == 0 → 当前是子进程
     *   < 0  → fork失败（系统资源不足等）
     */
    pid = fork();
    if (pid < 0) {
        perror("fork 失败");
        return 1;
    }
    if (pid == 0) {
        /* ---- 子进程执行这段代码 ---- */
        printf("子进程 PID = %d，父进程 PID = %d\n",
               getpid(), getppid());
        /* execve 三个参数：
         * 1. 可执行文件路径
         * 2. 参数数组（argv），第一个元素是程序名，最后必须是 NULL
         * 3. 环境变量数组，NULL 表示继承父进程环境
         *
         * execve 成功后，当前进程的代码/数据/栈全部被替换
         * 下面的 printf 永远不会执行（除非 execve 失败）
         */
        char *argv[] = {"/bin/ls", "-l", "/tmp", NULL};
        execve("/bin/ls", argv, NULL);
        /* 只有 execve 失败才到这里 */
        perror("execve 失败");
        exit(1);
    } else {
        /* ---- 父进程执行这段代码 ---- */
        printf("父进程等待子进程 %d 结束...\n", pid);
        /* waitpid 等待指定子进程结束
         * 参数1：等待的PID（-1 表示等待任意子进程）
         * 参数2：存放退出状态
         * 参数3：选项（0=阻塞等待）
         */
        waitpid(pid, &status, 0);
        /* WEXITSTATUS 宏提取退出码（0=正常，非0=出错）*/
        printf("子进程退出，退出码 = %d\n", WEXITSTATUS(status));
    }
    return 0;
}

https://godbolt.org/z/Ghn3GxTrd

2.3 Windows 创建进程：CreateProcess

Windows 把创建和加载程序合并成一个函数 CreateProcess，有 10个参数（复杂得多）：

/* Windows CreateProcess 示意（不可直接在 Linux 编译，仅供理解结构）*/
/*
BOOL CreateProcess(
    LPCTSTR lpApplicationName,    // 可执行文件路径
    LPTSTR  lpCommandLine,        // 命令行字符串
    LPSECURITY_ATTRIBUTES lpProcessAttr,  // 进程安全属性
    LPSECURITY_ATTRIBUTES lpThreadAttr,   // 线程安全属性
    BOOL    bInheritHandles,      // 是否继承父进程的句柄
    DWORD   dwCreationFlags,      // 优先级等创建标志
    LPVOID  lpEnvironment,        // 环境变量（NULL=继承）
    LPCTSTR lpCurrentDirectory,   // 当前目录
    LPSTARTUPINFO lpStartupInfo,  // 窗口和输入输出配置
    LPPROCESS_INFORMATION lpProcessInformation  // 返回新进程信息
);
*/

UNIX 与 Windows 创建进程对比：

对比项	UNIX	Windows
创建方式	`fork()` + `execve()` 两步	`CreateProcess()` 一步
子进程初始内容	父进程的完整副本	直接加载指定程序
进程关系	有父子层次（进程树）	平等，无严格层次
等待子进程	`waitpid()`	`WaitForSingleObject()`

3. 进程的终止

进程终止的四种原因：

注意：UNIX 和 Windows 中，父进程终止时，子进程不会自动被终止（孤儿进程由 init 收养）。

4. 进程的层次结构

4.1 UNIX：进程树

UNIX 中进程形成严格的树形结构，根是 init（PID=1）：

UNIX 启动流程：

计算机启动
  → 内核启动
  → 创建 init 进程（PID=1）
  → init 读取配置，为每个终端 fork 一个 login 进程
  → 用户登录成功后，login fork 出 shell（bash/zsh 等）
  → shell 等待用户输入命令，每个命令 fork 一个子进程
  → 所有进程都是 init 的后代，形成一棵树

信号与进程组：按 Ctrl+C 时，信号发送给当前终端关联的整个进程组，而非单个进程。

4.2 Windows：平等模型

Windows 没有进程树的概念。父进程创建子进程后，得到一个"句柄（handle）"，但这个句柄可以传给其他进程，层次关系并不严格。

5. 进程的状态

5.1 三种基本状态

每个进程在任意时刻处于三种状态之一：

运行（Running）：当前正在 CPU 上执行
就绪（Ready）：  可以运行，但 CPU 正在给其他进程用
阻塞（Blocked）：等待某个外部事件（如I/O完成），即使 CPU 空闲也不能运行

5.2 状态转换图

         +----------+
         |  运行中   |
         | Running  |
         +----------+
        /            \
  转换2/              \转换1
（调度器              （进程等I/O，
  决定切走）           主动阻塞）
      /                  \
     v                    v
+----------+          +----------+
|   就绪   |          |   阻塞   |
|  Ready   |          |  Blocked |
+----------+          +----------+
     ^                    |
      \                   |转换4
  转换3\           （I/O完成，
（调度器 \            事件发生）
  选中它）\                |
           +---------------+

四种状态转换详解：

转换	触发者	说明
转换1：运行→阻塞	进程自身	等待 I/O（读键盘、读磁盘），逻辑上无法继续
转换2：运行→就绪	调度器	时间片用完，调度器强制切走，进程本身没问题
转换3：就绪→运行	调度器	轮到该进程使用 CPU
转换4：阻塞→就绪	外部事件	等待的 I/O 完成，进程可以继续了

注意：没有"阻塞→运行"的直接转换！阻塞的进程必须先变成就绪，再等调度器选中才能运行。

5.3 用 C 代码模拟状态机

/* 进程状态机模拟演示 */
/* 编译：gcc -o state_machine state_machine.c */
#include <stdio.h>
#include <stdlib.h>
/* 定义进程的三种状态 */
typedef enum {
    RUNNING = 0,   /* 运行中 */
    READY   = 1,   /* 就绪 */
    BLOCKED = 2    /* 阻塞 */
} ProcessState;
/* 进程控制块（简化版）*/
typedef struct {
    int         pid;       /* 进程ID */
    ProcessState state;    /* 当前状态 */
    const char  *name;     /* 进程名（调试用）*/
} Process;
/* 状态名称（方便打印）*/
const char *state_name[] = {"运行中", "就绪  ", "阻塞  "};
/* 打印进程状态 */
void print_state(const Process *p) {
    printf("进程 [%s (PID=%d)] 状态: %s\n",
           p->name, p->pid, state_name[p->state]);
}
/* 转换1：运行 → 阻塞（等待I/O）*/
void process_block(Process *p) {
    if (p->state != RUNNING) {
        printf("错误：只有运行中的进程才能阻塞\n");
        return;
    }
    p->state = BLOCKED;
    printf("  [转换1] %s 等待I/O，进入阻塞状态\n", p->name);
    print_state(p);
}
/* 转换2：运行 → 就绪（时间片用完）*/
void scheduler_preempt(Process *p) {
    if (p->state != RUNNING) {
        printf("错误：只有运行中的进程才能被抢占\n");
        return;
    }
    p->state = READY;
    printf("  [转换2] 调度器剥夺 %s 的CPU，进入就绪状态\n", p->name);
    print_state(p);
}
/* 转换3：就绪 → 运行（调度器选中）*/
void scheduler_dispatch(Process *p) {
    if (p->state != READY) {
        printf("错误：只有就绪进程才能被调度\n");
        return;
    }
    p->state = RUNNING;
    printf("  [转换3] 调度器选中 %s，开始运行\n", p->name);
    print_state(p);
}
/* 转换4：阻塞 → 就绪（I/O完成）*/
void io_complete(Process *p) {
    if (p->state != BLOCKED) {
        printf("错误：只有阻塞进程才能被唤醒\n");
        return;
    }
    p->state = READY;
    printf("  [转换4] %s 等待的I/O完成，进入就绪状态\n", p->name);
    print_state(p);
}
int main(void) {
    /* 创建两个进程 */
    Process p1 = {1, RUNNING, "浏览器"};
    Process p2 = {2, READY,   "编译器"};
    printf("=== 初始状态 ===\n");
    print_state(&p1);
    print_state(&p2);
    printf("\n=== 模拟调度过程 ===\n");
    /* p1 开始等待网络数据（I/O），阻塞 */
    process_block(&p1);
    /* 调度器把CPU给p2 */
    scheduler_dispatch(&p2);
    /* p1 的网络数据到了，变就绪 */
    io_complete(&p1);
    /* p2 时间片用完 */
    scheduler_preempt(&p2);
    /* 调度器选 p1 运行 */
    scheduler_dispatch(&p1);
    return 0;
}
/* 输出示例：
=== 初始状态 ===
进程 [浏览器 (PID=1)] 状态: 运行中
进程 [编译器 (PID=2)] 状态: 就绪
=== 模拟调度过程 ===
  [转换1] 浏览器 等待I/O，进入阻塞状态
  [转换3] 调度器选中 编译器，开始运行
  [转换4] 浏览器 等待的I/O完成，进入就绪状态
  [转换2] 调度器剥夺 编译器 的CPU，进入就绪状态
  [转换3] 调度器选中 浏览器，开始运行
*/

https://godbolt.org/z/YsM947Mh9

6. 进程的实现

6.1 进程表（Process Table）

操作系统为每个进程维护一个进程表项（Process Control Block，PCB），保存进程的所有信息：

进程表（操作系统内核中的数组/链表）：
+--------+--------+--------+--------+
| 进程0  | 进程1  | 进程2  | ...    |
+--------+--------+--------+--------+
    |
    v
每个表项包含：
进程管理信息：
  - 寄存器值（PC, SP, PSW, 通用寄存器...）
  - 进程状态（运行/就绪/阻塞）
  - 优先级、调度参数
  - PID、父进程PID、进程组
  - 信号掩码与处理函数
  - 进程开始时间、已用CPU时间
内存管理信息：
  - 代码段指针
  - 数据段指针
  - 栈段指针
文件管理信息：
  - 根目录
  - 当前工作目录
  - 打开的文件描述符表
  - UID、GID

6.2 中断处理与进程切换的完整流程

当磁盘中断发生时（进程3正在运行）：

1. 硬件把 PC（程序计数器）和 PSW（程序状态字）压入当前栈
2. 硬件跳转到中断向量表中该中断对应的地址（ISR入口）
3. 汇编例程：保存所有寄存器到进程3的进程表项
4. 汇编例程：切换到操作系统专用的临时栈
5. C语言中断服务例程运行（例如：从磁盘读数据，放入缓冲区）
6. 调度器决定下一个运行哪个进程（可能是进程3，也可能是其他进程）
7. C代码返回汇编代码
8. 汇编代码从新进程的进程表项中恢复寄存器
9. 新进程开始（或继续）运行

关键点：进程每次被中断后，必须精确恢复到中断前的状态，就好像什么都没发生过一样。

7. 多道程序设计的CPU利用率模型

7.1 概率模型

设每个进程有 $p$ 的时间在等待 I/O（阻塞），则 $(1 - p)$ 的时间在用 CPU。
有 $n$ 个进程同时在内存时，所有进程同时在等 I/O 的概率（CPU空闲的概率）为：
$P(\text{CPU空闲}) = p^n$
CPU 利用率为：
$\text{CPU利用率} = 1 - p^n$

7.2 数值示例

进程数 $n$	$p=20\%$ （CPU密集型）	$p=50\%$ （均衡型）	$p=80\%$ （I/O密集型）
1	$1 - 0.2^1 = 80\%$	$1 - 0.5^1 = 50\%$	$1 - 0.8^1 = 20\%$
2	$96\%$	$75\%$	$36\%$
4	$\approx 99.8\%$	$\approx 94\%$	$\approx 59\%$
8	$\approx 100\%$	$\approx 99.6\%$	$\approx 83\%$
10	$\approx 100\%$	$\approx 99.9\%$	$0.8^{10} \approx 89\%$

对 I/O 密集型应用（ $p=80\%$ ），至少需要 10 个进程才能把 CPU 浪费控制在 10% 以下：
$\text{CPU浪费} = p^{10} = 0.8^{10} \approx 0.107 = 10.7\%$

7.3 内存投资的边际效益

实际应用场景（ $p=80\%$ ，每个用户程序占 $2\text{ GB}$ ，OS 占 $2\text{ GB}$ ）：
初始状态（8 GB 内存）：
$\text{可容纳进程数} = \frac{8 - 2}{2} = 3 \text{ 个进程}$
$\text{CPU利用率} = 1 - 0.8^3 \approx 49\%$
增加 8 GB（共 16 GB）：
$\text{可容纳进程数} = \frac{16 - 2}{2} = 7 \text{ 个进程}$
$\text{CPU利用率} = 1 - 0.8^7 \approx 79\%$
$\text{提升} = 79\% - 49\% = 30\%$
再增加 8 GB（共 24 GB）：
$\text{可容纳进程数} = \frac{24 - 2}{2} = 11 \text{ 个进程}$
$\text{CPU利用率} = 1 - 0.8^{11} \approx 91\%$
$\text{提升} = 91\% - 79\% = 12\%$
结论：第一次加内存（ $+8\text{ GB}$ ）提升了 30%，第二次只提升了 12%——边际效益递减。

8. 线程的概念与用途

8.1 为什么需要线程？

进程解决了多任务的问题，但有个缺点：进程间不共享内存，通信代价高。
线程（Thread）= 在同一进程内并发执行的多条控制流，共享地址空间和全局数据。

8.2 线程比进程的优势

优势	说明
共享内存	多个线程直接读写同一份数据，无需进程间通信
创建快	线程创建速度比进程快 10~100 倍
切换快	同进程线程切换不需要切换内存映射，比进程切换快
并发 I/O	一个线程等 I/O 时，其他线程继续用 CPU

8.3 三个经典线程使用场景

场景一：文字处理器（Word Processor）

单线程做法（糟糕）：
  用户删除第1页一句话
  → 程序开始重排整本书（800页）
  → 用户完全卡住，什么都不能做
  → 等排版完成才能继续
三线程做法（优雅）：
  线程1（交互线程）：响应键盘鼠标，永远不卡
  线程2（排版线程）：后台默默重排，不影响交互
  线程3（备份线程）：每隔几分钟自动保存，防止丢失
  三个线程共享同一份文档（同一内存），互不干扰

为什么不能用三个进程代替三个线程？因为三个进程不共享内存，无法访问同一份文档！

场景二：Web 服务器

Web服务器接收大量请求：
调度线程（Dispatcher）：
  while (TRUE) {
      等待新请求到来;
      从线程池取一个空闲工作线程;
      把请求交给它;
  }
工作线程（Worker）：
  while (TRUE) {
      等待调度线程分配任务;
      查页面缓存，命中就直接返回;
      没命中就从磁盘读（此时阻塞）;
      把页面返回给客户端;
  }

调度线程
    |
    |── 请求1 ──> 工作线程1 [查缓存→命中→返回] (快)
    |── 请求2 ──> 工作线程2 [查缓存→未命中→读磁盘→阻塞...] (慢，但不影响其他线程)
    |── 请求3 ──> 工作线程3 [查缓存→命中→返回] (快)
    |
    |── 更多请求进来... 从线程池取更多工作线程

单线程服务器：一个请求磁盘就阻塞，完全不响应其他请求。

场景三：流水线数据处理

处理大量数据的流水线：
[输入线程] ──读数据到输入缓冲──> [处理线程] ──结果到输出缓冲──> [输出线程]
三个线程同时推进，I/O 和计算重叠，整体吞吐量提升
（需要操作系统支持：阻塞系统调用只阻塞调用它的线程，不阻塞整个进程）

9. 线程的经典模型

9.1 进程 vs 线程的资源所有权

进程（资源容器）拥有：          线程（执行实体）拥有：
  地址空间                        程序计数器（PC）
  全局变量                        寄存器（工作变量）
  打开的文件                      栈（局部变量、调用历史）
  子进程                          状态（运行/就绪/阻塞）
  未处理的信号
  信号处理函数
  账户信息

同一进程的所有线程共享进程级资源，各自私有线程级资源。

9.2 三进程 vs 单进程三线程

方案A：3个独立进程（各自独立地址空间）
+--------+  +--------+  +--------+
|进程1   |  |进程2   |  |进程3   |
|  线程  |  |  线程  |  |  线程  |
|地址空间|  |地址空间|  |地址空间|
+--------+  +--------+  +--------+
适用于：三个不相关的任务，不需要共享数据
方案B：1个进程内3个线程（共享地址空间）
+----------------------------------+
|            进程                   |
|  +------+ +------+ +------+      |
|  |线程1 | |线程2 | |线程3 |      |
|  |自己的| |自己的| |自己的|      |
|  |栈    | |栈    | |栈    |      |
|  +------+ +------+ +------+      |
|                                   |
|     共享的地址空间（全局数据）     |
+----------------------------------+
适用于：三个紧密协作的任务，需要共享同一份数据

9.3 每个线程有自己的栈

进程内存布局（单进程三线程）：
地址高  +--------------+
        | 线程1的栈    | ← 线程1 的函数调用链
        +--------------+
        | 线程2的栈    | ← 线程2 的函数调用链（独立！）
        +--------------+
        | 线程3的栈    | ← 线程3 的函数调用链（独立！）
        +--------------+
        | 共享的堆     | ← malloc 分配的内存，所有线程可访问
        | 共享的数据段 | ← 全局变量，所有线程可访问
        | 共享的代码段 | ← 程序代码（只读），所有线程共享
地址低  +--------------+

每个线程都可能调用不同的函数序列，因此必须有自己的栈来保存各自的局部变量和返回地址。

10. POSIX 线程（Pthreads）

IEEE 标准 1003.1c 定义了可移植线程接口，称为 Pthreads，UNIX/Linux 普遍支持。

10.1 常用 Pthreads 函数

函数	作用
`pthread_create`	创建新线程
`pthread_exit`	终止当前线程
`pthread_join`	等待指定线程结束
`pthread_yield`	主动让出 CPU
`pthread_attr_init`	初始化线程属性结构
`pthread_attr_destroy`	销毁线程属性结构

10.2 完整可运行的 Pthreads 示例

/* Pthreads 完整演示：创建多个线程，展示并发执行 */
/* 编译：gcc -o pthread_demo pthread_demo.c -lpthread */
/* （必须链接 pthread 库，加上 -lpthread）*/
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>   /* Pthreads 头文件 */
#include <unistd.h>    /* sleep() */
#define NUMBER_OF_THREADS 5
/* 线程函数：每个线程都执行这个函数
 * 参数是 void* 类型，可以传任意数据（这里传线程编号）
 * 返回值也是 void*（通常不用）
 */
void *print_hello_world(void *tid) {
    long thread_id = (long)tid; /* 把 void* 转回整数 */
    printf("线程 %ld 开始运行\n", thread_id);
    /* 模拟工作：睡眠一段时间 */
    sleep(1);
    printf("线程 %ld 完成工作，即将退出\n", thread_id);
    /* pthread_exit 终止当前线程，参数是返回值（可以被 pthread_join 获取）*/
    pthread_exit(NULL);
    /* 也可以直接 return NULL; 效果相同 */
}
int main(void) {
    pthread_t threads[NUMBER_OF_THREADS]; /* 存放线程标识符的数组 */
    int status;
    long i;
    printf("主线程开始，将创建 %d 个子线程\n", NUMBER_OF_THREADS);
    for (i = 0; i < NUMBER_OF_THREADS; i++) {
        printf("主线程：正在创建线程 %ld\n", i);
        /* pthread_create 四个参数：
         * 1. 线程标识符的地址（输出参数，创建成功后填入）
         * 2. 线程属性（NULL=使用默认属性）
         * 3. 线程函数（函数指针）
         * 4. 传给线程函数的参数（void* 类型）
         * 返回0表示成功，非0表示失败
         */
        status = pthread_create(
            &threads[i],       /* 输出：新线程的ID */
            NULL,              /* 属性：默认 */
            print_hello_world, /* 线程函数 */
            (void *)i          /* 传入线程编号作为参数 */
        );
        if (status != 0) {
            fprintf(stderr, "创建线程 %ld 失败，错误码 %d\n", i, status);
            exit(1);
        }
    }
    printf("主线程：所有线程已创建，等待它们完成...\n");
    /* 等待所有线程完成 */
    for (i = 0; i < NUMBER_OF_THREADS; i++) {
        /* pthread_join 两个参数：
         * 1. 要等待的线程ID
         * 2. 存放线程返回值的地址（NULL=不关心返回值）
         * 阻塞调用者，直到指定线程退出
         */
        status = pthread_join(threads[i], NULL);
        if (status != 0) {
            fprintf(stderr, "等待线程 %ld 失败\n", i);
        }
    }
    printf("主线程：所有线程已完成，程序退出\n");
    return 0;
}
/* 可能的运行输出（顺序不确定，因为线程并发执行）：
主线程开始，将创建 5 个子线程
主线程：正在创建线程 0
主线程：正在创建线程 1
线程 0 开始运行
主线程：正在创建线程 2
线程 1 开始运行
线程 2 开始运行
主线程：正在创建线程 3
主线程：正在创建线程 4
线程 3 开始运行
线程 4 开始运行
主线程：所有线程已创建，等待它们完成...
线程 0 完成工作，即将退出
线程 2 完成工作，即将退出
线程 1 完成工作，即将退出
线程 3 完成工作，即将退出
线程 4 完成工作，即将退出
主线程：所有线程已完成，程序退出
*/

https://godbolt.org/z/TM5odYqd3

11. 用户级线程 vs 内核级线程

11.1 用户级线程（User-Level Threads）

内核不知道线程的存在，线程管理全在用户空间的运行时库里实现。

用户级线程结构：
+---------------------------------------+
|              用户空间                  |
|  +----------------------------------+ |
|  |           进程                   | |
|  |  线程1  线程2  线程3             | |
|  |    |      |      |              | |
|  |  +----------------------------+ | |
|  |  |     运行时库（调度器）     | | |
|  |  |  线程表（每个进程一张）    | | |
|  |  +----------------------------+ | |
|  +----------------------------------+ |
+---------------------------------------+
|              内核空间                  |
|    内核只看到进程，不知道线程存在       |
|    进程表（每个进程一项）               |
+---------------------------------------+

优点：

线程切换极快（不需要陷入内核，只是几条指令保存/恢复寄存器）
可以在不支持线程的 OS 上运行
每个进程可以有自定制的线程调度算法
缺点（严重）：

问题	说明
阻塞系统调用	一个线程调用 `read()` 阻塞，整个进程的所有线程都被阻塞
缺页中断	一个线程触发缺页，内核阻塞整个进程，所有线程暂停
没有时钟中断	线程间没有强制切换，一个线程不主动让出 CPU，其他线程永远等待
不能利用多核	同一进程的所有线程映射到一个内核进程，只能用一个CPU核

11.2 内核级线程（Kernel-Level Threads）

内核知道每个线程，线程表在内核中，所有线程操作都是系统调用。

内核级线程结构：
+---------------------------------------+
|              用户空间                  |
|  进程A                进程B           |
|  线程1 线程2 线程3    线程4 线程5     |
+---------------------------------------+
|              内核空间                  |
|  内核线程表（所有线程都在这里）        |
|  进程表                               |
|  调度器（直接调度内核线程）           |
+---------------------------------------+

优点：

一个线程阻塞，内核可以调度同进程的其他线程
真正利用多核并行
缺页中断不影响其他线程
缺点：
创建/销毁/切换线程需要系统调用，开销比用户级线程大 10~100 倍
线程频繁创建时开销显著（部分系统用"线程池/线程复用"缓解）

11.3 对比总结

对比项	用户级线程	内核级线程
内核感知	否	是
切换速度	极快（用户态）	较慢（需系统调用）
阻塞系统调用	阻塞整个进程	只阻塞该线程
多核并行	不能（受限于单进程）	能
线程管理	用户空间运行时库	内核
典型实现	早期 POSIX 线程	Linux NPTL, Windows线程

12. 混合实现

将两者结合：内核提供若干内核线程，用户再在每个内核线程上多路复用多个用户线程。

混合实现结构：
用户线程：  U1 U2 U3    U4 U5    U6
              \  |  /    |  |      |
               \ | /     | /       |
内核线程：     KT1        KT2      KT3
内核只调度 KT1、KT2、KT3
用户运行时库决定 U1/U2/U3 轮流在 KT1 上运行
程序员可以调节内核线程数和用户线程数

这种模型在灵活性和性能之间取得平衡，现代系统（如 Go 语言的 goroutine）使用类似思想。

13. 单线程代码改为多线程的陷阱

13.1 全局变量冲突（errno 问题）

UNIX 系统中，errno 是一个全局变量，用于保存上一次系统调用的错误码。多线程时：

时间线：
线程1：access("file")  →  errno 被设置为 EACCES (13)
                          线程1还没来得及读 errno
调度器：切换到线程2
线程2：open("other")   →  errno 被覆盖为 ENOENT (2)
调度器：切回线程1
线程1：读 errno  →  读到 ENOENT，但这是线程2的错误！线程1行为错乱！

解决方案：线程本地存储（Thread-Local Storage，TLS）。每个线程有自己私有的 errno 副本：

/* 线程本地存储演示 */
/* 编译：gcc -o tls_demo tls_demo.c -lpthread */
#include <stdio.h>
#include <pthread.h>
/* __thread 关键字（GCC扩展）声明线程局部变量
 * 每个线程各有一份独立副本，互不干扰 */
__thread int thread_local_errno = 0;
/* 模拟系统调用，设置线程自己的errno */
void simulated_syscall(int thread_id, int error_code) {
    thread_local_errno = error_code;
    printf("线程 %d 设置 errno = %d\n", thread_id, error_code);
}
void *thread_func(void *arg) {
    int tid = (int)(long)arg;
    /* 模拟系统调用失败，设置错误码 */
    simulated_syscall(tid, tid * 10); /* 每个线程设置不同的值 */
    /* 短暂让出CPU，让其他线程有机会修改（但不会影响我们的副本）*/
    pthread_yield();
    /* 读取时仍然是自己的值，不受其他线程影响 */
    printf("线程 %d 读到 errno = %d（应为 %d）\n",
           tid, thread_local_errno, tid * 10);
    return NULL;
}
int main(void) {
    pthread_t t1, t2, t3;
    pthread_create(&t1, NULL, thread_func, (void*)1L);
    pthread_create(&t2, NULL, thread_func, (void*)2L);
    pthread_create(&t3, NULL, thread_func, (void*)3L);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_join(t3, NULL);
    return 0;
}
/* 每个线程读到自己设置的值，互不干扰 */

https://godbolt.org/z/oxv4fzaKK

13.2 库函数不可重入（Non-Reentrant）

很多库函数使用静态内部缓冲区，不能被多个线程同时调用：

问题场景（malloc 的内部链表）：
线程1 开始执行 malloc(100)
  → malloc 正在更新空闲链表（链表处于不一致状态）
  ← 调度器切换到线程2
线程2 也调用 malloc(50)
  → malloc 看到破损的链表，指针无效
  → 程序崩溃！

解决方案：使用互斥锁保护共享数据（第2章后续内容：互斥量 Mutex）。

13.3 信号的复杂性

信号是发给进程的，不是线程
多线程时，操作系统随机选一个线程来处理信号
如果多个线程注册了同一信号的处理函数，行为可能不可预期

13.4 栈溢出问题

单线程时，内核会自动检测栈溢出并增长栈空间
多线程时，每个线程的栈是提前分配好的固定大小区域
一个线程栈溢出时，内核不知道这是线程栈，无法自动增长
可能覆盖相邻线程的栈，导致难以调试的数据损坏

总结：进程 vs 线程快速对比

特性	进程	线程
地址空间	独立	共享（同进程内）
全局变量	不共享	共享
打开的文件	不共享（复制）	共享
子进程	不共享	共享
创建开销	大（ms级）	小（μs级）
切换开销	大	小
通信方式	IPC（管道、套接字等）	直接读写共享内存
故障隔离	强（进程间隔离）	弱（线程共享地址空间）
多核利用	好	好（内核线程）

CPU 利用率计算练习

已知： $p = 0.8$ （I/O等待比例），计算不同进程数下的 CPU 利用率：
$\text{CPU利用率} = 1 - p^n = 1 - 0.8^n$

$n$	$0.8^n$	CPU利用率
1	$0.800$	$20\%$
2	$0.640$	$36\%$
3	$0.512$	$48.8\%$
5	$0.328$	$67.2\%$
10	$0.107$	$89.3\%$
20	$0.0115$	$98.8\%$

图形理解（ASCII 折线图）：

CPU
利 100% |                          .........
用  90% |                   .......
率  80% |             .......
    70% |         ....
    60% |       ..
    50% |      .
    40% |    ..
    30% |  ..
    20% |..
    10% |
     0% +--+--+--+--+--+--+--+--+--+--+-- n
        1  2  3  4  5  6  7  8  9  10
                                (I/O等待=80%)

操作系统第二章：进程与线程

2.3 事件驱动服务器（Event-Driven Servers）

三种服务器模型对比

在设计 Web 服务器时，有三种典型方案：

多线程服务器        单线程服务器        事件驱动服务器
  (快, 复杂)          (慢, 简单)         (快, 中等复杂)

当线程不可用或不希望使用线程，但单线程性能又太差时，可以使用事件驱动模型（前提是系统支持非阻塞系统调用）。

事件驱动服务器工作原理

核心思想：不等待，遇到需要等待的操作就先记录状态，去处理其他请求。

请求到来
   |
   v
检查缓存命中?
   |         \
  是          否
   |           \
直接返回     发起非阻塞磁盘 I/O
             记录请求状态到表中
             去处理下一个事件

服务器维护一张状态表，每次切换请求时保存当前计算状态，下次收到磁盘回复时再恢复继续处理。
这种设计本质上是用软件手动模拟了线程和调用栈——即有限状态机（Finite-State Machine, FSM）。

事件驱动"感谢服务器"伪代码详解

下面是教材中的伪代码，已加入详细中文注释：

/*
 * 事件驱动的"感谢服务器"
 * 功能：收到客户端消息后，回复 "Thank you!"
 * 核心：使用 select() 同时监听多个连接，不阻塞在任何一个上
 */
/* 预备变量 */
// svrSock  : 服务器主套接字，绑定到 TCP 12345 端口
// toSend   : 数据库，追踪还需要向哪个 fd 发送什么数据
//   toSend.put(fd, msg)     -- 登记需要在 fd 上发送 msg
//   toSend.get(fd)          -- 查询 fd 上待发送的字符串
//   toSend.destroy(fd)      -- 删除 fd 的所有信息
inFds    = {svrSock}  /* 监听"可读"的文件描述符集合（初始只有服务器套接字） */
outFds   = {}         /* 监听"可写"的文件描述符集合（初始为空） */
exceptFds= {}         /* 监听"异常"的文件描述符集合（本例不用） */
char msgBuf[MAXMSGSIZE]         /* 接收消息用的缓冲区 */
char *thankYouMsg = "Thank you!" /* 要回复的内容 */
while (TRUE)
{
    /*
     * select() 是关键：它会阻塞，直到 inFds/outFds 中至少有一个 fd 就绪
     * 返回三个集合：rdyIns（可读）、rdyOuts（可写）、rdyExcepts（异常）
     */
    rdyIns, rdyOuts, rdyExcepts = select(inFds, outFds, exceptFds, NO_TIMEOUT)
    /* ---- 处理所有可读事件 ---- */
    for (fd in rdyIns)
    {
        if (fd == svrSock)  /* 情况1：有新客户端连接 */
        {
            newSock = accept(svrSock)      /* 接受连接，生成新套接字 */
            inFds = inFds ∪ {newSock}     /* 把新套接字加入监听集合 */
        }
        else  /* 情况2：已有客户端发来了消息 */
        {
            n = receive(fd, msgBuf, MAXMSGSIZE)   /* 接收消息 */
            printf("Received: %s", msgBuf)
            toSend.put(fd, thankYouMsg)    /* 登记：需要向 fd 发送感谢语 */
            outFds = outFds ∪ {fd}        /* 把 fd 加入"可写"监听集合 */
        }
    }
    /* ---- 处理所有可写事件（发送感谢消息）---- */
    for (fd in rdyOuts)
    {
        msg = toSend.get(fd)               /* 查询还需要发什么 */
        n = send(fd, msg, strlen(msg))     /* 尝试发送 */
        if (n < strlen(thankYouMsg))
        {
            /* 没发完（缓冲区满），记录剩余部分，下次继续 */
            toSend.put(fd, msg + n)
        }
        else
        {
            /* 发送完毕 */
            toSend.destroy(fd)            /* 清除记录 */
            outFds = outFds \ {fd}        /* 从可写监听集合中移除 */
        }
    }
}

关键点：单线程却能同时服务多个客户端，因为它从不阻塞——遇到不能立刻完成的操作就记录状态、先做别的。

高性能 I/O 通知接口

操作系统	接口名
Linux	`epoll`
FreeBSD/macOS	`kqueue`
Windows	IOCP（完成端口）

这些接口比 select 效率高得多，是 nginx 等服务器支撑万级并发（C10k 问题）的基础。

三种服务器模型总结

模型	并行性	系统调用类型	编程难度
多线程	有	阻塞式	中等
单线程进程	无	阻塞式	简单
有限状态机/事件驱动	有	非阻塞+中断	较难

2.4 同步与进程间通信（IPC）

进程间通信有三个核心问题：

信息传递：一个进程如何把数据传给另一个进程
互斥：防止多个进程同时操作共享数据造成混乱
顺序协调：有依赖关系时保证正确的执行顺序

2.4.1 竞态条件（Race Conditions）

打印假脱机目录示例

共享变量：
  out = 4  （下一个要打印的文件编号）
  in  = 7  （下一个空槽位）
槽位状态：
  0,1,2,3 → 已打印，空闲
  4,5,6   → 等待打印（abc, prog.c, prog.n）
  7       → 下一个空槽

竞态发生过程（时间线）：

进程A                           进程B
  |                               |
读 in，得到 7，存入 next_free=7   |
  |                               |
  --- 时钟中断，切换到 B ---       |
                                读 in，得到 7，存入 next_free=7
                                将文件名写入槽位 7
                                将 in 更新为 8
  --- 切换回 A ---               |
将自己的文件名写入槽位 7（覆盖了B的文件名！）
将 in 更新为 8

后果：进程B的文件名被覆盖，永远不会被打印。
定义：两个或多个进程读写共享数据，最终结果依赖于它们精确的执行时序，称为竞态条件。

2.4.2 临界区（Critical Regions）

互斥（Mutual Exclusion）：保证同一时刻最多一个进程在访问共享数据。
访问共享数据的代码段称为临界区（Critical Region / Critical Section）。
一个好的临界区解决方案必须满足四个条件：

互斥性：任意时刻，最多一个进程在其临界区内
无假设：不对 CPU 速度和数量做任何假设
无外部阻塞：临界区外的进程不能阻塞其他进程进入临界区
有限等待：任何进程都不应该永远等待进入临界区

时序示意图（ASCII）

进程A ----[进入临界区]==========[离开临界区]------------>
                                    |
进程B --------[尝试进入,被阻塞]---[进入]====[离开]------->
              T2                   T3        T4
         T1（A进入）

2.4.3 忙等待实现互斥

方法一：关闭中断

/* 进入临界区前 */
disable_interrupts();
/* ... 临界区代码 ... */
/* 离开临界区后 */
enable_interrupts();

缺点：

用户程序有权关中断太危险（关了不开怎么办？）
多处理器上只能关闭当前 CPU 的中断，其他 CPU 照样运行
随着多核 CPU 普及，此方法越来越不适用
适用场景：操作系统内核内部，短暂禁用中断（几条指令内）。

方法二：锁变量（Lock Variable）

用一个共享变量 lock（初值 0）：

0 表示无进程在临界区
1 表示有进程在临界区
致命缺陷：与打印假脱机目录同样的问题——读和写之间可能被打断，导致两个进程同时进入临界区。

方法三：严格轮换（Strict Alternation）

/* 进程0的代码 */
while (TRUE) {
    while (turn != 0) {}  /* 忙等待，直到轮到自己 */
    critical_region();
    turn = 1;             /* 让给进程1 */
    noncritical_region();
}
/* 进程1的代码 */
while (TRUE) {
    while (turn != 1) {}  /* 忙等待，直到轮到自己 */
    critical_region();
    turn = 0;             /* 让给进程0 */
    noncritical_region();
}

缺陷：违反条件3。若进程1在非临界区很慢，进程0（即使临界区已空）也必须等待——被不在临界区的进程阻塞。

方法四：Peterson 算法

1981年荷兰数学家 Peterson 提出的软件解法：

#define FALSE 0
#define TRUE  1
#define N     2        /* 进程数量 */
int turn;              /* 轮到谁了 */
int interested[N];     /* 各进程是否感兴趣，初始全为 FALSE */
/*
 * 进入临界区
 * process: 当前进程编号（0 或 1）
 */
void enter_region(int process)
{
    int other = 1 - process;          /* 另一个进程的编号 */
    interested[process] = TRUE;       /* 声明自己想进入临界区 */
    turn = process;                   /* 把 turn 设为自己（礼让对方） */
    /*
     * 等待条件：turn 仍是自己 并且 对方也感兴趣
     * 若两个进程几乎同时调用，后写 turn 的那个会在此等待
     */
    while (turn == process && interested[other] == TRUE)
        ;  /* 忙等待 */
}
/*
 * 离开临界区
 * process: 当前进程编号
 */
void leave_region(int process)
{
    interested[process] = FALSE;      /* 声明自己不再需要临界区 */
}

工作原理：

若只有一个进程调用，直接进入（另一个 interested 为 FALSE，循环不执行）
若两个进程同时调用，turn 最后被哪个写入就是哪个等待，另一个立刻进入
满足全部四个条件

方法五：TSL 指令（Test and Set Lock）

硬件支持的原子指令，一条指令完成"读取并置1"，不可被打断：

; 汇编伪代码
enter_region:
    TSL  REGISTER, LOCK   ; 原子操作：把 LOCK 读入 REGISTER，同时把 LOCK 置 1
    CMP  REGISTER, #0     ; 判断 LOCK 原来是否为 0（即是否空闲）
    JNE  enter_region     ; 若非 0（已被锁），跳回继续等待
    RET                   ; 若为 0，成功获取锁，返回
leave_region:
    MOVE LOCK, #0         ; 释放锁（直接写 0 即可）
    RET

类似的还有 XCHG 指令（原子交换，x86 CPU 使用此指令）：

enter_region:
    MOVE REGISTER, #1     ; 寄存器 = 1
    XCHG REGISTER, LOCK   ; 原子交换：REGISTER 和 LOCK 互换内容
    CMP  REGISTER, #0     ; 如果交换前 LOCK 是 0，说明锁空闲
    JNE  enter_region     ; 否则继续等待
    RET
leave_region:
    MOVE LOCK, #0
    RET

忙等待的问题——优先级反转（Priority Inversion）：

场景：H（高优先级）、L（低优先级）
1. L 进入临界区
2. H 变为就绪态，抢占 CPU（因为优先级更高）
3. H 忙等待 L 释放锁，但 L 永远无法运行（CPU 一直被 H 占着）
4. 死循环！

2.4.4 睡眠与唤醒（Sleep & Wakeup）

忙等待浪费 CPU，改用阻塞原语：

sleep()：让调用者阻塞，直到被唤醒
wakeup(pid)：唤醒指定进程

生产者-消费者问题（有缺陷版本）

#define N 100          /* 缓冲区大小 */
int count = 0;         /* 缓冲区中的物品数 */
void producer(void)
{
    int item;
    while (TRUE) {
        item = produce_item();
        if (count == N) sleep();    /* 缓冲区满，睡眠 */
        insert_item(item);
        count++;
        if (count == 1) wakeup(consumer); /* 刚放入第一个，唤醒消费者 */
    }
}
void consumer(void)
{
    int item;
    while (TRUE) {
        if (count == 0) sleep();    /* 缓冲区空，睡眠 */
        item = remove_item();
        count--;
        if (count == N - 1) wakeup(producer); /* 刚腾出空间，唤醒生产者 */
        consume_item(item);
    }
}

致命竞态：

1. 消费者读 count=0，准备 sleep()
2. 调度器切换到生产者
3. 生产者放入物品，count=1，调用 wakeup(消费者)
   → 但消费者还没睡着，wakeup 信号丢失！
4. 消费者恢复运行，执行 sleep()，永远睡下去
5. 生产者填满缓冲区后也睡下去
6. 双方永远阻塞 = 死锁

2.4.5 信号量（Semaphores）

1965年 Dijkstra 提出：用一个整数变量保存"待用的唤醒次数"。
两个原子操作：

down（P操作）：若值 > 0，减1继续；若值 = 0，进程睡眠
up（V操作）：值加1；若有进程在睡眠，唤醒其中一个
两个操作都是原子的（不可中断）。

用信号量解决生产者-消费者问题

#define N 100
typedef int semaphore;
/*
 * 三个信号量：
 *   mutex : 互斥锁，保证同时只有一个进程访问缓冲区（初值 1）
 *   empty : 空槽数量（初值 N，表示全空）
 *   full  : 满槽数量（初值 0，表示没有物品）
 */
semaphore mutex = 1;
semaphore empty = N;
semaphore full  = 0;
void producer(void)
{
    int item;
    while (TRUE) {
        item = produce_item();
        down(&empty);        /* 空槽数减1；若为0则等待（缓冲区满） */
        down(&mutex);        /* 加互斥锁，进入临界区 */
        insert_item(item);   /* 放入物品 */
        up(&mutex);          /* 释放互斥锁，离开临界区 */
        up(&full);           /* 满槽数加1；若有消费者在等待，唤醒它 */
    }
}
void consumer(void)
{
    int item;
    while (TRUE) {
        down(&full);         /* 满槽数减1；若为0则等待（缓冲区空） */
        down(&mutex);        /* 加互斥锁，进入临界区 */
        item = remove_item();/* 取出物品 */
        up(&mutex);          /* 释放互斥锁，离开临界区 */
        up(&empty);          /* 空槽数加1；若有生产者在等待，唤醒它 */
        consume_item(item);
    }
}

注意顺序：down(&empty) / down(&full) 必须在 down(&mutex) 之前，否则会死锁！

若顺序颠倒（先加互斥锁再检查 empty/full），缓冲区满时生产者持有 mutex 睡眠，消费者无法获取 mutex 也睡眠 → 死锁。
信号量的两种用途：

mutex：用于互斥（保护临界区）
empty / full：用于同步（保证正确的事件顺序）

读者-写者问题

多个进程共享数据库：

多个读者可以同时读
写者必须独占访问（写时无读者也无其他写者）

typedef int semaphore;
semaphore mutex = 1;  /* 保护 rc（读者计数器） */
semaphore db    = 1;  /* 保护数据库访问 */
int rc = 0;           /* 当前正在读的进程数 */
void reader(void)
{
    while (TRUE) {
        down(&mutex);          /* 准备修改 rc，加锁 */
        rc++;
        if (rc == 1)           /* 第一个读者：锁住数据库，阻止写者 */
            down(&db);
        up(&mutex);            /* 释放 rc 的锁 */
        read_database();       /* 读数据 */
        down(&mutex);          /* 准备修改 rc，加锁 */
        rc--;
        if (rc == 0)           /* 最后一个读者：释放数据库锁 */
            up(&db);
        up(&mutex);
        use_data_read();
    }
}
void writer(void)
{
    while (TRUE) {
        think_up_data();
        down(&db);             /* 独占数据库 */
        write_database();
        up(&db);               /* 释放数据库 */
    }
}

问题：只要持续有读者到来，写者可能永远等待（读者优先策略）。改进方案：写者到来后，新读者需排在写者之后。

2.4.6 互斥量（Mutex）

信号量的简化版，只有加锁和解锁两个状态（0=未锁，非0=已锁）。

; 用 TSL 实现的 mutex_lock / mutex_unlock（用户空间线程库）
mutex_lock:
    TSL    REGISTER, MUTEX   ; 原子读取并置1
    CMP    REGISTER, #0      ; 锁原来是否空闲？
    JZE    ok                ; 是 → 成功获得锁，返回
    CALL   thread_yield      ; 否 → 主动让出 CPU（不忙等待！）
    JMP    mutex_lock        ; 再次尝试
ok:
    RET
mutex_unlock:
    MOVE   MUTEX, #0         ; 直接清零释放锁
    RET

与 enter_region（忙等待）的关键区别：失败时调用 thread_yield 主动让出 CPU，避免了死循环占用 CPU。

Futex（Fast Userspace Mutex）

Linux 特有机制，结合了自旋锁和内核等待队列的优点：

无竞争时：         完全在用户空间操作（原子自减），不进入内核
有竞争时：         陷入内核，排入等待队列，等待被唤醒
锁释放时：         原子自增；若有等待者，通知内核唤醒

目标：竞争少时快（不切换内核），竞争多时省 CPU（不忙等待）。

Pthreads 互斥量 API

函数	说明
`pthread_mutex_init`	创建互斥量
`pthread_mutex_destroy`	销毁互斥量
`pthread_mutex_lock`	加锁（阻塞等待）
`pthread_mutex_trylock`	尝试加锁（失败立即返回错误码）
`pthread_mutex_unlock`	解锁

条件变量（Condition Variables）

互斥量解决"能不能进入"，条件变量解决"要不要等待某个条件"：

函数	说明
`pthread_cond_init`	创建条件变量
`pthread_cond_destroy`	销毁条件变量
`pthread_cond_wait`	等待信号（自动释放互斥量）
`pthread_cond_signal`	唤醒一个等待者
`pthread_cond_broadcast`	唤醒所有等待者

使用模式（生产者-消费者，Pthreads版）：

#include <stdio.h>
#include <pthread.h>
#define MAX 1000000000  /* 生产数量上限 */
pthread_mutex_t the_mutex;     /* 互斥量 */
pthread_cond_t  condc, condp;  /* 消费者等待条件、生产者等待条件 */
int buffer = 0;                /* 单物品缓冲区（0表示空） */
/* 生产者线程 */
void *producer(void *ptr)
{
    int i;
    for (i = 1; i <= MAX; i++) {
        pthread_mutex_lock(&the_mutex);    /* 加锁 */
        /* 缓冲区不为空就等待（while防止虚假唤醒） */
        while (buffer != 0)
            pthread_cond_wait(&condp, &the_mutex);
        buffer = i;                        /* 生产一个物品 */
        pthread_cond_signal(&condc);       /* 唤醒消费者 */
        pthread_mutex_unlock(&the_mutex);  /* 解锁 */
    }
    pthread_exit(0);
}
/* 消费者线程 */
void *consumer(void *ptr)
{
    int i;
    for (i = 1; i <= MAX; i++) {
        pthread_mutex_lock(&the_mutex);    /* 加锁 */
        /* 缓冲区为空就等待 */
        while (buffer == 0)
            pthread_cond_wait(&condc, &the_mutex);
        buffer = 0;                        /* 消费物品（清空缓冲区） */
        pthread_cond_signal(&condp);       /* 唤醒生产者 */
        pthread_mutex_unlock(&the_mutex);  /* 解锁 */
    }
    pthread_exit(0);
}
int main(void)
{
    pthread_t pro, con;
    pthread_mutex_init(&the_mutex, 0);
    pthread_cond_init(&condc, 0);
    pthread_cond_init(&condp, 0);
    pthread_create(&con, 0, consumer, 0);  /* 创建消费者线程 */
    pthread_create(&pro, 0, producer, 0);  /* 创建生产者线程 */
    pthread_join(pro, 0);                  /* 等待生产者结束 */
    pthread_join(con, 0);                  /* 等待消费者结束 */
    pthread_cond_destroy(&condc);
    pthread_cond_destroy(&condp);
    pthread_mutex_destroy(&the_mutex);
    return 0;
}

https://godbolt.org/z/hcGrjrWsv
注意：条件变量没有"记忆"——若 signal 发出时没有等待者，信号丢失，不像信号量会累积。

2.4.7 管程（Monitors）

信号量虽然强大，但容易出错（比如交换两个 down 的顺序就可能死锁）。
管程是更高级的同步原语：将共享变量、操作它们的过程，打包进一个特殊的模块，由编译器保证互斥。
特性：任何时刻最多一个进程在管程内活跃（编译器自动实现，无需程序员手动加锁）。

monitor ProducerConsumer
    condition full, empty;  /* 条件变量 */
    integer count;          /* 缓冲区物品数 */
    procedure insert(item):
        if count = N then wait(full)   /* 满了就等 */
        insert_item(item)
        count++
        if count = 1 then signal(empty) /* 通知消费者 */
    function remove():
        if count = 0 then wait(empty)  /* 空了就等 */
        remove = remove_item()
        count--
        if count = N-1 then signal(full) /* 通知生产者 */
    count = 0
end monitor

管程中的 wait/signal 与 sleep/wakeup 的关键区别：

管程的互斥性保证 wait 执行时不会被调度器打断 → 不存在"唤醒丢失"的竞态
Java 中的管程：用 synchronized 关键字修饰方法，Java 保证同一时刻只有一个线程执行该对象的同步方法。
管程的局限：
只能用于支持管程的编程语言（C 不支持）
只适用于共享内存的系统，不适用于分布式系统

2.4.8 消息传递（Message Passing）

两个原语：

send(destination, &message);    /* 发送消息到目标 */
receive(source, &message);      /* 从来源接收消息 */

设计问题：

消息丢失 → 接收方发回确认（ACK），超时重传
重复消息 → 消息编号，接收方忽略重复序号
命名问题 → 进程地址或邮箱（Mailbox）

消息传递解决生产者-消费者

#define N 100  /* 消息（缓冲槽）数量 */
void producer(void)
{
    int item;
    message m;
    while (TRUE) {
        item = produce_item();
        receive(consumer, &m);       /* 等待空消息（等消费者给"空槽"） */
        build_message(&m, item);     /* 将物品打包进消息 */
        send(consumer, &m);          /* 发送满消息给消费者 */
    }
}
void consumer(void)
{
    int item, i;
    message m;
    /* 初始化：发送 N 个空消息给生产者（表示 N 个空槽） */
    for (i = 0; i < N; i++) send(producer, &m);
    while (TRUE) {
        receive(producer, &m);       /* 等待满消息 */
        item = extract_item(&m);     /* 从消息中取出物品 */
        send(producer, &m);          /* 发回空消息（归还空槽） */
        consume_item(item);
    }
}

系统中消息总数恒为 N，满消息和空消息此消彼长，天然控制流量。
集会（Rendezvous）：无缓冲消息传递，发送方阻塞直到接收方准备好，强制同步执行。

2.4.9 屏障（Barriers）

用于一组进程的阶段同步：所有进程都到达屏障后，才能全部继续。

阶段 1 计算              屏障              阶段 2 计算
进程A =========>          |
进程B ==========>         |  所有到达后
进程C ============>       |  同时放行       ---------> 继续
进程D ===========>        |

应用场景：大规模矩阵迭代计算（物理模拟），每次迭代必须等所有进程完成上一次才能开始下一次。
内存屏障（Memory Barrier / Memory Fence）：
防止 CPU 乱序执行（Out-of-Order Execution）导致的问题：

/* 问题示例（可能因乱序执行打印旧的 x 值）*/
/* 线程1 */                   /* 线程2 */
while (turn != 1) {}          x = 100;
printf("%d\n", x);            turn = 1;
                              /* CPU 可能先执行 turn=1，再执行 x=100 */

在赋值语句之间插入内存屏障指令，强制其按序完成。

2.4.10 优先级反转（Priority Inversion）

火星探路者号（1997年）真实案例：

解决方案：

方法	说明
禁用中断	临界区内关中断，不适合用户程序
优先级天花板（Priority Ceiling）	给互斥锁赋予优先级，持锁者继承该优先级
优先级继承（Priority Inheritance）	低优先级进程持锁时，继承高优先级进程的优先级
随机提升（Windows）	随机给持锁线程提升优先级直到退出临界区

火星探路者号最终使用优先级继承方案修复。

2.4.11 无锁：读-拷贝-更新（RCU）

最快的锁是没有锁。RCU（Read-Copy-Update）允许读写并发进行（无锁），前提是每个读者看到的是完整的旧版本或新版本，而非两者混合。

树节点操作示意

核心思想：

插入：先完整初始化新节点，再用一次原子写入把它接入树，读者永远看到完整状态
删除：先更新指针让新读者看不到旧节点，等所有旧读者离开后，再释放内存
宽限期（Grace Period）：等待所有线程都经历一次上下文切换，确保旧引用不再存在
RCU 应用：Linux 内核广泛使用（网络栈、文件系统、内存管理等），适合读多写少的场景。

2.5 调度（Scheduling）

当多个进程/线程争用 CPU 时，调度器（Scheduler）决定谁先运行，使用的算法称为调度算法。

2.5.1 调度基础

进程的两类行为

CPU 密集型进程（CPU-bound）：
  [长时间计算][短暂I/O][长时间计算][短暂I/O] ...
I/O 密集型进程（I/O-bound）：
  [短计算][长I/O等待][短计算][长I/O等待] ...

随着 CPU 越来越快，进程越来越倾向于 I/O 密集型。

何时调度

创建新进程时（父进程 or 子进程先跑？）
进程退出时
进程因 I/O、信号量等阻塞时
I/O 中断发生时

抢占式 vs 非抢占式

非抢占式：进程一旦获得 CPU，运行到阻塞或主动放弃为止
抢占式：进程运行最多一个时间片，超时强制切换

各类系统调度目标

场景	目标
所有系统	公平性、策略执行、系统均衡
批处理系统	吞吐量最大、周转时间最短、CPU 利用率高
交互式系统	响应时间短、符合用户预期
实时系统	满足截止时间、行为可预测

2.5.2 批处理系统调度算法

先来先服务（FCFS / First-Come, First-Served）

最简单的非抢占式算法，按请求顺序执行。
缺点：一个长 CPU 密集型作业会拖慢所有 I/O 密集型作业。

最短作业优先（SJF / Shortest Job First）

在所有作业同时就绪的情况下，最优的非抢占算法。
示例：4 个作业，运行时间 8、4、4、4 分钟

ABCD顺序：A(8) + B(12) + C(16) + D(20) → 平均 14 分钟
BCDA顺序：B(4) + C(8)  + D(12) + A(20) → 平均 11 分钟  ← 更优

证明：设运行时间为 $\leq b \leq c \leq d$ ，平均周转时间为：
$\bar{T} = \frac{4a + 3b + 2c + d}{4}$
$a$ 系数最大，所以最短的作业要放第一个。
局限：只有所有作业同时可用时才最优；需要提前知道运行时间。

最短剩余时间优先（SRTN）

SJF 的抢占版：新作业到来时，若其剩余时间比当前进程的剩余时间短，则抢占。

2.5.3 交互式系统调度算法

轮转调度（Round-Robin）

每个进程分配一个时间片（quantum），用完后排到队列末尾。

队列：[B] [F] [D] [G] [A]
         ↑当前运行
B用完时间片后：
队列：[F] [D] [G] [A] [B]
         ↑当前运行

时间片长度的权衡：

时间片太短	时间片太长
上下文切换开销大（CPU效率低）	短请求响应慢

经验值：20～50 毫秒是合理的折中。
设上下文切换耗时 $s$ ，时间片长度 $q$ ，CPU 利用率为：
$\text{CPU利用率} = \frac{q}{q + s}$

优先级调度（Priority Scheduling）

每个进程有一个优先级，优先级高的先运行。

优先级4队列：[进程P1] [进程P2]  ← 总是先运行这里
优先级3队列：[进程P3]
优先级2队列：[进程P4] [进程P5]
优先级1队列：[进程P6]           ← 最后运行

防止高优先级进程长期占用：每个时钟 tick 降低其优先级，或限制最大时间片。
动态优先级：I/O 密集型进程优先级设为 $\frac{1}{f}$ （ $f$ 为上次时间片的使用比例），I/O 密集型进程总能快速获得 CPU。

多级队列（CTSS 方案）

最高优先级：分配 1 个时间片
次高优先级：分配 2 个时间片
再次：分配 4 个时间片（以此类推）
每当进程用完所有分配时间片，下移一级。CPU 密集型进程逐渐沉到低优先级，减少切换次数；交互型进程（经常让出 CPU）保持高优先级。

最短进程优先（Shortest Process Next）

为交互系统估计每次命令的执行时间，用**老化（Aging）**技术：
$T_{est} = \alpha T_0 + (1-\alpha) T_1$
即加权平均历史运行时间和最新运行时间， $\alpha$ 控制遗忘速度。
以 $\alpha = \frac{1}{2}$ 为例，若历史运行时间序列为 $T_0, T_1, T_2, T_3$ ，当前估计为：
$T_{est} = \frac{T_0}{8} + \frac{T_1}{8} + \frac{T_2}{4} + \frac{T_3}{2}$

保证调度（Guaranteed Scheduling）

向每个用户承诺：若有 $n$ 个用户（或进程），每人得到 $\frac{1}{n}$ 的 CPU 时间。
跟踪实际CPU时间/应得CPU时间的比值，始终运行比值最小的进程。
Linux 的 CFS（完全公平调度） 就是此思想的实现，用红黑树按"已消耗运行时间"排序，每次选最左节点（消耗最少的）运行。

彩票调度（Lottery Scheduling）

给进程分发彩票，每次随机抽一张，中签的进程运行。

重要进程拿更多彩票
占 $f$ 比例彩票的进程，长期得到 $f$ 比例的 CPU
新进程立刻参与竞争（高响应性）
合作进程可以转让彩票

公平分享调度（Fair-Share Scheduling）

按用户而非进程分配 CPU，防止某用户开多个进程就多占资源。

2.5.4 实时系统调度

可调度性判断：设有 $m$ 个周期事件，事件 $i$ 的周期为 $P_i$ ，每次需要 $C_i$ 秒 CPU 时间，系统可调度的条件是：
$\sum_{i=1}^{m} \frac{C_i}{P_i} \leq 1$
示例：三个事件，周期 100ms、200ms、500ms，CPU 需求 50ms、30ms、100ms：
$\frac{50}{100} + \frac{30}{200} + \frac{100}{500} = 0.5 + 0.15 + 0.2 = 0.85 < 1 \quad \checkmark \text{（可调度）}$

2.5.5 策略与机制分离

原则：调度机制（如优先级调度算法）在内核，调度策略（如优先级数值）可由用户进程通过系统调用设置。
父进程最了解自己子进程的重要程度，应该允许父进程告诉内核如何调度它的子进程。

2.5.6 线程调度

用户级线程

内核不知道线程的存在，只调度进程：

进程内的线程切换很快（几条指令）
一个线程阻塞在 I/O → 整个进程都阻塞
不能真正并行（即使多核，一个进程同时只能跑一个线程）

可能的执行顺序：A1 A2 A3 A1 A2 A3 ...
不可能出现：    A1 B1 A2 B2 ...（A、B是不同进程的线程）

内核级线程

内核直接调度线程：

一个线程阻塞不影响同进程其他线程
切换开销大（完整上下文切换）
可以真正跨核并行

可能：A1 B1 A2 B2 A3 B3 ...（来自不同进程的线程交替）

对比

特性	用户级线程	内核级线程
切换开销	极小（纳秒级）	大（需切换内存映射和缓存）
一个线程阻塞	整个进程阻塞	只阻塞该线程
并行能力	无（单进程单CPU）	有（多核）
应用感知调度	可以（运行时系统定制）	不行（内核不知应用语义）

重要概念速查

概念	核心思想
竞态条件	结果依赖于进程执行的精确时序
临界区	访问共享数据的代码段
互斥	保证同时只有一个进程在临界区
信号量	计数型同步原语，down/up 操作原子
互斥量	二值信号量，专用于互斥
管程	语言级互斥，编译器保证，更安全
消息传递	send/receive，适用于分布式系统
屏障	一组进程的阶段同步点
优先级反转	低优先级进程间接阻塞高优先级进程
RCU	无锁并发读写，解耦删除与回收
轮转调度	公平，时间片轮流
SJF	最优平均周转时间（需知道运行时间）
彩票调度	概率性，简单且响应快
CFS	Linux 完全公平调度，红黑树实现

openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

Linux 基本指令详解

操作系统是一款专门进行软硬件资源 “管理”的软件系统，它通过对下层硬件资源的高效管理和调度，为上层应用程序提供稳定、统一的运行环境。操作系统本质上是一个"管理者"，负责协调和管理计算机系统中的所有硬件和软件资源。

openEuler 社区

超算中心海光异构卡dcu bw 64G显卡报错无法通过设置来解决的办法，通过新增服务器跳过显卡

【代码】超算中心海光异构卡dcu bw 64G显卡报错无法通过设置来解决的办法，通过新增服务器跳过显卡。

openEuler 社区

【深度思考】Agent 架构的底层真相：从进程模型到调度器，我们正在用自然语言重写一遍操作系统（附3个预测）

openEuler 社区

所有评论(0)

查看更多评论

虾球xz

@TM1695648164

已为社区贡献14条内容

Modern Operating Systems 第五版学习:操作系统 第一章

虾球xz

目录

1. 什么是操作系统

1.1 基本概念

1.2 内核模式 vs 用户模式

计算机通常有两种运行模式：

2. 操作系统的两大功能

2.1 功能一：提供抽象（自顶向下视角）

2.2 功能二：资源管理（自底向上视角）

时分复用（Time Multiplexing）

空分复用（Space Multiplexing）

3. 操作系统的发展历史

3.1 第一代（1945–1955）：真空管

3.2 第二代（1955–1965）：晶体管与批处理系统

3.3 第三代（1965–1980）：集成电路与多道程序设计

IBM System/360 的贡献

多道程序设计（Multiprogramming）

假脱机（Spooling）

分时系统（Time-Sharing）

MULTICS 与 UNIX 的诞生

3.4 第四代（1980–至今）：个人计算机

3.5 第五代（1990–至今）：移动设备

4. 计算机硬件基础

4.1 处理器（CPU）

CPU 中的重要寄存器

流水线（Pipeline）

超标量（Superscalar）CPU

多核与多线程

4.2 内存层次结构

缓存工作原理

虚拟内存（Virtual Memory）

4.3 非易失存储

4.4 I/O 设备与中断

I/O 的三种方式

4.5 总线结构

USB（通用串行总线）演进

4.6 计算机启动过程

旧式 BIOS 启动流程

新式 UEFI 启动

UEFI（Unified Extensible Firmware Interface）改进了旧式BIOS：

5. 操作系统的种类

各类操作系统特点对比

实时系统详解

总结：核心概念速查

操作系统 第一章笔记（下）

目录

1. 操作系统的核心概念

1.1 进程（Process）

1.2 地址空间（Address Space）

1.3 文件（File）

1.4 Shell（命令解释器）

1.5 “个体发育重演系统发育”

作者借用生物学概念说明：每一代新型计算机（大型机→小型机→个人电脑→嵌入式→智能卡）都会重演前辈走过的路——从汇编语言编程开始，逐渐发展出高级语言、保护机制、文件系统、虚拟内存……

2. 系统调用详解

2.1 系统调用执行的完整流程

2.2 POSIX 主要系统调用

进程管理

文件管理

目录管理

权限保护

UNIX 与 Windows API 对比

3. 操作系统的内部结构

3.1 整体式结构（Monolithic / 宏内核）

3.2 分层结构（Layered）

3.3 微内核（Microkernel）

3.4 客户端-服务器模型（Client-Server）

3.5 虚拟机（Virtual Machine）

容器（Container）vs 虚拟机：

3.6 外核（Exokernel）与单内核（Unikernel）

4. C语言与操作系统开发

4.1 C 语言的关键特性

操作系统为什么用 C 而不是 Java/Python？

4.2 头文件与预处理

4.3 大型项目的编译流程

4.4 进程的内存布局（运行时模型）

5. 度量单位

操作系统领域有两套单位系统：存储容量（内存/硬盘）：二进制（ 2 2 2 的幂次）

网络速率/时钟频率：十进制（ 10 10 10 的幂次）

6. 课后习题解析

Modern Operating Systems 第五版学习:操作系统第一章

操作系统第一章笔记（下）

操作系统领域有两套单位系统：
存储容量（内存/硬盘）：二进制（ $2$ 的幂次）

网络速率/时钟频率：十进制（ $10$ 的幂次）

操作系统第二章笔记：进程与线程

已知： $p = 0.8$ （I/O等待比例），计算不同进程数下的 CPU 利用率：
$\text{CPU利用率} = 1 - p^n = 1 - 0.8^n$