信号量: 一块资源 对于某种进程 所能容忍的 对该资源进行操作的 次数。

所谓操作，涵盖了生产和消费。

不是说生产者进程生产了，就是信号量要加 1 。相反，它需要减 1 。因为生产者进程对这块资源的生产就是对这块资源的操作，既然是操作，那么相应的，这类进程对这块资源的的信号量就要减 1。

虽然生产者进程的信号量变化不那么直观，但是消费者进程的信号量的变化还是很直观的。消费者消费了，就是对这块资源的一个申请，信号量就要减 1 。不消费了，就是一次释放，信号量自然要加 1 。

信号量(semaphore)，有两个著名操作，PV操作，这两个单词是荷兰语，就不深究为什么是P和V了。但是需要记得的是，P操作是申请资源，V操作是释放资源。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct semaphore {
    int count; // 记录资源个数
    PCB* queue; // 记录等待在该信号量上的进程
    
// 上面对信号量的解释其实是对count的解释，真正的信号量还应当包含一个队列，用来记录等待进程
}

void P(struct semaphore sem) {
    sem.count--; // 先申请再做下一步打算
    if (sem.count < 0) { // 先减再判断
        /* place this process in sem.queue */
        /* block this process */
    }
}

void V(struct semphore sem) {
    sem.count++; // 先释放再做下一步打算
    if (sem.count <= 0) { // 先加再判断
        /* remove the front process from sem.queue */
        /* place the process on ready list */
    }
}

用信号量可以实现判断是否要让一个进程睡眠还是唤醒，实现进程之间的同步。于是，信号量的count一定要正确，一定要对应上其队列中的个数。考虑下面一种情况。

1
2
3
4
5
6
7
void P(struct semaphore sem)
{
    // 将count--分解为
    register = count;
    register--;
    count = register;
}

有两个进程，可能会有如下的调度顺序

1
2
3
4
5
6
P1.register = count; // count == n
P1.register--;
P2.register = count; // count == n
P2.register--;
count = P1.register;
count = P2.register;

本来，count是要等于n-2，但是现在count等于n-1，于是错误就产生了。这是由于系统的进程调度机制导致的。

所以引出了临界区的概念，对信号量加上一层保护。

临界区：对于同一段代码，一次只允许一个进程进入。比如上面要修改信号量的值，一次应该只允许一个进程执行，所以将这段代码划为一个临界区。

为了实现对实现临界区的保护，还需要些两段代码：进入区和退出区。

下面要讲述的就是如何实现进入区和退出区。

临界区代码的保护原则：

  1. 互斥进入：如果一个进程在临界区中执行，则其它进程不允许进入。这种进程间的约束关系称为互斥（mutual exclusion）
  2. 有空让进：如果当临界区空闲时，有一个进程想要进去，就必须让该进程马上进入
  3. 有限等待：从进程发出请求进入临界区到允许进入，不能无限等待

轮换法(值日法)

1
2
3
4
5
6
7
8
9
10
11
12
int turn = 0;
进程P0 {
    while (turn != 0); // 空转
    /* 临界区 */
    turn = 1; // 退出区
}

进程P1 {
    while (turn != 1); // 空转
    /* 临界区 */
    turn = 0; // 退出区
}

大概意思就是，没轮到我执行就空转，我执行好了，就把执行机会让给你

轮换法的缺点：把turn交给对方后，对方迟迟不肯使用，导致我方也无法使用。不符合有空让进原则

标记法

1
2
3
4
5
6
7
8
9
10
11
12
13
进程P0 {
    flag[0] = true;
    while (flag[1]); // 空转
    /* 临界区 */
    flag[0] = false; // 退出区
}

进程P1 {
    flag[1] = true;
    while (flag[0]); // 空转
    /* 临界区 */
    flag[1] = false; // 退出区
}

大概意思是，到我执行了，我先打个标记表示我要执行了，如果你先打了标记，就空转等你执行好。我执行好了就把标记撤下来。

标记法的缺点：因为系统调度的缘故，在对方标记的同时，我方也进行了标记，导致二者进入僵持状态，都不进入临界区，不满足有限等待原则

上面讲述的是两个小方法，各有优缺点，并不能很好的满足要求。

Perterson算法

  • 结合了轮转和标记两种方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
进程P0 {
    flag[0] = true;
    while (flag[1] && turn == 1); // 空转
    /* 临界区 */
    flag[0] = false; 
    turn = 1;        //退出区
}

进程P1 {
    flag[1] = true;
    while (flag[0] && turn == 0); // 空转
    /* 临界区 */
    flag[1] = false;
    turn = 0;        // 退出区
}

空转的条件更加严格，对方已经先打上了标记并且我方之前已经把执行的机会让给了对方

靠一个turn满足了互斥原则

我如果想进，就先打上标记，如果此时turn在对方那，但是对方阻塞了没有打上标记，此时不满足空转条件，我就能进去，满足了有空让进原则

在满足了有空让进原则的前提下，我进去执行时，对方如果也想进去，此时我已经打上了标记并且执行权在我这，对方进入空转；我执行好后，就算只先把标记撤掉，对方也能满足进入临界区的条件。满足了有限等待原则

Peterson算法只能满足两个进程，如果有多个进程，就需要进化为面包店算法

下面讲述三个主要的算法

面包店算法

  • 如何轮转：每个进程获得一个序号，序号最小的的进入临界区
  • 如何标记：序号不为0表示打上标记，进程在退出区将序号置为0
1
2
3
4
5
6
7
8
9
10
11
12
进程Pi {
    choosing[i] = true; // 开始选号
    num[i] = max(num[0],...,num[n-1]) + 1;
    choosing[i] = false; // 选号结束
    for (j = 0; i < n; j++) {
        while (choosing[j]); // 等别人选完号
        while (num[j] != 0 && num[j] < num[i]);
    }
    /* 临界区 */
    num[i] = 0; // 退出区
    }
}

只有最小号进程能够进入，满足互斥原则

如果没有进程在临界区中，最小序号一定能够进入，满足有空让进原则

等待前面的进程执行完后就轮到了，满足有限等待原则

关中断

调度由中断触发，只要关中断，调度也就不会触发，就能保证只有一个进程进入临界区

1
2
3
4
5
进程Pi {
	cli(); // close interrupt关中断，系统调用函数，只有一条内嵌汇编指令用于关中断
	/* 临界区 */
	sti(); // start interrupt开中断   
}

中断的开关是由INTR这个寄存器实现的，如果INTR为 1 表示关中断，中断不会触发也就不会有别的进程进入同一个临界区。但是如果是多CPU或者多核处理器，每个CPU都有自己的INTR这时就有可能导致别的进程进入临界区

硬件原子指令

1
2
3
4
5
6
7
8
9
10
11
bool TestAndSet(bool& x) // 原子函数，三段代码一次执行完毕
{
    bool rv = x;
    x = true;
    return x;
}
进程Pi {
    while (TestAndSet(lock)); // lock==true表示被锁上了，空转
    /* 临界区 */
    lock = false; //退出区，解锁
}

会有硬件确保TestAndSet()不会被打断

用临界区去保护信号量，用信号量去实现同步