基于操作轉(zhuǎn)換的并發(fā)控制算法的研究

孫 敏 王瑞花

(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)

基于操作轉(zhuǎn)換的并發(fā)控制算法的研究

孫 敏 王瑞花

(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)

為解決協(xié)同圖形編輯中出現(xiàn)的結(jié)果不一致、因果不一致、操作意愿不一致和語(yǔ)意不一致問(wèn)題，提出一種基于操作轉(zhuǎn)換的并發(fā)控制算法。該算法定義了操作序列的上下文有序、操作序列的上下文并發(fā)等概念。從協(xié)同編輯操作的預(yù)處理及實(shí)際執(zhí)行時(shí)的操作轉(zhuǎn)換兩個(gè)方面，對(duì)基于上下文的操作轉(zhuǎn)換(COT)算法進(jìn)行改進(jìn)，并進(jìn)行實(shí)例驗(yàn)證分析。研究發(fā)現(xiàn)，其可有效地減少COT算法中存在的操作轉(zhuǎn)換冗余的問(wèn)題。

并發(fā)控制 協(xié)同編輯 操作轉(zhuǎn)換 上下文有序

0 引 言

實(shí)時(shí)協(xié)同編輯支持地域上分散的用戶(hù),通過(guò)網(wǎng)絡(luò)在同一時(shí)間對(duì)一共享文檔進(jìn)行編輯,并保證所有操作都能正確執(zhí)行。由于存在人為或網(wǎng)絡(luò)延遲等不可預(yù)料因素，若對(duì)各站點(diǎn)上協(xié)同操作的執(zhí)行不加以控制，就可能會(huì)產(chǎn)生副本的不一致。協(xié)同圖形編輯是協(xié)同編輯的一個(gè)子研究領(lǐng)域，對(duì)編輯過(guò)程進(jìn)行有效的并發(fā)控制和一致性維護(hù)是研究的重點(diǎn)。相應(yīng)的方法除有令牌環(huán)機(jī)制、鎖機(jī)制和串行化機(jī)制等傳統(tǒng)方法之外，目前主流的有兩類(lèi)：基于對(duì)象復(fù)制的多版本方法和基于操作轉(zhuǎn)換的方法[1]。

Kanawati等在文獻(xiàn)[2]中提出基于多版本技術(shù)的共享對(duì)象一致性保持算法。該算法將沖突操作的效果應(yīng)用到同一操作對(duì)象的不同副本,無(wú)沖突操作應(yīng)用到同一對(duì)象,從而使共享副本保持一致。楊君等提出基于版本復(fù)制的多版本模型[3],并設(shè)計(jì)多版本增創(chuàng)算法MVIC(Multiple Versions Incremental Creation)。之后許多研究人員在MVIC的基礎(chǔ)上進(jìn)行了諸多改進(jìn)。但是，隨著協(xié)同用戶(hù)的不斷增加、協(xié)同工作的逐漸深入，此類(lèi)算法要求站點(diǎn)維系的版本數(shù)量也不斷增多，操作之間的沖突也趨于復(fù)雜。這對(duì)信息的管理和存儲(chǔ)提出挑戰(zhàn)，同時(shí)也使得最終版本的選擇策略趨于復(fù)雜，實(shí)時(shí)響應(yīng)也變得有點(diǎn)不現(xiàn)實(shí)。

基于操作轉(zhuǎn)換的算法最早由Ellis等提出[4]，他提出分布式操作轉(zhuǎn)換算法 (dOPT)，是一種樂(lè)觀并發(fā)控制方法。該算法能很好地解決因果和操作意愿維護(hù)問(wèn)題，但算法構(gòu)造的轉(zhuǎn)換函數(shù)僅限于特定應(yīng)用，存在不足。之后又出現(xiàn)大量對(duì)dOPT的改進(jìn)算法。如Ressel等提出adOPTed算法[5-6]，是在 dOPT基礎(chǔ)上，加入L-轉(zhuǎn)換和多維交互圖，它能解決因果和操作意愿一致性維護(hù)，但并不能完全解決數(shù)據(jù)不一致問(wèn)題。之后Sun等[7]提出GOT及其優(yōu)化算法，即GOTO。GOT只針對(duì)簡(jiǎn)單并發(fā)問(wèn)題，通過(guò)設(shè)計(jì)包含轉(zhuǎn)換和排斥轉(zhuǎn)換兩種轉(zhuǎn)換函數(shù)來(lái)進(jìn)行一致性維護(hù)，沒(méi)有解決偏并發(fā)問(wèn)題，而GOTO則是在GOT的基礎(chǔ)上解決了偏并發(fā)問(wèn)題。此外，還有SOCT2、SOCT3、TIBOT、 COT等操作轉(zhuǎn)換算法。COT算法是由Sun等提出的[8-9]。此算法通過(guò)引入操作上下文的概念來(lái)系統(tǒng)地表述和判斷協(xié)同操作間的關(guān)系，為操作副本的一致性維護(hù)提供了有效方法。

COT算法是目前在實(shí)際中應(yīng)用最廣泛的算法。但是，COT算法仍然存在許多不足。本文就是對(duì)COT算法中存在的不足進(jìn)行研究和改進(jìn)。

1 相關(guān)理論基礎(chǔ)

1.1 基本關(guān)系描述

在協(xié)同編輯中，各個(gè)協(xié)同副本及操作之間存在的關(guān)系[8-9]如下所示：

1) 文檔狀態(tài)

表示某時(shí)刻某個(gè)站點(diǎn)副本的狀態(tài)，是一個(gè)動(dòng)態(tài)變化的已執(zhí)行操作的集合。

(1) 初始情況下,定義站點(diǎn)的文檔狀態(tài)DS={}；

(2) 當(dāng)有操作O執(zhí)行后，其文檔狀態(tài)為DS′=DS∪{org(O)}，其中org(O)是O的原始表示。

2) 操作上下文(C(O))

(1) 對(duì)于一個(gè)原始操作，C(O)=DS；

(2) 對(duì)于轉(zhuǎn)換操作O′，C(O′)=C(O)∪{org(O)}，其中O′=IT(O,Ox)。

3) 上下文依賴(lài)關(guān)系(上下文因果關(guān)系)

4) 上下文等價(jià)關(guān)系

給定兩個(gè)操作Oa和Ob以及其上下文C(Oa)和C(Ob)，稱(chēng)操作Oa和Ob的上下文是等價(jià)的，當(dāng)且僅當(dāng)C(Oa)=C(Ob)。

1.2 協(xié)作編輯中的不一致問(wèn)題

由于人為或網(wǎng)絡(luò)延遲等原因，各協(xié)同操作到達(dá)站點(diǎn)是無(wú)序的。若對(duì)各站點(diǎn)上操作的執(zhí)行不加控制，就可能會(huì)產(chǎn)生副本不一致，如圖1所示。

圖1 協(xié)同站點(diǎn)間的并發(fā)操作

常見(jiàn)的不一致有以下4種[10]：

1) 結(jié)果不一致

假設(shè)O1、O2、O3的執(zhí)行順序一定。在各個(gè)站點(diǎn)上，如果操作的執(zhí)行順序沒(méi)有限制，就可能產(chǎn)生結(jié)果不一致。假設(shè)站點(diǎn)初始狀態(tài)為“A12Ba”，若O1:Insert(2,"C")，O2:Delete(3)，O3:Insert(4,"5")，則在站點(diǎn)1的執(zhí)行結(jié)果為“A12B5a”，在站點(diǎn)2的執(zhí)行結(jié)果為“A1C2B5”。

2) 因果不一致

由于網(wǎng)絡(luò)延時(shí)，難以保證操作信息按產(chǎn)生的順序到達(dá)各個(gè)站點(diǎn)。如果這些遠(yuǎn)程操作在執(zhí)行時(shí)不加限制，就可能產(chǎn)生不一致。

3) 操作意愿不一致

是指協(xié)作者期望達(dá)到的效果與實(shí)際產(chǎn)生的結(jié)果不同。仍以1)中數(shù)據(jù)為例，O2實(shí)際意義是刪除“A12Ba”中第三個(gè)位置上的“2”,但在站點(diǎn)1，實(shí)際刪除的是O1插入的“C”，這違背了協(xié)作者的意愿，產(chǎn)生不一致。

4) 語(yǔ)義不一致

在基于對(duì)象的協(xié)同圖形編輯中，圖形對(duì)象可能存在空間位置上的依賴(lài)關(guān)系，也可能存在某些相關(guān)屬性的依賴(lài)關(guān)系。如果操作執(zhí)行時(shí)，違背了這些語(yǔ)義關(guān)系，就會(huì)產(chǎn)生不一致。如圖2所示，并發(fā)操作O1、O2，O1是改變橢圓1的大小，O2是改變橢圓2的位置。若操作的對(duì)象相互獨(dú)立，則O1、O2間不存在沖突。若在操作對(duì)象間建立聯(lián)系：兩個(gè)橢圓大小相等、位置平行，則O1、O2在兩個(gè)協(xié)同站點(diǎn)執(zhí)行，雖能保證結(jié)果一致，但會(huì)違背語(yǔ)義約束，出現(xiàn)操作語(yǔ)義的不一致。

圖2 圖形對(duì)象間的依賴(lài)關(guān)系

2 COT算法及改進(jìn)

基于操作轉(zhuǎn)換的算法通常分為兩部分[11]：高層的轉(zhuǎn)換控制算法和底層的轉(zhuǎn)換函數(shù)。當(dāng)?shù)竭_(dá)站點(diǎn)的遠(yuǎn)程操作已就緒，根據(jù)操作間的上下文關(guān)系，轉(zhuǎn)換控制算法決定哪些操作需與此操作進(jìn)行轉(zhuǎn)換，及應(yīng)采用怎樣的轉(zhuǎn)換順序；轉(zhuǎn)換函數(shù)是通過(guò)對(duì)操作的各種參數(shù)進(jìn)行分析，來(lái)確定將以何種方式進(jìn)行操作間的轉(zhuǎn)換。而轉(zhuǎn)換屬性和條件則是介于轉(zhuǎn)換控制算法和具體的轉(zhuǎn)換函數(shù)之間，主要用來(lái)保證遠(yuǎn)程操作的正確轉(zhuǎn)換和執(zhí)行，以及最終版本的一致性維護(hù)。因此，對(duì)協(xié)同編輯中的并發(fā)控制和一致性維護(hù)進(jìn)行研究，一般是從以上這兩個(gè)方面入手。

2.1 基于上下文的操作轉(zhuǎn)換算法COT

COT算法是基于上下文的操作轉(zhuǎn)換算法。在各個(gè)協(xié)同站點(diǎn)，都維護(hù)著一個(gè)文檔狀態(tài)DS，是已執(zhí)行操作的集合。COT的基本思路是：本地操作立即執(zhí)行，遠(yuǎn)程操作O只有當(dāng)操作上下文C(O)與接收站點(diǎn)的文檔狀態(tài)相同時(shí)，才能執(zhí)行。因此，站點(diǎn)接收到O，首先檢測(cè)是否上下文就緒。若準(zhǔn)備就緒，查看O的上下文與站點(diǎn)的文檔狀態(tài)是否一致，若一致，則O立即執(zhí)行；否則需通過(guò)一定的轉(zhuǎn)換，將O的上下文上升到接收站點(diǎn)的文檔狀態(tài)，或者說(shuō)，將O轉(zhuǎn)換為可執(zhí)行的形式，然后執(zhí)行。執(zhí)行完后更新站點(diǎn)的文檔狀態(tài)。具體COT算法如下(算法1和算法2)：

算法1

COT(O,DS)

O′=transform(O,DS-C(O))；

執(zhí)行O′；

DS=DS∪{org(O′)}

算法2

transform(O,CD)

循環(huán)直到CD={}；

從CD中選擇并移出Ox,滿(mǎn)足C(Ox)?C(O)；

transform(Ox,C(O)-C(Ox))；

O′=IT(O,Ox)；

C(O′)=C(O)∪{org(Ox)}

2.2 COT算法的不足及改進(jìn)

2.2.1 COT算法的不足

定義2 假設(shè)存在兩個(gè)上下文有序的圖形編輯操作序列L1、L2，若C(L1)=C(L2)，稱(chēng)L1、L2上下文并發(fā)，即L1‖L2。

定義3 假設(shè)存在圖形編輯操作序列L1、L2，若滿(mǎn)足條件L1‖L2，當(dāng)且僅當(dāng)C(L1)?L1=C(L2)?L2時(shí)，L1與L2等價(jià)，即L1≡L(fǎng)2(C(L1)?L1指在文檔狀態(tài)為C(L1)時(shí)順序執(zhí)行L1中的操作)。

2.2.2COT算法的改進(jìn)

在各個(gè)協(xié)同站點(diǎn)，都包含有如下的4個(gè)隊(duì)列：產(chǎn)生隊(duì)列GH、接收隊(duì)列RH、等待隊(duì)列WH及實(shí)際操作執(zhí)行序列H(H中存放的是各個(gè)操作的最近轉(zhuǎn)換形式，由LLT轉(zhuǎn)換得到)。由操作轉(zhuǎn)換的基本思想可知，本地操作的優(yōu)先權(quán)高于遠(yuǎn)程操作。當(dāng)某個(gè)遠(yuǎn)程操作獲得優(yōu)先權(quán)，進(jìn)行轉(zhuǎn)換執(zhí)行時(shí)，若有本地操作產(chǎn)生，則將其加入到GH及H中。當(dāng)某個(gè)遠(yuǎn)程操作執(zhí)行完后，首先要查看執(zhí)行站點(diǎn)的GH是否為空，若不為空，則將GH中的操作進(jìn)行轉(zhuǎn)換和封裝，然后發(fā)送到各協(xié)同站點(diǎn)。

本文提出的并發(fā)控制算法分為兩部分：一部分是GH中的操作轉(zhuǎn)換封裝、遠(yuǎn)程站點(diǎn)協(xié)同操作的接收及具體操作的執(zhí)行，另一部分是對(duì)COT算法的改進(jìn)，分別如算法3和算法4所示。

算法3

1) 本地操作的傳播

步驟1 若站點(diǎn)的RH為空，則直接將GH中的操作封裝為一個(gè)協(xié)同請(qǐng)求，傳輸?shù)礁鱾€(gè)協(xié)同站點(diǎn)。

步驟2 若站點(diǎn)的RH不為空，則通過(guò)調(diào)用LLT(GH,RH)轉(zhuǎn)換，將GH中的操作和RH中的操作進(jìn)行轉(zhuǎn)換，然后將GH中經(jīng)轉(zhuǎn)換后的操作封裝為一個(gè)協(xié)同請(qǐng)求，傳輸?shù)礁鱾€(gè)協(xié)同站點(diǎn)。

2) 遠(yuǎn)程操作的接收

步驟1 查看協(xié)同請(qǐng)求中的操作L是否因果就緒，若沒(méi)有就緒，則將其加到WH的隊(duì)尾；否則轉(zhuǎn)步驟2。

步驟2 查看接收站點(diǎn)的RH是否為空，若為空，則查看協(xié)同請(qǐng)求中的操作序列L的上下文與DS的關(guān)系。若相等，則直接將L中的操作加到RH的隊(duì)尾，并更新H；若不相等，則通過(guò)調(diào)用ICOT(L,DS)，將操作序列L轉(zhuǎn)換為可執(zhí)行形式，然后將其加到RH的隊(duì)尾，并更新H,然后轉(zhuǎn)步驟3。

步驟3 若RH非空，則直接調(diào)用ICOT(L,RH)。然后將轉(zhuǎn)換后的操作加到RH的隊(duì)尾，并更新H。

步驟4 一旦WH中的操作滿(mǎn)足因果就緒，則將其與協(xié)同請(qǐng)求中的操作先進(jìn)行轉(zhuǎn)換結(jié)合，使其整體上下文有序(轉(zhuǎn)換過(guò)程仍通過(guò)ICOT實(shí)現(xiàn))，然后轉(zhuǎn)步驟2。

算法4

LLT(L1,L2)：

算法5

SIT(O1,O2)：操作O1、O2是上下文等價(jià)

3) 遠(yuǎn)程操作的執(zhí)行

選中將要執(zhí)行的操作O=RH[0]，如果GH為空，則直接執(zhí)行操作O即可；若GH不為空，則調(diào)用LLT(O,GH)，然后再執(zhí)行經(jīng)過(guò)轉(zhuǎn)換后的操作。

ICOT算法，是對(duì)COT算法的改進(jìn)，如算法6所示。

算法6

ICOT(L,ds)：

步驟1 判斷L的上下文與ds間的關(guān)系。若C(L)=ds，則操作序列保持不變，否則轉(zhuǎn)步驟2；

步驟2 獲得上下文差異集CD，CD=ds-C(L)，對(duì)于CD中的每一組操作，均是上下文有序的。循環(huán)選取CD中的每一組上下文有序的操作序列Q，并從H中獲得其操作序列的最近轉(zhuǎn)換形式Q′，選擇與L的上下文更接近的操作序列作為Q。若C(L)=C(Q)，則調(diào)用LLT(L,Q)；否則，令ds=C(Q)-C(L)，遞歸地調(diào)用ICOT(L,ds)。

2.3 實(shí)例分析

假設(shè)有7個(gè)協(xié)同操作，在各協(xié)作站點(diǎn)的執(zhí)行順序以及操作之間的關(guān)系如圖3所示，初始的文檔狀態(tài)為空。假設(shè)在站點(diǎn)1，當(dāng)接收遠(yuǎn)程操作時(shí)，GH中的操作還沒(méi)有進(jìn)行傳播，即GH不為空；在站點(diǎn)2和3，當(dāng)接收遠(yuǎn)程操作時(shí)，GH為空(假設(shè)遠(yuǎn)程操作接收后不會(huì)執(zhí)行)。

圖3 實(shí)例分析圖

通過(guò)對(duì)改進(jìn)前后的算法進(jìn)行對(duì)比分析可知，改進(jìn)后的算法在協(xié)同操作向其他站點(diǎn)發(fā)送之前，以及遠(yuǎn)程操作在接收之時(shí)，均進(jìn)行了操作轉(zhuǎn)換。且發(fā)送和接收的并不是操作的原始形式，而是其轉(zhuǎn)換后的形式。通過(guò)這種預(yù)處理方式，可以有效地減少操作間轉(zhuǎn)換的重復(fù)，減少轉(zhuǎn)換的次數(shù)。

3 實(shí)驗(yàn)及算法的正確性分析

3.1 實(shí)驗(yàn)及分析比較

通過(guò)模擬實(shí)驗(yàn)對(duì)COT算法和本文算法的性能進(jìn)行比較分析。假設(shè)有9個(gè)協(xié)同操作，在各協(xié)同站點(diǎn)的執(zhí)行順序以及各個(gè)操作之間的關(guān)系如圖4所示(初始文檔狀態(tài)為空)。在兩個(gè)算法中，任意操作的響應(yīng)時(shí)間均由三部分構(gòu)成：操作傳播時(shí)間、操作在遠(yuǎn)程站點(diǎn)進(jìn)行響應(yīng)轉(zhuǎn)換的時(shí)間、操作執(zhí)行的時(shí)間，其中操作進(jìn)行轉(zhuǎn)換的時(shí)間起主導(dǎo)作用。故對(duì)兩個(gè)算法進(jìn)行模擬實(shí)驗(yàn)和性能分析，可以用操作執(zhí)行時(shí)需轉(zhuǎn)換的次數(shù)來(lái)代替操作的響應(yīng)時(shí)間(如圖5、圖6所示)。

圖4 模擬協(xié)同操作的執(zhí)行

在站點(diǎn)2上的運(yùn)行結(jié)果如圖5所示。

圖5 兩種算法中操作轉(zhuǎn)換次數(shù)的比較(站點(diǎn)2)

在站點(diǎn)3上的運(yùn)行結(jié)果如圖6所示。

圖6 兩種算法中操作轉(zhuǎn)換次數(shù)的比較(站點(diǎn)3)

從實(shí)驗(yàn)結(jié)果對(duì)比分析可知，遠(yuǎn)程操作在轉(zhuǎn)換執(zhí)行時(shí)，若采用COT算法，則隨著協(xié)同操作數(shù)的增加，操作執(zhí)行時(shí)需轉(zhuǎn)換的次數(shù)增加幅度遠(yuǎn)遠(yuǎn)大于采用本文算法。因此，本文算法可大幅度減少操作轉(zhuǎn)換的次數(shù)，減少遠(yuǎn)程操作的響應(yīng)時(shí)間，增加實(shí)時(shí)協(xié)同編輯時(shí)的效率。

3.2 改進(jìn)前后算法時(shí)間復(fù)雜度的比較

對(duì)于改進(jìn)前后的算法，其核心操作是進(jìn)行操作間的轉(zhuǎn)換，因此對(duì)改進(jìn)前后算法的時(shí)間復(fù)雜度進(jìn)行分析比較，也就是要對(duì)操作間的轉(zhuǎn)換次數(shù)進(jìn)行比較分析。改進(jìn)后的本文算法，通過(guò)引入操作序列上下文有序及并發(fā)的概念，有效地減少了操作間轉(zhuǎn)換的多次重復(fù)，減少了總的轉(zhuǎn)換次數(shù)。

1) 假設(shè)存在操作O1,O2,…,On，C(O1)=C(O2)=…=C(On),若采用COT進(jìn)行操作的轉(zhuǎn)換執(zhí)行，轉(zhuǎn)換次數(shù)[9]為：

若采用本文算法，在轉(zhuǎn)換的過(guò)程中，只有LLT轉(zhuǎn)換。轉(zhuǎn)換的次數(shù)為：T(n)=n-1。

2) 假設(shè)存在兩組上下文有序序列S1=O1,1,O1,2,…,O1,n、S2=O2,1,O2,2,…,O2,n,S1和S2上下文并發(fā)。若采用COT對(duì)S2中的任一操作與S1中的操作進(jìn)行轉(zhuǎn)換執(zhí)行，轉(zhuǎn)換的次數(shù)為[9]：

若采用本文算法，在轉(zhuǎn)換中采用LLT和SIT轉(zhuǎn)換，進(jìn)行轉(zhuǎn)換的次數(shù)為：T(n,m)=2(m-1)×n+(n+m-1)。

對(duì)改進(jìn)前后算法中有代表性的兩類(lèi)操作間的轉(zhuǎn)換進(jìn)行比較分析，理論上證明改進(jìn)后的算法能有效地減少操作之間的轉(zhuǎn)換次數(shù)，且所減少的轉(zhuǎn)換次數(shù)均是COT算法中的冗余轉(zhuǎn)換。

3.3 本文算法中操作的正確執(zhí)行和轉(zhuǎn)換

在COT算法中引入操作的上下文，是方便對(duì)操作的正確執(zhí)行和轉(zhuǎn)換進(jìn)行統(tǒng)一管理。一個(gè)操作能正確執(zhí)行，需滿(mǎn)足:其定義上下文(操作產(chǎn)生時(shí)的文檔狀態(tài))與執(zhí)行上下文(操作執(zhí)行時(shí)的文檔狀態(tài))是相等的。兩個(gè)操作能正確轉(zhuǎn)換，則兩個(gè)操作需是上下文等價(jià)的。本文算法延續(xù)使用了操作的上下文，為保證改進(jìn)后算法中的并發(fā)操作能夠正確執(zhí)行和轉(zhuǎn)換[10]，在本文算法中，真正只用到了LLT和SIT轉(zhuǎn)換。因此只要LLT轉(zhuǎn)換滿(mǎn)足正確執(zhí)行和轉(zhuǎn)換的條件，那么本文算法中也同樣滿(mǎn)足條件。

4 結(jié) 語(yǔ)

本文針對(duì)在協(xié)同編輯中遇到的4種常見(jiàn)的不一致性問(wèn)題進(jìn)行闡述，對(duì)COT算法中存在的不足進(jìn)行分析，并在此基礎(chǔ)上，從兩個(gè)方面進(jìn)行改進(jìn)。改進(jìn)后的算法可有效地減少操作執(zhí)行時(shí)轉(zhuǎn)換的次數(shù)。但是，前文介紹的語(yǔ)義不一致問(wèn)題沒(méi)有解決，且在協(xié)同圖形編輯中，對(duì)于圖形編輯操作，有許多的操作是可以合并的，例如一個(gè)用戶(hù)對(duì)同一圖形對(duì)象的位置進(jìn)行多次移動(dòng)的操作，是可以合并為一個(gè)操作的。若在操作進(jìn)行傳播前能對(duì)這類(lèi)型的操作進(jìn)行一定的預(yù)處理，可以進(jìn)一步減少轉(zhuǎn)換的次數(shù)，提高協(xié)作的效率。怎樣使得語(yǔ)義得到一致性維護(hù)，什么樣的操作是可合并的操作，應(yīng)對(duì)這些可合并的操作進(jìn)行怎樣的合并處理，將是下一步要研究的重點(diǎn)。

[1] 薛良貴. 協(xié)同圖形編輯系統(tǒng)中操作合并的研究[D]. 廣州：華南理工大學(xué), 2010.

[2]KanawatiR.LICRA:Areplicated-datamanagementalgorithmfordistributedsynchronousgroupwareapplication[J].ParallelComputing,1997,22(13):1733-1746.

[3] 楊君, 竇萬(wàn)峰. 一種新的多版本增創(chuàng)算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(4):702-710.

[4]EllisCA,GibbsSJ.Concurrencycontrolingroupwaresystems[N].AcmSigmodRecord.ACM,1989,18(2): 399-407.

[5]ResselM,Nitsche-RuhlandD,Gunzenh?userR.Anintegrating,transformation-orientedapproachtoconcurrencycontrolandundoingroupeditors[C]//Proceedingsofthe1996ACMConferenceonComputerSupportedCooperativeWork.ACM,1996:288-297.

[6] 廖斌, 何發(fā)智, 荊樹(shù)旭. 實(shí)時(shí)協(xié)同工作系統(tǒng)中操作轉(zhuǎn)換算法綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(2):326-333.

[7]SunD,SunC.Operationcontextandcontext-basedoperationaltransformation[C]//Proceedingsofthe2006 20thAnniversaryConferenceonComputerSupportedCooperativeWork.ACM,2006:279-288.

[8]SunD,SunC.Context-basedoperationaltransformationindistributedcollaborativeeditingsystems[J].IEEETransactionsonParallelandDistributedSystems, 2009, 20(10): 1454-1470.

[9] 許堅(jiān), 姜曉峰, 張坤．基于圖形對(duì)象的一致性維護(hù)問(wèn)題的研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012, 29(2): 261-265.

[10]Sun,C.OTFAQ:OperationalTransformationFrequentlyAskedQuestionsandAnswers[EB/OL].http://www3.ntu.edu.sg/home/czsun/projects/otfaq/.[11]SunC,WenH,FanH.Operationaltransformationfororthogonalconflictresolutioninreal-timecollaborative2deditingsystems[C]//ProceedingsoftheACM2012ConferenceonComputerSupportedCooperativeWork.ACM, 2012:1391-1400.

[12]Agustina,SunC,XuD.Operationaltransformationfordependencyconflictresolutioninreal-timecollaborative3Ddesignsystems[C]//ProceedingsoftheACM2012conferenceonComputerSupportedCooperativeWork.ACM, 2012:1401-1410.

[13]Agustina,SunC.Dependency-conflictdetectioninreal-timecollaborative3Ddesignsystems[C]//Proceedingsofthe2013ConferenceonComputerSupportedCooperativeWork.ACM, 2013:715-728.

[14]XuY,SunC,LiM.Achievingconvergenceinoperationaltransformation:conditions,mechanismsandsystems[C]//Proceedingsofthe17thACMConferenceonComputerSupportedCooperativeWork&SocialComputing.ACM, 2014: 505-518.

[15] 楊永濤, 黃國(guó)言.CSCW環(huán)境下協(xié)同設(shè)計(jì)并發(fā)控制算法的研究[J]. 現(xiàn)代計(jì)算機(jī): 中旬刊, 2014(4): 16-21.

RESEARCH ON CONCURRENT CONTROL ALGORITHM BASED ON OPERATIONALTRANSFORMATION

Sun Min Wang Ruihua

(SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006,Shanxi,China)

To solve the inconsistency problem about results, causality, operational intention and semantics in collaborative graphic editing, a concurrent control algorithm based on operational transformation is proposed. The algorithm defines the conceptions about the context order, the concurrency of operation sequence, etc. From preprocess of collaborative editing and operational transformation in cooperative editing operation, the context-based operational transformation (COT) algorithm is improved. After verifying and analyzing the instance, it is found that the redundant problem in operation transformation in COT algorithm can be effectively reduced.

Concurrent control Collaborative editing Operational transformation Context in order

2015-09-20。山西省科技基礎(chǔ)條件平臺(tái)建設(shè)項(xiàng)目(2014091004-0105)；山西省高等學(xué)校教學(xué)改革重點(diǎn)項(xiàng)目(J2013010)。孫敏，副教授，主研領(lǐng)域：計(jì)算機(jī)網(wǎng)絡(luò)。王瑞花，碩士生。

TP391

A

10.3969/j.issn.1000-386x.2017.01.048