（计算机应用技术专业论文）可适应的实时协同编辑系统若干问题研究.pdf

浙江大学博上学位论文 摘要 分布式实时协同编辑系统支持分布在各地的用户通过i n t e m e t 同时浏览和编 辑文本图形图像多媒体文档。它应用在协同编著，远程教育，协同c a d ，协 同编程与调试，远程会议等场合，为人们提供了跨越时空界限的、便捷的协同和 交流空间。近几年，随着固定网络与无线网络的融合，以及便携移动计算设备的 普及，i n t e m e t 正逐步发展成为人们随时随处可以访问和获取计算资源与信息资 源的网络计算环境。从协同计算角度来看，i n t e r n e t 网络计算环境具有一些新的 特点：人和计算设备的移动性，以及计算设备和网络连接方式的多样性，表现为 协同工作过程中协同站点计算资源、网络资源和地理位置等动态变化。上述特点 限制了已有实时协同技术在i n t e m e t 环境下的运用，需要我们对适应新的i n t e m e t 计算环境的实时协同系统关键技术进行研究。 本文结合“基于互联网的图案协同c a d c a m 关键技术研究”项目，对基 于i n t e m e t 的实时协同编辑系统中存在的三个方面问题进行了研究：图像协同编 辑的并发控制和一致性维持，图案协同编辑中的冲突预防机制和实时协同系统的 动态体系结构问题。 提出了图像一致性维持方法( d i o p t ) ，通过图像操作转换方法实现协同图像 编辑一致性维持。 提出了图像协同编辑的a n yu n d o 框架和算法；a n yu n d o 框架和算法实现了 u n d o 模式与u n d o 实现机制的分离，支持多种u n d o 模式，同一组用户可以选择 不同u n d o 模式。 提出了图形协同编辑的动态锁机制模型( o c d l ) 和算法：o c d l 实现了加锁 策略与锁机制的分离，用户可以自定义加锁策略；o c d l 根据协同编辑活动和加 锁策略自适应的调节加锁粒度；o c d l 是一种可选锁机制，用户可以根据需要启 用锁机制。 提出了图像协同编辑的隐含锁机锚i j ( i d l m ) 和算法，实现了图像协同编辑中 的不规则区域加锁和锁区域的动态调节。 提出了基于消息的动态系统结构模型( m a s c a ) ；m a s c a 支持协同应用层和 用户接口层的运行时动态分布以及二者之间的消息映射关系动态调节，实现了协 同系统结构运行时动态迁移。 提出了由消息路由动态构成协同消息总线机制，为上层协同应用提供消息映 射、消息传输和共享状态同步服务。 关键词：c s c w ，实时协同编辑系统，分布式计算，动态协同体系结构，动 态锁机制，并发控制，一致性维持，图像协同编辑，d l o p t ，g r o u p u n d o ，a n yu n d o i 浙江大学博。l 。学位论文 a b s t r a c t d i s t r i b u t e dr e a l t i m ec o l l a b o r a t i v ee d i t i n gs y s t e ma l l o w sag r o u po fu s e r st o v i e wa n de d i tt h es a m et e x t g r a p h i c i m a g e m u l t i m e d i ad o c u m e n ta tt h es a m et i m e f r o mg e o g r a p h i c a l l y d i s p e r s e ds i t e sc o m a e c t e db yn e t w o r k s t h e yh a v em a n y a p p l i c a t i o n ss u c ha sc o l l a b o r a t i v ew r i t i n g a u t h o r i n g ，c o m p u t e r - s u p p o r t e dc o o p e r a t i v e l e a r n i n g ，c o l l a b o r a t i v ec a d ，c o l l a b o r a t i v ep r o g r a m m i n ga n dd e b u g g i n g ，a n d e l e c t r o n i c c o n f e r e n c e ，e r e t h e yp r o v i d e ac o n v e n i e n tv i r t u a l w o r k s p a c ef o r c o l l a b o r a t i o na n dc o m m u n i c a t i o na m o n gp e o p l e i nr e c e n ty e a r s ，w i t hi n t e g r a t i o no f w i r e da n dw i r e l e s sn e t w o r kt e c h n o l o g y , a n dw i d e l yu t i l i z a t i o no fm o b i l ec o m p u t i n g d e v i c e s ，i n t e m e ti sb e c o m i n gan e wc o m p u t i n gn e t w o r k i n ge n v i r o n m e n t ，i nw h i c h p e o p l ec a na c c e s sa n da c q u i r ec o m p u t a t i o na n di n f o r m a t i o nr e s o u r c e sa ta n y w h e r e a n da n y t i m e f r o mt h ep e r s p e c t i v eo fc o o p e r a t i v ec o m p u t i n g ，i n t e r n e te n v i r o n m e n t h a ss o m en e wf e a t u r e s ：m o b i l i t yo fc o o p e r a t i v ep a r t i c i p a n t sa n dt h e i rd e v i c e s ， d i v e r s i t yo fc o m p u t i n gd e v i c ea n dn e t w o r kc o n n e c t i o n t h e s ef e a t u r e sp r e s e n ta s d y n a m i cc h a n g i n go f p a r t i c i p a n t sl o c a t i o na n d r e s o u r c e so fc o m p u t a t i o na n dn e t w o r k i nt h ep r o c e s so fc o l l a b o r a t i o n t h e s ef e a t u r e sr e s t r i c tt h eu s eo fe x i s t i n gc o l l a b o r a t i v e t e c h n o l o g i e si nt h en e wi n t e m e te n v i r o n m e n t i t i sn e c e s s a r yt oi n v e s t i g a t en e w c o l l a b o r a t i v e t e c h n o l o g i e s t h a tm e e tt h en e e d so fc o l l a b o r a t i o ni ni n t e r n e t e n v i r o n n e n t ， i nt h i sp a p e r , s e v e r a lk e yi s s u e so fi n t e m e t b a s e dr e a l t i m ec o l l a b o r a t i v ee d i t i n g s y s t e m sa r ei n v e s t i g a t e d ，s u c ha sc o n c u r r e n c yc o n t r o la n dc o n s i s t e n c ym a i n t e n a n c ei n i m a g e - b a s e dc o l l a b o r a t i v ee d i t i n g ，c o n f l i c t i o np r e v e n t i o nm e c h a n i s m si nc o l l a b o r a t i v e g r a p h i c se d i t i n g ，a n dd y n a m i ca r c h i t e c t u r eo f c o l l a b o r a t i v es y s t e m s t h ei n v e s t i g a t i o n i sc o m b i n e dw i t hk e yi s s u e si nt h er e s e a r c hp r o j e c to f r e s e a r c ho nk e yt e c h n o l o g i e s i nt h ei n t e m e t - b a s e dc o l l a b o r a t i v ep a t t e mc a d c a ms y s t e m ” ad i s t r i b u t e di m a g eo p e r a t i o nt r a n s f o r m a t i o n ( d l o p 砷a l g o r i t h mw a sp r o p o s e d t oa c h i e v ec o n s i s t e n c ym a i n t e n a n c eo fi m a g ei nc o l l a b o r a t i v ee d i t i n gs y s t e m s ， a na n yu n d of r a m e w o r ka n dr e l a t e da l g o r i t h m sf o rc o l l a b o r a t i v ei m a g ee d i t i n g a r ep r o p o s e d ，w h i c hi m p l e m e n t st h es e p a r a t i o no fu n d om o d ea n du n d om e c h a n i s m t h eu n d om e c h a n i s ms u p p o r t ss e v e r a lu n d om o d e s ，a n du s e rc a ns e l e c td i f f e r e n tu n d o m o d ei nt h es a m ee d i t i n gs e s s i o n a no p t i o n a la n dc u s t o m i z a b l ed y n a m i cl o c k i n g ( o c d l ) m o d e la n dr e l a t e d a l g o r i t h m su s e di no b j e c t e d b a s e dc o l l a b o r a t i v es y s t e ma r ep r e s e n t e d o c d lr e a l i z e s i i i 一塑坚尘堂堂主堂焦堡些 s e p a r a t i o no nl o c k i n gp o l i c ya n dl o c k i n gm e c h a n i s m u s e rc a nd e s c r i b eas p e c i f i c l o c k i n gp o l i c ya sn e e d e d o c d lm e c h a n i s mc a l la d a p t st h el o c k i n gs c o p ea n dl o c k i n g g r a n u l a r i t y a tr u n t i m ea c c o r d i n gt o u s e r se d i t i n ga c t i v i t i e sa n dl o c k i n gp o l i c y s e l e c t e d o c d li sa no p t i o n a ll o c k i n gm e c h a n i s m ，a n di t c a r lb ee n a b l e dw h e n n e e d e d a ni m p l i c i ta n dd y n a m i cl o c k i n gm e c h a n i s m ( 1 d l m ) u s e di nc o l l a b o r a t i v e i m a g ee d i t i n gs y s t e m si sp r o p o s e d i d l mm e c h a n i s mr e a l i z e sl o c k i n go ni r r e g u l a r r e g i o n ，a n dl o c k e dr e g i o nc a r lb ed y n a m i c a l l ya d j u s t e da c c o r d i n gt ot h el o c k i n gp o l i c y s e l e c t e d am o d e lo fm e s s a g e d - b a s e da d a p t i v es y n c h r o n o u sc o l l a b o r a t i v ea r c h i t e c t u r e ( m a s c a ) i sp r e s e n t e d m a s c ar e a l i z e sd y n a m i cd i s t r i b u t i o no fa p p l i c a t i o nl a y e ra n d u s e ri n t e r f a c el a y e r , a n ds u p p o r t sd y n a m i cm e s s a g em a p p i n gb e t w e e nt w ol a y e r s m a s c a s u p p o r t sd y n a m i ca r c h i t e c t u r et r a n s i t i o na tm n t i m e ac o l l a b o r a t i v em e s s a g eb u sm e c h a n i s m ，w h i c hi sc o n s i s t e do f m e s s a g er o u t e r s ， i sp r o p o s e d t h em e c h a n i s m p r o v i d e sm e s s a g em a p p i n g ，m e s s a g et r a n s p o r t a t i o na n d s h a r e ds t a t e ss y n c h r o n i z a t i o ns e r v i c e sf o rc o l l a b o r a t i v ea p p l i c a t i o n k e y w o r d s ：c s c w ，s y n c h r o n o u sc o l l a b o r a t i v ee d i t i n gs y s t e m ，d i s t r i b u t e d c o m p u t i n g ，d y n a m i cc o l l a b o r a t i v ea r c h i t e c t u r e ，d y n a m i cl o c k i n gm e c h a n i s m ， c o n c u r r e n c yc o n t r o l ，c o n s i s t e n c ym a i n t e n a n c e ，i m a g e - b a s e dc o l l a b o r a t i v ee d i t i n g ， d l o p t ，g r o u pu n d o ，a n yu n d o i v 本文工作受以下项目资助 浙江省自然科学基金重点重大项目 “基于互联网的图案协同c a d c a n 关键技术研究” ( 项目批准号：z 6 0 3 2 3 1 ) 第一章绪论 浙江大学博十学位论文 1 1 论文背景 第一章绪论 随着人类社会信息化进程的深入，在通信技术、计算机及i n t e m e t 技术的不 断融合与发展中产生了一个新的研究领域：计算机支持的协同工作( c o m p u t e r s u p p o r t e d c o o p e r a t i v e w o r k 一- - c s c w ) ，计算机应用的重点开始从求解问题和信 息处理向方便人们相互交流和支持人们协同工作的方向发展f 史美林2 0 0 1 1 。经 过2 0 多年的发展，c s c w 已经成为综合计算机技术、心理学、人类工程学、认 知科学、社会学、管理科学、心理学等多个学科于一体的交叉研究领域；其研究 成果在教育、军事、医疗、政府、企业、等领域得到应用。c s c w 研究发展 及其技术成果的应用提高了人们的工作效率，并正在影响和改变人类群体工作方 式和生活方式。 c s c w 定义： b a n n o n 【b a n n o n1 9 9 1 ：“c s c w 致力于研究协同工作的本质和特征，并 以此为基础设计出具有足够的计算机技术支持的协同工作信息系统。” e l l i s e l l i s1 9 9 1 ：“c s c w 为一个基于计算机的系统，能够为多用户从事 共同的任务( 或目标) 提供共享的工作环境。” 史美林f 史美林1 9 9 8 ：“在计算机技术支持的环境下( 即c s ) ，特别是在 计算机网络环境下，一个群体协同工作完成一项共同的任务( 即c w ) ； 它的目标是要设计支持各种各样的协同工作的应用系统。” 我们认为：c s c w 本质是利用计算机技术、多媒体技术和网络通讯技术，为 人们提供一个支持群体成员进行协同工作、交互协商、共同完成协同任务的虚拟 环境，它支持多个时间上分离、空间上分布的协同工作。从计算机科学角度看， c s c w 研究涉及网络技术、多媒体技术、人机交互技术、人工智能等诸多研究领 域；其研究内容概括起来有：协同模型、分布式体系结构、并发控制、访问控制、 一致性维持、协调控制、会议管理、协同感知、数据管理、加锁机制、群组通信 等研究问题f 史美林2 0 0 1 ，g r u d i n1 9 9 4 ，r o d d e n1 9 9 1 ，e l l i s1 9 9 1 。 分布式实时协同编辑系统( s y n c h r o n o u sc o l l a b o r a t i v ee d i t i n gs y s t e m - c e s ) 是c s c w 研究应用领域的一个主要分支 u r n e s1 9 9 8 1 。c e s 支持分布在各地的用 户通过i m e m e t 同时浏览、编辑共享文本图形图像多媒体文档。c e s 可以应用 第一章绪论 浙江丈学博上学位论文 在协同编著，c s c l ，协同c a d ，协同编程与调试、远程会议等应用场合，为人 们提供了跨越时空界限的虚拟协同和交流空f h r o t h2 0 0 0 ，s u n2 0 0 2 1 。实时协同编 辑系统可以分为：文本协同编辑( t e x tc o l l a b o r a t i v ee d i t i n 曲、超文本协同编辑 ( h y p e r t e x tc o l l a b o r a t i v ee d i t i n g ) 、图案协同编辑( g r a p h i c sc o l l a b o r a t i v ee d i t i n g ) 等。图案协同编辑可以迸一步分为基于图形( o b j e c t b a s e dg r a p h i c s ) 署 1 基于图像 ( i m a g e b a s e dg r a p h i c s ) 的协同编辑系统 s u nc 2 0 0 2 1 。 分布式实时协同编辑系统相关研究问题主要包括 p h i l l i p s1 9 9 9 ：并发控制问 题、一致性维持、系统体系结构、容错技术、多用户接口等问题。其研究目标是 在各种网络环境( 带宽、延时、差错率) 和计算环境资源约束下，满足多用户实时 协同编辑系统的响应性、交互流畅性、并行性等要求。近几年，宽带网络和无线 网络技术发展突飞猛进，价格低廉的移动计算设备( p d a 、p a l mt o p 、n o t e b o o k 、 m o b i l ep h o n e ) 正在普及应用，i n t e r n e t 逐渐演变为支持移动计算和普适计算 技术的新网络计算环境 g a r l a n2 0 0 0 ，它具有：移动性表现在人和计算设备 的流动，具有移动计算特征；动态性人们使用计算设备和网络连接方式在工 作过程中的动态变化；动态组织工作组的动态变化，包括成员、计算资源、 网络资源、地理位置等动态变化。近几年，有关c e s 的部分研究内容就是围绕 上述新的i n t e m e t 技术背景展开的，目的是解决c e s 系统的可适应性问题 c h u n g 2 0 0 4 ， s h e n2 0 0 4 ，y a n g2 0 0 4 。 分布式实时协同编辑系统是c s c w 领域的研究热点之一。在c s c w 研究领 域最顶级的国际会议a c mc 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 和e u r o p e a n c o m p m e rs u p p o r t e dc o o p e r a t i v ew o r k 上，每届都有与c e s 系统相关的技术专题 和w o r k s h o p 。从e c s c w2 0 0 1 2 0 0 3 和a c mc s c w2 0 0 2 2 0 0 4 来看，近几年c e s 主要研究问题是：( 1 ) 基于复制结构的并发控制与一致性维持问题 y a n g 2 0 0 4 ，s h e n2 0 0 4 ，l g n a t 2 0 0 3 ，d a v i s 2 0 0 2 ，i g n a t 2 0 0 1 1 ：针对复杂文档结构模型的 一致性维持方法研究，如x m l 和r i c h t e x t d a v i s2 0 0 2 ，i g n a t2 0 0 1 1 ；可适应协同 动念过程的灵活并发控制机制研究 y a n g2 0 0 4 ，s h e n2 0 0 4 。( 2 ) 协同体系结构问 题c h u n g2 0 0 4 ，c h u n g2 0 0 1 ，l i t t l e2 0 0 0 】：主要研究适应i n t e m e t 和移动计算环 境的协同动态体系结构及其实现技术。 综上所述，在i n t e r n e t 和移动计算等技术背景下，近几年分布式实时协同编 辑系统研究重点在于解决适应i n t e m e t 计算环境的关键技术问题，而其中的研究 重点和前沿为基于复制结构的并发控制和一致性维持，以及协同动态体系结构问 题。 2 第一章绪论 浙江大学博士学位论文 1 2 论文工作 1 2 1 研究问题 论文研究在浙江省重点基金项目“基于互联网的图案协同c a d c a m 关键 技术研究”( z 6 0 3 2 3 1 ) 资助下进行，以面向轻纺行业的图案协同设计制作 ( c a d c a m ) 为应用背景，结合1 1 节所述分布式实时协同编辑系统主要问题 展开研究。分三个方面问题： 图像协同编辑一致性问题研究 已有的实时协同并发控制和一致性维持问题研究集中在基于文本和基于 图形协同编辑的一致性维持，如基于文本的操作转换算法 s u n1 9 9 8 ，d a v i s 2 0 0 2 1 和基于图形的对象级多版本方法 c h e n2 0 0 1 1 。在轻纺图案协同设计中， 基于图像的协同编辑是图案设计的主要内容，解决基于i n t e r n e t 的图像协同 编辑中的并发控制和一致性维持问题，是实现图形图像融为一体的图案协同 设计系统中的一个主要问题。 图案协同编辑中的冲突预防机制研究 在协同系统设计中，实现协作机制和协作规则分离是一条重要的设计原 则，目的是尽量减少事先定义好的规则对用户工作的限制，从而能更自然、 流畅地进行协同_ t 作【y a n g2 0 0 4 。锁机制作为实时协同编辑系统中的一种主 要并发控制机制和预防冲突方法，也需要遵循上述实现机制和规则分离的原 则，使用户能根据协同任务特点、计算环境约束和协同进程需要动态地选择 加锁协议或规则，以适应不同阶段的协同工作。这就需要研究一种加锁策略 和锁控制机制分离的锁机制模型和实现技术，使得加锁机制可以适应不同协 同应用、不同协同阶段和不同用户的要求。 协同系统动态体系结构研究 现有实时协同编辑系统采用设计时“绑定”的静态体系结构，在系统运 行过程中不能根据应用环境变化进行调节以适应新的应用环境要求。在移 动、动态、异构的移动计算和i n t e r n e t 网络环境中，实时协同系统需要解决 在计算资源和网络资源约束动态改变情况下系统结构的可适应性和柔性问 题。这就需要对可适应的协同动态体系结构及其关键技术进行研究，构建一一 种具有动态的、可适应运行环境的协同应用系统，实现运行时协同系统结构 第一章绪论 浙江大学博士学位论文 的动态调节。 论文工作就是围绕上述问题展开的，并提出了解决上述问题的相关模型和算 法。上述三方面问题既是分布式计算和c s c w 研究领域的基础性问题，同时也 是基于i n t e m e t 的实时协同编辑系统需要解决的关键问题c h e n2 0 0 1 ， s u n 2 0 0 2 。而且，研究工作以面向纺织图案的协同c a d c a m 为应用背景，研究目 标是解决图案协同设计中存在的关键问题。因此，从研究的基础性和应用性角度 来说，研究工作具有重要的研究价值和应用价值。 1 2 2 论文贡献 论文对上述问题进行了深入研究，提出了一些模型和算法。归结为以下几点： ( 1 ) 提出了一种基于图像操作转换的图像一致性维持方法( d l o p t ) ，解决图像 协同编辑一致性问题。 ( 2 ) 提出了实现图像协同编辑g r o u pu n d o 的a n yu n d o 框架和算法；a n yu n d o 框架和算法实现了u n d o 模式与u n d o 实现机制分离，支持多种u n d o 模式， 同一组用户可以选择不同u n d o 模式。 f 3 1 提出了图形协同的动态锁机制模型( o c d l ) ，o c d l 加锁机制的体系结构 和分布式实现算法，以及保持全局锁状态一致性的冲突解决算法；0 c d l 实现了加锁策略与锁机制的分离，以及自适应的加锁粒度调节，用户可 以自定义加锁策略。 ( 4 ) 提出了预防图像协同冲突的隐含动态锁机制( i d l m ) 和实现算法。 f 5 ) 提出了基于消息的动态系统结构模型( m a s c a ) ，m a s c a 支持协同应用 层和用户接口层的运行时动态分布以及二者之间的消息映射关系动态调 节，实现了协同系统结构运行时的动态迁移。 ( 6 ) 研究了协同系统协议层次模型，提出了由消息路由动态构成的协同消息 总线机制，为上层协同应用提供消息映射、消息传输和共享状态同步服 务。 1 3 论文结构 第一章提出了本论文的研究背景及研究内容。 第二章结合研究内容介绍了实时协同编辑系统研究中有关一致性维持、加锁 4 第一章绪论 的动态调节。 浙江人学博+ 学位论文 论文工作就是围绕上述问题展开的，并提出了解决上述问题的相关模型和算 法。上述三方面问题既是分弗式计算和c s c w 研究领域的基础性问题，同时也 是基于i n t e m e t 的实时协同编辑系统需要解决的关键问题 t h e n2 0 0 1 ， s u n 2 0 0 2 1 。而且，研究工作以面向纺织图案的协同c a d c a m 为应用背景，研究目 标是解决图案协同设汁中存在的关键问题。因此，从研究的基础性和应用性角度 来说，研究工作具有重要的研究价值和应用价值。 1 2 2 论文贡献 论文对上述问题进行了深入研究，提出了一些模型和算法。归结为以下几点 ( 1 ) 提出了一种基于图像操作转换的图像一致性维持方法( d i o p t ) ，解决图像 协同编辑一致性问题。 ( 2 ) 提出了实现图像协同编辑g r o u p u n d o 的a n y u n d o 框架和算法；a n y u n d o 框架和算法实现了u n d o 模式与u n d o 实现机制分离，支持多种u n d o 模式， 同一组用户可以选择不同u n d o 模式。 ( 3 1 提出了图形协同的动态锁机制模型( o c d l ) ，o c d l 加锁机制的体系结构 和分布式实现算法，以及保持全局锁状态致性的冲突解决算法；o c d l 实现了加锁策略与锁机制的分离，以及自适应的加锁粒度调节，用户可 以自定义加锁策略。 ( 4 ) 提出，预防图像协同冲突的隐含动态锁机制( j d l m ) 和实现算法。 ( 5 ) 提出了基于消息的动态系统结构模型( m a s c a ) ，m a s c a 支持协同应用 层和用户接口层的运行时动态分布以及二者之间的消息映射关系动态调 节，实现了协同系统结构运行时的动态迁移。 ( 6 ) 研究了协同系统协议层次模型，提出了由消息路由动态构成的协同消息 总线机制，为上层协同应用提供消息映射、消息传输和共享状态同步服 务。 1 3 论文结构 第一章提出了本论文的研究背景及研究内容。 第：章结合研究内容介绍了实时协同编辑系统研究中有关一致性维持、加锁 第：章结合研究内容介绍j ，实时协同编辑系统研究中有关一致性维持、加锁 4 第一章绪论 浙江大学博士学位论文 的动态调节。 论文工作就是围绕上述问题展开的，并提出了解决上述问题的相关模型和算 法。上述三方面问题既是分布式计算和c s c w 研究领域的基础性问题，同时也 是基于i n t e m e t 的实时协同编辑系统需要解决的关键问题c h e n2 0 0 1 ， s u n 2 0 0 2 。而且，研究工作以面向纺织图案的协同c a d c a m 为应用背景，研究目 标是解决图案协同设计中存在的关键问题。因此，从研究的基础性和应用性角度 来说，研究工作具有重要的研究价值和应用价值。 1 2 2 论文贡献 论文对上述问题进行了深入研究，提出了一些模型和算法。归结为以下几点： ( 1 ) 提出了一种基于图像操作转换的图像一致性维持方法( d l o p t ) ，解决图像 协同编辑一致性问题。 ( 2 ) 提出了实现图像协同编辑g r o u pu n d o 的a n yu n d o 框架和算法；a n yu n d o 框架和算法实现了u n d o 模式与u n d o 实现机制分离，支持多种u n d o 模式， 同一组用户可以选择不同u n d o 模式。 f 3 1 提出了图形协同的动态锁机制模型( o c d l ) ，o c d l 加锁机制的体系结构 和分布式实现算法，以及保持全局锁状态一致性的冲突解决算法；0 c d l 实现了加锁策略与锁机制的分离，以及自适应的加锁粒度调节，用户可 以自定义加锁策略。 ( 4 ) 提出了预防图像协同冲突的隐含动态锁机制( i d l m ) 和实现算法。 f 5 ) 提出了基于消息的动态系统结构模型( m a s c a ) ，m a s c a 支持协同应用 层和用户接口层的运行时动态分布以及二者之间的消息映射关系动态调 节，实现了协同系统结构运行时的动态迁移。 ( 6 ) 研究了协同系统协议层次模型，提出了由消息路由动态构成的协同消息 总线机制，为上层协同应用提供消息映射、消息传输和共享状态同步服 务。 1 3 论文结构 第一章提出了本论文的研究背景及研究内容。 第二章结合研究内容介绍了实时协同编辑系统研究中有关一致性维持、加锁 4 螭一章绪论浙江人学博i ，学位论文 机制和体系结构等三个方面的研究现状和存在的问题。 第三章给出了解决协同图像编辑并发冲突和实现一致性的方法图像操 作转换方法d l o p t 。 第四章，在图像一致性维持方法的基础上，给出了实现图像协同g r o u p u n d o 的框架和算法。 第五章提出了用于图形协同编辑的冲突预防机制用户可选的、可客户化 的动态加锁机制和算法。 第六章提出了用于图像协同编辑环境的隐含动态锁机制。 第七章研究了可适应网络环境和计算环境资源约束变化的动态体系结构，提 出了基于透明消息总线机制的协同动态系统结构模型。 第八章介绍了图案协同设计c o d e s i g n 原型系统和实验平台。 第九章对研究工作进行总结并提出了今后工作的展望。 全文的组织结构可以用图1 1 描述。 幽像协同一致性j 维持问题研究 图案协同冲突 预防机制研究 协同系统动态 体系结构研究 第一章绪论 第二章相关研究综述 第三章图像协同编辑的一致性维持 第四章图像协同编辑g r o u pu n d o t 第五章图形协同的动态锁机制 第六章图像协同的隐含加锁机制 第七章实时协同系统动态体系结构模型l 第八章c o d e s i g n 原型系统 第九章总结与展望 图1 - l 论文组织结构 rl，l rjl 第二章相关研究综述 浙江大学博l j 学位论文 2 1 概述 第二章相关研究综述 人与人之间的交流和协作构成人类活动基础。随着宽带网络、无线网络和计 算机的普及和大众化，人们越来越广泛地使用计算机进行交流和协作。分布式实 时协同编辑系统在为人们提供跨越时空界限的便捷虚拟协同和交流空间方面发 挥了重要的作用。其研究内容涉及以下三方面问题 v o g e l2 0 0 4 ，l i2 0 0 0 ，u m e s 1 9 9 8 ，c r r a h a r n1 9 9 6 分布式系统相关问题：分布式实时协同系统支持地理上分布的多用户共 同参与协同工作，是一种典型的分布式系统，需要解决分布式体系结构、 并发控制、一致性维持、共享程序和数据的分布复制、容错技术、安全 问题、群组通信技术等问题。 实时系统相关问题：实时协同系统支持多用户实时协同和交流，需要满 足实时交互系统的性能约束，包括响应时间( f e e d b a c kt i m e ) 、馈通时间 ( f e e d t h r o u g ht i m e ) 并l l 抖动( j i t t e r ) 等要求。 人机接口相关问题：人杌接口可用性是影响用户对系统评价的主要因素。 协同系统用户接口包含人一机交互和人一人交互两部分功能，既要实现 和显示本地用户的交互操作，又要实现远程用户的交互；如何使人一机 交互和人一人交互自然流畅地进行是协同系统中需要研究的一个重要问 题。 上述三方面问题密切相关。如实时协同系统的响应时间要求直接影响到协同 系统采用什么体系结构和并发控制方法，数据和程序的分布方式 x u2 0 0 4 ， g u t w i n1 9 9 9 ，r a y n a l1 9 9 6 ，r o d d e n1 9 9 2 1 ；系统体系结构、并发控制、一致性维 持方法会影响人机交互界面设计 c a l v a r y1 9 9 7 ，d e w a n1 9 9 8 ，g r e e n b e r g1 9 9 4 ； 人机交互技术可以缓解由网络延时、抖动引起的交互界面滞涩、不流畅问题 d y c k 2 0 0 4 ，g u t w i n2 0 0 2 1 。这些问题包含很多可研究内容和研究方向，概括起来主要 有：并发控制问题、副本一致性维持、系统体系结构、容错技术、安全问题、群 组通信技术、多用户接口等问题。 本章仅就论文研究涉及的并发控制、一致性维持和系统体系结构等问题进行 综述，介绍相关研究现状与进展。 7 第二章相关研究综述 浙江大学博士学位论文 2 2 并发控制与一致性维持 并发控制和一致性维持并不是一个新的研究课题。并发控制技术广泛应用于 一般的分布式系统和分布式协同系统 m u n s o n1 9 9 6 1 。一般的分布式系统是非交 互式系统，其并发控制一般是面向系统的，并发控制操作由用户进程发出，且对 用户透明 s t r o m1 9 9 8 】。比如，数据库系统的加锁目的是使各个用户均感觉到只 有他自己在单独使用这个系统，使系统拥有更高的吞吐率 c h a n g2 0 0 2 。而在分 布式协同系统中，协作感知是多用户进行协同工作的基础，用户对共享对象的操 作应立即被其他参与协同工作的用户所感知 l i2 0 0 3 ，g u t w i n1 9 9 9 ，e l l i s1 9 9 1 ； 另外，分布式协同系统是支持人一人交互的人机交互系统，比其他分布式系统需 要更多地考虑人的问题 s l a g t e r2 0 0 0 。因此，并发控制机制的选择需要考虑到对 用户协同工作的影响以及用户接口的表现形式。许多学者对实时协同系统并发控 制以及一致性维持问题进行了深人的研究，提出了诸多并发控制方法、模型 s u n 2 0 0 2 ，杨光信2 0 0 0 ，m u n s o n1 9 9 6 ，g r e e n b e r g1 9 9 4 ，n e w m a n - w o l f e1 9 9 2 ，e l l i s 1 9 8 9 ，l a n t z1 9 8 7 1 。每一种并发控制方法都有其适应性和局限性。 2 2 1 并发控制模型 令牌轮转：令牌方式( r u m t a k i n g ) 每次只允许一个用户持有令牌，该用户对 于共享数据或文档有完全的操作权年l j s h e n2 0 0 4 1 。由内部协议或外部社交协议控 制令牌控制。令牌方式独立于应用语义，因此一般用于应用程序共享系统，如 m i c r o s o f tn e t m e e t i n g ，s h a r e d x p o r t h e r f i e l d1 9 9 1 系统采用令牌方式。令牌方式 每次只允许一个活动用户，不支持并发操作。这种方法局限于一个活动用户就可 以满足协同工作需要的场合，不适合于多数实时协同应用环境，因为协同的本质 特征就是支持多用户的并发活动流。 集中控制法：通过一个集中协调控制进程，协调管理所有共享对象的操作流： 接收所有用户的数据操作请求，并将其广播给所有的用户，从而使操作有序，确 保数据的一致性。n c s ah a b a n e r o 【c h a b e r t1 9 9 8 ，j a m m b e g o l e1 9 9 8 ，p r o s p e r o f d o u r i s h1 9 9 6 等协同系统采用集中控制方法。这种方法的优点是并发控制实现 机制比较简单，但它最大的缺点是集中协同控制会造成系统瓶颈问题，一方面， 当参与协同较多时，受控制服务器的网络带宽限制导致系统性能的下降；另一方 面，当集中协调控制进程出错时，系统也随之瘫痪，集中控制进程削弱了系统的 稳定性：另外，用户申请的操作必须先达到集中控制器，当其从集中控制器返回 时才能执行，因而延长了系统的响应时间。 8 第= 章相关研究综述 浙江大学博l 学位论文 加锁( l o c k i n g ) ：加锁是对并发控制和保证数据一致性的常用手段，它提供对 共享数据的加锁和解锁，用于控制用户的并发操作【x u e2 0 0 0 】。 c o d i a g r a r n c a n a p b e l l1 9 9 9 ，e n s e m b l e n e w m a n w o l f e1 9 9 2 是采用加锁机制的协 同系统。在r e d u c e s u n2 0 0 2 ，g r a c e c h e n2 0 0 0 系统中，加锁机制作为一 种可选的并发控制机制。加锁的优点是设计和实现较为简单。但是在应用协同系 统存在一定的问题：首先是申请和释放锁的开销会影响用户动作的快速反馈，并 且何时申请或释放，系统很难确定，又不易由用户控制。其次，被封锁数据的粒 度难于确定，过小加重系统负担，过大则影响用户操作的并行性。因此，何时使 用加锁机制、怎样进行加锁是协同环境中加锁机制有效利用的前提。 序列化( s e r i a l i z a t i o n ) ： 采用序列化方式，操作可以并