DocumentCode :
2627443
Title :
How to share an object: A fast timing-based solution
Author :
Alur, Rajeev ; Taubenfeld, Gadi
Author_Institution :
AT&T Bell Lab., Murray Hill, NJ, USA
fYear :
1993
fDate :
1-4 Dec 1993
Firstpage :
470
Lastpage :
477
Abstract :
We consider the problem of transforming a given sequential implementation of a data structure into a wait-free concurrent implementation. Given the code for different operations of an object that is designed to work under the assumption that only a single process accesses it, we want to construct an implementation that works correctly in a concurrent environment where it may be accessed by many processes. We assume a shared memory model with atomic registers. It is well known that using atomic registers it is impossible to construct concurrent implementations of even very simple objects such as test-and-set bits. However, we show that the knowledge about relative speeds of processes can be used for such implementations. We assume that there is a known upper bound on the time taken by the slowest process to execute a statement involving an access to the shared memory. This timing assumption is very powerful and enables us to construct fast wait-free implementations of data structures such as queues, stacks and synchronization primitives such as test-and-set, compare-and-swap, fetch-and-add, etc. Our transformation works only when the given sequential implementation is bounded, that is, there is a known upper bound on the number of steps required to complete any of the operations it supports. In the absence of contention, it guarantees that there is only a small overhead in the cost of executing the concurrent operations over the sequential ones, namely, only a constant number of accesses to the shared memory
Keywords :
computational complexity; data structures; multiprocessing systems; object-oriented programming; parallel programming; shared memory systems; synchronisation; atomic registers; compare-and-swap; concurrent environment; data structure; fast timing-based solution; fetch-and-add; object sharing; queues; relative speeds; sequential implementation; shared memory model; single process; small overhead; stacks; synchronization primitives; test-and-set; test-and-set bits; timing assumption; upper bound; wait-free concurrent implementation; Costs; Data structures; Protection; Registers; Testing; Timing; Upper bound; Writing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
Type :
conf
DOI :
10.1109/SPDP.1993.395496
Filename :
395496
Link To Document :
بازگشت