信号量机制
简介
1965年，荷兰学者Dijkstra提出的信号量（Semaphores）机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。现在，信号量机制已经被广泛地应用于单处理机和多处理机系统以及计算机网络中。
分类
整形信号量
- 简介：
整型信号量最初Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般的整型量不同，除初始化外，仅能通过两个标准原子操作（Atomic Operation，所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何context switch：切换到另一个线程）：wait(S)和signal(S)，也就是P，V操作
- 代码实现：
wait(S){ while (S < 0) ; //do no-op ，空循环（不满足条件就不会释放资源） S--; } signal(S){ S++; }
- 优点：仅通过两个原子操作，将 S（资源）的初值设置为1，便可实现互斥访问
- 缺点：不满足让权等待的规则，因为while处会进行空循环，进程会死等，造成资源的浪费
- 局限性：S的资源数目使用与释放均是以1为单位的
记录型信号量
- 简介：
记录型信号量在整型信号量机制中的wait操作，只要是信号量S<=0,就会不断测试。因此，该机制并未遵循“让权等待”准则，而是使进程处于“忙等”状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一个临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应该增加一个进程链表指针L（list），用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。同时引入了阻塞原语，与唤醒原语block(S->list)，wakeup(S->list)。
- 代码实现：
typedef struct{ int value; //value代替整形信号量 struct process_control_block *list; //阻塞队列，通过链表实现 }semaphore; //自定义信号量 wait(semaphore *S){ //先减一，再判断与整形信号量不同 S->value--; if（S->value < 0) block(S->list); //若资源缺少，将进程加入阻塞队列 } signal(semaphore *S){ S->value++; if(S->value >= 0) wakeup(S->list); //资源满足，将进程从阻塞队列中唤醒 }
- 优点：实现了让权等待，并且使得信号量具有了物理意义（当S.value >= 0，表示目前该资源的数目，若S.value < 0，则其绝对值表示目前阻塞队列中进程的数目），若S.value的初始值设置为1，那么信号量便会转化为互斥信号量，用于进程的互斥访问
- 缺点：一次只能解决一类型的资源访问问题，无法实现多类资源的访问
AND型信号量
- 简述：
AND型信号量在一些应用场合，是一个进程需要先获得两个或者更多的共享资源后方能执行其任务。假定现在有两个进程A和B，他们都要求访问共享数据D和E。当然，共享数据都应该作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex，并令他们的初值都是1。相应的，在两个进程中都要包含两个对Dmutex和Emutex的操作，即：
process A: process B:
wait(Dmutex); wait(Emutex);
wait(Emutex); wait(Dmutex);
若A运行了wait(Dmutex)，B运行wait(Emutex)，此时Dmutex和Emutex均为0；紧接着若A运行了wait(Emutex)，B运行了wait(Dmutex)，此时Dmutex和Emutex均为-1。那么进程A和B将处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。我们称此时的进程A 和B已经进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能性就越大。
- 思想：
将进程在整个运行过程中需要的所有资源，一次性全部的分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配给进程，要么一个也不分配。由死锁理论可知，这样就可以避免上述死锁情况发生。
- 代码实现：
Swait(S1, S2, ……, Sn){ //simultaneous wait 也就是wait操作 while (TRUE){ if(S1 >= 1 && …… && Sn >= 1){ //资源全部满足 for (i = 1; i <= n; i++) Si--; break; //成功为进程分配资源跳出while } else{ //若不满足条件，进程进入第一个不满足资源的阻塞队列 Place the process in the waiting queue associated with the first Si found with Si < 1,and set the progress count of this process to the beginning of Swait operation } } } Ssignal(S1, S2, …, Sn){ //simultaneous signal 也就是signal操作 while(TRUE){ for (i=1; i<=n; i++) { //释放Si，并检查Si等待队列中的全部进程 Si++; //若通过Swait测试，进入就绪队列 //若没通过，将该进程加入其对应的阻塞队列中 Remove all the process waiting in the queue associated with Si into the ready queue } } }
- 优点：解决了多资源的使用问题
- 缺点：每一次资源调度的单位仍然为1，不满足实际需求。同时，效率较低，容易造成死锁
信号量集
- 简述：
信号量集在记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或者减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，便要进行N次wait(S)操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下限值时，便不予分配。因而，在每次分配前，都必须测试该资源数量，看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。
- 思想：（信号量，下限值，需求值）
原有的value和list阻塞队列保留，新增属性t和d。d表示进程需要的某类资源的数量，t表示进程能执行需要某类资源数量的最小值，value表示当前某类资源个数。这里的d，t必须满足关系t>=d才能保证进程可以执行。解释一下：假设d=5，也就是进程本身需要5个A资源；t=7，也就是进程最小需要7个A类资源才能执行，多出来的两个是分给操作系统使用的，因为控制进程执行的指令也需要操作系统分配资源。当然当前i资源数S也必须大于7才能保证进程整体可以执行。 - 代码实现：
typedef struct{ int value; //信号量 int t; //下限值 int d; //需求量 struct process_control_block * list; //阻塞队列 } semaphore; Swait(S1, t1, d1, ……, Sn, tn, dn){ //simultaneous wait 也就是wait操作 while (TRUE){ if(S1 >= t1 && …… && Sn >= tn){ //资源全部满足 for (i = 1; i <= n; i++) Si -= di; break; //成功为进程分配资源跳出while } else{ //若不满足条件，进程进入第一个不满足资源的阻塞队列 Place the process in the waiting queue associated with the first Si found with Si < ti,and set the progress count of this process to the beginning of Swait operation } } Ssignal(S1, di, S2, d2 …, Sn, dn){ //simultaneous signal 也就是signal操作 while(TRUE){ for (i=1; i<=n; i++) { //释放Si，并检查Si等待队列中的全部进程 Si += dn; //若通过Swait测试，进入就绪队列 //若没通过，将该进程加入其对应的阻塞队列中 Remove all the process waiting in the queue associated with Si into the ready queue } } }
应用
进程互斥
- 概述：两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥，也就是说，一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。
- 互斥型信号量mutex，初值为1。取值范围（-1，0，1）：当mutex = 1，表示两个进程均为进入临界区；当mutex = 0，表示有一个进程进入临界区运行，另一个进程必须等待，挂入阻塞队列；当mutex = -1；表示一个进程正在临界区运行，而另一个进程因等待而阻塞在队列中，需要被当前临界区运行的进程退出时唤醒
- 临界区：每个进程中访问临界资源的那段代码。
- wait(mutex)：进入区，上锁
- signal(mutex)：退出区，解锁
- 代码实现：
//使用mutex实现Pa，Pb进程对临界区的互斥访问 semaphore mutex = 1; Pa(){ while(1){ wait(mutex); 临界区； signal(mutex); 剩余区; } } Pb(){ while(1){ wait(mutex); 临界区； signal(mutex); 剩余区; } }
进程同步（前趋关系）
- 概述：在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。例如：C1 -->C2，两端代码C1，C2，C1必须强制先于C2执行。
- 同步信号量S，其初始值为0，取值范围为（-1，0，1）。当S = 0，表示C1还未执行，则C2也未执行；当S = 1时，表示C1已经执行，则C2可以执行；当S = -1，表示C2想要执行，但是C1还未执行，C2处于阻塞状态
- 代码实现：
//使用S实现p1,p2进程的同步进行 semaphore S = 0; p1(){ while(TRUE){ C1； signal(S); //对信号量S的释放 } } p2(){ while(TRUE){ wait(S); //消耗信号量S C2; } }
- 例：
semaphore a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0; p1(){ while(TRUE){ S1; signal(a); signal(b); } } p2(){ while(TRUE){ wait(a); S2; signal(c); signal(d); } } p3(){ while(TRUE){ wait(b); S3; signal(g); } } p4(){ while(TRUE){ wait(c); S4; signal(e); } } p5(){ while(TRUE){ wait(d); S5; signal(f); } } p6(){ while(TRUE){ wait(e); wait(f); wait(g); S6; } }
