QEQuantumEinsteinSearchCtrl/⌘K
Notes/📖 操作系统（Operating System）—— 408考研完全笔记/第四章 进程同步（核心考点⭐⭐⭐）

第四章 进程同步（核心考点⭐⭐⭐）

4 分钟阅读1,441 字30 个小节
返回目录

第四章 进程同步（核心考点⭐⭐⭐）

4.1 基本概念

两种制约关系

  • 间接制约（互斥）：多个进程因共享临界资源而互斥使用
  • 直接制约（同步）：多个进程因合作而需要协调推进顺序

临界资源

一次仅允许一个进程使用的资源。硬件如打印机、软件如共享变量。

临界区

进程中访问临界资源的那段代码。

同步机制应遵循的四个准则

准则说明
空闲让进临界区空闲时，允许请求进入
忙则等待临界区被占用时，其他请求必须等待
有限等待保证进程在有限时间内能进入临界区（不饥饿）
让权等待不能进入临界区的进程应释放CPU（原则上应遵循但非必须）

4.2 软件同步方法

Peterson算法（两进程互斥⭐）

c
// 进程Pi
flag[i] = true;     // 表示Pi想进入
turn = j;           // 谦让：设置对方优先
while(flag[j] && turn == j);  // 等待
    // 临界区
flag[i] = false;
  • 满足空闲让进、忙则等待、有限等待（前3条准则）
  • 不满足让权等待（忙等）
  • 仅适用于两个进程

4.3 硬件同步机制

方法原理缺点
关中断进入临界区前关中断，退出后开中断滥用风险、影响效率、不适用多CPU
TS指令(Test-and-Set)原子操作：读取lock旧值并置lock=true忙等,不满足让权等待
Swap/XCHG指令原子交换两个变量忙等,不满足让权等待
c
// TS指令
boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}
// 使用：while(TestAndSet(&lock)); 临界区; lock=false;

4.4 信号量机制（⭐⭐⭐最核心）

整型信号量

c
wait(S) { while(S <= 0); S--; }   // 忙等
signal(S) { S++; }

缺点：忙等（不满足让权等待）

记录型信号量（⭐⭐⭐）

c
typedef struct {
    int value;
    struct process_control_block *list;  // 等待队列
} semaphore;

void wait(semaphore *S) {     // P操作
    S->value--;
    if (S->value < 0)
        block(S->list);       // 阻塞自己,插入等待队列
}

void signal(semaphore *S) {   // V操作
    S->value++;
    if (S->value <= 0)
        wakeup(S->list);      // 唤醒等待队列中的一个进程
}

⭐ 关键理解：

  • value>0value > 0：有valuevalue个资源可用
  • value=0value = 0：无资源可用，无进程等待
  • value<0value < 0：∣value∣|value| = 等待队列中的进程数
  • 满足让权等待（阻塞自己而非忙等）

AND型信号量

  • Swait(S1, S2, ..., Sn)：同时申请所有资源，全部≥1才分配
  • Ssignal(S1, S2, ..., Sn)：同时释放所有资源
  • 避免死锁（一次获取所有需要的资源）

信号量集

  • Swait(S1,t1,d1; S2,t2,d2; ...; Sn,tn,dn)
    • tit_i：测试值（Si≥tiS_i \geq t_i 才分配）
    • did_i：需求值（每次分配did_i个）
  • 特殊情况：
    • (S,d,d)(S,d,d)：每次申请dd个
    • (S,1,1)(S,1,1)：等价于记录型信号量
    • (S,1,0)(S,1,0)：开关型（S≥1S \geq 1时允许，S=0S=0时阻塞，但不消耗资源）

4.5 信号量的应用（⭐⭐⭐）

实现互斥

c
semaphore mutex = 1;  // 互斥信号量,初值为1

// 进程Pi
wait(mutex);          // P(mutex)
    // 临界区
signal(mutex);        // V(mutex)

mutexmutex 取值范围：−1,0,1-1, 0, 1

  • 11：资源空闲
  • 00：一个进程在临界区，无等待
  • −1-1：一个在临界区，一个在等待

实现同步

c
semaphore S = 0;  // 同步信号量,初值为0

// 进程P1                          // 进程P2
C1;  // 语句C1                     wait(S);  // P(S) 等在前面
signal(S); // V(S) 执行完C1后通知   C2;       // C2必须在C1之后执行

口诀：前V后P（在"前面的"操作后面做V，在"后面的"操作前面做P）

4.6 管程（⭐⭐）

管程的定义

管程由以下四部分组成：

  1. 管程名称
  2. 共享数据结构
  3. 对该数据结构操作的一组过程（函数）
  4. 对共享数据设置初始值的语句

管程的特性

  • 封装：数据结构只能被管程内部的过程访问
  • 互斥：每次只允许一个进程进入管程执行
  • 信息隐蔽：外部不可见内部数据

条件变量

x.wait() // 阻塞调用进程,释放管程,将进程加入x的等待队列 x.signal() // 唤醒x等待队列中的一个进程;若无等待进程,则无操作

⚠️ 条件变量的signal与信号量的signal不同：

  • 信号量的signal：SS值加1，即使无等待进程也有效果
  • 条件变量的signal：若无等待进程则无动作（不会"记忆"）

管程 vs 进程

方面管程进程
目的管理共享资源实现系统并发
数据结构共享数据结构PCB
操作同步操作程序执行
工作方式被动调用主动运行
并发不可并发(互斥进入)可并发
动态性管程是OS的一个资源管理模块（静态）进程有生命周期（动态）

4.7 经典同步问题（⭐⭐⭐必考）

生产者-消费者问题

c
semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty = n;   // 空缓冲槽数量,初始n
semaphore full = 0;    // 满缓冲槽数量,初始0

// 生产者                              // 消费者
while(1) {                             while(1) {
    生产一个产品;                          wait(full);     // 有产品才取
    wait(empty);    // 有空槽才放          wait(mutex);
    wait(mutex);                           从缓冲区取产品;
    放入缓冲区;                            signal(mutex);
    signal(mutex);                         signal(empty);  // 增加一个空槽
    signal(full);   // 增加一个产品         消费产品;
}                                      }

⚠️ 必须先P资源信号量,再P互斥信号量！反过来必死锁！

  • 错误示例：wait(mutex); wait(empty); → 若缓冲区满,生产者持有mutex等empty,消费者想进入要等mutex → 死锁

哲学家进餐问题

5个哲学家围坐，5根筷子。每人需左右两根筷子才能吃饭。

c
semaphore chopstick[5] = {1, 1, 1, 1, 1};

// 哲学家i
while(1) {
    思考;
    wait(chopstick[i]);         // 拿左
    wait(chopstick[(i+1)%5]);   // 拿右
    进餐;
    signal(chopstick[i]);       // 放左
    signal(chopstick[(i+1)%5]); // 放右
}

可能死锁！（5人同时拿左筷子）

死锁解决方案（任选一）：

  1. 最多4人同时进餐（限制同时拿筷子的人数）
  2. 同时拿起两根筷子（AND信号量）
  3. 奇偶号策略：奇号哲学家先拿左再拿右，偶号先拿右再拿左

读者-写者问题

c
// 读者优先解法
semaphore rmutex = 1;    // 保护readcount
semaphore wmutex = 1;    // 互斥写
int readcount = 0;

// 读者                                // 写者
wait(rmutex);                          wait(wmutex);
    readcount++;                           写操作;
    if(readcount == 1)                 signal(wmutex);
        wait(wmutex);  // 第一个读者锁住写
signal(rmutex);
    读操作;
wait(rmutex);
    readcount--;
    if(readcount == 0)
        signal(wmutex); // 最后一个读者解锁写
signal(rmutex);

第一问题（读者优先）：读者可能导致写者饥饿 第二问题（写者优先）：需增加额外信号量，写者到达后新读者不能读

写者优先思路（补充）

c
// 写者优先常见信号量
semaphore rmutex = 1;    // 保护readcount
semaphore wmutex = 1;    // 写互斥
semaphore readTry = 1;   // 是否允许新读者进入
semaphore wcMutex = 1;   // 保护writecount
int readcount = 0, writecount = 0;

// 写者
wait(wcMutex); writecount++;
if (writecount == 1) wait(readTry);  // 第一位写者到达，阻止新读者
signal(wcMutex);

wait(wmutex); 写操作; signal(wmutex);

wait(wcMutex); writecount--;
if (writecount == 0) signal(readTry); // 最后一位写者离开，放行读者
signal(wcMutex);

要点：readTry 是“闸门”，只要有写者等待，就不再放新读者进入，从而避免写者饥饿。

4.8 Linux同步机制

  • 并发来源：中断、内核态抢占、多处理机
  • 原子操作：lock前缀指令、atomic_t
  • 自旋锁：多处理机忙等,适用短临界区; spin_lock/spin_unlock; 变种rwlock/seqlock
  • 信号量：适用长临界区,可睡眠

🎯 本章真题锚点与最短模板

  • 高频题号（2009-2025）：2009Q45、2010Q27、2011Q45、2014Q47、2015Q45、2017Q46、2018Q32、2019Q43、2020Q45、2021Q45/Q46、2022Q45、2024Q46、2025Q45
  • 优质例题：三线程A/B/C有前驱约束 A→C、B→C、C→D，写出最少信号量与P/V序列。
  • 最短解题模板：
    1. 先画前驱图，给每条“前驱边”分配一个同步信号量。
    2. 每个活动：前驱边对应 P 在前，后继边对应 V 在后。
    3. 共享缓冲区再补 mutex（互斥）+ empty/full（同步）。

⚡ 秒杀版口令卡（10秒回忆）

  • 口令：先前驱后PV，不画图不下笔。
  • 口令：互斥用mutex，同步用前驱信号量。
  • 口令：缓冲区三件套：mutex、empty、full。