信号量

多道程序环境下，进程并发执行，不同进程存在着不同的制约关系，为了协调进程的制约关系，引入了进程同步概念。

同步亦称为直接制约关系，指多个进程在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。

互斥也称间接制约关系，当一个进程使用临界区资源时，另一个进程必须等待，当前一个进程释放资源后，才能访问临界区资源。

---

信号量机制可以用来解决互斥和同步问题，他只能被两个标准原语wait(S)和signal(S)访问，也可记作P操作和V操作。原语指完成某种功能且不能被分割，不被中断执行的操作序列，通常由硬件实现。

• 整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，wait和signal如下

wait(S){
    while(S<=0);
    S=S-1;
}
signal(S){
    S=S+1;
}

wait操作中，只要信号量S<=0，就会不断测试。该机制使进程处于忙等状态

• 记录型信号量

除了一个代表资源数目的整型变量外，还增加了一个进程链表L，用于链接所有等待该资源的进程。

typedef struct{
    int value;
    struct process *L;
} semaphore
void wait(semaphore S){
    S.value--;
    if(S.value<=0){
        add this process to S.L;
        block(S.L)
    }
}
void signal(semaphore S){
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}

wait操作，S.value--表示请求一个资源，当小于0时，表示资源分配完毕，该进程自我阻塞，并插入等待队列。

signal操作，表示释放一个该类资源，若资源加1之后S.value仍然小于0，表示等待队列中仍有进程被阻塞，因此使用wakeup原语唤醒进程。

• 信号量实现同步

semaphore S=0;
P1(){
    ...
    x;
    V(S);
}
P2(){
    ...
    P(S);
    y;
}

只有x语句执行完，y语句才能执行。若P2先执行，到P(S)时，S为0，阻塞。进程P1中的x语句执行完之后，执行V操作，把P2从阻塞队列中唤醒，执行P2进程。

• 信号量实现互斥

semaphore S=1;
P1(){
    ...
    P(S);
    进程P1临界区；
    V(S);
}
P2(){
    ...
    P(S);
    进程P2临界区；
    V(S);
}

当没有进程进入临界区时，任意进程要进入临界区，需要先执行P操作，将S值减为0，然后进入临界区。此时别的进程要进入临界区，执行P操作时会阻塞。当临界区的进程执行完后，执行V操作，S值变为1，其他进程才可以进入临界区。