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

1、操作系统操作系统Operating Systems2.3 进进 程程 同同 步步 进程同步的根本概念进程同步的根本概念 两种方式的制约关系两种方式的制约关系 间接相互制约关系。间接相互制约关系。 间接相互制约源于资源共享间接相互制约源于资源共享 直接相互制约关系。直接相互制约关系。 主要源于进程间的协作。主要源于进程间的协作。进程的同步与互斥进程的同步与互斥 进程的两大关系：进程的两大关系： 互斥间接制约关系：互斥间接制约关系： 各进程竞争运用同一临界资源各进程竞争运用同一临界资源 临界资源：一次只允许一个进程运用的系统资源临界资源：一次只允许一个进程运用的系统资源 进程同步直接制约关系：进程

2、同步直接制约关系： 根据一定的时序关系协作完成一项义务根据一定的时序关系协作完成一项义务 为完成共同义务的并发进程基于某个条件来协调其活动为完成共同义务的并发进程基于某个条件来协调其活动消费者消费者-消费者问题消费者问题 消费者消费者-消费者消费者(producer-consumer)问题是一个著名的问题是一个著名的进程同步问题。进程同步问题。123 . nPC消费者消费者-消费者问题消费者问题producer: repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=(in+1) mod

3、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：regist

4、er2:=counter；register2:=register2-1；counter:=register2； 消费者消费者-消费者问题消费者问题消费者进程消费者进程 counter初始值初始值=5 register1:=counter； register1:=register1+1； counter:=register1； 消费者进程消费者进程 register2:=counter; register2:=register2-1 ; counter:=register2； ;程序的执行曾经失去了再现性。程序的执行曾经失去了再现性。处理此问题的关键是应把变量处理此问题的关键是应把变量count

5、er作为临界资源处置，作为临界资源处置，令消费者进程和消费者进程互斥地访问变量令消费者进程和消费者进程互斥地访问变量counter。5 5register1register15 5register2register24 46 65 5counter4 46 6临界区临界区 把在每个进程中访问临界资源的那段代码称为临界区把在每个进程中访问临界资源的那段代码称为临界区 假设能保证诸进程互斥地进入本人的临界区，便可实现诸假设能保证诸进程互斥地进入本人的临界区，便可实现诸进程对临界资源的互斥访问。进程对临界资源的互斥访问。 repeat entry section进入区进入区 critical sec

6、tion； exit section退出区退出区 remainder section； until false； 临界区临界区同步机制应遵照的规那么同步机制应遵照的规那么 空闲让进。空闲让进。 忙那么等待。忙那么等待。 有限等待。有限等待。 让权等待。让权等待。 2.3.2信号量机制信号量机制1 整型信号量整型信号量定义为一个用于表示资源数目的整型量定义为一个用于表示资源数目的整型量S仅能经过两个规范的原子操作仅能经过两个规范的原子操作P操作操作(wait)和和V操作操作(signal)来访问。来访问。wait(S)： while S=0 do no-op； S:=S-1；signal(S)：

7、 S:=S+1； S S2 记录型信号量记录型信号量 记录型信号量机制是一种不存在记录型信号量机制是一种不存在“忙等景象的进程同步忙等景象的进程同步机制。机制。 添加一个进程链表指针添加一个进程链表指针L 用于链接上述的一切等待进程。用于链接上述的一切等待进程。 记录型信号量采用了记录型的数据构造：记录型信号量采用了记录型的数据构造： type semaphore=record value: integer； L: list of process； end 信号量的值信号量的值 value value 信号量队列指针信号量队列指针恳求一个单位资源：procedure wait(S)var S：

8、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(

9、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; unti

10、l false; endprocess 2: begin repeat wait(mutex); critical section; signal(mutex); remainder section； until false;Endparend mutex10 NULL-12.3.4 2.3.4 管程机制管程机制 管程引入管程引入 把分散在各进程中的临界区集中起来进展管理把分散在各进程中的临界区集中起来进展管理 ； 防止进程有意或无意的违法同步操作防止进程有意或无意的违法同步操作 可利用共享数据构造笼统地表示共享资源，把对共享数据可利用共享数据构造笼统地表示共享资源，把对共享数据构造实施的操作

11、定义为一组过程构造实施的操作定义为一组过程 进程对共享资源的操作，都是经过这组过程对共享数据构进程对共享资源的操作，都是经过这组过程对共享数据构造的操作来实现的造的操作来实现的 确保每次仅有一个进程运用共享资源确保每次仅有一个进程运用共享资源管程的定义管程的定义 一个管程定义了一个数据构造和能为并发进程所执行一个管程定义了一个数据构造和能为并发进程所执行( (在在该数据构造上该数据构造上) )的一组操作，这组操作能同步进程和改动的一组操作，这组操作能同步进程和改动管程中的数据。管程中的数据。 管程的组成管程的组成 1.1.称号；称号； 2.2.部分于管程内部的共享数据构造阐明；部分于管程内部的

12、共享数据构造阐明； 3.3.对该数据构造进展操作的一组过程；对该数据构造进展操作的一组过程； 4.4.对部分于管程内部的共享数据设置初始值语句。对部分于管程内部的共享数据设置初始值语句。管程的表示图管程的表示图 condition c1condition c1wait(c1)wait(c1)condition cncondition cn wait(cn) wait(cn) 部分数据部分数据 条件变量条件变量 过程过程/ /函数函数1 1 过程过程/ /函数函数k k出口出口 初始化代码初始化代码入口入口管程管程等待调用过程等待调用过程的进程队列的进程队列管程等待区管程等待区管程的条件变量管程

13、的条件变量 条件变量条件变量 出如今管程内的一种数据构造出如今管程内的一种数据构造 Var x Var x，y y：conditioncondition 只需在管程中才干被访问只需在管程中才干被访问 它对管程内的一切过程是全局的它对管程内的一切过程是全局的 只能经过两个原语操作只能经过两个原语操作waitwait和和signalsignal来控制它。来控制它。 x.waitx.wait 正在调用管程的进程因正在调用管程的进程因x x条件需求被阻塞或挂起时调用条件需求被阻塞或挂起时调用x.waitx.wait： 将本人插入到将本人插入到x x条件的等待队列上并释放管程，条件的等待队列上并释放管程

14、， 直到直到x x条件变化。条件变化。 此时其它进程可以运用该管程。此时其它进程可以运用该管程。x.signalx.signal 正在调用管程的进程发现正在调用管程的进程发现x x条件发生了变化，那么调用条件发生了变化，那么调用x.signalx.signal 重新启动一个因重新启动一个因x x条件而阻塞或挂起的进程。条件而阻塞或挂起的进程。 这与信号量机制中的这与信号量机制中的signalsignal操作不同。操作不同。 假设进程假设进程Q Q因因x x条件阻塞，而正在调用管程的进程条件阻塞，而正在调用管程的进程P P执行执行x.signalx.signal操作后，操作后，Q Q被重新启动，

15、可采用下述两种方式之被重新启动，可采用下述两种方式之一进展处置：一进展处置： P P等待，直至等待，直至Q Q分开管程或等待另一条件。分开管程或等待另一条件。 Q Q等待，直至等待，直至P P分开管程或等待另一条件。分开管程或等待另一条件。管程主要特性管程主要特性 模块化模块化 根本程序单位，可以单独编译；根本程序单位，可以单独编译； 笼统数据类型笼统数据类型 包含数据和操作；包含数据和操作； 信息隐蔽信息隐蔽 从外部看不到内部信息；从外部看不到内部信息；管程和进程不同管程和进程不同 管程定义的是公共数据构造；管程定义的是公共数据构造； 进程定义的是私有数据构造进程定义的是私有数据构造PCBP

16、CB 管程把共享变量上的同步操作集中起来管程把共享变量上的同步操作集中起来 临界区却分散在每个进程中；临界区却分散在每个进程中； 管程的设置那么是处理共享资源的互斥运用问题管程的设置那么是处理共享资源的互斥运用问题 设置进程的目的在于实现系统的并发性；设置进程的目的在于实现系统的并发性； 进程经过调用管程中的过程对共享数据构造实行操作进程经过调用管程中的过程对共享数据构造实行操作 管程为被开任务方式，进程那么为主开任务方式；管程为被开任务方式，进程那么为主开任务方式；管程和进程不同续管程和进程不同续 管程不能与其调用者并发管程不能与其调用者并发 进程之间能并发执行；进程之间能并发执行； 管程是

17、操作系统中的一个资源管理模块，供进程调用。管程是操作系统中的一个资源管理模块，供进程调用。 进程具有动态性，由进程具有动态性，由“创建而诞生，由创建而诞生，由“撤销而消亡撤销而消亡2.4 经典进程的同步问题经典进程的同步问题 2.4.1 消费者消费者消费者问题消费者问题 消费者消费者消费者问题是相互协作的进程关系的一种笼统消费者问题是相互协作的进程关系的一种笼统 制约关系：制约关系： 只需缓冲池未满，消费者便可将音讯送入缓冲池；只需缓冲池未满，消费者便可将音讯送入缓冲池； 只需缓冲池未空，消费者便可从缓冲池中取走一个音讯只需缓冲池未空，消费者便可从缓冲池中取走一个音讯123 . nPC信号量处

18、理消费者消费者问题信号量处理消费者消费者问题 用信号量及用信号量及P、V操作处理进程间同步问题操作处理进程间同步问题 一个消费者、一个消费者共享一个缓冲区一个消费者、一个消费者共享一个缓冲区 多个消费者、多个消费者共享多个缓冲区多个消费者、多个消费者共享多个缓冲区一个消费者、一个消费者共享一个缓一个消费者、一个消费者共享一个缓冲区的解冲区的解int B;semaphore empty; /可以运用的空缓冲区数可以运用的空缓冲区数semaphore full; /缓冲区内可以运用的产品数缓冲区内可以运用的产品数empty=1; /缓冲区内允许放入一件产品缓冲区内允许放入一件产品full=0; /

19、缓冲区内没有产品缓冲区内没有产品一 个一 个缓 冲缓 冲区区一 个一 个消 费消 费者者消 费 一消 费 一个产品个产品取 出 一取 出 一个产品个产品一个消费者、一个消费者共享一个缓冲区一个消费者、一个消费者共享一个缓冲区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(

20、) from B;一组消费者，一组消费者，公用一组消费者，一组消费者，公用n个环形缓冲个环形缓冲区区利用记录型信号量处理消费者利用记录型信号量处理消费者消费者问题消费者问题Var buffer:array0, , n-1 of item;in，out:integer:=0,0; /放入、取出缓冲区指针放入、取出缓冲区指针mutex: semaphore:=1；empty: semaphore:=n; /可以运用的空缓冲区数可以运用的空缓冲区数full: semaphore:=0; /缓冲区内可以运用的产品数缓冲区内可以运用的产品数123 . nP1P2P3 .Pm.C1C2C3.Ck消费者消费

21、者/ /消费者、共享多个缓冲区的解消费者、共享多个缓冲区的解 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;endparendConsumer_j:begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mu

22、tex); 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(mu

23、tex); 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

24、)和和P(S2)两个操作在一同，那么两个操作在一同，那么P操作的顺序至操作的顺序至关重要关重要 一个同步一个同步P操作与一个互斥操作与一个互斥P操作在一同时，同步操作在一同时，同步P操作在操作在互斥互斥P操作前操作前 两个两个V操作无关紧要操作无关紧要哲学家进餐问题哲学家进餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把筷子。每个哲学人面前有一只空盘子，每两人之间放一把筷子。每个哲学家思索、饥饿、然后吃通心面。为了吃面，每个哲学家必家思索、饥饿、然后吃通心面。为了吃面，每个哲学家必需获得两只筷子，且

25、每人只能直接从本人左边或右边去取需获得两只筷子，且每人只能直接从本人左边或右边去取筷子筷子 处理思绪处理思绪 5位哲学家看作位哲学家看作5个进程个进程 筷子是临界资源，在一段时间内只允许一位哲学家运用筷子是临界资源，在一段时间内只允许一位哲学家运用 可以用一个信号量表示一只筷子可以用一个信号量表示一只筷子 由这五个信号量构成信号量数组。其描画如下：由这五个信号量构成信号量数组。其描画如下： Var chopstick: array0，4 of semaphore； 一切信号量均被初始化为一切信号量均被初始化为1用记录型信号量处理哲学家进餐问题用记录型信号量处理哲学家进餐问题 第第i位哲学家的活

26、动可描画为：位哲学家的活动可描画为： repeat wait(chopsticki)； wait(chopstick(i+1)mod 5)； eat； signal(chopsticki)； signal(chopstick(i+1)mod 5)； think； until false； 分析分析 上述解法可保证不会有两个相邻的哲学家同时进餐上述解法可保证不会有两个相邻的哲学家同时进餐问题问题 有能够引起死锁有能够引起死锁 能够出现永远等待能够出现永远等待有假设干种方法可防止这类死锁有假设干种方法可防止这类死锁 至多允许四个哲学家同时吃；至多允许四个哲学家同时吃； 奇数号先取左手边的筷子，偶数

27、号先取右手边的筷子；奇数号先取左手边的筷子，偶数号先取右手边的筷子； 每个哲学家取到手边的两把筷子才吃，否那么一把筷子也每个哲学家取到手边的两把筷子才吃，否那么一把筷子也不取。不取。 本质上就是本质上就是AND同步问题同步问题 用用AND信号量机制可获得最简约的解法。信号量机制可获得最简约的解法。利用利用AND信号量机制处理哲学家进餐问题信号量机制处理哲学家进餐问题Var chopsiick array of semaphore:=(1,1,1,1,1)；processirepeatthink；Swait(chopstick(i+1)mod 5，chopsticki)；eat；Ssignal(

28、chopstick(i+1)mod 5，chopsticki)； until false； 读者读者-写者问题写者问题 有两组并发进程：有两组并发进程： 读者和写者读者和写者 共享一个文件共享一个文件F， 要求：要求： 允许多个读者同时执行读操作允许多个读者同时执行读操作 只允许一个写者执行写操作只允许一个写者执行写操作 不允许恣意一个写者和其他读者或其他写者同时访问文件不允许恣意一个写者和其他读者或其他写者同时访问文件读者读者-写者问题：处理思绪写者问题：处理思绪 为处理为处理Reader与与Writer进程间互斥进程间互斥 设置信号量设置信号量Wmutex 表示能否允许写的，初值为表示能否

29、允许写的，初值为1读者读者-写者问题：处理思绪写者问题：处理思绪 设置一个整型变量设置一个整型变量Readcount表示正在读的进程数目表示正在读的进程数目 初值为初值为0 Readcount是一个可被多个是一个可被多个Reader进程访问的临界资源进程访问的临界资源 为它设置一个互斥信号量为它设置一个互斥信号量rmutex 初值为初值为1parbeginReader: begin repeatwait(rmutex)； if readcount=0 then wait(wmutex)；Readcount:=Readcount+1；signal(rmutex)； perform read op

30、eration； 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(

31、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；Endparbe

32、ginReader: 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苹果桔子问题苹果桔子问题 苹果桔子问题苹果桔子问题 桌