背景、问题和基本概念

对于独立程序

  • 不和其他程序共享资源

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

  • 可重现起始条件

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

  • 调度顺序不重要

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

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

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

原子操作(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,低优先级拥有独占资源

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

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