信号量：整型、记录型信号量以及利用信号量实现进程互斥和前驱关系

信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”和“V操作”。

原语是指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。

如前述的“Test-and-Set”和“Swap”指令，就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机时可由软件通过屏蔽中断方法实现。

原语之所以不能被中断执行，是因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。

如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，wait和signal操作可描述为：

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

wait操作中，只要信号量S<=0，就会不断地测试。

因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。

记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。

除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。

记录型信号量可描述为：

typedef struct{
    int value;
    struct process *L;
} semaphore;

相应的wait(S)和signal(S)的操作如下：

void wait (semaphore S) { //相当于申请资源
    S.value--;
    if(S.value<0) {
        add this process to S.L;
        block(S.L);
    }
}

wait操作，S.value–，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。

void signal (semaphore S) {  //相当于释放资源
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}

signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。

若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒。

利用信号量实现同步

信号量机构能用于解决进程间各种同步问题。

设S为实现进程P1、P2同步的公共信号量，初值为0。

进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。

其实现进程同步的算法如下：

semaphore S = 0;  //初始化信号量
P1 ( ) {
    // …
    x;  //语句x
    V(S);  //告诉进程P2,语句乂已经完成
}
P2()）{
    // …
    P(S) ;  //检查语句x是否运行完成
    y;  // 检查无误，运行y语句
    // …
}

互斥的实现是不同进程对同一信号量进行P、V操作，一个进程在成功地对信号量执行了 P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作,表示当前没有进程进入临界区，可以让其他进程进入。

利用信号量实现前驱关系

信号量也可以用来描述程序之间或者语句之间的前驱关系。

图2-8给出了一个前驱图，其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。

例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。

同样，为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。

输入图片说明

算法

semaphore  al=a2=bl=b2=c=d=e=0;  //初始化信号量
S1() {
    // …
    V(al);  V(a2) ;  //S1已经运行完成
}
S2() {
    P(a1);  //检查S1是否运行完成
    // …
    V(bl); V(b2); // S2已经运行完成
}
S3() {
    P(a2);  //检查S1是否已经运行完成
    // …
    V(c);  //S3已经运行完成
}
S4() {
    P(b1);  //检查S2是否已经运行完成
    // …
    V(d);  //S4已经运行完成
}
S5() {
    P(b2);  //检查S2是否已经运行完成
    // …
    V(e);  // S5已经运行完成
}
S6() {
    P(c);  //检查S3是否已经运行完成
    P(d);  //检查S4是否已经运行完成
    P(e);  //检查S5是否已经运行完成
    // …;
}

分析进程同步和互斥问题的方法步骤

1) 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。

2) 整理思路。找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。

3) 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。

管程

定义

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。

管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。

管程的组成

1) 局部于管程的共享结构数据说明。

2) 对该数据结构进行操作的一组过程。

3) 对局部于管程的共享数据设置初始值的语句。

管程的基本特性

1) 局部于管程的数据只能被局部于管程内的过程所访问。

2) 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。

3) 每次仅允许一个进程在管程内执行某个内部过程。

由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加，无需程序员关注，而且保证正确。

参考资料

操作系统的基本概念

https://lgwain.gitbooks.io/os/content/unit11.html