（计算机应用技术专业论文）协同cad系统中并发控制的研究.pdf

哈尔滨理t 大学i t 学硕上学位论文 协同c a d 系统中并发控制的研究 摘要 近年来由于计算机技术在工程设计领域的广泛应用，使c a d ( 计算机辅 助设计1 技术迅速发展起来。协同c a d 系统是c s c w 技术的一个典型应 用。它支持不同地理位置的多个设计者通过分工协调和随时随地的交流合作 完成同一个制图设计任务，满足了人们在信息社会中工作模式的要求，已成 为一个研究热点。但由于各方面的局限性，目前的协同c a d 系统还不完 善，本文对其核心问题并发控制进行了研究。 为了能够保证协同设计各站点模型的一致性，本文针对目前协同特征造 型系统中的并发控制大都采用并发冲突防止策略的锁机制，从而并发度受到 很大限制的问题，为了提高协同设计的并发度，对协同设计中的并发控制问 题进行了深入的研究，其主要工作如下： ( 1 ) 对协同设计的操作对象特点及协同设计过程中出现的并发冲突做了 简要分析和归类，根据主流三维c a d 设计中基于特征的设计特点分析和总 结了特征模型中的特征依赖关系，根据特征依赖关系的工程语义给出了一个 基于特征依赖关系的并发冲突定义。 ( 2 ) 利用特征依赖图对整个特征模型中的特征依赖关系进行层次化组 织，提出了一个高效的基于特征依赖关系的并发冲突检测算法，详细介绍了 算法流程，并对其做了详细的分析，根据冲突检测的结果进行相应的冲突解 决，提出了基于角色的冲突解决方法和多版本机制。 ( 3 ) 针对基于用户角色的访问控制模型存在的不足，提出一种增强型模 型e r b a c ，通过定义工作组权限集来增强角色权限的灵活性，支持多角色 动态分配、角色继承、负权限以及权限继承，更加适用于大型动态协作系 统，同时还结合用户身份验证和数据加密技术，增强了协同系统的安全性。 ( 4 ) 构建完善了协同h u s t - c a i d 原型系统，并在系统中运用了本文提出 的并发控制策略和访问控制机制。详细介绍分析了协同系统框架和功能模 型。结果证明本文提出的并发控制机制是有效的、可行的、成功的。 关键词协同设计；并发控制；特征依赖关系；并发冲突 - i 哈尔滨理工大学工学硕+ 学位论文 r e s e a r c ho nc o n c u r r e n c yo fc o l l a b o r a t i v ec a d s y s t e m a b s t r a c t a sc o m p u t e rt e c h n i q u ei sw i d e l yu s e di ne n g i n e e r i n gd e s i g nf i e l di nr e c e n t y e a r s ，c a dt e c h n i q u ei sd e v e l o p i n gf a s t e ra n df a s t e r c o l l a b o r a t i v ec a ds y s t e m i sat y p i c a lb r a n c ho fc s c w i ts u p p o r t sag r o u po fd e s i g n e r sf r o md i f f e r e n ts i t e s t oa c c o m p l i s ht h es a m ed e s i g nb yc o o p e r a t i n ga n dc o m m u n i c a t i n gf r e e l yw i t h e a c ho t h e r , w h i c hm e e t st h em o d e mp a t t e r no fi n f o r m a t i o nt e c h n o l o g ya n dh a s b e c o m eap r o m i s i n gr e s e a r c h n o w a d a y s ，c o l l a b o r a t i v ec a ds y s t e m sa r en o t p e r f e c t b e c a u s eo fs o m el i m i t a t i o n s t h e r e f o r e ，t h ec o n c u r r e n c y c o n t r o l m e c h a n i s mo fc o l l a b o r a t i v ec a ds y s t e mi sc a r e f u l l ys t u d i e di nt h i sp a p e r i no r d e rt om a i n t a i nt h ec o n s i s t e n c yo ft h em o d e l so fc o l l a b o r a t i v ed e s i g n s ， l o c k e dm e c h a n i s mi su s e dt op r e v e n tc o n c u r r e n c yc o n f l i c t sc o n s i d e r i n gm o s t c o n c u r r e n c yc o n t r o li n t h er e c e n tc o l l a b o r a t i v ef e a t u r em o d e l i n g ，t h u sl i m i t i n g t h ec o n c u r r e n c yg r a n u l a r i t yt oal a r g ee x t e n t t oi m p r o v et h ec o n c u r r e n c y g r a n u l a r i t yo fc o l l a b o r a t i v ed e s i g n ，t h i sp a p e rd e e p l ys t u d i e s t h ec o n c u r r e n c y c o n t r o lo fc o l l a b o r a t i v ed e s i g n ，i n c l u d i n gt h ef o l l o w i n gm a i na c t i v i t i e s ： 1 t h ec h a r a c t e r i s t i c so fs h a r e do b j e c t sa r ea n a l y z e da n dt h ec o n c u r r e n c y c o n f l i c t si nc o l l a b o r a t i v ed e s i g na r cc l a s s i f i e d b a s e do nt h ea n a l y s e s ，ac o n c e p t o ff e a t u r ed e p e n d e n c yi sp u tf o r w a r da n db a s e do ni t ，an e wd e f i n i t i o no f c o n c u r r e n c yc o n f l i c tf o rc o l l a b o r a t i v ed e s i g ni sp r e s e n t e d 2 t h er e l a t i o n s h i po ff e a t u r ed e p e n d e n c yo fc o l l a b o r a t i v em o d e li sr e - o r g a n i z e di n t oa h i e r a r c h i c a lg r a p h a ne f f i c i e n ta n db a s e do nf e a t u r ed e p e n d e n c y c o n c u r r e n c yc o n f l i c td e t e c t i o na l g o r i t h mi sp r o p o s e d i ti n t r o d u c e st h ea l g o r i t h m i nd e t a i la n da l s om a k e sad e t a i l e da n a l y s i s a n da c c o r d i n gt ot h er e s u l t so ft h e c o r r e s p o n d i n gc o n f l i c td e t e c t i o n ，ar o l e b a s e d c o n f l i c tr e s o l u t i o nm e t h o d sa n d m u l t i v e r s i o nm e c h a n i s m sa r ep u tf o r w a r d i l - 哈尔滨理工大学工学硕士学位论文 3 c o n s i d e r i n gt h ew e a k n e s so fr o l e - b a s e d a c c e s sc o n t r o lm o d e s ，a n a d v a n c e dm o d ee r b a ci si n t r o d u c e d t h er o l e s p e r m i s s i o n sb e c o m em o r e f l e x i b l eb yd e f i n i n gw o r k g r o u p s p e r m i s s i o n ，a n de r b a ca l s os u p p o r t sm u l t i p l e r o l e sd y n a m i c a l l ya s s i g n e d ，i n h e d t e dr o l e s ，n e g a t i v ep e r m i s s i o n sa n di n h e d t e d p e r m i s s i o n s ，e s p e c i a l l ya d a p t e dt ol a r g ec o l l a b o r a t i v es y s t e m s a n da tt h es a m e t i m e ，i ts t r e n g t h e n st h es e c u r i t yo f c o l l a b o r a t i v e s y s t e m sb yi n t e g r a t i n g a u t h e n t i c a t i o na n dd a t ae n c r y p t e dt e c h n o l o g y 4 ac o l l a b o r a t i v eh u s t - c a i dp r o t o - s y s t e mi sb u i l ta n di m p r o v e di nt h i s p a p e r w i t ht h es t r a t e g yo fc o n c u r r e n c yc o n t r o la n da c c e s sc o n t r o lm e c h a n i s m s u s e di nt h es y s t e m a f t e rd e t a i l e di n t r o d u c t i o no ft h ef r a m e w o r ka n df u n c t i o n a l m o d e so ft h ec o l l a b o r a t i v es y s t e m ，i tp r o v e st h ep r o p o s e dc o n c u r r e n c yc o n t r o l m e c h a n i s mt ob ee f f e c t i v e f e a s i b l ea n ds u c c e s s f u l k e y w o r d sc o l l a b o r a t i v ed e s i g n ，c o n c u r r e n c yc o n t r o l ，f e a t u r ed e p e n d e n c y r e l a t i o n ，c o n c u r r e n c yc o n f l i c t s i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文协同c a d 系统中并发控制的 研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表 或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：卸建哥 日期：1 年月日 哈尔滨理工大学硕士学位论文使用授权书 协同c a d 系统中并发控制的研究系本人在哈尔滨理工大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大 学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨 理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论 文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密凹。 ( 请在以上相应方框内打) 作者签名： 导师签名： 印糊 i 如钐维 日期：7 年弓月伽日 日期：w ( 年弓月伽日 哈尔滨理t 大学工学硕：l 学位论文 第1 章绪论 1 1c a d 技术的发展历程 计算机辅助设计( c o m p u t e r - a i d e dd e s i g n ，c a o ) 技术最早起步于2 0 世纪5 0 年代后期，以美国i v a ne s u t h e r l a n d 博士在其论文“s k e t c h p a d - 一种人 机对话系统 中提出概念为标志n 2 1 。早期的c a d 系统主要用于二维绘图。 6 0 年代出现的三维c a d 系统只是极为简单的线框式系统。这种初期的线 框造型系统只能表达基本的几何信息，不能有效表达几何数据间的拓扑关系。 由于缺乏形体的表面信息，c a m 及c a e 均无法实现。 、 进入7 0 年代之后，c a d 系统将绘图功能与几何数据管理结合起来，支持 二维交互绘图、曲面造型和三维几何造型。此时法国人提出了一种贝赛尔算 法，使得人们在用计算机处理曲线及曲面问题时变得可以操作，同时也使得法 国的达索飞机制造公司的开发者们，能在一维绘图系统c a d 的基础上，开发 出以表面模型为特点的自由曲面建模方法，推出了三维曲面造型系统 c a t i a 。它的出现，标志着计算机辅助设计技术从单纯模仿工程图纸的三视图 模式中解放出来，首次实现以计算机完整描述产品零件的主要信息，同时也使 得c a m 技术的开发有了现实的基础。曲面造型系统c a t i a 为人类带来了第 一次c a d 技术革命，改变了以往只能借助油泥模型来近似准确表达曲面的落 后的工作方式。 8 0 年代初，基于对c a d g 嗵一体化技术发展的探索，s d r c 公司于 1 9 7 9 年发布了世界上第一个完全基于实体造型技术的大型c a d c a e 软件一i d e a s 。由于实体造型技术能够精确表达零件的全部属性，在理论上有助于统 一c a d 、c a e 、c a m 的模型表达，给设计带来了惊人的方便性。它代表着未 来c a d 技术的发展方向。基于这样的共识，各软件纷纷仿效。一时间，实体 造型技术呼声满天下。可以说，实体造型技术的普及应用标志c a d 发展史上 的第二次技术革命。 进入8 0 年代中期，c v 公司内部以高级副总裁为首的一批人提出了一种比 无约束自由造型更新颖、更好的算法一参数化实体造型方法。从算法上来说， 这是一种很好的设想。它主要的特点是：基于特征、全尺寸约束、全数据相 关、尺寸驱动设计修改。当时的参数化技术方案还处于一种发展的初级阶段， 1 - 哈尔滨理工大学工学硕士学位论文 很多技术难点有待于攻克。 9 0 年代初期，参数化建模技术不断完善，并出现了特征建模技术，特征建 模技术是一种高抽象层次的建模方法，它能够包含特征、参数和约束等建模信 息，提高了c a d 系统的性能，同时计算机硬件的发展，使得c a d 系统的成本 和价格也得到了降低，微机版c a d 系统的出现，加速了c a d 技术的普及。 在9 0 年代中期，r b i d a r r a 和w f b r o n s v o o r t 提出了基于细胞元 表示的语义特征造型阻1 ，该方法有效的克服了原有造型技术在构建造型过程 中基于历程的缺点，它使得造型构建过程不再基于历程，并能包含特征、参数 和约束等上层抽象信息。同时人们还进一步提出了面向智能化、集成化、网络 化的新一代c a d 技术。 1 2 计算机支持的协同设计 近些年来随着计算机网络技术的快速发展和日益成熟，以网络为技术基础 的科学活动环境成为了当前国际计算机技术研究的热点和前沿领域，已经引起 了学术界的高度重视。设计活动也突破了时间和空间上的制约，逐步达到以计 算机支持的协同工作为特征的高度并行、分布、开放和协同的工作模式。 计算机支持的协同工作( c o m p u t e rs u p p o r t e dc o o p e r a t i v ew o r k , c s c w ) 最早 是在1 9 8 4 年美国m 盯的i r e n eg r e i f 和d e c 公司的p a u lc i a s h m a n 两位 研究人员提出来的，用于描述他们所组织安排的如何用计算机支持来自不同领 域和学科的人们共同工作的课题，并缩写为c s c w 喊 。它的基本含义是在计 算机技术支持的环境中，一个群体协作地完成一项共同的任务。从它的出现之 初，c s c w 就被认为是一个全新的研究领域。实现c s c w 系统的关键技术 有：群体工作理论；协同多媒体通信；冲突解决与协调机制；共享对象与并发 控制；多用户界面与人一人交互接口；网络安全性；基于w e b 的协同工作 等。与并行工程相比，c s c w 更加突出人的作用，强调相关活动的各方面人员 ( 包括设计、制造、销售、管理、服务、甚至客户) 的协同工作，协同工作的思 想认为在未来的全球化企业竞争中，只有使来自不同专业领域、具有不同经验 技能的专家彼此问共享知识、交流思想、激发灵感，才能有效地实现产品设计 的创新，这样才能立于不败之地。 计算机支持的协同设计( c o m p u t e rs u p p o s e dc o o p e r a t i v ed e s i g n ，c s c d ) 是 c s c w 与先进制造技术相结合，并对产品设计过程进行有效支持的研究领域， 是一个以知识为基础的计算过程呻一。它是指两个或者两个以上来自不同专业 2 哈尔滨理t 大学t 学硕。 ：学位论文 领域的设计专家，通过一定的信息交换和相互协同机制、共享关于产品设计的 信息和知识，从而提高产品设计过程中决策的正确率，减少返工次数，加速决 策的过程，进而提高设计的效率。 c s c d 系统比单纯c a d 系统复杂，表现在以下方面：( 1 ) 它应该是运行在 网络环境下；( 2 ) 各c a d 系统是自治的、任务分工明确的；( 3 ) 各c a d 系统之 间围绕设计进行交互和协同；( 4 ) 涉及过程或进程要有协调控制；( 5 ) 对设计数 据、版本和结果要进行协同控制。通常来讲，组建的c s c d 系统应具备下列集 成的技术特性：( 1 ) 高速带宽网络，保证三维的、多媒体信息数据的正确可靠传 输；( 2 ) - - 维高性能c a d 工作站，能够进行异地数字化设计和数字化装配；( 3 ) 提供实时交互的计算机多媒体会议系统，具有音频、视频、白板、黑板和其他 共享应用功能；( 4 ) 对分布式异构数据库、设计数据、版本和结果进行协同控制 和管理。 协同c a d 是从二十世纪九十年代发展起来的新兴的产品设计方式n 。 从斯坦福大学设计研究中心的c u t k o s k y 等人开始的对协同c a d 方面的最 初的探索到c s c w 技术与c a d 的各个分支领域相结合，不断向底层和深层发 展。目前，协同c a d 已经成为国际上c a d 领域的一大研究热点。现有研究工 作大体上可分为q 邺f x 工具的分布集成、异步协同设计、同步协同设计、 协同装配设计等。 协同设计系统的类型是多种多样的，根据各个站点在协同中的地位和分布 情况，协同设计系统可以分为集中式协同设计系统和复制式协同设计系统，以 及混合式协同设计系统；根据各个站点的响应情况，可以分为同步协同设计系 统和异步协同设计系统；根据各个站点中采用的c a d 系统的相似与否，可以 分为同构系统和异构系统等。在实际应用中，可以根据具体需要采用不同的协 同设计系统，如复制式异构同步协同设计系统。 早期的协同c a d 大部分都是异步协同设计系统。异步协同设计是一种松 散耦合的协同工作。其特点是：多个协作者在分布集成的平台上围绕共同的任 务进行协同设计工作，但各自有不同的工作空间，可以在不同的时间内进行工 作，但通常不能迅速地从其他协作者处得到反馈信息。其代表性的工作有斯坦 福大学的c u t k o s k y 领导的s h a r e 项目和m a d e f a s t 项目，加州大学伯 克利分校的w r i g h t 等人研究开发的c y b e r c u t 系统，k i m 等人开发的 c y b e r v i e w 系统，香港中文大学s h i 等研究了支持分布应用之间通过i n t e m e t 进 行协同的代理a g e n t 方法n 2 1 3 1 等。 而同步协同设计是一种紧密藕合的协同工作，多个协作者在相同的时间 - 3 哈尔滨理_ t 大学工学硕上学位论文 内，通过共享工作空间进行设计活动，并且任何一个协作者都可以迅速地从其 他协作者处得到反馈信息n 钉。因此近年来，其正在成为协同设计领域研究的 热点之一。这方面的代表性研究工作主要有：韩国的l e e 等人开发的基于 w e b 的协同特征造型系统n e t f e a t u r e n 钔，荷兰d e l f t 大学b i d a r r a 等开发的基 于特征的协同建模系统w e b s p i f f n 朝，德国的l u k a s 等人研发的和香港的 c h a n 等人开发的c s m 系统n 引。 1 3 并发控制的研究现状及发展趋势 虽然人们针对并发控制问题做了大量工作，但在协同设计系统中因为 c a d 模型数据量庞大以及模型复杂度、耦合度高等不同于其它协同系统或分 布式系统的特殊性，已有的并发控制算法在协同设计系统中并不适用，这使并 发控制成为近几年来构建协同设计系统时一个亟待解决的问题晗。 1 3 1 国外相关领域研究状况 现有的针对基于复制式结构的同步协同设计系统比较有代表性的工作有： 英国n a m 等人开发的c o l l i d e 环境和s y c 0 3 d 系统吻1 、德国l u k a s 等人开 发的t o b a c o 1 等。我们通过分析以上两个典型的复制式同步协同设计系统 中的并发控制机制来了解人们对于复制式结构的同步协同设计系统中的并发冲 突解决的基本看法，并根据所给的并发冲突和用户对复制式结构的协同系统的 要求来分析适合于复制式同步协同设计系统的并发方法。 c o l l i d e 环境是为多个协同用户使用独立的c a d 系统提供接口的插件程 序，s y c 0 3 d 则是在c o l i i d 基础上设计的基于复制式结构的同步协同设计系 统。c o l l i d e 环境使用了p r i v a t es t a g e s h a r e ds t a g e 结构，分离用户在不同时刻 需要的不同设计平台，例如用户在平时只关注p r i v a t es t a g e ，而在需要协同时 通过锁机制允许用户单独将p r i v a t es t a g e 中的结果提交到s h a r e ds t a g e 进行协 同。这种并发控制机制实际是一种并发防止机制，因为相同两个用户不在具有 一致性的s t a g e ( s h a r e ds t a g e ) q b 进行同步协同设计，因而避免了并发的产生。 这种并发控制方法的缺陷在于系统支持的并不是实际意义上的同步协同设 计，而更接近同步协同装配。用户需要在开始时就被分配不同的设计任务，而 不是自由的进行协同工作。用户如果在协同过程中没有及时的提交自己的设计 结果，将导致分配任务的相交部分严重冲突，甚至无法协调。 t o b a c o 环境也是一个对当前的常见设计工具进行封装的集成协同插 4 哈尔滨理丁大学工学硕士学位论文 件。t o b a c o 利用c o r b a 进行网络通讯，传递。狮命令来更新结果模型， 并通过任务管理器和历史纪录来辅助协同过程。t o b a c o 中主要通过地板控 $ o ( f l o o r c o n t r 0 1 ) 的方法进行并发控制。这种并发控制机制是非常严格的，在 t o b a c o 中只有令牌( t o k e n ) l 拘拥有者才能对结果模型进行改变，其他用户此 时只能对结果模型做视角变换等不影响数据结构的操作。 这种并发控制方法的缺陷在于系统通过锁的方式避免了并发操作的产生， 并因此避免并发冲突的产生。在绪论中我们提到复制式系统的设计初衷即为了 实现系统的快速响应和高并发。但由于采用了严格的地板控制，t o b a c o 无 法实现系统所需的高并发性。这种方法与操作结果更新频率相对较高的异步协 同设计并没有区别，用户很难通过这种类似于异步( 一个操作结果被用户确认 之后才进行下一个操作) ，但却对用户具有同步要求( 协同时必须注意力集中) 的 协作方式大大提高设计效率。 1 3 2 国内相关领域的研究状况 周勋在n e t c o s m o s 系统中采用了冲突检测与解决的方法他劓。系统中以特 征操作粒度，通过特征在生成站点与其它特征的相对位置关系和在远程站点执 行后相应的相对位置关系比较的异同作为判别并发冲突的标准，然后对存在冲 突的操作做序列跳。这一机制提高了协同设计系统的并发度，在设计过程中设 计者不再受任何限制。不过其中的并发冲突定义没有考虑不同用户对不同粒度 的要求，没有充分考虑特征间的约束关系，冲突判断需要在操作执行以后进 行，在此基础上的冲突处理方法可能影响系统的稳定性。 李氓提出了一个特征粒度下的锁机制并发控制方法瞳5 她2 7 1 。该方法以特征 为加锁对象，当设计者要修改某个特征时需要使用基于r i c a r - a g r a w a l a ( r - a ) 算 法的锁申请机制来取得对这个特征的控制权。不过这种基于特征的锁机制只适 用于特征修改操作，对于协同设计过程中的其它操作还无法支持。 1 4 并发控制研究发展趋势 同步协同设计是网络信息时代具有广泛应用前景的设计方式，而并发控制 是实现同步协同设计系统的核心和关键。但是由于协同设计系统操作对象的特 殊性和紧祸合性，使得针对协同设计的并发控制仍没有得到较好的解决，特别 是复制式同步协同设计系统的并发控制机制研究还处于初步阶段。 当前协同设计系统的并发控制绝大多数都是采用并发冲突防止策略的锁机 5 哈尔滨理t 大学工学硕上学位论文 制，这种并发控制方法对协同设计用户有着较大的限制，致使系统的并发度受 到了很大影响啪确1 。如何根据协同设计系统的特点，设计适用于协同设计系 统、适当粒度、高并发度、鲁棒的基于并发冲突检测与解决的并发控制机制是 未来协同设计并发控制研究的重点和难点。本文在这样的研究背景下，通过对 同步协同设计系统的深入分析，结合三维c a d 设计系统的设计方式和特点， 力图提出套行之有效的并发控制机制。 1 5 课题的来源及研究内容 1 5 1 课题的来源 本课题全名为“协同c a d 系统中并发控制的研究 ，来源于国家自然基金 资助的项目“基于细胞元表示的语义特征模型和“哈尔滨理工大学计算机辅 助工业造型系统( h u s t - c a i d ) 的实际发展需要和驱动。针对协同设计过程中 存在冲突的问题研究并发控制机制，改进和发展相关的关键技术，将研究成果 有效的应用到h u s t - c a i d 系统中。所以本课题的研究具有重要的理论意义和 实用价值，属于计算机图形学和q 蛐领域的应用基础研究的前沿课题。 1 5 2 立论目的和意义 随着i n t e r n e t 技术的发展，许多跨行业、跨地区的虚拟型企业应运而生。 协同设计与制造作为一种新兴的产品开发方式，受到企业的欢迎，它使得分布 在不同地理位置上的产品开发人员通过网络在各种各样计算机辅助工具的支持 下协同地进行产品的设计与制造工作。并且企业间希望通过应用现有的网络技 术和协同框架，来支持有单机单用户操作环境向分布式环境的转变，协同 c 加技术随之发展。 目前的协同设计系统尚不完善，特别是在并发控制方面做得不够，绝大多 数都是采用并发冲突防止策略的锁机制，这种并发控制方法对协同设计用户有 着较大的限制，致使系统的并发度受到了很大影响。本课题在前期研究成果的 基础上，将着重于协同设计中并发控制的研究，进一步改进现有的并发控制方 法，提高协同设计工作的效率，进而结合哈尔滨理工大学c a d 应用技术研究所 所开发的拥有自主知识产权的h u s t - c a i d 系统，对自主开发的计算机辅助工 业造型系统( h u s t - c a i d ) 做进一步的改善。本课题属于c a d 领域的应用基础研 6 哈尔滨理工大学t 学硕十学位论文 究的前沿课题，具有一定的理论价值和使用价值。 1 5 3 研究的基本内容 本课题将从理论和原型系统开发两个方面对协同设计中的并发控制问题进 行理论的研究和实际的验证。根据协同设计过程中可能的冲突进行相应的并发 控制，引入基于特征依赖关系的并发控制机制，并用实际的原型系统进行验证 和改进，最后将把该系统引入到自主开发的计算机辅助工业造型系统( h u s t - c a i d ) 中，从而提高协同设计的效率。因此，本课题的研究内容主要包括： 1 对于协同设计中的并发控制问题进行系统地分析和研究，指出当前并 发控制研究的现状、问题以及以后的发展趋势。 2 对协同设计的操作对象特点及协同设计过程中出现的并发冲突做了简 要分析和归类，根据主流三维c a d 设计中基于特征的设计特点，分析和总结 了特征模型中的特征依赖关系，根据特征依赖关系的工程语义给出了一个基于 特征依赖关系的并发冲突定义。 3 利用特征依赖图对整个特征模型中的特征依赖关系进行层次化组织， 提出了一个高效的基于特征依赖关系的并发冲突检测算法，详细介绍了算法流 程，并对其做了详细的分析，根据冲突检测的结果进行相应的冲突解决，提出 了基于角色的冲突解决方法和多版本机制。 4 针对基于用户角色的访问控制模型存在的不足，提出一种增强型访问 控制模型e r b a c ，通过定义工作组权限集来增强角色权限的灵活性，支持多 角色动态分配、角色继承、负权限以及权限继承，更加适用于大型动态协作系 统，同时还结合用户身份验证和数据加密技术，增强了协同系统的安全性。 5 构建完善了协同h u s t - c a i d 原型系统，并在系统中运用本文提出的 并发控制策略和访问控制机制。 7 哈尔滨理t 大学t 学硕：仁学位论文 第2 章基于特征依赖关系的并发冲突分析 2 1 引言 并发冲突检测与解决作为并发控制的基本策略之一，其首要问题是对并发 冲突给出一个恰当的定义3 1 捌。但到目前为止，针对协同设计并发冲突定义 的工作还比较少，只有周勋在其n e t c o s m o s 系统中提出基于特征间相对位 置关系的并发冲突定义，但该定义没有考虑不同用户对不同粒度的要求，没有 考虑特征其本身所有的工程语义，而且在该定义基础上的冲突检测和处理办法 可能造成系统的不稳定和不连贯。因此，本章将就并发冲突问题进行详细的分 析和研究以给出一个更适当的并发冲突定义标准和判断规则。 2 2 协同设计中的并发冲突分析 协同系统中的并发冲突定义，抑或并发控制其它相关问题如冲突检测、冲 突解决方法等，都是和特定的领域相关的，不同的应用领域有着不同的标准和 方法随弛删。因此，本节首先对协同设计系统中操作对象的特点以及协同设计 过程中的并发冲突进行必要的分析总结，以明确协同设计中并发冲突的表现形 式及产生原因，为并发冲突定义的提出提供相应的依据。 2 2 1 协同设计中操作对象的特点 当前主流三维c a d 设计系统大多采用的是基于特征的设计方式，所以本 文选择特征作为协同设计的基本操作对象，此后的讨论也是指基于特征的协同 设计。协同设计中模型的特征有其不同的特点和约束，总体来说有以下三个特 点： 1 模型中的特征可能是相互关联而不是独立的。一个特征的变动有可能 对其它特征造成影响。如图2 1a ) 所示模型，孔与槽两个特征看似并没有联 系，但从设计语义来说这两个特征之间的相对位置应该是分离的。如果两个并 发操作在互不了解的情况下一个增大孔的半径而另一个改变槽的位置，这两个 操作执行后结果使两个特征相交从而有悖于实际设计语义。如图2 - 1b ) 和图2 - 1 c ) 所示两个操作的执行结果如图2 1d ) 。 8 哈尔滨理工大学工学硕士学位论文 nr 1r 1n l - - 一u - l - 。一 n 原模型 b ) 左移槽0 增大孔半径 d ) 冲突模型 b ) l e f t g r o o v e曲i n c r e a s eh o l er a d i u sd ) c o n f l i c t m o d e l 图2 - 1 不同特征的并发修改冲突示倒 f i g 2 - 1 e x a m p l eo fc o n c u r r e n c y m o d i f i c a t i o no f d i f f e r e n t f e a t u r e 2 模型中同一特征的不同参数也可能是相互关联的。正如上面提到的不 同特征存在关联的可能性，针对特征的不同参数也因此变得有关联可能，因为 对不同参数的修改也可能影响到其它特征。如图2 - 2 所示，两个操作b ) 和c ) 分 别修改槽的两个参数，一个改变其位置，一个改变其宽度，这两个并发操作的 最终结果也改变了槽与孔的相离关系。 nr 可厂n - l i l 一- l jl i a ) 原模型b ) 左移槽c ) 增大槽宽 d ) 冲突模型 a ) i n i t i a l m o d e lb ) l e f t g r o o v ec ) i n c r e a s eg m o v e w i d ed 1 c o n f l i c t m o d e l 图2 - 2 同一特征不同参数修改的冲突示例 f i g2 - 2 e x a m p l eo f c o n f l i c t o f m o d i f i c a t i o n o f d i f f e r e n tp a r a m e t e r s t oa f e a t u r e 3 特征在生成之后，其各种设计参数不允许系统为了达到某种目的而自 行修改。如图2 - 2 ，为了保证两个并发操作b 1 和c ) 执行后孔和槽的相离关系保 持不变，系统自行改变孔在基台上的位置来达到要求是不被允许的。这个限定 是出于保证设计者意图和模型语义的考虑，在设计中特征的形态表现、坐标定 位等是设计者主观意图和模型语义需求的体现，如果系统被允许私自修改其中 的相关数据可能导致设计者意图或模型语义被破坏。 从以上三个特点中可以看到特征模型的藕合度很大，针对一个特征的变动 可能对其它多个特征的语义表达产生影响，这使协同设计中并发操作发生冲突 的具体表现形式变得复杂多样。因此，在进一步讨论协同设计的并发冲突定义 9 哈尔滨理工大学工学碗士学位论文 之前有必要先对协同设计过程中各种繁杂多样的冲突形式进行总结分类。 2 2 2 协同设计中并发冲突的分类 通过上述特征在协同设计中的三个特点可以知道协同设计产生并友冲突的 两个主要原因，即不同站点的设计者所关注的模型局部不同咀及对模型的相同 特征进行并发操作。除了这两个主观原因外，还有一个客观原因就是网络通讯 的延时也会引发冲突。根据这三个主要的主客观原因大致可以把协同设计中的 并发冲突分为以下四类： 1 因果冲突由于网络延时而导致某一站点生成的本地操作不能实时地传 送到其它站点，造成不同站点接收到协同操作的顺序可能各不相同，即操作到 达的乱序性。操作乱序到达必然造成一些存在因果时序关系的操作在到达不同 站点时其时序关系无法被保证而发生冲突，这就是因果冲突。 门门门厂 _ 一 - - i - j - j - - l a ) 原模型 a 、l n i t i 柚m o d e l b ) o p 2 操作 b 1 0 p 2 0 p e r a t i o n 0 p ， m 冲突模型 d 、c o n f l i d m o d e l e ) 田果时序9 - -n 因果时序图二 e ) c a u s a l t i m i n gd i a g r a m ln c a u s a l t i m i n g d i a g r a m2 圈2 - 3 因果冲突示例 f i g2 - 3 e x a m p l eo fc a u s a lc o n f l i c t 1 0 哈尔滨理工大学t 学硕 ：学位论文 如图2 3 所示三个操作o p l ，0 1 2 ，o p 3 ，站点1 的操作o p l 做了一个凸 台，站点2 的操作o p 2 对凸台的一条边做一个凹形圆角操作，站点3 的操作 o p 3 则以o p l ，o p 2 为基础在凸台上做了一个凹槽。如果这三个操作到达站点 的时序图如图2 3e ) 所示，那操作o p 2 ，o p 3 在站点1 上的执行结果就可能是图 2 3d ) 所示的结果。但是如果相应的时序图变为图2 30 所示，操作o p 2 和o p 3 在站点4 却无法执行，因为生成凸台特征的操作o p l 还没有到达站点4 ，凸台 此刻还不存在，所以o p 2 、o p 3 就失去了执行的基础。 2 意图冲突当操作在一个站点生成后被传送给其它站点进行同步执行， 但在这个操作到达某个站点执行之前这个站点的对象模型已经被本地操作或其 它远程并发操作修改，因此当这个操作执行时它所基于的模型上下文环境已经 发生改变，这样操作执行的结果可能与操作在本地站点的执行结果大相径庭， 从而不满足设计者的原有意图，这样的冲突即意图冲突。如图2 4 所示两个站 点分别执行了o p l 、o p 2 ，当o p l 到达站点2 时，站点2 的模型对象己经被 o p 2 修改，o p l 上的执行结果如图2 - 4c ) 所示，这样的结果违背了操作o p l 的原 有设计意图，同时也不符合操作o p 2 的意图。 a ) o p l 操作”o p 2 操作c ) 冲突结果 a ) o p lo p e r a t i o nb ) 0 1 2o p e r a t i o nc ) c o n f l i c tr e s u l t 图“意图冲突示例 f i g 2 - 4e x a m p l eo fi n t e n t i o nc o n f l i c t 意图冲突是因为不同设计者所关注对象模型的局部不尽相同，同时设计意 图也不同，但是这些主观性的意图在协同设计过程中因为异地协同交流的局限 性，使得各个设计者之间很能进行有效而准确的感知，因而不可避免地出现了 各个并发操作之间相互破坏彼此设计意图的并发冲突。 意图冲突是纯粹从特征语义上来说的冲突，仅从几何造型的角度来看意图 冲突的操作实际上并不存在冲突，它们都能被执行。但是操作执行后所得的特 征形态已不能满足它本该有的工程、设计等语义特性，也就是说这个特征已失 去了其该有的作用。 1 1 3 参数冲突当特征操作在一个站点生成后被传送给其它设计站点进行同 步执行，但在这个特征操作到达某个站点之前这个站点的对象模型已经被本地 操作或其它远程并发操作修改，该特征所依赖的特征的参数可能已经被修改， 从而找不到所需的参数，操作无法执行，这时发生的冲突称为参数冲突。 4 分歧冲突分歧冲突是并发操作对模型的同一特征的同一属性进行修改 而引发的冲突。如图2 - 5 所示，有两个并发操作：一个增大0 5 个单位的孔半 径，而另一操作则增大1 个单位的孔半径。 一一一 - - l - j - j a ) 原模型b ) 增大0 , 5 个单位 时i n i t i a lm o d e l”i n c r e a s e0 5u n i t 图2 - 5 分歧冲突示例 c 1 增大1 个单位 c 1 i n c 北a s e1u n i t f i g 2 - 5e x a m p l eo fd i f f e r e n c e sc o n f l i c t 分歧神突是不同设计者对模型的同一特征的共同关注而产生的，它与意图 冲突的不同之处在于涉及分歧冲突的那些并发操作同时把焦点聚集于同一个特 征单元上，这些操作无论谁先执行谁后执行对象模型都能且仅能体现其中一个 操作的意图，其它操作的执行结果无法表现出来，分歧冲突具有不可调和性。 从以上对并发冲突的归类分析中可以看到，协同设计中的四类冲突形式