一個以陣列為基礎並使用比較與交換指令之非阻塞性共享佇列演算法

Abstract

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