（计算机应用技术专业论文）协同工作流中应用共享方法的研究.pdf

山东大学硕士学位论文 摘要 工作流技术在管理、生产等领域得到了非常广泛的应用。在工作流的流转过 程中，单个参与者所执行的任务并非是独立的。很多情况下多个参与者会对同一 份文档、同一个数据对象进行操作，他们之间需要协同编辑，才能达到一个整体 的目标。现有的工作流系统在处理需要协同交互的过程时却有着很大的局限性。 很多优秀的协同编辑工具，如( 的v e 、r e d u c e 等都很好的支持实时的协同交互， 但作为编辑工具来讲，其功能和可用性远不如某些常用的单用户应用程序，如m s w o r d 。为了既能拥有强大的编辑功能和可用性，又能很好的支持协同交互，对单 用户应用程序进行扩展是个很好的方案。 本文提出了一个单用户应用程序共享的方案，用于支持协同工作流中的协同 编辑，并结合现有的工作流管理系统，设计和实现了一个支持协同编辑的协同工 作流系统。 为了支持多用户之间实时的无限制的协同编辑，本文对单用户应用程序进行 扩展，并使用操作变换机制维护数据在全局的一致性。操作变换机制并非适用于 任意结构的文档。操作变换要求共享文档中的对象存储在一维或多维的地址空间 中，并且可以使用位置作为索引定位对象。为了达到操作变换需要的条件，在单 用户应用程序的外部设置了一个线性表用以索引文档中的对象。另一方面，传统 的操作变换算法只能支持对文档的插入和删除操作，d 撕ds 吼提出一种扩展的操 作变换算法，可以另外支持更新操作，但它的算法是不完备，本文在它的基础上 提出了一个改进的扩展o t 算法，以维持协同编辑中具有复杂对象结构的文档在全 局的一致性。 本文以m sw j r d 作为单用户应用程序的例子，设计和实现了一个系统原型， 对上述方案进行试验和验证。选择一个现有的传统工作流引擎：s h a r k 工作流引擎， 在其基础上进行适当的扩展，将现有的工作流引擎和现有的单用户应用程序进行 集成，实现一个能支持协同编辑的协同工作流系统。整个系统采用b s 和c s 混 合的结构模式，使用多种语言开发完成。系统主要分为工作流引擎服务器，协同 数据服务器，协同客户端和单用户应用程序四个部分。协同同客户端是整个系统 的纽带，它将系统的其余部分有机地连接起来。协同客户端本身又分为三个模块： 山东大学硕士学位论文 工作流客户端、协同数据客户端和应用程序代理。应用程序代理是协同客户端中 的核心，采用w i n d o 、s h o o k 技术和c o m 接口对m s w b r d 进行监听和控制，协同 多个用户之间的同步操作。关键的操作变换算法就在应用程序代理中实现。 通过实现系统原型进行验证，证明本文提出的通过单用户应用程序共享方法 实现协同编辑的方案是正确的。 关键词：应用共享：协同工作流；协同编辑；操作变换：单用户应用程序 n 山东大学硕士学位论文 a b s t r a c t 霄o r k f l 佣t e c h n 0 1 0 9 yi su s e dw i d e l yi na 血i n s t r a t i v e 髓d ”o d u c t i o n f i e l d s i n g l eu s e r st a s ki sn o ti s o l a t e di nt r a n s i t i o np r o c e s so f 们r k f l 佣 i n s t a n c e i o s t l y ，ag r o u po fu s e r sn e e dt oe d i tt h es 锄ed o c 岫e n t ，o rt h es a m e d a t ao b j e c ti nt h es 锄e t h e yn e e dt oe d i ti tc o o p e r a t i v e l yt oc 伽p l e t et h e i r t a s k t h ee x i s t i n g 霄o r k f l o ws y s t e m ss h o wt h e i r1 i m i t s _ h e nu s e r sn e e dt o w o r kc o o p e r a t i v e l y s e v e r a lg o o de x c e l l e n tc o o p e r 8 t i v ee d i t o r s ，s u c ha s g r o v e ，r e 叫c e ，s u p p o r tr e a 卜t i c o o p e r a t i v ee d i t i n ge f f i c i e n t l y ，h 0 w e r v e r ， a s e d i t i n g t o o ls ， t h e y a r en o t g o o d a ss o m ec o 删n o n s i n 9 1 e _ u s e r a p p l i c a t i o n ，s u c h a sm s w o r d ，i n f u n c t i o na n d u s a b i l i t y t oe x p e n d s i n 9 1 e u s e ra 】) p l i c a t i o nt os u p p o r tc o o p e r a t i v ee d i t i n gi sa 印p r o a c h ，i t c a nr e a c hb o t hg o o df u n c t i o na n du s a b i l i t ya 1 1 dc o o p e r a t i v ee d i t i n g a na p p r o a c hb a s e do ns i n 9 1 e 1 l s e ra p p l i c a t i o ns h a r i n gi sp r o p o s e dt o s u p p o r tc 0 1 1 a b o r a t i v ee d i t i n gi nc o o p e r t i v ew o r k = f l o 霄a l l dac o o p e r t i v e 们r k f l o ws y s t e ms u p p o r t i n gc 0 1 l a b o r a t i v ee d i t i n gi sd e s i g n e da n d i m p l e m e n t e d t h ea p p r o a c h s u p p o r t su n c o n s t r a i n e dc 0 1 l a b o r a t i o n ，a n d u s e s o p e r a t i o n a lt r a n s f o r m a t i o nt om a i n t a i nd 8 t ac o n s i s t e n c y n o td o c u m e n t sw i t h a n y s t r u c t u r ec a n s u p p o r to p e r a t i o n a l t r a n s f o r m a t i o n a l g o r i t h m o p e r a t i o n a lt r a n s f o m a t i o na l g o r i t l l mr e q u i r e st h eo b j e c t si nad o c 瑚e n t t ob ea d d r e s s a b l eb yp o s i t i o n a lr e f e r e n c e si n8o n e o rm u l t i d i m e n s i o n a l a d d r e s ss p a c e b e c a u s eo ft h i sr e q u i r e m e n t ，as e q u e c et a b l ei ss e to u t s i d e o fs i n 9 1 e u s e ra p p l i c a t i o nt oa d d r e s st h eo b j e c t si nd o c u m e n t t r a d i t i o n a l o p e r a t i o n a lt r a n s f o 珊a t i o na l g o r i t l l m ss u p p o r to n l yi n s e r t i n ga n dd e l e t i n g o p e r a t i o n d a v i ds u np r o p o s e dae x p e n d e da l g o r i t l l mt h a tc 粕s u p p o r tu p d a t i n g o p e r a t i nb e s i d e s h o w e v e r ，t h ea l g o r i t h c a nn o t _ d r kc o r r e c t l yi na l l c o n d i t i o n s a r i i m p r o v e m e n t o fd a v i ds u n s e x t e n d i n go p e r a t i o n a l t r a n s f o 蛐a t i o na l g o r i t h m0 nt h ec o n t r o l1 a y e ri sp r o p o s e dt o s u p p o r t 山东大学硕士学位论文 s h a r i n gc o n t r 0 1t od o c u m e n t sw 】i c hh a v ec 彻p l e xo b j e c ts t r u c t u r e ap r o t o t y p es y s t e mi sd e s i g n e da n di m p l e m e n tb a s e do nt h ea p p r o a c ho f e x p e n d i n gs i n g l e 1 l s e ra p p l i c a t i o n ，a n dm sw o r di su s e da sae x 锄p l eo f s i n 9 1 e u s e ra p p l i c a t i o n ne x i s t i n gt r a d i t i o n a lw o r k f l o s y s t e m s h a r k w o r k f l a ws y s t e mi sc h o s e da n di m p r o v e d i n t e g r a t es i n g l e 1 l s e r 印p l i c a t i o n i n t os h a r kw o r k f l o ws y s t e mt oi m p l e m e n tac o o p e r a t i v ew o r k f l o ws y s t e m s u p p o r t i n gc o o p e r a t i v ee d i t i n g t h e曲0 1 es y s t e mu 8 e sb s锄dc s a r c h i t e c h t u r et o g e t h e r ，a n dm u t i l p l ep r o g r 锄i n gl a n g u a g e sa r eu s e dt o i m p l e m e n t t h i s s y s t e m t h e w h 0 1 es y s t 锄c a nd i v i d ei n t of o i l r c o m p o n e n t s ：w o r f l o we n g i n es e r v e r ，c o o p e r t i v ed a t as e r v e r ，c o o p e r t i v ec l i e n t a n ds i n g l e u s e ra 】) p l i c a t i o n c o o p e r t i v ec l i e n ti st h ei m p o r t a l l tp a r to f a 1 1 ，a n di tb o n d st h eo t h e rt h r e ec o m p o n e n t st o g e t h e r c o o p e r t i v ec l i e n ti s d i v i d e di n t ot h r e em o d u l e s ：w o r k f l 0 wc l i e n t ，c o o p e r a t i v ed a t ac l i e n ta n d s i n 9 1 e l l s e ra p p l i c a t i o na g e n t s i g l e - u s e ra p p l i c a t i o na g e n ti st h ec o r eo f c o o p e r t i v ec l i e n t i tm o n i t o r sa l l dc o n t r 0 1 s 螂w o r dt h r o u g hw i n d o w sh o o k t e c l l i l 0 1 0 9 ya n dc a hi n t e r f a c ea n ds y n c h r o n i z ec o n c u r r e n to p e r a t i o n so f 哪t l p l eu s e st h r o u g ho p e r a t i o n a lt r a n s f o r m a t i o na l g o r i t h m t h ep r o t o t y p es y s t e mi m p l e m e n t e ds h o 霄st h a tt h ea p p r o c hb a s e d0 n s i n 9 1 e u s e ra p p l i c a t i o ns h a r i n gi sc o r r e c t k e o r d 5 ： p p | c a t i o ns h a r in g ：c o o p e r a t i v ew o r k f l 佣：c o o p e r a t i v ee d i t i n g 0 p e r a t j o n a lt r a n s f o r 恫t i o n ；s in g i e u s e r p p i i c a t i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责 任由本人承担。 论文作者签名：参捧日期：2 卑：? l 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅； 本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：排导师签名： 山东大学硕士学位论文 第l 章绪论 1 1 研究背景和现状 工作流技术在管理、生产等领域得到了非常广泛的应用。在现实生活中，如 公文流转、购物消费等过程，都具有典型的工作流特征，可以通过工作流系统加 以实现。在这些过程中，文档、信息和任务在工作流引擎的控制和指引下，按照 一定的规则在多个参与者之间流转，大大提高了工作的效率。工作流系统使得单 个的参与者可以专注于自己手上的任务，而不必去考虑这些任务是从谁那里接手 过来、完成了又要交给谁进行下一步的处理。 在传统的观点中，工作流一般被划分到“异地异步”协作系统的范畴。但是 在现实中很多情况下多个参与者之间需要进行实时的协同和交互，这就需要将同 步协作的特性引入到工作流系统中来。g f o g o r i 【1 1 提出；虽然现有的工作流模型和 工作流系统能很好的应用于管理和生产领域，但在处理需要协同交互的过程时却 有着很大的局限性，而这种交互式过程广泛存在于协同设计等领域。 在史美林等开发的工作流管理系统、) l b 、 w f 圆p 】中提供了对工作流执行过程中 的协同交互的支持。、w w w l 使用应用表单机制来实现对不同应用的集成。应用表 单实际上是提供给某个或某组用户用以处理不同任务的一组应用程序的组合，以 j a v a b e 锄组件的形式实现，并且都实现一个统一的接口，用户可以对其进行扩展。 w b u 删! 通过在表单中添加一些特殊的控件：如协同编辑框、虚拟绘图框等来提供 对协同交互的支持。 随着对c s c w 【4 1 研究的深入，出现了很多优秀的协同编辑工具，如g f o v e f 5 l 、 r e d u c e 【6 】、觚c e 川、蛳i t e 一1 等。这些工具采用复制结构，使用操作变换 9 1 ( 0 p e r 撕o n a lt r 锄s f o 衄，简称0 叨维持数据的全局一致性，从而提供了很强大的协 同能力，使得多个用户之间可以进行无限制地协同交互，而且具有很好的响应时 间。 无论是w 曲w v ! 中的表单中的协同控件，还是像r e d u c e 这样专门的协同编 辑工具，虽然提供了很好的协同能力，但作为编辑工具来讲，其功能和可用性远 不如某些常用的单用户应用程序，如m sw j r d 。为了既能拥有强大的编辑功能和 可用性，又能很好的支持协同交互，对单用户应用程序进行扩展是个很好的方案。 山东大学硕士学位论文 如果能把操作变换机制引入到单用户应用程序扩展系统中来，就可以实现对 无限制协同的支持。传统的应用程序扩展系统采用视图级共享或命令级共享，无 论视图还是命令( 一般是鼠标键盘操作) ，都是无法进行操作变换的。d ul i 提出了 i c t ( i n t e l l 培锄tc o l l a b o f a t i o n 缸锄s p 砌c y ) 方法解决这个问题。在该方法中，用户 的鼠标键盘操作被截获下来，转换成带有语义的应用级操作( 如插入字符、删除字 符1 。这些应用级操作被发送到其他客户端，并利用操作变换机制进行一致性维护， 在远程客户端执行时要把应用级操作再转换成鼠标键盘事件然后进行回放。插入 字符和删除字符等应用级操作能够进行操作变换，从而成功地把操作变换机制引 入到单用户应用程序扩展系统中来。但i c t 方法只能处理对文本的协同编辑，无法 处理图像等复杂对象，这大大限制了它在实际中的应用。 受i c t 的启发，d 撕ds 吼提出了c o b r d 疗法【1 1 】【1 2 】，它不仅能处理文本，而且 能处理像w b r d 文档这样复杂的对象结构。d 撕ds u r i 对在g 0 ，r o 【9 l 框架下对叩算法 进行了扩展，增加了一个“u p d a t e ”元操作以支持对复杂对象的操作( 如修改对象 的属性值) 。但a i r r i i i i e 指出g o t o 算法在某些特定情况下不能保证数据在全局的一 致性1 3 】。所以c o w b r d 方法也有待改进。 对工作流的研究和对单用户应用程序扩展的研究都取得了一定的突破，但目 前对两者的结合却是一个空白。如果将单用户应用程序扩展引入到工作流系统中 来，能给用户提供更好的处理任务的工作环境，同时可以大大加强工作流执行过 程中的协同交互。 1 2 本文的工作 本文提出了一个单用户应用程序共享的方案，用于支持协同工作流中的协同 编辑，结合现有的工作流管理系统，实现了一个支持协同编辑的协同工作流系统。 本文的主要工作： 提出了一个基于单用户应用程序共享的方案，实现对工作流系统中的无限 制协同编辑的支持。要实现无限制协同，关键就在于利用操作变换机制维 持数据的全局一致性。为了能充分利用操作变换机制，在单用户应用程序 的外部设置了一个线性表用以索引文档中的对象。 提出了一个改进的扩展c r r 算法，以维持协同编辑中具有复杂对象结构的 文档在全局的一致性，是本文的主要创新点。 山东大学硕士学位论文 设计和实现一个系统原型，对上述研究内容进行试验和验证。选择一个现 有的传统工作流引擎，在其基础上进行适当的扩展，将现有的工作流引擎 和现有的单用户应用程序进行集成，实现一个能支持协同编辑的协同工作 流系统。 本文的主要创新点： 对d 撕d s m 的0 t 算法进行了改进，提出了一个改进的扩展0 t 算法。 设计和实现了支持协同编辑的协同工作流原型系统。 1 3 本文的组织 本文第二章对协同编辑和协同工作流的背景和研究现状进行概述。在此基础 上，第三章提出了一中扩展单用户应用程序实现协同编辑的方案，提出了一个改 进的扩展o t 算法。在提出的方案的理论基础上，第四章对支持协同编辑的协同工 作流系统进行了设计，给出了总体架构设计方案，划分了模块，并对需要使用的 关键技术进行了介绍。第四章着重介绍支持协同编辑的协同工作流系统的实现， 对各模块的实现进行了详细介绍。最后对本文进行了总结，并提出以后需要改进 的方向。 山东大学硕士学位论文 第2 章协同编辑和协同工作流概述 2 1 协同编辑概述 协同编辑是一类重要的c s c w ( c o r n p u t e rs u p p o 哟dc o o p e r a t i v ew o r k ) 应 用，从c s c w 研究的早期开始就是主要的研究课题之一。随着网络技术的发展和分 布式系统的普及，计算机应用正从传统的单用户工作模式向多用户协同工作的方 向发展，需要编辑的文档数量急剧膨胀，文档内容和结构日趋复杂，个人编辑行 为已经难以满足大量生成有组织的文档的要求，如果没有一个协同编辑管理系统 对编辑的文档和过程进行管理，对编者的行为加以控制和协调，势必造成文档的 混乱，编辑任务难以按时完成，因此，协同编辑应运而生，对协同编辑系统的研 究和开发势在必行。它允许地理上分散的用户在同一时刻浏览和编辑共享的文档。 在编辑过程中，存在着不同程度的协作模式【3 】。一种极端的情况是单个用户通 过与其他的用户的讨论和评审独立完成一份文档，另一种极端是多个用户联合完 成一份文档。在协同编辑过程中，有顺序、并行和交互三种协作策略。顺序协作 是指编辑任务被划分为多个子任务，这些子任务以某种顺序完成。对于并行协作 来说，一个编辑任务被划分为多个子任务，并将这些任务分配给组内的每个成员， 这些子任务以并行的方式进行。交互协作是组内的用户同时工作，实时地编辑同 一文档，共同完成任务。在交互模式下，协作成员同时对同一文档进行编辑，每 个成员对文档的修改操作都实时地广播给其他成员，并使其他成员及时看到修改 后的结果。 顺序协作和并行协作属于异步协作模式，组内成员对文档的编辑操作，在任 务提交以后，其他成员才能看到效果；而交互协作属于同步协作模式，组内成员 对文档的编辑操作实时地广播给其他成员，其他成员可以立即看到编辑的效果。 交互协作实质是并行协作的一种高级形式。两者都是将任务分配组内成员同 时进行，不同的是并行协作的过程中不支持组内成员之间的实时交互，而交互协 作则能够实现组内成员能够实时地看到其他成员编辑的结果。 对于顺序协作和并行协作方式，需要工作流系统对流程进行控制，但不需要 特殊的协同编辑工具；对于交互协作方式，则需要采用特殊的协同编辑工具以支 持实时的交互。目前有不少协同编辑工具软件可以支持交互协作模式的协同编辑。 4 山东大学硕士学位论文 协同编辑系统的体系结构可以划分为两种类型：集中式体系结构、对等式分 布结构。 集中式体系结构中有一台服务器做为中心，其主要功能是管理共享文档和协 同参与者。参与者开始编辑时，作为客户连接倒服务器上，共享文档统一存放在 服务器中，每个参与者对文档的修改都实时地传送到服务器中。 对等式体系结构与集中式结构不同的地方在于，当多个参与者同步对一个文 档进行编辑时，每个参与者站点分别保存该文档的一个副本，而且这些文档副本 保持实时的数据一致。每个参与者的动作在本地执行后广播给其他参与者。这种 方式用户操作的响应时间短，但保持各站点数据的一致性较为困难。 集中式结构和对等式结构有各自的优缺点，单纯地采用某种结构都不能很好 的实现一个完整的协同编辑系统。可以采用混合式的体系结构，对用户信息和文 档数据采用进行集中式管理，但在进行交互式协同编辑时，每个参与者保存一个 文档副本，参与者与参与者直接通信，不通过中心服务器。 一般来说，对协同编辑系统应具有以下的要求【1 6 1 ： ( 1 ) 实时性。对本地用户操作的响应要快( 就象单用户在操作一样) ，对远程 用户操作响应的时延也要尽可能的小。从总体上讲，一项工作有多个人合作完成， 无疑提高了效率，但信息在网络上传输的开销可能导致性能降低。 ( 2 ) 无限制的协作。参与会议的多个用户可以在任意时刻自由地、并行地编辑 共享文档的任何一部分。 ( 3 ) 并发性和一致性。系统应允许多个用户同时操作，并保持共享数据的一致 性，这一点一直是同步协同编辑实现的难点，许多专家在这方面作了大量的理论 研究，但真正的合理有效的实现还需进一步的尝试。很显然，一致性可能对并发 性作一定的限制。 ( 4 ) 可靠性。系统应对一些故障( 如网络故障、突然掉线、意外死机等) 进行 及时的恢复，用户操作的失误也不应导致整个系统的崩溃。即：系统应具有一定 的容错性。 随着对c s c w 研究的深入，出现了很多优秀的协同编辑工具，如g r o v e ， r e d u c e 等。一组用户可以使用它们实时地、无限制地、并发地对同一文档进行 编辑，用户的编辑操作在本地生效的同时立即广播给其他用户，实现了上文提到 山东大学硕士学位论文 的交互协作模式。这些协同编辑工具采用对等式或混合式体系结构，使用操作变 换机制来维持数据的全局一致性。 操作变换机制采用复制结构切。考虑n 个站点共同编辑一个共享文档，每个站 点都维持共享文档的一个备份。操作变换机制的作用就是要维护n 个站点的文档备 份的致性。每个站点上的编辑操作在本地立即执行并立即广播给其他站点进行 执行。对每个操作的处理可以分为四步： ( 1 ) 操作在本地的产生和执行； ( 2 ) 广播操作给其他站点； ( 3 ) 其他站点接收到操作； ( 4 ) 操作在其他站点的执行。 给定一个具体的操作0 p 。由于网络等方面的原因，一个站点接收到其他站点 发送来的操作序列的顺序与其产生的先后顺序有可能是不一致的。所以o p 在本地 执行时的上下文环境( 文档状态) ，和远程站点接收到o p 以后准备执行时的上下 文环境有可能是不相同。如果在远程站点直接执行0 p ，将会造成各个站点的文档 状态不一致。 在操作变换机制中，远程站点接收到o p 以后，并不是直接执行o p ，而是先 参照该站点的操作执行历史，对o p 进行适当的变换后再执行。变换的作用就是使 各个站点的文档能够保持一致性。 这种变换通过操作变换函数嘲来实现。一个操作变换函数f 包括两个参数：o l 和 o2 。0l 和o2 必须是定义在相同的文档状态上，这样才有意义。操作变换函数f 的 返回值为0 l ，它效果与0 i 相同，但定义在oz 执行后的文档状态上。 传统的操作变换算法有d o p r 【”、g o t l l ”、a d o 唧【”、g o 旧纠等，这些算 法能在一定程度维持协同编辑中数据的全局一致性。这些算法只能支持对文档的 插入和删除操作，但在编辑一些复杂的文档( 如m s w j r d 文档) 时，还存在对对象 的更新操作( 如更改字体、字号等) 。d a 、r i ds u n 对g o t o 算法进行了扩展，提出一 种支持插入、删除、更新三种操作的操作变换算法，用以支持对复杂文档的协同 编辑，但它的算法是不完备的，在某些情况无法保持数据的全局一致性。 像r e d u c e 这样专门的协同编辑工具，虽然提供了很好的协同能力，但作为 编辑工具来讲，其功能和可用性远不如某些常用的单用户应用程序，如m sw b r d 。 山东大学硕士学位论文 如果能对单用户应用程序进行扩展，使之具备协同编辑的功能，则能够大大提高 协同编辑的效率。 2 。2 协同工作流中的协同编辑 现有的工作流系统，大多致力于管理流程和生产流程的自动化啪l 【2 。这些流 程中的过程都是预先定义好的，每个任务在流转过程中独立执行，只有在流程的 开始和结束时进行同步。虽然现有的工作流系统能很好的应用于管理和生产领域， 但在处理需要协同和交互的创作性过程时却有着很大的局限性，而这种交互式过 程广泛存在于协同设计、协同著作等领域捌咧。这些需要协同编辑机制来协同用 户之间的交互操作。 在工作流的流转过程中，单个参与者所执行的任务并非是独立的。很多情况 下多个参与者会对同一份文档、同一个数据对象进行操作，他们之间需要相互沟 通、相互协调，才能达到一个整体的目标。例如：一份申请表格，需要多个部门 的负责人填写审批意见。在工作流运行过程中，多位部门负责人可以同时查看这 份表格并填写各自的意见。多个参与者对同一文档并发操作的需求，使得工作流 系统中必须有对协同编辑的支持。 工作流中的协同编辑，主要发生在以下两种场景： 横向协同：协同编辑发生在并行的两个或多个任务之间。上面提到的 多个部门的负责人审批一份申请表格的例子就属于这种情况。如下图所示，任务 b 、c 、d 之间需要协同编辑，共同完成对申请表格的审批。 图2 1 横向协同示意图 纵向协同：协同编辑发生在相邻的两个任务之问。考虑一个群体协作 编辑一份报告的例子来说明这种情况，流程如下图所示。审稿活动可以在起草活 动进行了一部分以后就提前进行，随后两者并发进行，审稿人可以参考起草人的 山东大学硕士学位论文 编辑情况动态改变自己的审稿结果，另一方面起草人可以及时得到审稿人的反馈 意见及早地对草案进行修改。 abc 图2 2 纵向协同示意图 由于工作流领域的特殊性，对协同编辑提出了更高的要求，要能同时支持同 步协作模式和异步协作模式。 工作流的执行过程是一个长时间的过程，需要在多个环节之间流转。在流转 过程可能需要多次进行协同编辑，即整个协同编辑过程是个不连续的过程。在每 个协同编辑任务的过程中采用同步协作模式，多个用户之间进行实时的交互；在 两次协同编辑任务之间，则需要采用异步协作模式，文档保存到一个固定的中心 服务器，下一次执行协同编辑任务时，用户从中心服务器下载最新的文档。 同步协作模式的协同编辑要求支持无限制的协同。所谓无限制的协同【4 】，是指 在协同编辑期间的任何时刻，每个用户都能够并发地，并且是自由地编辑共享文 档的任意部分。 要实现无限制的协同，可以借鉴g f o v e 、r e d u c e 这些协同编辑工具的协同机 制。在这些系统里，一种乐观的并发控制机制，操作变换( 0 p e r 撕o n a l t f a n s f b 咖觚o n ，简称o ，n 【9 l ，被用来维护文档在全局的一致性。在每个客户端都拥 有共享文档的一个副本，所有的用户都可以自由地对文档进行编辑，这些操作在 本地立即执行，然后把操作广播给其他的客户端，操作在远程的客户端执行之前 先要进行操作变换。如果能把操作变换机制引入到单用户应用程序共享系统中来， 就可以实现对无限制协同的支持。 2 3 本章小结 工作流技术在管理、生产等领域得到了非常广泛的应用。在工作流的流转过 程中，单个参与者所执行的任务并非是独立的。很多情况下多个参与者会对同一 份文档、同一个数据对象进行操作，他们之间需要协同编辑，才能达到一个整体 的目标。现有的工作流系统在处理需要协同交互的过程时却有着很大的局限性。 山东大学硕士学位论文 很多优秀的协同编辑工具，如g v e 、r e d u c e 等都很好的支持实时的协同交互， 但作为编辑工具来讲，其功能和可用性远不如某些常用的单用户应用程序，如m s w b r d 。为了既能拥有强大的编辑功能和可用性，又能很好的支持协同交互，对单 用户应用程序进行扩展是个很好的方案。 山东大学硕士学位论文 第3 章一种扩展单用户应用程序实现协同编辑的方法 3 1 扩展单用户应用程序实现无限制协同 无限制的协剐“】，是指在协同编辑期间的任何时刻，每个用户都能够并发地， 并且是自由地编辑共享文档的任意部分。每个用户在对共享文档编辑时不会被其 他用户的操作所打断，感觉自己是在独占文档。 为了达到无限制协同的目的，用户的操作必须在本地立即执行而产生效果， 同时将操作广播给其他用户。其他站点接收到远程操作以后，应当在后台执行相 应的操作，同时不能本地用户在前台的编辑活动。 在这个过程中，非常重要的一点就是保持各个用户拥有的文档的一致性。操 作变换机制是协同编辑领域广泛应用的一种维持数据全局一致性的方法。 一个操作变换算法( 以下简称o t 算法) 一般可以分为两部分，上层的控制算 法和下层的操作变换函数。控制算法负责操作的广播、接收、和执行，并负责维 护操作历史序列，它与具体的操作变换函数是独立：操作变换函数则负责对定义 在相同文档状态下的两个操作进行变换。两层结构使得操作变换算法的设计更加 灵活，易于重用。 操作变换机制并非适用于任意结构的文档。操作变换要求共享文档中的对象 存储在一维或多维的地址空间中，并且可以使用位置作为索引定位对象例。但在用 户界面上，文档中的对象不一定非要按照线性顺序排列。 m sw b r d 是个很好的例子，它支持文字和图表的混排，在界面上不是按照严 格的线性顺序排列。在m sw b r d 提供的a p i 中，个w a r d 文档对应于一个 d o c u m e n t 对象，一块连续的w b r d 文档区域对应一个r 舶g e 对象。在c o w b r d 方 法中，利用r 册g e 对象中包含的线性表来对文档内部的对象进行定位，从而达到 了操作变换所要求的条件。 然而在不同的单用户应用程序中，文档内部对象的存储方式是各不相同的。 为了对尽可能多的单用户应用程序进行扩展，本文对c o w b r d 【1 1 1 的方法进行扩展。 用户利用单用户应用程序对文档的操作是多种多样，如剪切粘贴一段文本， 改变某个图像的大小，改变文本的字体，删除某个表格等。这些操作最终都可以 转化为三种元操作：插入对象，删除对象，更新对象属性。这三种元操作的形式 可以归结如下： 山东大学硕士学位论文 h l s e r t o b j t ( 定位参数，o b j ) d e l e t e o b j e c t ( 定位参数) u p d 砒e o b j 酬定位参数 i l 锄e ，砌u e ) 其中，定位参数指明了如果对目标对象进行定位，o b j 是待插入的对象，n 锄e 代表对象属性的名称，v a i 代表属性的值。 另一方面，为了符合操作变换机制的要求，定义个包含文档中所有对象的 线性表和一个在线性表上的操作集。线性表的结构如图l 所示。 图3 - 1 线性表 线性表上的操作集定义如下： h i s e r “p o s ，o b j ) d e l e t e s ) u p d a t e ( p o s ，n 锄e ，v a l u e ) 其中p o s 代表操作的目标对象在线性表的位置。显然线性表符合操作变换机制 所要求的条件。如果能把对文档的三种元操作映射为线性表上的三种操作，可以 对线性表上的三种操作进行操作变换来间接达到维持共享文档全局一致性的目 的。关键是要实现定位参数和p o s 之间的互相映射，这样就能实现两个操作集合之 间的映射。从图2 中我们看到这种映射关系。 图3 2 不同层次操作之间的映射 在每个客户端都有一个单用户应用程序的实例( 包含了共享文档的副本) ，以及 一个用于索引对象的线性表。操作变换的作用对象是对线性表的操作： h l s 酬b o s ，o b j ) ，d e l 咖( p o s ) ，u p d a 喊p o s ，n 锄e ，v a l u e ) 。本地客户端把对线性表的操 山东大学硕士学位论文 作广播给其他的客户端，利用操作变换机制维护各个客户端的线性表的一致性。 由于最终的目的是对单用户应用程序中的文档进行协同，线性表要同应用程序中 的文档保持同步。一方面，用户通过单用户应用程序对本地文档进行了修改，线 性表中的内容也要进行相应的改变；另一方面，从其他客户端到来的对线性表的 操作，也得引起单用户应用程序中的文档进行相应更新。 当用户利用单用户应用程序对文档进行操作时，截获其鼠标键盘事件。调用 应用程序的a p i ，根据鼠标，键盘事件提供的参数解析出被操作对象的定位参数以 及被修改的属性名和属性值，从而映射为应用程序元操作。然后根据定位参数解 析出对象在线性表的位置p o s ，进一步映射为线性表操作。对线性表执行了相应操 作以后，需要将线性表操作广播给其他客户端。 当某个客户端收到其他客户端发来的线性表操作时，首先对其进行操作变换， 然后根据线性表操作的位置参数p o s 解析出目标对象的定位参数，从而将线性表操 作映射为应用程序元操作，最后调用相应的a p i 对文档进行更新。 在客户端之间传播的是线性表操作，操作变换对线性表操作进行并发控制， 以维持文档在全局的一致性。传统的o t 算法只能处理插入和删除操作，为了支持 更新对象属性的操作，必须将0 t 算法进行扩展。下一节将提出一个改进的扩展 0 t 算法。 3 2 改进的扩展0 t 算法 如前所述，0 t 算法可以分成两层，下层是变换函数，上层是控制算法。变换 函数决定了一个操作针对另一个操作如何进行变换，操作参数怎样进行调整；控 制算法则负责对本地的操作队列进行管理，一个远程操作到达时与队列中的哪些 操作进行变换，以何种顺序与这些操作进行变换。从整体上来看，控制算法要对 变换函数进行调用。 d 撕d s 吼在变换函数层上对传统的0 t 算法进行了扩剧“，下文将首先介绍这 种扩展，然后在控制算法层对d 撕ds 眦的算法进行改进。 3 2 。1 扩展变换函数 在g 0 1 吣算法中变换函数分为两类。一类是h l c l 吣i o nt r 缸s f b 删撕函数 山东大学硕士学位论文 ( o l ，0 2 ) ，0 l 针对0 2 做变换，使0 1 在不影响自身操作效果的基础上能包含0 2 的操 作效果；另一类是e x c i u s i o n 伽l s f b m l 撕函数e t ( o l ，0 2 ) ，使o l 在不影响自身操 作效果的基础上能去除0 2 的操作效果。 上文提到对线性表的操作有三种：h l 吣o s ，o b j ) ，d e l 蜥s ) ， u p d 砒e s n 锄e 州u e ) 。g o t o 算法的变换函数只能支持i l l s e n 和d e l 咖两种操作。 其算法如算法l 和算法2 所示。o 代表操作，o t y p e 代表操作的类型( 可以为 玳s e r t ，d e 唧) ，o p 代表操作的位置参数，o o b j 代表操作的对象。 算法lh 函数 ( o l ，0 2 ) 0 l l ：o l ：0 1 ； 2 ：i f ( o l p 0 2 p ) 3 ：i f ( 0 2 t y p e = 踯e r t ) 4 ： o l p + = 1 ； 5 ： d i f ( 0 ，白，p e = d e l e r r e ) 6 0 1 p 二l ； 7 ： d i f ( 0 1 p = 0 2 p ) 8 ： i f ( 0 1 1 y p e = 吣e r t 锄d0 2 t y p e = 矾s e 盯柚d o l i d 0 2 i d ) 9 ： o l p 十= l ； 删用比较用户i d 来解决插入冲突 l o ： e 1 辩i f ( ( o l t y p e = d e l e t e ) a n d 0 2 1 y p e 2 矾s e r t ) l l ： 0 1 p + ：l ； 1 2 ： d i f ( ( o l l y p e = d e l e l e ) m l d 0