2.3.3 信号量与PV操作

📝 学习目标

• 深入理解信号量的概念和作用
• 熟练掌握P操作和V操作的执行过程
• 能够用PV操作解决经典同步问题
• 理解信号量在操作系统中的实现

🎯 信号量基本概念

什么是信号量

信号量（Semaphore）：

• 由Dijkstra提出的进程同步机制
• 一个非负整数变量，表示可用资源数量
• 只能通过P、V操作进行访问（原子操作）

信号量的类型

类型	取值范围	用途	示例
二元信号量	0或1	互斥访问	临界区保护
计数信号量	≥0	资源计数	缓冲区管理

🔧 PV操作定义

P操作（Wait/Down）

P(S) {
    S = S - 1;
    if (S < 0) {
        将进程加入S的等待队列;
        阻塞进程;
    }
}

含义：

• 申请一个资源
• 如果资源不足，进程阻塞等待

V操作（Signal/Up）

V(S) {
    S = S + 1;
    if (S <= 0) {
        从S的等待队列中唤醒一个进程;
    }
}

含义：

• 释放一个资源
• 如果有等待进程，唤醒一个

📊 PV操作执行过程

示例：信号量S=2

时刻	操作	S值	等待队列	说明
T0	初始	2	空	有2个资源
T1	P1执行P(S)	1	空	P1获得资源
T2	P2执行P(S)	0	空	P2获得资源
T3	P3执行P(S)	-1	P3	P3阻塞等待
T4	P4执行P(S)	-2	P3,P4	P4阻塞等待
T5	P1执行V(S)	-1	P4	P3被唤醒
T6	P2执行V(S)	0	空	P4被唤醒

🏭 经典同步问题

1. 生产者-消费者问题

问题描述：

• 生产者产生数据放入缓冲区
• 消费者从缓冲区取数据
• 缓冲区大小有限

信号量设置：

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

生产者进程：

while(true) {
    生产一个产品;
    P(empty);           // 申请空缓冲区
    P(mutex);           // 进入临界区
    将产品放入缓冲区;
    V(mutex);           // 离开临界区
    V(full);            // 增加满缓冲区
}

消费者进程：

while(true) {
    P(full);            // 申请满缓冲区
    P(mutex);           // 进入临界区
    从缓冲区取出产品;
    V(mutex);           // 离开临界区
    V(empty);           // 增加空缓冲区
    消费产品;
}

2. 读者-写者问题

问题描述：

• 多个读者可以同时读
• 写者与任何进程互斥
• 读者优先 vs 写者优先

读者优先方案：

semaphore mutex = 1;        // 保护readcount
semaphore wrt = 1;          // 写者互斥
int readcount = 0;          // 读者计数

读者进程：

while(true) {
    P(mutex);
    readcount++;
    if(readcount == 1)
        P(wrt);             // 第一个读者阻止写者
    V(mutex);

    执行读操作;

    P(mutex);
    readcount--;
    if(readcount == 0)
        V(wrt);             // 最后一个读者允许写者
    V(mutex);
}

写者进程：

while(true) {
    P(wrt);                 // 申请写权限
    执行写操作;
    V(wrt);                 // 释放写权限
}

3. 哲学家就餐问题

问题描述：

• 5个哲学家围圆桌而坐
• 每人需要两支筷子才能就餐
• 避免死锁和饥饿

解决方案1：奇偶策略

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

// 奇数号哲学家
void philosopher_odd(int i) {
    while(true) {
        P(chopstick[i]);        // 先拿左筷子
        P(chopstick[(i+1)%5]);  // 再拿右筷子
        就餐;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        思考;
    }
}

// 偶数号哲学家
void philosopher_even(int i) {
    while(true) {
        P(chopstick[(i+1)%5]);  // 先拿右筷子
        P(chopstick[i]);        // 再拿左筷子
        就餐;
        V(chopstick[(i+1)%5]);
        V(chopstick[i]);
        思考;
    }
}

🧮 PV操作设计原则

设计步骤

1. 分析问题：

   • 识别进程和资源
   • 找出同步和互斥关系

2. 设置信号量：

   • 互斥信号量：初值为1
   • 资源信号量：初值为资源数量
   • 同步信号量：初值为0

3. 编写PV操作：

   • P操作在使用资源前
   • V操作在释放资源后
   • 注意操作顺序

常见错误

1. 死锁：

   // 错误：可能死锁
   P(S1); P(S2); ... V(S2); V(S1);
   P(S2); P(S1); ... V(S1); V(S2);

2. PV不匹配：

   // 错误：P多V少
   P(S); P(S); ... V(S);  // 缺少一个V操作

3. 顺序错误：

   // 错误：先互斥后同步可能死锁
   P(mutex); P(empty); ...

🔍 信号量实现

硬件实现

Test-and-Set指令：

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

使用TAS实现互斥：

while(TestAndSet(&lock));  // 忙等待
临界区代码;
lock = false;

软件实现

Peterson算法（两进程互斥）：

boolean flag[2] = {false, false};
int turn = 0;

// 进程i进入临界区
flag[i] = true;
turn = j;  // j是另一个进程
while(flag[j] && turn == j);
临界区;
flag[i] = false;

🧮 练习题

基础题

1. PV操作执行

   • 信号量S初值为3
   • 执行序列：P(S), P(S), V(S), P(S), P(S), V(S)
   • 画出S值变化和进程状态

2. 生产者消费者

   • 缓冲区大小为5
   • 2个生产者，3个消费者
   • 设计PV操作

提高题

1. 理发师问题

   • 理发店有1个理发师，n把椅子
   • 顾客来时如果有空椅子就等待，否则离开
   • 设计同步方案

2. 吸烟者问题

   • 3个吸烟者，分别有烟草、纸、火柴
   • 供应者随机提供其中两样
   • 有对应第三样的吸烟者制作香烟并吸烟

答案提示

基础题1：

初始：S=3, 无等待进程
P(S): S=2
P(S): S=1
V(S): S=2
P(S): S=1
P(S): S=0
V(S): S=1

💡 解题技巧

考试要点

1. PV操作含义：P申请资源，V释放资源
2. 信号量类型：互斥(初值1)、资源(初值n)、同步(初值0)
3. 经典问题：生产者消费者、读者写者、哲学家就餐
4. 死锁避免：注意PV操作顺序

解题步骤

1. 理解题意：明确进程关系和约束条件
2. 设置信号量：根据资源和约束设置
3. 编写伪代码：按照PV操作规则编写
4. 检查正确性：验证是否满足同步互斥要求

📚 本课小结

1. 信号量机制：通过PV操作实现进程同步互斥
2. PV操作：P申请资源可能阻塞，V释放资源可能唤醒
3. 经典问题：生产者消费者、读者写者、哲学家就餐
4. 设计原则：正确设置信号量，合理安排PV顺序

---

💪 课后作业

1. 完成所有练习题
2. 分析理发师问题和吸烟者问题的解决方案
3. 思考如何用PV操作实现进程的前趋关系
4. 研究读者写者问题的写者优先方案