协同编辑环境下基于树型结构的锁操作意愿维护研究

论文摘要

一致性维护是实时协同编辑系统中的核心问题,长期以来受到本领域研究学者的普遍重视。一致性维护包括句法一致性和语义一致性。已有的主流一致性维护方法:操作转换和地址空间转换可以有效维护实时协同编辑系统的句法一致性。而语义一致性的维护需要由锁操作来实现。锁操作在维护实时协同编辑系统语义一致性的同时,其自身也要满足一致性维护的要求,而其中锁操作的意愿维护是最主要也是最复杂的一部分。因此锁操作的意愿维护对保证实时协同编辑系统的语义一致性是至关重要的。在分析现有工作的基础上,本文基于操作转换和地址空间转换这两种一致性维护方法对锁操作的意愿维护进行了研究,主要研究内容如下:提出了基于操作转换的锁操作意愿维护算法TreeLock_GOTO,该算法使用树型结构的文档表示方式,并在文档的不同层级引入可选锁机制。和已有基于线形文档的锁操作转换算法相比,TreeLock_GOTO算法在维护锁操作意愿的同时,大大提高了锁操作的转换效率。提出了基于地址空间转换的锁操作意愿维护算法TreeLock_AST。地址空间转换是操作转换之外的另一种主流一致性维护方法,可以有效维护实时协同编辑系统的句法一致性。本文进一步研究发现和操作转换一样,地址空间转换可以有效维护锁操作的意愿。和TreeLock_GOTO算法相比,TreeLock_AST算法并不修正锁操作本身,而是将文档的地址空间回溯到锁操作生成时的状态,在这个状态下锁操作可以立即执行。从而避免了操作转换过程中操作间相对位置信息的丢失,而且转换过程更加直观更接近用户的自然编辑场景。给出了TreeLock_GOTO算法和TreeLock_AST算法的执行实例,详细讨论了这两个算法的执行效率,并设计了支持这两个算法的实时协同编辑系统构架。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 引言
• 1.1 CSCW与实时协同编辑系统概述
• 1.2 复制式结构下和一致性模型
• 1.3 实时协同编辑系统的一致性研究现状
• 1.3.1 CCl模型和句法一致性
• 1.3.2 语义一致性
• 1.3.3 一致性维护小结
• 1.4 锁操作的意愿维护
• 1.4.1 可选锁机制
• 1.4.2 锁操作的意愿维护和锁操作的一致性维护
• 1.4.3 锁操作的一致性维护和语义一致性维护
• 1.5 存在的问题
• 1.6 本文的目标及结构安排
• GOTO'>第二章 基于操作转换的锁操作意愿维护算法TreeLock_GOTO
• 2.1 引入可选锁机制的树型文档模型
• GOTO'>2.2 树型文档下的锁操作转换算法Lock_GOTO
• GOTO'>2.3 树型文档下的锁操作转换控制算法TreeLock_GOTO
• AST'>第三章 基于地址空间转换的锁操作意愿维护算法TreeLock_AST
• 3.1 地址空间转换思想
• 3.2 基于地址空间转换的锁操作一致性维护
• 3.3 地址空间转换下的树型文档模型
• 3.4 树型文档下的地址空间转换过程
• AST'>3.5 树型文档下的地址空间转换控制算法TreeLock_AST
• 第四章 算法实例、效率分析与系统构架设计
• GOTO算法实例'>4.1 TreeLock_GOTO算法实例
• GOTO算法效率分析'>4.2 TreeLock_GOTO算法效率分析
• AST算法实例'>4.3 TreeLock_AST算法实例
• 4.3.1 协同编辑场景
• 4.3.2 锁操作意愿维护
• 4.3.3 语义一致性维护
• AST算法效率分析'>4.4 TreeLock_AST算法效率分析
• 4.5 协同编辑系统构架设计
• 4.5.1 系统构架
• 4.5.2 系统构架实例
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 硕士期间科研工作
• 1.发表的论文
• 2.参与的科研项目