1、信号量-semaphore

1.1 抽象数据类型

一个整型(sem)，两个原子操作；

P()：sem减1，如果  sem<0，等待，否则继续；

V()：sem加1，如果  sem≤0，唤醒一个等待的进程

1.2 信号量的属性

信号量是整数；

信号量是被保护的变量，初始化完成之后，唯一改变一个信号量的值的方法是通过P()和V()操作，操作对象必须是原子；

P()能够阻塞，V()不会阻塞；

1.3 两种类型的信号量

二进制信号量：可以是0或者是1，将semaphore的初始值设置为1，可以模拟lock机制；

一般/计数信号量：可以取任何非负值，将semaphore的初始值设置为一个正数( n n n)这种情况下可以允许 n n n个进程进入到临界区进行执行，不同于lock机制下只允许一个进程进入临界区进行执行；

信号量可以用于互斥和条件同步2个方面。

1.4 使用信号量实现消费者问题

消费者问题表述为：一个或者多个生产者向buffer中填充数据；单个消费者每次从缓冲区中取出数据；在任意时间内只有一个生产者或者消费者可以访问缓冲区；

其正确性要求：在一个时间内只能有一个线程操作缓冲区(互斥)；当缓冲区为空时，消费者必须等待生产者向缓冲区填充数据(同步)；当缓冲区填满之后，生产者必须等待消费者从缓冲区取出数据之后才能继续填充数据(同步)。上述正确性要求可以通过三个信号量来处理三个不同的约束：一个二进制信号量处理互斥；一个一般信号量处理第一个同步；一个一般信号量处理第二个同步。

最终实现逻辑如下图所示：

上述逻辑中，V()操作的顺序可以互换，P()操作的顺序不能互换，会导致死锁。

1.5 信号量的底层实现

class Semaphore
{//信号量结构体
  int sem;    //计数变量
  waitQueue q;  //等待队列
}

Semaphore::P()
{//信号量的P操作实现
  --sem;
  if(sem<0)
  {
    Add this thread t to q;
    block(p);//使进程p进行睡眠
  }
}

Semaphore::V()
{//信号量的V操作实现 
  ++sem;
  if(sem<=0)
  {
    Remove a thread t from q;
    wakeup(t);//唤醒进程t，使用FIFO的顺序
  }
}

2、管程

目的： 分离互斥和条件同步的关注；概念： 管程中包含一个锁：用来指定临界区；管程中还包含0或者多个条件变量：用来等待/通知信号量用于管理并发访问的共享数据。根据条件的个数来设定条件变量的数量。线程进入管程时，同一时间只有一个线程能够进入。管程的大致结构如下图所示：

2.1 条件变量

条件变量 允许等待状态进入临界区，允许处于等待状态的线程进入临界区，某个时刻院子释放锁进入睡眠。条件变量包含以下两个操作：wait() 释放锁，睡眠，重新获得锁(返回后)；signal() 唤醒等待者，如果有的话。条件变量的实现如下所示：

Class Condition
{//条件变量的结构体
  int numWaiting = 0;
  WaitQueue q;
}

Condition::Wait(lock)
{//条件变量的wait操作
  ++numWaiting;     //表示挂在当前条件变量上睡眠的线程多了一个
  Add this thread t to q;//把线程加到等待队列里面
  release(lock);      //释放锁
  shedule();//need mutex  //选择下一个线程去执行
  require(lock);      //获得锁
}

Condition::Signal()
{//条件变量的signal操作，其实wait操作的反向操作
  if(numWaiting>0)//判断是否有挂在当前条件变量上的睡眠的线程
  {
    Remove a thread t from q;//将一个睡眠线程从等待队列中取出来，FIFO规则
    wakeup(t);//need mutex   //唤醒当前的线程t
    --numWaiting;      //挂在条件变量上的睡眠的线程数量减1
  }
}

2.2 使用管程解决生产消费问题

使用管程解决生产者消费者问题的过程如下，左边为生产者，右边为消费者。