互斥問題在空間與遠端存取次數的最佳解

Abstract

互斥問題為非同步共享記憶體系統中的基本問題，用來管理系統中的資源。本論文針對此問題，分別就空間使用與遠端存取次數上提出最佳解。

針對像嵌入式即時系統這樣具有時間與資源限制的環境，互斥演算法應該符合公平性並且降低記憶體的使用。在文獻中，已有數個演算法僅用一個共享變數並且具有公平性。然而，這些演算法使用一些從未在任何系統中出現的假設性指令來設計。在不使用這樣的指令之下，我們首先提出兩個具公平性的演算法，並且僅需多用一個共享變數。所採用的指令為常見於一般系統的 fetch&store 與 read/write。第一個演算法符合 bounded bypass 條件。第二個則是改進第一個演算法，使其達到 FCFS 的公平性。改進公平性所需的代價為需更大的共享變數，在第一個演算法中共享變數大小為 2log_2(n+1) 位元，第二個演算法則需 1 + 3log_2 (n+1) 位元，其中 n 代表所有 process 的個數。此外，我們進一步去證明在使用相同指令的條件下，至少需兩個共享變數才能達到 bounded bypass 的公平性。因此，就共享變數的使用個數上，所提出的演算法為最佳解。

而針對分散式共享記憶體系統，近期的研究主要為設計降低遠端存取次數的互斥演算法。頻繁地遠端存取會產生大量記憶體與處理器之間的流量，進而降低系統的效能。在此研究方向上，我們提出一個遠端存取次數的lower bound。所假設的系統為採用通用 read-modify-write 指令的分散式共享記憶體系統。此通用 read-modify-write 指令為一般常見於系統一次存取一個共享變數的不可分割指令之一般化模型，因此所提出的 lower bound 適用於所有採用這類指令的系統。再者，根據黃廷祿博士於 ICDCS’99 提出的演算法，此 lower bound 為最佳。

The mutual exclusion problem is fundamental to resource allocation in asynchronous shared memory systems. In this dissertation we present mutual exclusion algorithms with fairness and the minimum number of shared variables, and then show a tight bound on remote reference time complexity.

For shared memory systems under time and memory constraints such as embedded real-time systems, a mutual exclusion mechanism that is both fair and space-efficient can be highly valuable. Several algorithms that utilize only one shared variable and guarantee a certain level of fairness have been proposed. However, these use hypothetical read-modify-write primitives that have never been implemented in any system. We present two fair algorithms that do not use such primitives, but each algorithm has one additional shared variable. The proposed algorithms employ commonly available primitives, fetch&store and read/write, on two shared variables. The first algorithm satisfies the bounded bypass condition. The second is an improvement on the first that satisfies the FCFS condition, which is the most stringent fairness condition. The improvement is at the cost of increasing the size of a shared variable from 2 log_2 (n+1) bits to 1 + 3 log_2 (n+1) bits, where n is the number of processes. In addition, it is shown that achieving the bounded bypass condition using the same set of primitives requires two shared variables. Both of the algorithms are thus space-optimal in terms of the number of shared variables.

For distributed shared memory (DSM) systems, recent work on this problem has focused on the design of mutual exclusion algorithms that minimize the number of remote memory references, which generate processor-to-memory traffic and therefore may result in a bottleneck. We establish a lower bound of three on remote reference time complexity for mutual exclusion algorithms in a DSM model where processes communicate by means of a general read-modify-write primitive that accesses at most one shared variable in one instruction. Since the general read-modify-write primitive is a generalization of a variety of atomic primitives that have been implemented in multiprocessor systems, the lower bound holds for all mutual exclusion algorithms that use such primitives. Additionally, the lower bound is tight because it matches the upper bound of Huang's algorithm proposed in ICDCS'99.