临界区与原子操作

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟

并发访问控制

通过互斥访问保障 多进程/多线程正确地使用共享资源

临界区（Critical Section）

进程中访问临界资源（共享资源）的一段需要互斥执行的代码

进入临界区

  • 检查是否可以进入临界区
  • 如果可以进入，则设置相应“正在访问临界区”的标志

退出临界区

  • 清除“正在访问临界区”的标志

原子操作

  • 原子操作是指一次不存在任何中断或失败的操作
    • 只有可能操作成功完成
    • 或者操作完全没有执行
    • 不可能出现操作部分执行的状态
  • 对临界区的操作必须是原子操作，进入临界区的操作也必须要是原子操作
  • 操作系统需要利用同步机制在进线程并发执行的同时，保证一些操作是原子操作

同步机制

  • 第一步：识别出共享资源和使用者
  • 第二步：设计合适的同步机制
  • 第三步：验证临界区是否符合原子操作

以协调采购为例：

时间 A B
3:00 查看冰箱发现没有面包
3:05 离开家去商店
3:10 到达商店 查看冰箱发现没有面包
3:15 购买面包 离开家去商店
3:20 到家并把面包放进冰箱 到达商店
3:25 购买面包
3:30 到家并把面包放进冰箱

方案一

方案描述

  • 在冰箱上设置一把锁和钥匙
  • 去买面包前锁住冰箱并且拿走钥匙

临界区

  • 进入临界区：锁住冰箱并拿走钥匙
  • 临界区操作：去商店买面包
  • 退出临界区：打开冰箱，放入面包，放回钥匙

缺点：

  • 进入临界区的时候锁住的资源太大，让冰箱内的其他食品也无法被取到

方案二

方案描述

  • 利用便签来避免购买太多的面包
  • 购买之前留下一张便签
  • 购买完之后把便签移除
  • 当其他人看到标签后，就不会再去购买面包

临界区

  • 进入临界区：查看别人是否留便签，若没有人留下便签，则留下便签
  • 临界区操作：去商店买面包
  • 退出临界区：拿走便签

缺点

  • 如果在检查面包和标签后、贴标签之前，有其他人也检查了面包和便签
    • 可能会购买太多面包
1
2
3
4
5
6
7
8
9
if (noBread)
{
    if (noNote)
    {
        Leave Note;
        Buy Bread;
        Remove Note;
    }
}

方案三

方案描述

  • 在方案二的基础上，修改贴标签、检查面包和标签两者的顺序
  • 修改为先贴标签，后检查面包和其他人留下的标签

缺点

  • 如果在贴标签之后、检查面包和标签前，有其他人也贴了标签
    • 可能没有人买面包
1
2
3
4
5
6
7
8
9
Leave Note;
if (noBread)
{
    if (noNote)
    {
        Buy Bread;
    }
}
Remove Note;

方案四

方案描述

  • 两个人采取不同的流程
    • 例如A采取方案二，B采取方案三

缺点

  • A和B的代码不同，扩展性差
  • A可能时刻处于忙等状态

方案五

方案描述

  • 利用同步机制：锁（Lock）
  • Lock.Acquire()
    • 在锁被释放前一直等待，直到获得锁
    • 如果两人都在等待同一个锁，并且同时发现锁被释放了，那么只有一个能够获得锁
  • Lock.Release()
    • 解锁并唤醒任何等待中的进程

注意：锁的操作必须是原子操作！

1
2
3
4
5
6
BreadLock.Acquire();
if (noBread)
{
    Buy Bread;
}
BreadLock.Release();

临界区的保障

以下代码都是基于线程Ti实现

基于软件的方法

线程之间可通过共享一些共有变量来同步它们的行为

1
2
3
4
5
6
do{
    enter section       // 进入临界区
    critical section    // 执行临界区
    exit section        // 退出临界区
    remainder section   // 执行剩余区
} while (1);

方案一

利用共享变量turn，turn的值代表允许进入临界区的线程

1
2
3
4
5
6
do{
    while (turn != i);
    critical section
    turn = j;
    remainder section
} while (1);
  • 满足“忙则等待”，但有时候不满足“空闲则入”
    • 例如Ti进入临界区后，被切换而没能执行。
    • Tj需要等待再次调度器切换到Ti，并等待Ti执行完成后才能再继续运行。

方案二

利用共享变量flag[N]，flag[i]=1代表线程Ti可以进入临界区

1
2
3
4
5
6
7
do{
    while (flag[j]==1);
    flag[i]==1;
    critical section
    flag[i]=0;
    remainder section
} while (1);
  • 不满足“忙则等待”

修改如下：

1
2
3
4
5
6
7
do{
    flag[i]==1;
    while (flag[j]==1);
    critical section
    flag[i]=0;
    remainder section
} while (1);
  • 满足“忙则等待”，但是不满足“空闲则入”

Dekker's 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
flag[0]=flag[1]=false; turn=0;
do{
    flag[i]=true;               // 示意自己需要访问临界区
    while (flag[j])             // 检查对方是否需要访问临界区
    {
        if (turn!=i)            // 如果轮到对方访问
        {
            flag[i]=false;      // 示意自己不访问临界区
            while (turn !=i);   // 等待对方访问完成
            flag[i]=true;       // 重新示意自己需要访问临界区
        }
    }
    critical section            // 执行临界区操作
    turn = j;                   // 将下一轮竞争的轮次让给对手
    flag[i]=false;              // 示意自己不访问临界区
    remainder section           // 进入剩余区
} while (1);

Peterson算法

1
2
3
4
5
6
7
8
do{
    flag[i]=true;                 // 示意自己需要访问临界区
    turn=j;                       // 将机会谦让给另一个线程
    while (flag[j] && turn==j);   // 等待另一个线程完成访问
    critical section              // 进入临界区
    flag[i] = false;              // 示意自己不访问临界区
    remainder section             // 进入剩余区
}

分析

  • 复杂
    • 需要算法和两个进程/线程之间的共享数据项来保证锁的原子性
  • 需要“忙等”
    • 浪费CPU时间

禁用中断实现互斥

  • 使用中断
    • 可以实现抢占式的CPU调度
    • 两种类型的事件可以引起切换
      • 内部事件，主动放弃CPU控制权
      • 外部事件，使得CPU重新调度
  • 通过在acquire和release之间禁止上下文切换来提供互斥
  • 禁用中断以屏蔽外部事件
    • 引入不可中断的代码区域
    • 大多数时候用串行思维
    • 延迟处理外部事件

相当于同步机制中的方案一，锁住了整个冰箱

使用锁变量并引入等待队列

设置等待队列以避免忙等，并在yield前启用中断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Acquire(lock)
{
    disable interrupts;
    while (lock.value == BUSY)
    {
        add TCB to wait_queue;
        enable interrupts;
        yield();
        disable interrupts;
    }
    lock.value=BUSY;
    enable interrupts;
}

Release(lock)
{
    disable interrupts;
    remove every thread from wait_queue and wakeup them;
    lock.value=FREE;
    enable interrupts;
}

缺点

  • 禁用中断后，进程无法被停止
    • 整个系统都会为此而停止
    • 可能导致其他进程处于饥饿状态
  • 临界区可能很长
    • 无法确定处理临界区需要的时间
    • 可能导致长时间无法响应中断

原子操作指令和互斥锁

现代CPU都提供一些特殊的原子操作指令

  • 例如TAS指令（Test-and-Set）
    • 从内存单元中读取值
    • 返回内存单元原值
    • 将内存单元值设置为1
  • 利用TAS指令可以实现自旋锁和互斥锁

优点

  • 适用于单处理器或者共享主存的多处理器中任意数量的进程同步
  • 简单且易证明
  • 支持多临界区

缺点

  • 忙等会消耗处理器时间
  • 可能导致饥饿
    • 进程离开临界区时有多个等待进程的情况
  • 死锁
    • 低优先级进程占有临界区
    • 请求访问临界区的高优先级进程获得处理器并等待临界区