1.基本概念

1. 互斥
   只有一个线程能访问临界区。

2. 临界资源
   多个线程可以共享系统中的资源，但是临界资源只允许一个线程在某一时刻访问。如某些变量、硬件资源。

3. 临界区
   访问临界资源的代码即临界区。

2.信号量与管程

管程（Monitors）和信号量（Semaphores）是操作系统中用于实现并发编程的两种重要技术。

2.1 信号量

2.1.1 定义

操作系统提供的一种协调共享资源访问的方法，优先级高于进程，可以保证原子性。

信号中包括一个整形变量，和两个原子操作 P 和 V。其原子性由操作系统保证，这个整形变量只能通过 P 操作和 V 操作改变。

• P(Prolaag，荷兰语尝试减少)：信号量值减 1，如果信号量值小于 0，则说明资源不够用的，把进程加入等待队列。

• V (Verhoog，荷兰语增加)：信号量值加 1，如果信号量值小于等于 0，则说明等待队列里有进程，那么唤醒一个等待进程。

共享变量S只能由 PV 操作，PV的原子性由操作系统保证。
P相当获取锁，可能会阻塞线程;V相当于释放锁，不会阻塞线程。
根据同步队列中唤醒线程的先后顺序，可以分为公平和非公平两种。

信号量分类：

• 二进制信号量：资源数目为 0 或 1。
• 资源信号量：资源数目为任何非负值

2.1.2 例子

实现生产者消费者针对同一队列进行通信，任一时刻只有一个线程在操作队列。

假设只有一个生产者，n个消费者，那么需要三个信号量：

notFull： 表示队列不满，可以推送消息
notEmpty： 表示队列不空，可以消费消息
mutex： 表示互斥，限制同时只有一个线程访问

class Queue {

	private Semaphore notFull = new Semaphore(1);

	private Semaphore notEmpty = new Semaphore(n);

	private Semaphore mutex = new Semaphore(1);

	publib void produce() {
		notFull.P();  //队列不满才能推送，否则等待
		mutex.P();
		//生产消息加入队列
		mutex.V();
		notEmpty.V(); //唤醒等待消费线程
	}

	publib void consume() {
		notEmpty.P();  //队列不空才能消费，否则等待
		mutex.P();
		//生产消息加入队列
		mutex.V();
		notFull.V(); //唤醒等待生产者线程
	}

}

2.2 管程

2.2.1 定义

管程是为了解决信号量在临界区的PV操作上的配对的麻烦而提出的并发编程方法，使用条件变量等同步机制来实现线程之间的协作。

条件变量:
线程中的一种同步机制，它允许线程等待某个条件成立，与信号量不同。
当条件不满足时，线程将自己加入等待队列，同时释放持有的互斥锁；
当一个线程唤醒一个或多个等待线程时，此时条件不一定为真（虚假唤醒）。

先后出现过三种不同的管程模型，分别是：Hasen 模型、Hoare 模型和 MESA 模型，当前广泛使用的是MESA模型。

MESA模型图示：

2.2.2 MESA模型编程范式

while (条件不满足) {
  wait();
}

MESA模型使用while判断的原因是，wait()是进入了条件变量的等待队列。若被notify()或者notifyAll()唤醒，也只是从条件变量等待队列到了入口等待队列。入口等待队列才是竞争锁的地方，等到此线程实际执行的时候，条件可能又不满足了，需要再次wait()。

2.3.3 例子

实现一个自定的阻塞队列，通过Lock类保证互斥条件，notFull和notEmpty分别表示队列非满及非空的条件变量。

public class BlockedQueue<T>{
  final Lock lock = new ReentrantLock();
  // 条件变量：队列不满
  final Condition notFull = lock.newCondition();
  // 条件变量：队列不空
  final Condition notEmpty = lock.newCondition();

  // 入队
  void enq(T x) {
    lock.lock();
    try {
      while (队列已满){
        // 等待队列不满
        notFull.await();
      }
      // 省略入队操作...
      //入队后,通知可出队
      notEmpty.signal();
    }finally {
      lock.unlock();
    }
  }
  // 出队
  void deq(){
    lock.lock();
    try {
      while (队列已空){
        // 等待队列不空
        notEmpty.await();
      }
      // 省略出队操作...
      //出队后，通知可入队
      notFull.signal();
    }finally {
      lock.unlock();
    }
  }
}

2.3.4 唤醒对比

无论何种情况，尽量使用notifyAll()及signalAll(), 可以避免意想不到的bug。