Browsing by Author "Huang, Ting-Lu"

Now showing 1 - 2 of 2

A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model
(2006-11-01)
Chen, Sheng-Hsiung
;
Huang, Ting-Lu
;
資訊工程學系
;
Department of Computer Science
In distributed shared memory multiprocessors, remote memory references generate processor-to-memory traffic, which may result in a bottleneck. It is therefore important to design algorithms that minimize the number of remote memory references. We establish a lower bound of three on remote reference time complexity for mutual exclusion algorithms in a 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, our lower bound holds for all mutual exclusion algorithms that use such primitives. Furthermore, this lower bound is shown to be tight by presenting an algorithm with the matching upper bound. (C) 2006 Elsevier Inc. All rights reserved.
Bounded-Bypass Mutual Exclusion with Minimum Number of Registers
(2009-12-01)
Chen, Sheng-Hsiung
;
Huang, Ting-Lu
;
資訊工程學系
;
Department of Computer Science
A mutual exclusion mechanism that is both fair and space efficient can be highly valuable for shared memory systems under time and memory constraints such as embedded real-time systems. 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 operations that have never been implemented in any system. This paper presents two fair algorithms that do not use such operations, each of which uses a single additional shared variable. The proposed algorithms employ commonly available operations, 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 FIFO condition, which is the most stringent fairness condition. Additionally, it is shown that achieving the bounded-bypass condition using the same set of operations requires two shared variables. Both of the algorithms are thus optimal with respect to the number of shared variables.