動態醢序結構上協同運算之設計

Abstract

由於多使用者資料庫系統的廣泛使用，為了降低運算的反應時間，增加單位產出以及 防止共時運算之間的交互影響，提供一套有效的協同控制法則除了能保持正確性之外 ，也能夠增加系統的平行度。 以往對於特殊資料結構上協同運算設計的研究多偏向於動態樹狀結構，對於動態醢序 結構上協同運算之設計並不多見，因為醢序結構在資料庫系統應用上的重要性日增， 本論文分別在可延展醢序檔及線性醢序檔上提出一套可以處理各種共時運算的協同控 制法則。此法則結合了樂觀協同控制法則中驗證的觀點以及在動態醢序結構上，運算 特殊及已知的語意。 利用重覆地檢查目錄的內容，可延展醢序檔上的運算法則不會產生死結的情況，並且 允許尋取運算與插入或去除運算同時進行而不需要鎖住目錄或資料頁，它也允許插入 及去除運算同時進行而不需要鎖住目錄。有關於此演算法之證明亦已提出予以討論。 在線性醢序檔上的演算法則在有共時運算發生交互影響而產生錯誤時，會導至受影響 運算的在嘗試，此種方法是利用一個遞增的計數器把一些不必要的再嘗試給去除掉， 而允許尋取，插入，去除運算與分裂以及結合運算同時進行。尋取運算不鎖住任何東 西而且插入與去除運算都不需要鎖住共用變數，使得系統擁有相當高的並行度。本論 文除了對此演算法則的正確性加以討論之外，也利用平均值法來計算〝假的再嘗試〞 發生的機率，並且討論一個計數器就足以應付所有的情況，與使用一個位元字串來記 錄分裂及結合運算的發生過程，會減少多少比例的〝假的再嘗試〞。