操作系统——进程同步与互斥

进程同步与互斥

简介

多线程并发会导致资源竞争。

同步即协调多线程对共享数据的访问，保证任何时刻都只能有一个线程执行临界区代码。

互斥是解决进程同步的方式。

进程间合作

独立进程是指一个进程在运行过程中不会与其他进程进行交互的进程。

但是，进程在运行的过程中不可避免的要进行进程间合作。

进程合作的优势：

• 共享资源
  • 一台电脑，多个用户
  • 一个银行存储余额，多台ATM机
  • 嵌入式系统（机器人控制：手臂和手的协调）
• 加速
  • I / O操作和计算可重叠
  • 多处理机——将程序分成多个部分执行
• 模块快
  • 将大程序分解成小程序
    • 如编译系统。
  • 视系统易于扩展

进程间合作的问题

进程间合作要避免不确定性和不可重现性。由于进程调度的不确定性，因此进程的一个操作可能被打断。

进程间通信要解决三个问题：

1. 一个进程如何将信息传递给另一个进程
2. 确保多个进程在关键活动中不会交叉，即进程互斥问题。
3. 保证正确的访问顺序，即进程同步问题。

竞争条件

竞争条件是说多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序。

案例：

• 通过调用函数fork来创建一个进程。
  • new_pid = next_pid++；
  • 这一条语句翻译成汇编代码会是四句，因此要把他们当成一个原子操作去执行。
• 两个程序并发执行访问并更改一个变量x。

原子操作

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

• 该执行成功结束
• 或者根本没有执行
• 并且不应该出现任何部分执行的状态

但是实际上操作往往不是原子的

• 有些看上去是原子操作，但是实际上不是，如x++，实际上此条语句由三条汇编语言组成。
• 有时甚至连单条机器指令都不是原子的，如Pipiline、super-scalar、out-of-order、page fault等。

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

临界区相关的几个概念

临界区是指多个程序访问临界资源的一段代码。也可以说是进程访问临界资源的一段需要互斥的代码。

1. 在进入临界区前检查是否可进入临界区。
2. 若可以进入，则设置相应标志表示正在访问临界区。
3. 在访问完成之后将标志恢复为可访问临界区。
4. 然后去执行非临界区代码。

要避免竞争条件，即要找出某个途径来阻止多个进程同时读写共享数据，提出一种解决方案为互斥，即以某种手段保证当一个程序在使用一个共享爱那个文件或变量时，其他进程不能做同样的操作。

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

死锁是指多个进程相互等待完成特定任务二最终无法将自身任务进行下去。

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

避免竞争条件即使临界区中只能有一个进程。

一个好的解决竞争条件的方案需要满足下列四个条件：

1. 任何两个进程不能同时处于临界区
2. 不应对CPU的速度和数量做任何假设
3. 临界区外执行的进程不得阻塞其他进程
4. 不得使进程无限期等待进入临界区
5. 不能进入临界区的进程应该释放CPU资源（可选）。

忙等待的互斥

连续测试一个变量直到某个值出现为止称为忙等待，用于忙等待的锁称为自旋锁。

下列几种方式都可以保证任意两个进程不同时处于临界区。

基于硬件的同步解决办法：屏蔽中断

单处理器系统中，最简单的方法是使每个进程刚进入临界区后就立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也会被屏蔽，而CPU只有发生时钟中断或其他中断时才会进行进程切换，因此在屏蔽中断之后就不会被切换到其他进程。

但是这种方式有一个问题：若此进程不打开中断的话其他进程就都无法执行。

而且若是处于多处理器系统中，其他的CPU也可以将进程调度，从而还是无法避免多个进程同时访问临界区的问题。

因此，屏蔽中断对用户进程不是一种合适的通用互斥机制。

总结如下：

• 硬件将中断处理延迟到中断被启用之后
• 现代计算机体系结构都提供指令来实现禁用中断
  • 首先保存当前CPU状态
  • 然后禁用中断，访问临界区
  • 最后恢复CPU状态

缺点：

• 禁用中断之后，进程无法被停止。
  • 整个系统都会为之停下来
  • 可能导致其他进程处于饥饿状态
• 临界区可能很长
  • 无法确定响应中断所需的时间

基于软件的同步解决方法

通过共享一些共有变量来同步进程的行为。

严格轮换法

turn用来表示哪一个进程进入临界区，假设只有两个进程，进程0执行a代码，进程1执行b代码，此时考虑两种情况：

1. 一个进程连续两次进入临界区，第一次进入临界区时发现turn是0，因此进入，在执行完临界区代码之后将turn的值设置为1，那么他在下次进入临界区之前发现turn不是0，因此一直循环等待，但此时临界区中是没有进程在执行的。
2. 进程0先被调度执行，此时turn的值为0，因此进程0进入临界区执行代码，在它执行完临界区代码退出后，将turn的值更改为1，此时进程1被调度进入CPU执行，发现此时turn的值为1，因此执行临界区的代码，当临界区代码执行完毕之后将要更改turn的值时，CPU调度进程0进入CPU执行，但是此时turn的值还是为1，因此进程0不能执行临界区代码，但是此时临界区却没有进程在执行，因为违反了上面的第三条规则：为处于临界区的进程不得阻塞其他进程。

由此可见，此种方式也不合适。

Peterson解法

此算法可以解决两个进程的同步问题。

N线程的软件方法

进程Pi要等待从turn到i-1的进程都退出临界区后访问临界区。

进程Pi退出时将turn给下一个想要进入的进程Pj。

基于软件解决办法的分析

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

更高级的抽象方法

简介

硬件提供了一些同步原语

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

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

• 如：锁、信号量
• 用硬件原语来创建。

原子操作指令

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

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

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

交换（exchange）指令：

• 交换内存中的两个值。

锁变量

锁是一个抽象的数据结构

• 一个二进制变量（锁定/解锁）
• Lock::Acquire()
• Lock::Release()

使用锁来控制临界区的访问：当进程进入临界区之前先判断锁变量的值，若有锁的话就等待，否则进入临界区并且更改锁变量的值，然后再退出临界区时将锁变量的值再次修改。

但是这又回到了最开始的问题：读锁变量和修改锁变量时两个操作，在第一个进程读取锁变量时发现可以进入，然后CPU调度第二个进程进入CPU进行执行，此时第一个进程还未将锁变量进行修改，因此第二个进程也发现可以进入，因此更改了锁变量进入临界区，此时又被切换至第一个进程，第一个进程认为此时临界区中没有进程，因此也进入了临界区，所以还是不能解决竞争条件的问题。

使用TS指令实现自旋锁

//忙等待，此种方式为自旋锁方式
class Lock {
	int value = 0;
}
Lock::Acquire() { //若锁被释放，则TS指令读取0并将值设置为1，否则，TS指令读取1并将值设置为1
	while(test-and-set(value))
		;
}
Lock::Release() {
	value = 0;
}

//无忙等待，此种方式为等待队列方式，即阻塞式方法。
class Lock {
    int value = 0;
    WaitQueue q;
}
Lock::Acquire() {
    while(test-and-set(value)) {
        //将当前进程加入等待队列
        add this PCB to wait queue q
        //执行调度
        schedule();
    }
}
Lock::Release() {
    value = 0;
    //从等待队列中移除一个进程p，并唤醒他去执行。
    remove one process p from q;
    wakeup(p);
}

基于原子操作指令锁的特征

优点：

• 适用于单处理器或者共享主存的多处理器中任意数量的进程同步机制。
• 简单并且容易验证
• 支持多临界区

缺点：

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

参考资料

清华大学—操作系统原理
现代操作系统