234_信号量机制
# 2.3_4_信号量机制
那么在正式聊本节的内容之前，我们先用之前小节学过的内容来两个问题。之前咱们学过在进程互持当中有 4 种软件实现方式和 3 种硬件实现方式，其中单标志法双标志先检查和双标志后检查，这三种方法都存在着比较严重的一些问题的隐患，大家尝试回忆一下还能不能想起来。
那么在双标志先检查法当中，我们之前聊过造成双标志先检查法的问题的主要原因在于他在进入区的检查和上锁，这两个操作是无法一气呵成的，中间有可能先执行了检查就进行进程切换，所以在这种情况下，如果两个进程并发执行的话，那么就有可能导致两个进程同时进入临界区的问题。
各位同学大家好，在这个小节中我们会学习信号量机制，这个极其重要的知识点，在考研当中我们需要掌握两种类型的信号量，一种是整型信号量，另一种是记录型信号量，我们会在后面分别展开讲解。
那么我们提出第一个问题，能不能用某种方法能够让检查和上锁，这两个操作都可以一气呵成，从而避免双标志检查先检查法的严重问题。第二个问题，除了这三种问题比较大的算法之外，Peterson 算法还有后面的三种硬件实现方式，其实问题都不大，但是这些方式也都无法实现让权等待这个原则。那么第二个问题就是我们能不能用某种方式实现真正的让这些并发执行的进程，能够遵守让权等待的原则，这是第二个问题。
其实这两个问题在很早很早以前，1965 年有一个荷兰学者叫做迪杰斯特拉，如果学过数据结构的同学对这个名字可能并不陌生，他提出了一个很好的解决方式，解决方案叫做信号量机制，那么信号量机制就可以比较好的解决进程互斥和进程同步的问题。
# 信号量机制
我们先来看一下对信号量机制的一些文字性的描述，用户可以通过操作系统提供的一对原语来对信号量进行操作，然后实现进程互斥进程同步这样的事情。这提到的信号量，其实我们可以简单的理解为它就是某一种变量，它可以是一个整数，也可以是比较复杂的记录型的这种数据结构的变量。一个信号量，它可以用来表示系统当中的某种资源的数量。比如说一个系统当中有一台打印机，那么我们就可以为打印机设置一个和它对应的信号量，让信号量的值把它初始值设为 1，那么就表示这个系统当中打印机这种资源的数量是有 1 个，所以这是信号量的用法，那么之后我们还会根据更多的例子来让大家加深对这段话的理解。
这提到的原语咱们在之前也介绍过，它其实就是一种特殊的程序段，就是由操作系统提供的，一种在执行的过程当中不可以被中断，只能一气呵成的这种程序。
而原语的具体实是怎么实现的，咱们之前也介绍过，还记得刚开始开篇的时候，咱们提过的问题吗？双标志先检查法的问题主要在于它在进入区当中的检查和操作，检查和上锁这两个操作无法一气呵成。那么既然原语拥有这种一气呵成不可被中断的特性，如果说我们把检查和上锁这两个操作都放在一个原语当中完成，那么是不是就可以避免它无法一气呵成的这种问题了呢？所以这就是为什么信号量机制会想到用原语来解决问题的一个原因。
这儿提到的一对原语指的是 wait(S)原语和 signal(S)原语，这两个原语其实我们就把它理解为是一种我们自己写的程序段，这个 wait 其实就是函数名，然后括号里的 s 我们就把它理解为是一种函数调用时候的一个参数。这个地方大家如果学过数据结构或者自己有一些编程基础的话，应该不难理解。
另外 wait 和 signal 这两个原语或者说这两个程序也可以简称为 pv 操作。 Pv 操作我在自己复习的时候一直不明白它的来历，然后之前查了一下才知道他其实是来自两个荷兰语，具体什么意思，有兴趣的同学大家可以去查一下。
P 原语： P 是荷兰语 Proberen(测试)的首字母。为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源(把信号量减 1)，若成功，则退出；若失败，则该进程被阻塞；
V 原语： V 是荷兰语 Verhogen(增加)的首字母。为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一个被占用的资源(把信号量加 1)，如果发现有被阻塞的进程，则选择一个唤醒之。
在我们的考研当中经常会把 wait 和 signal 这两个函数这两个原语把它简写为 p 和 v 这样的一种简写的形式。说了这么多，其实这整块想要告诉大家的无非就是两件事，第一，信号量它是一种变量，可以用信号量来表示我们系统当中某种资源的数量。第二，我们可以用系统提供的一对原语，wait 原语和 signal 原语来对信号量进行操作，具体是怎么操作，我们之后的讲解还会展开。
# 整型信号量
我们注意这个地方的有一句话，信号量这种变量它可以是一个整数，也可以是一个更复杂的记录型的变量。那么根据这个问题，我们就引申出了两种类型的信号量，一种叫整型信号量，一种叫记录型信号量。
我们先来看第一种整型信号量，整型信号量其实就是用一个整数来表示某一种系统资源的数量，那么它和普通的整型变量有什么区别呢？普通的整型变量我们可以对它进行加减乘除，各种各样的操作运算。但是对于作为信号量来说的这种整型变量来说，我们只能对这种信号量进行三种操作，一种是初始化，另一种是 p 操作，还有一种是 v 操作。
所以按照它的定义，如果说一个计算机系统当中有一台打印机，那么我们就可以定义一个和打印机这种系统资源对应的整型信号量，我们把它变量名设置为 S=1，也就是说这个系统当中原本是有一台打印机这种系统资源的，我们可以通过 weight 和 signal，或者说 pv 这两个操作，对 s 信号量进行一些更改，一些操作。具体 wait 和 signal 做了一些什么事情，我们直接来看一个例子。
如果一个进程 p0 它想要使用打印机这种资源，那么由于这种资源是有限的，它只有一个，并且我们需要互斥的访问这个打印机，所以在使用打印机资源之前，p0 它必须要先执行一个 wait 原语，对信号量 s 进行操作。
wait 原语当中做了两件事情。第一件事就是这句代码他会检查当前剩余的资源数量是否还足，如果 S 小于等于 0，就说明现在系统当中已经没有这种资源了，那么进程就会被一直卡在这个循环下不去
但是由于 p0 进程执行 wait 原语的时候， s 的值是 1，所以这个循环并不会卡住，它会跳出这个循环，然后执行下一句，是把 s 的值减一，也就是说打印机资源已经被分配给 p0 进程了，因此系统当中打印机资源的数量 s 要减一，所以这是这一步的意思，所以 s 就变为了 0 这个值。
那么当 p0 在访问打印机资源的过程当中，假如说发生了进程切换，有另外的进程，比如说进程 p1，他也想使用打印机这种资源，那么他在使用之前先执行 wait 原语，不过由于此时 s 的值已经是 0，也就是说此时系统当中已经没有打印机资源了，所以 p1 进程在执行 while 这个循环的时候，所以它会一直循环等待，直到 p0 进程把打印机资源释放了，其他的进程也一样，即使他们都想争着使用打印机资源，但是由于这个循环是过不了的，所以他们会一直循环等待，一直到 p0 使用完打印机资源之后，他又执行了 signal 原语。
Signal 的原语做的事情很简单，其实就是把 s 的值加一，也就是告诉把打印机还给系统，并且把打印机对应的信号量的值加一，也就表示打印机资源的数量变多了。当打印当 s 等于一之后，p1 或者说其中的某一个正在等待打印机的进程，这个循环就可以被跳过然后再继续执行下面的询下面的语句，于是 p1 进程就可以使开始使用打印机，然后一直到 p1 再把打印机释放，然后又把打印机资源交给别的进程使用，这就是整型信号量做的一个事情。
其实通过对比大家会发现整型信号量在 wait 原语当中的这两个操作，其实逻辑上来看和双标志先检查法当中，先检查后上锁其实做的是一样的事情，大家可以对比着来串联一下这两个知识点。
那么因为它是用一个原语来实现的检查和上锁，所以他这两个操作一气呵成，就避免了双标志先检查法那种就是两个进程同时进入临界区的问题。
第二点，在整型信号量机制当中，我们可以看到这个地方有一个 while 循环，如果说此时一个进程暂时进不了临界区，暂时使用不了这个资源，那么它会一直卡在这个循环这儿，因此会发生进程一直占用处理机盲等的这种情况，并不满足让权等待的原则。
这个地方可能会有一个疑问，如果一个进程暂时进不了临界区，也就意味着它被卡在 wait 原语的 while 循环里，那么既然 wait 原语它是不可被中断的，那么也就意味着当前正在执行 while 循环的进程，是不是一直不会被切换呢？这个地方确实是一个让人感觉不太严谨的地方，有兴趣的同学可以自己下去研究一下。但是我们在很多经典的教材当中，其实他们都是这么写的，所以这个地方我们姑且认为它没有问题，不会导致一个进程一直占用处理机的情况。
在整型信号量当中其实比较容易考察的是它存在的问题，这一点经常会把整型信号量和记录性的信号量做对比，那么它俩的区别就在于整型信号量不满足让权等待，会发生盲等，所以这个地方是大家需要重点关注的。
而刚才提出的问题有兴趣的同学可以自己下去研究一下。
# 记录型信号量
接下来我们介绍第二种信号量叫做记录型信号量。刚才的整型信号量有一个很大的缺陷，就是如果一个进程暂时进不了临界区，系统的那种资源暂时不够的话，它会一直占用处理机一直循环检查，从而导致盲等的情况，不满足让权等待的原则。
所以后来人们又提出了记录型信号量，就是为了解决刚才所说的问题，这种信号量是用一个记录型的数据结构来表示，其中 value 表示的是当前这种系统资源的剩余数量，比如说刚才咱们提到的打印机，第二个比较重要的是在这种信号量当中，它还会保持一个指向，等待这种系统资源的等待，队列指向等待他的那些进程，具体的咱们之后用一个具体的例子来再展开细聊。
对于记录型信号量的 wait 操作是这样的，首先执行了 wait 操作，就意味着某一个进程它需要使用与信号量对应的那种系统资源，所以我们会把这个资源的数量，也就是它的 value 的值做一个减一的操作。当它减一之后，又会对 Value 的值进行一个检查。如果说我们在执行了减一操作之后，导致 value 的值已经小于 0 了，那么就说明它在减一之前其实已经没有这种系统资源了，因此在这个时候是没有系统资源可以分配给当前申请这种资源的进程的。因此在这个地方需要执行一个 block 原语，作用就是把当前的进程阻塞起来，主动的阻塞，放弃处理机，并且把它挂到这个信号量对应的队列等待队列当中，这是 wait 操作。
而 signal 操作是当一个进程，他在使用完这种系统资源的时候会执行的一个原语操作，首先是会把这种资源的数量进行一个加 1 的操作，如果 value 的值在加 1 之后仍然小于等于 0，那么就说明在进程释放资源之前，依然还有一些进程是处于等待队列的，所以就需要再调用一个 wake up 原语，也就是从信号量对应的等待队列当中唤醒其中的某一个进程，然后让他从阻塞态回到就绪态，并且把这他所申请的他所等待的资源分配给他。
所以这就是 wait 原语和 signal 原语要做的两件事情。他们做的一个共同点是不管怎么说，肯定是对 value 的值先减减或者先加加，然后之后还会再对 value 的值做一个检查，再来判断是否需要对进程进行阻塞，或者是否需要唤醒某一个进程。
具体我们来看一个例子，如果说一个计算机系统当中有两台打印机，那么我们可以把初始的信号量的初始值把它设置为二，就是 value 值设置为二，而刚开始等待打印机资源的等待队列肯定是空的，各个进程在使用这个打印机资源之前，需要先用 wait 原语来申请打印机资源，在使用完之后又需要执行 signal 原语来释放一个打印机资源，所以所有各个进程的代码大概是这个样子，这些省略号就是其余的部分。
假如说刚开始 CPU 是为 p0 进程服务的，那么当它执行到 wait 原语的时候，首先会执行的事情是 value--对吧？所以 S.value 这个值它会由二减为一。之后系统判断它此时是有打印机资源的，所以会把其中的一个打印机分配给 p0 进程。然后 p0 可以呃往下开始使用打印机。之后切换到了 p1 进程，p1 进程同样的它执行 wait 原语的时候，其实也是在申请一个打印机资源，首先做的事情是会让 s.value 的值做一个减一的操作，所以这个值从 1 变为了 0 之后系统会把打印机分配给 p1 进程，然后 p1 进程可以开始使用打印机。那么我们可以看到当 value 的值变为了 0 的时候，此时系统当中的所有的打印机刚好就已经全部分配给了某一些进程，说明资源恰好分配完毕。
那么接下来如果 CPU 再为 p2 进程执行，而 p2 进程同样需要使用打印机资源，他在执行 wait 操作的时候，同样首先肯定是让这个信号量的 value 值做一个减 1 的操作，所以 value 会由 0 变为-1，当 value 的值在减 1 之后小于 0，那么就说明此时系统当中已经没有多余的资源可以分配给这个进程了。因此这个进程会主动的在 wait 原语当中主动的执行一个 block 原语，也就是把自己阻塞的原语，所以 p2 进程它会被挂到打印机这种资源的等待队列里。在这个地方我们会发现，当 value 的值等于-1 的时候，是有一个进程在等待打印机资源，刚好就是负数的绝对值
接下来 CPU 再转向为 p3 进程服务。那么同样的它在执行 wait 的原语的时候，首先是对 value 值减一，同样的当它减一之后小于 0，所以也会知道此时这种资源打印机资源已经分配完毕，所以 p3 进程也会主动的执行 block 原语，因此 p3 也会被插入到等相应的等待队列的对尾，就是这个样子
那么由于 p2 和 p3 都不能执行，因此接下来 CPU 只能为 p0 或者 p1 服务。
假设接下来 CPU 是为 p0 进程服务的，p0 在使用完打印机之后执行了一个 signal 原语，还记得 signal 原语做了什么事情吗？首先它会让 value 的值做一个加 1 的操作，所以 value 会从-2 变成-1。
而如果 value 的值在加 1 之后，它依然是小于等于 0 的，那么就说明此时在等待队列当中依然还有一些进程正在等待。所以 p0 进程在 signal 原语当中，他会主动的执行一个 wake up 原语，用来唤醒信号量对应的等待队列当中的队头的进程，也就是 p2。所以 p2 进程会从阻塞队列的放回就绪队列，并且会把 p0 刚刚才释放的打印机资源分配给 p2。
那么接下来 p0 在执行了其他语句之后就执行完毕，之后如果说 CPU 再接着为 p2 进程服务，p2 就可以得以开始使用打印机资源，然后在使用完了之后，会对打印机资源进行释放，执行一个 signal 原语。那么同样的它首先是会对 value 的值进行加 1 的操作，由于它加 1 之后，它的值依然是小于等于 0 的，所以说明此时在等待队列当中还是有进程，正在等待这种资源，所以它也会执行一个 wake up 原语来唤醒此时处于等待队列队头的进程，也就是 p3 进程。因此在执行了这个 wake up 原语之后，p3 进程会从阻塞态变回就绪态，并且 p2 刚才释放的打印机资源会被分配给 p3，然后 p3 的信息会从等待队列当中消失，这样的话等待队列就变为了空的状态。
接下来 p2 在执行完剩余的代码，然后就结束了。在之后如果说 CPU 又回到了为 P1 服务，那么 P1 当他使用完打印机资源之后，又会对打印机进行释放，此时它会对首先是会对 value 的值进行一个加 1 的操作，于是从 value 的值从 0 变为一，而由于加 1 之后它已经大于 0 了，所以说明此时在等待队列当中已经没有进程在等待了。所以 p1 进程它在执行 signal 操作的时候并不需要执行 wake up 原语，接下来系统会回收分配给 PE 的打印机资源，然后 P1 得以继续往下执行
最后还有 p3 进程没有结束，所以 CPU 会为 p3 进程服务。那么 p3 在使用完打印机之后，也是会对打印机资源进行释放，同样的 value 的值会加一变为二，然后之后系统回收打印机资源，然后 p3 得以顺利的执行，最后结束，那么这就是一个记录型信号量的一个具体的例子，相信根据通过刚才的动画，大家应该能够比较形象的理解。
那么我们再结合刚才的 weight 和 signal 的代码再来进行一个总结。wait 和 signal 这两个原语分别可以用于对系统资源的申请和释放的时候，那么这个 value 的初值其实是表示系统当中某一种资源的数目，如果对一个信号量 s 进行一次 p 操作，也就是申请信号量 s 对应的那种系统资源的话，那么就意味着 p 操作会导致系统的这种剩余资源数会减一，所以我们需要首先进行一个 value 减这样一个操作。如果说在它减一之后，发现它的值已经小于 0 了，那么就意味着这种资源其实之前就已经分配完毕了，所以它需要主动的调用 block 原语来进行自我阻塞，这会导致进程的状态从运行态变为阻塞态，并且进程相关的信息会被挂到 s 这个信号量对应的等待队列当中，用于之后的唤醒工作。那么可以看到这种机制其实遵循了所谓的让权等待原则，因为当一个进程他暂时申请得不到他所申请的这种系统资源的时候，他会主动的进行自我阻塞，主动的放弃 CPU，所以就不会出现之前的那些解决方案当中忙等的这种现象。
另外如果对一个信号量 s 进行 v 操作，那么就意味着需要释放一个与 s 这个信号量相对应的那种资源。所以我们此时需要对 value 的值进行加一的操作，如果说加 1 之后，它仍然是小于等于 0 的，就意味着此时在 s 对应的等待队列当中，依然还有进程在等待这种资源的分配，所以就需要调用 wake up 原语，从队列的对头当中把对头的进程给唤醒，也就是让他从阻塞重新回到就绪态，并且把资源分配给进程，所以这就是记录型信号量在 p 操作和 v 操作当中做的事情。
# 小结
那么我们再来简单的回顾一下小节，讲了整型信号量和记录型信号量，其中整型信号量比较容易考察的是它存在的问题，也就是不满足让权等待的原则，有可能会出现盲等的现象。
而记录型信号量可以说是操作系统这门课当中最重要的知识点，在大题和小题当中都会有很高的概率会考察记录型信号量。那么我们需要注意的是，那么大家需要自己在草稿纸上动手写一下记录型信号量的 pv 操作，还有在什么条件下需要执行 block 和 wake up 这两个原语，一定不能用死记硬背的方式，需要把这个地方彻底的理解。
从刚才的讲解我们也知道这种记录性的信号量，其实可以很方便的用于实现系统资源的申请和释放这样的一个操作。除此之外，记录型信号量还可以实现进程互斥进程同步，这两个咱们之前提过的问题，但这两个问题咱们会放到下个小节的视频当中再进行讲解。另外我们需要强调的一点是，如果说在题目当中出现了对某一个信号量 s 的 p 操作和 v 操作，如果说题目中没有特别说明的话，这个 s 这个信号量指的都是记录性的信号量，也就是说如果说 p 操作暂时得不到他所申请的资源的话，那么进程不会盲等，而是会进入到阻塞的状态
