计算机操作系统 · 综合大题

进程同步 · 银行家算法 · 4道综合练习

第一部分：生产者-消费者同步问题

经典进程同步模型 — 掌握信号量的 P/V 操作及多缓冲区协作。

练习一：基础生产者-消费者

问题描述

有生产者进程 P 和消费者进程 C，共享一个容量为 5 的环形缓冲区。

• P 生产产品放入缓冲区（有空位时）
• C 从缓冲区取产品消费（有产品时）

问题

1. 需要哪些信号量？初值各是多少？
2. 写出 P 和 C 的伪代码
3. 是否还需要额外的互斥信号量？为什么？

参考答案

信号量：empty = 5（空位数），full = 0（产品数），mutex = 1（互斥访问缓冲区）

需要 mutex：多个 P 或 C 同时操作缓冲区时，必须互斥。

// 生产者 P
while (true) {
    item = 生产产品();
    P(empty);      // 等空位
    P(mutex);      // 互斥进入
    放入缓冲区(item);
    V(mutex);
    V(full);       // 产品+1
}

// 消费者 C
while (true) {
    P(full);       // 等产品
    P(mutex);      // 互斥进入
    item = 取产品();
    V(mutex);
    V(empty);      // 空位+1
    消费(item);
}

练习二：日志收集系统

问题描述

某日志系统有 3 个进程和 2 个缓冲区，缓冲区容量均为 1：

• P1（采集进程）：从传感器读取数据 → 写入 B1
• P2（分析进程）：从 B1 读取 → 分析处理 → 结果写入 B2
• P3（上报进程）：从 B2 读取 → 发送到云端

约束

• B1 / B2 容量均为 1
• P1 只在 B1 有空位时写入
• P2 只在 B1 有数据 且 B2 有空位时才工作
• P3 只在 B2 有数据时读取

问题

1. 定义全部信号量及其初值
2. 分析进程间的同步关系
3. 写出 P1、P2、P3 的伪代码

参考答案

同步关系：P1→P2（前驱，通过 B1），P2→P3（前驱，通过 B2）

// P1 采集进程
while (true) {
    采集数据();
    P(empty1);      // 等 B1 空
    写 B1();
    V(full1);       // 通知 B1 有数据
}

// P2 分析进程
while (true) {
    P(full1);       // 等 B1 有数据
    读 B1();
    V(empty1);      // 通知 B1 空
    分析处理();
    P(empty2);      // 等 B2 空
    写 B2();
    V(full2);       // 通知 B2 有数据
}

// P3 上报进程
while (true) {
    P(full2);       // 等 B2 有数据
    读 B2();
    V(empty2);      // 通知 B2 空
    发送云端();
}

第二部分：银行家算法（死锁避免）

核心概念

练习三：系统资源分配（一）

题目

系统有 5 个进程 {P0-P4}，3 类资源 {A, B, C}，总资源量 (12, 9, 11)。

问题

1. 计算 Need 矩阵
2. 计算当前 Available
3. 判断系统是否处于安全状态？若是，给出一个安全序列
4. 若 P1 发出请求 Request(2, 2, 1)，能否分配？

参考答案

Need 矩阵

Available 计算

ΣAllocation：A=2+1+0+3+1=7, B=2+1+2+1+1=7, C=3+2+1+1+0=7

Available = (12-7, 9-7, 11-7) = (5, 2, 4)

安全序列判断

一个安全序列：P3 → P1 → P0 → P2 → P4

验证（简要）：P3 Need(4,2,3) ≤ Available(5,2,4) → 执行 → 释放后 Available=(8,3,5) → P1 执行 → ...

P1 Request(2, 2, 1) 分析

① Request(2,2,1) ≤ Need(4,2,3) ✓

② Request(2,2,1) ≤ Available(5,2,4) ✓

③ 试探分配后，Available=(3,0,3)，仍可找到安全序列 → 可以分配

练习四：系统资源分配（二）

题目

系统有 5 个进程 {P0-P4}，3 类资源 {A, B, C}，总资源量 (8, 6, 10)。

问题

1. 写出 Need 矩阵并计算 Available
2. 判断当前状态是否安全
3. 若 P2 请求 Request(3, 1, 0)，能否分配？
4. 举一个生活中类似"银行家算法"的例子

参考答案

Need = Max - Allocation

ΣAllocation：A=2+1+0+2+1=6, B=1+1+2+0+2=6, C=2+1+1+1+0=5

Available = (8-6, 6-6, 10-5) = (2, 0, 5)

安全序列判断

一个安全序列：P3 → P1 → P4 → P0 → P2

P2 Request(3, 1, 0) 分析

① Request(3,1,0) ≤ Need(3,3,3) ✓

② Request(3,1,0) ≤ Available(2,0,5) → 不成立！A 资源 3 > 2

③ 不能分配。当前 A 类资源不足。

生活实例

餐厅预约系统：顾客订座前，系统检查剩余桌位（Available）是否满足需求（Need），确认不超卖后才确认预订，避免"超订"死锁。

练习题目 · 仅供学习参考