操作系统9—-并发与同步

                                                 并发与同步

1.并发

2.临界区

2.1临界区(Critical Section)

2.2临界区访问规则

3.临界区实现方法

3.1.禁用中断

3.2.软件方法

3.2.1Peterson算法

3.2.2Dekkers算法

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

3.3.高级抽象

3.3.1锁(lock)

3.3.2原子操作指令

1.并发

独立进程 

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

并发进程

在多个进程间有资源共享；不确定性；不可重现

并发进程的正确性

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

并发进程引起的错误

利用fork系统调用创建新进程，需要生成一个唯一的PID

翻译成机器指令

假定初始时刻next_pid=100，则进程1 PID=101  进程2 PID=102

进程A执行过程中，发生上下文切换，导致两个进程PID均为100，而next_pid=101发生错误。

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

互斥 ( mutual exclusion )  一个进程占用资源，其它进程不能使用

死锁（deadlock）多个进程各占用部分资源，形成循环等待

饥饿（starvation） 其他进程可能轮流占用资源，一个进程一直得不到资源

2.临界区

2.1临界区(Critical Section)

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

进入区(entry section)  检查可否进入临界区的一段代码，如可进入，设置相应“正在访问临界区“标志

退出区(exit section)  清除“正在访问临界区”标志

剩余区(remainder section)  代码中的其余部分

2.2临界区访问规则

忙则等待：已有进程处于其临界区；

空闲则入：其他进程均不处于临界区；

有限等待：等待进入临界区的进程不能“死等“；

让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

?互斥:假定进程Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外.

?有空让进:临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间.

?有限等待:在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的

?让权等待(可选)：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

3.临界区实现方法

3.1.禁用中断

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

硬件将中断处理延迟到中断被启用之后，现代计算机体系结构都提供指令来实现禁用中断

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

缺点：

禁用中断后，进程无法被停止，整个系统都会为此停下来，可能导致其他进程处于饥饿状态；

临界区可能很长，无法确定响应中断所需的时间（可能存在硬件影响）；

3.2.软件方法

3.2.1Peterson算法

满足线程Ti和Tj之间互斥的经典的基于软件的解决方法（1981年）

线程Ti代码

turn表示该谁进入临界区，flag表示进程是否准备好进入临界区

假定初始时，进程i想进入临界区，此时flag[i]=true,turn=j,flag[j]=false,故while循环条件不满足，i可以进入临界区；

此时如果j也想进入临界区，flag[j]=true,flag[i]=true,turn=i,此时while循环条件while(flag[i]&&turn==i)满足，则j应该等待；

当i离开临界区时，flag[i]=false，此时对于j线程while(flag[i]&&turn==i)不满足，则j可以进入临界区；

如果i,j同时想进入临界区，则flag[i]=true, flag[j]=true，此时对于turn赋值两次，假定线程i后赋值，即turn=j，此时线程i应该等待，线程j可以进入。

3.2.2Dekkers算法

线程Ti 的代码

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

缺点：复杂；需要忙等待

3.3.高级抽象

硬件提供了一些同步原语，中断禁用，原子操作指令等；

操作系统提供更高级的编程抽象来简化进程同步，例如：锁、信 量，用硬件原语来构建；

3.3.1锁(lock)

锁是一个抽象的数据结构，一个二进制变量（锁定/解锁）

Lock::Acquire() 锁被释放前一直等待，然后得到锁

Lock::Release() 释放锁，唤醒任何等待的进程

使用锁来控制临界区访问

3.3.2原子操作指令

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

测试和置位（Test-and-Set ）指令

从内存单元中读取值，测试该值是否为1（然后返回真或假），内存单元值设置为1

交换指令（exchange）交换内存中的两个值

使用TS指令实现自旋锁(spinlock)

test-and-set指令，读取变量值，并且设置为1

value初始=0，如果当前锁释放状态，value=0，acquire方法获取锁，则while循环不满足，并且获取锁之后value=1;

value=1,此时如果再想获取锁，则ts指令返回为1，while循环需要一直等待，直到所被释放value=0，才能够获取锁；

如果两个线程想同时获取锁，由于ts指令原子性，因此必定只有一个线程能够将value置位1，获取锁。

无忙等待锁

增加等待队列，如果当前进程获取锁处于等待状态，则可以加入到等待队列，调度其他进程进行执行。

原子操作指令锁的特征

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

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

参考：清华大学 操作系统  陈渝  http://os.cs.tsinghua.edu.cn/oscourse/OS2015/