操作系统原理之信号量

发表于 | 分类于

操作系统原理之信号量

同步和互斥是比较重要的概念，这里转载一篇文章并做整理。

操作系统原理之进程和线程管理

实现临界区互斥的基本方法

软件实现方法

在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

算法一：单标志法

该算法设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号。
即若turn=0，则允许P0进程进入临界区；相应的，若turn=1，则允许P1进程进入临界区.

注意：该算法可确保每次只允许一个进程进入临界区，但两个进程必须交替进入临界区。
如果某个进程进入了一次后退出，那么另一个进程将无法进入临界区（违背“空闲让进”），这样很容易造成资源利用的不充分。

1
2
3
4
5
// P0进程
while(turn!=0);
critical section;
turn=1;
remainder section;
1
2
3
4
5
// P1进程
while(turn!=1);  // 进入区
critical section;  // 临界区
turn = 0;  // 退出区
remainder section;  // 剩余区

算法二：双标志法先检查

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。
为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。

1
2
3
4
5
6
// Pi 进程
while(flag[j]);  // ①    
flag[i]=TRUE;  // ③  
critical section;   
flag[i] = FALSE; 
remainder section;
1
2
3
4
5
6
// Pj 进程
while(flag[i]);  // ② 进入区
flag[j] =TRUE;  // ④ 进入区
critical section;  // 临界区
flag[j] = FALSE;  // 退出区
remainder section;  // 剩余区

优点：不用交替进入，可连续使用；
缺点：Pi和Pj可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag之前有一段时间（可能进程被剥夺了执行权），结果都检查通过。

这里的问题出在检查（while(flag[i])）和修改(flag[j])操作不能一次进行。

算法三：双标志法后检查

算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。

为此，算法三釆用先设置自己标志为TRUE后,再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

1
2
3
4
5
6
// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;
1
2
3
4
5
6
// Pj进程
flag[j] =TRUE;  // 进入区
while(flag[i]);  // 进入区
critical section;  // 临界区
flag [j] =FLASE;   // 退出区
remainder section;  // 剩余区

缺点：当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

算法四：Peterson’s Algorithm

为了防止两个进程为进入临界区而无限期等待，又设置变量turn，指示不允许进入临界区的进程编号，每个进程在先设置自己标志后再设置turn标志，不允许另一个进程进入。

这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。

1
2
3
4
5
6
// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j); 
critical section;
flag[i]=FLASE;
remainder section;
1
2
3
4
5
6
// Pj进程
flag[j] =TRUE;turn=i;  // 进入区
while(flag[i]&&turn==i);   // 进入区
critical section;  // 临界区
flag[j]=FLASE;  // 退出区
remainder section;  // 剩余区

本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。

硬件实现方法

硬件实现和信号量相关。

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。
通过硬件支持实现临界段问题的低级方法或称为元方法。

中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。
因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。

其典型模式为：

1
2
3
关中断;
临界区;
开中断;

缺点：这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后执行出现错误，而不再开中断，则系统可能会因此终止。

硬件指令方法

1、TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。

指令的功能描述如下：

1
2
3
4
5
6
boolean TestAndSet(boolean *lock){
    boolean old;
    old = *lock;
    *lock=true;
    return old;
}

可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。
在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。

利用该指令实现进程互斥的算法描述如下：

1
2
3
4
while TestAndSet(&lock);
// 进程的临界区代码段;
lock=false;
// 进程的其他代码

2、Swap指令：该指令的功能是交换两个字节的内容。其功能描述如下。

1
2
3
4
5
6
Swap(boolean *a, boolean *b){  
    boolean temp;
    Temp=*a;
    *a = *b;
    *b = temp;
}

注意：以上对TestAndSet和Swap指令的描述仅仅是功能实现，并非软件实现定义（软件实现也有类似，比如CAS），事实上它们是由硬件逻辑直接实现的，不会被中断。

应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。
在进入临界区之前先利用Swap指令交换lock与key的内容，然后检查key的状态；
有进程在临界区时，重复交换和检查过程，直到进程退出。

利用Swap指令实现进程互斥的算法描述如下：

1
2
3
4
5
6
key=true;
while(key!=false)
Swap(&lock, &key); 
// 进程的临界区代码段；
lock=false;
// 进程的其他代码；

硬件方法的优点：适用于任意数目的进程，不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。
硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

信号量

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

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

原语之所以不能被中断执行，是因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

整型信号量

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

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

wait操作中，只要信号量S<=0，就会不断地测试。
因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。

记录型信号量

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

记录型信号量可描述为：

1
2
3
4
typedef struct{
    int value;
    struct process *L;
} semaphore;

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

1
2
3
4
5
6
7
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中，可见该机制遵循了“让权等待”的准则。

1
2
3
4
5
6
7
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才可以执行。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
semaphore S = 0;  //初始化信号量
P1() {
    // …
    x;  //语句x
    V(S);  //告诉进程P2,语句乂已经完成
}

P2() {
    // …
    P(S) ;  //检查语句x是否运行完成
    y;  // 检查无误，运行y语句
    // …
}

利用信号量实现进程互斥

信号量机构也能很方便地解决进程互斥问题。

设S为实现进程Pl、P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1)。
只需把临界区置于P(S)和V(S)之间，即可实现两进程对临界资源的互斥访问。

其算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
semaphore S = 1;  //初化信号量
P1 ( ) {
    // …
    P(S);  // 准备开始访问临界资源，加锁
    // 进程P1的临界区
    V(S);  // 访问结束，解锁
    // …
}

P2() {
    // …
    P(S); //准备开始访问临界资源，加锁
    // 进程P2的临界区；
    V(S);  // 访问结束，解锁
    // …
}

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

利用信号量实现前驱关系

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

下图给出了一个前驱图，其中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。

image

实现算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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) 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。