信号量是操作系统提供的一种协同共享资源访问的方法。

信号量 semaphore s 的取值：
– 当 s > 0 时，表示有 s 个资源可用
– 当 s = 0 时，表示可用资源为 0
– 当 s<0 时，表示可用资源为 0，且有 |s| 个阻塞进程正等待资源分配

三个基础操作

概括来讲，PV 所需要做到得都来自三个基础操作：同步、互斥、交替访问。掌握了这三个，千变万化不离其中。

1.同步 – 即程序的先后顺序

semaphore signal = 0; // 信号量初值设为 0，用于同步
ProcessA() {
    我说完，B 才能说话
    V(signal); // A 执行完后，信号量加 1
}
ProcessB() {
    P(signal); // 若 A 没有得到执行的话，此时 P 操作会使该进程会被阻塞
    A说完，我才能说话
}

2.互斥 – 资源在某一时间段内只能由某个进程所占有

用于互斥时，设置信号量的初值为 1，取值为 1 ~ -(n – 1)。
– s = 1 时：有一个资源可用，一个进程可以进入临界区。
– s = 0 时：有

semaphore mutex = 1; // 信号量初值设为 1，用于互斥
ProcessA() {
    while (true) {
        P(mutex); // 执行 P 操作后，mutex 变成 0，其它进程再执行只能等待
        这个麦克风只有我（A）能用，B 只能等我唱完歌 // 即需要互斥访问的代码
        V(mutex);
    }
}
ProcessB() {
    while (true) {
        P(mutex);
        这个麦克风只有我（B）能用，A 只能等我唱完歌 // 即需要互斥访问的代码
        V(mutex);
    }
}

3.交替访问

假设 A 先说话：

semaphore s1 = 1;
semaphore s2 = 0;
ProcessA() {
    while (true) {
        P(s1);
        我说一句就得停下来，让 B 说一句
        V(s2);
    }
}
ProcessB() {
    while (true) {
        P(s2);
        我说一句也得停下来，让 A 说一句
        V(s1);
    }
}

常见问题总结

• 一、读者、写着问题
• 二、吸烟者问题
• 三、售票问题
• 四、橘子-苹果问题
• 五、理发师问题
• 六、生产与装配车间问题
• 七、缓冲区问题
• 八、哲学家就餐问题
• 九、农夫猎人问题
• 十、银行业务问题
• 十一、黑白棋子问题

一、读者、写着问题

读者写者问题（reader-writer problem(Courtois, 1971)）是一个经典的并发程序设计问题。
有两组并发进程：读者和写者，共享一个数据对象。要求：
1. 允许多个读者进程同时读取。
2. 一次只允许一个写者往文件中写信息。
3. 当一个写者正在写时，不允许其它读者或者写者访问该数据对象。

该问题的解法分为读者优先和写者优先，读者优先就是意味着当至少有一个读者正在读数据时，
后续如果陆陆续续到达读者进程及写者进程，那么只有当所有读者进程进行结束时，写者进程才会得到执行，即产生饥饿现象。

1. 读者优先

只要有读者正在读，后来的读者都能直接进入，如果读者持续不断，则写者处于饥饿状态。

semaphore writeMutex = 1; // 控制对数据对象的写互斥操作
semaphore readMutex = 1; // 控制对 readCount 变量的互斥访问
int readCount = 0;
reader () {
    while (true) {
        P(readMutex);
        if (readCount == 0) {
            P(writeMutex); // 第一个读进程进入后，执行 P 原语禁止写操作
        }
        readCount++;
        V(readMutex);
        读数据
        P(readMutex);
        readCount--;
        if (readCount == 0) {
            V(wiriteMutex); // 最后一个读进程退出后，允许写操作
        }
        V(readMutex);
    }
}
writer() {
    while (true) {
        P(writeMutex);
        写入数据对象
        V(writeMutex);
    }
}

2. 写者优先

当一个进程想写时，不允许新的读者进入数据对象，只有等待已有的写者写完才能读取，避免写者饥饿。
只需要在读者优先基础上加一个新的互斥信号量即可。网上还有其它各种实现方法，写者优先的实现可以有很多种，以下这种方法当有读者进来时，并不会抢占之前已经进入的读者，会阻塞随后进入的读者，并等待之前已经进入读者读完数据再开始写。

int readCount = 0;
semaphore mutex = 1;
semaphore readMutex = 1;
semaphore writeMutex = 1;
reader() {
    P(mutex);
    P(readMutex);
    if (readCount == 0) {
        P(writeMutex);
    }
    readCount++;
    V(readMutex);
    V(mutex);
    读取数据
    P(readMutex);
    readCount--;
    if (readCount == 0) {
        V(writeMutex);
    }
    V(readMutex);
}
writer() {
    P(mutex);
    P(writeMutex);
    写入数据
    V(writeMutex);
    V(mutex);
}

二、吸烟者问题

三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富的货物提供。三个吸烟者中，第一个由自己的烟草，第二个由自己的纸和第三个有自己的火柴。
供应者每次将两样东西放在桌子上，拥有剩下那种材料的吸烟者卷起一根烟并抽掉它，并给供应者一个信号完成了，供应者会再次选择两种材料重复此过程。这个过程会一直重复，让三个吸烟者轮流吸烟。

int i = 0;
semaphore s1 = 0; // 提供第一个吸烟者所需的两种材料
semaphore s2 = 0; // 第二个吸烟者所需材料
semaphore s3 = 0; // 第三个吸烟者所需材料
semaphore mutex = 1; // 互斥，唤醒供应者
provider() {
    while (true) {
        P(mutex);
        if (i == 1) {
            V(s1);
        } else if (i == 2) {
            V(s2);
        } else if (i == 3) {
            V(s3);
        }
        i = (i + 1) % 3;
    }
}
smoker1() {
    while (true) {
        P(s1);
        制作香烟并消耗
        V(mutex);
    }
}
smoker2() {
    while (true) {
        P(s2);
        制作香烟并消耗
        V(mutex);
    }
}
smoker3() {
    while (true) {
        P(s3);
        制作香烟并消耗
        V(mutex);
    }
}

三、售票问题

汽车死机与售票员之间必须协同工作，一方面只有售票员把车门关好了死机才能开机，因此，售票员关好门应通知司机开车，然后售票员进行售票。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应该通知售票员。假定某辆公共汽车上有一名司机与两名售票员，汽车当前正在始发站停车上客。

分析：这里涉及到四个需要同步点：其中两个是一名司机与两名售票员停车，另两个是两名售票员与一名司机得关门，因此需要设计四个用于同步操作的 semaphore 变量。

semaphore stop1 = 0; // 初值为 0，同步信号量，用于司机告知售票员车停下了
semaphore stop2 = 0;
semaphore close1 = 0; // 初值为 0，同步信号量，用于售票员告知司机门关上了
semaphore close2 = 0;
driver() {
    while (true) {
        P(close1);
        P(close2);
        开车
        停车
        V(stop1);
        V(stop2);
    }
}
seller1() {
    // 这个执行过程顺序，当前正在始发站停车上客，意味着需要售票员先通知车门关上。
    while (true) {
        上乘客
        关车门
        V(close1);
        客车行驶，售票
        P(stop1);
        开车门
        下乘客
    }
}
seller2() {
    while (true) {
        上乘客
        关车门
        V(close2);
        客车行驶，售票
        P(stop2);
        开车门
        下乘客
    }
}

四、橘子-苹果问题

一儿一女，只能放一个水果

桌子上有一只盘子，每次只能放入一个水果，爸爸专门向盘子中放苹果，妈妈专门向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。

分析：简单的同步互斥问题。同步，即爸爸放入后女儿才能取苹果，妈妈放入后儿子才能取橘子；互斥，即盘子只能放一个水果。

semaphore orange = 0;
semaphore apple = 0;
semaphore mutex = 1;
father() {
    while (true) {
        P(mutex);
        放苹果
        V(apple);
    }
}
mother() {
    while (true) {
        P(mutex);
        放橘子
        V(orange);
    }
}
son() {
    while (true) {
        P(orange);
        拿橘子
        V(mutex);
    }
}
daughter() {
    while (true) {
        P(apple);
        拿苹果
        V(mutex);
    }
}

一儿一女，可以放N个水果

五、理发师问题

理发店理有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉，一个顾客到来时，它必须叫醒理发师。如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

int CHAIRS = n; // 将 n 声明为常量，表示可供等候的椅子数
int waiting = 0; // 等候中的顾客数量
semaphore customers = 0; // 顾客数量
semaphore barbers = 0; // 理发师状态，初始为0，睡着了
semaphore mutex = 1; // 互斥访问临界区
barber() {
    while (true) {
        P(customers); // 来顾客？
        P(mutex); // 来顾客，则进入临界区
        waiting--; // 等候顾客少一个
        V(barbers); // 理发师准备为顾客理发
        V(mutex); // 退出临界区
        cut_hair(); // 理发师正在立法（非临界区）
    }
}
customer() {
    while (true) {
        P(mutex); // 进入临界区
        if (waiting < CHAIRS) { // 是否有空椅子
            waiting++;
            V(customers); // 唤醒理发师
            V(mutex); // 退出临界区
            P(barbers); // 理发师忙，执行 P 操作阻塞进程，即顾客等待
            get_hair(); // 否则顾客坐下理发
        } else {
            V(mutex); // 人满了，退出临界区
        }
    }
}

六、生产与装配车间问题

某工厂有两个生产车间和一个装配车间，两个生成车间分别生产 A、B 两种零件，装配车间的任务是把 A、B 两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架 F1、F2 上，F1存在零件A，F2存在零件B，F1 和 F2 的容量均为可以存放 10 个零件。装配工人每次从货架上取一个 A 零件和一个 B 零件，然后将其组装成产品。

分析：涉及到类似有缓冲储存的，就设置一个 empty 变量用户表示空闲的数量，一个 full 表示已用的数量，一个mutex 用于互斥访问。

semaphore empty1 = 10; // 对应货架 F1 上的空闲空间
semaphore full1 = 0; // 对应 F1 上 A 产品的数量
semaphore empty2 = 10;
semaphore full2 = 0;
semaphore mutex1 = 1; // 互斥访问 F1
semaphore mutex2 = 1;

workshopA() {
    while (true) {
        P(empty1);
        生产一个 A 产品
        P(mutex1);
        放到F1货架上
        V(mutex1);
        V(full1);
    }
}
workshopB() {
    while (true) {
        P(empty2);
        生产一个 B 产品
        P(mutex2);
        放到F2货架上
        V(mutex2);
        V(full1);
    }
}
worker() {
    while (true) {
        P(full1);
        P(mutex1);
        从货架 F1 上取出一个产品
        V(mutex1);
        V(empty1);

        P(full2);
        P(mutex2);
        从货架 F2 上取出一个产品
        V(mutex2);
        V(empty2);
        组装
    }
}

七、缓冲区问题

容量为 80 的缓冲区

有 n (n > 1) 个进程将字符逐个读入到一个容量为 80 的缓冲区中，当缓冲区满后，由输出进程 Q 负责一次性取走这 80 个字符。这种过程循环往复，请用信号量和 P、V 操作写出 n 个读入进程（P1, P2, …, Pn）和输出进程 Q 能正确工作的动作序列。

char buffer[80];
semaphore empty = 80;
semaphore full = 0;
semaphore mutex = 1;
int count = 0;
Producer-i(i = 1,2,3,...) {
    while (true) {
        P(empty);
        str = getStr(); // 生产一个字符
        P(mutex);
        buffer[count++] = str;
        if (count == 80) {
            V(full);
        }
        V(mutex);
    }
}
Q() {
    while (true) {
        P(full);
        P(mutex);
        for (int i = 0; i < 80; i++) {
            read(buffer[i]);
        }
        count = 0;
        for (int i = 0; i < 80; i++) {
            V(empty);
        }
        V(mutex);
    }
}

八、哲学家就餐问题

有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一直空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿，然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或者右边去取叉子。

分析：这里要注意死锁问题，比如五位哲学家同时拿起右边（或者左边）的叉子，当每位哲学家再试图拿起左边（或者右边）的叉子时，将会出现死锁。有若干种方法可以避免这类死锁：
1. 至多运行 4 位哲学家同时吃通心面；
2. 奇数号哲学家先取左边叉子，再取右边叉子；偶数号反之。
3. 每位哲学家取到手边的两把叉子才开始吃通心面，否则一把叉子也不取。

下面给出提到的第 3 种避免死锁的方法。

semaphore fork[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Philosopher(int i) {
    while (true) {
        P(mutex);
        P(fork[i]);
        P(fork[(i + 1) % 5]);
        V(mutex);
        就餐
        V(fork[i]);
        V(fork[(i + 1) %]);
        思考
    }
}

九、农夫猎人问题

有一个铁笼子，每次只能放入一个动物。猎手向笼中放入老虎，农夫向笼中放入羊；动物园等待取笼中的老虎，饭店等待取笼中的羊。请用P、V操作原语写出同步执行的程序。

semaphore cage = 1;
semaphore tiger = 0;
semaphore sheep = 0;
hunter() {
    while (true) {
        P(cage);
        放入老虎
        V(tiger);
    }
}
farmer() {
    while (true) {
        P(cage);
        放入羊
        V(sheep);
    }
}
zoo() {
    while (true) {
        P(tiger);
        取出老虎
        V(cage);
    }
}
restaurant() {
    while (true) {
        P(sheep);
        取出羊
        V(cage);
    }
}

十、银行业务问题

某大型银行办理人民币储蓄业务，由 n 个储蓄员负责。每个顾客进入银行后先至取号机取一个号，并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增，并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来，就叫下一个号。

semaphore customer_count = 0;
semaphore server_count = n;
semaphore mutex = 1;
customer-i(i = 1, 2, 3,...) {
    取号
    P(mutex);
    等待区找到空沙发坐下
    V(mutex);
    V(customer_count);
    P(server_count);
}
server-i(i = 1, 2, 3,...) {
    while (true) {
        P(customer_count);
        P(mutex);
        被呼号顾客离开沙发走出等待区
        V(mutex);
        为改号客人服务
        客人离开
        V(server_count)
    }
}

十一、黑白棋子问题

在一个盒子里，混装了数量相等的黑白围棋子，现在用自动分拣系统把黑子、白子分开，设分拣系统又两个进程P1和P2，其中 P1 拣白字，P2 拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程取拣；当一个进程拣了一子时，必须让另一个进程去拣。

semaphore s1 = 1;
semaphore s2 = 0;
P1() {
    while (true) {
        P(s1);
        拣白子
        V(s2);
    }
}
P2() {
    while (true) {
        P(s2);
        拣黑子
        V(s1);
    }
}