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. 若进程1先执行，执行完后执行V操作，S++后S变为1。然后进程2执行，执行P操作，发现有可用资源可以用，S—变为0，进程2不会执行block阻塞自己。
2. 若进程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使用

按如上方法依次执行，便可以实现前驱操作。可以发现，前驱关系其实是一种特殊的同步关系。