一、生产者-消费者问题
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用;
生产者、消费者共享一个初始为空、大小为n的缓冲区;
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待;
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待;
1、分析关系
生产者和消费者的工作需要同步,即生产完成之后才能消费。
2、设置信号量
semaphore mutex = 1; //互斥信号量,实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量,表示空闲缓冲区的数量
semaphore full = 0; //同步信号量,表示产品(非空缓冲区)的数量
3、实际代码
producer(){
while(1){
生产产品
P(empty); //申请新的缓冲区
P(mutex); //申请访问临界资源
存入缓冲区
V(mutex); //释放临界资源
V(full); //释放一个消费品(非空缓冲区)
}
}
consumer(){
while(1){
P(full); //申请使用消费品
P(mutex); //申请访问临界资源
从缓冲区取出
V(mutex); //释放临界资源
V(empty); //释放一个空缓冲区
消费产品
}
}
实现互斥的P操作一定要在实现同步的P操作之后
两个V操作可以交换顺序
二、多生产者-多消费者问题
有父亲、母亲、儿子、女儿四人,其中:
1、分析关系
2、设置信号量
semaphore mutex = 1; //互斥信号量,实现盘子的互斥访问
semaphore plate = 1; //同步信号量,代表盘子的剩余空位
semaphore apple = 0; //同步信号量,代表苹果数量
semaphore orange = 0; //同步信号量,代表橘子数量
3、实际代码
dad(){
while(1){
准备苹果
P(plate); //申请盘子资源
P(mutex);
将苹果放入盘子
V(mutex);
V(apple); //释放一个苹果
}
}
mom(){
while(1){
准备橘子
P(plate); //申请盘子资源
P(mutex);
将橘子放入盘子
V(mutex);
V(orange); //释放一个橘子
}
}
daughter(){
while(1){
P(apple); //申请苹果资源
P(mutex);
拿出苹果
V(mutex);
V(plate); //释放盘子资源
恰苹果
}
}
son(){
while(1){
P(orange); //申请橘子资源
P(mutex);
拿出橘子
V(mutex);
V(plate); //释放盘子资源
恰橘子
}
}
由于本问题缓冲区为1,可以考虑不设置信号量。
三、吸烟者问题
系统中有一个供应者和三个吸烟者,吸烟者吸烟需要自己卷烟,其中
供应者每次会提供其中两种材料,并由缺少该材料的吸烟者拿取
吸烟者制作完烟并抽掉后,发出信号,供应者放下一组物品
1、分析关系
可以将桌子视为容量为1的缓冲区,并且将两种材料分别视为三种组合:
2、信号量设置
semaphore offer1 = 0; //同步信号量,桌上组合一的数量
semaphore offer1 = 0; //同步信号量,桌上组合二的数量
semaphore offer1 = 0; //同步信号量,桌上组合三的数量
semaphore finish = 0; //同步信号量,抽烟是否完成
int i = 0; //实现轮流提供材料
3、实际代码
provider(){
while(1){
if (i==0){
将组合一放在桌上
V(offer1); //提供材料
}else if (i==1){
将组合二放在桌上
V(offer2);
}else if (i ==2){
将组合三放在桌上
V(offer3);
}
i = (i+1) % 3; //轮流提供素材
P(finish); //等待完成信号
}
}
smoker1(){
while(1){
P(offer1); //请求组合一资源
从桌上拿走组合一
卷烟,抽烟
V(finish); //发出完成信号
}
}
smoker2(){
while(1){
P(offer2);
从桌上拿走组合二
卷烟,抽烟
V(finish);
}
}
smoker3(){
while(1){
P(offer3);
从桌上拿走组合三
卷烟,抽烟
V(finish);
}
}
四、读者-写者问题
有读者和写者两组并发进程,共享一个文件。要求:
任一写着完成写操作之前不允许其他进程进行读或写操作;
1、关系分析
2、信号量设置
semaphore rw = 1; //互斥信号量,实现读、写对文件的互斥访问
int count = 0; //同时在读文件的读进程数量
semaphore mutex = 1; //互斥信号量,实现读进程对count的互斥访问
然而,以上信号量设置有可能导致饿死,具体如下代码一所示,因此,增加一个信号量
semaphore w = 1; //同步信号量,用于实现“写优先”
3、实际代码
writer(){
while(1){
P(rw);
写文件
V(rw);
}
}
reader(){
while(1){
P(mutex);
if (count == 0){
P(rw); //由第一个读进程负责上锁
}
V(mutex);
读文件
P(mutex);
count--;
if (count == 0){
V(rw); //由最后一个读进程负责解锁
}
V(mutex);
}
}
以上代码存在饿死现象,即一直有读进程占用,写进程始终无法运行
因此,引入了“写优先”的信号量:
writer(){
while(1){
P(w);
P(rw);
写文件
V(rw);
V(w);
}
}
reader(){
while(1){
P(w); //对每一个读和写进程之间做互斥处理
P(mutex);
if (count == 0){
P(rw); //由第一个读进程负责上锁
}
V(mutex);
V(w);
读文件
P(mutex);
count--;
if (count == 0){
V(rw); //由最后一个读进程负责解锁
}
V(mutex);
}
}
当然,这种实际上是各个读、写进程之间公平运行,并不是准确的写优先。
五、哲学家进餐问题
在一个桌子上,有5位哲学家,其中
哲学家平时在思考人生,饿了就会尝试拿起左右手的筷子(一根一根的拿)
1、关系分析
设计有三种思路来防止死锁:
只允许奇数号的哲学家拿起左边的筷子;偶数号的哲学家拿起右边的筷子
2、信号量设置
semaphore chopstick[5] = {1, 1, 1, 1, 1}; //代表五根筷子的资源
semaphore mutex = 1; //对左右筷子整体资源互斥访问
3、实际代码
Pi(){
while (1){
P(mutex);
P(chopstick[i]); //拿左
P(chopstick[ (i+1) % 5]); //拿右
V(mutex);
吃饭
V(chopstick[i]);
V(chopstick[ (i+1) % 5]);
思考
}
}
实现了只有当左右手筷子都可用时才拿起筷子