共享記憶體多處理機上非阻塞性的並行二元搜索樹演算法

Abstract

二元搜索樹( binary search tree)通常被應用於作業系統及資料庫系統和圖形演算法。非阻塞性(nonblocking)演算法保證某個程式能夠在有限的步驟內內完成其運算。相較於傳統的lock-based演算法，非阻塞性演算法具有較高的並行度與容錯性。在本論文文中，我們提出一個非阻塞性二元搜索樹演算法。為了避免並行插入和移除（concurrent insert and delete）而造成資料錯亂，我們使用輔助的節點在我們樹的結構上。我們也解決在不使用lock情況下，能使繼續維持二元搜索樹的特性。最後，我們證明這個演算法是正確的。

Binary search tree is often used in operating system, database system and graph algorithm. Nonblocking algorithm guarantees that some process will complete its operation within a finite number of steps in the system. The nonblocking algorithm, in contrast to the traditional lock-based algorithm, enjoys higher concurrency and fault-tolerance. In this thesis, we propose a nonblocking concurrent binary search tree algorithm. In order to maintain the data integrity in the course of concurrent insert and delete, we use the auxiliary node in the tree structure. The algorithm maintains binary search tree property without locking. Finally, we prove the correctness of our algorithms.