【例1】有三个进程PA 、PB 和PC 协作解决文件打印问题：PA 将文件记录从磁盘读入内存的缓冲区1中，每执行一次读一个记录；PB 将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC 将缓冲区2中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。请用信号量来保证文件的正确打印。
答：该文件打印过程的同步算法可描述如下：
【例2】进程A1、A2、…An1通过m 个缓冲区向进程B1、B2、…Bn2不断地发送消息。发送和接收工作遵循如下规则：
（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。
（2）对于每一个消息，B1、B2、…Bn2都需各接收一次，读入自己的数据区内。
（3）m 个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。
试用wait,signal 操作描述它们的同步关系。
分析：本题是生产者－消费者问题的一个变形。由于每个缓冲区都只写一次，但要读n2次，故我们可将每个缓冲区看成是由n2格组成的。只有当某个缓冲区的n2
格都空闲时，才允许写入，
而且写一次缓冲区相当于将该缓冲区的n2格全部写一遍。Bj 进程从缓冲中取消息时，它只取相应缓冲的第j 格。由于每个Bj 取消息的速度不同，故需为它们分别设置指针outj ，用来指示从哪个缓冲区的第j 格中取消息。
答：我们将每个缓冲区看成是由n2格组成的，可为本题设置下列信号量：mutex，初值为1，用来实现对缓冲区的互斥访问；empty[i](i=1,…,n2)，初值均为m ，每个empty[i]对应于缓冲池的第i 格中的所有空闲缓冲区；full[i](i=1,…,n2)，初值均为0，对应缓冲池第i 格中装有消息的缓冲区。另外还需要提供整型变量in 用来指示将消息放入哪个缓冲区，outj(j=1,…,n2)用来指示Bj 从哪个缓冲区中取消息，这些变量的初值均为0。Ai,Bj 的算法描述如下：
【例3】设有两个生产者进程A 、B 和一个销售进程C ，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库，而且要求生产A 产品和B 产品的件数满足以下关系：
－n ≤A 的件数－B 的件数≤m
其中n 、m 是正整数，但对仓库中A 产品和B 产品的件数无上述要求，请用信号量机制写出A 、
B 、
C 三个进程的工作流程。
分析：本题中存在着以下的同步和互斥关系：（1）生产者A 、B 和消费者C 之间，不能同时将产品入库和出库，故仓库是一个临界资源。（2）两个生产者之间必须进行同步。当生产者的A 、B 产品的件数之差大于等于m 时，生产者A 必须等待；小于等于－n 时，生产者B 必须等待。这种关系可想象成有两种令牌，分别跟允许A 和B 生产的产品数量相关，A 和B 必须取得对应的令牌后才能生产产品，故这两类令牌也就是两种临界资源。（3）生产者和销售者之间也必有进行同步，只有当生产者生产出产品并入库后，销售者才能进行销售。
答：为了互斥地入库和出库，需为仓库设置一初值为1的互斥信号量mutex ；为了使生产的产品件数满
generated足：－n ≤A 的件数－B 的件数≤m ，需设置两个信号量，其中SAB 表示当前允许A
生产
的产品数量，其初值为m,SBA表示当前允许B生产的产品数量，其初值为n；还需设置一个初值为0的资源信号量S，对应于仓库的产品量。具体的同步算法如下：
【例4】请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。
答：将独木桥的两个方向分别标记为A和B；并用整型变量countA,countB分别表示A、B方向上已在独木桥上的行人数，它们的初值为0；再设置三个初值都为1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向行人对独木桥的互斥使用。则可将A方向行人的动作描述为：
【例5】嗜睡的理发师问题：一个理发店由一个有Ｎ张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。
分析：本题中，顾客进程和理发师进程之间存在着多种同步关系：
（１）只有在理发椅空闲时，顾客才能坐到理发椅上等待理发师理发，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待。这种同步关系类似于单缓冲（对应于理发椅）的生产者－消费者问题中的同步关系，故可通过信号量empty和full来控制。
（２）顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开，而理发师则需等待顾客付费，并在收费后通知顾客离开，这可分别通过两个信号量payment和receipt来控制。
（３）等候室中的Ｎ张沙发是顾客进程竞争的资源，故还需为它们设置一个资源信号量sofa。
（４）为了控制顾客的人数，使顾客能在所有的沙发都被占用时离开理发店，还必须设置一个
整形变量count来对理发店中的顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，这可通过
一个互斥信号量mutex来实现。
答：为解决上述问题，需设置一个整型变量count用来对理发店中的顾客进行计数，并需设置６个信号量。其中：mutex用来实现顾客进程对count变量的互斥访问，其初值为１；sofa是对应于等候室中Ｎ张沙发的资源信号量，其初值为Ｎ；empty表示是否有空闲的理发椅，其初值为１；full表示理发椅是否坐有等待理发的顾客，其初值为０；payment用来等待付费，其初值为０；receipt 用来等待收费，其初值为０。具体的算法描述如下：
【例6】试用记录型信号量写出一个不死锁的哲学家进餐问题的算法。
答：除了为每只筷子设置一个初值为１的信号量chopstick[i](i=0,…,4)外，还需再设置一个初值为４的信号量Sm，以限制同时就餐的哲学家人数不超过４.第i个哲学家的活动可描述为：
【例7】请给出一个写者优先的“读者－写者”问题的算法描述。
分析：与读者优先不同的方案有三种。第一种是读者和写者的地位是完全平等的，即无论是读者、还是写者，都按它们到达的时间先后决定优先次序。第二种方案中，写者的优先权得到了提高，先于写者到达的读者比写者优先，但当一个写进程声明要进行写操作时，其后续读者必须等写操作完成之后，才能进行读。而且，如果在写完成之前，又有新的写者到达，那么新的写者的优先权将高于已在
等待的读者。第三种方案写者的优先权更高，某个写者到达时，即使它是目前唯一的写者，那些先于它到达但还没来得及读的读者都将等待它完成写操作。
答：为了使写者优先，可在原来的读者优先的基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成。初值为0的整型变量writecount用来写者进行计数；初值为1的互斥信号量mutex用来实现多个写者对writecount的互斥访问。
读者动作的描述如下：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。