互斥读者-读者问题

2017-01-08

在操作系统（专题）：信号量编程（上）中，我对《操作系统概念》原书课后习题 7.16 过桥问题做了一定改动，此部分记录对改动后题目的分析。

注：以下解法均已通过程序验证，不会发生饥饿或死锁，验证代码可在这里查看。

村庄过桥问题

原题大致翻译（原书 7.16）：一座桥连接了南北两个村庄，两个村庄的居民可以从桥上通过，但桥上不能同时承载两个人（无论同方向还是相向）。使用信号量保证死锁和饥饿都不会发生。
我个人对此题编写的信号量解法如下，通过两个互斥信号量均衡双方争夺过桥权限的次数：

int num_waiting_north = 0;
int num_waiting_south = 0;     // 南北方等待过桥人数
semaphore mutex_south = 1;
semaphore mutex_north = 1;     // 南北方等待过桥人数修改互斥锁
semaphore bridge = 1;          // 过桥权限
semaphore north_entry = 1;
semaphore south_entry = 1;             
// 南北参与争夺桥的权限，开始双方均允许争夺

void enter_bridge_north() {    // 北方居民试图过桥
    wait(mutex_north);
    num_waiting_north ++;
    signal(mutex_north);
    wait(north_entry);    
        // 将自己加入等待队列，如果等待队列有资源就可以等待桥资源
    wait(bridge);
    // 过桥
    wait(mutex_north);
    num_waiting_north --;
    signal(mutex_north);
    wait(mutex_south);
    if (num_waiting_south == 0)   
        // 若南方当前无人准备过桥则本次过桥不计入争夺次数
        signal(north_entry);
    else
        // 若南方有居民准备过桥则允许南方等待队列中的一个居民争夺过桥权限
        signal(south_entry);      
    signal(mutex_south);   
    signal(bridge);
}

void enter_bridge_south() {    // 南方居民试图过桥
    // 与北方居民对称
}

互斥读者-读者问题

在操作系统（专题）：信号量编程（下）的 “简单信号量编程” 部分中，北京大学 1992 年的入学考试题实际也是对书后习题 7.16 的改动，即 同一方向允许多辆车依次通过但不允许两辆车相对行驶 ，但未要求不发生饥饿。
再对原题做了一点改变：将原题条件改成同一方向同时允许多个居民依次通过但不允许两个居民相向行走， 同时保证不发生饥饿现象 。 新的题目和原来的两道题目的主要区别 在于：
- 与教材 7.16 相比，教材 7.16 要求桥上任何时刻最多只能有一个人，而新的题目允许桥上同时出现多个同方向的居民。即原题要求依次通过，所以即使是同方向的居民也需要等待；新的题目允许同时通过，即同方向的居民无需等待。
- 与北京大学 1992 入学考试题相比，原题允许同方向多辆车同时通过，但未要求保证不发生饥饿，而新的题目要求保证不发生饥饿现象。
我个人认为改造后的问题等价为读者-写者问题的变种：将读者-写者问题中的写者也换成另一类读者，并且要保证没有饥饿现象。因此我将改造后的问题称作 互斥读者-读者问题 ，只需要对第三读者写者问题中的写者稍作处理就可以使用第三读者写者问题的解法实现。我基于第三读者-写者问题编写的信号量解法如下，解法依赖于信号量自身进程队列的先进先出特性：

int num_waiting_north = 0;
int num_waiting_south = 0;    // 南北等待人数
semaphore north_mutex = 1;
semaphore south_mutex = 1;    // 修改等待人数的互斥锁
semaphore bridge = 1;         // 桥资源
semaphore queue = 1;          // 通过信号量的先进先出维护双方居民顺序

void enter_bridge_north() {   // 北方居民尝试过桥
    wait(queue);
    wait(north_mutex);
    num_waiting_north++;
    if (num_waiting_north == 1)
        // 第一个北方居民要获得桥的通过权
        wait(bridge);
    signal(queue);
    signal(north_mutex);
    // 过桥
    wait(north_mutex);
    num_waiting_north --;
    if (num_waiting_north == 0)
        // 最后一个离开的北方居民交出桥的通过权权
        signal(bridge);
    signal(north_mutex);
}

void enter_bridge_south(){    // 南方居民尝试过桥
    // 与北方居民过桥对称
}

对于上面改造后的问题，通过转换为第三读者-写者问题得到的解法 依赖于信号量进程队列的先进先出特性 。我构想了另一种解法（下面的代码），但我认为这种解法有些过于复杂，并且依赖状态的记录。此算法已经经过程序验证。或者你有另外的解法，请一定要告诉我（在评论中留言或点此向我发送邮件）！

// 其它变量和上面代码相同
bool north_entered = FALSE;
bool south_entered = FALSE;   
// 我方自上次对方通过桥后是否又有人通过桥
semaphore north_entry = 1;
semaphore south_entry = 1;    // 双方居民争夺桥权的资格

void enter_bridge_north() {   // 北方居民过桥
    wait(mutex_north);
    num_waiting_north ++;
    signal(mutex_north);
    wait(north_entry);    
    // 此句必须放置在 num_waiting_north++ 后，否则一方通过后将再无机会
    // 打断对方的权限，直到对方主动交出
    if (num_waiting_north == 1) {
        // 第一个北方居民要获取桥的资源
        wait(bridge);
    }
    north_entered = TRUE;    // 标记北方已经有人通过桥
    if (num_waiting_south == 0)
        // 南方无人等待过桥则允许下一个北方居民过桥
        // 如果南方有人过桥，过桥后一定会再次给北方机会所以跳过此步
        signal(north_entry); 
    // 过桥
    wait(mutex_north);
    num_waiting_north --;
    if (south_entered) { 
        signal(south_entry);
        south_entered = FALSE;
    }
    // 如果有南方居民已经通过桥，则说明 south_entry 为 0，因为最后
    // 一个通过的南方居民没有机会对 south_entry 做 signal。这样最后
    // 一个离开的北方居民需要将 south_entry 置为 1，使南方居民能够获得过桥资格。
    signal(mutex_north);
    signal(bridge);
}

void enter_bridge_south() {    // 南方居民过桥
    // 与北方居民对称
}

专栏目录：计算机理论基础
此专栏的上一篇文章：操作系统（十五）：信号量编程（下）
此专栏的下一篇文章：专栏已结束

参考资料：《操作系统概念英文第七版》，恐龙书，英文名《Operating System Concepts》，作者 Abraham Silberschatz、Peter Baer Galvin、Greg Gagne

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/01/08/os-concepts-16/) 、作者信息（Forec）和本声明。