09-同步
一、背景
到目前为止
- 多道程序设计（multi-programming）: 现代操作系统的重要特性
- 并行很有用（为什么？）多个并发实体CPU(s) I/O 用户
- 进程/线程: 操作系统抽象出来用于支持多道程序设计
- CPU调度：实现多道程序设计的机制
- 调度算法 -不同的策略
接下来 - 协同多道程序设计和并发问题
独立的线程
- 不和其他线程共享资源或状态
- 确定性->输入状态决定结果
- 可重现->能够重现起始条件
- 调度顺序不重要
合作线程
- 在多个线程中共享状态
- 不确定性
- 不可重现
不确定性和不可重现意味着bug可能是间歇性发生的
进程/线程, 计算机/设备需要合作
优点1：共享资源
- 一台电脑，多个用户
- 嵌入式系统（机器人控制：手臂和手的协调）
优点2：加速 - I/O操作和计算可以重叠
- 多处理器-将程序分成多个部分并行执行
优点3：模块化 - 将大程序分解成小程序 以编译为例：gcc会调用cpp,cc1,cc2,as,ld
- 使系统易于扩展
无论多个线程的指令序列怎样交替执行，程序都必须正常工作
多线程程序具有不确定性和不可重现的特点
不经过专门设计，调试难度很高
不确定性要求并行程序的正确性
先思考清楚问题，吧程序的行为设计清楚
切忌基于着手写代码，碰到问题再调试
一些概念
Race Condition(竞态条件)
系统缺陷：结果依赖于并发执行或者时间的顺序/时间
- 不确定性
- 不可重现
如何避免竞态
原子操作 Atomic Operation
- 原子操作是指一次不存在任何中断或失败的执行
该执行成功结束
或者根本没有执行
并且不应该发现任何部分执行的状态 - 实际上操作往往不是原子的
有些看上去是原子操作
连x++这样的简单语句，实际上是由3条指令构成的
有时候甚至连单条机器指令都不是原子的 Pipeline,super-scalar, out-of-order, page fault
critical section(临界区)
临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域
Mutual exclusion(互斥)
当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源
Dead lock(死锁)
两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去
Starvation(饥饿)
一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行
Lock(锁)
在门，抽屉等物体上加上保护性装置，使得外人无法访问物体内的东西，只能等待解锁后才能访问
Unlock(解锁)
打开保护性装置，使得可以访问之前被锁保护的物体类的东西
DeadLock(死锁)
A拿到锁1，B拿到锁2，A想继续拿到锁2后再继续执行，B想拿到锁1后再继续执行。导致A和B谁也无法继续执行
二、临界区
互斥
同一时间临界区中最多存在一个线程
Progress
如果一个线程想要进入临界区，那么它最终会成功
有限等待
如果一个线程i处于入口区，那么在i的请求被接受之前，其他进程进入临界区的时间是有限的
无忙等待（可选）
如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起
如何实现对临界区代码的保护？有以下三种方法
三、方法1：禁用硬件中断
没有中断。没有上细问切换，因此没有并发
- 硬件将中断处理延迟到中断被启用之后
- 大多数现代计算机体系结构都提供指令来完成
进入临界区
- 禁用中断
离开临界区
- 开启中断
一旦中断被禁用，线程就无法被停止
- 整个系统都会为你停下来
- 可能导致其他线程处于饥饿状态
要是临界区可以任意长怎么办
- 无法限制响应中断所需的时间（可能存在硬件影响）
要小心使用
不适用于多CPU的情况
四、方法2：基于软件的解决方法
Peterson 算法(针对两个进程)
do {
flag[i] = TRUE;
turn = j;
while(flag[j] && turn ==j);
CRITICAL SECTION
flag[i] = FALSE;
REMAINDER SECTION
} while (TRUE)
Dekker 算法
flag[0]:=false flag[1]:=false turn :=0 // or 1
do {
flag[i]=TRUE;
while flag[j]=true {
if turn!=i {
falg[i]!= false;
while turn != i {}
flag[i]:=TRUE
}
}
CRITICAL SECTION
turn:=j
flag[i]=TRUE
REMAINDER SECTION
} while (TRUE)
Bakery 算法
N个进程的临界区
- 进入临界区之前，进程接收一个数字
- 得到数字最小的进入临界区
- 如果进程Pi和Pj收到相同的数字，那么如果i<j, Pi先进入临界区，否则Pj先进入临界区
- 编号方案总是按照枚举的增加顺序生成数字
Dekker算法（1965）：第一个针对双线程例子的正确解决方案
Bakery算法（Lamport 1979）: 针对n线程的临界问题解决方案
复杂：需要两个进程间的共享数据项
需要忙等待：浪费CPU时间
没有硬件保证的情况下无真正的软件解决方案： Peterson算法需要原子的LOAD和STORE指令
五、方法3：更高级的抽象
- 硬件提供了一些原语
像中断禁用，原子操作指令等
大多数现代体系结构都这样 - 操作系统提供更高级的编程抽象来简化并行编程
例如：锁，信号量
从硬件原语中构建 - 锁是一个抽象的数据结构
一个二进制状态（锁定、解锁），两种方法
Lock::Acquire() -锁被释放前一直等待，然后得到锁
Lock::Release() -释放锁，唤醒任何等待的进程 - 使用锁来编写临界区
前面的例子变得简单起来lock_next_pid->Acquire(); new_pid = next_pid++; lock_next_pid->Release(); - 大多数现代体系结构都提供特殊的原子操作指令
通过特殊的内存访问电路
针对单处理器和多处理器 - Test-and-Set测试和置位
从内存中读取值
测试该值是否为1（然后返回真或假）
内存值设置为1 - 交换
交换内存中的两个值boolean TestAndSet(boolean *target) { boolean rv = *target; *target = TRUE; return rv; } void Exchange(boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp; }
使用 TestAndSet 方法实现锁
class Lock {
int value=0;
}
Lock::Acquire() {
while (test-and-set(value));//spin
}
// 如果锁被释放，那么test-and-set读取0并将值设置为1 -> 锁被设置为忙并且需要等待完成
// 如果锁处于忙状态，那么test-and-set读取1并将值设置为1 -> 不改变所得状态并且需要循环（自旋spin）
Lock::Release() {
value=0;
}
- 使用忙等待的锁
就像上面使用test-and-set实现的锁一样
线程在等待的时候消耗CPU周期
如何做的更好？
无忙等待
class Lock {
int value = 0;
WaitQueue q;
}
Lock::Acquire(){
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);
}
使用 change方法实现锁
共享数据（初始化为0）
int lock= 0；
线程 Ti
int key;
do {
key=1;
while(key==1) exchange(lock,key);
critical section
lock = 0;
remainder section
}
-
优点
适用于单处理器或者共享主存的多处理器中任意数量的进程
简单并且容易证明
可以用于支持多临界区 -
缺点
忙等待消耗处理器时间
当进程离开临界区并且多个进程在等待的时候可能导致饥饿
死锁
如果一个低优先级的进程拥有临界区并且一个该优先级的进程也需求，那么高优先级进程会获得处理器并等待临界区 -
锁是更高等级的编程抽象
互斥可以使用锁来实现
通常需要一定等级的硬件支持 -
常用的三种实现方法
禁用中断（仅限于单处理器）
软件方法（复杂）
原子操作指令（单处理器或多处理器均可） -
可选的实现内容
有忙等待
无忙等待