B进程同步课件

1、1B进程同步PPT课件2B进程同步PPT课件程序（间）并发执行的特征：程序（间）并发执行的特征：3B进程同步PPT课件进程的同步进程的同步4B进程同步PPT课件进程的同步关系进程的同步关系5B进程同步PPT课件6B进程同步PPT课件进程间的同步关系（一）进程间的同步关系（一）7B进程同步PPT课件进程间的同步关系（二）进程间的同步关系（二）8B进程同步PPT课件进程间的同步关系（三）进程间的同步关系（三）9B进程同步PPT课件进程间的同步关系进程间的同步关系10B进程同步PPT课件两种形式的制约关系两种形式的制约关系11B进程同步PPT课件12B进程同步PPT课件同步实现初探（二）同步实现初探

2、（二）13B进程同步PPT课件同步实现初探（三）同步实现初探（三）14B进程同步PPT课件进程间的同步关系进程间的同步关系司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者15B进程同步PPT课件临界资源临界资源生产者消费者生产者消费者的同步问题的同步问题产品仓仓 库库 生产者生产者 消费者消费者 生产者把产品生产出来，送入仓库。生产者把产品生产出来，送入仓库。给消费者发信给消费者发信号号，消费者得到信号后，到仓库取产品，消费者得到信号后，到仓库取产品，取走产品后给生取走产品后给生产者发信号产者发信号16B进程同步PPT课件 如果生产者和消费者共享的缓冲池容量为可以存如果

3、生产者和消费者共享的缓冲池容量为可以存放放n n件物品件物品(n1)(n1)。 由于缓冲器可存由于缓冲器可存n n件物品件物品, ,因此因此, ,必须指出缓冲器必须指出缓冲器中什么位置已有物品可供消费中什么位置已有物品可供消费, ,什么位置尚无物品可什么位置尚无物品可供生产者存放物品。可以用供生产者存放物品。可以用输入指针输入指针inin和和输出指针输出指针outout分别指示分别指示生产者往缓冲器存物品生产者往缓冲器存物品和和消费者从缓冲消费者从缓冲器取物品器取物品的相对位置的相对位置, ,它们的它们的初值为初值为0 0, ,生产者和消费生产者和消费者按位置的顺序去存物品和取物品，缓冲池被循

4、环者按位置的顺序去存物品和取物品，缓冲池被循环使用。使用。 每当生产进程生产并投放一个产品后，输入指针每当生产进程生产并投放一个产品后，输入指针加加 1 1 ， 由 于 缓 冲 池 循 环 使 用 ， 可 表 示 为 ：， 由 于 缓 冲 池 循 环 使 用 ， 可 表 示 为 ： in:=(in+1)mod n ;in:=(in+1)mod n ; 每当消费者进程取走一个产品后，输出指针加每当消费者进程取走一个产品后，输出指针加1 1，由于缓冲池循环使用，可表示为：由于缓冲池循环使用，可表示为：out:=(out+1)mod out:=(out+1)mod n ;n ;17B进程同步PPT课

5、件 当当(in+1)mod n =out (in+1)mod n =out 时，时，表示缓冲池满表示缓冲池满； 当当in = out in = out 时时 , ,表示缓冲池空表示缓冲池空； 整型变量整型变量countercounter表示表示缓冲池中产品的个数缓冲池中产品的个数，初值为初值为0 0； n o - o pn o - o p 是 一 条 空 操 作 指 令是 一 条 空 操 作 指 令 ， w h i l e w h i l e condition do no-opcondition do no-op语句表示重复测试条件语句表示重复测试条件（condicition),condic

6、ition),直至条件为直至条件为false(false(假假) )。 局部变量局部变量nextpnextp: :生产者用于暂时存放刚生产者用于暂时存放刚生产出的产品；生产出的产品； 局部变量局部变量nextcnextc: :消费者暂时存放要消费的消费者暂时存放要消费的产品；产品；18B进程同步PPT课件Var n , integer ;type item=var buffer : array0,1,n-1 of itemin , out : 0, 1 , , n-1;counter : 0, 1, , n ;producer: repeatproduce an item in nextp;w

7、hile counter = n do no-op;bufferin : =nextp;in : =(in+1)mod n ;counter : =counter+1 ;until false;consumer: repeatwhile counter = 0 do no-op;nextc : =bufferout ;out : =(out+1)mod n ;counter : =counter-1 ;consumer the item in nextc;until false;19B进程同步PPT课件 上述两个操作用机器语言实现时，可用下面的上述两个操作用机器语言实现时，可用下面的形式描述：

8、形式描述：register1 : = counter ;register1 : = register1 + 1 ;counter : = register1 ;register2 : = counter;register2 : = register2 - 1 ;counter : = register2 ;各进程如何互斥使用临界资源？20B进程同步PPT课件临界区临界区21B进程同步PPT课件 repeatrepeat entry section entry section critical section; critical section; exit section exit sectio

9、n remainder section; remainder section; until false; until false;22B进程同步PPT课件临界区临界区23B进程同步PPT课件同步四原则同步四原则24B进程同步PPT课件同步原则同步原则25B进程同步PPT课件同步原则同步原则26B进程同步PPT课件锁机制锁机制27B进程同步PPT课件锁机制锁机制28B进程同步PPT课件锁机制实现锁机制实现29B进程同步PPT课件锁机制实现锁机制实现30B进程同步PPT课件锁操作模型锁操作模型31B进程同步PPT课件出了问题的锁出了问题的锁32B进程同步PPT课件锁机制实现锁机制实现33B进程同步

10、PPT课件2.3.2 信号量机制信号量机制wait(S): while S=0 do no-op S:=S-1;signal(S): S:=S+1;34B进程同步PPT课件经典信号量经典信号量35B进程同步PPT课件P原语操作和原语操作和V原语操作原语操作36B进程同步PPT课件入口s=s-1s0调度进程入等待队列转进程调度返回s.否value 0) 继续运行；继续运行； else 唤醒等待队列中的唤醒等待队列中的一个进程，并继续运行；一个进程，并继续运行；信号量：信号量： PV操作操作38B进程同步PPT课件记录型信号量记录型信号量39B进程同步PPT课件记录型信号量的记录型信号量的P，V操

11、作操作40B进程同步PPT课件P(s)和和V(s)操作原语操作原语void P(s) struct semaphore s; s.value=s.value-1; if (s.value1)(n1)。 由于缓冲器可存由于缓冲器可存n n件物品件物品, ,因此因此, ,必须指出缓冲器必须指出缓冲器中什么位置已有物品可供消费中什么位置已有物品可供消费, ,什么位置尚无物品可什么位置尚无物品可供生产者存放物品。可以用供生产者存放物品。可以用输入指针输入指针inin和和输出指针输出指针outout分别指示分别指示生产者往缓冲器存物品生产者往缓冲器存物品和和消费者从缓冲消费者从缓冲器取物品器取物品的相对

12、位置的相对位置, ,它们的它们的初值为初值为0 0, ,生产者和消费生产者和消费者按位置的顺序去存物品和取物品，缓冲池被循环者按位置的顺序去存物品和取物品，缓冲池被循环使用。使用。 每当生产进程生产并投放一个产品后，输入指针每当生产进程生产并投放一个产品后，输入指针加加 1 1 ， 由 于 缓 冲 池 循 环 使 用 ， 可 表 示 为 ：， 由 于 缓 冲 池 循 环 使 用 ， 可 表 示 为 ： in:=(in+1)mod n ;in:=(in+1)mod n ; 每当消费者进程取走一个产品后，输出指针加每当消费者进程取走一个产品后，输出指针加1 1，由于缓冲池循环使用，可表示为：由于缓

13、冲池循环使用，可表示为：out:=(out+1)mod out:=(out+1)mod n ;n ;64B进程同步PPT课件 当当(in+1)mod n =out (in+1)mod n =out 时，时，表示缓冲池满表示缓冲池满； 当当in = out in = out 时时 , ,表示缓冲池空表示缓冲池空； 局部变量局部变量nextpnextp: :生产者用于暂时存放刚生产者用于暂时存放刚生产出的产品；生产出的产品； 局部变量局部变量nextcnextc: :消费者暂时存放要消费的消费者暂时存放要消费的产品；产品；65B进程同步PPT课件生产者消费者问题生产者消费者问题66B进程同步PPT

14、课件生产者消费者算法分析生产者消费者算法分析67B进程同步PPT课件生产者消费者算法分析生产者消费者算法分析68B进程同步PPT课件利用记录型信号量实现利用记录型信号量实现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; endconsumer : begin repeat P( full ); P( mutex ); nextc :=buffer(

15、out); out :=(out+1) mod n; V( mutex ); V(empty); consumer the item in nextc;Until false;end69B进程同步PPT课件 P P操作的顺序是很重要的操作的顺序是很重要的, ,如果把生产者和如果把生产者和消费者进程中的两个消费者进程中的两个P P操作交换顺序操作交换顺序, ,则会导则会导致错误。而致错误。而V V操作的顺序却是无关紧要的。一操作的顺序却是无关紧要的。一般来说般来说, ,用于同步的信号量上的用于同步的信号量上的P P操作在前执操作在前执行行, ,而用于互斥的信号量上的而用于互斥的信号量上的P P操

16、作在后执行。操作在后执行。70B进程同步PPT课件利用利用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 )

17、;71B进程同步PPT课件生产者消费者算法小结生产者消费者算法小结72B进程同步PPT课件73B进程同步PPT课件Var mutex1, mutex2, empty, full, count: semaphore; mutex1:=1; mutex2:=1; empty:=10; full:=0; count:=3;process 小和尚: begin repeat P(empty); P(count); P(mutex1); 从井中取水； V(mutex1); P(mutex2); 送水入水缸； V(mutex2); V(count); V(full); until false; endprocess 老和尚: begin repeat P(full); P(count); P(mutex2); 从缸中取水； V(mutex2); V(empty); V(count); until false; end74B进程同步PPT课件75B进程同步PPT课件76B进程同步PPT课件读者写者问题读者写者问题77B进