经典进程同步互斥问题集VIP免费

1【例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格都空闲时，才允许写入，varempty1,full1,empty2,full2:semaphore:=1,0,1,0;beginparbeginPA:beginrepeat从磁盘读一个记录;wait(empty1);将记录存放到缓冲区1中;signal(full1);untilfalseendPB:beginRepeatwait(full1);从缓冲区1中取出一个记录;signal(empty1);wait(empty2);将记录复制到缓冲区2中;signal(full2);untilfalseendPC:beginrepeatwait(full2);从缓冲区2中取出一个记录;signal(empty2);将取出的记录打印出来;untilfalseendparendendGeneratedbyFoxitPDFCreator©FoxitSoftwarehttp://www.foxitsoftware.comForevaluationonly.2而且写一次缓冲区相当于将该缓冲区的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；为了使生产的产品件数满足：－n≤A的件数－B的件数≤m，需设置两个信号量，其中SAB表示当前允许A生产Ai(i=1,…,n1):beginrepeatfork:=1ton2dowait(empty[k]);wait(mutex);将Ai的消息放入第in个缓冲区的所有n2格中；in:=(in+1)modm;signal(mutex)fork:=1ton2dosignal[full[k]];untilfalseendBj(j=1,…,n2):beginrepeatwait(full[j]);wait(mutex);从第outj个缓冲区的第j格中取出消息；outj:=(outj+1)modn2;signal(mutex);signal[empty[j]];将消息写到数据区中；untilfalseendGeneratedbyFoxitPDFCreator©FoxitSoftwarehttp://www.foxitsoftware.comForev...