共享記憶體多處理機上可延伸的有序串列演算法

Abstract

共用的資料結構在共享記憶體多處理機上的系統軟體及應用程式中是必要 的。為了維持資料的一致性，必須要採用一些 lock 的方法。近來的研究 人員注意到記憶體及連結網路爭奪的問題，並且證明讓每一個處理機在可 局部存取的記憶體上持續等待而不經過連結網路可以有效減少此問題的發 生。在本論文中提出一系列符合此一要求的演算法。讀者作家同步問題允 許多個處理同時檢視共用物件的內容。現存的解法一般利用到計數器而可 能引起 hot spot 的產生，我們提出一個演算法來解決因為使用計數器而 引起的記憶體爭奪問題。利用解決讀者作家問題的做法，我們提出一個高 度平行的有序串列演算法，作用在串列上相衝突的動作可以部份相重疊， 並且總是維持串列的順序。 Mellor-Crummey 和 Scott 在 1991 年提出 了有區域等待(local spinning) 性質的 lock 同步演算法。但是在沒有 compare_and_swap 指令時，他們的演算法會導致可能餓死的問題。由我 們先前研究所得到的技術，我們提出一個不會導致餓死而且不須使用 compare_and_swap 的互斥演算法。 In a shared-memory multiprocessor system, maintaining a common data structure is essential in system softwares and application programs. Some locking mechanisms must be supported to maintain data consistency. Recently many researchers have addressed the problem of memory and interconnect contention and have shown that to have all the processors spin on locally- accessible variables without going through the entire processor- memory data path is effective in reducing the problem. We propose a series of local-spinning algorithms in the thesis. Reader-writer synchronization relaxes the constraints of mutual exclusion to permit more than one process to inspect a shared object concurrently. Typical use of counters in the existing solutions introduces a potential hot spot that may receive excessive memory accesses. We propose an algorithm that reduces the memory contention caused by centralized counter accesses. Based on the reader-writer lock, we propose a parallel ordered list that is highly concurrent. Some conflicting operations on the list structure can be partially overlapped and the order in the list is always kept consistent. Mellor-Crummey and Scott proposed in 1991 an algorithm for lock synchronization that enjoys local spinning property. However, for machine without compare_and_swap instructions their algorithm suffers the possibility of starvation. By using some techniques found in our previous work, we give a new list-based mutual exclusion lock algorithm that uses only fetch_and_store atomic instruction and is starvation free.