进程管理B互斥与同步.pptx
《进程管理B互斥与同步.pptx》由会员分享,可在线阅读,更多相关《进程管理B互斥与同步.pptx(127页珍藏版)》请在咨信网上搜索。
1、1第第2、3章章 进程管理进程管理B互斥与同步互斥与同步 本章知识点:本章知识点:并发原理并发原理 互斥互斥软件解决方法软件解决方法互斥互斥硬件解决方法硬件解决方法 2.3 进程同步进程同步管程管程2.5 进程通讯进程通讯2.4 经典进程的同步问题经典进程的同步问题2顺序程序及其特性顺序程序及其特性程序的顺序性包括如下两层含义:(1)内部顺序性,对于一个进程来说,它的所有指令是按序执行的;(2)外部顺序性,对于多个进程来说,所有进程是依次执行的;例如,假设有P1和P2两个进程,其活动分别为:P1活动:a1a2a3a4P2活动:b1b2b3b4顺序执行时,有如下两种情形:情形1:a1a2a3a4
2、b1b2b3b4情形2:b1b2b3b4a1a2a3a43顺序程序设计三个良好的特性:顺序程序设计三个良好的特性:(1)顺序性:处理机严格按照指令次序依次执行,即仅当一条指令执行完后才开始执行下一条指令;(2)封闭性:程序在执行过程中独占系统中的全部资源,该程序的运行环境只与其自身动作有关,不受其它程序及外界因素影响;(3)可再现性:程序的执行结果与执行速度无关,而只与初始条件有关,给定相同的初始条件,程序的任意多次执行一定得到相同的执行结果.4并发程序及其特性并发程序及其特性程序的并发性包括如下两层含义:(1)内部并发性,对于一个进程来说,它的所有指令可能按序执行,也可能不按次序执行;(2)
3、外部并发性:对于多个进程来说,所有进程是交叉(interleave)执行的.例如,对于上面P1和P2两个进程来说,只考虑外部并发性,具有许多情形,如:情形1:a1b1b2a2a3b3a4b4情形2:b1b2a1a2a3b3b4a4并发进程在其执行过程中,出现哪种交叉情形是不可预知的,这就是并发程序带来的不确定性5并发程序三个特性并发程序三个特性(1)交叉性:程序并发执行对应某一种交叉,不同的交叉可能导致不同的计算结果,操作系统应当保证只产生导致正确结果的交叉,去除那些可能导致不正确结果的交叉.(2)非封闭性:一个进程的运行环境可能被其它进程所改变,从而相互影响(3)不可再现性:由于交叉的随机性
4、,并发程序的多次执行可能对应不同的交叉,因而不能期望重新运行的程序能够再现上次运行的结果6与时间有关的错误与时间有关的错误若有两个进程P1、P2,共享一个公用变量c,初值为8,P1、P2所做工作如下:P1(退票)P2(售票)L1:a=c;L4:b=c;L2:a=a+1;L5:b=b-1;L3:c=a;L6:c=b;7与时间有关的错误与时间有关的错误试看下述两种执行情况:(1)若语句执行顺序为L1,L2,L3,L4,L5,L6,则c=8;(2)若语句执行顺序为L1,L2,L4,L5,L3,L6,则c=7。显然,上述结果是不能令人满意的。P1、P2是进程,每个进程中语句执行顺序是不变的,而两个进程
5、的语句是可以交叉执行的,它们以哪种方式交叉执行是不可预知的。改进:将c处理成临界资源,让P1、P2互斥访问c,一个进程对于c的一次访问完毕,另一个进程才能访问,就不会出现这种情况。8与时间有关的错误与时间有关的错误上述错误并不是一定发生的,它与进程的推进速度有关.即上述错误发生与否与进程P1和P2的推进速度有关,而速度是时间的函数,因而这种错误称为与时间有关的错误.发生上述错误的原因在于两个进程P1和P2同时对于一个变量C进行操作,一个进程对C的操作仅做了一部分,另一个进程中途插入使得变量C处于一种不确定的状态,用数据库的术语来说,就是失去了变量C的数据完整性.9 临界区临界区critical
6、 section进程访问临界资源的程序段称为临界区。在一个系统中,可以用某些方法或某种机制保证进程对临界区的互斥访问,一个好的解决方案应该遵循以下条件:(1)任何两个进程不能同时处于临界区内;(2)进程在临界区外只作有限时间的等待;(3)临界区外的进程不得阻塞其它进程进入临界区;(4)等待临界区时,释放CPU。102.3 并发原理并发原理 在单处理机多道程序的系统中,进程的并发执行方式是插入执行,表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源,必须保护每一进程的数据和物理资源不被其他进程
7、侵犯,并且进程执行的结果与其他并发进程执行时的相对速度无关。112.3 进程间相互联系与进程间相互联系与相互作用相互作用相互联系:(1)相关进程:在逻辑上具有某种联系的进程称作相关进程.(2)无关进程:在逻辑上没有任何联系的进程称作无关进程.相互作用:(1)直接相互作用:进程之间不需要通过中间媒介而发生的相互作用,这种相互作用通常是有意识的.(2)间接相互作用:进程之间需要通过某种中间媒介而发生的相互作用,这种相互作用通常是无意识的.122.3 进程间的相互竞争进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题:互斥 mutual exclusion(临界资
8、源和临界段)死锁 deadlock饥饿 starvation 竞争的控制不可避免地涉及到操作系统,因为是操作系统分配资源,另外,进程自身也必须能以某种方式表达互斥的要求。132.3 进程间的相互合作进程间的相互合作 1.通过共享合作这些进程并不是通过名字察觉到对方,而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外,保证数据的一致性也是一个潜在的控制问题。142.3 进程间的相互合作进程间的相互合作2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构,在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享
9、,所以这种形式的合作不需要互斥,但是还存在死锁和饥饿问题。15进程互斥的实现进程互斥的实现实现进程互斥,也就是实现对于临界区域的管理.为了保证其管理的正确性和公平性,应当满足下面三个管理原则:(1)正确性原则(correctness):任意时刻至多只能有一个进程处于关于同一组共享变量的临界区域之中;(2)公平性原则(fairness):一个请求进入临界区的进程应当在有限等待时间内获得进入该临界区的机会;(3)进展性原则(progress):当临界区空闲时,竞争进入临界区的多个进程在有限时间之内确定下一个进入临界区的进程.对此资源的管理应当满足如下调度原则:(1)当关于某一组共享变量的所有临界区
10、域均为空闲时,一个要求进入该组共享变量某一临界区域的进程应当能够立即进入;(2)当关于某一组共享变量的某一临界区域被占用时,一个要求进入该组共享变量某一临界区域的进程应当等待;(3)当一个进程离开关于某一组共享变量的某一临界区域时,应当容许某一个等待进入关于该组共享变量某一临界区域的进程进入.16Dijkstra成就成就程序设计:结构化程序设计,goto有害Os中并发程序设计,CS:what,why,how,P、V原语网络:最短路径算法17Dijkstra成就成就1965年提出解决CS问题4个基本准则:1、不能虚设硬件指令或假设处理机数目,但可以认为基本的机器指令是不会被分割执行的。2、不能假
11、设n个进程的相对执行速度。3、当一个进程未处于cs时,它不应阻止其它进程进入cs4、当若干个进程欲进入cs时,os应在有限的时间内选择出一个进程进入其cs。18使用互斥的原则使用互斥的原则由Dijkstra的四个基本准则可以导出:有空让进无空等待多中择一有限等待让权等待19互斥互斥软件解决方法软件解决方法软件方法对并发进程不提供任何支持,因此,无论是系统程序或应用程序,进程都要同其他进程合作以解决互斥,它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误,但有利于深刻理解并发的复杂性。20Dekker算法算法Dekker算法的优点在于它描述了并发进程发展过程中
12、遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束,其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。21Dekker算法算法 1.第1种途径这种方法保证了互斥,但它只记住了允许哪个进程进入其临界段,未记住每个进程的状态。varturn:0.1;turn为共享的全局变量PROCESS0PROCESS1whileturn0donothing whileturn1donothing;criticalsection;criticalsection;turn:=1;turn:=0;22Dekker算法算法2.第2种途径这种解决方法依赖于进程执行的相对速度共享的全局变量是:varf
13、lag:array0.1ofboolean;它被初始化为falsePROCESS0PROCESS1whileflag1donothing;whileflag0donothing;flag0:=true;flag1:=true;criticalsection;criticalsection;flag0:=false;flag1:=false;23Dekker算法算法3.第3种途径这种方法保证了互斥但会导致死锁问题。PROCESS0PROCESS1flag0:=true;flag1:=true;whileflag1donothing;whileflag0donothing;criticalsect
14、ion;criticalsection;flag0:=false;flag1:=false;24Dekker算法算法4.第4种途径PROCESS0PROCESS1flag0:=true;flag1:=true;whileflag1whileflag0beginbeginflag0:=false;flag1:=false;delayforashorttime;delayforashorttime;flag0:=true;flag1:=true;end;end;criticalsection;criticalsection;flag0:=false;flag1:=false;25Dekker算法算
15、法5.一个正确的解决方法设计一个“指示”小屋,小屋内的黑板标明“turn”,当P0想进入其临界段时,置自己的flag为“true”,这时它去查看P1的flag,如果是“false”,则P0就立即进入自己的临界段,反之P0去查看“指示”小屋,如果turn=0,那么它知道自己应该坚持并不时去查看P1的小屋,P1将觉察到它应该放弃并在自己的黑板上写上“false”,以允许P0继续执行。P0执行完临界段后,它将flag置为“false”以释放临界段,并且将turn置为1,将进入权交给P1。26Peterson算法算法 Dekker算法可以解决互斥问题,但是,其复杂的程序难于理解,其正确性难于证明。Pe
16、terson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法,进一步可将Peterson算法推广到多个进程的情况。27Peterson算法算法varflag:array0.1 ofboolean;flag1:=true;turn:0.1;turn:=0;procedure P0;whileflag0andturn=0donothing;begincriticalsection;repeatflag1:=false;flag0:=true;remainderturn:=1;foreverwhileflag1andturn=1donothing;end;criticalsection;be
17、ginflag0:=false;flag0:=false;remainderflag1:=false;forever turn:=1;end;parbeginprocedure P1;P0;P1beginparend repeat end.28Lamport面包店算法该算法的基本思想源于顾客在面包店中购买面包时的排队原理.顾客在进入面包店前,首先抓一个号,然后按照号码由小到大的次序依次进入面包店购买面包.这里,面包店发放的号码是由小到大的,但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥),如果多个顾客抓到相同的号码,则规定按照顾客名字的字典次序进行排序,这里假定顾客是没
18、有重名的.在计算机系统中,顾客就相当于进程,每个进程有一个唯一的标识,我们用P的下面加一个下标来表示.例如:对于Pi和Pj,如果有ij,则先为Pi服务,即Pi先进入临界区.29Lamport面包店算法面包店算法 该算法的实现需要如下两个数据结构:intchoosingn;intnumbern;前者表示进程是否正在抓号,正在抓号的进程choosingi为1,否则为0,其初值均为0.后者用来记录各个进程所抓到的号码,如numberi为0,则进程Pi没有抓号,如numberi不为0,则其正整数值为进程Pi所抓到的号码,其初值均为0.为了方便起见,我们定义下述表记法:(a,b)(c,d)如果ac or
19、(a=candbd).max(a0,an1)其值为一正整数k,对于所有i,0in1,kai.30Lamport面包店算法dochoosingi=1;numberi=maxnumber0,number1,numbern1+1;choosingi=0;for(j=0;jn;j+)while(choosingj)skip;while(numberj0)&(numberj,j)value;if(svaluequeue);V操作原语定义如下:voidV(semaphore*s)svalue+;if(svaluequeue);其中调用了asleep和wakeup两个标准过程,它们的定义如下:asleep(
20、squeue):执行此操作进程的PCB进入队列squeue的尾部,其状态由运行转为等待,系统转到处理机调度程序.wakeup(squeue):将队列squeue头部的进程的PCB由该队列中取出并将其排入就绪队列,其状态由等待转为就绪.51S.value的初值表示系统中某类资源的数目,因而又称为资源信号量,对它的每次P操作,意味着进程请求一个单位的该类资源,因此描述为S.value=S.value1;当S.value0时,表示该类资源已分配完毕,因此进程应调用block原语,进行自我阻塞,放弃处理机,并插入到信号量链表S.L中。可见,该机制遵循了“让权等待”准则。此时S.value的绝对值表示在
21、该信号量链表中已阻塞进程的数目。对信号量的每次signal操作,表示执行进程释放一个单位资源,故S.value =S.value+1操作表示资源数目加1。若加1后仍是S.value0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故还应调用V原语,将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1,表示只允许一个进程访问临界资源,此时的信号量转化为互斥信号量。52信号量信号量司机活动:司机活动:售票员活动:售票员活动:do do 启动车辆启动车辆 关车门关车门 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 while(1)while(1)53信号量用信号量和
22、用信号量和 P、V操作解决这一问题,需要定义两个信号量,一操作解决这一问题,需要定义两个信号量,一个信号量个信号量start表示是否允许司机启动车辆,另一个信号量表示是否允许司机启动车辆,另一个信号量open表表示是否允许售票员开车门。初始状态是车停在始发站,车门开着,示是否允许售票员开车门。初始状态是车停在始发站,车门开着,等待乘客上车。因此,两个信号量的初值都是等待乘客上车。因此,两个信号量的初值都是0。54信号量信号量关于信号灯变量的使用有如下两个基本要求:(1)必需置一次初值,只能置一次初值,(2)初值必需为非负整数;(3)只能执行P操作和V操作,所有其它操作均是非法的.55信号量信号
23、量基于上述规定,我们可以得到如下几个有用的结论:(1)当svalue0时,svalue为可用资源个数、不被阻塞的进程数,squeue阻塞队列为空;(2)当svaluevalue为squeue中等待进程的个数;(3)当svalue的初值为1时,可以用来实现进程互斥,这只需在进入临界区时执行一次P操作,在离开临界区时执行一次V操作.(4)当svalue的初值为正整数时,可以用来管理同种组合资源(具有多个实例的同种类资源,如5台打印机),申请时执行一次P操作,归还时执行一次V操作.56用信号量解决互斥问题用信号量解决互斥问题 信号量的互斥算法可以用小屋模型来描述。除了黑板外,小屋中还有一个大冰箱。某
24、进程进入小屋后执行wait操作将黑板上的数减1,这时,如果黑板上的值非负,它就进入临界段,反之它就进入冰箱内冬眠。这时,就允许另一进程进入小屋。当一个进程完成其临界段后,它进入小屋执行signal,将黑板上的值加1,这时如果黑板上的值为非正数,它就从冰箱中唤醒一个进程。57用信号量解决互斥问题用信号量解决互斥问题Vars:semaphore(:=1);ProcedureP()repeatP(s);V(s);forever58用信号量解决生产者用信号量解决生产者/消费者问题消费者问题 问题描述如下:一个生产者生产出某种类型的数据(记录、字符),并把它送入缓冲区(缓冲区为1),惟一的一个消费者一次
25、从缓冲区中取走一个数据。系统要保证缓冲区操作不发生重叠,即在任一时刻只能有一方(生产者或消费者)访问缓冲区。59例1.唯一生产者、唯一消费者单缓冲区问题1箱子,容量箱子,容量1 生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之60例1.唯一生产者、唯一消费者单缓冲区问题ProducerWhile(true)生产一个产品;P(s1);送入缓冲区;V(s2);s1=缓冲区空位数,初值1ConsumerWhile(true)P(s2);缓冲区取一个产品;V(s1);消费该产品;s2=产品数,初值061用信号量解决生产者用信号量解决生产者/消费者问题消费者问题 问题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 进程 管理 同步
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。