目录

2.4.3 信号量机制

1. 整型信号量

2. 记录型信号量

3. AND 型信号量

4. 信号量集

三种特例

2.4.4 信号量的应用

1. 利用信号量实现进程互斥

2. 利用信号量实现前趋关系

2.4.5 管程机制

1. 管程的组成

2. 管程的主要特点

2.4.3 信号量机制

信号量（Semaphores）机制:是一种卓有成效的进程同步工具。

1. 整型信号量

把整型信号量定义为一个用于表示资源数目的整型量 S，仅能通过两个标准的原子操作 wait(S) 和 signal(S) 来访问。这两个原子操作又分别被称为 P 和 V 操作，注意必须使用大写。

wait(S) {while(S <= 0);  //do no-op，CPU空转S--;            //访问资源，资源减一
}signal(S) {S++;            //释放资源，资源加一
}

在 wait(S) 中，对 S 值的测试和做 S=S-1 操作时都是不可中断的。

2. 记录型信号量

整型信号量的问题：忙等，即当 wait(S) 中信号量 S<=0 时，会不停地进行测试，因此未遵循让权等待的原则。而记录型信号量机制则是一种不存在 “忙等” 现象的进程同步机制。

记录型信号量的数据结构可描述如下：

typedef struct {int value;struct process_control_block * list;
} semaphore;

原子操作 wait(S) 和 signal(S) 可描述如下：

wait(semaphore * S) {S->value--;if(S->value < 0) block(S->list);//S->value == 0时代表刚好取走最后一个资源
}signal(semaphore * S) {S->value++;if(S->value <= 0) wakeup(S->list);//S->value == 0时代表刚好还有一个进程被阻塞
}

整型信号量和记录型信号量的问题：

• 只能有效地解决多个进程共享一种临界资源的情况
• 即只需要设置一个临界区

下面来看多个进程需要访问多种临界资源的情况。假设进程 A 和 B 需要访问共享数据 D 和 E，设置互斥型信号量 Dmutex 和 Emutex，两者初始值均为 1，进程 A 和 B 的访问操作如下：

process A:         |process B:
wait(Dmutex);      |wait(Emutex);
wait(Emutex);      |wait(Dmutex);
signal(Emutex);    |signal(Dmutex);
signal(Dmutex);    |signal(Emutex);

若进程 A 和 B 按下述次序交替执行 wait 操作：

process A: wait(Dmutex);    //Dmutex=0
process B: wait(Emutex);    //Emutex=0
process A: wait(Emutex);    //Emutex=-1, A blocked
process B: wait(Dmutex);    //Dmutex=-1, B blocked

进程阻塞以后也不能释放已持有的资源。最后，进程 A 和 B 就将处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。我们称此时的进程 A 和 B 已进入死锁状态。

3. AND 型信号量

AND 同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全都地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。

对若干个临界资源的分配采取原子操作：要么把它所请求的资源全部分配到进程，要么一个也不分配。具体方法是在 wait 操作中，增加了一个 “AND” 条件，故称为 AND 同步，或称为同时 wait 操作（simultaneous wait）。

Swait 操作定义如下：

Swait(S1, S2, ... , Sn) {while(true) {if(S1 >= 1 && S2 >= 1 && ... && Sn >= 1) {for(i = 1; i <= n; ++i) Si = Si - 1;break;  //分配完资源后，直接退出while循环} else {/*place the process in the waiting queue associated withthe first Si found with Si<1, and set the program countof this process to the beginning of Swait operation*/}}
}

Ssignal 操作定义如下：

Ssignal(S1, S2, ... , Sn) {for(i = 1; i <= n; ++i) Si = Si + 1;/*remove all the process waiting in the queueassociated with Si into the ready queue*/
}

4. 信号量集

在每次分配时，采用信号量集来控制，可以分配多个资源。

Swait 操作定义如下：

Swait(S1, t1, d1, ... , Sn, tn, dn) {while(true) {if(S1 >= t1 && ... && Sn >= t1) {for(i = 1; i <= n; ++i) Si = Si - di;break;  //分配完资源后，直接退出while循环} else {/*place the process in the waiting queue associated withthe first Si found with Si

Ssignal(S1, d1, ... , Sn, dn) {for(i = 1; i <= n; ++i) Si = Si + di;/*remove all the process waiting in the queueassociated with Si into the ready queue*/
}

P0：Swait(S, 1, 0)  //S>=1成立，且不改变信号量
P1：Swait(S, 1, 0)  //S>=1成立，且不改变信号量
Pw：Swait(S, 1, 1)  //S>=1成立，且S-1=0
P2：Swait(S, 1, 0)  //S>=1不成立

var mutex:semaphore:=1; //将mutex定义为semaphore类型，且赋初值为1
begin
parbeginprocess1: beginrepeatwait(mutex);//critical sectionsignal(mutex);//remainder sectionuntil falseendprocess2: beginrepeatwait(mutex);//critical sectionsignal(mutex);//remainder sectionuntil falseendparend
end

p1(){ S1; signal(a); signal(b); }
p2(){ wait(a); S2; signal(c); signal(d); }
p3(){ wait(b); S3; signal(e); }
p4(){ wait(c); S4; signal(f); }
p5(){ wait(d); S5; signal(g); }
p6(){ wait(e); wait(f); wait(g); S6; }void main() {semaphore a, b, c, d, e, f, g;//将信号量初值均设置为0，若后续进程试图执行则必被阻塞a.value = b.value = c.value = 0;d.value = e.value = f.value = g.value = 0;cobegin  //采用并行执行p1(); p2(); p3(); p4(); p5(); p6();coend;
}