信号量
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时，阻止任何进程进入特定区域。
经常使用的是后两种信号量集。
