第四章-分布式资源管理要点课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第四章 分布式资源管理,4.1,资源共享,4.2,资源管理,策略,4.3,分布式系统中的死锁处理,1第四章 分布式资源管理4.1 资源共享,2,4.1,资源共享,实现资源共享的三种方法。,4.1.1,数据迁移,数据迁移的两种方法：,第一种方法是将整个文件转移给场点,A,，尔后，所有对该文件的存取都是局部的了。当用户不再需要访问该文件时，它的副本（如果它被修改过）被回送给场点,B,。对一个文件的任何微小的修改，都得将这整个文件传送回去,。,24.1 资源共享实现资源共享的三种方法。,3,另一种方法是只将该文件中实际需要的部分 转移给,A,。一旦用户不再使用该文件，该文件的任何已作过修改时部分必须回送给场点,B,。,显然，如果只访问一个较大文件的一小部分，那么采用后一种方法较好；否则采用第一种方法较合适。不过，仅仅从一个场点向另一个场点转移数据是不够的，系统还得执行各种数据转换（如果两个场点不是直接兼容的话）。例如，如果它们使用了不同的字符代码表示。,3 另一种方法是只将该文件中实际需要的部分 转移给A。一旦,4,4.1.2,计算迁移,在某些情形中，转移计算比转移数据更有效。例如，考虑这样一个作业，它需要存取位于不同场点上的若干较大的文件，以获得它们的概况。一种比较有效的办法是在它们驻留的场点上各自存取这些文件，然后分别回送所需要的值给初启该计算的那个场点 。,计算的实现方式：,可用一个远程过程调用来初启。进程,p,引用场点,A,上预定义的一个过程，该过程执行完后给,p,回送 所需要的结果。,4 4.1.2 计算迁移,5,通过消息传递的方式 。进程,p,可以发送一条消息给场点,A,，操作系统在场点,A,创建一个新进程,q,，,q,的功能是执行由该消息所指定的任务，当,q,完成其执行后，它又通过消息系统给,p,回送所需要的结果。,这两种方案都可用来存取驻留在各个场点上的若干文件。,5,6,4.1.3,作业迁移,当一个作业提交给系统后，系统可以在一特定的场点上执行这整个作业，或在不同的场点上执行它的某一部分 利用这种方案的主要原因是：,负载均衡：作业（或子作业）可以分散到系统中以,均衡系统的工作负载。,计算速度的提高：如果单个作业可以分解成若干子,作业，这些子作业可以在不同的场点并发地执行，那么，,整个作业的周转时间将会减少。,64.1.3 作业迁移,7,硬件特性：该作业可能有这祥一些特性，即它比较适合于在某些特殊的处理机上执行。例如，矩阵转换就比较适合于在阵列机上执行。,软件特性：该作业可能需要特定场点上的软件或不能移动的软件，或者移动该作业比较划算。,显示迁移,隐式迁移,7 硬件特性：该作业可能有这祥一些特性，,8,4.2,资源管理管理策略,分布式系统对于资源管理有两种基本的观点：,单个资源管理,单个资源与多个管理机构相互关系的角度进行分析。,多个资源管理,多个资源与多个管理机构相互关系的角度进行分析。,前者是后者的基础，后者是前者的提高。,84.2资源管理管理策略 分布式系统对于资源管理有两种,9,单个资源管理，有四种资源管理方式：,集中管理方式：,只有一个管理者对该资源的各种活动统一进行管理，其它管理者对该资源均不具有管理职能和责任。该方式也称为专制（,autocratic,）管理方式。,功能分布管理方式：,多个管理者按照不同的资源活动分担管理职能和责任，且每种活动只由一个管理者管理。该方式也称为分担管理方式或分割（,partitioned),管理方式。,9,10,浮动管理方式：,多个管理者均可同等地担负管理职能和责任，但在一段时间内，只有一个管理者行使职权，“任期”满后再由另一管理者接替，如此轮流下去。该方式也称轮流（,successive,）管理方式。,分散管理方式：,多个管理者采取协商一致的原则对资源活动进行全面管理，其中各个管理者的地位和功能是完全平等的。该方式也称民主,(democratic,）管理方式。,10浮动管理方式：多个管理者均可同等地担负管理职能和责任，但,11,从多个资源管理，可分为如下四种管理方式：,集中：,每一类资源只属一个管理者管理。它控制该类 全部资源。,分管,（集中分布式）：每一类资源由多个管理者管理，但每一资源只属一个管理者管理。,合管,（完全分布式）：不仅每一类资源存在多个管理者管理，而且该类中每个资源属于全部管理者共同管理。,部分管理,：每一类资源由多个管理者管理，每一资源 属于若干管理者管理。,如图,4.1,所示。其中圆圈表示管理者，三角形表示资源。,11从多个资源管理，可分为如下四种管理方式：,12,图,4.1,资源管理方式,12图4.1 资源管理方式,13,分布式管理方式和集中式管理方式的主要区别是对同类资源是采用多个管理者还是一个管理者。集中分布管理和完全分布管理的主要区别是前者让资源管理者对它管理的资源拥有全部控制权，而后者只允许资源管理者对它管理的资源拥有部分控制权。从上述两种管理方式的角度来考虑系统资源的划分。,从实用的角度讲，分布式系统中的资源管理方式主要有,局部集中式,、,分散式,和,分级式,。,13 分布式管理方式和集中式管理方式的,14,4.2.2,局部集中管理,每个资源由一个且仅由一个资源管理者管理，具体讲就是，资源按其在各场点上的分布情况分别由其所在的场点进行局部的集中管理，不存在全系统范围的集中管理者。,这种管理方式主要适用于,和处理机紧密相连的资源，,如内存、键盘、显示器，,当与它们紧密相连的处理机失效时，这些资源也就随之失效了。,14 4.2.2 局部集中管理,15,4.2.2,分散式管理,一个资源由多个场点上的管理者在协商一致的原则下共同管理。,这类则,和处理机的关系不甚紧密,，例如多副本文件，网络打印机等。,15 4.2.2 分散式管理 一,16,4.2.3,分级式管理,分级式管理的基本原理是：,针对实际的分布式系统对其中的各种资源进行分析，然后根据其重要性、常用性和隶属关系将资源分为两个级别：第一级是被多个场点经常使用的资源；第二级是仅被本场点使用的资源。,采用不同的方式管理不同级别的资源。即对第一级资源，由于它们被系统中的多个场点经常使用，因此，必须采用分散式管理方式，由多个场点在协商一致的原则下共同管理。对第二级资源，由于它们属于某个场点，不被其它场点使用，可以采用集中式管理方式，由某个场点集中管理。,164.2.3 分级式管理,17,4.2.4,一个分散式资源管理算法,1.,基本说明,占有资源的进程，必须先释放资源，系统才能把该资源分配给另一进程；,多个进程申请同一资源时，必须按其请求的先后次序来分配；,若每个分配到资源的进程都在有限时间内释放所占有的资源，则每个资源申者就可能在有限时间内获得该资源；,假定系统由,n,个场点组成，每个场点运行一个进程，它们的编号依次为,p,1, p,2, , p,n,。每个进程都有一个自己管理的申请队列用以存放请求消息。,174.2.4 一个分散式资源管理算法 1.基,18,2.,算法描述,该算法利用时间戳来标明申请资源的先后次序，以此来尽量消除对共享资源的竞争。,当系统中的任一进程,pi,，申请资源,rj,时，向系统中的其它每一进程发一,Request(Ti, pi, rj),消息，（其中,Ti,为此时的时间戳）并把它存入自己的请求队列；,进程,pk,，接收到这一消息后，将其存入自己的请求队列，若,pk,当前未请求该资源，则它马上给,Pi,发送一个带有时间戳的认可消息；若,pk,也正在请求使用该资源，且其时间戳,Tk,先于,Ti,，则它暂不给,Pi,发送认可消息；,182.算法描述,19,仅当下列条件成立时，,Pi,才可以分配该资源,;,在其请求队列中，它的,Request(Ti, pi, rj),消,息中的,Ti,比所有其它请求消息中的时间戳都要小；,pi,已接收到所有其它进程发来的时间戳迟于,Ti,的认可 消息。,在释放资源时，,pi,从自己的请求队列中去掉,Request(Ti, pi, ri),消息，并向系统中每个正等待请求使用该资源的进程发一条,Release(Ti, pi, ri),消息和一条带时间戳的认可消息。,当进程,pj,收到,pi,发来的,Release(Ti, pi, ri),消息后，从其请求队列中去掉,Request(Ti, pi, ri),消息。,19 仅当下列条件成立时，Pi才可以分配该资源;,20,1.,算法描述,当一资源管理者打算向其它场点的资源管理者申请资源时，先将招标消息广播出去；,当一资源管理者接收到这一招标消息后，若该场点有所需资源，则它根据一定方法计算出”标数”。然后，给申请者发一条投标消息，否则回复一条拒绝投标的消息；,4.2.5,招标算法,201.算法描述当一资源管理者打算向其它场点的资源管理者,21,当申请者接收到所有的投标消息后，根据一定的策略选择一个投标者，并直接向它发送一条申请资源的消息；,接收到此申请资源消息的资源管理者，将申请者的名字排入其等待队列，并在可以分配所指资源时再发消息通知申请者；,申请者在使用完所需资源后，通知分配资源者回收资源。,21 当申请者接收到所有的投标消息后，根据一定的策略选,22,投标与选标策略可视具体情况而定，例如，可用等待队列中排队等待的申请者的个数作为标数来投标，选标时则选择标数最小的投标者中标，或者不仅考虑有多个资源申请者，还考虑到投标者与招标者之间的距离，如，可规定标数为：,x,c,1,a,c,2,b,选取最小的,x,中标，其中,a,为等待的申请者的个数，,b,为投标者与招标者之间的距离,c,1,和,c,2,为两个常数。采用这种投标与选标策略考虑到了资源使用的均衡性和有效性。,22,23,若考虑场点故障而仍使该算法有效，则可增加如下措施：,若资源申请者发出申请消息后久末获得所需资源，则向中标者发一询问消息，若中标者末故障就立即予以回复；若发出询问消息后仍无回复，则申请者重新广播招标消息。,此时，修改为：“当申请者接收到所有的投标消息后，或等待时间超过预定时间值,T,后，根据一定的策略选择一个投标者，并直接向它发送一条申请资源的消息”。,23若考虑场点故障而仍使该算法有效，则可增加如下措施：,容易看出，该算法有如下特点：,不会出现饥饿现象，因为只要系统中有所申请的资源就必有一个中标者，只要每个资源占有者在有限长时间内归还所占资源，申请者总能从中标者处获得所需资源。,在无场点故障情况下，从广播招标消息到接到获得资源的通知，一共交换了,2,(n - 1),2,2n,条消息。,24,容易看出，该算法有如下特点：24,25,2.,适用于环形结构的招标算法,对于具有环形结构的分布式计算机系统，相应的招标算法为：,申请资源者向其邻近场点发一招标消息；,接收到招标消息后，若本场点上无所指资源，则它将招标消息沿环转移给下一邻近场点，否则,:,若此消息中未附投标信息，则它将本场点的投标信息附上，并将这一新形成的消息转移给下一邻近场点；,若此消息中已附有投标消息，则它就将本场点的投标消息同此消息进行比较，优选一个附上转移给下一邻近场点；,252.适用于环形结构的招标算法,26,某场点接收到自己发出的招标消息后，从其中所附的投标信息可知中标者是谁，直接向中标的资源管理者发一申请资源的消息；,中标者接收到申请消息后，将申请者的名字排入其等待队列，并在可以分配所需资源时向申请者发通知；,当资源使用完后，申请者通知分配资源者回收资源。,对于非环结构的分布式计算机系统，也可采用上述算法，只要规定消息统一按“逻辑环”转移即可。,26,27,4.3,分布式系统中的死锁处理,分布式系统中用于解决死锁问题的方法。,基于死锁预防,基于死锁检测。,引入资源分配图和进程等待图的概念。,27 4.3 分布式系统中的死锁处理,28,4.3.1,资源分配图,考虑如图,4.2,所示的资源分配图,G,。,其中，,V = P R,，,P = p1, p2, p3,，,R = r1, r2, r3, r4,，,E = (p1, r1), (p2, r3), (r1, p2), (r2, p1), (r2, p2), (r3, p3),资源类该类例示个数,r11,r22,r31,r42,图,4.2,资源分配图,284.3.1 资源分配图 考虑如图4.2所示的,29,可以证明，对于给定的资源分配图,G,，若,G,中不含环路，则表明系统未发生死锁，反之，若,G,中含有环路，则表明系统可能存在死锁。例如，若在图,4.2,中插入边,(p3, r2),（如虚线所示），则在这种情形，系统可能出现死锁。,图,4.3,含有环路的资源分配图,图,4.4,含有环路的非死锁资源分配图,29可以证明，对于给定的资源分配图G，若G中不含环路，则表明,30,4.3.2,进程等待图,从资源分配图中去掉表示资源类的方形并且合并相关的有向边便可得到对应的进程等待图,(process waiting graph),。例如，与图,4.3,中资源分配图对应的进程等待图如图,4.5,所示。,进程等待图中从,pi,到,pj,的有向边,(p,i, p,j,),意指：,p,i,等待,p,j,释被它所需要的资源。,而有向边,(p,i, p,j,),在进程等待图中存在，当且仅当对应的资源分配图中，对某个资源类,r,k,存在两条边，,(p,i, r,k,),和,(r,k, p,j,),。,若系统中的每一资源类仅含一个例示，则,系统发生死锁的充要条件是进程等待图中存在环路。,进程等待图常简称为等待图。,图,4.5,进程等待图,304.3.2 进程等待图 从资源分配图中去掉,31,4.3.3,利用时间戳预防死锁方法,预防死锁即破坏导致死锁成立的四个必要条件之一入手。,四个必要条件：,互斥,请求与保持,不剥夺,环路等待,314.3.3 利用时间戳预防死锁方法 预防死锁即,我们可以通过抢占资源（如果必要）来破坏循环等待条件。,为了控制抢占，我们给每个进程赋一个唯一的优先数，这些优先数用以决定进程,p,i,是否等待进程,p,j,。例如，如果,p,i,的优先数高于,p,j,的优先数，我们可以让,p,i,等待,p,j,，否则,p,i,被撤离。这种方法能防止死锁，因为对于等待图中的每一条边,(p,i, p,j,),，,p,i,的优先数高于,p,j,的优先数，因此也就不存在循环等待现象。,可能会发生饥饿现象？,提出了使用时间戳作为优先数的方法。,对系统中的每一进程，当创建它时，就赋给它一个时间戳，,32,我们可以通过抢占资源（如果必要）来破坏循环等待条件。32,33,等死（,wait-die,）方法,：是一种基于非抢占性技术的方法。当进程申请当前己由,p,j,占有的资源时，仅当,p,i,的时间戳小于,p,j,的时间戳（即,p,i,比,p,j,年长）时，让,p,i,等待,否则,pi,被撤离（死去）。例如，假定进程,p,1,，,p,2,和,p,3,分别有时间戳,5,，,10,和,15,，若,p,1,申请已由,p,2,占有的资源，,p,1,就等待；如果,p,3,申请已由,p,2,占有的资源，,p,3,就被撤离。,利用时间戳预防死锁的两种方法是,：,33 利用时间戳预防死锁的两种方法是：,34,因伤等待,(wound-wait),：是一种基于抢占性技术的方法。而且与上述方法对应。当,p,i,申请当前已由,p,j,占有的资源时，如果,p,i,的时间戳大于,p,j,的时间戳（即,p,i,比,p,j,年轻）时让,p,i,等待，否则,p,j,被撤离（即,p,j,被,p,i,致伤），,p,i,占有资源。再考虑前面的例子，如果,p,1,申请已由,p,2,占有的资源，那么该资源从,p,2,手中抢占，而且,p,2,被撤离；如果,p,3,申请已由,p,2,占有的资源，则,p,3,就等待。,34 因伤等待(wound-wait)：是一种基,35,这两种方案都可以避免饥饿现象发生，只要对被撤离的进程不再赋以新的时间戳，因为时间戳总是递增的，因此，被撤离的进程最终将具有最小的时间戳，因此它将不会再次被撤离。但这两种方案是有差别的：,在“等死”方案中，年长的进程必须等待年轻的进程释放它的资源，因此进程越“年长”，它就越容易引起等待。与此相反，在“因伤等待”方案中，年长的进程决不会等待年轻的进程。,35 这两种方案都可以避免饥饿现象发生，只要对,36,在“等死”方案中，如果进程,pi,因为申请已由进程,pj,占领的资源而被撤离和死掉，那么当它再次激活时，它又可能再次发出相同的申请，此时，若资源仍由,pj,占有，那么，,pi,将再次“死掉。因此在得到所需要的资源之前。,pi,可能被撤离若干次。但在“因伤等待”方案中，进程,pi,因为,pj,申请已由它所占有的资源而被撤离和致伤，当,pi,再次激话并申请正由,pj,占有的资源时，,pi,就等待。因此，在“因伤等待”方案中撤离的次数较少。,36 在“等死”方案中，如果进程pi因为申,37,死锁预防算法甚至在不发生死锁时也可能抢占资源。,死锁检测算法,构造一等待图来描述资源分配状态。因为我们假定每类资源只有单个例示，因此，等待图中的环路就表示死锁发生。,如何管理等待图？,要求每一场点管理一个局部等待图。图中的结点对应所有这样的进程（本地及远程的），这些进程当前正占有或者正在申请局部于该场点的任何资源。例如，图,4.6,中的系统由两个场点组成，每个场点都管理它的局部等待图。注意进程,p,2,和,p,3,出现在两个图中，表示它们在两个场点中申请资源。,4.3.4,死锁检测方法,37 死锁预防算法甚至在不发生死锁时也可能抢占资,38,图,4.6,局部等待图和全局等待图,38图4.6局部等待图和全局等待图,39,显然，如果任何局部等待图中存在环路，则表明发生了死锁。但任何局部等待图中不出现环路并不意味不存在死锁,。,例如，考虑图,4.6,中的情况，其中每个局部等待图中均无环路，但该系统却存在死锁，因为在它的所有局部等待图之并图中存在环路。图,4.7,中的等待图就是图,4.6,中两个（局部）等待图之并，它的确含有环路，这隐含该系统存在死锁。,有许多不同的方法构造分布式系统中的等待图，几个常用的方法介绍如下：,39 有许多不同的方法构造分布式系统中的等,40,4.3.5,集中式死锁检测方式,采用集中式方式，全局等待图是取所有局部等待图之并构造而成的，它是由单一进程管理的，这个特殊的进程称为”死锁检测协调者（,coordinator,）”进程，等待图可以在不同时刻构造：,每当从局部等待图中去掉一条边或向局部等待图插入一条新的边时；,周期性地当等待图中已经发生了若干改变时；,每当协调者需要引用环路检测算法时。,404.3.5 集中式死锁检测方式 采用集中,41,当引用该死锁检测算法时，协调者搜索它的全局图，如果发现一环路，则挑选一个进程作为牺牲者予以撤离，从而破坏环路。事后协调者必须通知所有的场点“此时某一进程已经选作为牺牲者”。接到通知的场点也应作相应的处理。,41,42,这种方案可能导致不必要的撤离，因为存在下述几种现象：,在全局等待图中可能存在假环路。例如，考虑图,4.7,中的系统。假定,p2,释放了它在场点,A,中占有的资源，从而导致场点,A,中删除边,(p1, p2),，然后进程,p2,申请场点,B,中已由,p3,占有的资源，于是导致场点,B,中插入边,(p2, p3),。如果来自场点,B,的消息,insert(p2, p3),在来自场点,A,的,delete(p1, p2),消息之前到达，那么，在“插入”之后“删去”之前的这段时间隔，协调者可能发现假环路,p,1,，,p,2,，,p,3,，我们称这种情况为假死锁（,falsedeadlock,）。这时就得调用死锁解除算法，尽管实际上并没有发生死锁。,42这种方案可能导致不必要的撤离，因为存在下述几种现象：,43,当死锁的确发生而且已选定了一个牺牲者，但在同时某进程由于与死锁毫不相干的原因被暂时夭折（如进程的执行时间超过了分配给它的时间片）时，也可能导致不必要的撤离。,例如，假定图,4.6,中的场点,A,决定让,p,2,夭折，但在同时协调者已发现一个环路并选定,p,3,作为牺牲者。于是,p,2,和,p,3,现在都得撤离，尽管此时实际上仅,p,2,需要撤离。,43当死锁的确发生而且已选定了一个牺牲者，但在同时某进程由,44,为了避免报告假死锁，它要求来自不同场点的请求消息附上唯一的标识（时间戳）。当场点,A,上的进程,pi,申请位于场点,B,的进程,pj,占有的资源时，应发送一条带有时间戳,n,的申请消息。于是，边,(p,i, p,j, n),被插入到,A,的局部等待图中，如果,pj,已经接收到这一请求消息但不能马上释放所请求的资源时，边,(p,i, p,j, n),也插入场点,B,的局部等待图中；,图,4.7,全局等待图,中的假环路,44为了避免报告假死锁，它要求来自不同场点的请求消息附上唯一,45,如果同一场点中的进程,pi,向,pj,提出申请，则相应的请求消息中不必附上时间戳。该检测算法的执行过程如下：,协调者向系统中每一场点发送一条初始消息；,当接收到这一消息后，各场点将它的局部等待图发送给协调者。注意，每一个等待图包含该场点的所有局部信息。这种等待图反映了相应场点瞬时的状态，但它并不与反映任何其它场点的等待图同步。,45 如果同一场点中的进程pi向pj提出申请，,46,当协调者接收到来自每一场点的回复消息后，它就按如下方法构造等待图：,系统中的每一进程作为图中一个结点；,当且仅当这些等待图之一中有边,(pi, pj),或者边,(pi, pj, n)(,对某个,n),出现在一个以上的等待图中时，则在全局等待图中就加上边,(pi, pj),。,可以断言，如果按此方法所构造的等待图中出现环路，那么该系统处于死锁状态。如果所构造的图中不存在环路，那么在开始执行该算法时，该系统不是处于死锁状态。,46 当协调者接收到来自每一场点的回复,47,4.3.6,层次式死锁检测方法,集中式死锁检测算法要求所有的信息部驻留在一个进程中，并且由该进程管理。层次式死锁检测算法则是将这些信息分散给多个进程来管理。因而它是一种分布式算法。,同集中式方法类似，每个场点管理它自己的局部等待图，但与集中式方式不同的是全局等待图被分散给若干不同的控制者（,controller,）管理，这些控制者组织成树形结构。其中每片叶子包含单个场点的局那等待图。每个非叶子控制者管理着它下面子树的控制者管理的等待图。,474.3.6 层次式死锁检测方法 集中式死锁,48,控制者,c,的局部等待图；,从,C,到,A,的路径中每一控制者的局部等待图；,从,C,到,B,的路径中每一控制者的局部等待图。,此外，如果,pi,和,pj,出现在控制者,D,的等待图中，而且,D,的孩子之一的等待图中存在从,pi,到,pj,的路径，那么边,(pi, pj),也必须出现在,D,的等待图中。,令,A,、,B,和,C,是控制者，,C,是,A,和,B,的父亲（注意，,C,必须唯一，因为我们讨论的是树形结构）。如果结点,pi,出现在控制者,A,和,B,的局部等待图中，那么，,pi,也必须出现在下面的局部等待图中：,48 令A、B和C是控制者，C是A和B的父亲（注,49,如果这些等待图中的任何一个出现环路，那么，该系统处于死锁状态，必须引用相应的死锁解除算法。,例如，考虑图,4.6,所示的系统，该系统的树形结构如图,4.8,所示。由于,p2,和,p3,都在,A,和,B,中出现，所以它们也出现在,C,中。由于在,A,中存在从,p2,到,p3,的路径，因此,C,中包含,(p2, p3),。类似地，由于,B,中存在从认,p3,到,p2,的路径，所以，,C,中也包含边,(p3, p2),。注意,C,的等待图中出现了环路，这表明该系统已出现死锁。,49 如果这些等待图中的任何一个出现环路，那么，该系统处于死,50,图,4.8,层次式等待图,50图4.8 层次式等待图,51,Thanks !,51Thanks !,