互斥与同步

在单处理器多道程序设计系统中，进程会被交替地执行，因而在宏观上表现出一种并发执行的外部特征。
而多处理器系统中，不仅可以从单个核心的角度看是交替执行进程，还可以在多个核心的角度上看多个进程是重叠执行的。

多处理器中进程重叠执行

单处理器条件下，中断可能会在进程中的任何地方停止指令的执行，对于一个共享内存，多个进程间紧密的交互访问，会导致读写混乱。

在多处理器条件下，还有可能多个进程同时试图访问同一个全局变量，也会引发问题。

竞争条件是并发的产生的问题

竞争条件发生在多个进程读写数据时，最终结果取决于多个进程的执行执行的顺序。

并发导致共享变量读写混乱

竞争进程面临互斥的问题

多个进程需要访问一个不可共享的资源，称之为临界资源（Critical Resource），
使用临界资源的那部分程序称为程序的临界区（Critical Section）。一次只允许有一个程序在临界区中。

互斥会导致死锁

两个进程都在等待对方进程已经获得的临界资源，在获得其他资源前，谁都不会释放自己已拥有的资源，此时这两个进程就会发生死锁。

互斥会导致饥饿

多个进程轮流访问互斥资源，导致其他进程无限被拒绝资源访问。

支持互斥必须临界区只有一个进程在执行

要提供对互斥的支持，必须满足以下要求：

满足这些互斥条件的方法有多种：

通过软件方法支持互斥

通过机器指令支持互斥

单处理器用中断禁用的方式保证互斥

单处理器机器中，并发只能交替。一个进程在调用一个系统服务或被中断前，将一直运行。因此，为保证互斥，只需保证一个进程不被中断即可。

while (true) {
    // 禁用中断
    /*
     * 临界区
     */
    // 启用中断
}

这种方式代价高，且不适用于多处理器体系结构中。

专用机器指令

通过操作系统或程序语言支持互斥

信号量

多个进程通过简单的信号进行合作，强迫进程在某个位置停止，知道接收到一个特性的信号。进程通过原语 semSignal(s) 发生信号，
通过原语 semWait(s) 接收信号。

计数信号量

struct semaphore {
    int count;
    queueType queue;
}

void semWait(semaphore s) {
    s.count --;
    if (s.count < 0) {
        // 把当前进程插入队列
        // 阻塞当前进程
    }
}

void segSinal(semaphore s) {
    s.count++;
    if (s.count <= 0) {
        // 把进程P从队列中移除
        // 把进程P插入就绪队列
    }
}

其中，semWait 和 semSinal 原语被假设是原子操作。

二元信号量

二元信号量的值，只能是 00 和 11 。

struct binary_semaphore {
    enum(zero, one} value;
    queueType queue;
}

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

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

其中，semWaitB 和 semSinalB 原语被假设是原子操作。

例：

进程A、B、C、依赖进程D的结果。

信号量机制示例

通过信号量解决互斥问题

进程访问受信号量保护的共享数据

管程

使用信号量设计一个正确的程序是很困难的。在于 semWait 和 semSignal 操作可能分布在整个程序中，很难看出信号量上的这些操作所产生的整体效果。

管程是一种程序设计语言结构，提供的功能与信号量相同，更易于控制。
用管程可以锁定任何对象，对于类似链表之类的对象，可以用一个锁锁住整个链表，也可以每个表用一个锁，还可以为表中的每个元素用一个锁。

一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

原理：

管程提供一种互斥机制：

因此，可以把一个临界资源放在管程中，进程通过管程间接访问该资源，从而实现了进程互斥。

Hoare模型：

进程在管程中被阻塞后必须马上释放管程，否则其他进程无法进入。因此引入条件变量，每个条件变量保存了一个链表用于记录因该条件变量被阻塞的进程。
并提供两个操作：

Hoare模型要求条件队列至少有一个进程每当另一个进程为该条件产生 csinal 时，立即运行队列中的一个进程。因此，产生 csignal 的进程必须立即退出管程或阻塞在管程上。

缺点：

  1. 若产生 csignal 的进程在管程内还未结束，则需要两次额外的进程切换。
  2. 调度程序必须确保在激活相应条件队列中的进程前，没有其他进程进入管程，否则进程被激活的条件可能会改变。

MESA模型：

改进Hoare模型中的 csignal 方法为 cnotify：

死锁与饥饿
树