操作系统核心概念回顾 ¶

本文档综合了两份演示文稿，对操作系统的核心概念进行了全面回顾，涵盖了从操作系统基础、进程与线程管理，到 CPU 调度、同步机制和死锁等关键主题。

操作系统概述 (R1: page 3-17) ¶

操作系统（Operating System, OS）是计算机系统中最核心的系统软件，它在应用程序和底层硬件之间扮演着至关重要的桥梁角色。

核心功能与运行模式 (R1: page 6-9) ¶

为了有效管理资源并提高效率，操作系统引入了多道程序设计、分时系统等关键技术，并通过硬件支持的双模式操作来确保自身的稳定和安全。

• 多道程序设计 (Multiprogramming): 内存中同时存放多个作业（Jobs）。当一个作业需要等待 I/O 操作时，操作系统会切换到另一个作业，从而保证 CPU 始终有任务执行，提高了系统利用率。
• 分时系统 (Timesharing / Multitasking): 这是多道程序设计的逻辑扩展。操作系统在不同作业之间进行极其频繁的切换（通常响应时间小于 1 秒），使得每个用户都能与自己的程序（即进程）进行交互，感觉就像是独占了整个计算机。

资源管理 (R1: page 13-17) ¶

操作系统是计算机系统的资源管理器，主要负责以下几类资源的管理：

1. 进程管理 (Process Management): 进程是“执行中的程序”，是操作系统进行资源分配和保护的基本单位。操作系统负责进程的创建、终止、挂起、恢复、同步和通信。
2. 内存管理 (Memory Management): 内存是 CPU 能直接访问的存储。操作系统需要跟踪哪些内存正在被使用、由谁使用，并在进程需要时为其分配和回收内存。为了优化 CPU 利用率和响应时间，操作系统还为程序员提供了虚拟内存 (virtual memory) 的抽象。
3. 文件系统管理 (File System Management): 操作系统以文件 (file) 的形式提供统一、逻辑的数据存储视图。文件通常被组织在目录 (directories) 中。操作系统负责文件的创建、删除、读写以及访问控制。

操作系统结构与服务 (R1: page 18-48) ¶

操作系统向用户和系统自身提供一系列服务，并通过特定的结构来组织这些功能。

操作系统服务 (R1: page 19-21) ¶

从不同视角看，操作系统的服务可分为两类：

1. 用户可见的服务 (User-Visible Services): - 用户界面 (UI): 包括命令行界面（CLI）、图形用户界面（GUI）和批处理。 - 程序执行: 加载程序到内存，执行它，并处理其正常或异常的终止。 - I/O 操作: 管理程序与文件或 I/O 设备的交互。 - 文件系统操作: 文件的读、写、创建、删除、搜索和权限管理。 - 通信: 支持进程间的信息交换，可以通过共享内存或消息传递。 - 错误检测: 持续监控 CPU、内存、I/O 设备及用户程序中可能发生的错误，并采取措施保证系统的正确性和一致性。

2. 系统视角的服务 (System View Services): - 资源分配: 为并发运行的多个用户或作业分配 CPU、内存、文件、I/O 设备等资源。 - 记账 / 日志: 跟踪记录用户使用的资源类型和数量。 - 保护与安全 (Protection and Security): - 保护是控制进程或用户对系统资源访问的机制。例如，访问控制和进程隔离。 - 安全是基于保护机制实现的策略，用于防止内外部对系统的非法访问，如用户认证。

系统调用：连接用户程序与内核的桥梁 (R1: page 23-34) ¶

系统调用是用户程序访问操作系统服务的编程接口。

系统调用的处理流程 (R1: page 26, 32-34): 以 x86-64 架构上的 write 系统调用为例： 1. 用户空间: C 库函数 write() 将系统调用号（syscall number）放入 %eax 寄存器，并将其他参数（文件描述符、缓冲区地址、大小）按约定放入其他寄存器。 2. 陷入内核: 程序执行 syscall 指令。这会导致 CPU 发生陷阱，模式从用户模式切换到内核模式，并将控制权转移到内核中一个预定义的入口点 (kernel_entry )。 3. 内核空间: - kernel_entry 代码首先保存所有用户空间寄存器的状态到当前进程的内核栈中。 - 内核通过 %eax 寄存器中的系统调用号，在系统调用表 (syscall_table) 中查找对应的处理函数（syscall_table[1] 指向 write 的实现）。 - 执行系统调用处理函数。 - 处理完成后，调用 ret_to_user，恢复之前保存的用户寄存器。 - 执行 iret (或类似指令) ，将 CPU 模式切换回用户模式，并返回到用户程序 syscall 指令的下一条指令继续执行。

操作系统结构模型 (R1: page 41-47) ¶

操作系统的内部组件可以有多种组织方式： - 简单结构 (Simple Structure): 如 MS-DOS，功能层级和接口划分不清晰，模块之间耦合度高，就像一盘意大利面。 - 宏内核 / 单体结构 (Monolithic Structure): 如传统的 UNIX 和现代的 Linux。所有核心功能（文件系统、CPU 调度、内存管理等）都运行在内核空间。优点是效率高，因为功能间的调用只是函数调用；缺点是代码庞大，一个模块的 bug 可能导致整个系统崩溃。 - 分层结构 (Layered Approach): 将操作系统划分为若干层，每一层只使用其下一层提供的服务。结构清晰，易于调试，但层级间的通信开销较大。 - 微内核结构 (Microkernel Structure): 将尽可能多的功能（如文件系统、设备驱动）移出内核，作为用户空间的服务器进程来运行。内核只保留最基本的功能（如进程通信、基本调度、内存管理）。优点是更可靠、更安全、易于扩展；缺点是用户空间和内核空间之间的通信（通常是消息传递）会带来性能开销。

进程管理 (R1: page 49-75) ¶

进程是操作系统中一个至关重要的概念，它是资源分配和调度的基础。

进程与程序 (R1: page 50-51) ¶

一个进程的内存布局通常包括： - 文本段 (Text Section): 程序代码。 - 数据段 (Data Section): 全局变量。 - 堆 (Heap): 动态分配的内存。 - 栈 (Stack): 存储函数参数、局部变量和返回地址。 - 运行时状态: 包括程序计数器 (PC) 和 CPU 寄存器的值。

进程控制块 (PCB) (R1: page 52) ¶

操作系统在内核中为每个进程维护一个进程控制块 (Process Control Block, PCB)，它包含了管理该进程所需的所有信息。在 Linux 中，这由 task_struct 结构体实现，其内容包括：

• 进程 ID (pid)
• 进程状态 (Process State): 如运行、就绪、等待等。
• 程序计数器 (PC) 和 CPU 寄存器: 当进程被中断时，这些信息被保存，以便后续恢复。
• CPU 调度信息: 进程优先级、调度队列指针等。
• 内存管理信息: 指向页表等数据结构的指针。
• I/O 状态信息: 分配给进程的 I/O 设备和打开的文件列表。

进程的生命周期 (R1: page 56) ¶

进程在其生命周期中会经历以下几种状态： - 新建 (New): 进程正在被创建。 - 运行 (Running): 指令正在被 CPU 执行。 - 等待 (Waiting): 进程正在等待某个事件发生（如 I/O 完成或收到信号）。 - 就绪 (Ready): 进程已准备好，等待被分配给 CPU 运行。 - 终止 (Terminated): 进程已完成执行。

进程创建 (R1: page 57-65) ¶

在 UNIX/Linux 系统中，进程通过 fork() 和 exec() 系统调用来创建： - fork(): 创建一个与父进程几乎完全相同的新进程（子进程）。它复制父进程的地址空间、寄存器等。fork() 的奇妙之处在于它调用一次，返回两次：在父进程中返回子进程的 PID，在子进程中返回 0。 - exec(): 在一个进程的上下文中加载并运行一个新的程序。它会用新程序的代码、数据、堆栈等覆盖当前进程的内存空间。 - wait(): 父进程可以使用此调用来等待其子进程终止。

pid_t pid = fork(); // 1. 创建子进程
if (pid < 0) {
    // fork 失败
} else if (pid == 0) {
    // 2. 子进程执行此代码块
    execlp("/bin/ls", "ls", NULL); // 3. 加载并执行 'ls' 程序
} else {
    // 4. 父进程执行此代码块
    wait(NULL); // 5. 等待子进程执行完毕
    printf("Child Complete");
}

上下文切换 (Context Switch) (R1: page 69-72) ¶

当操作系统需要将 CPU 从一个进程（或线程）切换到另一个时，就会发生上下文切换。这个过程包括： 1. 保存当前进程的上下文（CPU 寄存器状态、程序计数器等）到其 PCB 中。 2. 加载新进程的上下文到 CPU 寄存器中。

上下文切换是纯粹的系统开销 (overhead)，因为在此期间 CPU 没有执行任何有用的用户代码。其耗时取决于硬件支持，例如，某些硬件提供多套寄存器组，可以加快切换速度。

线程管理 (R2: page 3-24) ¶

在现代操作系统中，线程是比进程更轻量级的执行单位，它极大地提升了并发编程的效率和响应性。

为什么需要线程？ (R2: page 4)¶

• 并发执行: 一个应用程序中可能包含多个可以同时进行的任务，如 Web 服务器需要同时响应多个客户端请求，文本编辑器可以在用户输入的同时进行后台拼写检查。
• 效率: 创建一个新进程的开销很大（需要分配全新的地址空间等），而创建一个新线程则非常“轻量级”，因为它与同进程的其他线程共享大部分资源。线程间的上下文切换也比进程间的切换快得多。
• 简化编码: 将复杂的任务分解为多个独立的线程可以简化程序结构。

线程的定义 (R2: page 5) ¶

线程的优缺点 (R2: page 8-10) ¶

优点: 1. 经济性 (Economy): 创建和切换线程的成本远低于进程。线程切换时，由于共享地址空间，无需刷新 TLB (Translation Lookaside Buffer) 和缓存。 2. 资源共享 (Resource Sharing): 线程天然共享内存，无需像进程那样依赖复杂的 IPC 机制（如共享内存段）来进行数据交换。 3. 响应性 (Responsiveness): 在一个多线程应用中，即使一个线程被阻塞（例如，等待网络数据），其他线程仍然可以继续执行，从而保证了应用的响应能力。 4. 可伸缩性 (Scalability): 在多核处理器上，多线程可以实现真正的并行执行，有效利用多核优势。

缺点: 1. 弱隔离性: 由于共享内存，一个线程的错误（如非法内存访问，即段错误）会导致整个进程崩溃，进而影响所有其他线程。 2. 编程复杂性: 共享资源带来了同步问题（如竞态条件），需要程序员小心处理，这比单线程编程要困难得多。

用户线程与内核线程 (R2: page 11-12) ¶

线程的实现可以分为两个层面： - 用户线程 (User Threads): 在用户空间由线程库（如 POSIX Pthreads, Win32 threads）来管理，内核对此一无所知。管理开销小，但如果一个用户线程发起了阻塞式系统调用，整个进程（包括所有其他用户线程）都会被阻塞。 - 内核线程 (Kernel Threads): 由操作系统内核直接支持和管理。一个内核线程阻塞不会影响其他线程。现代主流操作系统（如 Windows, Linux）都支持内核线程。

为了让用户线程能够真正运行，必须将其映射到内核线程上。

多线程模型 (R2: page 13-16) ¶

用户线程与内核线程的映射关系有以下几种模型：

1. 多对一模型 (Many-to-One):

   • 描述: 多个用户线程映射到一个内核线程。
   • 优点: 线程管理在用户空间完成，效率高。
   • 缺点:
     • 一个线程阻塞，整个进程阻塞。
     • 无法在多核处理器上实现并行。
   • 示例: Solaris Green Threads。

2. 一对一模型 (One-to-One):

   • 描述: 每个用户线程映射到一个内核线程。
   • 优点:
     • 解决了阻塞问题，一个线程阻塞不影响其他线程。
     • 可以在多核上并行执行。
   • 缺点: 每创建一个用户线程都需要创建一个内核线程，开销较大，可能导致系统对线程数量有所限制。
   • 示例: Windows, Linux。这是目前最主流的模型。

3. 多对多模型 (Many-to-Many):

   • 描述: M 个用户线程映射到 N 个内核线程（M >= N）。
   • 优点: 结合了前两种模型的优点，既允许创建大量用户线程，又能实现多核并行。
   • 缺点: 实现复杂。
   • 示例: 旧版 Solaris, Windows NT/2000 with ThreadFiber package。

Linux 中的线程实现 (R2: page 18-24) ¶

CPU 调度 (R2: page 25-36) ¶

CPU 调度是操作系统的核心功能之一，其目标是选择就绪队列中的一个进程（或线程），并为其分配 CPU。

基本概念 (R2: page 26-27) ¶

• CPU-I/O 执行周期: 进程的执行是在 CPU 计算（CPU burst）和 I/O 等待（I/O burst）之间交替进行的。
• 调度时机: CPU 调度决策可能在以下情况发生：
  1. 进程从运行态切换到等待态（如 I/O 请求）。
  2. 进程从运行态切换到就绪态（如时钟中断）。
  3. 进程从等待态切换到就绪态（如 I/O 完成）。
  4. 进程终止。
• 抢占式 vs. 非抢占式调度:
  • 非抢占式 (Non-preemptive): 调度仅在情况 1 和 4 发生。一旦 CPU 分配给一个进程，该进程会一直持有 CPU 直到它自愿放弃（等待 I/O 或终止）。也称为协作式调度 (cooperative scheduling)。
  • 抢占式 (Preemptive): 调度也可能在情况 2 和 3 发生。操作系统可以强制剥夺当前进程的 CPU 使用权，并将其分配给另一个进程。现代通用操作系统都采用抢占式调度。

调度准则 (R2: page 28) ¶

评估调度算法性能的主要准则包括：

• CPU 利用率 (CPU utilization): CPU 处于忙碌状态的时间百分比。目标是最大化。
• 吞吐量 (Throughput): 单位时间内完成的进程数量。目标是最大化。
• 周转时间 (Turnaround time): 从进程提交到进程完成的总时间。目标是最小化。
• 等待时间 (Waiting time): 进程在就绪队列中等待的总时间。目标是最小化。
• 响应时间 (Response time): 从提交请求到产生第一次响应的时间。目标是最小化。

常用调度算法 (R2: page 29-36) ¶

1. 先来先服务 (First-Come, First-Served, FCFS) (R2: page 30)
   • 策略: 按照进程到达就绪队列的顺序进行调度。
   • 特点: 实现简单，但平均等待时间可能很长，特别是当一个长任务先于多个短任务到达时（护航效应）。非抢占式。
2. 最短作业优先 (Shortest-Job-First, SJF) (R2: page 31-33)
   • 策略: 选择下一个 CPU 执行周期最短的进程。
   • 特点:
     • 理论上最优: 对于给定的进程集合，SJF 能保证最小的平均等待时间。
     • 实现的困难: 无法精确预知下一个 CPU 执行周期的长度。通常使用历史数据进行指数平均来预测。
     • 可以是抢占式或非抢占式。抢占式版本称为最短剩余时间优先 (Shortest-Remaining-Time-First, SRTF)，即当一个新进程到达且其执行时间比当前进程的剩余时间还短时，会发生抢占。

3. 优先级调度 (Priority Scheduling) (R2: page 34-35)
   • 策略: 为每个进程分配一个优先级，CPU 分配给优先级最高的进程。
   • 特点:
     • 可以是抢占式或非抢占式。
     • SJF 是优先级调度的一个特例，优先级是下一个 CPU 执行周期的倒数。
     • 问题: 可能导致饥饿 (Starvation)，即低优先级进程可能永远得不到执行。
     • 解决方案: 老化 (Aging)，即随着时间的推移，逐步提高等待时间过长进程的优先级。
4. 轮转调度 (Round Robin, RR) (R2: page 36)
   • 策略: 专门为分时系统设计。将就绪队列视为一个循环队列，每个进程被分配一个固定的 CPU 时间片（time quantum, q）。如果进程在一个时间片内未完成，它将被抢占并放回就绪队列的末尾。
   • 特点:
     • 时间片大小是关键:
       • q 太大：退化为 FCFS。
       • q 太小：上下文切换开销过大，系统效率降低。
     • 通常时间片大小在 10-100 毫秒之间。

同步 (Synchronization) (R2: page 37-59) ¶

当多个并发进程或线程需要访问共享数据时，必须对它们的执行顺序进行协调，以避免数据不一致的问题。

竞态条件与临界区 (Race Condition & Critical Section) (R2: page 39-42) ¶

为了解决竞态条件，我们需要识别出代码中访问共享资源的临界区 (Critical Section)，并确保在任何时候，最多只有一个进程能在其临界区内执行。

临界区问题的解决方案 (R2: page 44-45) ¶

任何一个有效的解决方案都必须满足以下三个要求： 1. 互斥 (Mutual Exclusion): 如果一个进程正在其临界区内执行，那么其他任何进程都不能进入其临界区。 2. 进步 (Progress): 如果没有进程在临界区内，并且有进程希望进入，那么只有那些不在剩余区（remainder section）的进程可以参与选择，且这种选择不能被无限期推迟。 3. 有界等待 (Bounded Waiting): 从一个进程发出进入临界区的请求，到该请求被允许为止，其他进程被允许进入临界区的次数必须是有限的。这可以防止饥饿。

同步原语 (R2: page 47-53) ¶

操作系统和硬件提供了一系列同步工具，从低级到高级包括：

1. 硬件指令 (Hardware Instructions) (R2: page 47)
   • 现代处理器提供特殊的原子指令 (atomic instructions)，如 Test-and-Set 和 Compare-and-Swap。这些指令在执行期间不会被中断，是构建更高级同步锁的基础。
2. 互斥锁 (Mutex Locks) (R2: page 48-50)
   • 最简单的同步工具。通过 acquire() 获取锁，release() 释放锁来保护临界区。
   • 基于原子硬件指令的简单实现会导致忙等待 (busy waiting)，即进程在循环中不断检查锁是否可用，浪费 CPU 时间。这种锁也称为自旋锁 (spinlock)。自旋锁在锁持有时间极短且在多核系统上时是高效的，因为它避免了上下文切换的开销。
3. 信号量 (Semaphore) (R2: page 51-53)
   • 一个更强大的同步工具，由一个整数变量 S 和两个原子操作构成：wait(S) 和 signal(S)（也称为 P() 和 V()）。
   • 计数信号量: S的值可以为任意整数，用于控制对 N 个资源的访问。
   • 二元信号量: S的值只能是 0 或 1，功能类似互斥锁。
   • 避免忙等待的实现:
     • wait(S): S--。如果 S < 0，则将当前进程放入与信号量关联的等待队列并阻塞 (block)。
     • signal(S): S++。如果 S <= 0，则从等待队列中唤醒 (wakeup) 一个进程。
   • 这里的 S 值的含义：若为正，表示可用资源数；若为负，其绝对值表示等待该资源的进程数。

do {
  // produce an item
  wait(empty_slots); // 等待有空位
  wait(mutex);       // 获取缓冲区访问权
  // add item to buffer
  signal(mutex);       // 释放缓冲区访问权
  signal(full_slots);  // 通知有一个物品已满
} while (TRUE);

do {
  wait(full_slots);  // 等待有物品
  wait(mutex);       // 获取缓冲区访问权
  // remove item from buffer
  signal(mutex);       // 释放缓冲区访问权
  signal(empty_slots); // 通知有一个槽位已空
  // consume the item
} while (TRUE);

死锁 (Deadlock) (R2: page 60-65) ¶

死锁是多道程序环境下可能出现的一种严重问题。

死锁的定义与条件 (R2: page 61, 64) ¶

死锁发生的四个必要条件:

1. 互斥 (Mutual exclusion): 至少有一个资源必须以非共享模式持有，即一次只有一个进程可以使用。
2. 持有并等待 (Hold and wait): 一个进程至少持有一个资源，并且正在等待获取由其他进程持有的额外资源。
3. 非抢占 (No preemption): 资源不能被强制性地从持有它的进程中抢占，只能由持有它的进程在完成任务后自愿释放。
4. 循环等待 (Circular wait): 存在一个等待进程集合 {P₀, P₁, ..., Pₙ}，其中 P₀ 在等待 P₁ 持有的资源，P₁ 在等待 P₂ 持有的资源，...，Pₙ 在等待 P₀ 持有的资源。

// Thread 1
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);

// Thread 2
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);

死锁处理策略 (R2: page 65) ¶

主要有四种处理死锁的方法： 1. 死锁预防 (Prevention): 通过破坏死锁发生的四个必要条件中的至少一个来从结构上防止死锁。例如，要求所有进程一次性申请所有资源（破坏“持有并等待”），或者对资源类型进行排序，要求进程按序申请（破坏“循环等待”）。这种方法通常过于严格，会降低资源利用率。 2. 死锁避免 (Avoidance): 系统在分配资源前，先判断此次分配是否会导致系统进入不安全状态（可能导致死锁的状态）。如果会，则拒绝分配。这需要系统预先知道进程未来的资源需求，如银行家算法。 3. 死锁检测与恢复 (Detection and Recovery): 允许系统进入死锁状态，通过算法定期检测是否存在死锁。如果检测到，则采取措施进行恢复，如终止一个或多个死锁进程，或者抢占资源。 4. 忽略问题 (Ignoring the problem): 像鸵鸟一样把头埋进沙里，假装死锁从未发生。这是主流通用操作系统（如 UNIX, Linux, Windows）采用的策略。因为死锁预防和避免的代价太高，而死锁在通用系统中发生的频率相对较低，所以把处理死锁的责任交给了应用程序员。

如果这对你有用的话，请给我点个star吧 ===>