(34.236.244.39) 您好!臺灣時間:2021/03/09 18:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳東峻
研究生(外文):Dong-Jung Wu
論文名稱:一個以陣列為基礎並使用比較與交換指令之非阻塞性共享佇列演算法
論文名稱(外文):A nonblocking algorithm for array-based shared queue using compare&swap
指導教授:黃廷祿
指導教授(外文):Ting-Lu Huang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:中文
論文頁數:53
中文關鍵詞:非阻塞性比較與交換不可分割指令不可分割物件ABA問題
外文關鍵詞:nonblockingcompare&swapatomic instructionatomic objectABA problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:97
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
佇列通常被應用於計算機程式設計、作業系統及發展演算法。並行佇列容許數個作業程序同時在其上作業並且對分散式系統特別有用。
比起那些閒置的作業程序可能會阻礙其他正在運作共享資料的作業程序之阻塞性演算法,非阻塞性演算法確保正常的作業程序總是能有所進展。
為了避免垃圾回收的問題,我們發展出一套以陣列為基礎的非阻塞性共享佇列演算法。我們使用比較與交換基本指令來發展演算法。不像很多之前所提的演算法,我們的取出(Deq)運算的執行時間並不隨所累積的運算數目而增加。此外,我們證明了演算法的正確性。

Queues are often used in computer programming, operating system, and algorithm development. A concurrent queue allows several processes manipulating it simultaneously and is especially useful for distributed system.
Nonblocking algorithms, in contrast to blocking algorithm in which an idle process may block other processes¢ ongoing manipulation on shared data, guarantee that the nonfailed processes can always make progress.
In order to avoid garbage collection problem, we develop the algorithm for shared queue based on array. We use the compare&swap primitive to develop the algorithm. Unlike many proposed algorithms, the running time of our Deq operation is independent of the numbers of operations performed. In addition, we prove the correctness of our algorithm.

摘 要I
ABSTRACTII
誌 謝III
TABLE OF CONTENTSIV
LIST OF FIGURESIV
CHAPTER 1 INTRODUCTION1
CHAPTER 2 RELATED WORK4
2.1 HERLIHY AND WING:4
2.2 WING AND GONG5
2.3 MASSALIN AND PU5
2.4 VALOIS'S LOCK-FREE QUEUES5
CHAPTER 3 BACKGROUND7
3.1 DATA STRUCTURE7
3.2 ATOMIC INSTRUCTION8
3.3 FLOWCHARTS AS ALGORITHMS9
3.4 HAPPEN BEFORE (→) RELATION9
CHAPTER 4THE ALGORITHM11
4.1 QUEUE BASED ON INFINITE ARRAY13
4.1.1 THE ENQUEUE OPERATION13
4.1.2 THE DEQUEUE OPERATION15
4.2 QUEUE BASED ON BOUNDED ARRAY17
4.2.1 THE ENQ OPERATION17
4.2.2 THE DEQ OPERATION17
4.3 THE ABA PROBLEM20
4.3.1 DYNAMIC MEMORY ALLOCATION20
4.3.2 STATIC MEMORY ALLOCATION23
4.3.3 A LITTLE COMMENT ON THE ABA PROBLEM23
CHAPTER 5 THE CORRECTNESS PROOF26
5.1 ATOMIC OBJECT26
5.1.1 I/O AUTOMATON26
5.1.2 SHARED VARIABLE TYPE28
5.1.3 ATOMICITY PROPERTY28
5.1.4 THE PROBLEM29
5.1.5 THE ALGORITHM30
5.2 PRELIMINARY WORKS AND LEMMAS32
5.3 SAFETY PROPERTY40
5.4 LIVENESS PROPERTY43
CHAPTER 6 CONCLUSION45
REFERENCES46

[LAM 78] L. Lamport, Time, Clocks and Ordering of Events in Distributed Systems,Comm. ACM, vol. 21, no. 7, pp. 558-565, July 1978.
[H&M 90] M. P. Herlihy and J. M. Wing, Linearizability: A correctness condition for concurrent objects, ACM Trans. Program. Lang. Syst. 12, 3(July 1990), 463-492.
[W&G 90] J. Wing and C. Gong. A library of concurrent objects and their proofs of correctness. Technical Report CMU-CS-90-151, Carnegie Mellon University, 1990.
[HER 93] M. P. Herlihy, A methodology for implementing highly concurrent data structures, in Proceeding of 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 197-206, 1990.
[M&P 91] H. Massalin and C. Pu, A lock-free multiprocessor OS kernel, Technical report CUCS-005-91, Computer Science Department, Columbia University, 1991.
[SIT 92] R. L. Sites, Alpha Architecture Reference Manual. Digital Press, Burlington, Mass., 1992.
[HER 93] M. P. Herlihy, A methodology for implementing highly concurrent data objects, ACM Trans. Program. Lang. Syst. 15, 5 (November 1993), 745-770.
[PLJ 94] S. Prakash, Y. H. Lee, and T. Johnson, A nonblocking algorithm for shared queues using compare-and-swap, IEEE Trans. Comput. 43. 5(May 1994), 548-559.
[VAL 94] J. D. Valois, Lock-free linked lists using compare-and-swap, in "Proceedings of the Fourteenth ACM Symposium on Principles of Distributed Computing," Ottawa, Ontario, August 1995, pp. 214-222.
[H&P 96] David A. Patterson and John L. Hennessy, Computer architecture A Quantitative Approach, Morgan Kaufmann Publishers, 1996.
[LYN 96] Nancy A. Lynch, Distributed algorithms, Morgan Kaufmann Publishers, 1996.
[M&S 98] Maged M. Michael and Michael L. Scoot, Nonblocking algorithm and preemption-safe locking on multiprogrammed shared memory multiporcessors, Journal of Parallel and Distributed Computing 51, (1998) pp. 1-26.
[HTL 98] T. L. Huang, Fast mutual exclusion algorithms using read-modify-write and atomic read/write registers, in "(ICPADS' 98) Proceeding of the 1998 International Conference on Parallel and Distributed Systems," Dec. 1998, pp. 292-299.

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