操作系统入门教程——从进程到内存管理

概述

操作系统（Operating System）是管理计算机硬件和软件资源的系统软件，是用户与计算机硬件之间的接口。操作系统的主要功能包括进程管理、内存管理、文件管理、设备管理和用户接口。

我们每天使用的 Windows、macOS、Linux、Android、iOS 都是操作系统。没有操作系统，计算机只是一堆无法使用的硬件。本教程将系统讲解操作系统的核心知识，帮助你理解计算机是如何高效地管理资源和运行程序的。

---

一、进程管理

1.1 进程的概念

进程是程序的一次执行过程，是系统进行资源分配和调度的基本单位。进程与程序的区别：

• 程序是静态的代码文件，存储在磁盘上
• 进程是动态的执行过程，存在于内存中
• 一个程序可以对应多个进程（如打开多个浏览器窗口）

进程控制块（PCB）：操作系统用来管理进程的数据结构，包含：

• 进程标识符（PID）
• 进程状态（就绪、运行、阻塞等）
• 程序计数器（下一条要执行的指令地址）
• CPU寄存器的值
• 内存管理信息
• I/O状态信息

1.2 进程的状态与转换

进程的基本状态：

       创建
        ↓
      就绪态 ←─────┐
        ↓          │
      运行态 ──→ 阻塞态
        ↓          │
      终止     ────┘（I/O完成或事件发生）

• 就绪态（Ready）：进程已获得除CPU之外的所有资源，等待CPU调度
• 运行态（Running）：进程正在CPU上执行
• 阻塞态（Blocked/Waiting）：进程等待某个事件（如I/O完成），即使CPU空闲也无法执行

状态转换：

• 就绪→运行：被调度程序选中，获得CPU
• 运行→就绪：时间片用完或被高优先级进程抢占
• 运行→阻塞：请求I/O或等待事件
• 阻塞→就绪：I/O完成或事件发生

1.3 进程调度算法

当多个进程竞争CPU时，调度算法决定哪个进程获得CPU。

先来先服务（FCFS）：按照进程到达的顺序执行。

• 优点：简单公平
• 缺点：可能导致"护航效应"——短进程被长进程阻塞

短作业优先（SJF）：选择预计运行时间最短的进程优先执行。

• 优点：平均等待时间最短
• 缺点：可能导致长作业"饥饿"

时间片轮转（RR）：每个进程轮流执行一个固定的时间片（如20ms）。

• 优点：响应时间好，适合交互式系统
• 缺点：时间片太大退化为FCFS，太小则上下文切换开销大

优先级调度：根据进程的优先级分配CPU。

• 优点：灵活，可以反映进程的重要性
• 缺点：低优先级进程可能"饥饿"

多级反馈队列：综合了多种算法的优点，是现代操作系统最常用的调度算法。

例题：假设有3个进程，到达时间和运行时间如下，使用FCFS和SJF分别计算平均等待时间。

进程	到达时间	运行时间
P1	0	24
P2	1	3
P3	2	3

FCFS：执行顺序 P1→P2→P3

• P1等待：0，P2等待：24-1=23，P3等待：27-2=25
• 平均等待：(0+23+25)/3 = 16

SJF（P1到达后，P2和P3先到达，选择短的）：执行顺序 P1→P2→P3（因为P1已经开始执行） 实际上如果P1先执行完（非抢占式），顺序仍是P1→P2→P3。 如果使用抢占式SJF（最短剩余时间优先）：P1先执行1个时间单位，P2到达且运行时间更短，切换到P2，P2完成后P3到达且运行时间相同，执行P3，最后执行P1。

• 执行顺序：P1(0-1)→P2(1-4)→P3(4-7)→P1(7-30)
• P1等待：7-1=6（第一段等0，第二段等3），P2等待：0，P3等待：2
• 平均等待：(6+0+2)/3 ≈ 2.67

1.4 线程

线程是进程中的一个执行单元，是CPU调度的基本单位。一个进程可以包含多个线程，线程共享进程的地址空间和资源。

进程与线程的区别：

比较项	进程	线程
资源	拥有独立的地址空间	共享进程的地址空间
创建开销	大（需要分配资源）	小（共享资源）
切换开销	大（需要切换地址空间）	小（只需切换寄存器）
通信	需要IPC机制	可以直接读写共享变量
安全性	进程间互不影响	一个线程崩溃可能导致整个进程崩溃

并发与并行：

• 并发：多个任务在同一个时间段内交替执行（单核CPU）
• 并行：多个任务在同一时刻同时执行（多核CPU）

1.5 进程同步与互斥

临界区：访问共享资源的代码段。

互斥：多个进程不能同时进入临界区。

同步：多个进程按照一定的顺序执行。

信号量：用于实现同步和互斥的机制。

• 互斥信号量（mutex）：初始值为1，保证同一时刻只有一个进程进入临界区
• 同步信号量：初始值为0，用于控制进程的执行顺序

经典同步问题——生产者-消费者问题：

semaphore mutex = 1;  // 互斥信号量
semaphore empty = N;  // 空缓冲区数量
semaphore full = 0;   // 满缓冲区数量

// 生产者
void producer() {
    while (true) {
        produce_item();
        wait(empty);      // 等待空缓冲区
        wait(mutex);      // 进入临界区
        put_item();
        signal(mutex);    // 离开临界区
        signal(full);     // 增加满缓冲区
    }
}

// 消费者
void consumer() {
    while (true) {
        wait(full);       // 等待满缓冲区
        wait(mutex);      // 进入临界区
        get_item();
        signal(mutex);    // 离开临界区
        signal(empty);    // 增加空缓冲区
        consume_item();
    }
}

---

二、内存管理

2.1 内存管理的基本概念

内存管理的主要任务：

• 内存分配与回收：为进程分配内存空间，进程结束后回收
• 地址转换：将程序中的逻辑地址转换为物理地址
• 内存保护：防止进程访问其他进程的内存空间
• 内存扩充：通过虚拟内存技术扩大可用内存

2.2 连续分配方式

单一连续分配：内存分为系统区和用户区，一次只能运行一个进程。

固定分区分配：将用户区划分为若干固定大小的分区，每个分区装一个进程。

• 优点：简单
• 缺点：产生内部碎片（分区内未使用的空间）

动态分区分配：根据进程的大小动态分配内存。

• 分配算法：
  • 首次适应（First Fit）：从头开始找第一个足够大的空闲分区
  • 最佳适应（Best Fit）：找最小的足够大的空闲分区
  • 最坏适应（Worst Fit）：找最大的空闲分区
• 缺点：产生外部碎片（空闲分区太小无法使用）

2.3 分页存储管理

分页是将内存划分为固定大小的页框（Frame），将进程的地址空间划分为同样大小的页（Page）。页和页框的大小通常为4KB。

页表：记录每个页对应的页框号。

地址转换：逻辑地址 = 页号 + 页内偏移

• 页号 = 逻辑地址 / 页大小
• 页内偏移 = 逻辑地址 % 页大小
• 物理地址 = 页框号 × 页大小 + 页内偏移

例题：页大小为4KB，逻辑地址为8196，页表如下：

页号	页框号
0	3
1	5
2	8

求物理地址。

解：

• 页号 = 8196 / 4096 = 2
• 页内偏移 = 8196 % 4096 = 4
• 查页表：页号2对应页框号8
• 物理地址 = 8 × 4096 + 4 = 32772

2.4 虚拟内存

虚拟内存是利用磁盘空间来扩展物理内存的技术。它允许程序使用比实际物理内存更大的地址空间。

局部性原理：程序在执行时，对内存的访问具有局部性——时间局部性（最近访问的数据可能再次被访问）和空间局部性（相邻的数据可能被访问）。

请求分页：只有当进程需要某个页面时，才将其从磁盘调入内存（按需调页）。

页面置换算法：当内存空间不足时，需要选择一个页面换出到磁盘。

OPT（最佳置换）：换出将来最长时间不会被访问的页面。理论最优，但无法实现（需要预知未来）。

FIFO（先进先出）：换出最早进入内存的页面。可能出现Belady异常——增加页框数反而增加缺页次数。

LRU（最近最久未使用）：换出最长时间没有被访问的页面。性能接近OPT，但实现成本较高。

时钟算法（CLOCK）：LRU的近似实现，使用访问位。

例题：页面引用序列为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，分配3个页框，使用FIFO和LRU计算缺页次数。

FIFO： | 引用 | 页框1 | 页框2 | 页框3 | 是否缺页 | |------|-------|-------|-------|---------| | 7 | 7 | - | - | 缺页 | | 0 | 7 | 0 | - | 缺页 | | 1 | 7 | 0 | 1 | 缺页 | | 2 | 2 | 0 | 1 | 缺页 | | 0 | 2 | 0 | 1 | 命中 | | 3 | 2 | 3 | 1 | 缺页 | | 0 | 2 | 3 | 0 | 缺页 | | 4 | 4 | 3 | 0 | 缺页 | | 2 | 4 | 2 | 0 | 缺页 | | 3 | 4 | 2 | 3 | 缺页 | | 0 | 0 | 2 | 3 | 缺页 | | 3 | 0 | 2 | 3 | 命中 | | 2 | 0 | 2 | 3 | 命中 | | 1 | 0 | 1 | 3 | 缺页 | | 2 | 0 | 1 | 2 | 缺页 | | 0 | 0 | 1 | 2 | 命中 | | 1 | 0 | 1 | 2 | 命中 | | 7 | 7 | 1 | 2 | 缺页 | | 0 | 7 | 0 | 2 | 缺页 | | 1 | 7 | 0 | 1 | 缺页 |

FIFO缺页次数：15次

（LRU的计算类似，但替换策略不同，此处省略详细过程，LRU缺页次数约为12次）

---

三、文件系统

3.1 文件的概念

文件是具有符号名的一组相关数据的集合。文件系统负责管理文件的存储、检索和保护。

文件的逻辑结构：

• 无结构文件（流式文件）：一串字节流，如Unix/Linux中的文件
• 有结构文件（记录式文件）：由一组记录组成

文件的物理结构：

• 连续分配：文件占据连续的磁盘块。优点：读取快。缺点：外部碎片，不易扩展。
• 链接分配：文件的磁盘块通过指针链接。优点：无外部碎片。缺点：只能顺序访问。
• 索引分配：使用索引表记录文件的磁盘块号。优点：支持随机访问。缺点：索引表占用空间。

3.2 目录结构

目录是文件的组织方式，常见的目录结构：

• 单级目录：所有文件在同一目录下，不允许重名
• 两级目录：每个用户有自己的目录
• 树形目录：最常用的结构，支持多级嵌套
• 无环图目录：支持文件共享（多个目录指向同一文件）

3.3 磁盘调度算法

磁盘读写的主要时间消耗在寻道时间（磁头移动到目标磁道的时间）。磁盘调度算法的目标是减少平均寻道时间。

FCFS：按请求到达的顺序处理。

SSTF（最短寻道时间优先）：选择离当前磁头位置最近的请求。

• 优点：平均寻道时间短
• 缺点：可能导致远端请求"饥饿"

SCAN（电梯算法）：磁头沿一个方向移动，处理沿途的请求，到达端点后反向。

• 优点：公平性好，不会饥饿

C-SCAN（循环扫描）：磁头单向移动，到达端点后直接回到起点重新开始。

例题：磁头当前位置在53号磁道，请求队列为 98, 183, 37, 122, 14, 124, 65, 67。使用SCAN算法（向磁道号增加方向移动），计算总移动磁道数。

解：排序后：14, 37, 53, 65, 67, 98, 122, 124, 183 移动顺序：53→65→67→98→122→124→183→37→14 总移动：(183-53)+(183-14) = 130+169 = 299

---

四、死锁

4.1 死锁的概念

死锁是多个进程因竞争资源而造成的一种互相等待的僵局，若无外力作用，这些进程都无法继续执行。

4.2 死锁的四个必要条件

死锁发生必须同时满足以下四个条件：

1. 互斥条件：资源一次只能被一个进程使用
2. 请求与保持条件：进程持有资源的同时请求新资源
3. 不可剥夺条件：已获得的资源不能被强行剥夺
4. 循环等待条件：存在一个进程的循环等待链

4.3 死锁的处理

预防：破坏死锁的四个必要条件之一。

• 破坏请求与保持：一次性申请所有资源
• 破坏不可剥夺：允许剥夺资源
• 破坏循环等待：按编号顺序申请资源

避免：使用银行家算法，在分配资源前判断是否会导致不安全状态。

检测与恢复：允许死锁发生，但定期检测并恢复（如终止某个进程或回滚）。

银行家算法核心思想：在分配资源前，模拟分配后检查系统是否仍处于安全状态（存在一个安全序列使所有进程都能完成）。

---

练习题

题目一

解释进程和线程的区别，以及为什么现代操作系统更倾向于使用多线程。

答案：进程是资源分配的基本单位，拥有独立的地址空间；线程是CPU调度的基本单位，共享进程的地址空间。多线程的优势：①创建和切换开销小（不需要切换地址空间）；②线程间通信方便（可以直接读写共享变量）；③能充分利用多核CPU的并行能力。例如，Web服务器使用多线程可以同时处理多个客户端请求，而不需要为每个请求创建一个新进程。

题目二

页大小为4KB，逻辑地址为20500，页表为：页0→帧5，页1→帧3，页2→帧8，页3→帧2，页4→帧1。求物理地址。

答案：

• 页号 = 20500 / 4096 = 5（整数除法）
• 等等，20500 / 4096 = 5.004...，所以页号 = 5
• 但页表只到页4，说明逻辑地址越界
• 重新计算：20500 / 4096 = 5（因为 5 × 4096 = 20480，20500 - 20480 = 20）
• 页号5超出了页表范围（0-4），这是一个地址越界错误
• （如果题目意图是合理的，假设页表有页5→帧7）
• 物理地址 = 7 × 4096 + 20 = 28692

（注：此题原页表确实缺少页5，设计时应确保页表覆盖所有可能的页号）

题目三

说明FIFO页面置换算法可能出现Belady异常，并举例。

答案：Belady异常是指增加分配的页框数反而导致缺页次数增加的现象。例如，页面引用序列为 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。分配3个页框时缺页9次，分配4个页框时缺页10次。这是因为FIFO只考虑页面进入内存的时间，不考虑页面的使用频率和最近使用情况，所以增加页框可能把将来需要的页面换出。LRU和OPT不会出现Belady异常。

题目四

有一个磁盘请求队列：55, 58, 39, 18, 90, 160, 150, 38, 184。磁头当前位置在100号磁道。分别使用SSTF和SCAN（向磁道号减小方向移动）算法，求总移动磁道数。

答案： SSTF：选择离100最近的请求 100→90→58→55→39→38→18→150→160→184 移动：10+32+3+16+1+20+132+10+24 = 248

SCAN（向减小方向）： 100→90→58→55→39→38→18→150→160→184 移动：10+32+3+16+1+20+132+10+24 = 248 （注意：SCAN到达18后反向，所以18→150需要移动132）

实际上SCAN：100→90→58→55→39→38→18→(反向)→150→160→184 移动：10+32+3+16+1+20+132+10+24 = 248

题目五

什么是死锁？如何用银行家算法避免死锁？

答案：死锁是多个进程因竞争资源而造成互相等待的僵局。银行家算法通过在分配资源前检查系统是否仍处于安全状态来避免死锁。具体步骤：①维护可用资源向量、最大需求矩阵、已分配矩阵和需求矩阵；②当进程请求资源时，先检查请求是否超过需求和可用资源；③尝试分配资源，然后执行安全性算法——寻找一个安全序列，使得每个进程的剩余需求都能被满足；④如果存在安全序列，执行分配；否则拒绝分配，让进程等待。

---

总结

操作系统的核心知识可以归纳为四大模块：

1. 进程管理：进程与线程的概念和区别、进程状态转换、调度算法（FCFS、SJF、RR、优先级）、进程同步与互斥（信号量、生产者-消费者问题）。
2. 内存管理：连续分配、分页存储管理、页表与地址转换、虚拟内存与页面置换算法（FIFO、LRU、OPT）。
3. 文件系统：文件的逻辑和物理结构、目录结构、磁盘调度算法（SSTF、SCAN）。
4. 死锁：死锁的四个必要条件、预防、避免（银行家算法）、检测与恢复。

学习操作系统的关键是理解概念背后的原理，而不仅仅是记忆定义。建议结合实际操作来学习——在Linux系统中使用ps命令查看进程，使用top命令观察CPU和内存使用情况，使用strace跟踪系统调用。这些实践操作能帮助你更直观地理解操作系统的运行机制。