临界区互斥的软件及抽象方法

发表于 | 分类于
字数统计: 1,302

临界区

在每个进程中，访问互斥资源的代码段称为临界区。为了实现对资源互斥，在每一个时刻，只允许一个进程进入临界区执行相应的代码。如何控制一个进程进入，而其他进程被”卡住”，就是接下来要解决的问题。

互斥的四个条件

  • 忙则等待：任何两个进程不能同时处于临界区
  • 不应对CPU的速度和数量做任何假设
  • 让权等待：临界区外运行的进程不得阻塞其他进程，不能忙等
  • 有限等待：不得使进程无限期等待进入临界区

基本实现机制

  • 基于硬件的禁用中断——无法进行上下文切换，失去了并发，在多CPU中都不能工作。更严重的是，无法限制响应中断所需的时间，因为时钟中断也被屏蔽了，在临界区中的进程无法被停止
  • 基于软件的方法（如Peterson算法）
  • 更高级的抽象（锁，信号量，管程）

软件方法的演进

进程临界区处理的抽象结构(此处及以后均用伪代码表达)

1
2
3
4
5
6
do{
  enter section
    	critical section
  exit section
    	reminder section //提醒其他线程
}while(1);

单标志法(交替进入)

设置一个共享变量int turn = i; 表示现在轮到哪个进程

对于第i个进程，enter section：while(turn != i)； exit section: turn = j;

缺点：实现了互斥，但不满足前进属性。必须交替执行，违背“空闲让进”

双标志法先检查(先看排队)

设置一个数组int flag[n]; 当flag[i] = 1时表示进程 i 有进入临界区的意愿

对于第i个进程，enter section：while(flag[j] == 1)；flag[i]=1; 若无进程进入临界区则置自己的标志位

exit section: flag[i] = 0;

缺点：不满足互斥。可能同时查询同时置位，同时进入临界区。根本原因是置位过程被打断。

双标志法后检查(先抢位置)

enter section：flag[i]=1； while(flag[j] == 1);

缺点：满足互斥，但可能死锁。同时置位后都停在while死循环，都无法进入。

Peterson算法(两个进程)

同时使用 turn 和 flag

enter section：flag[i]=1；turn = j; while(flag[j] == 1 && turn == j); 先“谦让”一下，让对方先进，如果对方恰好有进入的意愿，则自己保持等待；对方不进则自己进。

Bakery算法(n个进程)

  1. 进入临界区之前，进程接收一个数字(请求号)，数字小的进入
  2. 若数字相同，比较进程号，i < j 则 i 进
  3. 编号方案总是按照枚举的增加序列生成数字

软件方法的缺点

  • 需要进程间共享数据项
  • while循环需要CPU忙等
  • 实现上需要硬件原子指令LOAD和STORE的支持

更高级的抽象

操作系统基于硬件的中断、原语提供更高级的编程抽象来简化并行编程。

硬件基础

通过特殊的内存访问电路提供特殊的原子操作指令

  • TestAndSet：从内存读值判断是否为1，内存值设为1
1
2
3
4
5
boolean TestAndSet(boolean *target){
  boolean rv = *target;
  *target = True;
  return rv;
}
  • Swap：交换内存中的值
1
2
3
4
5
viod Swap(boolean *a,boolean *b){
  boolean temp = *a;
  *a = *b;
  *b = temp;
}

以上指令虽然由多条操作组成，但在体系结构中已经被封装成了一条机器指令，由硬件逻辑直接实现，不会被中断。

锁(抽象数据结构)

忙等锁
  • class Lock{int value = 0;} 加锁/解锁
  • Lock :: Acquire(){while(TestAndSet(value));} 锁被释放前一直等待，直到得到锁
  • Lock :: Release(){value = 0;} 释放锁，唤醒等待进程

以上方法支持n个进程，但是仍然是忙等，使用忙等方式的锁称为自旋锁

改进：

无忙等锁(增加一个等待队列)

  • class Lock{int value = 0;WaitQueue q;} 

  • 1
    2
    3
    4
    5
    6
    Lock :: Acquire(){
      while(TestAndSet(value)){
        add this TCB to wait queue q;
        schedule();
      }
    }
  • 1
    2
    3
    4
    5
    Lock :: Release(){
      value = 0;
      remove one thread t from q;
      wakeup(t);
    }

挂到阻塞队列后，睡眠等待，让出CPU。因为有上下文切换的开销，更适用于临界区较长的情况。

基于Swap的锁
  • 共享数据 int lock = 0;
  • enter section：key=1; while(key == 1){Swap(lock,key);}
  • exit section: lock = 0;

只有lock为0时，才能通过Swap使得key为0 ，打破while循环。

可能存在的问题

优先级反转造成死锁：若一个低优先级的进程拥有临界区，一个高优先级进程获得CPU并等待临界区，那么低优先级进程就无法获得CPU以继续执行释放锁，导致死锁。根本原因是互斥资源占用顺序和CPU优先级不匹配，解决优先级反转问题有优先级天花板(priority ceiling)和优先级继承(priority inheritance)两种办法，其实就是对低优先级进程的优先级进行提升。

基于忙等的方式都可能存在优先级反转问题，所以还可以用睡眠与唤醒的方式来解决。