信号量机制

    1965年，荷兰学者Dijkstra提出的信号量（Semaphores）机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。现在，信号量机制已经被广泛地应用于单处理机和多处理机系统以及计算机网络中。[1] 

信号量S是一个整数，S大于等于零是代表可供并发进程使用的资源实体数，当S小于零时则表示正在等待使用临界区的进程数。

Dijkstra同时提出了对信号量操作的PV原语。

P原语操作的动作是：

（1）S减1；

（2）若S减1后仍大于或等于零，则进程继续执行；

（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。

V原语操作的动作是：

（1）S加1；

（2）若相加结果大于零，则进程继续执行；

（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。

PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。在PV原语执行期间不允许有中断的发生。

信号量机制分 整型信号量机制、记录型信号量机制、and型信号量机制、信号量集。

整型信号量是一种最简单的信号量，主要用于解决并发程序互斥访问临界资源问题。

记号信号量在整型信号量的举出上进行了改进，让不能进入临界区的进程“让权等待”，即进程状态有运行转换为阻塞状态，进程进入阻塞队列中等待。

AND型信号量集是将进程在运行中所需要的临界资源全部一次性分配给进程，等进程用完后再全部一次释放。

 

信号量集的定义

1.用s1、s2、...sn分别表示有n类裂解资源信号量；

2.用d1、d2、...dn分别表示进程需要的每类临界资源个数；

3.用t1、t2、...tn分别表示每类临界资源分给进程的下限值；

 

信号量分类

1. 整型信号量
   　　最初Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般的整型量不同，除初始化外，仅能通过两个标准原子操作（Atomic Operation）wait(S)和signal(S)操作可以描述为：
   wait(S): while S<=0 do no-op;
   S:=S-1;
   signal(S):S:=S+1;
2. 记录型信号量
   在整型信号量机制中的wait操作，只要是信号量S<=0,就会不断测试。因此，该机制并未遵循“让权等待”准则，而是使进程处于“忙等”状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。
   但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一个临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应该增加一个进程链表指针L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可以描述为：
   type semaphore=record
   value:integer
   L:list of process;
   end
   相应的，wait(S)和signal(S)的操作可描述为：
   procedure wait(S)
   var S: semaphore;
   begin
   S.value:=S.value-1;
   if S.value<0 then block(S.L);
   end
   procedure signal(S)
   var S: semaphore;
   begin
   S.value:=S.value+1;
   if S.value<=0 then wakeup(S.L);
   end
3. AND型信号量
   在一些应用场合，是一个进程需要先获得两个或者更多的共享资源后方能执行其任务。假定现在有两个进程A和B，他们都要求访问共享数据D和E。当然，共享数据都应该作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex，并令他们的初值都是1。相应的，在两个进程中都要包含两个对Dmutex和Emutex的操作，即：
   process A: process B:
   wait(Dmutex); wait(Emutex);
   wait(Emutex); wait(Dmutex);
   若进程A和B处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。我们称此时的进程A 和B已经进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能性就越大。
   AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部的分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配给进程，要么一个也不分配。由死锁理论可知，这样就可以避免上述死锁情况发生。为此，在wait操作中，增加一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneous wait)定义如下：
   Swait(S1,S2,......Sn)
   if Si>=1 and ....and Sn>=1 then
   for i:=1 to n do
   Si:=Si-1;
   endfor
   else
   place the process in the waiting queue associated with the first Si found with Si<1,and set the program count of this process to the beginning of Swait operation
   endif
   Ssignal(S1,S2,...Sn)
   for i:=1 to n do
   Si:=Si+1;
   Remove all the process waiting in the queue associated with Si into the ready queue.
   endfor;
4. 信号量集
   在记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或者减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，便要进行N次wait(S)操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下限值时，便不予分配。因而，在每次分配前，都必须测试该资源数量，看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下，其中S为信号量，d为需求值，而t为下限值。
   Swait(S1,t1,d1,......Sn,tn,dn)
   if Si>=t1 and ... and Sn>=tn then
   for i:=1 to n do
   Si:=Si-di;
   endfor
   else
   Place the ececuting process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation.
   endif
   Ssignal(S1,d1,......Sn,dn)
   for i:=1 to n do
   Si:=Si+di;
   Remove all the process waiting in the queue associated with Si into the ready queue
   endfor;[1]