同步互斥

请设置文章作者
Computer Science

发布于：2019年5月1日
次浏览

1. 背景

独立进程：不和其他进程共享资源和状态

确定性：输入状态决定结果
可重现：能够重现起始条件

并发进程：在多个进程间有资源共享

不确定性
不可重现

并发进程的正确性

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

进程并发的好处

  1. 共享资源
  2. 加速 （I/O操作和CPU计算同时进行）
  3. 模块化（将大程序分解成小程序，如编译，gcc调用cpp，cc1，cc2，as，ld）

1.1 并发创建新进程时的标识分配

调用函数fork()来创建一个新的进程（操作系统需要分配一个新的并且唯一的进程ID）

在内核中，这个系统调用会运行：

1
new_pid = next_pid++

两个进程并发执行时的预期结果：

  1. 一个进程ID为100
  2. 另一个进程ID为101
  3. next_pid应该增加到102

1

next_pid也只+1

1.2原子操作

指一次不存在任何中断或失败的操作

  1. 要么操作成功完成
  2. 要么操作没有执行

不存在部分执行的状态

操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作

2. 现实生活中的同步问题

操作系统和现实生活的问题类比

2.1 家庭采购问题的分析

  1. 有人去买面包
  2. 最多只有一个人买

可能的解决办法：

  1. 在冰箱上设置一个钥匙
  2. 去买面包之前锁住冰箱并且拿走钥匙������

加锁导致的问题：别人无法取食物

方案一：

使用便签来避免

1
2
3
4
5
6
7
if(noBread) {
  if(noNote) {
    leave Note;
    buy bread;
    removen Note;
  }
}

分析：

检查面包和便签中间，有其他人检查面包和便签

2

结果：买多了，买了2份gg

解决方案会有间歇性的失败

方案二：

先留便签，后检查面包和便签

1
2
3
4
5
6
7
leave Note;
if(noBread) {
  if(noNote) {
    buy bread;
  }
}
remove bread;

3

结果：谁也不会去买面包

方案三：

为便签增加标记，以区别不同人的便签

4

这么做可以行通吗？

5

结果：最后还没检查面包就退出了，还是谁都没买

方案四：

6

结果：A等待B离开后，去买面包啦！～

枚举完所有可能后，可以确认方案四是有效的

分析：

  1. 它有效，但太复杂
  2. A和B代码不一样
  3. 当A在等待时，它不能做其他事（busy-waiting）

方案五：

利用两个原子操作实现一个锁（lock）

Lock.Acquire():

  1. 在锁被释放前一直等待，然后获得锁
  2. 如果两个线程都在等待同一个锁，并且同时发现锁被释放了，那么只有一个能够获得锁

Lock.Release():

  1. 解锁并唤醒任何等待中的进程
1
2
3
4
5
breadlock.Acquire(); // 进入临界区
if(noBread) {
  buy bread;
}
breadlock.Release(); // 退出临界区

2.2 进程的交互关系

相互感知程度

7

三种关系：

  1. 互斥（mutual exclusion）- 一个进程占用了资源，其他进程不能使用
  2. 死锁（deadlock）- 多个进程占用部分资源，形成循环等待
  3. 饥饿（starvation）- 其他进程可能轮流占用资源，一个进程一直得不到资源

3. 临界区 Critical Section

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

1
2
3
4
entry section
  critical section
exit section
  remainder section

还有 进入区 & 退出区 & 剩余区

访问规则：

  1. 空闲则入
  2. 忙则等待
  3. 有限等待：等待区的进程不能无限期地等待下去
  4. 让权等待（可选）

实现方法：

  1. 禁用中断
  2. 软件方法
  3. 更高级的抽象方法

4. 禁用硬件中断同步方法

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

  1. 硬件将中断处理延迟到中断被启用之后
  2. 现代计算机体系结构都提供指令来实现禁用中断
1
2
3
4
// 临界区域访问代码
local_irq_save(unsigned long flags);
critical section
local_irq_restore(unsigned long flags);

进入临界区：禁止所有中断，并保存标志
离开临界区：使能所有中断，并恢复标志

缺点：

  1. 禁用中断后，进程无法被停止
  2. 可能导致其他进程处于饥饿
  3. 临界区可能很长（无法确定响应中断的时间）

5. 基于软件的同步方法

两个线程，T0和T1

线程Ti的代码：

1
2
3
4
5
6
do {
  enter section // 进入区
    critica sectio
  exit section //退出区
    remainder section
}while(1);

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

第一次尝试：

共享变量：

1
2
int turn = 0;
turn = i; // 表示允许进入临界区的线程ID

线程Ti的代码：

1
2
3
4
5
6
do {
    while(turn != i) ; // 不是i的话进入不了临界区
    critical section
    turn = j;
    remainder section
}while(1);

结果：满足“忙则等待”，但是有时不满足“空闲则入”

第二次尝试：

8

结果：不能满足“忙则等待”

第三次尝试：

9

结果：满足“忙则等待”，但是有时不满足“空闲则入”

5.1 Peterson算法

10

算法实现：

线程Ti的代码：

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
}while(true);

可以完成两个进程的同步

5.2 Dekkers算法

线程Ti的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    remainder section
}while(true);

这个算法可以扩展到多个线程，不局限2个线程的同步

N线程的软件方法：

11

算法分析：

  1. 复杂
  2. 忙等待（浪费CPU时间）

6. 高级抽象的同步方法

基于硬件提供的同步原语实现的同步方法（如，中断禁用，原子操作指令）

操作系统提供更高级的编程抽象来简化进程同步

例如：锁，信号量

6.1 锁 lock

锁是一个抽象的数据结构(由1个二进制变量和2个操作原语组成)

  1. 一个二进制变量（锁定 / 解锁）
  2. Lock::Acquire()
  3. Lock::Release()

使用锁来控制临界区访问：

1
2
3
lock_next_pid->Acquire();
new_pid = next_pid++;
lock_next_pid->Release();

6.2 原子操作指令

现在CPU体系结构都提供一些特殊的原子指令

  1. 测试和置位指令 Test-and-Set （也叫 TS指令）
    • 从内存单元中读取值
    • 测试该值是否为1（然后返回真 or 假）
    • 内存单元值设置为1
1
2
3
4
5
6
boolean TestAndSet (boolean *target)
{
    boolean rv = *target;
    *taregt = ture;
    return cv;
}

  1. 交换指令

    • 交换内存里的2个值
1
2
3
4
5
6
void Exchange(boolean *a, boolean *b)
{
    boolean temp = *a;
    *a = *b;
    *b = temp;
}
使用TS指令来实现自旋锁 Spinlock
1
2
3
4
5
6
7
8
9
10
11
class Lock {
    int value = 0; // 锁的初值为0
}

Lock::Acquire() {
    while(test-and-set(value))
        ; // spin
}
Lock::Release() {
    value = 0;
}

12

特点：线程在等待状态时是占用CPU的

So？What I can do？优化一下！

无忙等待锁

13

我们实现了让权等待

原子操作指令锁的特征：

  • 优点

    1. 适用于单处理机或者共享内存的多处理器中任意数量的进程同步
    2. 简单并容易证明
    3. 支持多临界区

  • 缺点

    1. 忙等待
    2. 可能导致饥饿（进程离开临界区时有多个等待进程的情况）
    3. 死锁（低优先级进程占用临界区资源等待CPU，高优先级进程获得处理器等待临界区）

总结：

14

原子指令的方法是适用性最好的。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.fuujiro.com/2019/05/01/%E5%90%8C%E6%AD%A5%E4%BA%92%E6%96%A5/

更新于：2020年9月13日

Operating System

ucore

评论