信号量及其使用和实现(超详细)

互斥锁，我们刚刚讨论过了，通常认为是最简单的同步工具。本节将会讨论一个更棒的工具，它的功能类似于互斥锁，但是它能提供更为高级的方法，以便进程能够同步活动。

一个信号量 S 是个整型变量，它除了初始化外只能通过两个标准原子操作：wait () 和 signal() 来访问：

• 操作 wait() 最初称为 P（荷兰语proberen，测试）；
• 操作 signal() 最初称为 V（荷兰语verhogen，增加）；

可按如下来定义wait ():

wait(S){
    while (S <= 0)
        ;// busy wait
    S--；
}

可按如下来定义signal()：

signal(S) {
    S++;
}

在 wait() 和 signal() 操作中，信号量整数值的修改应不可分割地执行。也就是说，当一个进程修改信号量值时，没有其他进程能够同时修改同一信号量的值。另外，对于 wait(S)，S 整数值的测试（S < 0）和修改（S--）也不能被中断。

首先，我们看看如何使用信号量。

信号量的使用

操作系统通常区分计数信号量与二进制信号量。计数信号量的值不受限制，而二进制信号量的值只能为 0 或 1。因此，二进制信号量类似于互斥锁。事实上，在没有提供互斥锁的系统上，可以使用二进制信号量来提供互斥。

计数信号量可以用于控制访问具有多个实例的某种资源。信号量的初值为可用资源数量。当进程需要使用资源时，需要对该信号量执行 wait() 操作（减少信号量的计数)。当进程释放资源时，需要对该信号量执行 signal() 操作（增加信号量的计数）。当信号量的计数为 0 时，所有资源都在使用中。之后，需要使用资源的进程将会阻塞，直到计数大于 0。

我们也可以使用信号量来解决各种同步问题。例如，现有两个并发运行的进程：P1 有语句 S1 而 P2 有语句 S2。假设要求只有在 S1 执行后才能执行 S2。我们可以轻松实现这一要求：让 P1 和 P2 共享同一信号量 synch，并且初始化为 0。

在进程 P1 中，插入语句：

在进程 P2 中，插入语句：

因为 synch 初始化为 0，只有在 P1 调用 signal(synch) ，即 S1 语句执行之后，P2 才会执行 S2。

信号量的实现

回想一下，互斥锁实现具有忙等待。刚才描述的信号量操作 wait() 和 signal()，也有同样问题。

为了克服忙等待需要，可以这样修改信号量操作 wait() 和 signal() 的定义：当一个进程执行操作 wait() 并且发现信号量值不为正时，它必须等待。然而，该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放到与信号量相关的等待队列中，并且将该进程状态切换成等待状态。然后，控制转到 CPU 调度程序，以便选择执行另一个进程。

等待信号量 S 而阻塞的进程，在其他进程执行操作 signal() 后，应被重新执行。进程的重新执行是通过操作 wakeup() 来进行的，它将进程从等待状态改为就绪状态。然而，进程被添加到就绪队列。（取决于 CPU 调度算法，CPU 可能会也可能不会从正在运行的进程切换到新的就绪进程。）

为了实现这样定义的信号量，我们按如下定义信号量：

typedef struct {
    int value;
    struct process *list;
} semaphore;

每个信号量都有一个整数 value 和一个进程链表 list。当一个进程必须等待信号量时，就被添加到进程链表。操作 signal() 从等待、进程链表上取走一个进程，并加以唤醒。

现在，信号量操作 wait() 可以定义如下：

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block();
    }
}

而信号量操作 signal() 可定义如下：

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

操作 block() 挂起调用它的进程。操作 wakeup(P) 重新启动阻塞进程 P 的执行。这两个操作都是由操作系统作为基本系统调用来提供的。

注意，这样实现的信号量的值可以是负数，而在具有忙等待的信号量经典定义下，信号量的值不能为负。如果信号量的值为负，那么它的绝对值就是等待它的进程数。出现这种情况源于，在实现操作 wait() 时互换了递减和测试的顺序。

通过每个进程控制块 PCB 的一个链接字段，等待进程的链表可以轻松实现。每个信号量包括一个整数和一个 PCB 链表指针。向链表中增加和删除进程以便确保有限等待的一种方法采用 FIFO 队列，这里的信号量包括队列的首指针和尾指针。然而，一般来说，链表可以使用任何排队策略。信号量的正确使用不依赖于信号量链表的特定排队策略。

关键的是，信号量操作应原子执行。我们应保证：对同一信号量，没有两个进程可以同时执行操作 wait() 和 signal()。这是一个临界区问题。

对于单处理器环境，在执行操作 wait() 和 signal() 时，可以简单禁止中断。这种方案在单处理器环境下能工作，这是因为一旦中断被禁用，不同进程指令不会交织在一起。只有当前运行进程一直执行，直到中断 被重新启用并且调度程序重新获得控制。

对于多处理器环境，每个处理器的中断都应被禁止；否则，在不同处理器上不同的运行进程可能会以任意不同方式一起交织执行。每个处理器中断的禁止会很困难，也会严重影响性能。因此，SMP 系统应提供其他加锁技术，如 compare_and__swap() 或自旋锁，以确保 wait() 与 signal() 原子执行。

重要的是，对于这里定义的操作 wait() 和 signal()，我们并没有完全取消忙等待。我们只是将忙等待从进入区移到临界区。此外，我们将忙等待限制在操作 wait() 和 signal() 的临界区内，这些区比较短（如经合理编码，它们不会超过 10 条指令）。因此，临界区几乎不被占用，忙等待很少发生，而且所需时间很短。对于应用程序，存在一种完全不同的情况，即临界区可能很长（数分钟或数小时）或几乎总是被占用。在这种情况下，忙等待极为低效。

死锁与饥饿

具有等待队列的信号量实现可能导致这样的情况：两个或多个进程无限等待一个事件，而该事件只能由这些等待进程之一来产生。当出现这样的状态时，这些进程就为死锁。

为了说明起见，假设有一个系统，它有两个进程 P0 和 P1，每个访问共享信号量 S 和 Q，这两个信号量的初值均为 1:

假设 P₀ 执行 wait(S)，接着 P₁ 执行 wait(Q)。当 P₀ 执行 wait(Q) 时，它必须等待直到 P₁ 执行 signal(Q)。类似地，当 P₁ 执行 wait(S) 时，它必须等待直到 P₀ 执行 signal(S)。由于这两个操作 signal() 都不能执行，这样 P₀ 和 P₁ 就死锁了。

我们说一组进程处于死锁状态：组内的每个进程都等待一个事件，而该事件只可能由组内的另一个进程产生。这里主要关心的事件是资源的获取和释放。然而，其他类型的事件也能导致死锁。

与死锁相关的另一个问题是无限阻塞或饥饿，即进程无限等待信号量。如果对与信号量有关的链表按 LIFO 顺序来增加和删除进程，那么可能发生无限阻塞。

优先级的反转

如果一个较高优先级的进程需要读取或修改内核数据，而且这个内核数据当前正被较低优先级的进程访问（这种串联方式可涉及更多进程），那么就会出现一个调度挑战。由于内核数据通常是用锁保护的，较高优先级的进程将不得不等待较低优先级的进程用完资源。如果较低优先级的进程被较高优先级的进程抢占，那么情况变得更加复杂。

比如，假设有三个进程 L、M 和 H，它们的优先级顺序为 L<M<H。假定进程 H 需要资源 R，而 R 目前正在被进程 L 访问。通常，进程 H 将等待 L 用完资源 R。但是，现在假设进程 M 进入可运行状态，从而抢占进程 L。间接地，具有较低优先级的进程 M，影响了进程 H 应等待多久，才会使得进程 L 释放资源 R。

这个问题称为优先级反转。它只出现在具有两个以上优先级的系统中，因此一个解决方案是只有两个优先级。然而，这对于大多数通用操作系统是不够的。通常，这些系统在解决问题时采用优先级继承协议。

根据这个协议，所有正在访问资源的进程获得需要访问它的更高优先级进程的优先级，直到它们用完了有关资源为止。当它们用完时，它们的优先级恢复到原始值。在上面的示例中，优先级继承协议将允许进程 L 临时继承进程 H 的优先级，从而防止进程 M 抢占执行。当进程 L 用完资源 R 时，它将放弃继承的进程 H 的优先级，以采用原来的优先级。因为资源 R 现在可用，进程 H（而不是进程 M）会接下来运行。