经典进程同步问题

2024-03-25 15:34:34

在多道程序环境下，进程同步问题十分重要，也是相当有趣的问题，因而吸引了不少学者对它进行研究，由此产生了一系列经典的进程同步问题，其中较有代表性的是 “生产者-消费者问题” 、“读者-写者问题” 、 “哲学家进餐问题” 等等。通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步概念及实现方法。

读者-写者问题

所谓“读者-写者（Reader-Writer Problem)问题“，是指保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题。

举例

设某航空公司有2个售票处，它们通过远程终端访问设在公司总部的航空订票系统，并要查询或修改系统中记录所有班机当前订票数的数据库B。
设Bi为某班机的当前订票数，P1和P2分别代表2个售票处的售票进程，R1和R2为进程执行时使用的工作寄存器。由于售票进程并发执行，且各自访问数据库B的时间是随机的，故有可能出现下面的访问序列(假定Bi的当前值为x)：
P1:R1:=Bi
R1:=R1+1
P2:R2:=Bi
R2:=R2+1
Bi:=R2
P1:Bi:=R1
可见，Bi的新值是X+1，而不是正确的X+2。这里的P1和P2均为写者，显然，对于写者Bi为临界资源，因此写者应该互斥。

读者进程与写者进程的一般结构：

var mutex,wrt:psem;
  readcount:integer;
  seminit(mutex.v,1;wrt.v,1);
  readcount:=0;
cobegin
  procedure reader;
  begin
     P(mutex);
     readcount:=readcount+1;
        if readcount=1 then P(wrt);
     V(mutex);
reading is perfermed；
      P(mutex);
   readcount:=readcount-1；
   if readcount=0 then Ｖ(wrt) ；
      V(mutex);
      end;
Procedure writer;
  begin
         Ｐ(wrt);
          writing is perfermed;
          V(wrt);
  end;
  coend;

⑴ 确定进程数和进程间的关系
⑵ 确定互斥和同步的规则
⑶ 确定同步、互斥的操作流程
⑷ 确定同步和互斥的信号量
⑸ 确定同步和互斥的信号量的初值
⑹ 确定同步和互斥的PV 操作的位置
⑺ 用类Pacal 语言或其它语言描述同步或互斥算法。

练习

桌上有个能盛得下五个水果的空盘子。爸爸不停地向盘中放苹果或桔子，儿子不停地从盘中取出桔子享用，女儿不停地从盘中取出苹果享用。规定三人不能同时从盘子中取放水果。
从参考选项中，选择正确选项序号，填入用信号量实现爸爸、儿子、女儿这三个循环进程同步的算法的空白处。
为了描述上述同步问题，可定义如下的信号量：
semaphore empty=5, orange=0, apple=0, mutex=1;
爸爸、儿子、女儿的算法分别为：