信号量机制与经典同步问题

复习定位

信号量是一个整数变量——通过P(wait)和V(signal)两个原子操作实现进程同步。P使信号量减1——若结果<0则阻塞；V使信号量加1——若结果≤0则唤醒一个阻塞进程。信号量最经典的应用是解决同步问题——生产者-消费者(管缓冲区空间)、读者-写者(确定读/写亲密度和公平性等逻辑)、哲学家进餐(避免死锁)。

信号量的定义与原子性

信号量Semaphore是一个整数S——只能通过以下两个不可分割(原子)的操作访问：

wait(S): // P操作
    while (S <= 0) ; // 忙等或进入阻塞队列
    S--;

signal(S): // V操作
    S++;
    if (S <= 0) // 如果有进程在等待——唤醒一个
        wakeup(等待队列);

P操作中——"判断S是否≤0"和"S--"必须连续执行——不可被中断——否则可能两个进程同时判断S>0同时进入临界区。原子性在单核CPU上通过"关中断"实现——多核通过硬件原子指令(TSL,CAS)实现。

用信号量实现互斥

semaphore mutex = 1; // 初始为1——表示没有进程在临界区内

// 进程进入临界区前
wait(mutex);
// 临界区代码
signal(mutex);
// 离开临界区后

P(mutex)将mutex减为0——其他进程再P(mutex)时阻塞——直到当前进程V(mutex)使mutex恢复为1并唤醒一个等待者。在多进程之间——mutex确保了同时只有一个进程进入临界区。

生产者-消费者问题(有界缓冲)

生产者进程向缓冲区写入数据——消费者进程从缓冲区读取数据。两个同步条件：

1. 缓冲区满时——生产者必须等待消费者消费。
2. 缓冲区空时——消费者必须等待生产者生产。

semaphore empty = N; // 空缓冲区数量——初始N
semaphore full = 0;  // 满缓冲区数量——初始0
semaphore mutex = 1; // 保护缓冲区访问的互斥

// 生产者
wait(empty);
wait(mutex);
// 向缓冲区写入数据
signal(mutex);
signal(full);

// 消费者
wait(full);
wait(mutex);
// 从缓冲区读取数据
signal(mutex);
signal(empty);

注意：wait(empty)和wait(full)的顺序要在wait(mutex)之前——如果先wait(mutex)再wait(empty)——缓冲区满时生产者会持有mutex等待empty——消费者因无法获得mutex进不去缓冲区从而无法signal(empty)——导致死锁。

读者-写者问题

读者只读数据——多个读者可以同时读。写者必须独占——正在写时——读者和其他写者不得访问。

读者优先方案——用一个信号量rw_mutex=1控制写操作——用一个read_count计数读者数量。

// 读者
wait(mutex);
    read_count++;
    if (read_count == 1) wait(rw_mutex); // 第一个读者锁住写者
signal(mutex);
// 读数据
wait(mutex);
    read_count--;
    if (read_count == 0) signal(rw_mutex); // 最后一个读者唤醒写者
signal(mutex);

// 写者
wait(rw_mutex);
// 写数据
signal(rw_mutex);

读者优先可能导致写者饥饿——如果连续读者不断到达——写者永远无法获得rw_mutex。

复习检查

1. 信号量P操作——"检查S是否≤0"和"S--"为什么必须是原子操作——如果不原子——两个进程同时测试S=1、都判断S>0、同时进入临界区——互斥失败。

2. 生产者-消费者中——如果wait(mutex)和wait(empty)的顺序颠倒——当缓冲区满时——会出现怎样的死锁？

3. 读者-写者——读者优先方案中——read_count变量为什么需要一个mutex保护(因为多个读者可能并发修改read_count——需要互斥保护)。

4. 读者-写者——如何改造为写者优先(可以用额外的信号量——读进程在写者等待时——不再继续往后读)。

5. 信号量的值能表示什么——正数表示剩余可用资源数——0表示无资源——负数表示有|S|个进程在该信号量上等待。