背景、问题和基本概念

对于独立程序

  • 不和其他程序共享资源

  • 输入状态决定结果，具有确定性

  • 可重现起始条件

    在计算机科学中，再现性是指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果

  • 调度顺序不重要

但对于并发进程来说，多个进程间有资源共享，可能会因为不同顺序出现相互的干扰。从而

  • 产生不确定性
  • 不可重现
  • 未定义行为，程序错误是间歇性发生的

实际上我们又希望使用多进程并发执行，提升效率、实现协同、模块化设计等，所以我们需要使用一些方式来克服并发设计的坏处（例如，使用一些原子操作）。

原子操作（Atomic Operation）指一次不存在任何中断或者失败的操作，要么操作完成，要么没有执行，不会出现半途而废、部分执行的情况。

临界区

进程的交互关系，根据相互感知程度的不同分为如下三种：

相互感知的程度 交互关系 进程间的影响
相互不感知 独立 一个进程的操作对于其他进程的结果没有影响
间接感知（双方都与第三方方交互，如共享资源 ） 通过共享进行协作 一个进程的结果依赖于共享资源的状态
直接感知（双方直接交互，如通信） 通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息

同步问题的解决方案主要基于间接感知的部分，其中主要会有如下三种状态：

  • 互斥（mutual exclusion）：一个进程占用资源，其他进程无法使用
  • 死锁（deadlock）：多个进程各占用部分资源，形成循环等待
  • 饥饿（starvation）：其他进程轮流占用资源，一个进程一直得不到资源

其中最为基本的状态称为互斥，这即是一个良好的原子操作的思路。

我们将互斥资源存放的位置称为临界区，其上资源同时只允许一个进程的访问，临界区附近的代码结构通常如下：

  • 进入区（entry section）：检查是否可以进入临界区的一段代码，如果可以进入，则设定“正在进入临界区”标志
  • 临界区（critical section）：进程中访问临界资源的一段需要互斥执行的代码
  • 退出区（exit section）：清除“正在访问临界区”标志
  • 剩余区（remainder section）：跟同步互斥无关的代码

临界区的访问规则如下：

  • 空闲则入：没有进程在临界区时，任何进程可以进入
  • 忙则等待：有进程在临界区时，其他进程均不能进入临界区
  • 有限等待：等待进入临界区的进程不能无限等待
  • 让权等待(可选)：不需要访问临界区的进程，应当释放CPU

在具体实现过程当中，我们必须满足前三条规则。

实现方法

禁用中断

禁止硬件中断响应，因而对一个正在运行的不会发生上下文切换，且没有并发。

  • 硬件将中断处理延迟到中断使能之后
  • 现代计算机体系结构都提供指令来实现禁用中断

缺点：

  1. 禁用中断之后，进程无法停止
  • 整个系统都会为此停下来
  • 可能导致其他进程处于饥饿状态
  1. 临界区可能很长，无法确定中断响应时间

所以应该谨慎使用。

软件方法

设置一些全局的共享变量，来标识两个线程对互斥资源的占用情况，从而实现同步。

Peterson算法

共享变量

1
2
int turn; // 表示该谁进入临界区
boolean flag[]; // 表示进程申请进入临界区

进程i 进入区代码

1
2
3
4
flag[i] = true;
 //这里相当于谦让，让另一个进程优先获得权限
turn = j;
while (flag[j] && turn == j)

退出区代码

1
flag[i] = false;

当进程 j 没有申请进入临界区 则 flag[j] = false; turn = j;

那么进程 i 可以直接进入临界区

当进程 j 也申请进入临界区 则 flag[j] = true; turn 有 两种情况 当 进程 i 先写 turn = j; 进程 j 后写 turn = i; 时 turn = i;

那么进程 i 可以进入临界区 进程 j 不可以进入临界区

也就是说先写turn这个标志的能进入临界区，后写的要等待

Peterson算法完整代码

1
2
3
4
5
6
7
8
9
10
11
12
do {
    flag[i] = true;
    turn = j;
    while ( flag[j] && turn == j);
    
            CRITICAL SECTION

    flag[i] = false;

            REMAINDER SECTION

   } while (true);

Dekkers算法

Dekkers算法是Peterson算法的扩展。对比 Peterson算法，其优点是可以很方便扩展到多个线程（即Eisenberg and McGuire’s Algorithm）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
do {
    flag[i] = true;
    while flag[j] == true { 
        if turn != i {
            flag[i] = false;
            while turn != i;
            flag[i] = true;
        }
    }

        CRITICAL SECTION

    turn = j;
    flag[i] = false;
        EMAINDER SECTION
   } while (true);

进程 i 申请进入临界区 flag[i] = true;
当进程 j 也申请进入临界区 则 flag[j] = true;
这时再判断 turn 这个共享变量 允许哪个进程进入临界区
若不允许 则将进程 flag[i] = false; 并一直等待 直到允许

N线程的软件方法(Eisenberg 和 McGuire)

将线程排成环 若要进入临界区 则将 线程的 flag 标志 填写好 再去看 turn 标志

  • 线程Ti要等待从 turn 到 i-1的线程 都退出临界区后才能访问临界区
  • 线程Ti退出时 将turn改成下一个请求线程

https://piazza.com/class/i5j09fnsl7k5x0?cid=1217 详细解释

Eisenberg_McGuire

基于软件同步方法的缺点

  • 复杂
    • 需要两个进程间共享变量
  • 需要忙等待
    • 浪费CPU时间 (需要频繁查询共享变量的状态)

更高级的抽象方法

现代CPU体系结构提供的一些特殊原子操作指令

测试和置位指令(TS Test-and-Set)

  • 从内存单元中读取值
  • 测试该值是否为1(真或假)
  • 内存单元值设置为1
1
2
3
4
5
boolean TestAndSet(boolean *target){
    boolean rv = *target;
    *target = true;
    return rv:
}

交换指令(Exchange)

交换内存中的两个值

1
2
3
4
5
void Exchange (boolean *a, boolean *b){
    boolean temp = *a;
    *a = *b;
    *b = temp:
}

将上述的想法抽象成一个二进制的数据结构（锁定/解锁），称为锁（lock）。
它有两个主要API：

  • Lock::Acquire() 申请锁
  • Lock::Release() 释放锁

将相关的互斥操作封装好之后，使用锁来控制临界区访问就会变得非常简单。

TS指令实现自旋锁(Spinlock)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Lock {
    int value = 0;
}
/* 通过TS指令 读出 value的值 然后写入1
    若value为0 说明锁被释放 TS指令读出0 并写入 1 进入临界区
    若value为1 说明锁为忙状态 TS指令读出1 并写入 1 状态并没有改变 但是陷入循环 一直等待
*/
Lock::Acquire() {
   while (test-and-set(value))
      ; //spin
}
Lock::Release() {
    value = 0;
}

但上述的自旋等待锁存在忙等待的问题，我们可以在锁的数据结构中加入等待队列，避免CPU自旋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Lock {
   int value = 0;
   WaitQueue q;
}
Lock::Acquire() {
    /*
        若锁处于忙状态则将当前进程加入等待队列并执行调度程序
        使得其他进程可以占用CPU继续执行
    */
   while (test-and-set(value)) {
      add this TCB to wait queue q;
      schedule();
   }
}
Lock::Release() {
   value = 0;
   remove one thread t from q;
   /*
    将等待进程放到就绪队列里去 相当于唤醒等待进程
   */
   wakeup(t);
}

原子操作指令锁特征

  • 优点

    • 适用于单处理机或者共享内存的多处理机中任意数量的进程同步(禁用中断只适用于单处理机, 多处理机的情况下 禁止单个处理机的中断, 其他处理机仍然能够响应中断)
    • 简单且容易证明
    • 支持多临界区

  • 缺点：

    • 忙等待消耗处理器时间
    • 可能会导致饥饿
    • 可能会导致死锁：高优先级拥有CPU，低优先级拥有独占资源

常用三种同步实现方法总结

  • 禁用中断(仅限于单处理机)
  • 软件方法(共享变量 复杂)
  • 原子操作指令(单处理机或多处理机均可)