【信号量机制】

利用硬件指令可以有效地实现进程互斥，但当进程资源忙碌时，其他访问进程必须不断地进行测试，处于一种忙等状态，不符合让权等待原则，造成了处理机的浪费

1965 年，Dijkstra 提出了信号量机制，在长期广泛的应用中，证明了其是一种卓有成效的进程同步机制，现广泛地利用于各种系统中

信号量是用于表示系统资源数量的变量，一般用 $S$ 来表示，规定其只能通过信号量机制中的两个标准的原语 $P$ 原语和 $V$ 原语来访问

其中，$P$ 原语常写为 wait(S)，用于申请资源，$V$ 原语常写为 signal(S)，用于释放资源，两者成对使用

【整型信号量】

整型信号量定义为一个用于表示资源数目的整型量 S，其与一般除初始化外，仅能通过 $P$ 原语和 $V$ 原语来访问

$P$ 原语和 $V$ 原语在执行时不可中断，他们的描述如下：

void wait(S) {     //P原语
    while(S <= 0); //忙等
    S--;
}
void signal(S) {   //V原语
    S++;
}

在 $P$ 原语中，只要信号量 $S\leq 0$，就会不断的测试，陷入忙等状态，因此，该机制并未遵循让权等待原则

【记录型信号量】

为解决整型信号量中的忙等问题，有了记录型信号量，其除了一个用于表示资源数目的整型变量 value 外，还增加了一个进程链表指针 link，用于链接多个等待进程

记录型信号量的结构如下：

struct Semaphore {
    int value; //记录资源数目
    struct process_control_block *link; //PCB链表指针
};

在记录型信号量中，${S->value}$ 的初值表示系统中某类资源的数目，对他的每次 wait 操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个；对他的每次 signal 操作，意味着进程释放一个单位的该类资源，使系统中可供分配的该类资源数增加一个

相应的， $P$ 原语和 $V$ 原语的描述如下：

void wait (Semaphore *S) { //P原语
    S->value--;
    if (S->value < 0)      //该类资源已分配完毕
        block(S->link);    //自我阻塞，放弃处理机
}
void signal (Semaphore *S) { //V原语
    S->value++;
    if (S->value <= 0)       //仍有等待资源的进程被堵塞
        wakeup(S->link);     //唤醒链表中的第一个等待进程
}

每执行一次 $P$ 原语，表示进程请求一个资源，当资源量 $value<0$ 时，表示该类资源已经分配完毕，因此要调用 block 原语，进行自我阻塞，放弃处理机，并插入到该类资源的 PCB 队列中

每执行一次 $V$ 原语，表示进程释放一个资源，使系统中可供分配的该类资源数 $+1$，故若 $+1$ 后，资源量 $value\leq0$，则表示在 PCB 链表中仍有等待该资源的进程被阻塞，因此还应调用 wakeup 原语，将 PCB 链表中的第一个等待进程唤醒

【AND 型信号量】

在某些应用场合，一个进程往往需要两个及以上的共享资源才能执行其任务

假定有两个进程 $A$、$B$，要求访问临界资源 $C$、$D$，那么，如果 $A$ 占有了 $C$ 等待 $D$，$B$ 占有了 $D$ 等待 $C$，那么就会陷入死锁状态，两者都在等待对方释放自己所需的资源

显然，当进程同时要求的共享资源越多时，发生进程死锁的可能性就越大

为预防进程死锁的问题，出现了 AND 型信号量，其基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放，简单来说，要么全部分配完成，要么一个也不分配

在实现中，对若干临界资源的分配采取了原子操作方式，为此在 wait 与 signal 的操作的基础上，加了一个 AND 条件，称为同时 wait 操作、同时 signal 操作，其描述如下：

void Swait(int S1, int S2, ..., int Sn) {
    while (true) {
        if(S1 > 0 && S2 > 0 && ... && Sn > 0) {
            for (int i = 1; i <= n; i++)
                Si--;
            break;
        }
        else{
            将进程堵塞在第一个不能满足资源信号量的队列中
        }
    }
}
void Ssignal(int S1, int S2, ..., int Sn) {
    while (true) {
        for (int i = 1; i <= n; i++) {
            Si+;
            唤醒所有与Si相关的阻塞进程
        }
    }
}

【信号量集】

对于记录型信号量，$P$ 原语或 $V$ 原语只能对某临界资源进行一个单位的申请或释放，当一次需要 $n$ 个单位时，意味着需要 $n$ 次 $P$、$V$ 操作，这不仅低效，还会增加死锁的概率

在某些情况下，为保证系统的安全性，当所申请的资源数量低于一定值时，必须要加以管制不予分配，因此当进程申请某类临界资源时，每次分配前都要测试资源数量，判断是否大于可分配的下限值，决定是否予以分配

基于以上两点，对 AND 型信号量进行扩充，在一次 P、V 原语中，对进程所申请的所有资源以及每类资源不同资源的需求量完成申请或释放

进程对信号量 ${S_i}$ 的测试值不再是 $1$，而是该类资源的分配下限值 ${t_i}$，即要求 ${S_i\geq t_i}$，否则不予分配，一旦允许分配，进程对该类资源的需求为 ${d_i}$，那么就进行 ${S_i=S_i-d_i}$操作，由此形成一般化的信号量集机制，对应的 $P$ 原语或 $V$ 原语次格式如下：

void Swait (int S[], int t[], int d[], int n) { //P原语
    if (S[1] >= t[1] && ... && S[n] >= t[n])
        for (int i = 1; i <= n; i++)
            S[i] -= d[i];
}
void Ssignal (int S[], int d[], int n) { //V原语
    for (int i = 1; i <= n; i++)
        S[i] += d[i];
}

一般的信号量集还具有以下三种情况：

Swait(S,d,d)：此时信号量集中仅有一个信号量，但允许他每次申请 $d$ 个资源，若现有资源数少于 $d$，不予分配
Swait(S,1,1)：相当于一般的记录型信号量（$S>1$）或互斥信号量（$S=1$）
Swait(S,1,0)：相当于一个可控开关，当 ${S \geq 1}$ 时，允许多个进程进入某特定区，当 ${S=0}$ 时，阻止任何进程进入特定区