《经典进程同步问题.》由会员分享，可在线阅读，更多相关《经典进程同步问题.（41页珍藏版）》请在金锄头文库上搜索。
1、2.4 经典进程同步问题 在多道程序环境下，进程同步问题是十 分重要的，也是相当有趣的问题，因而吸引 了不少学者对它进行研究。 其中较有代表性的是“生产者消费 者问题”、“读者写者问题”、“哲学家进 餐问题”等。 1 2.4.1 生产者消费者问题 问题的描述： 有一群生产者进程生产消息，并将此消息有一群生产者进程生产消息，并将此消息 提供给消费者进程消费。为使生产者进程和消提供给消费者进程消费。为使生产者进程和消 费者进程并发执行，在它们之间设置一个具有费者进程并发执行，在它们之间设置一个具有 n n个缓冲区的公共缓冲池。生产者进程将它所个缓冲区的公共缓冲池。生产者进程将它所 生产的消息放入一
2、个缓冲区中，消费者进程可生产的消息放入一个缓冲区中，消费者进程可 以从一个缓冲区中取得一个消息消费。以从一个缓冲区中取得一个消息消费。 不允许消息费者进程到一个空缓冲区中去不允许消息费者进程到一个空缓冲区中去 取消息，也不允许生产者进程向一个已装有消取消息，也不允许生产者进程向一个已装有消 息且尚未被取走消息的缓冲区中投放消息。息且尚未被取走消息的缓冲区中投放消息。 2 需要解决的问题： 1、对缓冲池的互斥访问，即只有一个进 程访问缓冲区。 2、对生产、消费进程的同步，即：有产 品时才能消费，无产品时，必须先生产后 消费；有空间时才能生产，空间满时，必 须先消费再生产。 3 信号量的设置： 1
3、、一个互斥信号量mutex，用于实现对共 享缓冲区的互斥访问，初始值为1。 2、两个同步信号量，分别表示可用资源数 ： Empty：表示空缓冲区的个数，初始值为n Full：表示装有消息的缓冲区的个数，初 始值为0，（一个缓冲区中放一条消息） 4 一、利用记录型信号量 解决生产者消费者问题 数据结构： Var mutex, empty, full：semaphore=1，n，0； /定义信号量并赋初值 buffer：array0, , n-1 of item; /定义缓冲区 in, out: integer=0, 0; /定义存取指针的初始位置 5 Proceduer： /生产者进程 begi
4、n repeat 生产一件产品; wait(empty); wait(mutex); bufferin:=nextp; in=(in+1) mod n; signal(mutex); signal(full); until false; end empty:=empty-1; if empty 0 then block; mutex:=mutex-1; if mutex 0 then block; full:=full + 1; if full =0 then wakeup; mutex:=mutex+1; if mutex =0 then wakeup; 6 consumer：/消费者进程
5、begin repeat wait(full); wait(mutex); nextc:=bufferout; out=(out+1) mod n; signal(mutex); signal(empty); 消费这件产品; until false; end full:=full - 1; if full 0 then block; mutex:=mutex-1; if mutex0 then block; empty:=empty+1; if empty=1 then empty:=empty-1; mutex:=mutex-1; mutex:=mutex+1; full:=full + 1
6、; 12 consumer：/消费者进程 begin repeat Swait(full，mutex); nextc:=bufferout; out=(out+1) mod n; Ssignal(mutex，empty); 消费这件产品; until false; end if full =1 and mutex=1 then full:=full - 1; mutex:=mutex-1; mutex:=mutex+1; empty:=empty+1; 13 3利用管程解决生产者消费者问题 在利用管程方法来解决生产者消费者问题时， 首先便是为它们建立一个管程，并命名为 ProclucerCon
7、sumer，或简称为PC。其中包括两个 过程： (1) put(item)过程。生产者利用该过程将自己生 产的产品投放到缓冲池中，并用整型变量count来表 示在缓冲池中已有的产品数目，当countn时，表示 缓冲池已满，生产者须等待。 (2) get(item)过程。消费者利用该过程从缓冲池 中取出一个产品，当count0时，表示缓冲池中已无 可取用的产品，消费者应等待。 14 PC管程可描述如下： type producer-consumer=monitor Var in,out,count: integer； buffer: array0, , n-1 of item； notfull，
8、notempty:condition； procedure entry put(item) begin if count=n then notfull.wait； buffer(in):=nextp； in:=(in+1) mod n； count:=count+1； if notempty.queue then notempty.signal； end 15 procedure entry get(item) begin if count=1 then L :=L - 1; if mx =1 then mx :=mx - 0; /即mx值不变 L :=L + 1; 34 writer: re
9、peat Swait(mx,1,1;L,RN,0); writing operation; Ssignal(mx,1); until false ; if mx =1 and L =RN then mx:=mx - 1; L:=L-0; /即在读进程数不变 mx :=mx + 1; 35 Swait(mx,1,0)语句起着开关的作用。 只要无writer进程进入写，则mx=1，reader 进程就都可以进入读。一旦有writer进程进 入写时，mx=0，则任何reader进程就都无法 进入读。 Swait(mx,1,1,L,RN,0)语句表示：仅 当既是无writer进程在写（mx=1）、又无
10、 reader进程在读（L=RN）时，writer进程才 能进入临界区写。 36 有一座桥，桥上不允许两车交会，但允许同 方向（南/北方向）多辆车依次通行（即桥 上可以有多台同方向的车）。 请用wait、signal操作实现交通管理以防止桥 上堵塞。 37 分析： n桥上不允许两车相会，因此，桥应该被互 斥访问； n同一方向上允许多辆车依次通过，即临界 区允许多个进程访问，可以用一个信号量 mutex来互斥访问临界区。并且保证最多某 一方向上连续通过一定数量的（m台）车后 ，必须让另一方向上的车通过。 38 数据结构： Var mutex, avail-n, avail-s：semaphore
11、：= 0, m, m; /mutex是互斥信号量，用于实现对共享缓冲区 的互斥访问，初始值为1 /avail-n表示允许向北行的车辆数，初始值为m /avail-s表示允许向南行的车辆数，初始值为m 39 South: Begin wait(avail-s); wait(mutex); cross the bridge; signal(mutex); signal(avail-n); End North: Begin wait(avail-n); wait(mutex); cross the bridge; signal(mutex); signal(avail-s); End 40 n第二章习题： nP81-83 2、24、26、27、28 41
