佇列通常被應用於計算機程式設計、作業系統及發展演算法。並行佇列容許數個作業程序同時在其上作業並且對分散式系統特別有用。
比起那些閒置的作業程序可能會阻礙其他正在運作共享資料的作業程序之阻塞性演算法，非阻塞性演算法確保正常的作業程序總是能有所進展。
為了避免垃圾回收的問題,我們發展出一套以陣列為基礎的非阻塞性共享佇列演算法。我們使用比較與交換基本指令來發展演算法。不像很多之前所提的演算法,我們的取出(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.