临界区互斥

一、基本概念

1.1 临界概念

定义：

• 临界资源：一次仅允许1个进程/线程使用的资源。比如，进程间的共享内存
• 临界区：对临界资源进行访问的代码片段。比如，进程中对共享内存进行访问的程序片段

1.2 同步

• 同步是一种进程/线程之间的合作关系
• 为完成某种任务而建立的多个进程或者线程之间的协调调用，次序等待，传递消息告知资源占用情况
• 同步是一种协调关系，为的是有序地运行

1.3 互斥

• 互斥是一种进程/线程之间的制约关系
• 当一个进程/线程进入临界区时，其他进程/线程必须等待
• 互斥具有唯一性和排它性，为的是避免访问冲突

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

为禁止2个进程/线程同时进入临界区，需满足以下条件：

• 空闲等待：临界区空闲时，允许进程/线程进入临界区
• 忙则等待：2个进程/线程不允许同时处于临界区，后来的进程/线程必须等待
• 有限等待：不能让进程/线程无限期地等待进入临界区
• 让权等待：当进程/线程不能进入临界区时，应立即释放处理器，防止忙等待

2.1 软件方法

2.1.1 锁变量法

直接用1个全局锁变量，其初始值为0，来记录当前进入临界区的进程：

int turn;

/* 进入临界区 */
void enter_region(int process)                          /* 当前进程号 */
{
    while (turn != 0);                                  /* 其他进程正在访问临界区 */
    turn = process;                                     /* 设置临界区访问标志 */
}

/* 离开临界区 */
void leave_region(int porcess)                          /* 当前进程号 */
{
    turn = 0;                                           /* 设置临界区访问标志 */
}

这种方法有可能导致2个进程同时进入临界区。

因为 while(turn != 0) 这一处代码有可能被2个进程同时执行，然后验证都能通过。

2.1.2 双标志法

2个线程时，给每个进程1个标志，用于表示当前线程正处于临界区内：

int interested[2]

/* 进入临界区 */
void enter_region(int process)                          /* 当前进程号，进程号是0或1 */
{
    int other;
    other = 1 - process;                                /* 另一方进程号 */
    while (interested[other] == 1);                     /* 另一方进程正在访问临界区 */
    interested[process] = 1;                            /* 设置当前进程状态 */
}

/* 离开临界区 */
void leave_region(int porcess)                          /* 当前进程号，进程号是0或1 */
{
    interested[process] = 0;                            /* 设置当前进程状态 */
}

和锁变量法一样，同样存在2个进程同时进入临界区的情况。

while (interested[other] == 1); 可能会并发同时执行，2个进程验证都能通过。

2.13 Peterson 算法

当2个进程同时要访问临界区时，结合锁变量 + 双标志法，后进入的线程需等待前一个线程执行完成：

int turn;
int interested[2]

/* 进入临界区 */
void enter_region(int process)                          /* 当前进程号，进程号是0或1 */
{
    int other;
    other = 1 - process;                                /* 另一方进程号 */
    interested[process] = 1;                            /* 设置当前进程状态 */
    turn = process;                                     /* 设置临界区访问标志 */
    while (turn == process && interested[other] == 1);  /* 另一方进程正在访问临界区 */
}

/* 离开临界区 */
void leave_region(int porcess)                          /* 当前进程号，进程号是0或1 */
{
    interested[process] = 0;                            /* 设置当前进程状态 */
}

在2个进程的情况下，可以保证在同一时间段内，只有1个进程能够访问临界区。

后来的进程会在 while (turn == process && interested[other] == 1); 这里等待前一个进程退出临界区为止。

2.2 硬件方法

2.2.1 中断屏蔽法

进程切换，只会在 CPU 发生中断的情况下，所以只要禁止一切中断，就能避免进程切换。

它的基本模式如下：

/* 进入临界区 */
void enter_region(int process)
{
    关闭中断
}

/* 离开临界区 */
void leave_region(int porcess)
{
    打开中断
}

屏蔽中断，实际上只会对单处理器生效。

比如说，在处理器1上屏蔽中断，是不会影响到处理器2的中断的，处理器2依旧能正常处理中断信号。

所以，屏蔽中断法，只能对单处理器生效，对于多处理器还是有问题的。

2.2.2 硬件指令法

计算机中有一些特殊的硬件指令，允许对一个内存字的内容进行检测和修改，并且保证读和写是不可分割的。即在该指令结束前，其他处理器均不允许访问该内存字。

这种硬件的原子指令，基本都是通过锁住内存总线，以达到禁止其他 CPU 访问内存字的目的。

屏蔽中断和锁住总线的区别：

• 屏蔽中断：只会对当前 CPU 生效，不影响其他 CPU 的中断处理
• 锁住总线：对所有 CPU 生效，因为 CPU 读写内存字，必须要经过内存总线

通过锁住总线的方式，可以避免多个 CPU 同时访问相同的内存字。

硬件指令法，实际上就是硬件版的锁变量法：

1. 首先为每个临界区都设置一个共享变量 lock
2. 然后利用硬件的原子指令设置 lock 的值
3. 设置成功的进程，就拿到了临界区的访问权
4. 设置不成功的进程，就进行自旋等待

具体看一下有哪些原子指令可以实现互斥。

(1) TestAndSet 指令

TestAndSet 指令的作用就是测试并设置内存字的值。

这类指令有 TSL 指令，它会将一个内存字读到寄存器，并在该内存地址上设值一个非零值。

伪代码类似这样（实际由硬件实现，是不可分割的原子操作）：

int TestAndSet (int *lock) {
    int old;
    old = *lock;
    *lock = 1;
    return old;
}

利用这个指令实现的临界区互斥方法：

/* 进入临界区 */
void enter_region(int *lock)
{
    while (TestAndSet(lock));      /* 自旋加互斥锁 */
}

/* 离开临界区 */
void leave_region(int *lock)
{
    *lock = 0;                     /* 释放互斥锁 */
}

硬件原子指令保证 TestAndSet(&lock) 是不可分割的，所以不存在2个进程都验证通过的情况。

(2) Swap 指令

Swap 指令的作用就是交换2个位置的内存，而且是原子不可分割的。

这类指令有 XCHG 指令，它可以交换2个位置的内存。

伪代码类似这样（实际由硬件实现，是不可分割的原子操作）：

void Swap (int *a, int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

利用这个指令实现的临界区互斥方法：

/* 进入临界区 */
void enter_region(int *lock)
{
    while (Swap(&lock, 1));        /* 自旋加互斥锁 */
}

/* 离开临界区 */
void leave_region(int *lock)
{
    *lock = 0;                     /* 释放互斥锁 */
}

硬件原子指令保证 Swap(&lock, 1) 是不可分割的，所以也不存在2个进程都验证通过的情况。

总结

临界概念：

• 临界资源：一次仅允许1个进程/线程使用的资源。比如，进程间的共享内存
• 临界区：对临界资源进行访问的代码片段。比如，进程中对共享内存进行访问的程序片段

同步：

• 同步是一种进程/线程之间的合作关系
• 为完成某种任务而建立的多个进程或者线程之间的协调调用，次序等待，传递消息告知资源占用情况
• 同步是一种协调关系，为的是有序地运行

互斥：

• 互斥是一种进程/线程之间的制约关系
• 当一个进程/线程进入临界区时，其他进程/线程必须等待
• 互斥具有唯一性和排它性，为的是避免访问冲突

临界区互斥实现：

• 软件互斥：
  • 锁变量法和双标志法，都不是完美的临界区互斥实现
  • Peterson 算法，可以正确互斥，保证2个进程互斥访问临界区
  • 只支持2个进程的互斥，自旋等待可能非常占用 CPU 资源
• 硬件互斥：
  • 中断屏蔽法，只对单处理器保证互斥访问临界区，多处理器无效
  • 硬件指令法，可以保证对多处理器下互斥访问临界区
  • 支持任意进程数量的互斥，支持进程有多个临界区（设多个临界区锁变量即可）
• 软硬件互斥实现，都有忙等待的缺点