Tight Bounds on Space and Remote Reference Time Complexity of Mutual Exclusion
| Autor: | Sheng-Hsiung Chen, 陳勝雄 |
|---|---|
| Rok vydání: | 2008 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 96 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|