共享記憶體多處理機系統之高效能互斥演算法

Abstract

在一個緊密耦合的系統中，共享記憶體提供了一個媒介，作為系統中的處 理元互相溝通的工具。這些處理元使用共享變數來完成資料共享和資訊傳 送的目的。為保持資料一致性，在任何時間最多只能有一個處理元存取其 臨界區間，也就是共享變數，因此互斥演算法應用在共享記憶體多處理機 系統中。雖然軟體根基的演算法可實際靈活的應用，但也可能導致大量的 網路交通。一個單元運算如：test_and_set，可容易的處理許多同步問 題; 但由於產生熱點問題，將會削弱了一個有大量處理機系統的效能。針 對分散的共享記憶體且不具備有快取記憶體的多處理機系統，我們提出了 兩個高效能的互斥演算法。每一個欲進入臨界區間的處理元反覆的讀取一 個本地旗標，一個剛離開臨界區間的處理元藉由一個非本地寫入的動作將 鎖傳遞至另一個等待的處理元而中止其反覆讀取的動作。這兩個演算法在 大型的共享記憶體多處理機系統中能降低記憶體和網路的競爭，而且驗証 是互斥的，不會產生死鎖，且每個等待的處理元必將會進入臨界區間。 Shared-memory provides convenient ways for processes to communicate with each other in a tightly coupled multi- processor system. Shared variables can be used for data sharing and information transfer among processes. To guarantee that only one process can execute the critical section at any instant, mutual exclusion algorithms are usually applied on shared-memory multiprocessor systems. Software-based mutual exclusion algorithms are flexible to be implemented, but they may also introduce heavy network traffic. Although an atomic Read-Modify-Write operation, i.e., test_and_set, can easily solve many synchronization problems, it may seriously impair the performance of a system because of the so-called hot-spot problem. Two efficient algorithms were proposed for those distributed shared-memory multiprocessor systems without coherent caches. One is the list-based solution and the other is the array-based solution. Each contending process spins locally on a private flag and one of them will be terminated through a remote write by the process which just exited the critical section. Both these two algorithms can reduce memory and network contentions in a large-scale shared-memory multiprocessor system.