信号量

• 在并发系统中，信号量是用于控制公共资源访问权限的 变量。信号量用于解决临界区问题，使得多任务环境下，进程能同步运行。
• 信号量的概念是由荷兰计算机科学家 Dijkstra 在 1962 年左右提出的。
• 信号量仅仅跟踪“还剩多少资源可用”，不会跟踪“哪些资源是可用的”。

PV 操作

• 计数信号量（Counting Semaphores）通常有两种操作，记做 P 和 V，V操作增加信号量 S，P操作减少信号量 S。信号量的一大特征就是它的值不能通过 PV 操作以外的方式更改。
• wait（P操作）：信号量数值减一，如果减一之后信号量数值为负，则进程进入信号量队列等待。
• signal（V操作）：信号量数值加一，如果之前信号量数值就是负的（表明有进程在等资源），则将一个进程块从信号量等待队列移到就绪队列。
• P、V 都来源自荷兰语，V 通常解释为 verhogen ("increase")，P 则有多种解释，包括 proberen ("to test" 或 "to try")、passeren ("pass")、pakken ("grab")。在 Dijkstra 最早的论文中，P 表示 passering ("passing")，V 表示 vrijgave ("release")。

信号量和 PV 操作的自习室类比

假设一个图书馆有 10 个相同的自习室，每次仅供一名学生使用。使用自习室前，学生需要向前台申请。使用完成后，学生也需要通知前台。在最简单的情形下，前台员工只知道剩余可用自习室的数量。当有学生请求使用自习室时，数量减一，当有学生离开自习室时，数量加一。这个数量可以代表一个信号量，自习室代表资源，学生代表进程/线程。这个例子中，信号量的初始值为 10，当一个自习室被释放，但是有多个学生在等待时，就需要选择一个学生进入自习室。

PV 原语操作及其伪代码

typedef struct semaphore {
    int value;                 /* 信号量的值 */
    struct pcb *list;          /* 信号量列队指针 */
}

// P操作原语
void P(semaphore s) {
    s.value --;                /* 信号量的值减一 */
    if (s.value < 0) {
        sleep(s.list);         /* 执行P操作的进程阻塞，移入s信号量队列，转向进程调度程序 */
    }
}

// V操作原语
void V(semaphore s) {
    s.value ++;
    if (s.value <= 0) {        /* 有进程在等待 */
        wakeup(s.list);        /*从 s 的队列中释放一个进程执行 */
    }
}

PV 操作经典问题

• 哲学家就餐问题