操作系统—经典同步问题

补充

互斥信号量mutex初值均为1

同步信号量根据问题实际描述自己设计

生产者-消费者问题

问题描述：一组生产者进程和一组消费者进程 共享一个初始为空、大小为n的缓冲区。（缓冲区：临界资源）

1. 只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待
2. 只有缓冲区不空时，消费者才能从中取出消息，否则必须等待

• 信号量mutex：互斥信号量，用于控制互斥访问缓冲池，初值为1
• 信号量full：同步信号量，用于记录当前缓冲池中的“满”缓冲区数，初值为0
• 信号量empty：同步信号量，用于记录当前缓冲池中的“空”缓冲区数，初值为n

注：①实现互斥的P操作一定要在实现同步的P操作之后

②两个V操作顺序可以交换

semaphore mutex=1;    //临界区互斥信号量
semaphore empty=n;    //同步信号量，表示空闲缓冲区数量
semaphore full=0;     //同步信号量，缓冲区初始化为空，表示满缓冲区数量
producer(){   //生产者进程while(1){produce an item in nextp;   //生产数据P(empty);    //获取空缓冲区单元，消耗一个空闲缓冲区P(mutex);    //进入临界区add nextp to buffer;   //将数据放入缓冲区V(mutex);    //离开临界区，释放互斥信号量V(full);     //满缓冲区数+1，即增加一个产品}
}
//V(full)和P(full)：实现两进程的同步关系，是在其中一个进程执行P，另一个进程执行V
consumer(){   //消费者进程while(1){P(full);    //获取满缓冲区单元，消耗一个产品（非空缓冲区）P(mutex);   //进入临界区remove an item from buffer;   //从缓冲区中取出数据V(mutex);   //离开临界区，释放互斥信号量V(empty);   //空缓冲区数+1，即增加一个空闲缓冲区consume the item;   //消费数据}
}

多生产者-多消费者

问题分析：桌上有一个盘子，每次只能向其中放入一个水果。

1. 只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果
2. 仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出

如图，儿子和女儿之间没有互斥和同步关系。

• 信号量plate：互斥信号量，表示是否允许向盘子放入水果，初值为1（表示允许放入，且只允许放入一个）
• 信号量apple：同步信号量，表示盘子中是否有苹果，初值为0（表示盘子为空，不许取，apple=1可取）
• 信号量orange：同步信号量，表示盘子中是否有橘子，初值为0（表示盘子为空，不许取，apple=1可取）

注：在缓冲区大小=1的情况下，可以不设置mutex。但若缓冲区大小>1，则需要设置mutex

semaphore plate=1,apple=0,orange=0;
dad(){  //父亲进程while(1){prepare an apple;   P(plate);   //互斥向盘中取、放水果，相当于盘子数-1put the apple on the plate;   //向盘中放苹果V(apple);  //允许取苹果，相当于苹果数+1}
}
mom(){  //母亲进程while(1){prepare an orange;P(plate);put the orange on the plate;V(orange);}
}
son(){  //儿子进程while(1){P(orange);   //互斥向盘中取橘子，相当于盘中橘子数-1take an orange from the plate;V(plate);   //允许向盘中取、放水果，相当于盘子数+1，告诉父母盘子空了eat the orange;}
}
daughter(){  //女儿进程while(1){P(apple);take an apple from the plate;V(plate);eat the apple;}
}

读者-写者问题

问题描述：有读者和写者两组并发进程，共享一个文件

1. 允许多个读者同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任意一个写者在完成写操作前不允许其他读者或写者工作
4. 写者执行写操作前，应让已有的读者和写者全部退出

• 信号量count：记录当前读者的数量，初值为0
• 互斥信号量mutex：保护更新count变量时的互斥
• 互斥信号量rw：保证读者和写者的互斥访问

读进程优先

int count=0;         //用于记录当前的读者数量
semaphore mutex=1;   //用于保护更新count变量时的互斥
semaphore rw=1;      //用于保证读者和写者互斥的访问文件
writer(){   //写者进程while(1){P(rw);     //互斥访问共享文件——加锁writing;   //写入V(rw);     //释放共享文件——解锁}
}
reader(){   //读者进程while(1){P(mutex);        //互斥访问count变量if(count==0)     //当第一个进程读共享文件时——加锁P(rw);   //阻止写进程写count++;         //读者计数器+1V(mutex);        //释放互斥变量countreading;         //读取P(mutex);        //互斥访问count变量count--;         //读者计数器-1if(count==0)     //当最后一个进程读共享文件时——解锁V(rw);   //允许写进程写V(mutex);        //释放互斥变量count}
}

读进程优先会导致：写进程“饿死”

写进程优先

当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行

• 增加一个信号量w：用于实现“写优先”，初值为1

int count=0;         //用于记录当前的读者数量
semaphore mutex=1;   //用于保护更新count变量时的互斥
semaphore rw=1;      //用于保证读者和写者互斥的访问文件
semaphore w=1;       //用于实现“写优先”
writer(){   //写者进程while(1){P(w);  //在无写进程请求时进入P(rw);     //互斥访问共享文件——加锁writing;   //写入V(rw);     //释放共享文件——解锁V(w);  //恢复对共享文件的访问}
}
reader(){   //读者进程while(1){P(w);  //在无写进程请求时进入P(mutex);        //互斥访问count变量if(count==0)     //当第一个进程读共享文件时——加锁P(rw);   //阻止写进程写count++;         //读者计数器+1V(mutex);        //释放互斥变量countV(w);  //恢复对共享文件的访问reading;         //读取P(mutex);        //互斥访问count变量count--;         //读者计数器-1if(count==0)     //当最后一个进程读共享文件时——解锁V(rw);   //允许写进程写V(mutex);        //释放互斥变量count}
}

哲学家进餐问题

问题描述：一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们只会思考和进餐。

注：若遇到一个进程需要同时持有多个临界资源的情况，应参考哲学家问题的思想

1. 哲学家在思考时，并不影响他人
2. 只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根拿起）
3. 若筷子已在他人手上，则需要等待
4. 饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐。进餐完毕后，放下筷子继续思考

• 互斥信号量数组chopstick[5]={1,1,1,1,1}：用于对5个筷子的互斥访问
• 哲学家 i 号，左边筷子编号为 i ，右边筷子编号为 (i+1)%5

制定规则：当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子（并不保证都可用时拿起）

semaphore chopstick[5]={1,1,1,1,1};   //初始化信号量
semaphore mutex=1;    //设置取筷子的信号量
Pi(){  //i号哲学家的进程do{P(mutex);   //在取筷子前获得互斥量P(chopstick[i]);   //取左边筷子P(chopstick[(i+1)%5]);   //取右边筷子V(mutex);   //释放取筷子的信号量eat;   //进餐V(chopstick[i]);   //放回左边筷子V(chopstick[(i+1)%5]);   //放回右边筷子think;  //思考}while(1);
}

//哲学家进餐模板
//定义大锁
semaphore lock=1;
//定义资源数int
//如 有a、b、c三类资源，分配有9、8、5个，则定义3个int变量：int a=9; int b=8; int c=5;
Process(){while(1){P(lock);if(所有资源都够){所有资源int值减少;取xxx资源;V(lock);break;}V(lock);}做进程该做的事;  //用中文说明即可P(lock);归还所有资源，所有资源int值增加;V(lock);
}

吸烟者问题（生产多个产品的单生产者）

问题描述：一个系统有三个抽烟者进程和一个供应者进程。

1. 抽烟者需要三种材料：烟草、纸和胶水
2. 第一个抽烟者拥有烟草，第二个抽烟者拥有纸，第三个抽烟者拥有胶水
3. 供应者无限提供三种材料，供应者每次将两种材料（组合）放到桌子上。
4. 拥有剩下那种材料的抽烟者卷一根烟并抽掉，同时给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上

• 供应者与三个抽烟者是同步关系；三个抽烟者对抽烟这个动作是互斥
• 信号量offer1，offer2，offer3分别表示两两组合（烟草和纸的组合、烟草和胶水的组合、纸和胶水的组合）
• 信号量finish：用于互斥进行抽烟动作

int num=0;   //存储随机数
semaphore offer1=0;   //定义信号量对应烟草和纸组合的资源
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0;   //定义信号量表示抽烟是否完成
provider(){   //供应者while(1){num++;num=(num+1)%3;if(num==0)V(offer1);   //提供烟草和纸else if(num==1)V(offer2);   //提供烟草和胶水elseV(offer3);   //提供纸和胶水任意两种材料放在桌子上;P(finish);}
}
smoker1(){   //拥有烟草者while(1){P(offer3);    //检查是否为组合3拿纸和胶水，卷成烟，抽掉;V(finish);}
}
smoker2(){   //拥有纸者while(1){P(offer2);拿烟草和胶水，卷成烟，抽掉;V(finish);}
}
smoker3(){   //拥有胶水者while(1){P(offer1);拿烟草和纸，卷成烟，抽掉;V(finish);}
}

理发师叫号

问题描述：一位理发师、一把理发椅，n把顾客等待理发的椅子

1. 无顾客，理发师在理发椅上睡觉
2. 有顾客，顾客叫醒理发师
3. 理发师正在理发时，有顾客，该顾客坐在空椅上，若无空椅，则离开

int num=0; //表示有几个顾客等待被服务
semaphore lock=1;  //互斥访问num
semaphore rest=0;   //同步信号量，让服务人员排队等待的队列
semaphore wait=0;   //同步信号量，让顾客排队等待的队列
Server(){                                            Customer(){while(1){                                             P(lock);P(lock);                                          if(num>等待人数上限){ //有些场景可能没有规定人数上限if(num>0){                                             V(lock);num--;                                             离开;叫号;                                          }else{V(lock);                                           num++;V(wait);   //唤醒一个顾客                           取号/排队;为顾客服务;                                         V(lock);}else{                                                  V(rest);   //唤醒一个等待的服务人员V(lock);                                            P(wait);   //等待被服务P(rest);   //服务人员休息                            被服务;}                                                  }}                                                 }
}