熟悉完操作系统的第八篇章，开始学习第九篇章，关于操作系统的同步&互斥。

0猜你喜欢

操作系统系列文章

操作系统学习笔记 1概述

9同步&互斥

背景介绍
一些概念
临界区
方法1：基于硬件中断
方法2：基于软件的解决方法
方法3：更高级的抽象

9.1背景

到目前为止

多道程序设计：现代操作系统的重要特性
并行很有用（多个并发实体：CPU，I/O，用户）
线程/进程：操作系统抽象出来用于支持多道程序设计
CPU调度：实现多道程序设计的机制
调度算法：不同的策略

9.1.1线程分类

独立的线程

不和其他线程共享资源或状态
确定性，输入状态决定结果
可重性，能够重现起始条件，I/O
调度顺序不重要

合作的线程

在多个线程中共享状态
不确定性
不可重现

不确定性和不可重现意味着bug可能是间歇性发生的

9.1.2合作优点

进程/线程，计算机/设备需要合作

共享资源

一台电脑，多个用户
一个银行存款余额，多台ATM机
嵌入式系统（机器人控制手臂和手的协调）

加速

I/O操作和计算可以重叠
多处理器，将程序分成多个部分并行执行

模块化

将打程序分解成小的程序
使得系统易于拓展

举例说明

操作系统中维护一个变量，这个变量记录了当前进程ID值。通常来说操作系统创建一个新的进程，当前这个变量的值加1操作，并把这个值赋予给新的进程。

1new_pid = next_pid++;

翻译成机器指令(汇编语言)

1LOAD next_pid Reg1（next_pid值赋给寄存器Reg1）
2STORE Reg1 new_pid（将寄存器的值赋给内存中的new_pid）
3INC Reg1(寄存器加1操作)
4STORE Reg1 next_pid（将寄存器的值赋给内存中的next_pid）

假设两个进程并发执行

如果next_pid等于100，那么其中一个进程得到的ID应该是100，另一个进程的id是101，next_pid应该增加到102

可以看到下图9-1所示，当进程1执行两条汇编指令后，发生上下文切换，产生一次调度，现在执行从进程1转到进程2，执行进程2完成后在调度到进程1，继续执行进程1的剩余两条汇编指令。

因为发生上下文切换之后，寄存器1依然保存之前的状态值，使得next_pid无法更新到102。

由于上下文切换可以发生在四条汇编指令任意位置，所以会出现不同的结果，这就造成不确定性。

图9-1 两个进程并发执行图

9.1.3合作期望

无论多个线程的指令序列怎么交替执行，程序都必须正常工作

多线程程序具有不确定性和不可重现的特点

不经过专门设计，调试难度极高
不确定性要求并行程序的正确性

先思考清楚问题，把程序的行为设计清楚

切忌急于着手编写代码，碰到问题再调试

必须要有一些新的机制来保证能够达到最终确定的结果，后面会引入同步互斥机制解决这种不确定性的问题。

9.2一些概念

竞态条件（Race Condition）

系统缺陷：结果依赖于并发执行或者事件的顺序/时间

不确定性
不可重性

如何避免竞态

让指令不被打断

9.2.1原子操作（Atomic Operation）

原子操作是指一次不存在任何中断或者失败的执行

该执行成功结束

或者根本没有执行

并且不应该发现任何部分执行的状态
实际上操作往往不是原子的

有些看上去是原子操作，实际上不是

连x++这样的简单语句，实际上是由3条指令构成的

有时候设置连单条机器指令都不是原子的（Pipeline，super-scalar，out-of-order，page fault）

举例说明

A和B两个线程互相竞争

其中一个尝试使一个共享的计数器加1

另外一个尝试使一个共享的计数器减1

这里会出现三种结果，线程A执行完毕，线程B执行完毕，两者相互竞争都是死循环（取决于CPU的调度）。

1//这个指令虽然只有一个语句，不是原子操作，转化汇编是好几条指令
2i = i + 1;

9.2.2名词解释

临界区（Critical section）

临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域。

互斥（Mutual exclusion）

当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源

死锁（Dead lock）

两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去

饥饿（Starvation）

一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不执行

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

更好地帮助理解现实生活的问题
但是，计算机比人更蠢

例如，一个寝室一个冰箱，两个室友共享一个冰箱。冰箱里面放有面包，如果没有面包就会有人去买面包。但是会出现A室友买面包的过程中，B室友也会去买面包，最终发现两个人都会去买面包。

两个室友好比两个线程，这个逻辑过程中就会出现面包买到两次操作的现象，这个并不是我们想要的。

什么是面包太多的问题的正确性质

最多有一个人去买面包

如果需要，有人会去买面包

例如，在冰箱上设置一个锁和要是
去买面包之前锁住冰箱并拿走钥匙
修复了太多的问题，钥匙有人想要果汁怎么办
可以改变锁的含义
锁包含等待

锁

在门、抽屉等物体上加上保护性装置，使得外人无法访问物体内的东西，只能等待解锁后才能访问

解锁

打开保护性装置，使得可以访问之前被锁保护的物体类的东西

死锁

A拿到锁1，B拿到锁2，A想继续拿到锁2后在继续执行，B想继续拿到锁1之后再继续执行，导致A和B谁也无法继续执行。

9.2.3方式1使用便签

使用便签来避免购买太多面包

购买之前留下一张标签（一种锁）
买完后移除标签（一种解锁）
如果存在便签就不需要购买面包（在便签被移除以前一直等待）

1//程序样例
2if(nobread){
3    if(noNote){
4        leave Note;
5        buy bread;
6        remove Note;
7    }
8}

如果两个进程一起执行，会出现问题，因为会存在线程的上下文切换的操作。如下图9-2所示，如果A线程执行到2的时候，发生上下文切换，这个时候线程B也会执行到4，这样就会出现重复买面包的操作。

图9-2 上下文切换的两个线程图

结果

偶尔情况下还是会购买太多面包
线程可以得到检查面包和便签之后，购买面包之前切换的上下文

该解决方案由于会间歇性地失败，使得问题更糟了

使问题更加难以调试
必须做调度器所做的事情

9.2.4把便签放放在第一位

如果把便签放在第一位，会造成线程A和线程B都不会去买面包。

因为在一个线程中，已经贴标签里后面看到自己贴的标签也还是不会去买面包。

9.2.5为便签增加标签

可以在检查之前留下便签

如下图9-3所示，这个时候线执行线程A会贴一个1的便签，然后发生上下文切换，这个时候执行B线程页会贴一个2的便签，这使得A和B线程都不会购买面包。

图9-3 为便签增加标签的算法图

可能导致没有现成去买面包

错误时间的上下文切换可能会导致每个线程都认为另一个线程会去买面包

最难处理的

极其不可能发生的事情也会发生在糟糕的时间
就像UNIX中的一些事情

这种锁定状态叫做饥饿

9.2.6更加复杂的两种便签方案

现在有效吗

当然有效，或者能够去买面包，或者有别人去买了，可以离开了

结论

它有效，但是真的不够好
太复杂了，即使对这个简单的例子而言

难以说服你自己它真的有效
A和B的代码不同

每个线程的代码会略不同，如果线程过多怎么办
当A等待的时候，其实在消耗CPU的时间

这种情况叫做忙等待

9.2.7临界区

假设我们有一些锁的实现

Lock Acquire

在锁释放前一直等待，然后获得锁
Lock Release

解锁并唤醒任何等待中的进程
这些一定是原子操作

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

1breadlock.Acquire();//进入临界区
2if (nobread)
3{
4    buy bread;
5}
6breadlock.Release();//退出临界区

9.3临界区

互斥

同一时间临界区中最多存在一个线程
Progress

如果一个线程想要进入临界区，那么它最终会成功
有限等待

如果一个线程i处于入口区，那么i的请求被接受前，其他进程进入临界区的时间是有限制的
无忙等待（可选）

如果一个进程在等待进入临界区，那么在他可以进入之前会被挂起

进入和离开临界区的代码

1ENTER_CRITICAL_SECTION
2EXIT_CRITICAL_SECTION

基本的机制

基于硬件中断
基于软件的解决方法
更高级的抽象

比较不同的机制

性能：并发级别

9.4方法1：基于硬件中断

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

硬件将中断处理延时到中断被启用之后
大多数现代计算机体系结构都提供指令完成

进入临界区

禁用中断

离开临界区

开始中断

缺点

一旦中断被禁用，线程就无法被停止

整个系统都会为你停下来

可能导致其他线程处于饥饿状态
要是临界区可以任意长怎么办

无法限制响应中断所需的时间（可能存在硬件影响）
要小心使用

多CPU只能屏蔽单个CPU，其他CPU是无法屏蔽的

9.5方法2：基于软件的解决方法

这种软件方式除了应用在操作系统，还被用在了分布式系统中，依靠软件能够完成有效的互斥。

9.5.1举例1

 1//Thread i
 2//turn的取值只能为0,1，线程0的初始化为0，线程1初始化为1
 3//turn为共享变量
 4int turn = 0;
 5//如果是线程0，i=0，j=1，反之线程1，i=1，j=0
 6do {
 7    while(turn != i);
 8    critical section
 9    turn = j;
10    reminder section
11}while(1);

结论

能够满足互斥，但是有时不满足progress

9.5.2举例2

改变共享变量，改成flag值，flag[0]=1代表0线程想进入临界区，初始化flag[0]和flag[1]都为0。

结论

这种情况是不存在互斥的，由于上下文切换有可能两个线程会同时进入临界区

9.5.3举例3

改变共享变量的顺序

结论

虽然能够满足互斥，但是存在死锁

9.5.4正确的方法

9.5.4.1`Peteron`算法

定义了三个共享变量

1int turn;//指示该谁进入临界区
2boolean flag[2];//指示进程是否准备好进入临界区

完整代码如下所示

1//线程Pi算法
2do{
3    flag[i] = true;
4    turn = j;
5    while(flag[j] && turn == j)
6        CRITICAL SECTION
7        flag[i] = false;
8        REMINDER SECTION
9}while(1);

结论

能够满足互斥，有限等待，前进三个条件。

9.5.4.2`Dekker`算法

定义了三个共享变量，比上述的Peteron算法要复杂些

 1//线程Pi的算法
 2do{
 3    flag[i] = true;
 4    while(flag[j] == true)
 5    {
 6        if(turn != i)
 7        {
 8            flag[i] = false;
 9            while(turn != i){}
10            flag[i] = true;
11        }
12    }
13    CRITCAL SECTION
14    turn = j;
15    flag[i] = false;
16    REMINDER SECTION
17}while(1);

9.5.4.3Eisnberg and McGuire’s Algorithm

针对于多个线程处理

9.5.4.4`Bakery`算法

N个进程的临界区
进入临界区之前，进程接收一个数字
得到的数字最小的进入临界区
如果进程Pi和Pj收到相同的数字，那么如果i<j，Pi先进入临界区，Pj后进入临界区
编号方案总是按照枚举的增加顺序生成数字

9.5.5总结

Dekker算法：第一个针对双线程例子的正确解决方案
Bakery算法：针对n线程的临界区问题解决方案
复杂

需要两个进程间的共享数据项
需要忙等待

浪费CPU时间
没有硬件保证的情况下无真正的软件解决方案

Peterson算法需要原子的LOAD和STORE指令

9.6方法3：更高级的抽象

9.6.1更高级的抽象介绍

硬件提供了一些原语

像中断禁用，原子操作指令等
大多数现代体系结构都这样

操作系统提供更高级的编程抽象来简化并行编程

例如：锁，信号量
从硬件原语中构建

锁是一个抽象的数据结构

一个二进制状态（锁定/解锁），两种方法
Lock::Acquire()，锁被释放前一直等待，然后得到锁
Lock::Release()，释放锁，唤醒任何等待的进程

使用锁来编写临界区

前面的例子变得简单起来

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

大多数现代体系结构都提供特殊的原子操作指令

通过特殊的内存访问电路
针对但处理器和多处理器

Test-and-Set测试和置位

从内存中读取值

测试该值是否为1（然后返回真或者假）

内存值设置为1
交换

交换内存中的两个值

下面的语句是不能被中途打断的，要不全部执行，不要不执行

 1bool TestAndSet(bool *target){
 2    boolean rv = *target;
 3    *target = true;
 4    return rv;
 5}
 6
 7void Exchange(bool *a, bool *b){
 8    bool temp = *a;
 9    *a = *b;
10    *b = temp;
11}

9.6.2Test-and-Set测试和置位

当一个进程进入临界区，执行Lock::Acquire，内部的value则为1，如果这时候又有另外一个进程出现，那么再次进入临界区，执行执行Lock::Acquire，只能自旋等待。这种方式，即便是多个进程的操作也不会受到影响。

使用忙等待的锁

就像上面使用test-and-set实现的锁一样
线程在等待的时候消耗CPU周期

下图9-4所示，虽然被挂起，但是依然在内存里面，已经放入到等待队列中，等待唤醒。

 1//无忙等待
 2class Lock{
 3    int value = 0;
 4    WaitQueue q;
 5};
 6
 7Lock::Acquire(){
 8    while(test-and-set(value)){
 9        add this TCB to wait queue q;
10        schedule();
11    }
12}
13
14Lock::Release(){
15    value = 0;
16    remove one thread t frome q;
17    wakeup(t);
18}

图9-4 test-and-set实现的锁图

9.6.3交换

共享数据(初始化为0)

当一个线程A执行时，key=1，lock=0，然后交换一次之后。lock=1，key=0，打破循环进入临界区。如果其他线程B执行时，由于key=lock=1，无限交换轮询，直到线程A退出临界区的时候，线程B才可以进入临界区，保证了互斥。

 1//线程Ti
 2int lock = 0;
 3int key;
 4do {
 5    key = 1;
 6    while(key == 1) exchange(lock, key);
 7        critical section
 8    lock = 0;
 9        reminder section
10}while(1);

9.6.4总结

锁是更高级的编程抽象

互斥可以使用锁来实现
通常需要一定等级的硬件支持

常用的三种实现方法

禁用中断（仅限但处理器）
软件方法（复杂）
原子操作指令（多处理器或单处理器均可）

可选的实现内容

有忙等待
无忙等待

	更高级的抽象（锁）
优点	适用于单处理器或者共享主存的多处理器中任意数量的进程简单并且容易证明可以用于支持多临界区
缺点	忙等待消耗处理器时间当进程离开临界区并且多个进程在等待的时候可能导致饥饿死锁。如果有一个低优先级的进程拥有临界区并且一个高优先级的进程也需求，那么高优先级进程会获得处理器并且等待临界区

操作系统学习笔记 9同步&互斥

600 Words|Read in about 3 Min|本文总阅读量次

0猜你喜欢

9同步&互斥

9.1背景

9.1.1线程分类

9.1.2合作优点

9.1.3合作期望

9.2一些概念

9.2.1原子操作（Atomic Operation）

9.2.2名词解释

9.2.3方式1使用便签

9.2.4把便签放放在第一位

9.2.5为便签增加标签

9.2.6更加复杂的两种便签方案

9.2.7临界区

9.3临界区

9.4方法1：基于硬件中断

9.5方法2：基于软件的解决方法

9.5.1举例1

9.5.2举例2

9.5.3举例3

9.5.4正确的方法

9.5.4.1`Peteron`算法

9.5.4.2`Dekker`算法

9.5.4.3Eisnberg and McGuire’s Algorithm

9.5.4.4`Bakery`算法

9.5.5总结

9.6方法3：更高级的抽象

9.6.1更高级的抽象介绍

9.6.2Test-and-Set测试和置位

9.6.3交换

9.6.4总结

Yang Ju

操作系统学习笔记 9同步&互斥

600 Words|Read in about 3 Min|本文总阅读量次

0猜你喜欢

9同步&互斥

9.1背景

9.1.1线程分类

9.1.2合作优点

9.1.3合作期望

9.2一些概念

9.2.1原子操作（Atomic Operation）

9.2.2名词解释

9.2.3方式1使用便签

9.2.4把便签放放在第一位

9.2.5为便签增加标签

9.2.6更加复杂的两种便签方案

9.2.7临界区

9.3临界区

9.4方法1：基于硬件中断

9.5方法2：基于软件的解决方法

9.5.1举例1

9.5.2举例2

9.5.3举例3

9.5.4正确的方法

9.5.4.1Peteron算法

9.5.4.2Dekker算法

9.5.4.3Eisnberg and McGuire’s Algorithm

9.5.4.4Bakery算法

9.5.5总结

9.6方法3：更高级的抽象

9.6.1更高级的抽象介绍

9.6.2Test-and-Set测试和置位

9.6.3交换

9.6.4总结

Yang Ju

9.5.4.1`Peteron`算法

9.5.4.2`Dekker`算法

9.5.4.4`Bakery`算法