实时协同编辑系中并发控制算法的研究.pdf

硕l二学何论文 摘 要 实时协同编辑系统是CSCw系统的一类重要应用，它支持地理上分散的用户通过 网络在同一时间浏览和编辑一个共享的文档、图形或者多媒体文件。为了支持实时、分 布式和无约束的特点，系统通常采用全复制结构，因此本文的重点是研究在全复制结构 下实时协同编辑系统的并发控制算法。 首先从协同编辑系统的特点出发，提出了协同编辑系统主要解决的问题是对并发操 作进行合理的调度，消除并发操作之问的冲突，从而达到结果收敛、因果关系一致和操 作意愿一致的要求。其次是从分析和阐述目前国内外各种实时协同编辑系统并发控制算 法入手，对已经存在的各种流行算法进行全面分析，总结了这些算法中存在的不足之处。 目前，GOT算法是被公认为较正确的算法，但GOT算法没有光标控制机制，并且 只能适用于简单运算，本文提出了一种改进的并发控制算法IGOT，用于解决GOT算法 中存在的问题和不足，使之更加适用于实际的协同编辑系统。该算法对原有算法的高层 调度部分和低层调度部分分别进行了改进，在低层部分提出了光标控制机制，解决实际 编辑系统中光标位置一致性的问题：在高层部分引入了复杂运算，并将复杂运算分割成 简单运算进行封装，可以按照简单运算进行调度。 最后，通过分析IGOT算法的低层控制部分和高层控制部分，得到这两部分的算法 复杂度。在低层控制部分，根据操作和历史缓存的并发关系证明操作变换控制策略，根 据历史缓存及其操作语义证明光标位置控制策略，然后将两者结合证明低层控制算法的 正确性。在高层控制部分，根据两两操作之间的语义和位置参数证明操作变换函数，从 而证明高层摔制算法的正确性。 关键词：计算机支持协同工作；协同编辑；并发控制；光标位置维护；一致性维护 实时协同编辑系统中并发控制算法的研究 Abstract Real．time isa toolinthe applica“on rapidly CooperativeEditingSystemveryimportant View editthes锄e of it allowsa ofusersto and areas expanding CSCW，and group documentatthesametime丹om dispersed text／graphics／image／multimedia geographically networks．The for stributedand sitesconnectedcommunication real—time，di by requirements usto afull architectureforthe unconstrainedcollaborationhave1ed adopt replicated storage concullrentcontrol afull ofshareddocuments．This onthe algorit№of paperplacesemphasis architectureRECES． replicated adopted tothecharacteristicsof main