操作系统（408考研）

进程与线程

进程与线程

一个进程（Process）是计算机中正在运行的程序的实例，它由以下核心组成部分构成：

1. PCB（Process Control Block，进程控制块）

• 进程ID（PID）、父进程ID（PPID）
• 进程状态（运行、就绪、阻塞等）

2. 代码段（Text Segment）
3. 数据段（Data Segment）

• 程序执行的实体。没有代码，进程无法运行；没有数据，代码无法处理信息。

PCB内主要有什么

1. 进程标识信息：PID
2. 进程状态信息：运行（Running）、就绪（Ready）、阻塞（Blocked）等
3. CPU上下文信息（状态）：（进程被切换时，保存当前CPU状态以便恢复）PC、SP
4. 等

进程的状态转换

• 区分就绪态与阻塞态
• 主动/被动的转换

进程的创建

1. 分配PID与PCB

   • 操作系统为新进程分配唯一的进程ID（PID）和空的进程控制块（PCB）。
   • 例子：在终端输入 ls 命令时，Shell（父进程）调用 fork() 创建子进程，内核为其分配PCB。

2. 分配资源

   • 子进程继承父进程的资源（如文件描述符、内存映射），或从操作系统申请新资源。
   • 例子：子进程通过 exec() 加载 ls 程序时，需申请内存存储代码和数据。

3. 初始化PCB

   • 设置进程状态（就绪）、程序计数器（PC）、堆栈指针等。

4. 加入就绪队列

   • 新进程被放入调度队列等待CPU分配。

进程终止

终止原因：

• 正常终止：进程执行完毕（如 main() 返回）。
• 异常终止：段错误（访问非法内存）、除零错误、被 kill 命令杀死。

终止步骤：

1. 触发终止：exit()、信号、父进程终止
2. 释放资源：内存、文件、锁、设备等
3. 更新 PCB：状态改为 Zombie，记录退出状态
4. 通知父进程：父进程 wait() 或由 init 接管
5. 删除 PCB

进程阻塞与唤醒

1. 阻塞（主动行为）

• 触发条件：进程主动调用阻塞操作（如 read() 等待I/O）。
• 过程：
  1. 进程从运行态转为阻塞态，PCB加入等待队列。
  2. CPU调度其他就绪进程。

2. 唤醒（被动行为）

• 触发条件：外部事件发生（如I/O完成、信号量释放）。
• 过程：
  1. 内核将对应PCB从阻塞队列移到就绪队列。
  2. 进程重新等待调度。

例子：

• 当磁盘I/O完成时，硬件触发中断，操作系统唤醒等待该I/O的进程。

易错点

1. 阻塞是主动的，唤醒是被动的：

   • 阻塞是进程主动请求等待（如调用 sleep()），而唤醒依赖外部事件（如定时器中断）。

2. 资源泄漏：

   • 终止进程时若未释放资源（如内存泄漏），会导致系统资源耗尽。

3. 进程调度负责分配CPU资源，而非进程创建
   进程调度（Process Scheduling）是操作系统内核的核心功能之一，负责从多个就绪（Ready）的进程中选择一个进程分配CPU资源，并控制进程状态的切换。其本质是解决CPU资源的分配问题，确保系统高效、公平地运行多个程序。

进程之间的通信

1. 共享存储：原理：多个进程访问同一块内存区域，直接读写数据，速度最快（无需内核介入）。
2. 消息传递：原理：进程通过发送/接收消息（数据包（HTTP））通信，由内核中转。
3. 管道通信：管道是一种特殊的文件：又称pipe文件。管道不满即可发、管道不空即可收

如何理解“进程获得处理器运行是通过调度得到的”？

这句话的核心含义是：在操作系统中，进程不能直接占用 CPU，而是必须由操作系统的调度程序（Scheduler）决定哪个进程可以运行、何时运行以及运行多久。

并发程序的执行速度与调度策略的关系

并发程序的执行速度并非单纯由CPU性能决定，调度策略的合理配置（如时间片（短时间片提高响应速度，长时间片提高吞吐量。）、算法选择（FCFS适合长任务，RR适合交互式任务。））同样关键

高级调度

高级调度的核心功能是 将作业从磁盘加载到内存并创建进程，因此 一定会导致新进程创建

为什么分时操作系统中，就绪态的任务最多？

分时操作系统的主要目标是：公平共享CPU时间（每个任务轮流执行一小段时间）。

实时操作系统阻塞态任务最多

因为：

1. 任务多为事件/周期驱动，大部分时间在等待触发条件。
2. 高优先级任务抢占CPU，低优先级任务长期阻塞。
3. 资源同步机制（如锁、信号量）强制任务阻塞等待。

线程

进程-资源分配的基本单位
线程-现代OS中CPU调度和分派的最小单位

系统线程 vs 用户线程

• 用系统线程：
  需要真并发（如视频编码、科学计算）。
  线程可能频繁阻塞（如网络服务）。

• 用用户线程：
  轻量级任务（如快速切换的小任务）。
  语言或环境限制（如Python的GIL）。

多级反馈队列调度算法

MLFQ的核心三点：

1. 优先级队列：高优先级处理短任务，低优先级处理长任务。
2. 动态降级：霸占CPU的任务会被“惩罚”到低优先级。
3. 奖励交互：频繁让出CPU的任务（如I/O）保持高优先级。// 以下举例

• 第一轮调度：X用了5ms后发起I/O请求（如加载图片）→ 保持Q0（因为主动释放了CPU）。
• 第二轮调度：X从I/O返回后，仍在 Q0，继续优先执行

利用信号量实现互斥

利用信号量实现同步

通过信号量，原本异步的进程可以像齿轮一样精准咬合，实现复杂的协作逻辑！

利用信号量实现前驱关系

生产者-消费者问题：为什么 PV 操作顺序很重要？

（1）生产者顺序：P(empty) → P(mutex)

• 如果先 P(mutex) 再 P(empty)：
  • 生产者拿到锁后，发现缓冲区满，会阻塞在 P(empty)。
  • 但锁未释放，消费者无法消费，导致死锁。

（2）消费者顺序：P(full) → P(mutex)

• 如果先 P(mutex) 再 P(full)：
  • 消费者拿到锁后，发现缓冲区空，会阻塞在 P(full)。
  • 但锁未释放，生产者无法生产，导致死锁。

结论：同步信号量（empty/full）必须先于互斥信号量（mutex）申请，否则可能死锁。

读者-写者

为什么这是“相对”写者优先？

阻塞队列的公平性：

• 若读者A和写者B同时请求：读者A先执行 P(w)，成功进入。写者B执行 P(w)，被阻塞。读者A完成 V(w) 后，唤醒的是阻塞队列的队首进程（可能是另一个读者C，而非写者B）。
• 结果：写者B可能仍需等待多个读者完成后才能执行，因此是相对优先而非绝对优先。

管程

管程（Monitor）详解

管程（Monitor）是一种高级进程同步工具，由编程语言或操作系统提供，用于解决信号量（Semaphore）在复杂同步问题中存在的死锁风险高、代码分散等问题。其核心思想是：
将共享资源及其操作封装为一个模块，自动实现互斥访问，并通过条件变量（Condition Variables）实现灵活的进程同步。

---

为什么需要管程？

信号量的缺陷

1. PV操作分散：每个进程需自行编写PV代码，容易遗漏或顺序错误。
2. 死锁风险高：如错误嵌套PV操作（如先 P(mutex) 再 P(empty)）。
3. 可维护性差：同步逻辑与业务逻辑混杂，代码难以理解。

管程的优势

• 内置互斥：管程的过程（函数）自动保证互斥执行（同一时间仅一个进程进入管程）。
• 条件变量：通过 wait() 和 signal() 实现进程阻塞与唤醒，避免忙等待。
• 代码模块化：同步逻辑集中在管程内，业务逻辑更清晰。

---

管程的组成

管程的定义包含以下4部分：

组成部分	说明
① 管程名称	例如 monitor Demo。
② 共享数据结构	描述资源的抽象数据（如缓冲区、计数器等）。
③ 操作共享数据的过程	提供对资源的访问接口（如 take_away()、give_back()）。
④ 初始化代码	设置共享数据的初始值（如 S=5）。

示例代码

monitor Demo                  // ① 管程名称
    shared int S;             // ② 共享数据结构（资源计数器）
    condition not_empty;      // 条件变量（用于同步）

    procedure take_away() {   // ③ 操作过程1：申请资源
        if (S <= 0) wait(not_empty);  // 资源不足时阻塞
        S--;                  // 占用资源
    }

    procedure give_back() {   // ③ 操作过程2：释放资源
        S++;                  // 释放资源
        signal(not_empty);    // 唤醒等待的进程
    }

    init_code() { S = 5; }    // ④ 初始化资源数为5
end monitor

---

管程的核心机制

（1）互斥访问

• 管程的过程（如 take_away()）自动互斥执行：
  当一个进程进入管程时，其他进程必须等待其退出后才能进入。

（2）条件变量（Condition Variables）

操作	作用
wait(c)	当前进程阻塞在条件变量 c 上，并释放管程的互斥锁。
signal(c)	唤醒一个在条件变量 c 上等待的进程（若无等待进程，则不产生效果）。

关键区别：

• 信号量的 V() 会改变信号量值，而管程的 signal() 仅唤醒进程，不改变条件变量状态。

---

管程 vs. 信号量

特性	管程（Monitor）	信号量（Semaphore）
互斥实现	自动（由管程保证）	手动（显式调用 P()/V()）
同步机制	条件变量（wait/signal）	PV操作（P()/V()）
死锁风险	低（内置互斥，逻辑集中）	高（PV顺序错误易导致死锁）
代码复杂度	低（同步逻辑封装在管程内）	高（分散在各进程中）
适用场景	高级语言（如Java的synchronized）	底层系统编程（如操作系统内核）

---

经典问题：用管程实现生产者-消费者

monitor ProducerConsumer {
    int buffer[N], count = 0;
    condition not_full, not_empty;  // 两个条件变量

    procedure produce(item) {
        if (count == N) wait(not_full);  // 缓冲区满则等待
        buffer[count] = item;
        count++;
        signal(not_empty);  // 唤醒消费者
    }

    procedure consume() {
        if (count == 0) wait(not_empty);  // 缓冲区空则等待
        item = buffer[count-1];
        count--;
        signal(not_full);  // 唤醒生产者
        return item;
    }
}

优势：

• 生产者和消费者只需调用 produce() 和 consume()，无需关心互斥细节。
• 条件变量直接表达“缓冲区非空”和“缓冲区非满”的同步逻辑。

---

管程的局限性

1. 语言依赖：需编程语言原生支持（如Java的 synchronized，Pascal的 monitor）。
2. 性能开销：管程的互斥和条件变量可能比信号量更耗时。
3. 灵活性不足：某些复杂场景（如嵌套同步）仍需结合其他机制。

---

常见疑问解答

Q1: 为什么管程的 signal() 不立即执行？

• 管程的 signal() 采用“Hansen风格”：
  唤醒的进程需等待当前进程退出管程后才会执行，避免频繁上下文切换。

Q2: 如何实现“读者优先”或“写者优先”？

• 在管程内通过条件变量和计数器实现：
  例如，读者-写者问题中可用 read_count 和 write_count 结合条件变量控制优先级。

---

循环等待与死锁的关系解析

循环等待的定义

循环等待是指存在一组进程 ({P_1, P_2, \cdots, P_n})，其中：

• (P_i) 持有的资源被 (P_{i+1}) 请求（(i=1, 2, \cdots, n-1)）。
• (P_n) 持有的资源被 (P_1) 请求，形成一个闭环等待链（如图2.13）。

循环等待 ≠ 死锁

虽然循环等待是死锁的必要条件，但并非充分条件。关键区别在于：

• 死锁的严格条件：
  所有 (P_i) 必须且只能从 (P_{i+1}) 获取资源（闭环内自给自足，无法被外部打破）。
• 循环等待的宽松条件：
  进程可能从闭环外的其他进程获取资源（如图2.14中的 (P_K)），从而避免死锁。

举例说明

场景1：严格死锁（循环等待导致死锁）

• (P_0) 持有 R1，请求 R2；
• (P_1) 持有 R2，请求 R1。
  结果：闭环内无外部资源可依赖，死锁必然发生。

场景2：循环等待但无死锁

• (P_0) 持有 R1，请求 R2；
• (P_1) 持有 R2，请求 R1 或 R3（R3被闭环外的 (P_K) 持有）。
  结果：若 (P_1) 选择请求 R3，且 (P_K) 释放 R3，则 (P_1) 可继续运行，闭环被打破，无死锁。

图解对比

图2.13（死锁）	图2.14（无死锁）
闭环内资源完全自循环，无外部依赖	闭环内进程可依赖外部资源（如 (P_K)）
必然死锁	可能避免死锁

核心结论

• 循环等待是死锁的必要条件：所有死锁一定存在循环等待链。
• 但循环等待不必然导致死锁：若闭环内进程能通过外部资源解除等待，则系统仍可正常运行。
• 死锁的充分条件：循环等待 + 资源完全闭环分配（无外部依赖）。

实际意义

• 死锁检测：仅发现循环等待链时，需进一步检查资源是否全部闭环。
• 死锁预防：允许进程从多来源申请资源（如银行家算法），可减少死锁概率。

简单说：
循环等待就像一群人围成一圈互相讨债，但如果有人能从圈外借到钱还债，圈子就能解开；若所有人只能靠圈内人还钱，就会僵持到底（死锁）。

死锁处理三大策略详解

死锁的应对方法可分为三类，分别作用于死锁发生的不同阶段：

---

1. 死锁预防（Prevention）

核心思想：破坏死锁的四个必要条件中的至少一个，确保系统永远不会进入死锁状态。
实现方式：

破坏条件	方法	缺点
互斥条件	允许资源共享（如只读文件），但多数资源无法避免互斥。	适用性有限。
请求并保持	进程必须一次性申请所有资源，否则不分配（静态分配）。	资源利用率低，可能饥饿。
不可剥脱条件	若进程申请资源失败，则释放已占有的资源（回滚）。	实现复杂，开销大。
循环等待条件（所有进程都在互相等待，谁都无法继续执行，形成“循环等待”。）	强制资源按线性顺序申请（如所有进程必须先申请R1再申请R2）。	限制灵活性，可能浪费资源。

特点：严格但保守，可能降低系统吞吐量。

---

2. 死锁避免（Avoidance）

核心思想：动态检查资源分配状态，确保系统始终处于安全状态（即存在至少一个进程执行序列不会导致死锁）。
关键算法：

• 银行家算法（Banker’s Algorithm）：
  1. 进程声明最大资源需求。
  2. 分配资源前，模拟检查分配后系统是否仍安全。
  3. 仅当安全时才分配资源。

安全状态示例：
假设系统有10个内存块：

• 进程A已占4，最多需7；
• 进程B已占2，最多需4；
• 剩余4块。
  安全序列：B可先完成（需再2块），释放后A可完成（需再3块）。

特点：需预知进程最大需求，运行时开销大，适合资源类型少的场景。

---

3. 死锁检测与恢复（Detection & Recovery）

核心思想：允许死锁发生，但定期检测并解除。

（1）死锁检测

• 资源分配图（RAG）算法：
  构建有向图（进程→资源：申请边；资源→进程：分配边），检测图中是否存在环。
• 时间复杂度：(O(n^2))（n为进程数）。

（2）死锁恢复

方法	操作	缺点
进程终止	终止所有死锁进程，或逐个终止直至死锁解除。	代价高，可能丢失工作。
资源抢占	强制剥夺某进程资源分配给其他进程（需解决饥饿和回滚问题）。	实现复杂，可能引发级联终止。

特点：适合对死锁容忍度高的系统（如通用操作系统）。

---

对比总结

策略	时机	开销	资源利用率	适用场景
预防	事前	低	低	嵌入式系统、实时系统
避免	事中（动态）	高	高	已知最大需求的批处理系统
检测与恢复	事后	中	最高	通用操作系统（如Linux、Windows）

---

如何选择策略？

1. 严格实时系统：优先预防（如航空控制系统）。
2. 高资源利用率需求：采用避免或检测（如数据库管理系统）。
3. 通用系统：通常结合预防（部分条件）和检测（如Unix/Linux默认不预防，仅定期检测）。

关键trade-off：安全性与性能的平衡！

循环等待条件的预防：资源有序分配法示例

核心思想

通过强制所有进程按照统一的线性顺序申请资源，破坏循环等待条件。例如，规定资源类型为R1、R2、R3时，所有进程必须按 R1 → R2 → R3 的顺序申请，禁止反向或跳跃申请。

---

具体示例

假设系统中有三种资源：

• 打印机（R1）
• 扫描仪（R2）
• 磁盘（R3）

规则：

所有进程必须按 R1 → R2 → R3 的顺序申请资源，不可逆序。

---

场景1：遵守顺序（无死锁）

• 进程A：
  1. 申请打印机（R1）→ 成功。
  2. 申请扫描仪（R2）→ 成功。
  3. 申请磁盘（R3）→ 成功。
• 进程B：
  1. 申请打印机（R1）→ 阻塞（因被进程A占用）。

结果：进程A完成后释放资源，进程B继续，不会形成循环等待。

---

场景2：违反顺序（可能死锁）

若允许无序申请：

• 进程X：
  1. 先申请扫描仪（R2）→ 成功。
  2. 再申请打印机（R1）→ 阻塞（假设被进程Y占用）。
• 进程Y：
  1. 先申请打印机（R1）→ 成功。
  2. 再申请扫描仪（R2）→ 阻塞（被进程X占用）。

结果：

• 进程X持有R2，等待R1；
• 进程Y持有R1，等待R2；
• 循环等待 → 死锁。

---

为什么有序分配能预防死锁？

• 打破闭环：强制线性顺序后，进程只能单向等待资源（如R1→R2→R3），无法形成“A等B，B等A”的环路。
• 数学证明：若有环存在，则至少有一个进程违反了申请顺序，与规则矛盾。

---

实际应用

• 数据库系统：按固定顺序锁表（如先锁表A再锁表B）。
• 操作系统：文件系统按层级顺序加锁。

缺点：

• 可能降低灵活性（如进程必须提前申请所有高序资源，即使暂时不需要）。
• 可能导致资源浪费（如进程A占用了R1但长时间不用，阻塞其他进程）。

总结：资源有序分配是简单有效的死锁预防手段，但需权衡效率与灵活性。