信号量机制

在我们之前学习的有关进程互斥的硬件软件方法中，都存在着一些不可避免的问题

例如在双标志检查法中，由于检查和上锁操作不能原子性的完成，导致两个进程可能同时进入临界区
又比如之前所讲的软硬件方法都无法实现“让权等待”

基于以上所说的问题，我们最终提出了有效解决进程互斥与进程同步的方法–信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而方便的实现进程互斥与进程同步

信号量实质就是一个变量（可以是一个整数，也可以是复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量（例如：系统有两台打印机，就可以设置一个信号量初始值为2）

原语是一种特殊程序段，其执行只能一气呵成，不可中断。原语是利用开/关中断指令实现的。软件解决方案的主要问题基本都出在进入区中的各种操作不能原子性的执行，因此如果能把进入区，退出区的操作都利用原语实现，就可以避免问题的产生

我们所使用的一对原语是：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名为wait和signal，括号里的S表示信号量S，其实就是函数调用时所传入的一个参数

wait和signal原语常被称为P,V操作，因此做题时也常将其写作P(S),V(S)

整型信号量

用一个整数型变量作为信号量，用来表示系统中某种资源的数量，整数型信号量与我们平常创建的普通整数变量的区别主要是我们对该信号量只能进行三种操作：即初始化或P操作和V操作

例如：系统中有一台打印机

int S=1;
void wait(int S) { //wait原语，相当于进入区
    //检查和上锁一气呵成，避免了并发过程中异步导致的问题
    while(S<=0); //如果资源不够，则始终循环等待，这一步不满足“让权等待”
    S=S-1; //如果资源足够，则占用一个资源
}

void signal(int s) { //signal原语，相当于退出区
    S=S+1;  //在使用完资源后，在退出区释放资源
}

按照上面示例，P0进程在进入区利用wait原语申请资源，然后进入临界区，此时S减一后为0，P1到Pn进程只能在wait原语中循环等待，直到P0进程释放资源。

此时就不会出现我们之前的两个进程同时进入临界区的情况，因为wait是原语，其执行原子性操作，所以检查和上锁是同时进行的

记录型信号量

整型信号量存在的缺陷是不满足“让权等待”存在忙等，所以人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量

/*记录型信号量的定义*/
typedef struct{
    int value;  //剩余资源数
    struct process *L;  //等待队列
}semaphore

/*某进程需要使用资源时，通过wait原语申请*/
void wait(semaphore S){
    S.value--;  //将资源数减一
    if(S.value<0){ //判断资源数是否小于0
        //小于0表示剩余资源不足
        block(S.L);
        //使用block原语使进程从运行态进入阻塞态，
        //并把该进程挂到信号量S的等待队列（即阻塞队列中）
    }
}

/*进程使用完资源后，使用signal原语释放资源*/
void signal(semaphore S){
    S.value++;  //将剩余资源数加一
    if(S.value<=0){ //判断资源数是否小于等于0
        //资源数小于等于0表示等待队列中还有进程处于阻塞态等待资源释放
        wakeup(S.L)
        //利用wakeup原语唤醒等待队列中的一个进程
        //该进程从阻塞态转变为就绪态
    }
}

示例

现在有四个进程按照P0->P3的顺序申请使用打印机

初始化打印机信号量：S.value=2
P0进程申请打印机，调用wait原语S.value-1=1，随后经过判断S.value>=0所以成功申请打印机并且不进入等待队列
P1进程申请打印机，调用wait原语S.value-1=0，经过判断S.value>=0，有剩余资源所以成功申请打印机并且不进入等待队列
P2申请打印机，调用wait原语S.value-1=-1，经过判断S.value<0所以没有剩余资源，利用block原语对P2进程进行阻塞，并将其放入等待队列
P3申请打印机，调用wait原语S.value-1=-2，经过判断S.value<0所以没有剩余资源，利用block原语对P3进程进行阻塞，并将其放入等待队列
P0进程使用结束，利用signal原语S.value+1=-1，经过判断S.value<=0，所以等待队列中有进程处于等待状态，调用wakeup原语唤醒一个等待进程
P2进程被唤醒，开始使用打印机，并且快速使用完毕，调用signal原语S.value+1=0，S.value<=0所以等待队列中还有进程在等待，调用wakeup原语唤醒一个进程
P3进程被唤醒，开始使用打印机
P1进程使用完毕，调用signal原语S.value+1=1，此时S.value>0所以等待队列中没有进程，所以不需要执行wakeup原语
P3进程使用完毕，调用signal原语S.value+1=2，此时S.value>0所以等待队列中没有进程，所以不需要执行wakeup原语

记录型信号量与整型信号量的主要区别在于其内部存储了等待队列，因此在发现资源被全部分配的情况下，进程不需要始终执行循环，造成“忙等”，而是可以利用block原语进行阻塞，主动放弃处理机，并进入该资源信号量的等待队列中，可见，记录型信号量完成的机制遵循了“让权等待”原则，不会出现“忙等”