操作系统(经典同步问题)

王道上操作系统几大经典同步算法

1. 生产者与消费者问题

分析:整个环境由生产者,消费者,缓冲区(临界区)组成，这种题明白以下几点
１）生产者与消费者对缓冲区的访问是互斥的，即某段时间内只允许二者其中一个对缓冲区进行访问
２）生产者与消费者之间也存在同步关系，即当且只有缓冲区不空时，消费者才允许从缓冲区中取数据，当且只有缓冲区不满时，才允许生产者往缓冲区放数据

//算法伪代码
semaphore mutex = 1;//用于生产者与消费者对缓冲区(临界区)的互斥访问
semaphore empty = n;//初始化缓冲区空的单元数为n，用来阻塞生产者进程
semaphore full = 0;//初始化缓冲区满的单元数为0，用来阻塞消费者进程

//生产者进程
producer(){
	while(true){
		p(empty);//阻塞中，等待消费者进程传递过来的信号量
		p(mutex);//进入临界区
		prepareData();//生产数据
		AddData();//放入缓冲区单元
		v(mutex);//退出临界区
		v(full);//动作完成,发送一个信号量给消费者
		｝
｝

//消费者进程
consumer(){
	while(true){
		p(full);//阻塞中，等待生产者进程传递过来的信号量
		p(mutex);//进入缓冲区
		fetchData();//取走数据
		useData();//使用数据
		v(mutex)//退出临界区
		v(empty);//动作完成，发送一个信号量给生产者
		}
}

2. 吃水果问题

吃水果问题与上述的问题相似，由原来的单线程问题变成了多线程对互斥资源的访问:题目描述如下:桌上有一个盘子，每次只能往盘子里放入一个水果，爸爸专门放苹果，妈妈专门放橘子，儿子专吃盘子里的橘子，女儿专门吃盘子里的苹果，只有盘子为空时，爸爸或者妈妈才可以往盘子里放入一个水果，当且仅有盘子里有自己想要的水果时，儿子或者女儿其一才可以去取
分析:可以看成是两组(生产者－消费者进程)对缓冲区的访问，儿子或者女儿只有在母亲或者父亲往盘子里放了它们想要的资源之后，才可以进入临界区去取

semaphore plate = 1,apple = 0,orange = 0;
dad(){
	while(true){
		prepareApple();
		p(plate);//互斥向盘子里取，放水果
		putAppleTothePlate();//放苹果
		v(apple);//告诉女儿可以取了
	}
}

mom(){
	while(true){
		prepareOrange();
		p(plate);//互斥向盘子里取，放水果
		putOrangeTothePlate();//放橘子
		v(orange);//告诉儿子可以取了
	}
}

son(){
	while(true){
		p(orange);//互斥从盘子里取橘子
		takeOrangeAndeat();
		v(plate);//告诉妈妈橘子吃完了
	}
}

daughter(){
	while(true){
		p(apple);//互斥从盘子里取苹果
		takeAppleAndeat();
		v(plate);//告诉爸爸苹果吃完了
	}
}