我的书签
添加书签
移除书签4.2.5 信号量机制
信号量机制包括两类：
·单信号量机制：适用于进程之间存在一种临界资源时的互斥和同步管理。
·多信号量机制：考虑了进程之间可能存在多种临界资源时的互斥和同步管理。
1.单信号量机制中的信号量
信号量是一种特殊的变量，它的表现形式是一个整型变量及其相应的队列。可以使用如下数据结构来描述记录型信号量：
struct semaphore{
int Value;
struct PCB*L;
}s;
除了对信号量设置非负整数的初值外，只能对信号量进行P操作和V操作，而且P、V操作是原语操作。
按照信号量的取值，一般将信号量分为：
1）二元信号量（又称互斥型信号量，或二进制信号量，或互斥锁），取值为0或1，主要用于解决进程互斥问题。信号量取值为1时，表示临界资源当前可用；信号量取值为0时，表示临界资源当前不可用。
2）一般信号量（又称记录型信号量，或计数信号量），取值为非负整数，主要用于解决进程同步问题。当信号量s＞0时，表示当前有s个临界资源可用；当s=0时，表示当前没有临界资源可用，也没有等待该临界资源的进程；当s＜0时，表示目前有|s|个进程在等待该临界资源。
按照信号量的用途，将信号量分为：
1）公有信号量，用于解决并发进程互斥进入临界区。
2）私有信号量，用于解决异步环境下进程之间的同步，也称为同步信号量。
2.P、V操作
（1）对于二元信号量的P、V操作
P操作相当于分配资源，V操作相当于回收资源。
P(s){
While(s＜=0);//不可执行任何操作
s—;//s值减1
}
V(s){
s++;//s值加1
}
（2）对于记录型信号量的P、V操作
P操作具有阻塞进程的功能，V操作具有唤醒进程的功能。
P(s){
S.Value=S.Value-1;
if(s.Value＜0)
block(S.L);
}
V(s){
S.Value=S.Value+1;
if(S.Value＜=0)
walkup(S.L);
}
对于二元型信号量机制，如果当前没有临界资源可用，那么进程只能反复测试是否有临界资源可用，无法满足临界区“让权等待”的原则，存在“忙等待”问题。采用记录型信号量机制解决了“忙等待”问题。二元信号量机制一般用于解决进程同步问题中两个进程之间的同步控制。
3.用P、V操作解决进程间互斥问题
利用信号量能方便地解决临界区问题。设mutex为互斥的公用信号量，初值为1，表示该临界区未被占领。然后只需将进入临界区的操作置于P（mutex）和V（mutex）之间，即可实现进程间的互斥。
这里给出如何使用信号量机制实现N个并发进程进入各自临界区互斥访问一种临界资源的例子。
设mutex为互斥信号量，初值设mutex=1，表示无进程进入临界区。若mutex=0，表示进程Pi(i=1,2,…,n)已进入临界区；mutex=-(n-1)表示已有一个进程在临界区内执行，而n-1个进程等待进入临界区。mutex的取值范围是1～-(n-1)。
并发进程描述如图4-1所示。
图 4-1 并发进程描述
4.用P、V操作解决进程同步问题
利用信号量还可以实现异步环境下的进程同步，它利用私用信号量在进程间实现同步。其最典型的应用为生产者-消费者问题（Producer-Consumer Problem）。
（1）在条件C成立时，保证两个并发进程中的进程P1一定先于进程P2执行
对应条件C，设置一个互斥信号量S，初值为0，即当条件C成立时，S=0。实现进程同步，只需要在P2要执行的同步操作前增加P（S）；在P1要执行的同步操作后增加V（S）。并发进程描述如图4-2所示。
图 4-2 并发进程描述
（2）保证对某个临界资源使用的两个进程保持同步
假设两个进程P1和P2，分别是计算进程和打印进程，它们合作使用一个缓冲区（假设一次只能存放一个数据）。当缓冲区为空时，P1一定先于P2执行；当缓冲区为满时，P2一定先于P1执行。
设P1的私有信号量S1的初值为1，表示开始时P1可以向缓冲区放一个数据；设P2私有信号量S2初值为0，表示开始时P2不可以向缓冲区取一个数据，即缓冲区中没有数据。并发进程描述如图4-3所示。
图 4-3 并发进程描述
（3）生产者-消费者问题
计算机系统中，每个进程都申请持有和释放各种不同类型的资源，这些资源可以是硬件资源（如CPU、外设、内存及缓冲区等），也包括软件资源（如临界区、数据、例程等）。将系统中使用某一类资源的进程，称为该资源的消费者；而将释放同类资源的进程，称为该资源的生产者。
将生产者和消费者的同步和互斥问题抽象化、一般化，可以得到一个抽象的一般模型，即生产者-消费者问题。
将一个长度为n（n＞0）的有界缓冲区与一组生产者进程P1、P2、……、Pm和一组消费者进程C1、C2、……、Ck联系起来。
首先，生产者-消费者问题中，存在进程同步问题，即生产者和消费者应满足如下条件：
1）消费者接收数据时，有界缓冲区至少有一个单元是满的。
2）生产者想发送数据时，有界缓冲区至少有一个单元是空的。
其次，生产者-消费者问题中，存在进程互斥问题。由于有界缓冲区是临界资源，因此生产者和消费者进程之间必须互斥访问有界缓冲区。
由以上分析可知，需要设置公用信号量mutex，保证生产者和消费者进程之间的互斥；还需要设置生产者进程的私用信号量avail，消费者进程的私用信号量full。信号量初值分别为mutex=1；avail=n，表示有界缓冲区中的空单元数；full=0，表示有界缓冲区中的满单元数。并发进程描述如图4-4所示。
图 4-4 并发进程描述
P、V操作在使用时要非常小心操作次序。一般来讲，由于V操作是释放资源的，所以可以以任意次序出现。但P操作则不然，如果次序不当，或混乱，将可能造成进程之间的死锁。
这里对P、V操作进行简单的小结：
1）P、V操作必须成对出现，有一个P操作就一定有一个V操作。
2）当为互斥操作时，P、V操作处于同一进程中。
3）当为同步操作时，P、V操作则不在同一进程中出现。
4）如果一个同步P操作与一个互斥P操作在一起，那么同步P操作在互斥P操作之前。
两个V操作次序无关紧要。
