计算机操作系统(第四版)第二章进程同步.pptVIP

* 如果生产者和消费者共享的缓冲池容量为可以存放n件物品(n1)。 由于缓冲器可存n件物品,因此,必须指出缓冲器中什么位置已有物品可供消费,什么位置尚无物品可供生产者存放物品。可以用输入指针in和输出指针out分别指示生产者往缓冲器存物品和消费者从缓冲器取物品的相对位置,它们的初值为0,生产者和消费者按位置的顺序去存物品和取物品，缓冲池被循环使用。 每当生产进程生产并投放一个产品后，输入指针加1，由于缓冲池循环使用，可表示为： in:=(in+1)mod n ; 每当消费者进程取走一个产品后，输出指针加1，由于缓冲池循环使用，可表示为：out:=(out+1)mod n ; * 当(in+1)mod n =out 时，表示缓冲池满； 当in = out 时 ,表示缓冲池空； 局部变量nextp:生产者用于暂时存放刚生产出的产品； 局部变量nextc:消费者暂时存放要消费的产品； * 生产者消费者问题 生产者生产的产品放入缓冲池内； 消费者从缓冲池内取走产品消费； 消费者消费后的空白缓冲区供生产者使用。 规则： 有空的buffer时生产者便可将产品送入缓冲池。 有满的buffer时消费者可从中取走产品。 消费者与生产者互斥地访问缓冲区。 * 生产者消费者算法分析 算法分析 两类进程：生产者进程和消费者进程 （1）进程间的关系 生产者生产产品后消费者消费 消费者消费后的空白缓冲块由生产者存放产品 两个进程在使用缓冲区时的关系 合作关系 互斥关系 * 生产者消费者算法分析 信号量 full：缓冲池中满缓冲区的数量 empty：缓冲池中空缓冲区的数量 mutex：实现各进程对缓冲池的互斥使用 * 利用记录型信号量实现 Var mutex,empty,full :semaphore :=1,n,0 ; buffer : array [0,……,n-1] of item ; in , out : integer := 0, 0 producer : begin repeat produce an item nextp; P( empty ); P( mutex ); Buffer( in ) :=nextp; In :=(in+1) mod n; V( mutex ); V( full ); Until false; end consumer : begin repeat P( full ); P( mutex ); nextc :=buffer( out); out :=(out+1) mod n; V( mutex ); V(empty); consumer the item in nextc; Until false; end * P操作的顺序是很重要的,如果把生产者和消费者进程中的两个P操作交换顺序,则会导致错误。而V操作的顺序却是无关紧要的。一般来说,用于同步的信号量上的P操作在前执行,而用于互斥的信号量上的P操作在后执行。 * 利用AND型信号量实现 Producer: produce an item nextp; P(empty,mutex) Buffer(in) :=nextp; In :=(in+1) mod n; V(mutex,full); consumer : P(full, mutex); nextc := buffer(out); out :=(out+1) mod n; V(mutex,empty); Consumer the item in nextc; 用P(empty,mutex)代替p(empty); 和　　　　p( mutex ); * 生产者消费者算法小结 小结： 在分析进程同步问题中，逐个分析进程间的关系是关键 不管多复杂的关系，总能归结为两种基本关系（竞争与合作），总是这两种关系的组合 不管公用还是私用，信号量的使用必须成对出现 * 和尚打水问题 某寺庙有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一井水。水井狭窄，每次只能容一个桶取水。水桶总数为3个