操作系统之信号量

信号量的定义：

为了防止出现因多个程序同时访问一个共享资源而引发的一系列问题，我们需要一种方法，它可以通过生成并使用令牌来授权，在任一时刻只能有一个执行线程访问代码的临界区域。临界区域是指执行数据更新的代码需要独占式地执行。而信号量就可以提供这样的一种访问机制，让一个临界区同一时间只有一个线程在访问它，也就是说信号量是用来调协进程对共享资源的访问的。

信号量是一个特殊的变量，程序对其访问都是原子操作，且只允许对它进行等待（即P(信号变量))和发送（即V(信号变量))信息操作。最简单的信号量是只能取0和1的变量，这也是信号量最常见的一种形式，叫做二进制信号量。而可以取多个正整数的信号量被称为通用信号量。这里主要讨论二进制信号量。

另一种定义

信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”和“V操作”。

原语

原语是指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。如前述的“Test-and-Set”和“Swap”指令，就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机时可由软件通过屏蔽中断方法实现。

整型信号量

<code class="hljs xml has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">wait(S){
    while (S<span class="hljs-tag" style="color: rgb(0, 102, 102); box-sizing: border-box;"><<span class="hljs-title" style="box-sizing: border-box; color: rgb(0, 0, 136);">=0);
</span>    <span class="hljs-attribute" style="box-sizing: border-box; color: rgb(102, 0, 102);">S</span>=<span class="hljs-value" style="box-sizing: border-box; color: rgb(0, 136, 0);">S-1;</span>
}
<span class="hljs-attribute" style="box-sizing: border-box; color: rgb(102, 0, 102);">signal</span>(<span class="hljs-attribute" style="box-sizing: border-box; color: rgb(102, 0, 102);">S</span>){
    <span class="hljs-attribute" style="box-sizing: border-box; color: rgb(102, 0, 102);">S</span>=<span class="hljs-value" style="box-sizing: border-box; color: rgb(0, 136, 0);">S+1;</span>
}</span></code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li></ul>

wait操作中，只要信号量S<=0，就会不断地测试。因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。

记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。记录型信号量可描述为：

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">typedef <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span>{
    <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">value</span>;
    <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> process *L;
} semaphore;</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li></ul>

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> wait (semaphore S) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//相当于申请资源</span>
    S.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">value</span>--;
    <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(S.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">value</span><<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>) {
        add <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span> process to S.L;
        block(S.L);
    }
}</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li></ul>

wait操作，S.value–，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> signal (semaphore S) {  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//相当于释放资源</span>
    S.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">value</span>++;
    <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(S.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">value</span><=<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>){
        remove a process P <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span> S.L;
        wakeup(P);
    }
}</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li></ul>

signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒。

利用信号量实现同步

信号量机构能用于解决进程间各种同步问题。设S为实现进程P1、P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。其实现进程同步的算法如下：

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">semaphore S = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//初始化信号量</span>
P1 ( ) {
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    x;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//语句x</span>
    V(S);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//告诉进程P2,语句乂已经完成</span>
}
P2()）{
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    P(S) ;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查语句x是否运行完成</span>
    y;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 检查无误，运行y语句</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
}</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li></ul>

利用信号量实现进程互斥

信号量机构也能很方便地解决进程互斥问题。设S为实现进程Pl、P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两进程对临界资源的互斥访问。其算法如下： 
复制纯文本新窗口

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">semaphore S = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//初化信号量</span>
P1 ( ) {
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    P(S);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 准备开始访问临界资源，加锁</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 进程P1的临界区</span>
    V(S);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 访问结束，解锁</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
}
P2() {
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    P(S); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//准备开始访问临界资源，加锁</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 进程P2的临界区；</span>
    V(S);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 访问结束，解锁</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
}</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li></ul>

互斥的实现是不同进程对同一信号量进行P、V操作，一个进程在成功地对信号量执行了 P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作,表示当前没有进程进入临界区，可以让其他进程进入。

利用信号量实现前驱关系

信号量也可以用来描述程序之间或者语句之间的前驱关系。图2-8给出了一个前驱图，其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。同样，为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。 

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: "Source Code Pro", monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">semaphore  al=a2=bl=b2=c=d=e=<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//初始化信号量</span>
S1() {
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    V(al);  V(a2) ;  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//S1已经运行完成</span>
}
S2() {
    P(a1);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S1是否运行完成</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    V(bl); V(b2); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// S2已经运行完成</span>
}
S3() {
    P(a2);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S1是否已经运行完成</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    V(c);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//S3已经运行完成</span>
}
S4() {
    P(b1);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S2是否已经运行完成</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    V(d);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//S4已经运行完成</span>
}
S5() {
    P(b2);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S2是否已经运行完成</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …</span>
    V(e);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// S5已经运行完成</span>
}
S6() {
    P(c);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S3是否已经运行完成</span>
    P(d);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S4是否已经运行完成</span>
    P(e);  <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//检查S5是否已经运行完成</span>
    <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// …;</span>
}</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right: 1px solid rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li></ul>

总结：

1) 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。

2) 整理思路。找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。

3) 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。