多屬性動態醯序結構上協同控制法的研究

Abstract

近年來, 在動態樹狀結構上, 如B-tree, 提出了許多的協同控制法, 而在動態醢序結 構上, 其協同控制法的研究則很少。至於在多屬性醢序結構上, 其協同控制法的研究 更是幾乎找不到。然而, 多屬性醢序結構的應用層面卻更為廣泛。因此在本論文中, 我們研究多屬性延展醢序及多屬性線性醢序的結構, 并分別為其提出適當的協同控制 法。這些協同控制法結合了樂觀協同控制法的原則以及機動鎖定, 外加對資料結構及 其運算語意的預先了解, 因而能降低負荷且提高并行執行的程度。 在多屬性延展醢序上的協同控制法, 允許搜尋以及部分匹配搜尋于插入運算同時進行 而不需任何鎖定。它也準許插入以及去除運算同時進行而不需鎖定目錄。利用重復讀 取以及檢查目錄, 此方法亦能夠保證資料結構的一致性和正確性。 在多屬性線性醢序的協同控制法上, 當并行運算間有了衝突時, 除了使用難的技術來 重新嘗試外, 它使用一個遞增的計數器把大部份不必要的嘗試給過濾掉而允許搜尋, 部分匹配搜尋, 插入以及去除運算能與分裂及結合運算同時進行。此外, 搜尋以及部 分匹配搜尋運算不需任何鎖定, 并且其他運算也不需對檔案的通用變數作鎖定, 因此 此系統能提供較高的並行程度。 最后, 本論文使用機率理論上的隨步模式, 將線性醢序上協同控制法的錯誤嘗試正規 化。根據此正規化的結果, 我們僅需對此協同控制法作一微小的修改即可幾乎去除所 有可能的錯誤嘗試。此外, 此項正規化于去除錯誤法試的經驗激發我們應用隨步模式 來研究另外一個問題一堆疊器空間分派的績效分析。根據此分析結果, 一旦分派空間 給堆疊器后, 其滿溢的機率便很容易決定。因此使得我們能夠分派適當大小的空間給 堆疊器并使堆疊器的運用更為有效而不會浪費儲存體的資源。