信号量

信号量这个东西，从本质上说，它实现了一个加锁原语，即让等待者睡眠，直到等待的资源变为空闲。

实际上，Linux提供两种信号量：
- 内核信号量，由内核控制路径使用
- System V IPC信号量，由用户态进程使用

在本专题，我们集中讨论内核信号量，而IPC信号量将有专门的专题来讲。

内核信号量类似于自旋锁，因为当锁关闭着时，它不允许内核控制路径继续进行。然而，当内核控制路径试图获取内核信号量所保护的忙资源时，相应的进程被挂起，其task_struck结构被从rq上脱链。只有在资源被释放时，进程才再次变为可运行的。因此，只有可以睡眠的函数才能获取内核信号量；中断处理程序和可延迟函数都不能使用内核信号量。回忆一下，如果中断处理程序或者其下半部如果睡眠了会怎样？中断处理程序是代表进程执行的，它所代表的进程必须总处于TASK_RUNNING状态；再回忆一下，Linux把紧随中断要执行的操作分为三类，紧急的（禁止可屏蔽中断）、非紧急的（开中断但不许延迟）、非紧急可延迟（由下半部执行）；这些都不能睡眠，否则内核控制路径就断了，系统就崩溃了！

内核信号量是struct semaphore类型的对象，包含下面这些字段：
struct semaphore {
atomic_t count;
int sleepers;
wait_queue_head_t wait;
};

count：
存放atomic_t类型的一个值。如果该值大于0，那么资源就是空闲的，也就是说，该资源现在可以使用。相反，如果count等于0，那么信号量是忙的，但没有进程等待这个被保护的资源。最后，如果count为负数，则资源是不可用的，并至少有一个进程等待资源，count为-n，则有n个进程在等待资源。

wait：
存放等待队列链表的地址，当前等待资源的所有睡眠进程都放在这个链表中。当然，如果count大于或等于0，等待队列就为空。

sleepers：
存放一个标志，表示是否有一些进程在信号量上睡眠。我们很快就会看到这个字段的作用。

可以用init_MUTEX()和init_MUTEX_LOCKED()函数来初始化互斥访问所需的信号量：
static inline void init_MUTEX (struct semaphore *sem)
{
sema_init(sem, 1);
}
static inline void init_MUTEX_LOCKED (struct semaphore *sem)
{
sema_init(sem, 0);
}
static inline void sema_init (struct semaphore *sem, int val)
{
atomic_set(&sem->count, val);
sem->sleepers = 0;
init_waitqueue_head(&sem->wait);
}

这两个函数分别把count字段设置成1（互斥访问的资源空闲）和0（对信号量进行初始化的进程当前互斥访问的资源忙）。

宏DECLARE_MUTEX和DECLARE_MUTEX_LOCKED完成同样的功能，但它们也静态分配semaphore结构的变量：
#define DECLARE_MUTEX(name) __DECLARE_SEMAPHORE_GENERIC(name,1)
#define DECLARE_MUTEX_LOCKED(name) __DECLARE_SEMAPHORE_GENERIC(name,0)

#define __DECLARE_SEMAPHORE_GENERIC(name,count) /
struct semaphore name = __SEMAPHORE_INITIALIZER(name,count)

#define __SEMAPHORE_INITIALIZER(name, n) /
{ /
.count = ATOMIC_INIT(n), /
.sleepers = 0, /
.wait = __WAIT_QUEUE_HEAD_INITIALIZER((name).wait) /
}

注意，也可以把信号量中的count初始化为任意的正数值n，在这种情况下，最多有n个进程可以并发地访问这个资源。

1 获取和释放信号量

让我们从如何释放一个信号量来开始讨论，这比获取一个信号量要简单得多。当进程希望释放内核信号量锁时，就调用up()函数：
static inline void up(struct semaphore * sem)
{
__asm__ __volatile__(
"# atomic up operation/n/t"
LOCK_PREFIX "incl %0/n/t" /* ++sem->count */
"jle 2f/n"
"1:/n"
LOCK_SECTION_START("")
"2:/tlea %0,%%eax/n/t"
"call __up_wakeup/n/t"
"jmp 1b/n"
LOCK_SECTION_END
".subsection 0/n"
:"+m" (sem->count)
:
:"memory","ax");
}

这个函数本质上等价于下列汇编语言片段：
movl $sem->count,%ecx
lock; incl (%ecx)
jg 1f
lea %ecx,%eax
pushl %edx
pushl %ecx
call __up
popl %ecx
popl %edx
1:
这里__up()是下列C函数：
__attribute__((regparm(3))) void _ _up(struct semaphore *sem)
{
wake_up(&sem->wait);
}

up()函数增加*sem信号量count字段的值，然后，检查它的值是否大于0。count的增加及其后jump指令所测试的标志的设置都必须原子地执行；否则，另一个内核控制路径有可能同时访问这个字段的值，这会导致灾难性的后果。如果count大于0，说明没有进程在等待队列上睡眠，因此，什么事也不做。否则，调用__up()函数以唤醒一个睡眠的进程。注意，__up()从eax寄存器接受参数（参见前面博文对函数__switch_to()的说明）。

相反，当进程希望获取内核信号量锁时，就调用down()函数。down()的实现相当棘手，但本质上等价于下列代码：
down:
movl $sem->count,%ecx
lock; decl (%ecx);
jns 1f
lea %ecx, %eax
pushl %edx
pushl %ecx
call _ _down
popl %ecx
popl %edx
1:
这里，__down()是下列C函数：
__attribute__((regparm(3))) void _ _down(struct semaphore * sem)
{
DECLARE_WAITQUEUE(wait, current);
unsigned long flags;
current->state = TASK_UNINTERRUPTIBLE;
spin_lock_irqsave(&sem->wait.lock, flags);
add_wait_queue_exclusive_locked(&sem->wait, &wait);
sem->sleepers++;
for (;;) {
if (!atomic_add_negative(sem->sleepers-1, &sem->count)) {
sem->sleepers = 0;
break;
}
sem->sleepers = 1;
spin_unlock_irqrestore(&sem->wait.lock, flags);
schedule( );
spin_lock_irqsave(&sem->wait.lock, flags);
current->state = TASK_UNINTERRUPTIBLE;
}
remove_wait_queue_locked(&sem->wait, &wait);
wake_up_locked(&sem->wait);
spin_unlock_irqrestore(&sem->wait.lock, flags);
current->state = TASK_RUNNING;
}

down()函数减少*sem信号量的count字段的值，然后检查该值是否为负。该值的减少和检查过程都必须是原子的。如果count大于或等于0，当前进程获得资源并继续正常执行。否则，count为负，当前进程必须挂起。把一些寄存器的内容保存在栈中，然后调用__down()。

从本质上说，__down()函数把当前进程的状态从TASK_RUNNING改变为TASK_UNINTERRUPTIBLE，并把进程放在信号量的等待队列。该函数在访问信号量结构的字段之前，要获得用来保护信号量等待队列的sem->wait.lock自旋锁（参见博文“非运行状态进程的组织”），并禁止本地中断。通常当插人和删除元素时，等待队列函数根据需要获取和释放等待队列的自旋锁。函数__down()也用等待队列自旋锁来保护信号量数据结构的其他字段，以使在其他CPU上运行的进程不能读或修改这些字段。最后，__down()使用等待队列函数的“_locked”版本，它假设在调用等待队列函数之前已经获得了自旋锁。

__down()函数的主要任务是挂起当前进程，直到信号量被释放。然而，要实现这种想法是并不容易。为了容易地理解代码，要牢记如果没有进程在信号量等待队列上睡眠，则信号量的sleepers字段通常被置为0，否则被置为1。让我们通过考虑几种典型的情况来解释代码：
MUTEX信号量打开了（count等于1，sleepers等于0）

down宏仅仅把count字段置为0，并跳到主程序的下一条指令；因此，__down()函数根本就不执行。

MUTEX信号量关闭，没有睡眠进程（count等于0, sleepers等于0）

down宏减count并将count字段置为-1且sleepers字段置为0来调用__down()函数。在循环体的每次循环中，该函数检查count字段是否为负。（因为当调用atomic_add_negative()函数时，sleepers等于0，因此atomic_add_negative()不改变count字段。）

- 如果count字段为负，__down()就调用schedule()挂起当前进程。count字段仍然置为-1，而sleepers字段置为1。随后，进程在这个循环内恢复自己的运行并又进行测试。

- 如果count字段不为负，则把sleepers置为O，并从循环退出。__down()试图唤醒信号量等待队列中的另一个进程（但在我们的情景中，队列现在为空），并终止保持的信号量。在退出时，count字段和sleepers字段都置为0，这表示信号量关闭且没有进程等待信号量。

MUTEX信号量关闭，有其他睡眠进程（count等于-1，sleepers等于1)

down宏减count并将count字段置为-2且sleepers字段置为1来调用__down()函数。该函数暂时把sleepers置为2,然后通过把sleepers-1加到count来取消由down宏执行的减操作。同时，该函数检查count是否依然为负（在__down()进入临界区之前，持有信号量的进程可能正好释放了信号量）。

- 如果count字段为负，__down()函数把sleepers重新设置为1，并调用schedule()挂起当前进程。count字段还是置为-1，而sleepers字段置为1。
- 如果count字段不为负，down()函数把sleepers置为0，试图唤醒信号量等待队列上的另一个进程，并退出持有的信号量。在退出时，count字段置为0且sleepers字段置为0。这两个字段的值看起来错了，因为还有其他的进程在睡眠。然而，考虑一下在等待队列上的另一个进程已经被唤醒。这个进程进行循环体的另一个次循环；atomic_add_negative()函数从count中减去1，count重新变为-1；此外，唤醒的进程在重新回去睡眠之前，把sleepers重置为1。

可以很容易地验证，代码在所有的情况下都正确地工作。考虑一下，__down()中的wake_up()函数至多唤醒一个进程，因为等待队列中的睡眠进程是互斥的（参见博文“非运行状态进程的组织”）。

只有异常处理程序，特别是系统调用服务例程，才可以调用down()函数。中断处理程序或可延迟的函数不必调用down()，因为当信号量忙时，这个函数挂起进程。由于这个原因，Linux提供了down_trylock()函数，前面提及的异步函数可以安全地使用down_trylock()函数。该函数和down()函数除了对资源繁忙情况的处理有所不同外，其他都是相同的。在资源繁忙时，该函数会立即返回，而不是让进程去睡眠。

系统中还定义了一个略有不同的函数，即down_interruptible()。该函数广泛地用在设备驱动程序中，因为如果进程接收了一个信号但在信号量上被阻塞，就允许进程放弃“down”操作。如果睡眠进程在获得需要的资源之前被一个信号唤醒，那么该函数就会增加信号量的count字段的值并返回-EINTR。另一方面，如果down_interruptible()正常结束并得到了需要的资源溉返回0。因此，在返回值是-EINTR时，设备驱动程序可以放弃I/O操作。

最后，因为进程通常发现信号量处于打开状态，因此，就可以优化信号量函数。尤其是，如果信号量等待队列为空，up()函数就不执行跳转指令；同样，如果信号量是打开的，down()函数就不执行跳转指令。信号量实现的复杂性是由于极力在执行流的主分支上避免费时的指令而造成的。

2 读/写信号量

读/写信号量类似于前面“读/写自旋锁”一节描述的读/写自旋锁，有一点不同：在信号量再次变为打开之前，等待进程挂起而不是自旋。

很多内核控制路径为读可以并发地获取读/写信号量。但是，任何写者内核控制路径必须有对被保护资源的互斥访问。因此，只有在没有内核控制路径为读访问或写访问持有信号量时，才可以为写获取信号量。读/写信号量可以提高内核中的并发度，并改善了整个系统的性能。

内核以严格的FIFO顺序处理等待读/写信号量的所有进程。如果读者或写者进程发现信号量关闭，这些进程就被插入到信号量等待队列链表的末尾。当信号量被释放时，就检查处于等待队列链表第一个位置的进程。第一个进程常被唤醒。如果是一个写者进程，等待队列上其他的进程就继续睡眠。如果是一个读者进程，那么紧跟第一个进程的其他所有读者进程也被唤醒并获得锁。不过，在写者进程之后排队的读者进程继续睡眠。

每个读/写信号量都是由rw_semaphore结构描述的，它包含下列字段：
struct rw_semaphore {
signed long count;
#define RWSEM_UNLOCKED_VALUE 0x00000000
#define RWSEM_ACTIVE_BIAS 0x00000001
#define RWSEM_ACTIVE_MASK 0x0000ffff
#define RWSEM_WAITING_BIAS (-0x00010000)
#define RWSEM_ACTIVE_READ_BIAS RWSEM_ACTIVE_BIAS
#define RWSEM_ACTIVE_WRITE_BIAS (RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
spinlock_t wait_lock;
struct list_head wait_list;
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
};

count：
存放两个16位的计数器。其中最高16位计数器以二进制补码形式存放非等待写者进程的总数(0或1)和等待的写内核控制路径数。最低16位计数器存放非等待的读者和写者进程的总数。

wait_list：
指向等待进程的链表。链表中的每个元素都是一个rwsem_waiter结构，该结构包含一个指针和一个标志，指针指向睡眠进程的描述符，标志表示进程是为读需要信号量还是为写需要信号量。

wait_lock：
一个自旋锁，用于保护等待队列链表和rw_semaphore结构本身。

init_rwsem()函数初始化rw_semaphore结构，即把count字段置为0，wait_lock自旋锁置为未锁，而把wait_list置为空链表。

down_read()和down_write()函数分别为读或写获取读/写信号量。同样，up_read()和up_write()函数为读或写释放以前获取的读/写信号量。down_read_trylock()和down_write_trylock()函数分别类似于down_read()和down_write()函数，但是，在信号量忙的情况下，它们不阻塞进程。最后，函数downgrade_write()自动把写锁转换成读锁。这5个函数的实现代码比较长，但因为它与普通信号量的实现类似，所以容易理解，我们就不再对它们进行说明。

3 补充信号量

Linux 2.6还使用了另一种类似于信号量的技术：补充(completion)。引入这种原语是为了解决多处理器系统上发生的一种微妙的竞争条件，当进程A分配了一个临时信号量变量，把它初始化为关闭的MUTEX，并把其地址传递给进程B，然后在A之上调用down()，进程A打算一但被唤醒就撤消该信号量。随后，运行在不同CPU上的进程B在同一信号量上调用up()。然而，up()和down()的目前实现还允许这两个函数在同一个信号量上并发执行。因此，进程A可以被唤醒并撤销临时信号量，而进程B还在运行up()函数。结果，up()可能试图访问一个不存在的数据结构。

当然，也可以改变up()和down()的实现以禁止在同一信号量上并发执行。然而，这种改变可能需要另外的指令，这对于频繁使用的函数来说不是什么好事。

补充是专门设计来解决以上问题的同步原语。completion数据结构包含一个等待队列头和一个标志：
struct completion {
unsigned int done;
wait_queue_head_t wait;
};

与up()对应的函数叫做complete()。complete()接收completion数据结构的地址作为参数，在补充等待队列的自旋锁上调用spin_lock_irqsave()，递增done字段，唤醒在wait等待队列上睡眠的互斥进程，最后调用spin_unlock_irqrestore()。

与down()对应的函数叫做wait_for_completion()。wait_for_completion()接收completion数据结构的地址作为参数，并检查done标志的值。如果该标志的值大于0，wait_for_completion()就终止，因为这说明complete()已经在另一个CPU上运行。否则，wait_for_completion()把current作为一个互斥进程加到等待队列的末尾，并把current为TASK_UNINTERRUPTIBLE状态让其睡眠。一旦current被唤醒，该函数就把current从等待队列中删除，然后，函数检查done标志的值：如果等于0函数就结束，否则，再次挂起当前进程。与complete()函数中的情形一样，wait_for_completion()使用补充等待队列中的自旋锁。

朴充原语和信号量之间的真正差别在于如何使用等待队列中包含的自旋锁。在补充原语中，自旋锁用来确保complete()和wait_for_completion()不会并发执行。在信号量中，自旋锁用于避免并发执行的down()函数弄乱信号量的数据结构。