Linux 内核信号量(semaphore) __down() 函数浅析

Linux 共有两种信号量——内核信号量和System V IPC 信号量，这里仅讨论内核信号量所用到的子程序 __down()（Linux 2.6.11.12） ，其他讨论见《深入理解Linux内核》（Understanding the Linux Kernel, 2nd edition, 中文版211页，英文版208页，顺带对国人翻译书名的功力表示称（tu）赞（cao））。

这里先放一下主要的代码，方便后面讨论

// file: include/asm-i386/semaphore.h
struct semaphore {
    atomic_t count;
    int sleepers;
    wait_queue_head_t wait;
};


// file: arch/i386/kernel/semaphore.c
fastcall void __sched __down(struct semaphore * sem)
{
    struct task_struct *tsk = current;
    DECLARE_WAITQUEUE(wait, tsk);
    unsigned long flags;

    tsk->state = TASK_UNINTERRUPTIBLE;
    spin_lock_irqsave(&sem->wait.lock, flags);
    add_wait_queue_exclusive_locked(&sem->wait, &wait);

    sem->sleepers++;
    for (;;) {
        int sleepers = sem->sleepers;

        /*
         * Add "everybody else" into it. They aren't
         * playing, because we own the spinlock in
         * the wait_queue_head.
         */
        if (!atomic_add_negative(sleepers - 1, &sem->count)) {
            sem->sleepers = 0;
            break;
        }
        sem->sleepers = 1;  /* us - see -1 above */
        spin_unlock_irqrestore(&sem->wait.lock, flags);

        schedule();

        spin_lock_irqsave(&sem->wait.lock, flags);
        tsk->state = TASK_UNINTERRUPTIBLE;
    }
    remove_wait_queue_locked(&sem->wait, &wait);
    wake_up_locked(&sem->wait);
    spin_unlock_irqrestore(&sem->wait.lock, flags);
    tsk->state = TASK_RUNNING;
}

若欲获取信号量时，可调用down()函数，down()原子地(atomic)将sem->count减1并检查它是否小于0。结果大于或等于0，说明资源可用（由于semaphore通常用于保护某一资源，在不引起歧义的情况下，文中之semaphore与“资源”二者可互换，表意相同），down()函数立即返回。否则，表明此时该资源被其他进程所占用，down()即调用__down()，以等待其他进程释放资源。


__down()函数中最令人费解的，莫过于下面这么一小段

if (!atomic_add_negative(sleepers - 1, &sem->count)) {
    sem->sleepers = 0;
    break;
}

注： atomic_add_negative(int i, atomic_t *v)将i加到*v，并测试*v是否为负。

即便是结合那少有的注释，也颇为费解。下面分两种情形讨论：

1. 只有一个进程等待信号量

此时，由于down()里的减一操作，现在有count == -1，执行上面的if语句时，sleepers == 1，结果呢，atomic_add_negative(sleepers - 1, &sem->count)并不改变count的大小（即该表达式执行后，count仍为-1），从而表达式返回真，加上前面的!运算符，使得if内代码块(block)并不执行。

随即，进程将sem->sleepers设为1，调用schedule()切换至其他进程（注意，此时进程状态为TASK_UNINTERRUPTIBLE，除非有人从等待队列上唤醒他（通常，由up()唤醒，下面会看到，__down()函数也可能会唤醒等待队列中的进程），不然进程将会一直休眠）。

突然，资源的拥有者释放该信号量(++count)，并唤醒等待队列中的进程（这里，队列中仅有一个进程）。随即，该醒来的进程再次执行至上面的if语句，此时，由于count == 1，if的条件测试将成立，此时函数返回，刚进程成为资源的拥有者（之一）。

2. 多个进程同时抢夺资源

假设现在有多个进程执行至__down()的临界区（critical section）前，由于每个进程都在down()函数中对sem->count减一，此时，sem->count必然小于-1。

然后，第一个获得锁的进程进入临界区，和情况1一样分析的一样，if的条件测试失败，旋即将sem->sleepers设置为1并调用schedule()，此时，sem->count并未发生变化。

接着，第二个进程进入临界区，执行sem->sleepers++后，sleepers == 2，于是，在if语句的条件测试中，sem->count将加1。尽管如此，count仍为负。与第一个进程一样，他将sleepers设置为1后（这一步非常关键），调用schedule()。

再往后，第三个进程也开始执行临界区中的代码，和第二个一样，他将count加1后，便继续休眠。

现在，我们应该能够理解源代码中注释那句 Add “everybody else” into it 的含义了。除了第一个（或者说，等待队列中的某一个），其他线程都将count加1，而每个进程都对count执行减1操作，最后，count将等于-1。其结果就像，虽然有多个进程在等待，但在临界区的那一个眼里，就像只有自己在等待资源一样（count == -1, sleepers == 1）。

终于，信号量被释放，count增加1。等待队列也被唤醒。某个幸运儿又一次执行到那个if语句。现在，count == 0，于是，if语句块终于得以重见天日，进程获得资源了！。他将自己移出等待队列，并唤醒其他进程（semaphore初始值可能大于1，多个进程可以同时获得资源）。

假设，semaphore的初值为1（即，一个mutex）。于是便有count == 0, sleepers == 0。此时，另一个进程醒来，继续执行schedule()后的代码，马上的，又遇到了我们的老朋友——那个if语句。测试语句再次被执行后，结果有了count == -1。紧接着，执行sem->sleepers = 1。好了，一切都归于平静，又回到了count == -1, sleepers == 1。

故事基本就到这里结束了，虽然有多个进程同时争夺信号量，他们依然可以和谐共处，一切都是那么的美好，优雅。