實時協(xié)同編輯系統(tǒng)中并發(fā)控制算法的研究.pdf

1、實時協(xié)同編輯系統(tǒng)是CSCW系統(tǒng)的一類重要應(yīng)用，它支持地理上分散的用戶通過網(wǎng)絡(luò)在同一時間瀏覽和編輯一個共享的文檔、圖形或者多媒體文件。為了支持實時、分布式和無約束的特點，系統(tǒng)通常采用全復(fù)制結(jié)構(gòu)，因此本文的重點是研究在全復(fù)制結(jié)構(gòu)下實時協(xié)同編輯系統(tǒng)的并發(fā)控制算法。 首先從協(xié)同編輯系統(tǒng)的特點出發(fā)，提出了協(xié)同編輯系統(tǒng)主要解決的問題是對并發(fā)操作進行合理的調(diào)度，消除并發(fā)操作之間的沖突，從而達到結(jié)果收斂、因果關(guān)系一致和操作意愿一致的要求。其次是

2、從分析和闡述目前國內(nèi)外各種實時協(xié)同編輯系統(tǒng)并發(fā)控制算法入手，對已經(jīng)存在的各種流行算法進行全面分析，總結(jié)了這些算法中存在的不足之處。 目前，GOT算法是被公認為較正確的算法，但GOT算法沒有光標控制機制，并且只能適用于簡單運算，本文提出了一種改進的并發(fā)控制算法IGOT，用于解決GOT算法中存在的問題和不足，使之更加適用于實際的協(xié)同編輯系統(tǒng)。該算法對原有算法的高層調(diào)度部分和低層調(diào)度部分分別進行了改進，在低層部分提出了光標控制機制，解

3、決實際編輯系統(tǒng)中光標位置一致性的問題：在高層部分引入了復(fù)雜運算，并將復(fù)雜運算分割成簡單運算進行封裝，可以按照簡單運算進行調(diào)度。 最后，通過分析IGOT算法的低層控制部分和高層控制部分，得到這兩部分的算法復(fù)雜度。在低層控制部分，根據(jù)操作和歷史緩存的并發(fā)關(guān)系證明操作變換控制策略，根據(jù)歷史緩存及其操作語義證明光標位置控制策略，然后將兩者結(jié)合證明低層控制算法的正確性。在高層控制部分，根據(jù)兩兩操作之間的語義和位置參數(shù)證明操作變換函數(shù)，從而