操作系统：同步互斥

第9章：同步互斥

背景
现实生活中的同步问题
临界区
方法1：禁用硬件中断
方法2：基于软件的解决方法
方法3：更高级的抽象方法

9.1 背景

同步互斥是操作系统当中协调进程之间动作和相互关系的一种机制。

并发进程的正确性

• 独立进程：
  不和其他进程共享资源或状态
  确定性–输入状态决定结果
  可重现–能够重现起始条件
  调度顺序不重要
• 并发进程：
  在多个进程间共享资源
  不确定性
  不可重现
• 并发进程的正确性：
  执行进程是不确定性和不可重现的
  程序错误可能是间歇性发生的
• 进程并发执行的好处
  进程需要与计算机中的其他进程和设备进行协作
  好处1：共享资源
  好处2：加速
  I/O操作和CPU计算可以重叠（并行）
  程序可划分成多个模块放在多个处理器上并行执行
  好处3：模块化
  将大程序分解成小程序
  使系统易于复用和扩展

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

• 程序可以调用函数fork()来创建一个新的进程
  操作系统需要分配一个新的并且唯一的进程ID
  在内核中，这个系统调用会运行 new_pid = next_pid++
  翻译成机器指令
  两个进程并发执行时的预期结果（假定是 next_pid = 100）
  一个进程得到的ID应该是100
  另一个进程的ID应该是101
  next_pid应该增加到102
• 新进程标识中的可能错误：
  两个不同的新进程分配了一样的new_pid，且next_pid只增加了1

原子操作（Atomic Operation）

defs：原子操作是指一次不存在任何中断或失败的操作
要么操作成功完成
要么操作没有执行
不会出现部分执行的状态
操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作

9.2 现实生活中的同步问题

• 互斥（mutual exclusion）
  一个进程占用资源，其他进程不能使用，必须等待适应资源的进程释放
• 死锁（deadlock）
  多个进程各占用部分资源，形成循环等待
• 饥饿（starvation）
  其他进程可能轮流占用资源，一个进程一直得不到资源

• 进程的交互关系：相互感知程度

  
  

9.3 临界区（critical section）

• 临界区（critical section）
  进程访问临界资源的一段需要互斥执行的代码
• 进入区（entry section）
  检查可否进入临界区的一段代码
  如可进入，设置相应“正在访问临界区”标志
• 退出区（exit section）
  清除“正在访问临界区”状态
• 剩余区（remainder section）
  代码中的其余部分
• 临界区访问规则

1. 空闲则入：
   没有进程在临界区时，任何进程可进入
2. 忙则等待：
   有进程在临界区时，其他进程均不能进入临界区
3. 有限等待：
   等待进入临界区的进程不能无限等待
4. 让权等待（可选）：
   不能进入临界区的进程应释放CPU（如转换到阻塞状态）

临界区的实现方法

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

禁用中断

• 其他进程无法打扰正在运行的进程，当前进程对临界区资源的访问也就不会有问题。但对系统的中断响应会有影响。
• 在硬件还没有支持的时候，尝试用共享变量协调的方式来做，比较复杂
• 借用操作系统的支持，来使应用提供同步的服务。由于引入管理者，进程间不对等协调

9.4 禁用硬件中断

• 没有中断，没有上下文切换，因此没有并发，整个系统由当前进程独占
  硬件将中断处理延迟到中断被启用之后
  现代计算机体系结构都提供指令来实现禁用中断
  进入临界区
  禁止所有中断，并保存标志
  离开临界区
  使能所有中断，并恢复标志
• 缺点
  禁用中断中，进程无法被停止
  如果进程执行出了问题，那整个系统都没有办法回来
  整个系统都会为此停下来
  可能导致其他进程处于饥饿状态
  临界区可能很长
  无法确定响应中断所需的时间（可能存在硬件影响）
  要小心使用

9.5 基于软件的同步方法

在两个进程之间，通过共享变量的访问，来实现线程之间的同步
线程可通过共享一些共有变量之间来同步它们的行为

• 第一次尝试
  共享变量

int turn = 0
turn == i//表示允许进入临界区的线程 
1
2
线程Ti的代码
do {
    while (turn != i);//条件不成立就可以进入临界区
    critical section
    trun = j;
    remainder section
}  while (1);
1
2
3
4
5
6

若turn不是i，则相当于我本身是i。允许另外一个线程进入临界区，i不允许进入临界区，这时它就一直等待，等待另一个线程把它改成i
当turn变成i之后，它能进去执行临界区的代码，执行完毕退出后，在退出区，它把turn改成j，也就是另一个线程的ID
满足“忙则等待”，但是有时不满足“空闲则入”
Ti不在临界区，Tj想要继续运行，但是必须等待Ti进入临界区后

• 第二次尝试
  共享变量

int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示线程Ti是否在临界区
1
2
3
线程Ti的代码
do {
    while (flag[j] == 1);
    flag[i] = 1;
    critical section
    flag[i] = 0;
    remainder section 
} while (1);
1
2
3
4
5
6
7

如果flag[j]不是1，则另一个线程不在临界区，这时把自己的标识改成1，进入临界区，出来了把自己的标识置为0
不满足“忙则等待”

• 第三次尝试
  共享变量

int flag[2];
flag[0] = flag[1] = 0;
flag[i] == 1;//表示线程Ti想要进入临界区
1
2
3

线程Ti的代码

do {
    flag[i] = 1;
    while (flag[j] == 1);
    critical section
    flag[i] = 0;
    remainder section
} whlie (1);
1
2
3
4
5
6
7

满足“忙则等待”，但是不满足“空闲则入”

Peterson算法

满足线程Ti和Tj之间互斥的基于软件的解决方法
共享变量

int turn;
boolean flag[];//表示进程是否准备好进入临界区
1
2
进入区代码
flag[i] = true;
turn = j;
while (flag[j] && turn ==j) //两个条件只要一个不满足就能进去
1
2
3
退出区代码
flag[i] = false;
1
线程Ti的代码
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
        critical section
    flag[i] = false;
        remainder section
} while (1);
1
2
3
4
5
6
7
8

Dekkers算法

线程Ti的代码

flag[0] := false; 
flag[1] := false;
turn := 0;//orl

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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

N线程的软件方法（Eisenberg 和 McGuire）

特点：

• 复杂：
  需要两个进程间的共享数据项
  需要忙等待
  浪费CPU时间

9.6 更高级的抽象方法

• 硬件提供了一些同步原语
  中断禁用，院子操作指令等
• 操作系统提供更高级的编程抽象来简化进程同步
  例如：锁、信号量
  用硬件原语来构建

锁（lock）

锁是一个抽象的数据结构

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

使用锁来控制临界区访问

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

原子操作指令

• 现代CPU体系结构都提供一些特殊的原子操作指令
  测试和置位（Test-and-Set）指令
  从内存单元中读取值
  测试该值是否为1（然后返回真或假）
  内存单元值设置为1
• 交换指令（exchange）
  交换内存中的两个值

使用TS指令实现自旋锁（spinlock）

class Lock {
    int value = 0;//初始化锁里的初值为0
}
Lock :: Acquire() {
    while （test-and-set（value））;//spin
    //构造它的请求操作原语，即用TS指令去把value的值读出来，并且往里写1。
    //如果是1，则这个操作就相当于是个检查，如果是0，则设为1，循环结束。
}
1
2
3
4
5
6
7
8

如果锁被释放，那么TS指令读取0并将值设置1

• 锁被设置为忙并且需要等待完成
  如果锁处于忙状态，那么TS指令读取1并将值设置为1

• 不改变锁的状态并且需要循环

Lock :: Release() {
    value = 0;
}
1
2
3

• 特点：
  线程在等待的时候消耗CPU时间

无忙等待锁

• 忙等待

Lock :: Acquire() {
    while （test-and-set（value））;//spin
}
Lock :: Release() {
    value = 0;
}
1
2
3
4
5
6

• 无忙等待

class Lock {
    int value = 0;
    WaitQueue q;//在锁的数据结构里加上一个等待队列，即等待这个锁的相应的进程所排的队列
}
Lock :: Acquire() {
    while （test-and-set（value））;{
        and this TCB to wait queue q;
        schedule();

    }
}
1
2
3
4
5
6
7
8
9
10
11

若查询一次之后，里面是1，就将当前线程放到等待队列，同时执行调度程序，此时其他程序可以继续执行
一旦切换回来，轮到该线程再运行时，即有释放锁操作，将该线程从等待状态变成就绪状态，此时再去查，若此时它的状态是解锁的状态，则请求完成，进入临界区

Lock :: Release() {
    value = 0;//表示释放锁
    remove one thread t from q;
    wakeup(t);//将线程从等待队列放到就绪队列。等待时，就处于放弃CPU使用权的状态，实现了让权等待
}
1
2
3
4
5

原子操作指令锁的特征

• 优点
  运用于单处理器或者共享主存的多处理器中任意数量的进程同步
  中断禁用只适用于单处理机
  简单并且容易证明
  支持多临界区
• 缺点
  忙等待消耗处理器时间
  可能导致饥饿
  进程离开临界区时有多个等待进程的情况
  并没有做到按先来后到的顺序来使用资源，因为在锁的请求操作当中，放到就绪队列之后会再去检查。若在检查的时候资源出于空闲状态，那就申请到了。回来的时候，实际上各个线程把就绪队列排定的顺序并不见得是申请锁的顺序
  拥有临界区的低优先级进程
  请求访问临界区的高优先级进程获得处理器并等待临界区
  低优先级等待CPU，高优先级等待临界区资源

同步方法总结

• 锁是一种高级的同步抽象方法
  互斥可使用锁来实现
  需要硬件支持
• 常用的三种同步实现方法
  禁用中断（仅限于单处理器）
  软件方法（复杂）
  原子操作指令（单处理器或多处理器均可）