操作系统之并发与同步

并发的概念

在单处理器多道程序设计系统中，进程会被交替地执行，因而表现出一种并发执行的外部特征。支持并发进程的基本需求是加强互斥的能力。也就是说，当一个进程被授予互斥能力时，那么在其活动期间，它具有排斥所有其他进程的能力。

并发包括很多设计问题，其中有进程间通信、资源共享与竞争（如内存、文件、I/O访问)、多个进程活动的同步以及给进程分配处理器时间等。并发问题源于多道程序设计系统的一个基本特性：进程的相对执行速度不可预测，它取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。

术语	解释
临界区	一段代码，在这段代码中进程将访问共享资源，当另外一个进程已在这段代码中运行时，这个进程就不能在这段代码中执行
死锁	两个或两个以上的进程因每个进程都在等待其他进程做完某些事情而不能继续执行的情形
互斥	当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源的情形
竞争条件	多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间的情形
饥饿	一个可运行进程尽管能继续执行，但被调度程序无限期地忽视，而不能被调度执行的情形
原子操作	保证指令序列要么作为一个组来执行，要么都不执行

如果需要保护共享的全局变量（以及其他共享的全局资源），唯一的办法是控制访问该变量的代码。

原子性和顺序性

原子性确保指令执行期间不被打断，要么全部执行完，要么根本不执行。另一方面，顺序性确保即使两条或多条指令出现在独立的执行线程中，甚至独立的处理器上，它们本该的执行顺序却依然要保持。顺序性通过屏障（barrier）指令来实施。

进程交互的分类

• 进程之间互相不知道对方的存在，它们表现出竞争关系
• 进程间接知道对方的存在，但它们共享某些对象，表现出通过共享合作的关系
• 进程直接知道对方的存在，可以通过进程ID互相传递消息进行通信，表现出通过通信合作的关系

竞争进程面临三个控制问题：

1. 互斥

   假设两个或更多的进程需要访问一个不可共享的资源，如打印机。在执行过程中，每个进程都给该IO设备发命令，接收状态信息，发送数据和接收数据。我们把这类资源称为临界资源，使用临界资源的那部分程序称为程序的临界区。一次只允许有一个程序在临界区中，这一点非常重要。

为了实现互斥则产生了下面两个问题：

2. 死锁

   考虑两个进程P1和P2，以及两个资源R1和R2，假设每个进程为执行部分功能都需要访问这两个资源，那么就有可能出现下列情况：操作系统把R1分配给P2，把R2分配给P1，每个进程都在等待另一个资源，且在获得其他资源并完成功能前，谁都不会释放自己已拥有的资源，此时这两个进程就会发生死锁。

3. 饥饿

   假设有三个进程（P1、P2和P3），每个进程都周期性地访问资源R。假设操作系统把访问权轮流授予P1和P3，那么即使没有死锁，P2也可能被无限地拒绝访间资源。

合作进程和竞争进程的唯一区别是可以按两种不同的模式（读和写）访问数据项，并且只有写操作必须保证互斥。除了面临上面三个问题外，还有一个新的要求：数据一致性。

若使用临界区来保护数据的一致性，则没有确定的资源或变量可作为参数。此时，可以把参数视为一个在并发进程间共享的标识符，用于标识必须互斥的临界区。

互斥的要求以及实现

1. 必须强制实施互斥：在与相同资源或共享对象的临界区有关的所有进程中，一次只允许一个进程进入临界区。
2. 没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。
3. 一个进程驻留在临界区中的时间必须是有限的。

硬件支持的实现

1. 禁用中断

   为保证互斥，只需保证一个进程不被中断即可，这种能力可通过系统内核为启用和禁用中断定义的原语来提供。但代价非常高。

2. 专用机器指令

   在硬件级别上，对存储单元的访问排斥对相同单元的其他访问。因此，处理器的设计者人员提出了一些机器指令，用于保证两个动作的原子性。

软件支持的实现

并发机制	解释
信号量	用于进程间传递信号的一个整数值。在信号量上只可进行三种操作，即初始化、递减和递增，它们都是原子操作。递减操作用于阻塞一个进程，递增操作用于解除一个进程的阻塞
二元信号量	只取0值和1值的信号量
互斥量	类似于二元信号量。关键区别在于为其加锁（设定值为0）的进程和为其解锁（设定值为1）的进程必须为同一个进程，一般被用在构造临界区上
条件变量	一种数据类型，用于阻塞进程或线程，直到特定的条件为真
自旋锁	一种互斥机制，进程在一个无条件循环中执行，等待锁变量的值可用

信号量

Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个不可用（已经被占用）的信号量时，信号量会将其推进一个等待队列，然后让其睡眠。这时处理器能重获自由，从而去执行其他代码。当持有的信号量可用（被释放）后，处于等待队列中的那个任务将被唤醒。

我们可以从信号量的睡眠特性得出一些有意思的结论：

• 由于争用信号量的进程在等待锁重新变为可用时会睡眠，所以信号量适用于锁会被长时间持有的情况。
• 相反，锁被短时间持有时，使用信号量就不太适宜了。因为睡眠、维护等待队列以及唤醒所花费的开销可能比锁被占用的全部时间还要长。
• 面于执行线程在锁被争用时会睡眠，所以只能在进程上下文中才能获取信号量锁，因为在中断上下文中是不能进行调度的。
• 你可以在持有信号量时去睡眠，因为当其他进程试图获得同一信号量时不会因此而死锁（因为该进程也只是去睡眠而已，而你最终会继续执行的）。

为达到预期效果，可把信号量视为一个值为整数的变量，整数值上定义了三个操作：

1. 一个信号量可以初始化成非负数。
2. semWait操作使信号量减1。若值变成负数，则阻塞执行semWait的进程，否则进程继续执行。
3. semSignal操作使信号量加1。被semWait操作阻塞的进程之一（可能没有被阻塞的）解除阻塞。

// 使用 比较和交换指令 实现的信号量原语
struct semaphore
{
    int count;
    bool flag;
    queueType queue;
};

void semwait(semaphore s)
{
    while(compare_and_swap(s.flag, 0, 1) == 1);
    s.count--;
    if(s.count < 0)
    {
        /* 把当前进程插入队列 */;
        /* 阻塞当前进程 */;
    }
    s.flag = 0;
}

void semSignal(semaphore s)
{
    while(compare_and_swap(s.flag, 0, 1) == 1);
    s.count++;
    if(s.count <= O)
    {
        /* 把进程 P 从队列中移除 */;
        /* 把进程卫插入就绪队列 */;
    }
    s.flag = 0;
}

• s.count ≥ 0：s.count是可执行semwait(s)而不被阻塞的进程数。这种情形允许信号量支持同步与互斥。
• s.count < 0：s.count的大小是阻塞在s.queue队列中的进程数。

二元信号量

1. 二元信号量可以初始化为0或1。
2. semWaitB操作检查信号的值。若值为0，则进程执行semwaitB就会受阻。若值为1，则将值改为0，并继续执行该进程。
3. semSignalB操作检查是否有任何进程在该信号上受阻。若有进程受阻，则通过semWaitB操作受阻的进程会被唤醒：若没有进程受阻，则值设置为1。

struct binary_semaphore
{
    enum {zero, one} value;
    qrueueType queue;
};

void semwaitB(binary semaphore s)
{
    if(s.value = one)
        s.value = zero;
    else
    {
        /* 把当前进程插入队列 */;
        /* 阻塞当前进程 */;
    }
}

void semSignalB(semaphore s)
{
    if(s.queue is empty())
        s.value =one;
    else
    {
        /* 把进程 P 从等待队列中移除 */;
        /* 把进程卫插入就绪队列 */;
    }
}

不论是计数信号量还是二元信号量，都需要使用队列来保存于信号量上等待的进程。这就产生了一个问题，进程按什么顺序从队列中移出？最公平的策略是先进先出，被阻塞时间最久的进程最先从队列释放。采用这一策略定义的信号量称为强信号量，而没有规定进程从队列中移出顺序的信号量称为弱信号量。

强信号量保证不会饥饿，而弱信号量则无法保证。

自旋锁

自旋锁最多只能被一个可执行线程持有。如果一个执行线程试图获得一个被已经持有（即所谓的争用）的自旋锁，那么该线程就会一直进行忙循环一旋转，等待锁重新可用。要是锁未被争用，请求锁的执行线程便能立刻得到它，继续执行。在任意时间，自旋锁都可以防止多于一个的执行线程同时进入临界区。

自旋锁是不可递归的（不可重入的）。

自旋锁可以使用在中断处理程序中（此处不能使用信号量，因为它们会导致睡眠）。在中断处理程序中使用自旋锁时，一定要在获取锁之前，首先禁止本地中断（在当前处理器上的中断请求），否则，中断处理程序就会打断正持有锁的内核代码，有可能会试图去争用这个已经被持有的自旋锁。这样一来，中断处理程序就会自旋，等待该锁重新可用，但是锁的持有者在这个中断处理程序执行完毕前不可能运行。这正是我们在前面的内容中提到的双重请求死锁。注意，需要关闭的只是当前处理器上的中断。如果中断发生在不同的处理器上，即使中断处理程序在同一锁上自旋，也不会妨碍锁的持有者（在不同处理器上）最终释放锁。

互斥量mutex

• 任何时刻中只有一个任务可以持有mutex，也就是说，mutex的使用计数永远是1。
• 给mutex上锁者必须负责给其再解锁——你不能在一个上下文中锁定一个mutex，而在另一个上下文中给它解锁。这个限制使得mutex不适合内核同用户空间复杂的同步场景。最常使用的方式是：在同一上下文中上锁和解锁。
• 递归地上锁和解锁是不允许的。也就是说，你不能递归地持有同一个锁，同样你也不能再去解锁一个已经被解开的mutex。
• 当持有一个mutex时，进程不可以退出。
• mutex只能通过官方API管理，不可被拷贝、赋值、重复初始化。

除非mutex的某个约束妨碍你使用，否则相比信号量要优先使用mutex。在中断上下文中只能使用自旋锁，而在任务睡眠时只能使用mutex。

死锁原理

死锁定义为一组相互竞争系统资源或进行通信的进程间的“永久”阻塞。当一组进程中的每个进程都在等待某个事件（典型情况下是等待释放所请求的资源），而仅有这组进程中被阻塞的其他进程才可触发该事件时，就称这组进程发生了死锁。

资源通常分为两类：可重用资源和可消耗资源。可重用资源是指一次仅供一个进程安全使用且不因使用而耗尽的资源。可重用资源的例子包括处理器、I/O通道、内存和外存、设备，以及诸如文件、数据库和信号量之类的数据结构。可消耗资源是指可被创建（生产）和销毁（消耗）的资源。存在。可消耗资源的例子有中断、信号、消息和I/O缓冲区中的信息。

产生死锁有三个必要条件：

1. 互斥。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。
2. 占有且等待。当一个进程等待其他进程时，继续占有已分配的资源。
3. 不可抢占。不能强行抢占进程已占有的资源。

要产生死锁，还需要第四个条件：

4. 循环等待。存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

第四个条件实际上是前三个条件的潜在结果，即假设前三个条件存在，那么可能发生的系列事件会导致不可解的循环等待。这个不可解的循环等待实际上就是死锁的定义。循环等待之所以不可解，是因为有前面三个条件的存在。因此，这四个条件一起构成 了死锁的充分必要条件。

死锁预防

死锁预防方法分为两类。一类是间接死锁预防方法，即防止前面列出的三个必要条件中的任何一个条件的发生；另一类是直接死锁预防方法，即防止循环等待的发生。

1. 互斥

   不可能禁止。如果需要对资源进行互斥访问，那么操作系统就必须支持互斥。

2. 占有且等待

   为预防占有且等待的条件，可以要求进程一次性地请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足。

3. 不可抢占

   预防不可抢占的方法有几种。首先，占有某些资源的一个进程进一步申请资源时若被拒绝，则该进程必须释放其最初占有的资源，必要时可再次申请这些资源和其他资源。其次，一个进程请求当前被另一个进程占有的一个资源时，操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不同的条件下，后一种方案才能预防死锁。

   此外，只有在资源状态可以很容易地保存和恢复的情况下（如CPU上下文），这种方法才是实用的。

4. 循环等待

   循环等待条件可通过定义资源类型的线性顺序来预防。若一个进程已分配了R类型的资源，则其接下来请求的资源只能是那些排在R类型之后的资源。

死锁避免

在死锁避免中，是否允许当前的资源分配请求是通过判断该请求是否可能导致死锁来决定的。因此，死锁避免需要知道未来进程资源请求的情况。

1. 进程启动拒绝。若一个进程的请求会导致死锁，则不启动该进程。
2. 资源分配拒绝，又称银行家算法。若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。

死锁避免的优点是，无须死锁预防中的抢占和回滚进程，

死锁检测

对于死锁检测来说，只要有可能，就会给进程分配其所请求的资源。操作系统周期性地执行一个算法来检测前面的循环等待条件。算法的策略是查找一个进程，使得可用资源能满足该进程的资源请求，然后假设同意这些资源，让该进程运行直到结束，再释放它的所有资源。然后，算法再寻找另一个可以满足资源请求的进程。

死锁恢复：

1. 取消所有的死锁进程。这是操作系统中最常采用的方法。
2. 连续取消死锁进程直到不再存在死锁。所选取消进程的顺序应基于某种最小代价原则。每次取消后，必须重新调用检测算法，以测试是否仍存在死锁。
3. 连续抢占资源直到不再存在死锁。

对于内存资源来说，基于抢占的死锁预防是最适合的策略。