同步互斥

理论

互斥、死锁、饥饿

互斥是指某一资源同时只允许一个进程对其进行访问,具有唯一性和排它性,但互斥不用限制进程对资源的访问顺序,即访问可以是无序的。

同步是指在进程间的执行必须严格按照规定的某种先后次序来运行,即访问是有序的,这种先后次序取决于要系统完成的任务需求。

17 临界区

空闲则入、忙则等待、有限等待、让权等待(可选)

实现的三种办法:禁用中断、软件方法、更高级的抽象方法

方法比较主要考虑性能:并发级别

禁用中断

1
2
3
local_irq_save(unsigned long flags);
// critical section
local_irq_restore(unsigned long flags);

进入临界区:禁用所有中断,并保存标志

离开临界区:使能所有中断、并恢复标志

缺点

  • 禁用中断后,进程无法被停止:使整个系统都停下来;可能导致其他进程饥饿
  • 临界区可能很长:无法确定响应中断所需的时间
  • 不得不使用时,才采用

基于软件的同步解决方法

Peterson算法(双进程)

Dekkers算法(多进程)

方法分析:复杂,需要进程间共享变量;需要忙等待,浪费CPU时间。

更高级的抽象算法

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

Test-and-Set

相当于以下过程

1
2
3
4
5
6
boolean TestAndSet (boolean *target)‏
{
boolean rv = *target;
*target = true;
return rv:
}

exchange

1
2
3
4
5
6
void Exchange (boolean *a, boolean *b)‏
{
boolean temp = *a;
*a = *b;
*b = temp:
}

图左:spinlock(自旋锁无法实现先进先出)

原子操作指令锁特征

优点

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

缺点

  • 可能的忙等待,消耗处理器时间

  • 可能导致饥饿

    进程离开临界区时,唤醒的次序

  • 死锁

    拥有临界区的低优先级进程

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

18 同步互斥

信号量(semaphore)

特性

  • 信号量是被保护的整数变量
    • 初始化完成后,只能通过P()和V()操作修改
    • 由操作系统保证,PV是原子操作
  • P()可能阻塞,V()不会阻塞

两种信号量:二进制信号量、资源信号量。(二者等价,基于一个可以实现另一个)

使用:互斥访问、条件同步

生产者消费者问题

问题描述:一个或者多个生产者在生成数据后放在一个缓冲区里;单个消费者从缓冲区取出数据区里;任何时候只能有一个生产者或者消费者进入临界区。

问题分析

  • 任何一个时刻只能有一个线程操作缓冲区(互斥访问)
  • 缓冲区空时,消费者必须等待生产者(条件同步)
  • 缓冲区满时,生产者必须等待消费者(条件同步)

信号量描述约束

  • 二进制信号量mutex
  • 资源信号量fullBuffers
  • 资源信号量emptyBuffers

信号量的困难

读/开发代码困难、容易出错(使用的信号量被占用,忘记释放信号量)、不能够处理死锁

管程

管程是一种用于多线程互斥访问共享资源的程序结构

  • 采用面向对象方法,简化了线程间的同步控制
  • 任一时刻最多只有一个线程执行管程代码
  • 正在管程中的线程可临时放弃管程的互斥访问,等待事件出现时恢复

管程的使用

  • 在对象/模块中,收集相关共享数据
  • 定义访问共享数据的方法

条件变量(Condition Variable)

  • 条件变量是管程内的等待机制
    • 进入管程的线程因资源被占用而进入等待状态
    • 每个条件变量表示一种等待原因,对应一个等待队列
  • Wait()操作
    • 将自己阻塞在等待队列中
    • 唤醒一个等待者或释放管程的互斥访问
  • Signal()操作
    • 将等待队列中的一个线程唤醒
    • 如果等待队列为空,则等同空操作

管程分类

Hoare管程存在两个缺陷:

  1. 若产生signal的进程在管程内还未结束,则需要两次额外的切换:阻塞这个进程需要一次切换;管程可用时恢复有需要一次切换
  2. 与信号相关的进程调度必须非常可靠。产生一个signal必须立即激活相关条件队列中的一个进程,调度程序必须保证在激活前没有其他进程进入管程,否则进程被激活的条件就发生改变。

Hansen管程

Hansen管程signal被notify所取代,可解释为:当一个正在管程中的进程执行notify(x)时,会使得x条件队列得到通知,但发信号的进程继续执行。通知的结果是未来会调度到该队列中的某个进程进行执行。但是,不能保证在他之前没有其他进程进入管程,因而被调度的这个等待进程必须重新检查条件。

这其中的区别就在于ifwhile的使用。这个方案对条件变量多了至少一次的检查,得到的回报是:不再有额外的进程切换,对等待进程之后什么时候运行没有任何限制。

因为if没有再次的检查机制,必须立即切换到等待的进程中,以防其他的进程进入管程破坏条件,所以是Hoare管程。

读者写者问题

问题描述

  • 共享数据的两类使用者

    读者:只读取数据,不修改

    写者:读取和修改数据

  • 分析

    “读-读”允许,“读-写”互斥,“写-写”互斥