同步与互斥

多生产者-多消费者（苹果橘子）

桌上一个盘子，每次只能放一个水果。爸爸只放苹果，妈妈只放橘子；女儿只吃苹果，儿子只吃橘子。盘子空时爸妈才能放；盘里是自己要的水果时，儿女才能取。

关键点

• “多”指多类：不同进程要的产品不同，所以苹果、橘子各一个信号量
• 从事件看关系：“盘子变空”可以由儿子或女儿引发，不用分别给爸妈各设一个
• 缓冲区容量为 1 时，plate 最多为 1，同一时刻最多一个进程能过 P(plate) 或 P(apple/orange)，所以 mutex 可以省；容量 > 1 必须加 mutex

semaphore mutex = 1, plate = 1;
semaphore apple = 0, orange = 0;

dad() {
    while (1) {
        准备一个苹果;
        P(plate);
        P(mutex);
        把苹果放入盘子;
        V(mutex);
        V(apple);
    }
}
mom() {             // 与 dad 对称
    while (1) {
        准备一个橘子;
        P(plate);
        P(mutex);
        把橘子放入盘子;
        V(mutex);
        V(orange);
    }
}
daughter() {
    while (1) {
        P(apple);
        P(mutex);
        从盘中取出苹果;
        V(mutex);
        V(plate);   // 盘子空了
        吃掉苹果;
    }
}
son() {             // 与 daughter 对称
    while (1) {
        P(orange);
        P(mutex);
        从盘中取出橘子;
        V(mutex);
        V(plate);
        吃掉橘子;
    }
}

吸烟者问题

三个抽烟者分别只有烟草、纸、胶水中的一种。供应者每次把另外两种材料放到桌上，缺这两种的那位抽烟者拿走、卷烟、抽完后通知供应者，供应者再放下一组。三位抽烟者轮流抽。

关键点

• 本质：一个生产者、生产多种产品，每种产品对应一个消费者
• 把“两种材料”看成一个组合，一个组合一个信号量
• “轮流”用整型变量 i 实现，每次 i = (i + 1) % 3
• 桌子容量为 1，同一时刻只有一个组合在桌上，不需要 mutex

semaphore offer1 = 0, offer2 = 0, offer3 = 0;
semaphore finish = 0;
int i = 0;          // 轮到哪位抽烟者

provider() {
    while (1) {
        if (i == 0) {
            把组合一放桌上;
            V(offer1);
        } else if (i == 1) {
            把组合二放桌上;
            V(offer2);
        } else {
            把组合三放桌上;
            V(offer3);
        }
        i = (i + 1) % 3;
        P(finish);  // 等抽烟者抽完
    }
}
smoker1() {
    while (1) {
        P(offer1);
        从桌上拿走组合一; 卷烟; 抽掉;
        V(finish);
    }
}
smoker2() {         // P(offer2)，其余同 smoker1
    while (1) {
        P(offer2);
        从桌上拿走组合二; 卷烟; 抽掉;
        V(finish);
    }
}
smoker3() {         // P(offer3)，其余同 smoker1
    while (1) {
        P(offer3);
        从桌上拿走组合三; 卷烟; 抽掉;
        V(finish);
    }
}

读者-写者问题（读优先）

多个读者可以同时读文件；写者写的时候，其他读者、写者都不能访问；写者写之前，已有的读者、写者都要退出。

关键点

• 核心是 count：第一个读者负责 P(rw) 挡住写者，最后一个读者负责 V(rw) 放行写者
• “检查 count == 0”和“count++”必须一气呵成，否则两个读者可能都以为自己是第一个，都去 P(rw)，第二个被阻塞。所以用 rmutex 把这两步包起来
• 缺点：只要读者源源不断，count 永远不归零，写者可能饿死

semaphore rw = 1;      // 文件的互斥
int count = 0;         // 正在读的读者数
semaphore rmutex = 1;  // 保护 count

writer() {
    while (1) {
        P(rw);
        写文件;
        V(rw);
    }
}
reader() {
    while (1) {
        P(rmutex);
        if (count == 0)  // 第一个读者
            P(rw);       // 替所有读者挡住写者
        count++;
        V(rmutex);

        读文件;

        P(rmutex);
        count--;
        if (count == 0)  // 最后一个读者
            V(rw);       // 放写者进来
        V(rmutex);
    }
}

读者-写者（写优先）

在读优先的基础上再加一个信号量 w = 1，读者和写者进门前都先 P(w)。

• 写者来了先 P(w)，并一直占着 w 直到写完。它之后到达的读者卡在 P(w) 上，不能再“插队”进去读
• 写者只需等当前正在读的读者读完，就能进去，不会饿死
• 严格说这是“读写公平”：大家在 w 上按到达顺序排队。王道称为写优先

semaphore w = 1;       // 新增：实现写优先

writer() {
    while (1) {
        P(w);
        P(rw);
        写文件;
        V(rw);
        V(w);
    }
}
reader() {
    while (1) {
        P(w);          // 有写者在排队就进不来
        P(rmutex);
        if (count == 0) P(rw);
        count++;
        V(rmutex);
        V(w);          // 进门后立刻放开 w
        读文件;
        P(rmutex);
        count--;
        if (count == 0) V(rw);
        V(rmutex);
    }
}

哲学家进餐问题

5 名哲学家围坐圆桌，每两人之间一根筷子。哲学家 i 左边是 chopstick[i]，右边是 chopstick[(i+1)%5]，拿到左右两根才能吃。

为什么朴素写法会死锁

每人先拿左、再拿右。若 5 人同时拿起左筷子，每人都在等右边那根，而右边那根正被邻居拿着：循环等待，死锁。

三种防死锁方案

• 最多 n − 1 = 4 人同时拿筷子：5 根筷子分给 4 个人，至少有一人能拿到两根
• 奇偶号不同顺序：奇数号先左后右，偶数号先右后左。相邻两人先争同一根，抢输的直接阻塞，手里不握筷子
• 拿两根筷子整体互斥：用 mutex 把“拿左 + 拿右”包起来。更准确的说法是“各哲学家拿筷子这件事互斥执行”：某人拿到一根后等另一根时占着 mutex，别人连拿都不能拿

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

// 朴素写法：可能死锁
Pi() {
    while (1) {
        P(chopstick[i]);         // 拿左
        P(chopstick[(i+1)%5]);   // 拿右
        吃饭;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        思考;
    }
}

// 方案一：最多 4 人同时拿
semaphore limit = 4;
Pi() {
    while (1) {
        P(limit);
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
        吃饭;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        V(limit);
        思考;
    }
}

// 方案二：奇数号先左后右，偶数号先右后左
Pi() {
    while (1) {
        if (i % 2 == 1) {
            P(chopstick[i]);
            P(chopstick[(i+1)%5]);
        } else {
            P(chopstick[(i+1)%5]);
            P(chopstick[i]);
        }
        吃饭;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        思考;
    }
}

// 方案三：拿筷子整体互斥
semaphore mutex = 1;
Pi() {
    while (1) {
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
        V(mutex);
        吃饭;
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        思考;
    }
}