Robbie Mosaic's Web Log

• 

猴子过桥问题的试解

猴子过桥问题是操作系统课本上的一个同步问题，见于塔嫩鲍姆的操作系统设计与实现第二版。今天是2012年8月15日，而昨天晚上我躺在床上睡觉时，想到了这个问题的一个答案。

问题概述：在两个相对的悬崖间，有一根绳子。悬崖两边有许多猴子，分别要到对面去。其中有一些属性，比如不能让不同方向的猴子同时处于绳上，同一方向的猴子必须依次通过等等。问，如何使用同步原语解决这个问题？

为了解决这个问题，我想到了以下的模型：一个表示当前方向的整数direction（0表示没有猴子在绳上，1表示猴子向右爬，2表示向左），一个表示当前方向上有几只猴子的整数count，一个用于保护前面两个变量的互斥量mutex。绳子上的步骤可以有多步，每一步都用一个独立的信号量step_semaphore[i]表示它是否有猴子在爬，总的步数step_count，一个通知当前方向的猴子是否已全部爬过的信号量rope_semaphore。（我一开始的想法里面有些东西没弄对，比如，想用两个信号量，分别控制两个方向。）

算法概述：

{
第一个猴子上绳：
down(mutex)
if direction == 0:
    # first monkey
    direction = self.direction
    count = 1
    down(step_semaphore[0]) # for now nobody has occupied the rope
    # if someone downed step_semaphore[0], it must have changed `direction'
    down(rope_semaphore)
    self.step = 0
    up(mutex)
elif direction == self.direction:
    ...
else:
    ...
第二个或后续猴子上绳：
down(mutex)
if direction == 0:
    ...
elif direction == self.direction:
    # followup monkey
    count += 1
    up(mutex)
    # not the first one so step_semaphore[0] can cause deadlock if downed
    # before upping mutex
    # QUESTIONS: 1. if all ahead ones quit; a: it won't up rope_semaphore; 2.
    # if more monkeys come; a: they'll compete on step_semaphore, which will be
    # judged by the OS
    down(step_semaphore[0])
    self.step = 0
else:
    ...
反方向猴子想要上绳：
while True:
    down(mutex)
    if direction == 0:
        ...
    elif direction == self.direction:
        ...
    else:
        # opposite direction monkey
        up(mutex)
        # QUESTIONS: 1. if all other direction ones quit; a: it will get
        # rope_semaphore; 2. if more monkeys come; a: they'll compete first on
        # rope_semaphore, then on mutex, which will be judged by the OS
        down(rope_semaphore)
        up(rope_semaphore)
        # now loop back to try again; note that we can't down mutex before the
        # up because doing this would break the lock order, which may lead to
        # dead lock
正方向猴子完成一步工作：
do_work()
if self.step + 1 < step_count:
    # it doesn't make much sense to up the semaphore without downing the next,
    # and that may even lead to wrong order
    down(step_semaphore[self.step + 1])
    up(step_semaphore[self.step])
    self.step += 1
else:
    # quit the rope
    down(mutex)
    # the up for step_semaphore is safe here
    up(step_semaphore[self.step])
    count -= 1
    if count == 0:
        direction = 0
        up(rope_semaphore)
    up(mutex)
    self.step = -1
}

规律总结：所有连续的down操作，只要能在检查mutex所保护的变量后保证马上成功，都在mutex信号量down的时候进行。所有不能保证马上获得的信号量则除外。所有down操作，只要之前有过up操作的，都要考虑此过程中是否有别的线程插入的情况，并将其抽象为一些同类状态，想办法合并多次操作后的状态为其中的一类，还要考虑嵌套的插入情况。