9同步互斥

17.1背景

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

并发进程的正确性

■独立进程

不和其他进程共享资源或状态

确定性－＞输入状态决定结果

可重现－＞能够重现起始条件（多次实现结果是一样的）

调度顺序不重要

■并发进程

在多个进程间有资源共享

不确定性

不可重现

■并发进程的正确性

执行过程是不确定性和不可重现的

程序错误可能是间歇性发生的

进程并发执行的好处

进程需要与计算机中的其他进程和设备进行协作

■好处1：共享资源

多个用户使用同一台计算机

银行账号存款余额在多台ATM机操作

机器人上的嵌入式系统协调手臂和手的动作

■好处2：加速

I/O操作和CPU计算可以重叠（并行）

程序可划分成多个模块放在多个处理器上并行执行

■好处3：模块化

·将大程序分解成小程序

以编译为例，gcc会调用cpp，cc1，cc2，as，ld

·使系统易于复用和扩展

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

■程序可以调用函数fork()来创建一个新的进程

操作系统需要分配一个新的并且唯一的进程ID

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

翻译成机器指令

■两个进程并发执行时的预期结果(假定next_pid=100)

一个进程得到的ID应该是100

另一个进程的ID应该是101

next_pid应该增加到102

新进程分配标识中的可能错误

原子操作（Atomic Operation）

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

要么操作成功完成

或者操作没有执行

不会出现部分执行的状态

■操作系统需要利用同步机制在并发执行（以便于我能做到资源共享和提高速度）的同时，保证一些操作是原子操作

17.2现实生活中的同步问题

例子：略。

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

■互斥( mutual exclusion )

一个进程占用资源，其它进程不能使用

■死锁（deadlock）

多个进程各占用部分资源，形成循环等待

■饥饿（starvation）

其他进程可能轮流占用资源，一个进程一直得不到资源

17.3临界区

临界区(Critical Section)

■ 临界区(critical section)

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

■ 进入区(entry section)

检查可否进入临界区的一段代码

如可进入，设置相应"正在访问临界区"标志

■ 退出区(exit section)

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

■ 剩余区(remainder section)

代码中的其余部分

临界区的访问规则

■ 空闲则入

没有进程在临界区时，任何进程可进入

■ 忙则等待

有进程在临界区时，其他进程均不能进入临界区

■ 有限等待

等待进入临界区的进程不能无限期等待

■让权等待（可选）

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

临界区的实现方法

禁用中断、软件方法、更高级的抽象方法

■不同的临界区实现机制的比较

性能：并发级别

方法1：禁用硬件中断

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

硬件将中断处理延迟到中断被启用之后

现代计算机体系结构都提供指令来实现禁用中断

■进入临界区

禁止所有中断，并保存标志

■离开临界区

使能所有中断，并恢复标志

精髓：

特点：

适用于在单处理器或共享内存的多处理器上的任何数目的进程。

非常简单且易于证明。

可用于支持多个临界区，每个临界区可以用它自己的变量定义。

缺点

■禁用中断后，进程无法被停止

整个系统都会为此停下来

可能导致其他进程处于饥饿状态

■临界区可能很长

无法确定响应中断所需的时间（可能存在硬件影响）

■要小心使用（在系统中不能不用它的时候才会用）

方法２：基于软件的同步解决方法

两个进程之间通过共享变量的访问来实现线程之间的同步

Peterson算法

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

Dekkers算法

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

有一个共享的turn变量，有若干线程排成一个环，每个环有个flag标志，想要进入临界区就得填写flag标志，有多个想进入临界区的话，就从前往后走，执行完一个线程，turn就改为下一个进程的值。

基于软件的解决方法的分析

■复杂

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

■需要忙等待

浪费CPU时间（必须频繁地来查询共享变量的状态）

方法3：更高级的抽象方法

■硬件提供了一些同步原语（硬件上保证原子性）

中断禁用，原子操作指令等

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

例如：锁、信号量

用硬件原语来构建

锁(lock)

■锁是一个抽象的数据结构

·一个二进制变量（锁定/解锁）

·Lock::Acquire()

锁被释放前一直等待，然后得到锁

·Lock::Release()

释放锁，唤醒任何等待的进程

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

注：锁内部基于原子操作指令

原子操作指令

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

■测试和置位（Test-and-Set）指令（原子操作不会中断）

从内存单元中读取值

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

内存单元值设置为1

■交换指令（exchange）

交换内存中的两个值

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

无忙等待锁

原子操作指令锁的特征

■优点

适用于单处理器或者共享主存的多处理器中任意数量的进程同步

简单并且容易证明

支持多临界区

■缺点

·忙等待消耗处理器时间

·可能导致饥饿

进程离开临界区时有多个等待进程的情况（申请锁的顺序和线程的就绪队列的顺序不一定相同）

·死锁

拥有临界区的低优先级进程（等cpu）

请求访问临界区的高优先级进程获得处理器并等待临界区（等临界区）

同步方法总结

■锁是一种高级的同步抽象方法

互斥可以使用锁来实现

需要硬件支持

■常用的三种同步实现方法

禁用中断（仅限于单处理器，并且会对系统中断的响应时间呢会有影响）。不得已的情况下才使用）

软件方法（复杂）

原子操作指令（单处理器或多处理器均可，容易验证）