十九、信号量和管程

• 1、信号量-semaphore
• • 1.1 抽象数据类型
  • 1.2 信号量的属性
  • 1.3 两种类型的信号量
  • 1.4 使用信号量实现消费者问题
  • 1.5 信号量的底层实现
• 2、管程
• • 2.1 条件变量
  • 2.2 使用管程解决生产消费问题

qquad 一个整型(sem)，两个原子操作；
qquad P()：sem减1，如果 s e m < 0 sem < 0 sem<0，等待，否则继续；
qquad V()：sem加1，如果 s e m ≤ 0 sem≤0 sem≤0，唤醒一个等待的进程

qquad 信号量是整数；
qquad 信号量是被保护的变量，初始化完成之后，唯一改变一个信号量的值的方法是通过P()和V()操作，操作对象必须是原子；
qquad P()能够阻塞，V()不会阻塞；
qquad 我们假定信号量是公平的，在实践中，唤醒等待进程的顺序通常采用FIFO的机制。

qquad 二进制信号量：可以是0或者是1，将semaphore的初始值设置为1，可以模拟lock机制；
qquad 一般/计数信号量：可以取任何非负值，将semaphore的初始值设置为一个正数( n n n)这种情况下可以允许 n n n个进程进入到临界区进行执行，不同于lock机制下只允许一个进程进入临界区进行执行；
qquad 信号量可以用于互斥和条件同步2个方面。

qquad 消费者问题表述为：一个或者多个生产者向buffer中填充数据；单个消费者每次从缓冲区中取出数据；在任意时间内只有一个生产者或者消费者可以访问缓冲区；
qquad 其正确性要求：在一个时间内只能有一个线程操作缓冲区(互斥)；当缓冲区为空时，消费者必须等待生产者向缓冲区填充数据(同步)；当缓冲区填满之后，生产者必须等待消费者从缓冲区取出数据之后才能继续填充数据(同步)。上述正确性要求可以通过三个信号量来处理三个不同的约束：一个二进制信号量处理互斥；一个一般信号量处理第一个同步；一个一般信号量处理第二个同步。
qquad 最终实现逻辑如下图所示：

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

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的顺序
	}

}

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

qquad 条件变量 允许等待状态进入临界区，允许处于等待状态的线程进入临界区，某个时刻院子释放锁进入睡眠。条件变量包含以下两个操作：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
	}

}

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