臺灣博碩士論文加值系統

二元搜索樹( 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.

摘 要i
Abstractii
誌 謝iii
Contentsiv
List of Figuresvi
Chapter 1 Introduction1
1.1.Binary Search Tree1
1.2.Synchronization and Nonblocking Algorithm3
1.2.1.Nonblocking Algorithm4
1.3.Synopsis5
Chapter 2 Related Work6
2.1Binary Search Tree Using Mutual Exclusion6
2.2Herlihy’s Universal Method7
2.3Tsay’s tree algorithm8
2.4Other Data Objects9
2.4.1Nonblocking Queue9
2.4.2Another Data Object9
Chapter 3 System Requirement and Data Structure11
3.1.Computational Model11
3.2.Atomic Instruction12
3.3.Data Structure13
3.4.The Problem of Concurrent Deletion15
Chapter 4 Binary Search Tree Algorithm17
4.1.Synchronization Consideration17
4.2.The Insert Operation18
4.3.The Delete Operation22
Chapter 5 The Correctness Proof29
5.1.Safety Property29
5.2.Liveness Property35
Chapter 6 Conclusion36
References38

References
[1] Thomas H. Cormen, “ Introduction to Algorithms. ” , pp. 244, 1996.
[2] P. Jayanti, “ Fault-tolerant Wait-free Shared Objects. ”, Proceedings of 33rd Annual Symposium on Foundations of Computer Science, pp. 157~166, 1992.
[3] A. LaMarca, “A Performance Evaluation of Lock-Free Synchronization Protocols. ”, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pp. 130~140, 1994.
[4] L. Lamport, “Concurrent reading and writing.” Communications of the ACM, pp. 806-811, 1977.
[5] M. Herlihy, “ Wait-Free Synchronization, ” ACM Transactions on Programming Languages and Systems, vol. 11, no.2, pp. 124-149, January 1991.
[6] M. Herlihy, “A methodology for implementing highly concurrent data structures.”, Proceedings of the Second ACM Symposium on Principles and Practice of Parallel Programming, pp. 197-206, 1990
[7] G. Barnes, “A method for implementing lock-free shared data structures. ”, Proceedings of the Fifth Symposium on Parallel Algorithms and Architectures, pp. 261-270, 1993.
[8] M. Herlihy, “A methodology for implementing highly concurrent data objects.”, ACM Transactions on Programming Languages and Systems, pp. 745-770,1993.
[9] Lee, H. -C, and J. -J Tsay, “Lock-Free Concurrent Tree Structures for Multiprocessor Systems,” 1994 International Conference on Parallel and Distributed Systems, pp. 544-549.
[10] M. Herlihy and J. Wing, “Linearizability: A correctness condition for concurrent objects.”, ACM Transactions on Programming Languages and Systems, pp.463-492, 1990.
[11] H. Massalin, “Synthesis: An Efficient Implementation of Fundamental Operating System Services.” PhD thesis, Columbia University, 1992.
[12] S. Prakash, Y. Lee, and T. Johnson, “A nonblocking algorithm for shared queues using Comparea&Swap.”, In Proceedings of the 1991 International Conference on Parallel Processing, pp. 68-75, 1991.
[13] J. M. Stone, “A non-blocking Compare&Swap algorithm for a shared circular queue. “, Parallel and Distributed Computing in Engineering Systems, p.p. 147-152, 1992.
[14] R. J. Anderson and H. Woll, “Wait-free parallel algorithms for the union problem.“, In Proceedings of the Twenty-third ACM Symposium on Theory of Computing, pp. 370-380, 1991.
[15] J. D. Valois, “Lock-Free Linked List Using Compare-and-Swap,” Proceedings of the 14th Annual Principles of Distributed Computing, pp.214-222, 1995.
[16] M. Herlihy and J. Moss, “Lock-free garbage collection for multiprocessors.”, Proceedings of the Third Symposium on Parallel Algorithms and Architectures, pp. 229-236, 1991.
[17] H. Kung, “Concurrent Manipulation of Binary Search Trees.“, ACM Transaction on Database Systems, pp. 354-382, 1980.
[18] D. Shasha, “Concurrent Search Structure Algorithm.“, ACM Transaction on Database Systems, pp. 53-90, 1988.
[19] Cheng-Te Hsiao, “A Scalable Parallel Ordered List for Shared-Memory Multiprocessors.”, Athesis Submitted to Institute of Computer Science and Information Engineering College of Engineering,pp. 2, 1994.
[20] Mukesh Singhal, “Advenced Concepts In Operating Systems”, Electronic Technical Publishing Services, 1994.