（计算机应用技术专业论文）分布式实时系统中动态负载共享算法的研究.pdf

中南大学硕士论文 摘要 在分布式实时系统中，如果任务到来不均衡地分布到结点上，那么有些结点可能 过载，而另外一些结点处于空载或轻载状态，这时，即使整个系统完全有能力完成所 有任务，也有些任务不能在截止时间以前完成，减少这个问题的一种方法是l s ( 负 载共享) 。 本文提出了一个在实时分布式系统有失败结点情况下容错的、动态的带区域状态 变化信息广播的负载共享算法。无论何时当一个结点的状态从轻载状态到重载状态或 相反，它都会向被称为伙伴集的一个结点集合中的其他结点广播这种变化，同样，一 个超载的结点不通过探查其他结点的状态也能从它的优先列表中选择第一个可用的结 点。本文主要讨论两个问题：确定最佳的超时值础，以便一个结点的失败能被其他 的结点检测出来，即如果结点竹自从最后一次收到结点f 的广播信息以后还曩? 没有 收到结点f 的广播信息，就认为结点f 失败，并且在再次收到广播消息以前不考虑把 任务交给结点f ：提出了调整结点的优先列表的算法，以保证每个结点被一个也只能 是一个结点选择做自己的第t 个优先结点，并相应地提出了一个处理结点失败的算 法。 用于诊断一个结点是否失败的超时值砭? 的确定取决于以下三个因素：系统负载 的动态变化：此结点上的负载分配：结点的初始状态。用于计算z ：? 所需的参数可以 通过贝叶斯估技术在结点j 上在线估计得到，然后应用状态信息计算叠? 。 本文的实验结果显示，带有在线估计参数、超时机制和额外的及时广播信息的动 态l s 算法相比其他没有任何超时机制或带有固定超时值的算法，能有效地减少任务 的失败率：同时实验结果还显示，无论系统中失败结点数有多少，应用相应算法凋整 之后的优先列表都能保持原来的特性，而且简单的容错的各份队列方法能减少任务丢 失数。 关键词：实时系统，负载共享，伙伴集，截止时间，优先列表，超时，随机化，贝叶 斯参数估计，假设检验，性能评估。 中南人学 * ! l 。论史 a b s t r a c t ht a s ka r f j v a l sa r en o 【u n i ! o r l l l 【yd j s t r i b u t e do v e rt h en o d e si nad i s t r i b u t e di a l 一“i n e s y s t e n l ，s o m en o d e sm a yb e c o m eo v e r l o a d e dw h i l eo t h e r sa r eu n d e r l o a d e d c o n s e q u e n “y s o m e a s k sc a n n o tb ec o m p l e t db e f o r et h e j rd e a d l i n e s ，e v e ni f l eo v e r a ns y s t e mh a st h e c a p a c i t yt om e e ta l ld e a d l i n e s l o a ds 1 1 a r i n g ( l s ) i so n ew a y t oa l i e v i a t et h i sp r o b 】e m t h i sp 印e ra d d r e s s e sa f a u l t t o l e r a n t ，d y n a n l i cl o a ds h 撕n g ( l s ) “t hs t a t e r e g i o n c h a n g eb r o a d c a s t si n 廿1 ep r e s e n c eo fn o d ef a i l u r e sf o rad i s t r i b u t e dr e a l t i m es y s t e m w 1 1 e 1 1 e v e r 1 es t a t eo fan o d ec h a n g e sf i o l nu n d e r j o a d e dc of u l l y l o a d e da n dv i c ev e r s a t h e 1 1 0 d eb r o a d c a s t k sc h a n g el oas e lo fn o d e s c aj i e da b u d d ys e f ，j 1 1t h es y s t e m a n o v e r l o a d e dn o d ec a ns e l e c t ，w i t h o u tp r o b i l l go t h e rn o d e s ，t h e6 r s ta v a i l a b l en o d ef i o n li t s p r e f e r r e dl i s t i nt 1 1 i sp a p e r ，m a i n ly ，w ea d d r e s st w oi m p o r t a n ti s s u e sa s s o c i a t e dw i t ht h el s ： ( 1 ) w ed e t e r m i n et h e ”b e s t ”t i m e o u tp e r i o df ：? t 1 1 0 u g l lw h i c hf a i l u r eo fan o d ei sd i a g n o s e d b yt h eo t l l e rn o d e s 。i 、h a fi st os a y ，i fn o d enh a sn o th e a r df r o mn o d eif o rr 等s i l l c ei t s r e c e i p to ft h e1 a t e s tb r o a d c a s t 丘o mn o d ei ，i tw i l lc o n s i d e rn o d eif a i l e d ，a n dw i l l n o t c q n s i d e ra n yt a s kt r a n s f e rt on o d ei u n t i li tl e c e i v e sab r o a d c a s tm e s s a g ef 的mn o d eia g a i l l ( 2 ) w 。p r o p o s ea l g o “1 h m st om o d i f j 【】1 ep r e i e r r e d1 j s ti ns u c haw a yi h a ee a c hn o d ew i l jb e s e l c cc e da st h ek d lp r e f e r r e d1 1 0 d eo fo n ea n do n l yo n eo 1 e rn o d ea n dp f o p o s e das i l l l l ) l c n l e c h a n i s n lt ot o i e r a t en o d ei h i l u r e s t h et i m e o u tp e r i o du s e dc od i a g l l o s ew 1 1 e t h e ran o d ei sf a u l l yo r1 1 0 tu s u a l l yd e p e n d so l l t h cd y u i cc 1 1 a 1 1 9 e si ns y s t e i n1 0 a d ，t 1 1 ec a s ka t t f i b u e sa t t h e1 1 0 d e ，a n dt l l es t a t et 1 1 e1 1 0 d e w 粥i n i c i a l l yi n 1 h ep a r a m e t e r sn e e d e df o rt h ec a l c u i a t i o no ff 搿a r ce s t i m a t e do j l _ l j l l eb y n o d ei u s i n g 1 eb a y e s i a nt e c l l i q u e t h eb r o a d c a 吼i n f o r m a t i o ni st h e nu s e dt od e t e n l l m e f 黔 0 u rs i m u l a t i o l lr e s u l t ss h o wt h a tm el sa l g o r i t h m sw h i c hc o m b i n e sc h eo i 卜i i l l e p a r a m e t e re s t i | n a t i o n ，t h et i m e o u tm e c l l a l l i s m ，a n daf b we x t r a 血n e l yb o a d c a s t sc a n s i 曲i f i c a n t l yr e d u c et 1 1 ep r o b a b j i i i _ yo fn l i s s i n gt a s kd e a d l j n e s ，a sc o m p a r e dt ot l l eo t h e r a j g o “出m se j t l l e rw n h o u ta 1 1 yt i m e o u tm e c h a 趟s mo rw i l ha 螽x e dt i m e o u tp e r i o d t h e p r e f 色i t e dl i s t sm o d i f i e db yt h ep r o p o s e da l g o “t sa r es h o w nt oi t a i nt h e i ro r i g i n a l p r o p e r t i e sr e g a r d l e s so ft h en u m b e ro ff a u l t yn o d e si nm es y s t e m ，a n dt 1 1 es “n p l er a u l t - t o i e r a n tb k oi ss h o w nt or e d u c et h en u m b e ro f t a s k1 0 s s e s i n ? e xt c r i n s ：r e a l 一t i m es y s 【e m s ，l o a ds h a r i l l g ，b u d d ys e t ，d e a d l i l l e s ，p r e f e r r e dl i s l ，t i n l e o u i r a n d o m i z a t i o n ，b a y e s i a np a r a n l e t e re s t i m a t i o n ，h y p o t l l e s i st e s t i l l g ，p e r f o r m a n c ee v a i u a “o n 中南大学硕士论文 1 1 研究背景 第l 章绪论 随着高速网络和处理器开始成为商品化硬件，价格可以承受并且合理高效的分布 式系统似乎无处不在了i l 】。然而，在分布式实时系统中，实时性是关键的，如果实时任 务不能在截止时间内完成将导致灾难性的结果【2 】，例如发电站、医院、制造和运输系统 等等。所以利用低价、高性能处理机和内存构成的具有高性能和高可靠性的分布式计算 绝对是实现实时应用的理想选择h 】。 在分布式系统中，如果任务到来不均衡地分布到分布式实时系统的结点上，那么 有些结点可能过载，而另外一些结点处于空载或轻载状态，这时，即使整个系统完全有 能力完成所有任务，有些任务不能在截止时间以前完成，减少这个问题的一种方法是 l s ( 负载共享) 。有关分布式系统中的l s 算法已经有很多的研究【4 “5 1 。 为了解决实时性问题，实时计算系统必须使用先进的调度算法，完成实时任务到 处理机的任务分配，以及把到达超载结点上的某些任务转发给轻载的结点完成，以达到 任务及时完成，减少任务丢失。有关的调度算法的研究有很多【睁3 0 】，决定结点间负载 共享的方式有静态和动态之分，静态决定方式l 引卫j 独立于系统当前状态，而动态决定方 式依赖于决定时的系统状态。静态l s 也被看作一个系统中的非决定性任务分配【3 1 ，3 2 】， 当一个超载结点f 以砌的概率把它的一些任务传递给结点m ，这个概率独立于系统的 当前状态，虽然静态l s 能很容易地用队列模型来进行分析，但是由于使自己适应于随 时间变化的系统而使其能力受到限制田】，例如，即使当结点m 超载，它还会象它处于 轻载状态一样，从其它结点接受任务。 然而，动态l s 不一样，一个超载结点能使用它当前系统的有关状态信息把任务传 递给其他结点【3 3 书】，因为任何动态策略需要每个结点知道其他结点的状态，所以必然 要比静态策略复杂。所有动态l s 算法所需的状态信息能通过几种途径收集到：状态信 息的定期交换【3 6 】；请求状态探查口7 q 9 】；定期广播状态变化【3 3 4 0 4 ”。基于状态信息的 定期交换的算法，需要一个优化的方法来决定信息交换的时间间隔，这是因为在做一个 l s 决定时的状态信息的精确度很大程度上取决于这个时间间隔：另一方面，基于请求 状态探查的算法在每次请求探查过程至少产生两个附加的信息：传入时问、通信超 量，因此不利于实时任务的及时完成，而且这些算法的性能对通信延迟的变化非常敏 感，所以，在状态区域变化时更新状态信息的算法有利于维护更多的最新状态信息，有 利于在需要做l s 决策前低价收集这些信息。尽管如此，这些算法还是存在以下潜在的 问题： ( 1 ) 当系统负载加重或系统中通信结点数目增多时高额通信变得极大： 中南大学硕士论文 ( 2 ) 如果排列任务传递的延时变大时，收集的状态信息很可能过时了； ( 3 ) 结点失败很容易影响性能，如果结点，l 安静( 例如，不传播它的状态变化信息) 一段时间的话，其他结点没有办法知道这个结点是失败了还是恰巧处于任务到达和完成 传递活动之间的交替阶段。 在本文的动态l s 算法中：引用s h i n 和c h a n g 在文献【4 0 】提出的伙伴集和优先列表 的概念来减少问题( 1 ) 的不利影响；利用文献【4 1 】的结果，本文提出的容错的、动态l s 算法能在存在不可忽略的通信延时的前提下大大地减轻问题( 2 ) ；解决问题( 3 ) 是通过在 含有非周期状态区域变化广播机制的l s 算法中引入越时机制【4 2 1 ，并对优先列表进行调 整，以减少任务丢失率。 对于应用状态区域变化广播技术的l s 算法来说，每个结点n 在任何时候只要它的 ( 墟7 i 任务累积执行时间) 超过某一个广播域值【4 l 】，就会广播一则信息，把有关的状态区 域的变化信息告诉本结点的伙伴集中的其他结点，每个结点根据l s 算法确定传递和定 位策略。另外，如果结点n 自从接受结点f 的最后广播信息以后超过时间础后还没有 接受到结点f 的信息，就认为结点f 是失败的，由它的最优先结点接管它的任务，并调 整结点的优先列表，如果以后即使观察到( 通过状态区域广播收集的状态信息) 结点f 有能力按时完成任务，结点 也不会把它的过剩任务传递给结点f 。在这里，确定互2 对于超时机制的性能是很关键的。 当一个结点失败时，其他结点不能再把任务传递给它，并且本结点上的任务必须保 证有其他正常的结点来接管，所以，必须调整结点的优先列表，把失败结点从优先列表 中去掉，以减少任务丢失，保证系统任务的准确、及时完成。 因此，调整结点的优先列表和超时机制及其优化的超时值的确定是本文的两个重点 课题。 1 2 优先列表调整 构造优先列表和伙伴集时的两个重要问题是协调问题和拥挤问题【帅】。首先，在过 载结点数不多于轻载结点数的情况下，不会发生两个或两个以上过载结点选择同一个轻 载结点做为它的任务接受者，否则，即使系统中存在有其他的轻载结点，也会发生由于 多个过载结点同时把自己的过载任务传递给一个轻载结点而导致此轻载结点过载，这个 问题是由于在过载结点中缺少协调引起的，所以为了减少任务传输延时，一个结点的伙 伴集应该由物理上相近的结点组成。但是，当系统中的某个区域内的过载结点数大于轻 载结点数时( 本文把这个区域叫过载区域) ，拥挤问题就发生了。为了解决这个问题， 结点的伙伴集可以重叠设计，以保证一个伙伴集的过载结点能够把过载任务传递给不同 伙伴集内的结点，从而到达一个过载区域内的过载结点上的任务能够在整个系统内实现 共享，而不仅仅在同一个伙伴集的结点间实现负载共享。 中南大学硕士论文 在文献【4 0 】中已经提出了在超立方体连接的多计算机系统中有结点失败的情况下构 造优先列表的算法，能够保证每个结点被一个也只能是一个结点选择做它的第七个优先 结点1 4 。为了减少由于利用l s 算法而引起的通信延时，选择优先列表中前面几个结点 做为伙伴集。在文献【4 4 】中已经证明当系统的结点数多于1 0 2 4 时选择伙伴集大小为1 0 1 5 时系统的性能达到最佳，而且由文献【4 0 】知道利用这样的优先列表能很好地解决协调 和拥挤问题。然而，如果失败结点简单地从优先列表中退出，原来的优先列表的结构将 遭到破坏。例如，设从和 ，v 是，结点的最优先和次优先结点并且设肌是 - 的最优 先结点，假设此时结点i 失败，并从，的优先列表中退出，然后肌将成为m 和尬的 最优先结点，从而违背了“每个结点被一个也只能是一个结点选择做它的第个优先结 点”这个特性。同样的情况发生在m 和m 两个结点都超载的情形。基于此，本文提出 了当结点失败时调整优先列表的算法，以保证l s 算法原来的特征。本文也将证明，不 管系统中的失败结点数为多少，这样的调整算法总是存在的，而且本文提出的算法能保 证摄小的通信延时。 假设一个结点在完成它的任务队列中的所有任务之前失败，而且如果没有提供容错 机制，队列中所有未完成的任务将会丢失。应用调整优先列表算法避免，最小化任务丢 失的一个简单的容错机制构造如下，每个结点虬上有一个队列用于备份它的最优先结 点他的任务，相应地结点 0 上有一个队列用于备份结点 0 的任务，如果一个结点过 载，它能传递任务给另一个结点，就象任务到达另一个结点一样。实验证明，应用这个 算法，在优先列表的失败结点将会被正常的结点所替换，以保证原来选择失败结点做为 最优先结点的结点的任务被一个正常的结点备份。 在此算法中，应用已存在的优先列表去备份失败结点有两个优点： ( 1 ) 在提供每个结点的备份队列时，利用优先列表不会产生额外的开销； ( 2 ) 调整算法能保证失败结点从优先列表退出时，它的任务总是能被一个正常的结 点来备份。 1 3 超时机制及其优化的超时值的确定 结点h 在z 2 内没有从结点f 收到状态广播信息不外乎以下两种情况： ( 1 ) 结点f 发送最后一次广播信息以后失败了一段时间； ( 2 ) 导致任务到达和任务完成传递两种情况以下面两种方式交替出现，结点f 状 念即c e 砰或者是在两个相邻广播闽值内摆动，或者是维持在一个阈值间隔内不动。 通过减少磁( 因此能较早地检测到一个结点的失败) 能获得性能的改善，而因为 仓促和不正确的诊断会导致性能降低，因此，冕? 的确定必须在这两种情况之间有个折 衷。为解决这个问题，首先做一个假设，然后通过在预先指定的一个错误判断概率的范 围内使检测结点失败的概率最大化来确定z 2 。 中南大学硕士论文 为了进一步减少错误判断的概率。每个结点栉同时计算自己和其他结点的最好的超 时值，不仅在状态信息改变的时候，而且在一个阈值区间内经过砭：时都会广播自己的 状态信息，这就是说，在快速检测结点失败时，利用这些额外的及时广播信息可以减少 错误判断带来的不必要的影响。 使超时机制的设计复杂化的一个原因是结点上任务到达和完成，传递活动( 进而包 括f 2 的最优值) 随着系统负载、任务分配和一个结点的初始状态而动态地变化，因 此，砭? 的计算需要在线估计结点j 上与任务分配有关的参数，即需要每个结点收集统 计信息，在线估计本结点的“组合”( 包括外来的和其他、结点传递进来的) 任务到达 率、任务执行时间和松驰量的分布，并通过状态信息广播方式把估计的参数传送到伙伴 集中其他结点其他结点利用这些信息确定其叠? 值。 本文是在文献【4 1 】中的非周期性状态信息广播的l s 算法中引入超时机制，并对结 点的优先列表进行调整，以大大降低系统的任务失败率。 本文是这样组织的：第2 章介绍算法模型：第3 章优先列表的构造及其容错技 术；第4 章超时机制及其优化的砭? 的确定；第5 章对动态负载共享算法进行实验性能 比较与分析；第6 章结束语。 4 中南大学硕士论文 第2 章动态负载共享算法模型 应用一个有限状态空问上的连续时间的马尔可夫链来模拟一个结点的状态的估 计即构造结点级系统模型，确定马尔可夫链的状态转移概率，在此基础上引入超时机 制，并调整结点的优先列表，形成了动态负载共享算法模型。本章首先对在本算法用到 的符号做出说明，然后阐明系统模型及其状态转移概率，最后从总体上对动态负载共享 算法进行描述。 2 1 符号说明 ( 1 ) ，：假设每个结点有一个指数失败率( 用于可靠性评估) ； ( 2 ) ，l ，：代表在结点，上的组合( 包括外来的和传入的) 任务达到率。本文近似地 认为组合任务达到过程服从泊松分布，这个近似被用于z 2 的推导及在线估计计算7 2 所需的参数： ( 3 ) 9 彩，1 昂。) ：结点f 上外来任务和传入任务总的执行时间的分布，这 里e 。是以时钟滴答数计算的最大任务执行时间，这个分布可以通过每个结点f 在线估 算： ( 4 ) e ，。厶，8 女) 啊，如，l ： 表示外来任务的执行时间分布，即任务集中对 所有的结点f ，一个外来任务执行时间为b 的概率为见，如果对于所有q ，均有见= p ，则 如，见：，心) 可表示为p ；同样地， 厶，如，厶 ，凡。 表示外来任务的松 驰量分布： ( 5 ) 尸，l 。) ：是结点j 上外来任务和传入任务的以时钟滴答数计算时 松驰量的分布情况，其中上。是最大松驰量，这个分布可以通过每个结点j 在线估 算； ( 6 ) c e 瓦：结点i 上任务的累积执行时间； ( 7 ) 丁泸( 乃，乃，丁乙) ：记录一个结点上的任务执行时间的有序队列，其中弓 = 咧，州， “是结点上有松驰量为j o ，1 ，厶。 的任务执行时间的记录， 而吲f o ，1 ，点二) ( 1 | + 1 ) 表示一个队列中的所有松驰量为_ ，的任务队列当 中第k 个任务所需要的执行时间( 如果没有七个松驰量为，的任务，则有吲= 0 ) 。之 所以5 以 倒州矗0 ，这样的形式表示，是由于一个结点在m l f s 原则下能排p l 具有松驰量为，的任务，这样只有最后一个松驰量为，的任务外所有的任务都只有一个 执行时间单元，并且在队列砀中没有松驰量小于，任务； ( 8 ) 门w ：表示结点f 的第，个优先结点； 中南大学硕士论文 ( 9 ) m j l ( ，) ：表示结点m - 】( ) 选择结点f 做为它的第，个优先结点； ( 1 0 ) s ：j 的大小为口的伙伴集，即s 。= m 。( ，) ，m 2 ( j ) ，m ，( m ) ) ； ( 1 1 ) s 是j 优先列表除的伙伴集中的结点外的所有结点的有序集合，例如 = ( m 。( m ) ，肘。( j ) ，吖。，( f ) ) ； ( 1 2 ) ：是圻1 ( m ) 的集合，1 打口，例如： 氍= m ) ，肘；( i ) ，m ，( m ) ； ( 1 3 ) 椰n 两次失败间的平均时间( j ) ； ( 1 4 ) z k ：平均任务执行时间； ( 1 5 )口：脚f 与珞。的比率； ( 1 6 ) 口：任务传递时间与的比率： ( 1 7 ) 彳r 排列在一个结点上的任务平均数目： ( 1 8 )屯：相邻结点间传递一个任务所需的时间，有a 芦= 屯成立； ( 1 9 ) 儿一：一个结点在【0 ，f 】上失败的概率密度函数： ( 2 0 ) ：一个结点上任务丢失的平均数； ( 2 1 ) 掣，：结点j 的( 外来) 任务队列； ( 2 2 ) 占? ，：结点f 的第- ，个备份队列。 2 2 系统模型 如图2 1 所示。应用一个有限状态空间s 上的连续时间的马尔可夫链( m a r k o v c h a i n ) 刷，f 0 来模拟一个结点的状态( c e r ) 的估计，在马尔可夫链中状态的转化以 一个转移矩阵q = 劬来表示，这里鼢( o i ，j n ) 是从状态j 到状态的一步转移概 率。在模型中需要的参数是 “ 只，l ，三。 ， 9 阮) ，l 七。 ，这些参数 必须由每个结点j 在线估计并在状态改变广播时向伙伴集中的其他结点广播。本文用非 先占式m l f s 规则来估计由任务接受，完成引起的c e 扎为了在一个有限状态空间中构 造一个连续的马尔科夫链，根据文献【4 6 】中的定理7 2 4 ：设蜀，局，五为相互独 立的随机变量，其分布为参数为k 的指数分布，令j 确斗为+ + 墨，则j 的分布为 爱尔朗分布j ，即： x 心 其中 0 ， 槛) ：j 蹀，分“p 。 ，k ) = ( 七一1 ) ! i o ，其他 斤为正整数。 中南大学硕士论文 本文假设每个接受排队的任务分配了肪1 个服务单元，其概率用q ，砂表示，l 局。，每个服务单元傥丁的消耗量服从参数为的指数分布，每个结点f 上c e 丁 外来任务 外来任务 “n 传出任务给其他结点 图2 1 系统模型 的消耗量( 单位时间执行一步，其c 丘r 消耗量为1 ) 近似地服从参数和的爱尔朗 ( e r l a n g ) 分布，并且当一一时爱尔朗分布更能精确反映事实( 例如当 = 1 ) 。本 文选择的值，使得从系统模型m 州e k 1 1 47 j 中所得到的概率尸( 砌6 f l 结点j 可 用 ( 见第4 章，即表示当结点j 正常时在时间f 内没有从结点接收到状态信息的概率) 与从系统模型m 【1 】e k + l 1 中所得的结果非常接近。根据文献【4 2 】的结果，当5 时， 对于任何的任务分配方式都能满足这个要求，所以本文选取 = l ，= 5 做为本文系统 的实验参数。 2 2 1 状态的定义 结点i 的状态可定义为h2 ( 胁；h ，；h ) ，这里巧可认为是结点f 上所有松 驰量为_ ，的任务的当前记录，玛2 w 矗；”坛- 是_ ，+ 1 个数的队列，认为是结点f 上所有 松驰量为_ ，的任务的当前记录，每个数鲜 0 ，1 ，。) 表示队列中第七个松驰量为- ， 中南大学硕士论文 的任务所分配的服务单元的个数。因为结点f 的所有松驰量为，的任务会根据其松驰量 大小从小到大来执行，所以结点最多能排列j + 1 个松驰量为j 的任务( 此时除最后一个 任务外所有任务需要一个执行单元的时问) 。 设c ：芝 f 表示所有松驰量为_ ，的任务所分配的服务单元的总数，k ，表示吩 队列中最后一个非0 值的序号，工一倒表示当前正在执行的任务的松驰量，即 上一( h ) = 一l ，当h = o ， i 最小的，使n ( 1 一岔o ，) ) = l ，当日o ，w o ) u t 砌：1 小巨。 ， j = 0 唯一的序号，当日o ，可，吖 o u 砌：1s 卅k ) 勰怖) = 伫盖仁如 例如，设系统参数为l 一- 3 ，b 。= 2 ，世= 4 ，由上式有上r ( o ；4 0 ；0 0 0 ；1 0 0 0 ) ) 一3 ，表 示当前正在运行的任务有3 个时间单元的松驰量，还有一个服务单元没有完成。同样， 。( ( 0 ；0 0 再4 0 ；8 0 0 0 ) 户2 ，表示在下一个状态转换之前没有松驰量为1 的任务到达的话， 就在下一个时间单元运行一个有两个时间单元松驰量和4 个服务单元的任务。 根据非先占的m l f s 原则，状态h 有以下的特征： ( 1 ) 咧是的整数倍，但 ? 可以例外，因为它表示当前正在执行的松驰量为 的任务所分配的服务单元数： ( 2 ) 状态空间数不超过n ( 碰。+ 1 ) ( e 一+ 1 ) 。，因而是有限的状态空问； ( 3 ) 当所有松驰量一1 的任务和当前正在执行的任务所分配的斑仉不大于 个执行时间单元时，本文才能接受排队一个带松驰量的任务，即仅当 ，- l 晦q ，w 【k ( h ) + 1 ，工。】或 j l 可c 。+ 俨”，w 【o ，k ( h ) 一1 】 1 0 时i o ，另外由三。佃的定义可知除日= o 外，工。，f ，肋 0 ； 【4 ) 因为排列在结点f 的每个松驰量为，的任务能按时执行，所以排列在它的前面 的所有任务的服务单元总数必须小于等于蟛，即有： j lh ( 乩卜l 蟛2 + 吲，w 【上一( ) + 1 ，k 】或 n 2 0n = l 中南大学硕士论文 卜l ，州i 。卜l 耐巳+ 卜+ 纠，w 【o ，三一( h ) 一1 】 例如，前面所说的系统模型，三一= 3 ，磊。= 2 ，足= 4 ，( 0 ；1 0 ；4 4 0 ；8 0 0 0 ) 是正确的状 态，而( 0 ；l o ：4 8 0 ；扣0 0 ) 是不正确的状态，因为那个有3 个时间单元松驰量和4 个服务 单元的任务( 下划线所示) 违背了( 3 ) 和( 4 ) 。又如，( o ；4 8 ；o o o ；8 0 0 0 ) 是正确的状 态，而( 0 ；4 墨；0 0 0 ；o o ) 是不正确的状态，因为在后一个状态中有个松驰量为3 的任 务( 下划线l 所示) 正在执行，因而那个有1 个单元松驰量和8 个服务单元的任务( 下 划线8 所示) 根据( 3 ) 和( 4 ) 不能排队在本结点上。 正如( 2 ) 所示，状态空间的大小是有限的，但事实上，根据( 1 ) 、( 3 ) 、( 4 ) 可 知，状态空间数远远小于( 2 ) 所给的值，不过其大小会随上。，e 。以及丘的增加而 显著地增大，但是象下文所述，马尔科夫链所对应的转换矩阵是很稀疏的，所以，可以 利用矩阵的稀疏特性来有效地存贮稀疏矩阵以减轻计算的困难，例如文献【3 9 】中所述的 s e r t 算法。 2 2 2 转换率的确定 引起状态转换的任务活动有两种：结点f 上任务的接受；结点f 上c e r 的消耗。根 据m l f s 调度原理，、当在有序的任务队列砀插入一个新到来的任务时，会引起本结点 的任务接受，也可能会引起原来排列在结点上的有些任务不能按时完成，因而必须传递 给其他有处理能力的结点。 2 2 2 1 任务接受而引起的状态转换 假设系统处于状态，当接受一个松驰量为j ( 1 ，厶和执行时间为m 的任务 时，系统的状态会转换到状态叫。= ( 域；叫：h ：) ，则有： ( 1 ) c 。，= c ，即h h ，1 j ，一l ，即松驰量，一l 的任务不受接受任务的 影响； ( 2 ) h i 等于h ，也许最后几项( ，+ 1 j 工一) 用。代替，所以c ：c ，就是 说，因为新任务的插入，原来有松驰量大于，的任务必须传出； ( 3 ) 功中非。项数不大于f ，并且h j _ 纠f ，乞) j 渤o o 。即叫由肠中非零项后 紧接数勋l ( 后可能跟有几个0 使项数为f + 1 ) 组成； 。 ( 4 ) 根据非占用的算法下，其相应的转换率为： g h ，片；“= ，p iu ) 吼( m ) c 厅8 c 七c e r ( d 。 ( 2 1 ) 俺t 。唧( e ，巧) z 赫一”讲一丁h 嘶r ( f ) + ( 1 一c 。唧( 皿，叫) ) 丁碱一丁砌，妒r ( r ) ：妻k “， 中南大学硕士论文 这里c 沁c k j e t ( 1 ) 五r o ( c ) # 0 m p ( h i h 11 l n s k 0 t p n 托啦r m 阳s k h 口咄r ( ) 的表达如 下： i ， i 岔( 日一c ，) ， 当ks ， e c 七一 f ( ，) = ： i 岔( 尉一( c ，+ 卜州) ) ，当k ， l= o z p r o ( c ) = ，i c j = o ) 碱鳓= ：； 魏硼 z 缸i 一丁k 咖，( f ) = ( 胁一( t + 形) ) j = o= l f l 伽i ( h ) x ) ( c j + 嘭) 一鼢) ) ， 当f = 三一( 日) 且胁f ( h ：) 2 ， j 卸j = 1 f l ) ( ( c j + 叫) 一曲) ， 当f = 厶。( h ) 且伽f ( q ) = l ， o 卜i船f 【) 一1 ( 髓一( c ：+ 嘭) ) j = 0= l 卜1k f ( 爿】 ) ( c ：+ 巧) 一船) ) ， 1 0j 1 当，= 三。( h ) 且，5 r ( 日：) = o ， 当f 厶。( h ) 且伽f ( q ) o ， ) ( c j 一厨) ，当， l 。( 日) 且栅r ( 叫) = o ， j = 0 p l ( “) 一1 岔( 鼢一( c j + 巧+ 砰一m ) ) j = 0，；l 卜i 蛔i i “】 x ) ( ( c j + 巧+ 卜”) 一鳓，当f ( ( c j + _ l l 卜”1 ) 一蔚) ， 当f l ， = 0= i r lm ( 巩l l 岔( 廊( c j + 嘭+ 而卜) ) 当f k ，= o j i 上面各式的具体含义是： ( 1 ) 第一个因子丑a ( ，) g | 咖) 是结点，上带松驰量为个时间单元，册个执行单元 时间的任务的到达率： ( 2 ) 第二个因子c 亿c 七f 力说明仅当下面两个情况之一成立时结点j 才能接受 排队最新到达的带松驰量为? 的任务； 如果当前正在执行的任务的松驰量小于等于，则必须满足带松驰量小于等于， 的任务所分配的c e r 小于等于f ，即 日c ， ，= o 如果当前正在执行的任务的松驰量大于，则必须满足带松驰量小于等于，的 任务和正在执行的任务所分配的c e r ，； ( 3 ) 最后一个因子说明了接受到达的任务所引起的任务传递，因为插入一个带松驰 量为z 的新任务将仅仅影响松驰量 ，的任务，所以仃仅执行从= f + 1 到f = 厶。 范围内那些使白o 的项。在满足条件c h e c k - f 形下，v f 【f + 1 ，上一】，如果以下条 件之一成立，转换将以五，以( ? ) 叮。( m ) 的比率发生。 日，= h j 并且带松驰量为，的所有任务在插入新任务以后还能按时完成： 卜l船f ( h ，) 一l 缸c j + 嘭， j 柚i t ，- im ( 乩) 一l 尉c j + 嘭+ 厅卜州， j = oj = l 当前正执行的任务的松驰量， 当前正执行的任务的松驰量 f 除最后的船f ( 只) 一f c 吲( 日：) 项为。外，圩。和叫是相等的，即，甜f 似j ，黜f ( 叫) 个带松驰量为f 任务必须传递出去。例如，在f k ( h ) 的情况下，当且仅当 ，一i ，4 “( r 卜卜l c j + 蟛蔚和 j = 0j t l 中南大学硕士论文 两式成立时有f 个带松驰量为，的任务必须传递出去，同样可以得到f 工( 何) 的情 况。 2 2 2 2c e t 消耗所产生的状态转换 根据前面的假设，单位时间执行一个服务单元，c e r 的消耗近似服从参数为k 的 e r l a i l g 分布，而且在每个单位时间的结束( 即每k 个服务单元结束) 时所有的松驰量都 必须减1 ，这说明个任务的松驰量必须根据当前时间来度量，即，系统从h 转换到 j 一，= ( h ：；日j ：h ：一) ，其概率为 ：擘羔：k 饵) ， ( 2 2 ) 9 吣2 1 0 ， 其他 【2 2 ) 这里： ( 1 ) 如果( j 一1 ) 岳 k 珊：l m e 。，) u o ) ，贝0 片i = ( 卜1 ) 日：砍。，而且w f ，日j = q ； ( 2 ) 如果( f - 1 ) ：1 肌e 一) u o ) ，则 日l 一2 0 ， h l = 日j + l = ? “ j “，w 【o ，f 一2 】u 【，三。一l 】， m 一1 ) m 叫，如果 b 1 ， 目，= j o ，如果 卜l 2 2 2 3 马尔科夫链的状态转换矩阵q 中最后一个非0 转换率为： ”一( 莓。+ 莩m 一。卜g “ 因为每个结点上的一个状态的逗留时间服从指数分布，而且系统下一个状态仅仅依 赖于当前状态以及在当前状态下发生的任务接受完成情况，所以，根据以上方法构造 的模型是一个连续时间的马尔科夫链。马尔科夫链的状态转换矩阵中除了2 卜2 3 式所 表示的转换率不为o 外的其他项都为o ，从而转移矩阵很稀疏的。 例如在系统模式= 3 ，既。= 2 ，= 4 下，状态( o ：1 0 ：4 0 q ：4 8 0 0 ) 仅仅能转换 到( 0 ：4 0 ：4 8 0 ：0 0 0 0 ) ，( o ：1 4 ：4 0 0 ：4 0 0 0 ) ，( 0 ：1 8 ：0 0 0 ：4 0 0 0 ) ，( 0 ：1 0 ：4 4 0 ：4 4 0 ：4 0 0 0 ) ，( 0 ：1 0 ： 2 嵇 h 嘭 篁川 _ 暮 c h 瑚 中南大学硕士论文 4 8 0 ：0 0 0 0 ) ，( o ：l o ：4 0 0 ：4 8 0 0 ) 等六种状态，其相应的转换率为斤，丑a ( 1 ) 吼( 1 ) ， 五，n ( 1 ) 吼( 2 ) ， n ( 2 ) g j ( 1 ) ， 只( 2 ) g f ( 2 ) ，一( k + p ，( f ) 吼( m ) ，如图7 2 所示。而 i 掣崽2 转换( 0 ；l o ；4 0 0 ；4 8 0 0 ) 一( 0 ：1 0 ；4 0 0 ：4 8 卸) 是不可能的，因为最近到达带松驰量为3 ， 的任务( 下划线4 所示) 将不会被接受( 因为由c ， 魁，得c 强e “一c b f ( ，) = o ) 。又 j = 0 如转换( o ；l o ；4 0 0 ；4 8 0 0 ) 一( 0 ：1 0 ：4 8 0 ：4 0 0 0 ) 也是不可能的，因为队列中带松驰量为 3 和执行时间为4 个服务单元( 下划线4 所示) 的任务在插入新任务以后必须传递出去 ( 有松驰量为3 和执行时间为8 个服务单元的任务也不例外) 。 图2 2 从状态( 0 ：1 0 ：4 0 0 ：4 8 0 0 ) 出发可能的状态转换图 ( 系统参数为= 3 ，e ，。= 2 。膏= 4 ) 同样地，从状态( 0 ：4 0 ：0 0 0 ：1 4 0 0 ) 出发能转换的状态有( 4 ：0 0 ：4 0 0 ：0 0 0 0 ) ，( 0 4 0 ：4 0 0 ：1 4 0 0 ) ，( 0 ：4 0 ：8 0 0 ：1 0 0 0 ) ，( 0 ：4 0 ；0 0 0 ：1 4 4 0 ) ，( o ：4 0 ：0 0 0 ：1 4 8 0 ) ，( 0 ： 4 0 ：0 0 0 ：1 4 0 0 ) 六种状态，其对应的转换率为儿 a ( 2 ) 吼( 1 ) ， a ( 2 ) g ，( 2 ) ， 中南大学硕士论文 p ，( 3 ) g ( 1 ) ， p ，( 3 ) q 。( 2 ) ，一( k + 丑p 。( f ) q ，( m ) 。但是( o ：40 o o o ：1 4 0 0 ) 一( o ： 2 划s 3 i s m i 2 4 4 ：0 0 0 ：1 4 0 0 ) 的转换是不可能的，因为当前正在执行的任务的松驰量为3 ( 由厶。 ( ( 0 ：4 0 ：o o o ：1 4 0 0 ) ) = 3 可知) ，新任务带松驰量f = 1 ，所以由 j q + 卜州 l m 可知此新任务不能被接受。 2 3 算法描述 下面对本文所提出的动态负载共享算法做个总结性的描述。 动态负载共享算法 f o r 每个结点刀d o b e g i n 当乃任务( 执行时间蜀，松驰量厶) 到达结点n 时 确定其在任务队列9 的位置厶使得厶工“ i f 当前时间+ b 厶m e n i = l b e g i n 在结点n 的优先列表中寻找可用的目标结点； 把任务正传递给目标结点： 调整目标结点及其最优先结点的备份任务队列： e n d e l s e b e g i n i f 当前时间+ 局厶t h e n ，；l b e g i n 在优先列表寻找可用的目标结点； 把死任务从队列删去，传递给目标结点； 调整本结点和目标结点及其相应的最优先结点的备份任务队列； e n d e n d i f 当前伍7 n 横过z 巧( 即从小于珊到大于强争或相反) t h e n 4 曲 p 曲 g 川 的 + 扫 l | n 七毗 r 呈； 知 中南大学硕士论文 b e g l n 向本结点力的伙伴集所有其他结点广播下列信息 ( 1 ) 带时间戳的c e 矗值； ( 2 ) 。，