同步互斥
背景
并发进程的正确性
-
独立进程
- 不和其它进程共享资源或状态
- 确定性——输入状态决定结果
- 可重现——能够重现起始条件
- 调度顺序不重要
-
并发进程
- 在多个进程间有资源共享
- 不确定性
- 不可重现
-
并发进程的正确性
- 执行过程是不确定性和不可重现的
- 程序错误可能是间歇性发生的
进程并发的好处
-
资源共享
- 一台电脑，多个用户
-
加速
- I/O操作和计算可以重叠
- 多处理器——将程序分成多个部分并行执行
-
模块化
- 将大程序分解成小程序
- 使系统易于扩展
概念
原子操作
- 原子操作是指一次不存在任何中断或失败的操作
- 要么操作成功完成
- 或者操作没有执行
- 不会出现部分执行的状态
临界区（Critical Section）
- 临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时不会被执行的代码区域
互斥（Mutual exclusion）
- 当一个进程处于临界区并仍访问共享资源时，没有其它进程会处于临界区并且访问任何相同的共享资源
死锁（Dead lock）
- 两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去
饥饿（Starvation）
- 一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行
临界区
- 互斥：同一间临界区最多存在一个线程
- Progress：如果一个线程想要进入临界区，那么它最终会成功
- 有限等待：如果一个线程i处于入口区，那么在i的请求被接受之前，其它线程进入临界区的时间是有限制的
- 无忙等待（可选）：如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起
方法1：禁用硬件中断
-
没有中断，没有上下文切换，因此没有并发
- 硬件将中断处理延迟到中断被启用之后
- 现代计算机体系结构都提供指令来实现禁用中断
进入临界区：禁止所有中断，并保存标志
离开临界区：使能所有中断，并恢复标志
-
缺点
- 禁用中断后，进程无法被停止。整个系统都会为此停下来；可能导致其它进程处于饥饿状态
- 临界区可能很长。无法确定响应中断所需的时间
- 小心使用
方法2：基于软件的解决方法
Peterson算法
-
满足线程Ti和Tj之间互斥的经典的基于软件的解决方法（1981年）
int turn; boolean flag[]; do{ flag[i] =true; turn =j; while(flag[j] && turn ==j); CRITICAL SECTION flag[i] =false; REMAINDER SECTION }while(true);
Dekkers算法
-
线程Ti的代码
flag[0]:= false; flag[1]:= false; turn:= 0;//or1 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);
Bakery算法
- N个进程的临界区
- 进入临界区之前，进程接收一个数字
- 得到的数字最小的进入临界区
- 如果进程Pi和Pj收到相同的数字，那么如果i<j，Pi先进入临界区，否则Pj先进入临界区
- 编号方案总是按照枚举的增加顺序生成数字
缺点
- 复杂
- 需要忙等待，浪费CPU时间
方法3：更高级的抽象
硬件提供了一些同步原语：中断禁用、原子操作指令等
-
操作系统提供更高级的编程抽象来简化进程同步
- 例如：锁、信号量
- 用硬件原语来构建
-
锁是一个抽象的数据结构
- 一个二进制状态（锁定/解锁）。两种方法
- Lock: Acquire()——锁被释放前一直等待，然后得到锁
- Lock: Release()——释放锁，唤醒任何等待的进程
-
使用锁来编写临界区
lock_next_pid ->Acquire(); new_pid =next_pid++; lock_next_pid ->Release(); -
大多数现代体系结构都提供特殊的原子操作指令
- 通过特殊的内存访问电路
- 针对处理器和多处理器
-
Test-and-Set测试和置位
从内存中读取值
测试值是否位1（然后返回真或假）
-
内存值设置为1
void TestAndSet(boolean *target){ boolean rv =*target; *target =true; return rv; }
-
交换：交换内存中的两个值
void Exchange(boolean *a, boolean *b){ boolean temp =*a; *a =*b; *b =temp; } -
使用TAS指令实现自旋锁（spinlock）
-
忙等待：适合临界区较短
class Lock{ int value =0; } Lock::Acquire(){ while(test-and-set(value)); //spin /* 如果锁被释放，那么TS指令读取0并将值设置为1——锁被设置为忙并且需要等待完成 如果锁处于忙状态，那么TS指令读取1并将值设置为1——不改变锁的状态并且需要循环 */ } Lock::Release(){ value =0; } -
无忙等待，适合临界区较长
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); }
-
-
优点
- 适用于单处理器或者共享主存的多处理器中任意数量的进程同步
- 简单并且容易证明
- 支持多临界区
-
缺点
- 忙等待消耗处理器时间
- 可能导致饥饿。进程离开临界区时有多个等待进程的情况
- 死锁
更多精彩，关注“咋家”
