操作系统之 同步互斥

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

并发进程的正确性

执行过程是不确定性和不可重现的 程序错误可能是间歇性发生的

  • 独立进程
    • 不和其他进程共享资源或状态
    • 确定性 输入状态决定结果
    • 可重现 能够重现起始条件
    • 调度顺序不重要
  • 并发进程
    • 在多个进程间有资源共享(都要CPU 内存)
    • 不确定性
    • 不可重现

进程并发执行的好处

进程需要与计算机中其他进程或设备进行协作

  1. 共享资源
  2. 加速
    • I/O操作和CPU计算可以并行
    • 程序可划分成多个模块放在多个处理机上并行执行
  3. 模块化
    • 将大程序分解成小程序(gcc会调用 cpp cc1 cc2 as ld)
    • 使系统易于复用和扩展

原子操作(Atomic Operation)

一次不存在任何中断或失败的操作 要么执行成功 要么没有执行

操作系统需要利用同步机制 即允许并发执行 以便进行资源共享 和提高速度 同时保证一些操作是原子操作

进程的交互关系

  • 互斥(Mutual Exclusion)
    • 一个进程占用资源 其他进程不能使用
  • 死锁(Deadlock)
    • 多个进程各占用部分资源 形成循环等待
  • 饥饿(Starvation)
    • 其他进程可能轮流占用资源 一个进程一直得不到资源

临界区(Critical Section)

进程访问临界资源的一段需要互斥执行的代码 

1
2
3
4
entry section
    critical section
exit section
    remainder section
  • 进入区(entry section)
    • 检查 可否 进入临界区的一段代码
    • 若可进入 设置相应 正在访问临界区 标志
  • 退出区(exit section)
    • 清除 正在访问临界区 标志
  • 剩余区(remainder section)
    • 代码中的其余部分

临界区访问规则

  • 空闲则入
    • 没有进程在临界区时 任何进程可进入
  • 忙则等待
    • 有进程在临界区时 其他进程不能进入临界区
  • 有限等待
    • 等待进入临界区的进程不能无限期等待
  • 让权等待(可选)
    • 不能进入临界区的进程 应释放CPU

临界区的实现方法

  • 禁用中断
  • 软件方法(共享变量)
  • 更高级的抽象方法(操作系统)

不同临界区实现机制衡量标准

  • 性能和并发级别

禁用中断

没有中断 没有上下文切换 因此没有并发

  • 硬件将中断处理延迟到中断被启用之后
1
2
3
local_irq_save(unsigned long flags);
critical section
local_irq_restore(unsigned long flags);
  • 进入临界区
    • 禁止所有中断 并保存标志
  • 退出临界区
    • 使能所有中断 并恢复标志
禁用中断缺点
  • 禁用中断后 进程无法被停止
    • 整个系统为此停下来
    • 可能导致其他进程处于饥饿状态
  • 临界区可能很长
    • 导致无法确定响应中断所需的时间

基于软件同步方法

线程通过共享变量来同步它们的行为

Peterson算法

共享变量

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

进程i 进入区代码

1
2
3
flag[i] = true;
turn = j;
while (flag[j] && turn == j)

退出区代码

1
flag[i] = false;
1
2
3
4
5
6
7
8
9
当进程 j 没有申请进入临界区 则 flag[j] = false;  turn = j;

那么进程 i 可以直接进入临界区
 
当进程 j 也申请进入临界区 则 flag[j] = true; turn 有 两种情况 当 进程 i 先写 turn = i; 进程 j 后写 turn = j; 时 turn = j;
 
那么进程 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算法

对比 Peterson算法 优点是可以很方便扩展到多个线程

1
2
3
4
进程 i 申请进入临界区 flag[i] = true;
当进程 j 也申请进入临界区 则 flag[j] = true;
这时再判断 turn 这个共享变量 允许哪个进程进入临界区
若不允许 则将进程 flag[i] = false; 并一直等待 直到允许
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);
N线程的软件方法(Eisenberg 和 McGuire)

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

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

Eisenberg_McGuire

基于软件同步方法的缺点
  • 复杂
    • 需要两个进程间共享变量
  • 需要忙等待
    • 浪费CPU时间 (需要频繁查询共享变量的状态)

更高级的抽象方法

硬件提供一些同步原语

  • 中断禁用
  • 原子操作指令(从硬件上保证其原子性)
锁(Lock)

一个抽象的数据结构 基于原子操作指令

  • 一个二进制变量(锁定/解锁)
  • Lock::Acquire()
    • 锁被释放前一直等待 然后得到锁
  • Lock::Release()
    • 释放锁 唤醒任何等待的进程

原子操作指令

现代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:
}
TS指令实现自旋锁(Spinlock)

线程在等待的时候消耗CPU时间

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;
}
TS指令实现无忙等待锁

在锁的数据结构中加入等待队列

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);
}

原子操作指令锁特征

  • 优点
    • 适用于单处理机或者共享内存的多处理机中任意数量的进程同步(禁用中断只适用于单处理机 多处理机的情况下 禁止单个处理机的中断 其他处理机仍然能够响应中断)
    • 简单且容易证明
    • 支持多临界区
  • 缺点
    • 忙等待锁会消耗处理机时间
    • 可能导致饥饿 进程离开临界区时有多个等待进程的情况
  • 死锁
    • 拥有临界区的低优先级进程 但请求访问临界区的高优先级进程获得处理机并等待临界区

同步方法总结

锁是一种高级的同步抽象方法

  • 互斥可以使用锁来实现
  • 需要硬件支持

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

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