1.信号量机制

进程互斥的四种软件实现方式和进程互斥的三种硬件实现方式都存在一些问题。

1.在双标志检查法中，进入区的“检查”、‘上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题。

2.所有的解决方案都无法实现“让权等待”。

1965 年，荷兰学者迪杰斯特拉 Dijkstra 提出了一种卓有成效的实现进程互斥、同步的方法–信号量机制

用户可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便地实现了进程互斥、进程同步。信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型信号量），可以用一个信号量来表示系统中的某种资源的数量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的，软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用原语实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait（s）原语和signal（s）原语，可以把原语理解为我们自己写的函数，函数名称分别为 wait 和 signal，括号里的信号量 s其实就是函数调用时传入的一个参数。wait、signal 原语常简称为 P，V 操作（来自荷兰语 proberen 和 verhogen，意思是“尝试”和“增加”）。因此，wait（s）和 signal（s）可被简写为P（s）和 V（s）。

2.整形信号量

用一个整数型的变量作为信号量，来表示系统中的某种资源的数量。

如：某计算机系统中有一台打印机：

int S = 1; //初始化整形信号量S，表示当前系统中可用的打印机资源数

void wait(int S){  //wait原语，相当于“进入区”
    while(s <= 0); //如果资源数不够，就一直循环等待
    S = S - 1;     //如果资源数够，就占用一个资源
}

void signal(int S){ //signal原语，相当于"退出区"
    S = S + 1;      //使用完资源后，在退出区释放资源
}

//如果一个进程P0想要访问打印机，则其操作的伪代码为：
...
wait(S); //进入区，申请自愿
使用的印记资源... //临界区，访问资源
signal(S);  //退出区，释放资源
...


//如果进程P1在进程P0正在放问打印机时想要访问打印机资源，只能一直执行wait(S)，等待进程P0释放
//临界区资源。
...
wait(S);
访问打印机资源...
signal(S);
...

信号量其与普通整数变量的区别：对信号量的操作只有三种，即 初始化、P 操作、V 操作。在 wait 原语中，“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。但是如果信号量 S 为 0，则其中的 while 语句会一直检查信号量 S 的占用情况，会一直占用处理机，不满足“让权等待”原则，会发生“忙等”。

3.记录型信号量（重要）

整形信号量的缺陷是存在“忙等”的问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

//信号量的数据结构
typedef struct{
    int value;   //剩余资源数
    struct process *L;  //等待队列
} semphore;

//某进程需要使用资源时，通过wait原语申请
void wait(semaphore S){
    S.value--;
    if(S.value < 0){  //如果剩余资源不够，使用block原语使进程从运行态进入阻塞态，并把它挂到
        block(S.L);   //信号量S的等待队列（即阻塞队列）中
    }
}

//进程使用完资源后，通过signal原语释放
void signal(semaphore S){
    S.value++;
    if(S.value<=0){  //释放资源后，如果还有别的进程在等待这种资源，则使用wakeup原语唤醒
        wakeup(S.L); //等待队列中的一个进程，使该进程从阻塞态变为就绪态。
    }
}

例：某计算机系统中有两台打印机，则可在初始化信号量 S 时将 S.value 的值设为 2，队列 S.L 设置为空

typedef struct{
    int value;    //剩余资源数为2
    struct process *L;  //等待队列-→null
}

//P0进程
...
wait(S);
使用打印机...
signal(S);
...

//P1进程
...
wait(S);
使用打印机...
signal(S);
...

//P2进程
...
wait(S);
使用打印机..
signal(S);
...

//P3进程
...
wait(S);
使用打印机...
signal(S);
...

/*
解释：有点啰嗦，能看得懂就行。
cpu首先为p0服务，P0使用wait原语检查剩余资源，系统中剩余打印机资源为2，可以分配给P0，value值减1变为1，P0可以使用打印机。之后cpu又为p1服务，P1使用wait原语检查剩余资源，系统中剩余打印机资源为1，value值减1变为0，可以分配给P1，P1可以使用打印机。再次cpu为P2服务，P2使用wait原语检查剩余打印机资源，系统中剩余打印机资源为0，资源已经暂时全部被占用，value值减1变为-1小于0，P2进程主动执行block原语，P2被挂载到了打印机的等待队列中，P3同理，value值变为-2.
value值为0时资源刚好被分配完，为-1时有一个进程在等待，为-2时有两个进程在等待。
当P0使用完成后，会执行signal原语释放打印机，value值加一变为-1，但此时value的值为-1仍然小于0，就说明此时等待队列中不止一个进程在等待打印机资源，进程P0会主动执行wakeup原语唤醒队列中的队头进程P2，P2从阻塞队列中被切换到就绪队列。待P2进程切换至运行态时，就可占用P0释放的打印机资源了。其余后续步骤同理。
*/

wait(S)和 signal(S)也可记为 P(S)，V(S)，这对原语用于实现系统资源的申请和释放。

S.value 的初始值表示系统中某种资源的数目。

对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.balue–，表示资源数减 1，当 S.value<0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态切换为阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待的原则”，不会出现“忙等”的现象。

对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数+1，若加一后仍是 S.value<=0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒的进程从阻塞态切换为就绪态）。

4.知识回顾

LLCHn1.png