devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统-经典同步例题_操作系统同步问题练习

作者：不正经 | 2024-06-02 06:24:32

赞

踩

操作系统同步问题练习

目录

1. 生产者/消费者问题

2. 读者和写者问题

3. 理发师睡觉问题

1. 生产者/消费者问题

描述：

  • 一个或多个生产者产生数据并放入缓冲
  • 每次只能有一个消费者从缓冲区取数据（互斥）
  • 每次只能由一个生产者或消费者访问缓冲区（互斥）
  • 保证缓冲区满时，生产者不会往缓冲区中增加数据
  • 保证缓冲区空时，消费者不能从缓冲区中取走数据

基本流程：

注意1：先申请资源信号量，再申请互斥信号量，顺序不能颠倒，否则死锁

注意2：同一进程中的多个signal语句顺序颠倒对执行无影响，但先释放互斥再资源时性能更好

注意3：同一信号量的PV操作可以出现在不同进程中，但必须配对

注意4：在一个进程中，wait操作不一定就先于signal

示例1

一个生产者和两个消费者被连接到大小为N的缓冲区上

  • 桌子上有一只盘子，最多可以放入N（N>0）个水果。
  • 爸爸随机向盘中放入苹果或桔子。儿子只吃盘中的桔子，女儿只吃盘中的苹果
  • 只有盘子中水果数目小于N时，爸爸才可以向盘子中放水果；
  • 仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果；
  • 每次只能放入或取出一个水果，且不允许多人同时使用盘子。

分析：

盘子是一互斥资源，故设置互斥信号量mutex

爸爸、儿子因为桔子的放入与取出而同步，设置产品资源信号量orange；

爸爸、女儿因为苹果的放入与取出而同步，设置产品资源信号量apple；

爸爸、儿子、女儿因为共享盘子，设置空间资源信号量empty。

程序：

  1. semaphore mutex=1;
  2. semaphore orange=0,apple=0,empty=N;
  3.  
  4. void father(){
  5.     while(true){
  6.         P(empty);
  7.         P(mutex);
  8.         //进入临界区，放置水果为result
  9.         V(mutex)
  10.         if (result == apple) V(apple);
  11.         else V(orange);
  12.  
  13. void son(){
  14.     whlie(true){
  15.         P(orange);
  16.         p(mutex);
  17.         //进入临界区，拿走橘子
  18.         V(mutex);
  19.         v(empty);
  20.     }
  21. }
  22.  
  23. void daughter(){
  24.     while(true){
  25.         P(apple);
  26.         P(mutex);
  27.         //进入临界区，拿走苹果
  28.         V(mutex);
  29.         V(empty);
  30.     }
  31. }

示例2

两个生产者和两个消费者被连接到大小为1的缓冲区上

  • 桌子上有一只盘子，爸爸负责向盘中放苹果，妈妈负责向盘中放桔子
  • 儿子只吃盘中的桔子，女儿只吃盘中的苹果。
  • 只有盘子为空时，爸爸或妈妈才可以向盘子中放入一个水果。
  • 仅当盘子中有自己需要的水果时，儿子或女儿才可以从盘子中取出相应的水果。

分析：

盘子是一互斥访问的空间资源，且缓冲大小为1，可只设置一个盘子资源信号量plate = 1

爸爸、女儿因为苹果的放入与取出而同步，设置产品资源信号量apple = 0；

妈妈、儿子因为桔子的放入与取出而同步，设置产品资源信号量orange = 0；

代码：

  1. semaphore plate=1, apple=0, orange=0;
  2.  
  3. void father(){
  4.     while(true){
  5.         P(plate);
  6.         //放苹果
  7.         V(apple)
  8.     }
  9. }
  10. void mother(){
  11.     while(true){
  12.         P(plate);
  13.         //放橘子
  14.         V(orange);
  15.     }
  16. }
  17. void son(){
  18.     while(true){
  19.         P(orange);
  20.         //拿橘子
  21.         V(plate);
  22.     }
  23. }
  24. void daughter(){
  25.     while(true){
  26.         P(apple);
  27.         //拿苹果
  28.         V(plate);
  29.     }
  30. }

例3

两个生产者和一个消费者被连接到大小为2的缓冲区上

  • 桌子上有一只盘子，最多可以放入2个水果，
  • 爸爸负责向盘中放苹果，妈妈负责向盘中放桔子，女儿负责取出并消费水果。放入者和取出者不允许同时使用盘子。
  • 当且仅当盘子中同时存在苹果和桔子时，女儿才从盘子中取出并消费水果。

分析：

盘子中是否可以放入苹果，设置空间资源信号量empty_apple；

盘子中是否可以取出苹果，设置产品资源信号量apple；

盘子中是否可以放入桔子，设置空间资源信号量empty_orange；

盘子中是否可以取出桔子，设置产品资源信号量orange

题中只说到“放入者和取出者不允许同时使用盘子”，那两个放入者可以同时使用盘子。所以不需要对盘子额外设置生产者的互斥信号量

程序：

  1. semaphore empty_apple=1, empty_orange=1;
  2. semaphore apple=0, orange=0;
  3.  
  4. void father(){
  5.     while(true){
  6.         P(empty_apple);
  7.         //放苹果
  8.         V(apple);
  9.     }
  10. } 
  11. void mother(){
  12.     while(true){
  13.         P(empty_orange);
  14.         //放橘子
  15.         V(orange);
  16.     }
  17. }
  18. void dauther(){
  19.     while(true){
  20.         P(apple);
  21.         P(orange);
  22.         //同时拿走苹果和橘子
  23.         V(orange);
  24.         V(apple);
  25.     }
  26. }

例4

一个生产者和两个消费者，一幅画要分别给两人看

  • 女儿负责画画，爸爸、妈妈负责欣赏。
  • 女儿在白板上画完一幅画后，请爸爸、妈妈均欣赏过一遍后，再创作新画，依次重复

分析：

题中说的是“均欣赏一遍后”，也没强调是“依次”欣赏，再结合实际可认为消费者之间不需要互斥（可以理解为，消费者只读，不互斥）

爸爸是否欣赏过，设置空间资源信号量empty_dad；

爸爸是否可以欣赏，设置产品资源信号量full_dad；

妈妈是否欣赏过，设置空间资源信号量empty_mom；

妈妈是否可以欣赏，设置产品资源信号量full_mom。

（其实对于爸爸妈妈是否可以访问也可以就只设置一个full=2的信号量就行）

程序：

  1. semaphore empty_dad = 1, empty_mom = 1; 
  2. semaphore full_dad = 0, full_mom = 0;   
  3.  
  4. void daughter(){
  5.     while(true){
  6.         P(empty_dad);
  7.         P(empty_mom)
  8.         //作画
  9.         V(full_dad);
  10.         V(full_mom);
  11.     }
  12. }
  13. void mother(){
  14.     while(true){
  15.         P(full_mom);
  16.         //看画
  17.         V(empty_mom);
  18.     }
  19. }
  20. void father(){
  21.     while(true){
  22.         P(full_dad);
  23.         //看画
  24.         V(empty_dad);
  25.     }
  26. }

2. 读者和写者问题

如何判断一个问题是生产者／消费者问题，还是读者／写者问题？

  • 生产者／消费者问题：数据消费后就没有了；读者／写者问题：数据可多次读。
  • 生产者／消费者问题：消费者彼此互斥；读者／写者问题：读者可以同时读。
  • 生产者／消费者问题：生产者/消费者之间有互斥关系和同步关系；读者／写者问题：读者/写者之间有互斥关系

例1. 读者优先

描述：

  • 一旦有读者正在读数据，则允许随后的读者进入读数据。
  • 只有当全部读者退出，才允许写者进入写数据。
  • 导致写者饥饿

信号量设置：

wsem：互斥信号量，用于Writers间互斥，Writers和Readers互斥

readcount：统计同时读数据的Readers个数

x：对变量readcount互斥算术操作

  1. semaphore wsem=1, x=1;
  2. int readcount=0;
  3.  
  4. void reader(){
  5.     while(true){
  6.         P(x);
  7.         readcount++;
  8.         if (readcount == 1) P(wsem);
  9.         V(x);
  10.         //读数据
  11.         P(x);
  12.         readcount--;
  13.         if (readcount == 0) V(wsem);
  14.         V(x)
  15.     }
  16. }
  17.  
  18. void writer(){
  19.     while(true){
  20.     P(wsem);
  21.     //写数据
  22.     V(wsem)
  23.     }
  24. }

例2. 公平读写

描述：

写过程中，若其它读者、写者到来，则按到达顺序处理

读过程中，若其他读者到来，直接进入临界区读数据

信号量设置：

wsem：互斥信号量，用于Writers间互斥，Reader互斥Writers

readcount：统计同时读数据的Readers个数

x：对变量readcount互斥算术操作

wrsem：互斥信号量，确定Writer 、Reader请求顺序

程序：

  1. semaphore x=l, wrsem=1, wsem=l;
  2. int readcount=0；
  3.  
  4. void reader() {
  5.   while (true) {
  6.     P(wrsem);
  7.     P(x);
  8.       readercount++;
  9.       if (readercount == 1) P(wsem);
  10.     V(x);
  11.     V(wrsem);
  12.     //读数据;
  13.     P(x);
  14.       readercount--;
  15.       if (readercount == 0) V(wsem);
  16.     V(x);
  17.   }
  18. }
  19. void writer(){
  20.     while(true){
  21.         P(wrsem);
  22.         P(wsem);
  23.         //写数据;
  24.         V(wsem);
  25.         V(wrsem);
  26.     }
  27. }

例3 写者优先

描述：

  • 当至少有一个写者声明想写数据时，则不再允许新的读者进入读数据。
  • 例如：(队列尾)WWRRW(头)，让三个W进程能优先于R进程写数据
  • 解决了写者饥饿问题，但降低了并发程度，系统的并发性能较差。

信号量设置：

rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据，第一个写者受rsem影响，一旦有第一个写者，后续写者不受rsem其影响。但是读者需要在rsem上排队。

writecount：用于控制rsem信号量

y：对变量writecount互斥算术操作

程序：

  1. int readcount = 0, writecount = 0;
  2. semaphore x=l, y= 1, wsem=1, rsem=l;
  3.  
  4. void reader(){
  5.     while(true){
  6.         P(rsem);
  7.         P(x);
  8.         readcount++;
  9.         if (readcount==1) P(wsem);
  10.         V(x);
  11.         V(rsem);
  12.         //读数据
  13.         P(x);
  14.         readcount--;
  15.         if (readcount==0) V(wsem);
  16.         V(x);
  17.     }
  18. }
  19. void writer(){
  20.     while(true){
  21.         P(y);
  22.         writecount++;
  23.         if (writecout==1) P(rsem);
  24.         V(y);
  25.         P(wsem);
  26.         //写数据
  27.         V(wsem);
  28.         P(y);
  29.         writecount--;
  30.         if (writecount==0) V(rsem);
  31.         V(y);    
  32.     }
  33. }

缺陷：WRRRR队列，W会等待长R队列

改进 : 增加z信号量，只对读者起作用

在rsem上不允许建造读进程的长队列，否则写进程将不能跳过这个队列.

允许一个读进程在rsem上排队,其他读进程在信号量z上排队

  1. int readcount = 0, writecount = 0;
  2. semaphore x=l, y= 1, wsem=1, rsem=l,z=1;
  3.  
  4. void reader(){
  5.     while(true){
  6.         P(z)
  7.         P(rsem);
  8.         P(x);
  9.         readcount++;
  10.         if (readcount==1) P(wsem);
  11.         V(x);
  12.         V(rsem);
  13.         V(z)
  14.         //读数据
  15.         P(x);
  16.         readcount--;
  17.         if (readcount==0) V(wsem);
  18.         V(x);
  19.     }
  20. }
  21. void writer(){
  22.     while(true){
  23.         P(y);
  24.         writecount++;
  25.         if (writecout==1) P(rsem);
  26.         V(y);
  27.         P(wsem);
  28.         //写数据
  29.         V(wsem);
  30.         P(y);
  31.         writecount--;
  32.         if (writecount==0) V(rsem);
  33.         V(y);    
  34.     }
  35. }

例4 过桥问题1

有一座东西方向的独木桥，同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待。桥上没有行人过桥时，任何一端的行人均可上桥。请用P、V操作来实现东西两端人过桥问题。    

分析：  

读者优先问题的变化，思想类似读者优先

两组读者，同一组之间可以同时读，不同组之间互斥，即只要有一组读者上桥，同组读者优先于另一组读者

桥-共享数据

murex：互斥信号量，用于两组读者互斥写者

countR：统计读者数目（同时在桥上的行人数目）

xR：对变量countR互斥算术操作

程序：

  1. int countA=0, countB=0;
  2. semaphore mutex=1, xA=1, xB=1;
  3.  
  4. void east_west(){
  5.     while(1){
  6.         P(xA)
  7.         countA++;
  8.         if (countA==1) P(mutex);
  9.         V(xA);
  10.         //过桥
  11.         P(xA);
  12.         countA--;
  13.         if (countA==0) V(mutex);
  14.         V(xA);
  15.     }
  16. }
  17. void west_east(){
  18.     while(1){
  19.         P(xB);
  20.         countB++;
  21.         if (countB==1) P(mutex);
  22.         V(xB);
  23.         //
  24.         P(xB);
  25.         countB--;
  26.         if (countB==0) V(mutex);
  27.         V(xB)
  28.     }
  29. }

例5 过桥问题2

 有一座东西方向的独木桥，同一方向的行人可连续过桥。当某一方向有行人过桥时，另一方向行人必须等待。桥上没有行人过桥时，任何一端的行人均可上桥。出于安全考虑，独木桥的最大承重为4人，即同时位于桥上的行人数目不能超过4。请用P、V操作来实现东西两端人过桥问题

分析：

类似上题，需引入信号量count=4来统计桥上人数，在进入临界区前后对count进行P、V

  1. int countA=0, countB=0;
  2. semaphore mutex=1, xA=1, xB=1, count=4;
  3.  
  4. void east_west(){
  5.     while(1){
  6.         P(xA)
  7.         countA++;
  8.         if (countA==1) P(mutex);
  9.         V(xA);
  10.         P(count)
  11.         //过桥
  12.         V(count)
  13.         P(xA);
  14.         countA--;
  15.         if (countA==0) V(mutex);
  16.         V(xA);
  17.     }
  18. }
  19. void west_east(){
  20.     while(1){
  21.         P(xB);
  22.         countB++;
  23.         if (countB==1) P(mutex);
  24.         V(xB);
  25.         P(count)  
  26.         //过桥
  27.         V(count)
  28.         P(xB);
  29.         countB--;
  30.         if (countB==0) V(mutex);
  31.         V(xB)
  32.     }
  33. }

3. 理发师睡觉问题

描述：

  • 理发店有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。
  • 如果没有顾客，则理发师睡觉。
  • 当一个顾客到来时，若理发师在睡觉他必须叫醒理发师进行理发，
  • 如果顾客到来时理发师正在理发，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他就离开。

分析：

  1.  
  2. semaphore barber=1   //理发师是否就绪
  3. semaphore ready=0;   //顾客是否就绪
  4. semaphore wait=5;    //空椅子个数  
  5. int num_customer=0;  //店里顾客总人数，等于6时新顾客离开
  6. semaphore mutex_num=1 //对num_customer互斥访问 
  7. semaphore finish=0;   //理发师是否完成理发
  8. void customer(){
  9.     while(true){
  10.         p(mutex_num);
  11.         if num_customer<6{
  12.             num_customer++;
  13.             V(mutex_num);
  14.             P(wait);      //找空椅子坐下
  15.             P(barber);    //找理发椅坐下
  16.             V(wait);      //释放空椅子 
  17.             V(ready);     //告知理发师该顾客准备好了
  18.             P(finish);    //等待完成理发
  19.             V(barber);    //释放理发椅
  20.             p(mutex_num);  
  21.             num_customer--;
  22.             V(P_mutex);
  23.         }
  24.         else V(num_mutex) 离开;
  25.     }
  26. }
  27.  
  28. void Baber(){
  29.     while(1){
  30.         P(ready);
  31.         //理发
  32.         V(finish);
  33.     }
  34. }

补充：理发师睡觉类似问题

银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务

  1. semaphore mutex = 1;              //互斥使用取号机的信号量
  2. semaphore empty = 10;             //空座位的数量信号量
  3. semaphore full = 0;               //已占座位的数量信号量
  4. semaphore service = 0;            //等待叫号信号量
  5.  
  6. void customer_i(){
  7.     P(empty);
  8.     P(mutex);
  9.     //取号
  10.     V(mutex);
  11.     V(full);
  12.     P(service);
  13.     V(empty);
  14.     //获取服务
  15. }
  16. void server(){
  17.     while(1){
  18.         P(full)
  19.         V(serveice)
  20.         //服务  
  21.     }     
  22. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/661569
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号