（计算机应用技术专业论文）服务计算避免死锁和活锁的资源分配算法研究.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学、计算机应用技术 研究方向：计算机通信与网间互连技术 作者：汤楠 指导教师：章韵副教授 iiyiiiiii11111t11111111175 5 03 1 峨 y 题目：服务计算避免死锁和活锁的资源分配算法研究 英文题目：r e s e a r c ho nd e a d l o c ka n dl i v e l o c kf r e er e s o u r c ea l l o c a t i o n a l g o r i t h m i ns e r v i c eo r i e n t e dc o m p u t i n g 主题词：服务计算，资源分配，死锁，活锁，多维背包问题( m k p ) k e y w o r d s ：s e r v i c eo r i e n t e dc o m p u t i n g ，r e s o u r c ea l l o c a t i o n ，d e a d l o c k ，l i v e l o c k , m k p ( m u l t i p l e - d i m e n s i o nk n a p s a c kp r o b l e m ) 南京邮电大学硕士研究生学位论文 摘要 摘要 服务计算作为一种新型的网络计算方式，目的是为用户提供一种全面共享各种资源的 计算环境，当前已成为分布式计算的最新发展方向。在服务计算环境中，服务资源的分配 管理是服务计算领域的一大研究热点，系统资源层怎样满足每个服务实例的资源分配需 求，保证其成功执行而不陷入死锁和活锁，是确保上层组合服务正常运行的重要问题。已 有的服务计算方面的研究大多关注于应用层和服务实例层，对系统资源层的相关研究还不 多见。 本文首先对服务资源分配过程中的死锁和活锁问题进行了分析，建立了基于有限状态 机f s m ( f i n i t es t a t em a c h i n e ) 的服务资源分配模型s r a s ( s c r v i c er e s o u r c ea l l o c a t i o n s y s t e m ) ，并制定了服务资源分配的基本策略。在此基础上，进一步设计了可以避免死锁和 活锁的服务资源分配算法d l f - r a a ，它采用并发请求资源的方式和基于资源排序的预防死 锁策略，该算法的子算法s s f 将下一状态的选择问题归化为m k p ( m u l t i p l e d i m e n s i o n k n a p s a c kp r o b l e m ) i 高 题来解决。通过仿真试验分析了上述算法的性能和适用情况，验证了 算法理论分析的正确性。 本文提出的资源分配模型比较完备地研究了服务计算底层系统资源层所涉及的资源 一 分配问题；提出的资源分配算法不需要并发服务实例之间消息通信，能够有效避免服务资 源分配过程中的死锁和活锁，表现出较高的性能。 关键词：服务计算，资源分配，死锁，活锁，多维背包问题( m k p ) 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t a san e wn e t w o r kc o m p u t i n gp l a t f o r m , s e r v i c eo r i e n t e dc o m p u t i n ga i m st op r o v i d ea n i n f r a s t r u c t u r ef o ru s e r st om a k eu s eo ft h ea c r o s s t h e - b o a r ds h a r i n gr e s o u r c e s ，a n di sb e i n gt h e l a t e s td e v e l o p m e n to fc u r r e n td i s t r i b u t e dc o m p u t i n g i ns e r v i c ec o m p u t i n ge n v i r o n m e n t , t h e r e s o b r c ea l l o c a t i o na n dm a n a g e m e n ti sa ni m p o r t a n tr e s e a r c hf o c u s s y s t e mr e s o u r c el a y e rh o w tom e e tt h er e s o u r c ea l l o c a t i o nr e q u i r e m e n to fe a c hs e r v i c ei n s t a n c ea n de n s u r ei t ss u c c e s s f u l e x e c u t i o nw i t h o u tf a l l i n gi n t od e a d l o c ka n dl i v e l o c k , i sa l li m p o r t a n ti s s u et ot h es u c c e s s f u l l y r u n n i n go fu p p e rc o m p o s i t es e r v i c e s e x i s t i n gr e s e a r c hm o s t l yf o c u so na p p l i c a t i o nl a y e ra n d s e r v i c ei n s t a n c el a y e r , r a t h e rt h a ns y s t e mr e s o u r c el a y e r w ef i r s t l ya n a l y z e dt h er e a s o no fd e a d l o c ka n dl i v e l o c ki ns e r v i c er e s o u r c ea l l o c a t i o na n db u i l t s e r v i c er e s o u r c ea l l o c a t i o nm o d e ls r a sb a s e do nf i n i t es t a t em a c h i n e ( f s m ) o nt h eb a s i so f s r a s ，w ee s t a b l i s h e dt h ep o l i c i e so fr e s o u r c ea l l o c a t i o n a f t e r w a r d ，w ed e s i g n e ds e r v i c e r e s o u r c ea l l o c a t i o n a l g o r i t h md l f - r a aw i t hp a r a l l e lr e q u e s t s ，w h i c ha d o p t so r d e r - b a s e d d e a d l o c kp r e v e n t i o n s t r a t e g y a n dt h ec h o i c e o fn e x ts a f es t a t ep r o b l e mi sf o r m u l a t e d 嬲 m k p ( m u l t i p l e d i m e n s i o nk n a p s a c kp r o b l e m ) i ns u b a l g o r i t h ms f f t h r o u g h s i m u l a t i o nt e s t w ea n a l y z e dt h ep e r f o r m a n c ea n da p p l i c a b i l i t yo ft h ea l g o r i t h m , a n dp r o v e dt h ec o r r e c t n e s so f t h e o r e t i c a la n a l y s i s r e s o u r c ea l l o c a t i o nm o d e lp r e s e n t e di n t h i sp a p e rc o m p l e t e l ys t u d i e st h er e s o u r c ea l l o c a t i o n p r o b l e mo fu n d e r l y i n gs y s t e mr e s o u r c el a y e r t h er e s o u r c ea l l o c a t i o na l g o r i t h md o e sn o t r e q u i r em e s s a g ec o m m u n i c a t i o nb e t w e e nt h e s e r v i c ei n s t a n c e s ，a n dc a i l e f f e c t i v e l ya v o i d d e a d l o c ka n dl i v e l o c ki ns e r v i c er e s o u r c ea l l o c a t i o np r o c e s sw i t hs h o w i n gah i g hp e r f o r m a n c e k e y w o r d s ：s e r v i c eo r i e n t e dc o m p u t i n g ，r e s o u r c ea l l o c a t i o n , d e a d l o c k ，l i v e l o c k , m k p ( m u l t i p l e d i m e n s i o nk n a p s a c kp r o b l e m ) 南京邮电大学硕士研究生学位论文 目录 目录 摘要i a b s t r a c t i 目录i i 缩略词 第一章绪论l 1 1 研究背景l 1 2 研究现状2 1 2 1 服务计算研究和发展现状2 1 2 2 分布式资源分配研究现状3 1 3 研究目标和内容5 1 4 论文组织结构5 第二章服务计算的资源分配问题7 2 1 服务计算概述7 2 1 1 服务的概念7 2 1 2 服务计算的概念8 2 1 3 面向服务的体系架构( s o a ) 8 2 1 4w 曲服务技术1 1 2 2 服务计算的资源分配管理一1 2 2 2 1 服务计算分层模型1 2 2 2 2 服务资源管理系统( s r m s ) 1 3 2 3 问题的提出一l5 2 3 1 死锁问题1 5 2 3 2 活锁问题18 2 4 本章小结2 0 第三章服务资源分配的建模及分配策略2 l 3 1 服务资源分配模型2 l 3 1 1 有限状态机f s m 的基本原理2 l 3 1 2 服务资源分配建模的相关数学定义2 2 3 1 3 基于f s m 的服务资源分配理论模型2 3 3 2 服务资源分配策略2 5 3 2 1 服务资源分配的特点2 5 3 2 2 服务资源分配的两种基本策略一2 5 3 3 本章小结2 7 第四章服务资源分配算法2 8 4 1 服务资源分配过程的安全性2 8 4 2 服务资源分配算法2 9 4 2 1 避免死锁和活锁的服务资源分配算法d l f - r a a 3 0 1 1 南京邮电大学硕士研究生学位论文 目录 4 2 2 安全子集查找子算法s s f 3 2 4 3 本章小结。3 6 第五章基于g r i d s i m 的资源管理仿真系统。3 7 5 1 网格仿真工具介绍3 7 5 2 主流模拟器的比较4 1 5 3 嘶d s i m 简介一4 2 5 3 1g - r i d s i m 体系结构4 3 5 3 2s i m j a v a 包z 辫 5 3 3g r i d s i m 实体和v i s u a lm o d e l e r 组件4 4 5 3 4 仿真模拟步骤4 6 5 4 仿真实验设计与评估4 6 5 4 1 性能参数介绍4 6 5 4 2 仿真环境设置和编译厶4 7 5 4 3 仿真结果分析4 8 5 5 本章小结5 0 第六章总结与展望5l 6 1 论文工作总结5l 6 2 下一步工作展望5 l j g 【谢5 2 参考文献5 3 攻读硕士期间论文发表情况一5 8 n i 南京邮电大学硕士研究生学位论文 缩略词 缩略词 c p n d l f - r a a f s m g i s g s c j v m o d p 2 o d p 3 q o s s a a s s d r a s s o c s o a s r a s s r a s s r m s s s f 缩略词 英文全称中文 c o l o r e dp e t r in e t s有色p e t r i 网 d e a d l o c ka n dl i v e l o c kf r e er e s o u r c e 避免死锁和活锁的资源 a l l o c a t i o na l g o r i t h m分配算法 f i n i t es t a t em a c h i n e有限状态机 g r i di n f o r m a t i o ns e r v i c e网格信息服务 g l o b a l l ys y n c h r o n i z e dc l o c k 全局同步时钟 j a v av i r t u a lm a c h i n ej a v a 虚拟机 o r d e r - b a s e dd e a d l o c k p r e v e n t i o n 基于资源排序的死锁预 p r o t o c o l 防算法 o r d e r - b a s e d d e a d l o c k p r e v e n t i o n 基于资源排序的并发请 p r o t o c o lw i t hp a r a l l e lr e q u e s t s 求式死锁预防算法 q u a l i t yo f s e r v i c e服务质量 s o r w a r e 龉as e r v i c e软件即服务 s i n g l e s t e p d i s t r i b u t e dr e s o u r c e 单跳分布式资源分配系 a l l o c a t i o ns y s t e m s统 s e r v i c eo r i e n t e dc o m p u t i n g服务计算 s e r v i c eo r i e n t e da r c h i t e c t u r e面向服务的体系架构 s e q u e n t i a lr e s o u r c ea l l o c a t i o ns y s t e m s 顺序资源分配系统 s e r v i c er e s o u r c ea l l o c a t i o ns y s t e m服务资源分配系统模型 s e r v i c er e s o u r c e m a n a g e m e n t 服务资源管理系统 s y s t e m s a f es u b s e tf i n d安全子集查找算法 i v 南京邮电大学硕士研究生学位论文第一章绪论 1 1 研究背景 第一章绪论 2 0 0 3 年，在i e e e 的推动下，服务计算( s o c ，s e r v i c eo r i e n t e dc o m p u t i n g ) 的概念正式被 提出，经过多年的发展，服务计算已经成为网络和分布式计算研究领域中的一个重要课题， 并逐渐成为在开放、异构网络环境下构造松耦合、组合化分布式应用的一种主流技术。它 作为一种新兴的网络计算模式，强调软件的广泛重用、松散耦合、可动态优化和在线扩展， 能够有效支持异构资源的集成和共享，以及企业业务流程的敏捷部署，提高服务应用者的 市场竞争力。因而服务计算的构建及相关科学理论问题成为企业和学术研究的热点。 服务计算基于面向服务的体系架构( s o a ，s e r v i c eo r i e n t e da r c h i t e c t u r e ) ，旨在通过服 务资源的抽象描述、组织、管理以及服务的动态组合，支持广域开放环境下的应用协同汇 聚以实现灵活高效的资源共享【l 】。服务是服务计算中最基本的元素，它独立于系统平台， 面向高层应用提供一组功能性操作，而使用户不必过多地关注其具体实现技术。 从功能模块来说，服务计算模型分为三个层次：应用层、服务实例层和系统资源层。这 三个层次主要解决以下三个方面的问题【2 】：业务流程聚合和管理，服务选择和组合，以及 服务资源管理。业务流程聚合和管理旨在根据业务流程控制逻辑和应用逻辑在用户层面上 提供业务处理流程的建模技术及其服务工作流的设计方法，它产生由多个服务结点组成的 工作流，各服务结点仅包含功能需求的描述，而无需指定具体的服务调用实例。服务选择 在众多具有相同功能的大量服务实例中选择一组服务实例进行组合以形成组合服务，并使 得组合服务在满足业务流程功能的基础上，尽量具有良好的服务质量( q o s ，q u a l i t yo f s e r v i c e ) 。服务资源管理处于服务计算模型的最底层，作为服务实例运行的支撑系统，它协 同分配服务实例运行时所需的资源，确保服务实例的成功运行，优秀的服务资源管理系统 需要提高服务实例的并发数，并避免并发服务实例请求资源时出现的死锁和活锁。 国内外的许多学者在上述服务计算模型的应用层和服务实例层上做了很多的研究工 作【3 jo 】，取得了丰硕的成果。但是，在系统资源层服务资源分配管理方面的研究工作却做 的比较少。所有服务选择方面的研究总是假设候选服务实例在运行过程中对系统资源层的 资源请求总是能够得到满足，而对于资源请求过程中很有可能出现的死锁活锁问题却很少 有人关注。 在服务计算资源分配过程中，通常是许多并发服务实例去竞争相对有限的共享资源， 1 堕室墅皇奎兰堡主婴壅竺兰垡丝茎 翌二雯堑望 这就会出现所谓的死锁和活锁现象。死锁，就是在某一资源分配状态一组并发的活跃服务 实例被永久阻塞，因为每一服务实例都分配占有了该组中另外某一服务实例请求的资源。 活锁，就是资源分配过程中服务实例反复分配和释放资源而不向前，不能保证所有需要的 资源最终能够分配【1 1 1 。 现今，服务计算面向的是大规模开放环境，资源呈现出异构性、分布性、动态性和隶 属于多管理域等特点，这些特点使得系统资源层如何避免服务资源分配过程中可能出现的 死锁活锁问题成为一大挑战，亟待解决。 1 2 研究现状 1 2 1 服务计算研究和发展现状 目前，服务计算作为一门独立的计算学科，已经得到国内外学术界的热烈关注。近几 年来，各个学术组织、研究机构纷纷创办了多个以服务计算为主体学术期刊，比如：i e e e t r a n s a c t i o n so ns e r v i c e s c o m p u t i n g ，i n t e r n a t i o n a lj o u r n a l o fw e bs e r v i c e sr e s e a r c h ， i n t e r n a t i o n a lj o u r n a lo f w 曲s e r v i c e sp r a c t i c e s 等。同时也形成了一系列有重要影响的专题国 际会议，比如：i c w s 、i c s o c 、s c c 等。而国内两大计算机界顶级权威期刊计算机学报 和软件学报组织了多次服务计算的专刊。在以上国内外重要期刊和会议上，涌现出一 大批研究成果，内容覆盖服务模型、服务语言、服务技术、服务方法、服务工程等方面， 极大推动了服务计算学科的向前发展。现在，在服务计算研究领域较为活跃、有重要影响 的国内外学术机构及研究团队如下： 荷兰大学的信息实验室( n a f o l a b ) 是最早提倡服务计算的研究组织之一。以m i c h a e lp p a p a z o g l o u 为代表的研究人员扩展了标砖的s o a ，提出了x s o a 体系，并以此为基础提出了 服务计算研究路线图，明确了服务计算的研究范畴、研究内容和研究方向。该研究路线图 得到了广大研究者的认可，是服务计算研究成果中引用率较高的成果之一。 美国卡耐基梅隆大学的智能软件a g e n t 实验室将语义w e b 技术引入到服务计算中，提出 了语义w e b 服务的概念，并成为制定第一个语义w e b 服务描述语言d a m l s 的主要力量。 美国乔治亚大学的大规模分布式信息系统实验室在其m e t e o r s 项目中致力于将语 义技术应用于服务标注、q o s 描述、服务发现、服务组合、服务流程管理中，提出了语义 w e b 流程概念，实现了基于语义的服务发现基础架构和服务组合框架。此外，该实验室联 合i b m 推出的基于w s d l 的轻量级语义w e b 服务描述语言w s d l s ，对语义w e b 服务的发展 2 南京邮电大学硕士研究生学位论文 第一章绪论 和应用起到了比较大的推动作用。 澳大利亚新南威尔士大学的服务计算研究小组在其早期的s e l f s e r v 项目中致力于 研究服务的快速组合与执行，以b e n a t a l l a hb 为代表的研究人员提出了基于p e e r - t o - p e e r 的服 务流程执行方式。此后，该研究小组又在服务及服务组合的q o s 、服务的协同适配、服务 计算中的信任管理以及移动环境中的服务计算等方面做了较多有影响力的研究工作，是目 前服务计算研究领域重要研究团队之一。 中科院计算技术研究所属下的网格与服务计算研究中心，是国内最早开展网格和服务 计算研究的团队之一。该中心研制的v i n c a 服务网格平台，支持按需即时的服务集成和业 务系统构造，并已用于电子政务、企业信息化管理领域。该平台提出了一个支持服务资源 动态整合、业务应用按需构造的聚合方法体系c a f i s e ，并提供相应开发工具集，以及面向 服务计算的开放环境下的业务终端编程语言v i n c a ，可以使得业务用户快速构造业务应 用。 1 2 2 分布式资源分配研究现状 分布式资源分配中解决死锁问题比较常用的策略有两种：死锁预防( d e a d l o c kp r e v e n t i o n ) 和死锁检测( d e a d l o c kd e t e c t i o n ) 。死锁预防是通过选择一些限制条件，破坏产生死锁的4 个 必要条件之一或其中几个，从而使系统不发生死锁。洲( o r d e r - b a s e dd e a d l o c kp r e v e n t i o n p r o t o c 0 1 ) 是典型的采用死锁预防策略的算法，它预定义了系统中各类资源的线性全局次序， 并要求每个应用按升序来逐一获得所需资源，从而保证应用不会陷入死锁【1 2 】【1 l 】。而死锁检 测是定期检测应用的资源分配状态，一旦发现存在死锁，就通过撤消一个或多个处于死锁 的应用来解除死锁【1 3 】【1 4 】。 服务计算环境中，并发的服务实例请求数量巨大，资源相对紧张，导致死锁会频繁发 生。这种情况下，死锁预防比死锁检测更适用于服务计算【l5 1 。死锁检测的缺点在于：( 1 ) 死锁检测需要应用之问进行大量的消息交换，执行时间较长，系统开销较大，所以它在大 规模服务计算环境中扩展性较差；( 2 ) 服务计算环境下，共享同一资源而隶属于不同管理域 的应用之间可能互不知道对方的存在，它们之间难以交换消息，因此需要一个中心结点控 制管理应用之间的消息交换，但是，分布式的服务计算环境难以构建这样一个中心管理结 点，这意味着死锁检测所必需的应用之间的消息交换存在问题。基于同样原因，一些需要 中心结点管理死锁的分布式资源分配方法也不适用于服务计算，例如基于全局同步时钟提 供系统唯一进程号的方法【1 6 1 和基于原子组播提供组播消息全局序号的方法【1 7 1 。 3 南京邮电大学硕士研究生学位论文 第一苹绪论 在分布式资源分配避免死锁和活锁方面，j o n g h u np a r k 等学者做了大量的研究工作，他 提出ts d - r a s ( s i n g l e - s t c pd i s t r i b u t e d 掀的u r c ea l l o c a t i o ns y s t e m s ) 资源分配模型，并基于该模 型阐述了一种分布式死锁预防算法一删( o r d e r - b a s e dd e a d l o c kp r e v e n t i o np r o t o c o lw i t h p a r a l l e lr e q u e s t s ) ，它的特点是并发发送资源请求，且不需要应用之间消息交换。 顺序资源分配系统( s r a s ，s e q u e n t i a lr e s o u r c ea l l o c a t i o ns y s t e m s ) 根据资源请求构成的 不同可以分为4 类【1 8 】：( 1 ) s i n g l e u n i tg h s ( s u g a s ) ，进程为成功执行只要请求一个单位的某 一种资源即可；( 2 ) s i n g l e - t y p er a s ( s t r a s ) ，进程为成功执行需要请求多个同一种资源； ( 3 ) c o n j u n c t i v er a s ( c r a s ) ，进程为成功执行需要请求多个不同种资源； ( 4 ) c o n j u n c t i v e d i s j u n c t i v er a s ( c d r a s ) ，进程为成功执行具有多个( 3 ) 中所述合取 ( c o n j u n c t i v e ) 型资源请求目标，只要满足其中任何一个目标即可。由于存在多个资源请求目 标，c d r a s 具有灵活的资源分配选择。 而s d r a s 就属于c d r a s 的一种，它由并发应用集和有限资源集构成【l9 1 ，其资源分配 行为可形式化为有限状态机，不同的应用具有不同的目标资源分配状态，每个应用的目标 资源分配状态也不唯一。应用可以只发送一次并发资源请求就获得它需要的所有资源，即 一步直接到达目标资源分配状态。s d r a s 的资源分配行为是具有选择性的顺序资源分配， 这表现在：( 1 ) 应用可能需要多步状态转移和多次状态选择，才能获得所有需要的资源；( 2 ) 应用可以在多个目标资源分配状态之间动态选择合适的资源分配方案。在服务计算中，系 统资源层的资源分配问题与上述模型非常相似，同样存在大量并发服务实例竞争有限资源 的情况，每个服务实例也都具有多个目标资源分配状态。本文在研究服务资源分配问题时 借鉴了s d r a s 模型。 j o n g h u np a r k 提出的o d l 9 算法，开始就向应用需要的所有资源发出并发请求，逐步扩 大已分配资源的集合，并保证发送请求之后得到的每个中间状态都是避免死锁和活锁的， 从而最终到达某一目标资源分配状态。而o d p e 贝j j 是按照资源的线性排序逐一发送资源请 求，在成功获得所申请的上一个资源之后才能发送下一个资源的请求，这种顺序资源请求 方式会导致应用等待时间过长，大幅降低o d p e 的效率。相比之下，支持多目标状态的o d p s 算法效率更高。但是，o d l 9 发送并发请求后所获得的资源，与先前的已分配资源直接合并 后所得到的资源分配状态不一定是避免死锁和活锁的，而避免死锁和活锁的中间资源分配 状态一定是这一并集的子集。这类子集选择问题是n ph a r d l 2 0 6 j 题，o d l 9 将其归化为k p 问题，以c p n ( c o l o r e dp e t r in e t s ) 中多重集距离作为k p 问题的目标函数，但并未提出明确有 效的子集选择算法。因此，o d l 9 至少存在两个问题亟待深入研究：( 1 ) o d f 算法选用多重 集距离作为目标函数是否合理，在后面的章节中我们将考虑到资源价值的因素，以其作为 4 堕室堕皇奎堂堡圭受壅生堂垡垒奎 箜二童篁笙 _ _ 。、- _ 。_ n - _ _ _ _ - _ _ - _ _ _ - _ _ - - - _ _ - - _ _ - _ _ _ _ _ _ _ _ - _ _ - _ i _ _ _ - - _ - i _ - l - _ _ _ - _ _ - _ _ _ _ - _ - _ _ _ _ _ 。- 。1 一一一一一一一 新的目标函数；( 2 ) 针对子集选择问题，如何找到一种有效的启发式算法。 1 3 研究目标和内容 在服务计算模型的三个研究层次中，本文的研究定位于最底层的系统资源层，解决并 发服务实例请求调用服务资源时引起的死锁和活锁问题，提出新的避免死锁和活锁的资源 分配启发式算法。通过设计服务资源管理仿真系统，与现有的资源分配算法比较性能，验 证本文提出的避免死锁和活锁的资源分配启发式算法的优越性。 为了实现上述研究目标，需要进行以下课题的研究： ( 1 ) 服务计算资源分配的形式化模型 针对服务计算的特点，提出描述服务资源分配的形式化模型，在此模型下，清晰地给 出死锁和活锁的形式化定义，为下一步展开避免死锁和活锁的资源分配问题的研究奠定基 础。 ( 2 ) 避免死锁和活锁的资源分配启发式算法 由于避免死锁和活锁的资源分配是n p h a r d 问题，在上一步形式化模型的基础上，提 出避免死锁和活锁的资源分配启发式算法，从理论上证明该算法能够避免死锁和活锁，并 证明该算法的收敛性。 ( 3 ) 服务计算资源管理仿真系统的设计与实现 设计并实现服务计算资源管理仿真系统，验证本文提出的避免死锁和活锁的资源分配 启发式算法的优越性。 1 4 论文组织结构 本文的组织结构为：第一章为研究背景和研究现状调研；第二章至第四章为理论研究 部分；第五章为系统实现部分；第六章总结全文。具体安排如下： 第一章主要介绍本文研究工作的背景及意义，综述服务计算和分布式资源分配死锁活 锁问题的研究现状，概括既有研究成果的优势及其对本文的启发，指出既有研究成果中亟 待解决的问题，由此引出本文的研究目标和研究内容。 第二章概述服务计算的相关概念，在提出服务计算三层模型的基础上，阐述了底层系 统资源层资源分配中的死锁活锁问题。 第三章从有限状态机f s m 的原理和多重集的相关概念入手，提出基于f s m 的服务资源 分配模型，并分析了服务资源分配的基本策略。 s 南京邮电大学硕士研究生学位论文第一章绪论 第四章研究基于f s m 服务资源分配模型下的资源分配问题，在对安全状态作出相关定 义的基础上，提出避免死锁和活锁的资源分配启发式算法。 第五章介绍仿真工具c _ 豇i d s i m 的设计和实现，通过g r i d s i m 网格模拟器对本文提出的服 务资源分配算法进行仿真实验，对实验结果进行分析和评价。 第六章对论文的研究工作进行了总结，并指出还存在和有待继续研究的问题，对未来 的研究工作作了展望。 6 南京邮电大学硕士研究生学位论文第二章服务计算的资源分配问题 第二章服务计算的资源分配问题 在服务计算环境中，底层系统资源层需要解决的一个重要问题是如何满足服务实例的 资源分配需求，保证其顺利执行，而不陷入死锁和活锁。本章首先介绍了服务计算的相关 概念，详细讨论了s o a 的基本框架和基本元素，阐述了服务计算的分层抽象模型，分析 归纳了模型底层系统资源层的资源分配问题死锁和活锁。 2 1 服务计算概述 伴随着计算机、网络技术的发展，传统的以一次开发、持续使用为特征的软件开发理 念和开发方法日渐落伍。如何解决企业应用系统“随需应变”的问题是当前软件业的热点， 也是制约软件产业再度变革的关键所在。服务计算正是为解决这一问题而提出来的一种新 型计算模式。 2 1 1 服务的概念 在计算机科学研究领域，服务迄今为止并没有统一明确的定义，但从现实世界的抽象 层面理解，服务是通过应用程序、机器或人来实现的一种活动。从软件开发的角度看，服 务是一个能够提供特殊功能的可重用构件2 1 1 。 软件即服务( s o i l w a r ea sas e r v i c e ，s a a s ) 的概念在2 0 世纪9 0 年代中后期出现【2 2 1 ，其 中提出了软件从供应牵引到需求牵引的转变，并强调软件的拥有者与软件的用户分离。尽 管s o c 与s a a s 是两个不同的概念，但二者之间存在很多相似点，比如服务描述、发布、 查找等。比较而言，s a a s 偏重于软件的商业模式，提出了一种软件的传递模型；s o c 则侧 重于提供服务的软件框架及实现规范。而两者可以互相补充，s a a s 为s o c 提供了一个很 好的概念模型，s o c 为s a a s 概念的实现提供了很好的平台和框架。 由此可见，服务在不同的背景下有着不同含义，从软件的角度来讨论和研究服务，本 文中讨论的服务具有以下几个特点： ( 1 ) 服务是一个可被发现的能够提供某些具体功能的可重用构件； ( 2 ) 服务具有严格的接口描述，其中包含有关如何使用服务的信息，服务用户只能够 得到服务的接口描述； ( 3 ) 服务是独立的、无状态的、松耦合的和可组合的。 7 南京邮电大学硕士研究生学位论文第二章服务计算的资源分配问题 乏：1 2 服务计算的概念 服务计算目前已经成为工业界和学术界的新热点，但迄今为止还没有统一的概念。随 着服务计算的不断发展，其定义和内涵也在不断变化。 从分布式计算的角度看，o r l o w s k am e 和w e e t a w a r a n as 等人认为，服务计算是从面 向对象和面向构件的计算演化而来的一种分布式计算模式，它使分布在企业内部或跨越企 业边界的不同商业应用系统能实现快捷、灵活的无缝集成与互相协作口3 1 。 从软件系统设计与开发的角度，p a p a z o g l o um p 认为，服务计算是一种以服务为基本 元素进行应用系统开发的方式【2 4 1 。 从服务技术的应用角度，s i n g hm p 和h u l m sm n 认为，服务计算是集服务概念、服 务体系架构、服务技术和服务基础设施于一体，指导如何使用服务的技术集合【2 5 1 。 从学科的角度，i b m 的张良杰博士认为，服务计算是一门跨越计算机与信息技术、商 业管理与咨询服务的基础学科，其目标在于利用服务科学和服务技术消除商业服务和信息 技术服务之间的鸿沟【2 6 1 。 以上的各种定义是在服务计算的不同发展阶段形成，侧重点各不相同，但相互之间没 有冲突。综合以上观点，本文认为，服务计算是面向动态、多变、复杂的网络环境而提出 的- - n 新的计算学科，它以w c b 服务、面向服务的体系架构( s o a ) 为基础支撑技术，以服 务组合为主要软件开发方法，以面向服务的软件分析和设计原则为基本理念。服务计算的 技术体系中，服务是最重要的核心概念，这里的服务是指基于网络环境具有自适应性、自 描述、模块化和良好互操作性的软件实体，w e b 服务则是符合该要求的一种具体表现形式 和功能载体。 2 1 3 面向服务的体系架构( s 0 h ) 面向服务的体系架构是构建大规模、分布式应用的最新架构思想，它被视为解决当前 复杂软件系统中长期存在的复杂度和相关度问题的最新方法，是服务计算技术体系的核心 和基础。 s o a 的概念最初由g a r t n e r 公司于1 9 9 6 年提出【2 7 1 ，但由于当时的网络和市场环境不成 熟，s o a 并没有得到广泛的关注。随着互联网的飞速发展，出现了越来越多的应用领域， 如电子商务等，从而引起了许多公司及组织的广泛关注，越来越多的公司和组织把自己的 业务范围扩展到了这些应用领域。为了解决功能模块的独立性、互操作性和可扩展性等问 8 南京邮电大学硕士研究生学位论文第二章服务计算的资源分配问题 题，w c b 服务框架被提出，并迅速得到了广泛应用。由于网络上存在着大量的w c b 服务， 它们由不同的平台所提供或不同的语言所实现，人们试图寻找一种统一的架构来认识、管 理和维护这些服务，s o a 重新引起了大家的注意。 目前尚未有一个统一的、为业界广泛接受的s o a 定义，但普遍认为，面向服务的架 构是一个组件模型，它将应用程序的不同功能单元服务，通过服务间定义良好的接口 和契约联系起来。接口采用中立的方式定义，独立于具体实现服务的软硬件平台、操作系 统和编程语言，使得构建在这样的系统中的服务可以使用统一和标准的方式进行通信。这 种具有中立接口的定义的特征被称为服务问的松耦合。 s o a 是面向服务的软件系统在体系结构层面的基本交互模式【2 1 1 ，其主要目标是通过构 建、组织、管理可重用的服务来提高1 1 r 公司响应业务需求的能力，包括服务的松耦合和互 操作能力，服务的可重用、抽象及可组装，以及在现有服务基础上更快构建复杂业务流程 的能力等。 服务请求者服务提供者 图2 1s o a 的基本框架 图2 1 中描述了s o a 的基本框架，它定义了3 种角色：服务提供者、服务注册中心和 服务请求者。服务提供者负责服务的具体实现，并把服务接口、服务访问地址等信息的描 述发布到服务注册中心。服务注册中心相当于一个服务中介，服务请求者可从这里查找、 定位所需服务。服务注册中心是实现间接寻址的关键，它要提供服务的发布、删除、查询 和更新机制，同时也可