(3.238.186.43) 您好!臺灣時間:2021/03/02 10:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃俊榮
研究生(外文):Jung-Rong Huang
論文名稱:共享記憶體多處理機上非阻塞性的並行二元搜索樹演算法
論文名稱(外文):Nonblocking Concurrent Binary Search Tree for Shared-Memory Multiprocessor
指導教授:黃俊榮黃俊榮引用關係
指導教授(外文):Ting-Lu Huang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:39
中文關鍵詞:非阻礙性二元搜索樹
外文關鍵詞:nonblockingbinary search tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:117
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
二元搜索樹( 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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔