003-信号量与PV操作

难度：🟡中级 | 预计时间：60-90分钟 | 前置：002-进程管理基础

学习目标

• 理解信号量的概念和作用机制
• 掌握P操作和V操作的原理和实现
• 学会使用信号量解决进程同步和互斥问题
• 掌握经典同步问题的解决方案
• 理解死锁的概念和预防策略

信号量基础概念

什么是信号量

信号量（Semaphore）是由荷兰计算机科学家Dijkstra在1965年提出的一种同步原语，用于解决进程间的同步和互斥问题。

信号量的本质：

• 一个非负整数变量
• 只能通过两个原子操作P和V来访问
• 用于控制对共享资源的访问

信号量的类型

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

信号量的结构

// 文件路径: kernel/semaphore.h
typedef struct {
    int value;              // 信号量的值
    struct process *list;   // 等待队列
} semaphore;

PV操作详解

P操作（Wait操作）

P操作也称为Wait操作或Down操作，用于申请资源。

// 文件路径: kernel/semaphore.c
void P(semaphore *s) {
    s->value--;
    if (s->value < 0) {
        // 将当前进程加入等待队列
        add_to_queue(s->list, current_process);
        // 阻塞当前进程
        block(current_process);
    }
}

P操作的语义：

1. 信号量值减1
2. 如果结果为负，进程被阻塞
3. 如果结果非负，进程继续执行

V操作（Signal操作）

V操作也称为Signal操作或Up操作，用于释放资源。

// 文件路径: kernel/semaphore.c
void V(semaphore *s) {
    s->value++;
    if (s->value <= 0) {
        // 从等待队列中取出一个进程
        process *p = remove_from_queue(s->list);
        // 唤醒该进程
        wakeup(p);
    }
}

V操作的语义：

1. 信号量值加1
2. 如果结果小于等于0，唤醒一个等待进程
3. 被唤醒的进程进入就绪状态

PV操作的原子性

信号量解决同步问题

互斥问题

使用二元信号量实现临界区的互斥访问：

// 文件路径: examples/mutex_example.c
semaphore mutex = 1;  // 初始化为1

void process_i() {
    while (true) {
        P(&mutex);        // 进入临界区
        // 临界区代码
        critical_section();
        V(&mutex);        // 离开临界区
        // 非临界区代码
        non_critical_section();
    }
}

同步问题

使用信号量实现进程间的同步：

// 文件路径: examples/sync_example.c
semaphore sync = 0;   // 初始化为0

void producer() {
    while (true) {
        produce_item();
        V(&sync);         // 通知消费者
    }
}

void consumer() {
    while (true) {
        P(&sync);         // 等待生产者
        consume_item();
    }
}

经典同步问题

生产者-消费者问题

问题描述：

• 生产者进程生产产品放入缓冲区
• 消费者进程从缓冲区取出产品消费
• 缓冲区大小有限

// 文件路径: examples/producer_consumer.c
#define BUFFER_SIZE 10

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

int buffer[BUFFER_SIZE];
int in = 0, out = 0;

void producer() {
    int item;
    while (true) {
        item = produce_item();
        P(&empty);              // 等待空缓冲区
        P(&mutex);              // 互斥访问
        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;
        V(&mutex);              // 释放互斥
        V(&full);               // 增加满缓冲区
    }
}

void consumer() {
    int item;
    while (true) {
        P(&full);               // 等待满缓冲区
        P(&mutex);              // 互斥访问
        item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        V(&mutex);              // 释放互斥
        V(&empty);              // 增加空缓冲区
        consume_item(item);
    }
}

读者-写者问题

问题描述：

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

// 文件路径: examples/reader_writer.c
semaphore rw_mutex = 1;     // 读写互斥
semaphore mutex = 1;        // 保护read_count
int read_count = 0;         // 读者计数

void reader() {
    while (true) {
        P(&mutex);
        read_count++;
        if (read_count == 1) {
            P(&rw_mutex);       // 第一个读者阻塞写者
        }
        V(&mutex);
        
        // 读取数据
        read_data();
        
        P(&mutex);
        read_count--;
        if (read_count == 0) {
            V(&rw_mutex);       // 最后一个读者释放写者
        }
        V(&mutex);
    }
}

void writer() {
    while (true) {
        P(&rw_mutex);           // 写者独占
        // 写入数据
        write_data();
        V(&rw_mutex);
    }
}

哲学家就餐问题

问题描述：

• 5个哲学家围圆桌而坐
• 每两个哲学家之间有一根筷子
• 哲学家需要两根筷子才能就餐

// 文件路径: examples/philosopher.c
#define N 5
semaphore chopstick[N] = {1, 1, 1, 1, 1};

void philosopher(int i) {
    while (true) {
        think();
        
        // 避免死锁的解决方案：奇数号先拿左筷子，偶数号先拿右筷子
        if (i % 2 == 0) {
            P(&chopstick[i]);           // 拿左筷子
            P(&chopstick[(i+1) % N]);   // 拿右筷子
        } else {
            P(&chopstick[(i+1) % N]);   // 拿右筷子
            P(&chopstick[i]);           // 拿左筷子
        }
        
        eat();
        
        V(&chopstick[i]);               // 放下左筷子
        V(&chopstick[(i+1) % N]);       // 放下右筷子
    }
}

死锁问题

死锁的定义

死锁是指两个或多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象。

死锁产生的四个必要条件

条件	描述	示例
互斥条件	资源不能被多个进程同时使用	打印机只能被一个进程使用
请求和保持条件	进程已获得资源，又请求新资源被阻塞时，不释放已获得的资源	进程持有A资源，请求B资源
不剥夺条件	进程已获得的资源不能被强制剥夺	系统不能强制回收进程的资源
环路等待条件	存在进程资源的循环等待链	P1等P2，P2等P1

死锁的预防策略

银行家算法

银行家算法是一种死锁避免算法：

// 文件路径: examples/banker_algorithm.c
#define MAX_PROCESS 10
#define MAX_RESOURCE 10

int available[MAX_RESOURCE];        // 可用资源
int max[MAX_PROCESS][MAX_RESOURCE]; // 最大需求
int allocation[MAX_PROCESS][MAX_RESOURCE]; // 已分配
int need[MAX_PROCESS][MAX_RESOURCE];       // 还需要

bool is_safe() {
    bool finish[MAX_PROCESS] = {false};
    int work[MAX_RESOURCE];
    
    // 初始化工作向量
    for (int i = 0; i < resource_num; i++) {
        work[i] = available[i];
    }
    
    // 寻找安全序列
    for (int count = 0; count < process_num; count++) {
        int found = -1;
        for (int i = 0; i < process_num; i++) {
            if (!finish[i]) {
                bool can_allocate = true;
                for (int j = 0; j < resource_num; j++) {
                    if (need[i][j] > work[j]) {
                        can_allocate = false;
                        break;
                    }
                }
                if (can_allocate) {
                    found = i;
                    break;
                }
            }
        }
        
        if (found == -1) {
            return false; // 不安全状态
        }
        
        // 模拟进程完成，释放资源
        finish[found] = true;
        for (int j = 0; j < resource_num; j++) {
            work[j] += allocation[found][j];
        }
    }
    
    return true; // 安全状态
}

可视化与UML

信号量状态图

生产者消费者时序图

实践练习

练习1：实现信号量

编写一个简单的信号量实现，包括初始化、P操作和V操作。

验收点：

• 正确实现原子操作
• 正确处理进程阻塞和唤醒
• 通过互斥测试

练习2：解决理发师问题

有一个理发师、一把理发椅、n把等待椅。使用信号量解决同步问题。

验收点：

• 正确处理顾客等待
• 避免死锁和饥饿
• 理发师正确休眠和唤醒

练习3：实现读写锁

使用信号量实现读写锁，支持多读者单写者。

验收点：

• 多个读者可以并发读取
• 写者与所有进程互斥
• 避免读者饥饿或写者饥饿

练习4：死锁检测算法

实现一个简单的死锁检测算法。

验收点：

• 正确构建资源分配图
• 准确检测死锁环路
• 输出死锁进程列表

练习5：银行家算法实现

完整实现银行家算法，包括安全性检查和资源分配。

验收点：

• 正确计算need矩阵
• 准确判断系统安全性
• 合理分配资源请求

常见问题（FAQ）

Q1：为什么PV操作必须是原子操作？

A1：如果PV操作不是原子的，可能出现以下问题：

• 竞态条件：多个进程同时修改信号量值
• 数据不一致：信号量值与实际状态不符
• 死锁：进程在操作过程中被中断

解决方法：

• 使用硬件原子指令（如Test-and-Set）
• 关中断实现临界区
• 使用自旋锁保护

Q2：信号量初值如何确定？

A2：信号量初值的确定原则：

• 互斥信号量：初值为1，表示资源可用
• 同步信号量：初值为0，表示事件未发生
• 资源信号量：初值为资源数量

错误示例：

semaphore mutex = 0;  // 错误：会导致死锁

正确示例：

semaphore mutex = 1;  // 正确：允许一个进程进入

Q3：如何避免信号量使用中的死锁？

A3：避免死锁的策略：

• 有序申请：按固定顺序申请资源
• 超时机制：设置等待超时
• 死锁检测：定期检测并解除死锁

死锁示例：

// 进程1
P(&s1); P(&s2);
// 进程2  
P(&s2); P(&s1);  // 可能死锁

避免死锁：

// 两个进程都按相同顺序申请
P(&s1); P(&s2);

Q4：生产者消费者问题中PV操作的顺序为什么重要？

A4：操作顺序影响程序正确性：

错误顺序（可能死锁）：

// 生产者
P(&mutex);  // 先获取互斥锁
P(&empty);  // 再等待空缓冲区 - 可能死锁

正确顺序：

// 生产者
P(&empty);  // 先等待资源
P(&mutex);  // 再获取互斥锁

Q5：如何处理信号量的优先级反转问题？

A5：优先级反转的解决方案：

• 优先级继承：低优先级进程继承高优先级
• 优先级天花板：设置资源访问的最高优先级
• 避免嵌套锁：减少锁的嵌套使用

总结

本章深入学习了信号量与PV操作的核心概念：

1. 信号量机制：理解了信号量作为同步原语的本质和作用
2. PV操作：掌握了P操作和V操作的语义和实现原理
3. 同步问题：学会了使用信号量解决互斥和同步问题
4. 经典问题：深入分析了生产者消费者、读者写者、哲学家就餐等经典同步问题
5. 死锁处理：理解了死锁的产生条件和预防、避免、检测策略

信号量是操作系统中最重要的同步机制之一，为进程间协作提供了强大而灵活的工具。

下一步

接下来将学习 004-死锁问题，深入探讨：

• 死锁的形成机制和检测算法
• 死锁预防和避免的具体策略
• 死锁解除的方法和代价分析
• 实际系统中的死锁处理机制

建议在继续之前：

• 完成本章的所有实践练习
• 理解各种同步问题的解决思路
• 熟练掌握PV操作的使用方法

参考与引用

1. 经典教材：

   • 《操作系统概念》(第9版) - Abraham Silberschatz
   • 《现代操作系统》(第4版) - Andrew S. Tanenbaum
   • 《操作系统设计与实现》- Andrew S. Tanenbaum

2. 学术论文：

   • Dijkstra, E. W. (1965). “Solution of a problem in concurrent programming control”
   • Hoare, C. A. R. (1974). “Monitors: An operating system structuring concept”

3. 在线资源：

   • Linux内核信号量实现
   • POSIX信号量标准

更新记录

• 更新时间: 2024-01-15 | 更新内容: 创建信号量与PV操作章节，包含基础概念、经典问题和死锁处理 | 更新人: Assistant