《经典进程同步互斥问题集》由会员分享，可在线阅读，更多相关《经典进程同步互斥问题集（8页珍藏版）》请在金锄头文库上搜索。
1、 1 【例 1】有三个进程 PA、PB 和 PC 协作解决文件打印问题：PA 将文件记录从磁盘读入内存的 缓冲区 1 中，每执行一次读一个记录；PB 将缓冲区 1 中的内容复制到缓冲区 2 中，每执行一次复 制一个记录；PC 将缓冲区 2 中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录 大小一样。请用信号量来保证文件的正确打印。 答：该文件打印过程的同步算法可描述如下： 【例 2】进程 A1、A2、An1 通过 m个缓冲区向进程 B1、B2、Bn2 不断地发送消息。发送 和接收工作遵循如下规则： （1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样。 （2
2、）对于每一个消息，B1、B2、Bn2 都需各接收一次，读入自己的数据区内。 （3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。 试用 wait,signal 操作描述它们的同步关系。 分析：本题是生产者消费者问题的一个变形。由于每个缓冲区都只写一次，但要读 n2 次， 故我们可将每个缓冲区看成是由 n2 格组成的。只有当某个缓冲区的 n2 格都空闲时，才允许写入，var empty1,full1,empty2,full2:semaphore := 1,0,1,0 ; begin parbegin PA:begin repeat 从磁盘读一个记录; wait(empty1);
3、 将记录存放到缓冲区 1 中; signal(full1); until false end PB:begin Repeat wait(full1); 从缓冲区 1 中取出一个记录; signal(empty1); wait(empty2); 将记录复制到缓冲区 2 中; signal(full2); until false end PC:begin repeat wait(full2); 从缓冲区 2 中取出一个记录; signal(empty2); 将取出的记录打印出来; until false end parend end Generated by Foxit PDF Creator F
4、oxit Software http:/ For evaluation only.2 而且写一次缓冲区相当于将该缓冲区的 n2 格全部写一遍。Bj 进程从缓冲中取消息时，它只取相应 缓冲的第 j 格。由于每个 Bj 取消息的速度不同，故需为它们分别设置指针 outj，用来指示从哪个缓 冲区的第 j 格中取消息。 答：我们将每个缓冲区看成是由 n2 格组成的，可为本题设置下列信号量：mutex,初值为 1，用 来实现对缓冲区的互斥访问；emptyi(i=1,n2)，初值均为 m，每个 emptyi对应于缓冲池的第 i 格中的所有空闲缓冲区；fulli(i=1,n2)，初值均为 0，对应缓冲池第
5、i 格中装有消息的缓冲区。 另外还需要提供整型变量 in 用来指示将消息放入哪个缓冲区，outj(j=1,n2)用来指示 Bj 从哪个缓 冲 区 中 取 消 息 ， 这 些 变 量 的 初 值 均 为0 。 Ai,Bj的 算 法 描 述 如 下 ：【例 3】设有两个生产者进程 A、B 和一个销售进程 C，他们共享一个无限大的仓库，生产者 每次循环生产一个产品， 然后入库供销售者销售； 销售者每次循环从仓库中取出一个产品进行销售。 如果不允许同时入库，也不允许边入库边出库，而且要求生产 A 产品和 B 产品的件数满足以下关 系： nA 的件数B 的件数m 其中 n、 m是正整数， 但对仓库中 A
6、 产品和 B 产品的件数无上述要求， 请用信号量机制写出 A、 B、C 三个进程的工作流程。 分析：本题中存在着以下的同步和互斥关系： （1）生产者 A、B 和消费者 C 之间，不能同时将 产品入库和出库，故仓库是一个临界资源。 （2）两个生产者之间必须进行同步。当生产者的 A、B 产品的件数之差大于等于 m 时，生产者 A 必须等待；小于等于n 时，生产者 B 必须等待。这种 关系可想象成有两种令牌，分别跟允许 A 和 B 生产的产品数量相关，A 和 B 必须取得对应的令牌 后才能生产产品，故这两类令牌也就是两种临界资源。 （3）生产者和销售者之间也必有进行同步， 只有当生产者生产出产品并入
7、库后，销售者才能进行销售。 答：为了互斥地入库和出库，需为仓库设置一初值为 1 的互斥信号量 mutex；为了使生产的产 品件数满足：nA 的件数B 的件数m，需设置两个信号量，其中 SAB 表示当前允许 A 生产Ai(i=1,n1):begin repeat for k:=1 to n2 do wait(emptyk); wait(mutex); 将 Ai 的消息放入第 in 个缓冲区的所有 n2 格中； in := (in+1) mod m; signal(mutex) for k:=1 to n2 do signalfullk; until false end Bj(j=1,n2):be
8、gin repeat wait(fullj); wait(mutex); 从第 outj 个缓冲区的第 j 格中取出消息； outj := (outj+1) mod n2; signal(mutex); signalemptyj; 将消息写到数据区中； until false end Generated by Foxit PDF Creator Foxit Software http:/ For evaluation only.3 的产品数量，其初值为 m,SBA 表示当前允许 B 生产的产品数量，其初值为 n;还需设置一个初值为 0 的资源信号量 S，对应于仓库的产品量。具体的同步算法如下：
9、 【例 4】请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向 有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。 答：将独木桥的两个方向分别标记为 A 和 B；并用整型变量 countA,countB 分别表示 A、B 方 向上已在独木桥上的行人数，它们的初值为 0；再设置三个初值都为 1 的互斥信号量：SA 用来实现 对 countA 的互斥访问，SB 用来实现对 countB 的互斥访问，mutex 用来实现两个方向行人对独木桥 的互斥使用。则可将 A 方向行人的动作描述为： var SAB,SBA,S,mutex : semaph
10、ore := m,n,0,1; begin parbegin process A : begin repeat wait(SAB); produce a product A; signal(SBA); wait(mutex); add the product A to the storehouse; signal(mutex); signal(S); until false end process B : begin repeat wait(SBA); produce a product B; signal(SAB); wait(mutex); add the product B to the
11、 storehouse; signal(mutex); signal(S); until false end process C : begin repeat wait(S); wait(mutex); take a product A or B from storehouse; signal(mutex); sell the product; until false end parend end Generated by Foxit PDF Creator Foxit Software http:/ For evaluation only.4 【例 5】嗜睡的理发师问题：一个理发店由一个有张
12、沙发的等候室和一个放有一张理发椅的 理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都 已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐 下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾 客必须付费，直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。 分析：本题中，顾客进程和理发师进程之间存在着多种同步关系： （）只有在理发椅空闲时，顾客才能坐到理发椅上等待理发师理发，否则顾客便必须等待； 只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待。这种同步关系类似于单
13、缓 冲（对应于理发椅）的生产者消费者问题中的同步关系，故可通过信号量 empty 和 full 来控制。 （）顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开，而理发师则需等待 顾客付费，并在收费后通知顾客离开，这可分别通过两个信号量 payment 和 receipt 来控制。 （）等候室中的张沙发是顾客进程竞争的资源，故还需为它们设置一个资源信号量 sofa。 （）为了控制顾客的人数，使顾客能在所有的沙发都被占用时离开理发店，还必须设置一个var SA,SB,mutext:semaphore:=1,1,1; countA,countB:integer:=0,0; begin pa
14、rbegin process AtoB:beging repeat wait(SA); if(countA=0) then wait(mutex); countA := countA+1; signal(SA); 通过独木桥； wait(SA); countA := countA-1; I f(countA=0) then signal(mutex); signal(SA); until false end process BtoA:beging repeat wait(SB); if(countB=0) then wait(mutex); countB := countB+1; signal
15、(SB); 通过独木桥； wait(SB); countB := countB-1; I f(countB=0) then signal(mutex); signal(SB); until false end parend end Generated by Foxit PDF Creator Foxit Software http:/ For evaluation only.5 整形变量 count 来对理发店中的顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，这可 通过一个互斥信号量 mutex 来实现。 答：为解决上述问题，需设置一个整型变量 count 用来对理发店中的顾客进行计数，并需设置 个信号量。其中：mutex 用来实现顾客进程对 count 变量的互斥访问，其初值为；sofa 是对应 于等候室中张沙发的资源信号量，其初值为；empty 表示是否有空闲的理发椅，其初值为； full 表示理发椅是否坐有等待理发的顾客， 其初值为； payment 用来等待付费， 其初值为； receipt 用来等待收费，其初值为。具体的算法描述如下： var count:integer:=0; mutex,sofa,empty,full : semaphore :=
