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

操作系统 Operating Systems WINDOWSWINDOWS UNIXUNIX LINUXLINUX OS2OS2 VxWorksVxWorks Mac OSMac OS 2.3 进 程 同 步 进程同步的基本概念 两种形式的制约关系 间接相互制约关系。 p间接相互制约源于资源共享 直接相互制约关系。 p主要源于进程间的合作。 进程的同步与互斥 进程的两大关系： 互斥（间接制约关系）： 各进程竞争使用同一临界资源 p临界资源：一次只允许一个进程使用的系统资源 进程同步（直接制约关系）： 根据一定的时序关系合作完成一项任务 为完成共同任务的并发进程基于某个条件来协调其 活动 生产者-消费者问题 生产者-消费者(producer-consumer)问题是一个著名的 进程同步问题。 123 . n PC 生产者-消费者问题 producer: repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=(in+1) mod n; counter:=counter+1; until false consumer: 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。 5register1 5register24 6 5counter46 临界区 把在每个进程中访问临界资源的那段代码称为临界区 若能保证诸进程互斥地进入自己的临界区，便可实现诸进 程对临界资源的互斥访问。 repeat entry section（进入区） critical section； exit section（退出区） remainder section； until false； 临界区 同步机制应遵循的规则 1. 空闲让进。 2. 忙则等待。 3. 有限等待。 4. 让权等待。 2.3.2 信号量机制 1 整型信号量 定义为一个用于表示资源数目的整型量S 仅能通过两个标准的原子操作P操作(wait)和V操作 (signal)来访问。 wait(S)： while S=1 and and Sn=1 then for i:=1 to n do Si:=Si-1； endfor else 当发现第一个 Si1就把该进程放入等待队列， 并将其指令计数器置于Swait操作的开始位置 endif Ssignal(S1，S2，Sn) for i:=1 to n do Si:=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; end process 2: begin repeat wait(mutex); critical section; signal(mutex); remainder section； until false; End parend mutex 10 NULL -1 2.3.4 管程机制 管程引入 把分散在各进程中的临界区集中起来进行管理 ； 防止进程有意或无意的违法同步操作 可利用共享数据结构抽象地表示共享资源，把对共享数据 结构实施的操作定义为一组过程 进程对共享资源的操作，都是通过这组过程对共享数 据结构的操作来实现的 确保每次仅有一个进程使用共享资源 管程的定义 一个管程定义了一个数据结构和能为并发进程所执行(在 该数据结构上)的一组操作，这组操作能同步进程和改变 管程中的数据。 管程的组成 1.名称； 2.局部于管程内部的共享数据结构说明； 3.对该数据结构进行操作的一组过程； 4.对局部于管程内部的共享数据设置初始值语句。 管程的示意图 condition c1 wait(c1) condition cn wait(cn) 局部数据 条件变量 过程/函数1 过程/函数k 出口 初始化代码 入口 管程 等待调用过程 的进程队列 管程等待区 管程的条件变量 条件变量 出现在管程内的一种数据结构 Var x，y：condition 只有在管程中才能被访问 它对管程内的所有过程是全局的 只能通过两个原语操作wait和signal来控制它。 x.wait 正在调用管程的进程因x条件需要被阻塞或挂起时调用 x.wait： 将自己插入到x条件的等待队列上并释放管程， 直到x条件变化。 此时其它进程可以使用该管程。 x.signal 正在调用管程的进程发现x条件发生了变化，则调用 x.signal 重新启动一个因x条件而阻塞或挂起的进程。 这与信号量机制中的signal操作不同。 若进程Q因x条件阻塞，而正在调用管程的进程P执行 x.signal操作后，Q被重新启动，可采用下述两种方式之 一进行处理： P等待，直至Q离开管程或等待另一条件。 Q等待，直至P离开管程或等待另一条件。 管程主要特性 模块化 基本程序单位，可以单独编译； 抽象数据类型 包含数据和操作； 信息隐蔽 从外部看不到内部信息； 管程和进程不同 管程定义的是公共数据结构； 进程定义的是私有数据结构PCB 管程把共享变量上的同步操作集中起来 临界区却分散在每个进程中； 管程的设置则是解决共享资源的互斥使用问题 设置进程的目的在于实现系统的并发性； 进程通过调用管程中的过程对共享数据结构实行操作 管程为被动工作方式，进程则为主动工作方式； 管程和进程不同（续） 管程不能与其调用者并发 进程之间能并发执行； 管程是操作系统中的一个资源管理模块，供进程调用。 进程具有动态性，由“创建”而诞生，由“撤销”而 消亡 2.4 经典进程的同步问题 2.4.1 生产者消费者问题 生产者消费者问题是相互合作的进程关系的一种抽象 制约关系： 只要缓冲池未满，生产者便可将消息送入缓冲池； 只要缓冲池未空，消费者便可从缓冲池中取走一个消息 123 . n PC 信号量解决生产者消费者问题 用信号量及P、V操作解决进程间同步问题 一个生产者、一个消费者共享一个缓冲区 多个生产者、多个消费者共享多个缓冲区 一个生产者、一个消费者共享一个缓 冲区的解 int B; semaphore empty; /可以使用的空缓冲区数 semaphore full; /缓冲区内可以使用的产品数 empty=1; /缓冲区内允许放入一件产品 full=0; /缓冲区内没有产品 一个 缓冲 区 一个 生产 者 生产一 个产品 取出一 个产品 一个生产者、一个消费者共享一个缓冲区 cobegin process producer() process consumer() while(true) while(true) produce( ); P(empty); append( ) to B; V(full); coend Empty full 空 1 不满 0 0 满 1 无缓冲区 -1 空 -1 P(full); V(empty); consume( ); take( ) 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 . n P1 P2 P3 . Pm. C1 C2 C3 . Ck 生产者/消费者、共享多个缓冲区的解 parbegin Proceducer_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; end parend Consumer_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 永远等待 cobegin process producer_i( ) while(true) produce( ); P(mutex); P(empty); append to Bin; in=(in+1)%k; V(mutex); V(full); coend process consumer_j ( ) while(true) P(full); P(mutex); take( ) from Bout; out=(out+1)%k; V(mutex); V(empty); consume( ); empty full 0 k Mutex=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)； processi repeat think； Swait(chopstick(i+1)mod 5，chopsticki)； eat； Ssignal(chopstick(i+1)mod 5，chopsticki)； until false； 读者-写者问题 有两组并发进程： 读者和写者 共享一个文件F， 要求： 允许多个读者同时执行读操作 只允许一个写者执行写操作 不允许任意一个写者和其他读者或其他写者同时访问 文件 读者-写者问题：解决思路 为解决Reader与Writer进程间互斥 设置信号量Wmutex 表示是否允许写的，初值为1 读者-写者问题：解决思路 设置一个整型变量Readcount表示正在读的进程数目 初值为0 Readcount是一个可被多个Reader进程访问的临界资源 为它设置一个互斥信号量rmutex 初值为1 parbegin Reader: begin repeat wait(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； end parend writer: begin repeat wait(wmutex)； perform write operation ； signal(wmutex)； until false； End parbegin Reader: begin repeat wait(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； end parend writer: begin repeat wait(wmutex)； perform write operation ； signal(wmutex)； until false； End parbegin Reader: begin repeat wait(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； end parend writer: begin repeat wait(wmutex)； perform write operation ； signal(wmutex)； until false； End 苹果桔子问题 苹果桔子问题 桌上有一只盘子，每次只能放入一只水果；爸爸专向盘 子中放苹果，妈妈专向盘子中放桔子；一个儿子专等吃 盘子中的桔子，一个女儿专等吃盘子里的苹果 苹果桔子问题 解决思路： 生产者消费者问题的变形，有两类生产者和两类消费者 互斥： 盘子 同步： 爸爸和女儿； 妈妈和儿子 进程数目 分析 设置3个信号量 empty表示盘子能放的水果数目，初值为1 full_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