理解操作系统之信号量机制

信号量

1965年荷兰Dijkstra提出的信号量（Semaphores）是一种卓有成效的进程同步工具，在长期的应用中，得到了很大的发展，从整型信号量经过记录型信号量，进而发展为“信号量集”机制。

• 信号量就是OS提供的管理公有资源的有效手段。
• 信号量代表可用资源实体的数量。

1: 整形信号量

定义：把整型信号量定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两个原子操作wait(S),signal(S)来访问也就是P(S)，V(S)操作

• P操作 wait(S):

while S < 0 do no-op
    S: S +1 

• V操作 signal(S):

S:=S+1;

注意：P、V操作是原子操作，不可中断。

2：记录型信号量

引入整型变量value(代表资源数目)、进程链表L (链接所有等待进程)
记录型数据结构：

 type  semaphore=record
               value: integer;
               L: list  of  process;
  end; 

Wait 操作：

• 申请资源，减量操作，S.value:=S.value-1
• 当S.value<0时，表示资源分配完，进行自我阻塞。

Signal操作：

• 释放资源，增量操作，S.value:=S.value+1
• 当S.value≤0，唤醒S.L链表中的等待进程

type  semaphore=record
      value: integer;
      L: list  of  process;
end; 

wait操作

wait(S)
   begin
          S.value:=S.value-1；
          if  S.value<0  then 
              block(S,L)
      end

signal操作

signal(S)
    begin
          S.value:=S.value+1;
          if  S.value<=0  then 
              wakeup(S,L)
      end

正确使用时能实现同步和互斥
含义：value>0，代表可用资源的数量
value<0，代表由于申请资源而阻塞的进程数量

记录型信号量机制：

每次只能获得或释放一个单位的资源，低效
每次分配前必须测试资源数量，看其是否大于其下界值

3: AND型信号量

两个进程A和B，共享数据D和E，为其分别设置互斥信号量Dmutex和Emutex，初值均为1。

Process  A：
    wait(Dmutex);
    wait(Emutex);
        使用D、E
    Signal(Dmutex)
    Signal(Emutex)

Process  B：
    wait(Emutex);
    wait(Dmutex);
       使用D、E
    Signal(Dmutex)
    Signal(Emutex)

Process A： wait(Dmutex); 于是Dmutex=0
Process B： wait(Emutex); 于是Emutex=0
Process A： wait(Emutex); 于是Emutex=-1 A阻塞
Process B： wait(Dmutex); 于是Dmutex=-1 B阻塞
可见：共享的资源越多，死锁的可能越大

AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。即对临界资源的分配采取原子操作。称为同时wait操作即Swait()

Swait(S1, S2, …, Sn)
    if Si >=1 and … and Sn>=1 then
          for i:=1 to n do
               Si:= Si -1 ;
          endfor
    else

4:信号量集：

对AND信号量机制加以扩充
S 为信号量；t 为下限值；d 为需求值

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 executing 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

一般信号量集的几种特殊情况：
Swait(信号量，下限值，需求值)
Swait(S, d, d)，只有一个信号量S，允许每次申请d个资源，若现有资源数少于d，不予分配。
Swait(S, 1, 1)，蜕化为一般的记录型信号量(S>1时)或互斥信号量(S=1时)。
Swait(S, 1, 0)，当S>=1时，允许多个进程进入某特定区，当S变为0后，阻止任何进程进入特定区，相当于可控开关。

Swait(S,1,0) 这一种比较难理解，其中S表示只有S个信号量，1为下限值，如果S>=1,则允许进程进入某特定区域，需求值为0，每次S = S -0，然而当S<1时，阻止任何进程进入特定区域。

经常使用的是后两种信号量集。