操作系统课件os02进程同步.ppt

操作系统操作系统Operating SystemsWINDOWSWINDOWSUNIXUNIXLINUXLINUXOS2OS2VxWorksVxWorksMac OSMac OS2.3 进进 程程 同同 步步 进程同步的基本概念进程同步的基本概念 两种形式的制约关系两种形式的制约关系间接相互制约关系。间接相互制约关系。p间接相互制约源于资源共享间接相互制约源于资源共享直接相互制约关系。直接相互制约关系。p主要源于进程间的合作。主要源于进程间的合作。进程的同步与互斥进程的同步与互斥进程的两大关系：进程的两大关系：互斥（间接制约关系）：互斥（间接制约关系）：各进程竞争使用同一临界资源各进程竞争使用同一临界资源p临界资源：一次只允许一个进程使用的系统资临界资源：一次只允许一个进程使用的系统资源源进程同步（直接制约关系）：进程同步（直接制约关系）：根据一定的根据一定的时序关系时序关系合作完成一项任务合作完成一项任务为完成共同任务的并发进程基于为完成共同任务的并发进程基于某个条件某个条件来协调其来协调其活动活动生产者生产者-消费者问题消费者问题 生产者生产者-消费者消费者(producer-consumer)问题是一个著名的问题是一个著名的进程同步问题。进程同步问题。123.nPC生产者生产者-消费者问题消费者问题producer:repeat produce an item in nextp;while counter=n do no-op;bufferin:=nextp;in:=(in+1)mod n;counter:=counter+1;until falseconsumer:repeat while counter=0 do no-op;nextc:=bufferout;out:=(out+1)mod n;counter:=counter-1;consumer the item in nextc;until false;生产者生产者-消费者问题消费者问题counter:=counter+1：register1:=counter；register1:=register1+1；counter:=register1；counter:=counter-1：register2:=counter；register2:=register2-1；counter:=register2；生产者生产者-消费者问题消费者问题生产者进程生产者进程:/counter初始值初始值=5 register1:=counter；register1:=register1+1；counter:=register1；消费者进程消费者进程 register2:=counter;register2:=register2-1;counter:=register2；;程序的执行已经失去了再现性。程序的执行已经失去了再现性。解决此问题的关键是应把变量解决此问题的关键是应把变量counter作为临界资源处理，作为临界资源处理，令生产者进程和消费者进程互斥地访问变量令生产者进程和消费者进程互斥地访问变量counter。5 5register1register15 5register2register24 46 65 5counter4 46 6临界区临界区把在每个进程中访问把在每个进程中访问临界资源临界资源的那段代码称为临界区的那段代码称为临界区若能保证诸进程互斥地进入自己的临界区，便可实现诸进若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。程对临界资源的互斥访问。repeatentry section（进入区）（进入区）critical section；exit section（退出区）（退出区）remainder section；until false；临界区临界区同步机制应遵循的规则同步机制应遵循的规则1.空闲让进。空闲让进。2.忙则等待。忙则等待。3.有限等待。有限等待。4.让权等待。让权等待。信号量机制信号量机制1 整型信号量整型信号量定义为一个用于表示定义为一个用于表示资源数目资源数目的的整型整型量量S仅仅能能通通过过两两个个标标准准的的原原子子操操作作P操操作作(wait)和和V操操作作(signal)来访问。来访问。wait(S)：while S=0 do no-op；S:=S-1；signal(S)：S:=S+1；S S2 记录型信号量记录型信号量记录型信号量机制是一种不存在记录型信号量机制是一种不存在“忙等忙等”现象的进程同步现象的进程同步机制。机制。增加一个进程链表指针增加一个进程链表指针L用于链接上述的所有等待进程。用于链接上述的所有等待进程。记录型信号量采用了记录型的数据结构：记录型信号量采用了记录型的数据结构：type semaphore=recordvalue:integer；L:list of process；end 信号量的值信号量的值 value 信号量队列指针信号量队列指针申请一个单位资源：申请一个单位资源：procedure wait(S)var S：semaphore；begin S.value:=S.value-1；if S.value0 then block(S.L)；end 释放一个单位资源：释放一个单位资源：procedure signal(S)var S:semaphore；Begin S.value:=S.value+1；if S.value=1 and and Sn=1 thenfor i:=1 to n do Si:=Si-1；endforelse 当发现第一个当发现第一个 Si1就把该进程放入等待队列，就把该进程放入等待队列，并将其指令计数器置于并将其指令计数器置于Swait操作的开始位置操作的开始位置endifSsignal(S1，S2，Sn)for i:=1 to n doSi:=Si+1；Remove all the process waiting in the queue associated with Si into the ready queue.endfor；2.3.3 信号量的应用信号量的应用利用信号量实现进程互斥利用信号量实现进程互斥 Var mutex:semaphore=1;begin parbegin process 1:begin repeat wait(mutex);critical section；signal(mutex);remainder section;until false;endprocess 2:begin repeat wait(mutex);critical section;signal(mutex);remainder section；until false;Endparend mutex10 NULL-12.3.4 2.3.4 管程机制管程机制管程引入管程引入把分散在各进程中的临界区集中起来进行管理把分散在各进程中的临界区集中起来进行管理 ；防止进程有意或无意的违法同步操作防止进程有意或无意的违法同步操作可可利利用用共共享享数数据据结结构构抽抽象象地地表表示示共共享享资资源源，把把对对共共享享数数据据结构实施的操作定义为结构实施的操作定义为一组过程一组过程进进程程对对共共享享资资源源的的操操作作，都都是是通通过过这这组组过过程程对对共共享享数数据结构的操作来实现的据结构的操作来实现的确保每次仅有一个进程使用共享资源确保每次仅有一个进程使用共享资源管程的定义管程的定义一个管程定义了一个一个管程定义了一个数据结构数据结构和能为并发进程所执行和能为并发进程所执行(在在该数据结构上该数据结构上)的的一组操作一组操作，这组操作能同步进程和改变，这组操作能同步进程和改变管程中的数据。管程中的数据。管程的组成管程的组成1.1.名称；名称；2.2.局部于管程内部的共享数据结构说明；局部于管程内部的共享数据结构说明；3.3.对该数据结构进行操作的一组过程；对该数据结构进行操作的一组过程；4.4.对局部于管程内部的共享数据设置初始值语句。对局部于管程内部的共享数据设置初始值语句。管程的示意图管程的示意图 condition c1condition c1wait(c1)wait(c1)condition ccondition cn n wait(c wait(cn n)局部数据局部数据 条件变量条件变量 过程过程/函数函数1 1 过程过程/函数函数k k出口出口 初始化代码初始化代码入口入口管程管程等待调用过程等待调用过程的进程队列的进程队列管程等待区管程等待区管程的条件变量管程的条件变量条件变量条件变量出现在管程内的一种数据结构出现在管程内的一种数据结构 Var xVar x，y y：conditioncondition只有在管程中才能被访问只有在管程中才能被访问它对管程内的所有过程是全局的它对管程内的所有过程是全局的只能通过两个原语操作只能通过两个原语操作waitwait和和signalsignal来控制它。来控制它。x.waitx.wait正在调用管程的进程因正在调用管程的进程因x x条件需要被阻塞或挂起时调用条件需要被阻塞或挂起时调用x.waitx.wait：将自己插入到将自己插入到x x条件的等待队列上并释放管程，条件的等待队列上并释放管程，直到直到x x条件变化。条件变化。此时其它进程可以使用该管程。此时其它进程可以使用该管程。x.signalx.signal正在调用管程的进程发现正在调用管程的进程发现x x条件发生了变化，则调用条件发生了变化，则调用x.signalx.signal重新启动一个因重新启动一个因x x条件而阻塞或挂起的进程。条件而阻塞或挂起的进程。这与信号量机制中的这与信号量机制中的signalsignal操作不同。操作不同。若进程若进程Q Q因因x x条件阻塞，而正在调用管程的进程条件阻塞，而正在调用管程的进程P P执行执行x.signalx.signal操作后，操作后，Q Q被重新启动，可采用下述两种方式之被重新启动，可采用下述两种方式之一进行处理：一进行处理：P P等待，直至等待，直至Q Q离开管程或等待另一条件。离开管程或等待另一条件。Q Q等待，直至等待，直至P P离开管程或等待另一条件。离开管程或等待另一条件。管程主要特性管程主要特性模块化模块化基本程序单位，可以单独编译；基本程序单位，可以单独编译；抽象数据类型抽象数据类型包含数据和操作；包含数据和操作；信息隐蔽信息隐蔽从外部看不到内部信息；从外部看不到内部信息；管程和进程不同管程和进程不同管程定义的是公共数据结构；管程定义的是公共数据结构；进程定义的是私有数据结构进程定义的是私有数据结构PCBPCB管程把共享变量上的同步操作集中起来管程把共享变量上的同步操作集中起来临界区却分散在每个进程中；临界区却分散在每个进程中；管程的设置则是解决共享资源的互斥使用问题管程的设置则是解决共享资源的互斥使用问题设置进程的目的在于实现系统的并发性；设置进程的目的在于实现系统的并发性；进程通过调用管程中的过程对共享数据结构实行操作进程通过调用管程中的过程对共享数据结构实行操作管程为被动工作方式，进程则为主动工作方式；管程为被动工作方式，进程则为主动工作方式；管程和进程不同（续）管程和进程不同（续）管程不能与其调用者并发管程不能与其调用者并发进程之间能并发执行；进程之间能并发执行；管程是操作系统中的一个资源管理模块，供进程调用。管程是操作系统中的一个资源管理模块，供进程调用。进程具有动态性，由进程具有动态性，由“创建创建”而诞生，由而诞生，由“撤销撤销”而而消亡消亡2.4 经典进程的同步问题经典进程的同步问题 2.4.1 生产者生产者消费者问题消费者问题生产者生产者消费者问题是相互合作的进程关系的一种抽象消费者问题是相互合作的进程关系的一种抽象制约关系：制约关系：只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息只要缓冲池未空，消费者便可从缓冲池中取走一个消息123.nPC信号量解决生产者消费者问题信号量解决生产者消费者问题用信号量及用信号量及P、V操作解决进程间同步问题操作解决进程间同步问题 一个生产者、一个消费者共享一个生产者、一个消费者共享一个一个缓冲区缓冲区多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区一个生产者、一个消费者共享一个缓一个生产者、一个消费者共享一个缓冲区的解冲区的解int B;semaphore empty;/可以使用的空缓冲区数可以使用的空缓冲区数semaphore full;/缓冲区内可以使用的产品数缓冲区内可以使用的产品数empty=1;/缓冲区内允许放入一件产品缓冲区内允许放入一件产品full=0;/缓冲区内没有产品缓冲区内没有产品一一个个缓缓冲冲区区一一 个个生生 产产者者生生 产产 一一个产品个产品取取 出出 一一个产品个产品一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享一个缓冲区cobeginprocess producer()process consumer()while(true)while(true)produce();P(empty);append()to B;V(full);coendEmptyfull空 1不满 0 0满 1无缓冲区 -1空 -1P(full);V(empty);consume();take()from B;一组生产者，一组消费者，公用一组生产者，一组消费者，公用n个环形缓冲区个环形缓冲区利用记录型信号量解决生产者利用记录型信号量解决生产者消费者问题消费者问题Var buffer:array0,n-1 of item;inin，out:integer:=0,0;/out:integer:=0,0;/放入、取出缓冲区指针放入、取出缓冲区指针mutex:semaphore:=1；empty:semaphore:=n;/可以使用的空缓冲区数可以使用的空缓冲区数full:semaphore:=0;/缓冲区内可以使用的产品数缓冲区内可以使用的产品数123.nP1P2P3.Pm.C1C2C3.Ck生产者生产者/消费者、共享多个缓冲区的解消费者、共享多个缓冲区的解 parbeginProceducer_i:begin repeat produce an item nextp;wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)mod n;signal(mutex);signal(full);until false;endparendparendConsumer_j:begin repeat wait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)mod n;signal(mutex);signal(empty)；consumer the item in nextc;until false;end parend end 永远等待永远等待cobegincobeginprocess producer_i()process producer_i()while(true)while(true)produce();produce();P(mutex);P(mutex);P(empty);P(empty);append to Bin;append to Bin;in=(in+1)%k;in=(in+1)%k;V(mutex);V(mutex);V(full);V(full);coendcoendprocess consumer_j()while(true)P(full);P(mutex);take()from Bout;out=(out+1)%k;V(mutex);V(empty);consume();emptyfull0kMutex=1Mutex=0-1信号量及信号量及P、V操作讨论操作讨论P、V操作必须成对出现操作必须成对出现当为互斥操作时，它们处于同一进程当为互斥操作时，它们处于同一进程当为同步操作时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现如果如果P(S1)和和P(S2)两个操作在一起，那么两个操作在一起，那么P操作的顺序至操作的顺序至关重要关重要一个同步一个同步P操作与一个互斥操作与一个互斥P操作在一起时，同步操作在一起时，同步P操作操作在互斥在互斥P操作前操作前两个两个V操作无关紧要操作无关紧要哲学家进餐问题哲学家进餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把筷子。每个哲学人面前有一只空盘子，每两人之间放一把筷子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两只筷子，且每人只能直接从自己左边或右边去取须获得两只筷子，且每人只能直接从自己左边或右边去取筷子筷子 解决思路解决思路5位哲学家看作位哲学家看作5个进程个进程筷子是临界资源，在一段时间内只允许一位哲学家使用筷子是临界资源，在一段时间内只允许一位哲学家使用可以用一个信号量表示一只筷子可以用一个信号量表示一只筷子由这五个信号量构成信号量数组。其描述如下：由这五个信号量构成信号量数组。其描述如下：Var chopstick:array0，4 of semaphore；所有信号量均被初始化为所有信号量均被初始化为1用记录型信号量解决哲学家进餐问题用记录型信号量解决哲学家进餐问题第第i位哲学家的活动可描述为：位哲学家的活动可描述为：repeat wait(chopsticki)；wait(chopstick(i+1)mod 5)；eat；signal(chopsticki)；signal(chopstick(i+1)mod 5)；think；until false；分析分析上述解法可保证不会有两个相邻的哲学家同时进餐上述解法可保证不会有两个相邻的哲学家同时进餐问题问题有可能引起死锁有可能引起死锁可能出现永远等待可能出现永远等待有若干种办法可避免这类死锁有若干种办法可避免这类死锁至多允许四个哲学家同时吃；至多允许四个哲学家同时吃；奇数号先取左手边的筷子，偶数号先取右手边的筷子；奇数号先取左手边的筷子，偶数号先取右手边的筷子；每个哲学家取到手边的两把筷子才吃，否则一把筷子也不每个哲学家取到手边的两把筷子才吃，否则一把筷子也不取。取。本质上就是本质上就是AND同步问题同步问题用用AND信号量机制可获得最简洁的解法。信号量机制可获得最简洁的解法。利用利用AND信号量机制解决哲学家进餐问题信号量机制解决哲学家进餐问题Var chopsiick array of semaphore:=(1,1,1,1,1)；processirepeatthink；Swait(chopstick(i+1)mod 5，chopsticki)；eat；Ssignal(chopstick(i+1)mod 5，chopsticki)；until false；读者读者-写者问题写者问题有两组并发进程：有两组并发进程：读者和写者读者和写者共享一个文件共享一个文件F，要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作只允许一个写者执行写操作只允许一个写者执行写操作不允许任意一个写者和其他读者或其他写者同时访问不允许任意一个写者和其他读者或其他写者同时访问文件文件读者读者-写者问题：解决思路写者问题：解决思路为解决为解决Reader与与Writer进程间互斥进程间互斥设置信号量设置信号量Wmutex表示是否允许写的，初值为表示是否允许写的，初值为1读者读者-写者问题：解决思路写者问题：解决思路设置一个整型变量设置一个整型变量Readcount表示正在读的进程数目表示正在读的进程数目初值为初值为0Readcount是一个可被多个是一个可被多个Reader进程访问的临界资源进程访问的临界资源为它设置一个互斥信号量为它设置一个互斥信号量rmutex初值为初值为1parbeginReader:begin repeatwait(rmutex)；if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 then signal(wmutex)；/最后一个读者离开时通知写者最后一个读者离开时通知写者 signal(rmutex)；until false；endparendwriter:beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；EndparbeginReader:begin repeatwait(rmutex)；if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 then signal(wmutex)；/最后一个读者离开时通知写者最后一个读者离开时通知写者 signal(rmutex)；until false；endparendwriter:beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；EndparbeginReader:begin repeatwait(rmutex)；if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 then signal(wmutex)；/最后一个读者离开时通知写者最后一个读者离开时通知写者 signal(rmutex)；until false；endparendwriter:beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End苹果桔子问题苹果桔子问题苹果桔子问题苹果桔子问题桌上有一只盘子，每次只能放入桌上有一只盘子，每次只能放入一只一只水果；爸爸专向盘水果；爸爸专向盘子中放苹果，妈妈专向盘子中放桔子；一个儿子专等吃子中放苹果，妈妈专向盘子中放桔子；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果盘子中的桔子，一个女儿专等吃盘子里的苹果苹果桔子问题苹果桔子问题解决思路：解决思路：生产者消费者问题的变形，有两类生产者和两类消费者生产者消费者问题的变形，有两类生产者和两类消费者互斥：互斥：盘子盘子同步同步：爸爸和女儿；爸爸和女儿；妈妈和儿子妈妈和儿子进程数目进程数目分析分析设置设置3个信号量个信号量empty表示盘子能放的水果数目，初值为表示盘子能放的水果数目，初值为1full_o表示盘子里有无桔子，初值为表示盘子里有无桔子，初值为0 full_a表示盘子里有无苹果，初值为表示盘子里有无苹果，初值为0 empty,full_o,full_a:semaphore;empty:=1;full_o:=0;full_a:=0;process father begin L1:削一个苹果；削一个苹果；P(empty);放苹果放苹果;V(full_a);goto L1;end;process mother begin L2:剥一个桔子；剥一个桔子；P(empty);放桔子；放桔子；V(full_o);goto L2;end;process daughter process daughter beginbegin L4:L4:P(P(full_a););取苹果；取苹果；取苹果；取苹果；V(V(empty););吃苹果；吃苹果；吃苹果；吃苹果；goto L4;goto L4;end;end;process son process son beginbegin L3:P(L3:P(full_o););取桔子；取桔子；取桔子；取桔子；V(V(empty););吃桔子；吃桔子；吃桔子；吃桔子；goto L3;goto L3;end;end;问题问题可以放可以放n个水果？个水果？empty表示盘子能放的水果数目，初值为表示盘子能放的水果数目，初值为nfull_o表示盘子里有无桔子，初值为表示盘子里有无桔子，初值为0 full_a表示盘子里有无苹果，初值为表示盘子里有无苹果，初值为0 mutex对盘子的互斥访问对盘子的互斥访问,初值为初值为1empty,full_o,full_a，mutext:semaphore;empty:=n;full_o:=0;full_a:=0;mutex=1process father begin L1:削一个苹果；削一个苹果；P(empty);P(mutex);放苹果放苹果;V(mutex);V(full_a);goto L1;end;process daughter process daughter beginbegin L4:L4:P(P(full_a););P(mutex);取苹果；取苹果；取苹果；取苹果；V(mutex);V(V(empty););吃苹果；吃苹果；吃苹果；吃苹果；goto L4;goto L4;end;end;process mother Begin L2:剥一个桔子；剥一个桔子；P(empty);P(mutex);放桔子；放桔子；V(mutex);V(full_o);goto L2;end;process son process son beginbegin L3:L3:P(P(full_o););P(mutex);取桔子；取桔子；取桔子；取桔子；V(mutex);V(V(empty););吃桔子；吃桔子；吃桔子；吃桔子；goto L3;goto L3;end;end;作业作业P82-83 24 26 27 28