【操作系统】基于信号量与PV操作解决东西向汽车过独木桥问题

【操作系统】基于信号量与PV操作解决东西向汽车过独木桥问题

问题

东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的汽车全部过完后，另一方的汽车才允许过桥。某一时刻，桥上可以有同方向的多辆车。试用信号量写出同步算法。

思路

定义信号量

• bridge：表示桥的状态，初始值为1。
• east：用于保护东向车辆计数的信号量，初始值为1。
• west：用于保护西向车辆计数的信号量，初始值为1。
• east_count：表示东向等待过桥的车辆数，初始值为0。
• west_count：表示西向等待过桥的车辆数，初始值为0。

东向车辆过桥的过程

1. 进入临界区：等待 east 信号量
2. 增加东向车辆计数
3. 如果是第一个东向车辆，等待 bridge 信号量
4. 离开临界区：释放 east 信号量
5. 过桥
6. 进入临界区：等待 east 信号量
7. 减少东向车辆计数
8. 如果是最后一个东向车辆，释放 bridge 信号量
9. 离开临界区：释放 east 信号量

西向车辆过桥的过程

1. 进入临界区：等待 west 信号量
2. 增加西向车辆计数
3. 如果是第一个西向车辆，等待 bridge 信号量
4. 离开临界区：释放 west 信号量
5. 过桥
6. 进入临界区：等待 west 信号量
7. 减少西向车辆计数
8. 如果是最后一个西向车辆，释放 bridge 信号量
9. 离开临界区：释放 west 信号量

伪代码

semaphore bridge = 1;    // 桥的状态
semaphore east = 1;      // 保护东向车辆计数的信号量
semaphore west = 1;      // 保护西向车辆计数的信号量
int east_count = 0;      // 东向等待过桥的车辆数
int west_count = 0;      // 西向等待过桥的车辆数

cobegin
process east_car() {
    while(true) {
        P(east);
        east_count++;
        if(east_count == 1) {
            P(bridge);  // 第一个东向车辆请求桥
        }
        V(east);
        
        cross_bridge();

        P(east);
        east_count--;
        if(east_count == 0) {
            V(bridge);  // 最后一个东向车辆离开桥
        }
        V(east);
    }
}
coend

cobegin
process west_car() {
    while(true) {
        P(west);
        west_count++;
        if(west_count == 1) {
            P(bridge);  // 第一个西向车辆请求桥
        }
        V(west);

        cross_bridge();

        P(west);
        west_count--;
        if(west_count == 0) {
            V(bridge);  // 最后一个西向车辆离开桥
        }
        V(west);
    }
}
coend