1、背景

对于独立的进程/线程来说，其不和其他进程/线程共享资源或者状态，执行具有确定性和可重复性 ，其调度顺序是不重要的；对于合作进程/线程来说，他们的状态和资源在其他多个进程/线程中进行共享，其执行具有不确定性和不可重现性，这就导致了bug可能是间歇性发生的且很难找到。

进程/线程之间的合作是必须的，通过合作具有共享资源，加速程序运行，和将程序进行模块化 的优点。无论多个线程的指令序列怎样交替执行，程序都必须正常工作，因为多线程程序具有不确定性和不可重现的特点，不经过专门设计，调试的难度很高。所以不确定性要求并行程序的正确性，在写程序之前要考虑清除问题，将程序的行为设计清楚。

2、基本概念

原子操作(Atomic operation) ：指一次不存在任何中断或者失败的执行，该执行成功结束或者根本没有执行，不会有部分执行的状态；实际上操作往往不是原子的，有些看上去的原子操作其实不是，如x++，甚至连单条机器指令都不是原子的，如pipeline，super-scalar，out-of-order，page fault。

临界区(Critical section) ：临界区指进程中的一段需要访问共享资源的代码区域，并且当另一个进程处于临界区时，其他进程便不会执行这段代码。

互斥(Mutual exclusion) ：当一个进程处于临界区访问共享资源时，其他进程不会处于临界区并访问任何相同的共享资源。

死锁(Dead lock) ：两个或以上的进程，在相互等待完成特定任务，而都最终没法将自身的任务进行下去。

d 饥饿(Starvation) ：一个可执行进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行。

d 锁(Lock) ：在门、抽屉等物体上加上保护性装置，使得外人无法访问物体内的东西，只能等待解锁后才能访问。

解锁(Unlock) ：打开保护性装置，使得可以访问之前被锁保护的物体类的东西。

死锁(Deadlock) ：A拿到锁1，B拿到锁2，A向继续拿到锁2之后在继续执行，B想拿到锁1之后再继续执行。导致A和B谁也无法继续执行。

3、临界区

临界区的属性有以下几个：互斥： 表示同一时间临界区最多存在一个线程；前进(Progress)： 如果一个线程想要进入临界区，那么他最终会成功；有限等待： 如果一个线程i处于入口区，那么在i的请求被接受之前，其他线程进入临界区的时间是有限制的；无忙等待： 是一个可选项，如果一个进程在等待进入临界区，那么在他可以进入之前会被挂起。实现临界区机制的方法有以下三种：禁用硬件中断；基于软件的解决方法；基于硬件原子操作的高层抽象。

3.1 禁用硬件中断

在进入临界区时禁用中断，在离开临界区之后开启中断。但这种方法需要小心使用，因为一旦中断被禁用，线程就无法被停止，整个系统都会为其停下来，还可能导致其他线程处于饥饿状态；另外要是临界区可以任意长会导致无法限制响应中断所需的时间。这种方法对于临界区很小的情况是有效的。中断机制对于多CPU执行的情况是无法解决互斥问题的。

3.2 基于软件的解决方法

使用两个共享数据项来实现软件解决方法。

int turn;   //指示该谁进入临界区
boolean flag[]; //指示进程是否准备好进入临界区
Code for ENTER_CRITICAL_SECTION
  flag[i]=TRUE;
  turn = j;
  while(flag[j] && turn == j);
Code for EXIT_CRITICAL_SECTION
  flag[i] = FALSE;

上述Peterson Algorithm是对于两个进程的临界区的实现，对于n个进程的实现算法有Eisenberg and McGuire’s Algorithm 和 Bakery Algorithm。

3.3 基于硬件原子操作的高层抽象实现

操作系统提供了更加高级的编程抽象来简化并行程序，例如锁、信号量等。

锁是一个抽象的数据结构，其内部是一种二进制的状态(锁定/解锁)，包含两种方法：Lock::Acquire() -锁在被释放前会一直等待，然后得到锁；Lock::Release() -释放锁，唤醒任何等待的进程。

优点：适用于单处理器或者共享内存处理器中任意数量的进程；简单并且容易证明；可以用于支持多临界区。

缺点：忙等待消耗处理器的时间；当进程离开临界区并且多个进程在等待的时候可能导致饥饿；可能产生死锁：如果一个低优先级的进程拥有临界区并且一个高优先级进程也有需求，那么高优先级进程会获得处理器并等待临界区，导致低优先级进程无法释放锁，导致死锁。