第二章—B 进程同步

1、12程序（间）并发执行的特征：程序（间）并发执行的特征：3进程的同步进程的同步4进程的同步关系进程的同步关系56进程间的同步关系（一）进程间的同步关系（一）7进程间的同步关系（二）进程间的同步关系（二）8进程间的同步关系（三）进程间的同步关系（三）9进程间的同步关系进程间的同步关系10两种形式的制约关系两种形式的制约关系12同步实现初探（二）同步实现初探（二）13同步实现初探（三）同步实现初探（三）14进程间的同步关系进程间的同步关系司机与售票员司机与售票员多个打印者多个打印者计算者与打印者计算者与打印者15临界资源临界资源生产者消费者生产者消费者的同步问题的同步问题产品仓仓 库库 生产者生产

2、者 消费者消费者 生产者把产品生产出来，送入仓库。生产者把产品生产出来，送入仓库。给消费者发信给消费者发信号号，消费者得到信号后，到仓库取产品，消费者得到信号后，到仓库取产品，取走产品后给生取走产品后给生产者发信号产者发信号16 如果生产者和消费者共享的缓冲池容量为可以存如果生产者和消费者共享的缓冲池容量为可以存放放n n件物品件物品(n1)(n1)。 由于缓冲器可存由于缓冲器可存n n件物品件物品, ,因此因此, ,必须指出缓冲器必须指出缓冲器中什么位置已有物品可供消费中什么位置已有物品可供消费, ,什么位置尚无物品可什么位置尚无物品可供生产者存放物品。可以用供生产者存放物品。可以用输入指针

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

4、=(in+1)mod n ; 每当消费者进程取走一个产品后，输出指针加每当消费者进程取走一个产品后，输出指针加1 1，由于缓冲池循环使用，可表示为：由于缓冲池循环使用，可表示为：out:=(out+1)mod out:=(out+1)mod n ;n ;17 当当(in+1)mod n =out (in+1)mod n =out 时，时，表示缓冲池满表示缓冲池满； 当当in = out in = out 时时 , ,表示缓冲池空表示缓冲池空； 整型变量整型变量countercounter表示表示缓冲池中产品的个数缓冲池中产品的个数，初值为初值为0 0； n o - o pn o - o p 是

5、 一 条 空 操 作 指 令是 一 条 空 操 作 指 令 ， w h i l e w h i l e condition do no-opcondition do no-op语句表示重复测试条件语句表示重复测试条件（condicitioncondicition),),直至条件为直至条件为false(false(假假) )。 局部变量局部变量nextpnextp: :生产者用于暂时存放刚生产者用于暂时存放刚生产出的产品；生产出的产品； 局部变量局部变量nextcnextc: :消费者暂时存放要消费的消费者暂时存放要消费的产品；产品；18Var n , integer ;type item=va

6、r buffer : array0,1,n-1 of itemin , out : 0, 1 , , n-1;counter : 0, 1, , n ;producer: repeatproduce an item in nextp;while 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 ;c

7、ounter : =counter-1 ;consumer the item in nextc;until false;19 上述两个操作用机器语言实现时，可用下面的上述两个操作用机器语言实现时，可用下面的形式描述：形式描述：register1 : = counter ;register1 : = register1 + 1 ;counter : = register1 ;register2 : = counter;register2 : = register2 - 1 ;counter : = register2 ;各进程如何互斥使用临界资源？20临界区临界区21 repeatrepeat

8、entry section entry section critical section; critical section; exit section exit section remainder section; remainder section; until false; until false;22临界区临界区23同步四原则同步四原则24同步原则同步原则25同步原则同步原则26锁机制锁机制27锁机制锁机制28锁机制实现锁机制实现29锁机制实现锁机制实现30锁操作模型锁操作模型31出了问题的锁出了问题的锁32锁机制实现锁机制实现332.3.2 信号量机制信号量机制wait(S): wh

9、ile S=0 do no-op S:=S-1;signal(S): S:=S+1;34经典信号量经典信号量35P原语操作原语操作和和V原语操作原语操作36入口s=s-1s0调度进程入等待队列转进程调度返回s.否value 0) 继续运行；继续运行； else 唤醒等待队列中的唤醒等待队列中的一个进程，并继续运行；一个进程，并继续运行；信号量：信号量： PV操作操作38记录型信号量记录型信号量39记录型信号量的记录型信号量的P，V操作操作40P(s)和和V(s)操作原语操作原语void P(s) struct semaphore s; s.value=s.value-1; if (s.valu

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

11、当生产进程生产并投放一个产品后，输入指针每当生产进程生产并投放一个产品后，输入指针加加 1 1 ， 由 于 缓 冲 池 循 环 使 用 ， 可 表 示 为 ：， 由 于 缓 冲 池 循 环 使 用 ， 可 表 示 为 ： in:=(in+1)mod n ;in:=(in+1)mod n ; 每当消费者进程取走一个产品后，输出指针加每当消费者进程取走一个产品后，输出指针加1 1，由于缓冲池循环使用，可表示为：由于缓冲池循环使用，可表示为：out:=(out+1)mod out:=(out+1)mod n ;n ;64 当当(in+1)mod n =out (in+1)mod n =out 时，时

12、，表示缓冲池满表示缓冲池满； 当当in = out in = out 时时 , ,表示缓冲池空表示缓冲池空； 局部变量局部变量nextpnextp: :生产者用于暂时存放刚生产者用于暂时存放刚生产出的产品；生产出的产品； 局部变量局部变量nextcnextc: :消费者暂时存放要消费的消费者暂时存放要消费的产品；产品；65生产者消费者问题生产者消费者问题66生产者消费者算法分析生产者消费者算法分析67生产者消费者算法分析生产者消费者算法分析68利用记录型信号量实现利用记录型信号量实现Var mutex,empty,full :semaphore :=1,n,0 ; buffer : array

13、 0,n-1 of item ; in , out : integer := 0, 0producer : 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( out); out :=(out+1) mod n; V( mutex ); V(em

14、pty); consumer the item in nextc;Until false;end69 P P操作的顺序是很重要的操作的顺序是很重要的, ,如果把生产者和如果把生产者和消费者进程中的两个消费者进程中的两个P P操作交换顺序操作交换顺序, ,则会导则会导致错误。而致错误。而V V操作的顺序却是无关紧要的。一操作的顺序却是无关紧要的。一般来说般来说, ,用于同步的信号量上的用于同步的信号量上的P P操作在前执操作在前执行行, ,而用于互斥的信号量上的而用于互斥的信号量上的P P操作在后执行。操作在后执行。70利用利用AND型信号量实现型信号量实现Producer: produce a

15、n 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 );71生产者消费者算法小结生产者消费者算法小结7273Var 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(m