经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 计算机原理 » 查看文章
操作系统——信号量例题
来源:cnblogs  作者:拓扑逻辑  时间:2021/6/15 8:55:10  对本文有异议

有一个仓库,可以存放 A 和 B 两种产品,仓库的存储空间足够大,但要求: (1)一次只能存入一种产品(A 或 B); (2)-N < (A 产品数量-B 产品数量) < M。 其中,N 和 M 是正整数。试用“存放 A”和“存放 B”以及 P、V 操作描述产品 A 与 产品 B 的入库过程。

  1. Semaphore Sa = M - 1;
  2. Semaphore Sb = N - 1;
  3. //代表还能存入的数量
  4. Semaphore mutex = 1;
  5. process_A() {
  6. while(1){
  7. P(Sa); //取一个A产品准备入库
  8. P(mutex);
  9. A产品入库;
  10. // A产品入库后还能存入A产品数量-1
  11. V(mutex);
  12. V(Sb); //还能存入B产品数量+1
  13. }
  14. }
  15. process_B() {
  16. while(1){
  17. P(Sb); //取一个B产品准备入库
  18. P(mutex);
  19. B产品入库;
  20. // B产品入库后还能存入B产品数量-1
  21. V(mutex);
  22. V(Sa); //还能存入A产品数量+1
  23. }
  24. }

桌子上有一只盘子,最多可容纳两个水果,每次只能放入或取出一个水果。爸爸专向盘子放苹果( apple),妈妈专向盘子中放桔子( orange);两个儿子专等吃盘子中的桔子,两个女儿专等吃盘子中的苹果。请用 P、 V 操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

  1. Semaphore mutex = 1; //互斥信号量, 其初值为1
  2. Semaphore empty = 2; //记录允许向盘子中放入水果的个数,初值为2
  3. Semaphore orange = 0; //盘子中已放入的苹果的个数,初值为0
  4. Semaphore apple = 0; //盘子中已放入的桔子的个数,初值为0
  5. main()
  6. {
  7. Cobegin
  8. {
  9.    father //父亲进程
  10. {
  11.     while (true)
  12. {
  13.          P(empty); //减少盘中可放入的水果数
  14. P(mutex); //申请向盘中取、放水果
  15. 向盘中放苹果;
  16. V(mutex); //允许向盘中取、放水果
  17. V(apple); //递增盘中的苹果数
  18. }
  19. }
  20. mother //母亲进程
  21. {
  22.     while (true)
  23. {
  24.           P(empty); //减少盘中可放入的水果数
  25. P(mutex); //申请向盘中取、放水果
  26. 向盘中放桔子;
  27. V(mutex); //允许向盘中取、放水果
  28. V(orange); //递增盘中的桔子数
  29. }
  30. }
  31. daughterii=1,2 //两女儿进程
  32. {
  33.     while (true)
  34. {
  35.        P(apple); //减少盘中苹果数
  36. P(mutex); //申请向盘中取、放水果
  37. 取盘中苹果;
  38. V(mutex); //允许向盘中取、放水果
  39. V(empty); //递增盘中可放入的水果数
  40. }
  41. }
  42. sonjj=1,2 //两儿子进程
  43. {
  44.     while (true)
  45. {
  46.          P(orange); //减少盘中桔子数
  47. P(mutex); //申请向盘中取、放水果
  48. 取盘中桔子;
  49. V(mutex); //允许向盘中取、放水果
  50. V(empty); //递增盘中可放入的水果数
  51. }
  52. }
  53. }
  54. Coend
  55. }

有一个理发师,一把理发椅和 N 把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发师椅子上睡觉;当一个顾客到来时,必须唤醒理发师进行理发;如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和顾客各编一段程序(伪代码)描述他们的行为,要求不能带有竞争条件。

  1. Semaphore mutex = 1; //互斥信号量,初值为1.
  2. Semaphore Wait = 0; //等待服务的顾客数
  3. Semaphore barbers= 0; //等待顾客的理发师数
  4. Int custNum = 0; //等待的顾客(还没理发的)
  5. Costumer()
  6. {
  7.   while(true)
  8.   {
  9. P(mutex); //申请理发
  10. if(custNum>0)
  11.      {
  12. if(custNum<N) //若等待人数小于N
  13.        {
  14. V(mutex); //释放进程等待
  15. CustNum++; //增加等待人数
  16. }
  17.        else //若等待人数超过N
  18.         {
  19. V(mutex); //释放进程等待
  20. 离开;
  21. }
  22.      }
  23.     else //若目前无人等待
  24.     {
  25. V(mutex); //释放进程等待
  26. V(barbers); //如果必要的话,唤醒理发师
  27. 理发;
  28. 离开;
  29. P(mutex); //要求进程等待
  30. custNum--; //顾客人数减1
  31. V(mutex); //释放进程等待
  32. V(wait); //等待人数减1
  33.     }
  34.   }
  35. }
  36. Barber()
  37. {
  38.   while(true)
  39.   {
  40. P(mutex); //要求进程等待
  41. if(custNum ==0) //目前无顾客
  42.      {
  43. V(mutex); //释放进程等待
  44. P(barbers); //理发师睡觉
  45.    }
  46.     else
  47.     {
  48. V(mutex); //释放进程等待
  49. 理发;
  50.     }
  51.   }
  52. }

吸烟者问题。三个吸烟者在一间房间内,还有一个香烟供应者。为了制造并抽掉香烟,每个吸烟者需要三样东西:烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中,第一个有自己的烟草,第二个有自己的纸,第三个有自己的火柴。供应者将两样东西放在桌子上,允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者,供应者再放两样东西(随机地)在桌面上,然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。

  1. Semaphore S = 1; //供应者
  2. Semaphore S1,S2,S3; //三个吸烟者
  3. S1 = S2 = S3 = 0;
  4. bool flag1,flag2,fiag3; //三种吸烟原料
  5. fiag1=flag2=flag3=true;
  6. Apply() //供应者
  7. {
  8.   While(true)
  9.   {
  10. P(S);
  11.       取两样香烟原料放桌上,由flagi标记;
  12.     if (flag2 && flag3) //供纸和火柴
  13.       {
  14.     V(S1); //唤醒吸烟者一
  15.     }
  16.    else if(flag1 && fiag3) //供烟草和火柴
  17.       {
  18.     V(S2); //唤醒吸烟者二
  19.     }
  20.      else //供烟草和纸
  21.       {
  22.     V(S3); //唤醒吸烟者三
  23. }
  24.    }
  25. }
  26. Smoker1() //吸烟者一
  27. {
  28.    While(true)
  29.    {
  30.     P(S1);
  31.     取原料;
  32.     做香烟;
  33.     V(S); //唤醒供应者
  34.     吸香烟;
  35.    }
  36. }
  37. smoker2() //吸烟者二
  38. {
  39.    While(true)
  40.    {
  41.     P(S2);
  42.     取原料;
  43.     做香烟;
  44.     V(S); //唤醒供应者
  45.     吸香烟;
  46.    }
  47. }
  48. Smoker3() //吸烟者三
  49. {
  50.    While(true)
  51. {
  52.     P(S3);
  53.    取原料;
  54.    做香烟;
  55.     V(S); //唤醒供应者
  56.     吸香烟;
  57.    }
  58. }

面包师问题。面包师有很多面包和蛋糕,由 n 个销售人员销售。每个顾客进店后先取一个号,并且等着叫号。当一个销售人员空闲下来,就叫下一个号。请分别编写销售人员和顾客进程的程序。

  1. Semaphore buyer= 0; //顾客人数
  2. Semaphore seller = n; //销售人员数
  3. Semaphore mutex_s = 1; //用于销售人员的互斥信号量
  4. Semaphore mutex_b = 1; //用于顾客的互斥信号量
  5. int count_s = 0; //记录取号的值
  6. int count_b = 0; //记录叫号的值
  7. void Buy() //顾客进程
  8. {
  9. 进店;
  10. P(mutex_b); //取号
  11. count_b++;
  12.    V(mutex_b);
  13.    V(buyer);
  14.   P(seller); //等待叫号
  15. 买面包;
  16. 离开
  17. }
  18. void Sell()
  19. {
  20. while(true)
  21. {
  22. P(buyer);
  23. P(mutex_s); //叫号
  24. count_s++;
  25. 叫编号为count_s的顾客;
  26. V(mutex_s);
  27. V(seller);
  28. }
  29. }

桌上有一空盘,运行存放一只水果,爸爸可向盘中放苹果,也可放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘中空时一次只能放一个水果供吃者取用,用 P,V 原语实现爸爸儿子和女儿 3 个并发进程的同步。

  1. Semaphore S = 1; //S 表示盘子是否为空;
  2. Semaphore Sa = 0; //Sa 表示盘中是否有苹果;
  3. Semaphore Sb = 0; //Sb 表示盘中是否有桔子;
  4. Father() //父亲进程
  5. {
  6. while(TRUE)
  7.   {
  8. P(S);
  9. 将水果放入盘中;
  10. if (放入的是桔子)
  11. V(Sb);
  12. else
  13. V(Sa);
  14. }
  15. }
  16. Son() //儿子进程
  17. {
  18. while(TRUE)
  19.   {
  20. P(Sb);
  21. 从盘中取出桔子;
  22. V(S);
  23.      吃桔子;
  24. }
  25. }
  26. Daughter() //女儿进程
  27. {
  28. while(TRUE)
  29.   {
  30. P(Sa);
  31. 从盘中取出苹果;
  32. V(S);
  33. 吃苹果;
  34. }
  35. }

写者优先的读者--写者问题。读者-写者问题为数据库访问建立了一个模型。例如,一个系统,其中有许多竞争的进程试图读写其中的数据,多个进程同时读是可以接受的,但如果一个进程正在更新数据库,则所有的其他进程都不能访问数据库,即使读操作也不行。写者优先是指当一个写者到达时,将阻止其后面的读者进入数据库,直到其离开为止。

  1. Semaphore Mut1, Mut2, Wmutex, Fmutex; //互斥信号量
  2. int Rcount, Wcount; //读写者人数
  3. Mut1 = Mut2 = WMutex = Fmutex = 1;
  4. Rcount = Wcount = 0;
  5. Writer() //写者进程
  6. {
  7.    While(true)
  8.    {
  9.     P(Mut1);
  10.     Wcount=Wcount+1
  11.     If (Wcount==1)
  12.      {
  13.     P(Fmutex); //如有读者,写者阻塞在此处
  14.     }
  15.     V(Mut1);
  16.     P(WMutex);
  17.     写;
  18.     V(Wmutex);
  19.     P(Mut1);
  20.     Wcount=Wcount-1;
  21.     If (Wcount==0)
  22.      {
  23.     V(Fmutex);
  24.     }
  25.     V(Mut1);
  26.    }
  27. }
  28. Reader() //读者进程
  29. {
  30.    While(true)
  31.    {
  32.     P(Mut2);
  33.     Rcount=Rcount+1;
  34.     If (Rcount==1)
  35.       {
  36.     P(Fmutex);
  37.     }
  38.     V(Mut2);
  39.     读;
  40.     P(Mut2);
  41.     Rcount=Rcount-1;
  42.     If (Rcount==0)
  43.      {
  44.     V(Fmutex);
  45.     }
  46.     V(Mut2);
  47.    }
  48. }

在天津大学与南开大学之间有一条弯曲的小路,这条路上每次每个方向上只允许一辆自行车通过。但其中有一个小的安全岛 M,同时允许两辆自行车停留,可供两辆自行车已从两端进入小路的情况下错车使用。如图所示。
file
下面的算法可以使来往的自行车均可顺利通过。其中使用了 4 个信号量, T 代表天大路口资源, S 代表南开路口资源, L 代表从天大到安全岛一段路的资源, K 代表从南开到安全岛一段路的资源。程序如下,请在空白位置处填写适当的 PV 操作语句,每处空白可能包含若干个 PV 操作语句。

  1. begin
  2. t:=1;s:=1;l:=1;k:=1;
  3. cobegin
  4. 从天大到南开的进程
  5. begin
  6. ______(1)______
  7. 通过 L 路段;
  8. 进入安全岛 M
  9. ______(2)______
  10. 通过 K 路段
  11. ______(3)______
  12. end
  13. 从南开到天大的进程
  14. begin
  15. 略,与“从天大到南开的进程”相反。
  16. end
  17. coend
  18. end

解答:

(1) P(t); P(l);

(2) V(l); P(k);

(3) V(k); V(t);

三个进程 P1、 P2、 P3 互斥使用一个包含 N(N>0)个单元的缓冲区。 P1 每次用 produce()生成一个正整数并用 put()送入缓冲区某一空单元中;P2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数;P3 每次用 geteven()从该缓冲区中取出一个偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动,并说明所定义信号量的含义。要求用伪代码描述。

  1. P1()
  2. {
  3.    While(true)
  4.    {
  5.     X = produce(); //生成一个数
  6.       P(empty); //是否有空单元格
  7.     P(mutex); //进入临界区
  8.     Put();
  9.     if(X%2 == 0)
  10.     V(s2); //如果是偶数,向P3发出信号
  11.     else
  12.     V(s1); //如果是奇数,向P2发出信号
  13.     V(mutex); //离开临界区,释放互斥信号量
  14.    }
  15. }
  16. P2()
  17. {
  18.    While(true)
  19.    {
  20.     P(s1); //收到P1发送来的信号,已产生奇数
  21.       P(mutex); //进入临界区
  22.     getodd();
  23.     countodd():=countodd()+1;
  24.     V(mutex);
  25.     V(empty); //离开临界区,释放互斥信号量
  26.    }
  27. }
  28. P3()
  29. {
  30.    While(true)
  31.    {
  32.       P(s2) //收到P1发送来的信号,已产生偶数
  33.     P(mutex); //进入临界区
  34.     geteven();
  35.     counteven():=counteven()+1;
  36.     V(mutex);
  37.     V(empty); //离开临界区,释放互斥信号量
  38.    }
  39. }

原文链接:http://www.cnblogs.com/revolver/p/14870437.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号