OS——信号量机制详解
OS——信号量机制详解
什么是信号量
信号量有三部分组成：称为信号量（semaphore）的特殊变量、P操作的原语以及V操作的原语。那么，什么是原语呢？
原语
书里的定义是：完成某种功能且不被分割、不被中断执行的操作序列，这里翻译一下，就是只能一气呵成，不能被中断
基本原理
为每个临界区设置一个信号量，作用就是在多个进程之间转发互斥信息。当一个进程需要使用临界资源时，对信号量执行P操作，了解临界资源的空闲情况。用完资源后，执行V操作，释放资源
//进程p0：
......
wait(s);//进入区，申请资源
使用资源//临界区，访问资源
signal(s);//退出区，释放资源
......信号量分类
这里讨论整型信号量和记录型信号量
整型信号量
我们刚刚提到，信号量是一个变量，那么整型信号量就是用一个整数型的变量作为信号量，表示系统中某种资源的数量。
可以执行的操作
- 初始化：初始化信号量的初值，应为非负数
- P操作
- V操作
smaphore S;
wait(S):
while S<=0 do no-op//如果资源数不够，就一直等待，直到S>0
S = S-1;//资源数够了，就占用一个资源
signal(S):
S = S+1;//使用完资源后，在退出区释放资源缺陷
在上面的P操作中我们可以看到，当S<=0时会一直等待，直到S>0才会停止在这期间是一直占用CPU的。而我们又知道，互斥准则之四：当一个进程不能进入临界区时要立马阻塞自己，让出CPU使用权，我们称之为让权等待。那么我们可以看到，整型信号量的P操作机制并未遵循让权等待的准则，有些进程可能会一直处于忙等。那么该如何解决这个问题呢？就该引出第二种信号量机制了——记录型信号量。
记录型信号量
那么，什么是记录型信号量呢？我们还是从组成的角度来看：在记录型信号量机制中，我们用整型变量count代表资源数目，一个进程链表指针queue链接所有的等待进程。
typedef struct{
int count;
queueType *queue;//类型即为等待进程的类型
}smaphore;count：值为正时，表示某种资源的数量，值为负时，表示该类资源已经被分配完毕，这里举一个栗子🌰：
当count = 3 时，表示临界资源还有3个
当count = -3 时，表明有3个进程在阻塞队列中排队
Wait(S)操作
smaphore S;
void wait(S){
S.count --;//使用临界资源，临界资源数量-1
if(S.count<0){//说明-1之前已经没有资源了，那就得阻塞自己了
block(S.queue);//使用block()原语阻塞自己链接到S.queue阻塞队列
}
}Signal(S)操作
void signal(S){
S.count ++;
if(S.count<=0){//释放一个资源后资源数还<=0，说明有进程在排队
wakeup(S.queue);//把它从阻塞队列移到就绪队列
}
}关于block与wake原语
刚刚听了完学校里的os课，对这个地方产生了些许疑问，疑问点在于：假设P1，P2，P3三个进程互斥访问资源S，S初值为0，假设执行顺序为P1，P2，P3。P1先执行，使用资源S，P2和P3在执行时都会自己block自己，S变为-2，那么问题来了：P1在执行后S=-1，于是执行wake原语，唤醒P2，那么此时P2是直接调用临界资源运行，还是再执行一遍wait呢？如果再执行一遍wait，S—后仍<0，P2仍然不能获得资源，百思不得其解之后跑去问老师了，结果如下：
看一下Wait操作的过程，P2是先申请了之后，发现没有资源，于是阻塞自己，不再占用CPU。回到P1，P1执行后，S++后发现<=0，于是调用wake唤醒P2，给其CPU，使其进入就绪态。等到P2从就绪转为运行时，直接进入临界区代码，因为P2之前已经申请过了（第二章学过进程的信号量可以保护现场）。
所以说真的有很多看似合理的地方会有值得挖掘的点，我在第一遍学wake的时候，觉得唤醒一个被阻塞的进程去调用临界资源，是一个很自然很合理的事情，直到第二遍听课的时候才发现问题。
举栗时间🌰
假设有四个进程p1~p4，他们都要使用打印机，也就是说打印机就是这四个进程的临界资源，我们假设有两台打印机。
现在P1申请资源：进行P操作后count = 1。
之后P2申请资源：进行P操作后count = 0。
P3也想申请资源：进行P操作后发现S.count < 0，也就是说此时没有资源可以给它用，那么P3此时立即执行block()原语把自己阻塞
p4也想申请资源：发现和p3一样，马上也把自己阻塞了。
p1用完资源：经过一段时间P1用完打印机了，执行V操作，count = -2 + 1 = -1，发现count值<=0，知道此时有进程正在排队，于是执行wakeup原语把队头的进程唤醒，也就是等了半天的P3大哥，P3大哥被唤醒后执行P操作，把资源拿来用。
p2用完资源：同样一段时间后，p2用完了，执行和p1同样的操作唤醒p4，把资源给它。
信号量的使用
信号量实现互斥
设n个进程共享一个信号量mutex，初值为1，把临界区置于P操作和V操作之间，即可实现进程互斥的进入临界区。原理很简单，一个进程执行P操作使用临界资源，如果此时没有资源可以使用就阻塞自己，直到有资源可以用。用完资源后执行V操作，同时检查此时资源数量，若<=0，说明有人在排队，就把它从阻塞队列中唤醒。具体代码如下:
void p1{
smaphore mutex = 1;
do{
wait(mutex);
临界区;
signal(mutex);
}while(true)
}信号量实现同步
那么首先回顾一下，什么是进程同步。我们知道：两个并发执行的进程具有异步性，因此两者的执行顺序是不确定的。但若进程2的操作必须基于进程1完成后才能执行，我们就必须确保要先执行完进程2再去执行进程1。这就是进程同步：让本来异步并发的进程互相配合，有序推进。
那么了解完进程同步是什么后，我们该如何实现它呢？很简单，概括为3步：
- 初始化公共信号量S = 0
- 在“前操作”执行完成后执行V操作
- 在“后操作”执行前执行P操作
smaphore S = 0;
//p1
void p1{
....
signal(S);//在“前操作”执行完成后执行V操作
}
void p2{
wait(S);//在“后操作”执行前执行P操作
....
}我们不妨分两种可能的情况来检验一下这样实现是否合理：
- 若进程1先执行，执行完后执行V操作，S++后S变为1。然后进程2执行，执行P操作，发现有可用资源可以用，S—变为0，进程2不会执行block阻塞自己。
- 若进程2先执行，执行之前先执行P操作，S—后为 -1，发现此时S<=0，也就是没有可用资源，便立即执行block阻塞自己。轮到进程1执行完后，执行P操作，S++变为0，表示目前有人在阻塞队列，因此V操作中会执行wakeup，唤醒进程p1，进程p1就继续执行。
信号量实现前驱
什么是前驱关系呢？这里还是直接举栗子🌰：
假设有6个进程P1~P6，执行顺序的关系如图所示：执行P1后才能执行P2，P5，执行完P2后才能执行P3和P4。
那么知道什么是前驱关系后，该如何实现它呢？我们的解决方案是为每一对前驱关系都设置一个同步变量，初值都为0。
然后在每一个前操作执行后执行V操作，同步变量++，在每个后操作执行前执行P操作，同步变量—。
过程即为：
- P1执行后执行V操作，a = 1。
- P2执行前，先执行P操作，a— = 0，即有可用的资源，于是P2使用资源，p2执行后执行V操作，使c++ ，c变为1，供p3使用
按如上方法依次执行，便可以实现前驱操作。可以发现，前驱关系其实是一种特殊的同步关系。