Test-and-Set in Optimal Space
Résumé
The test-and-set object is a fundamental synchronization primitive for shared memory systems. This paper addresses the number of registers (supporting atomic reads and writes) required to implement a one-shot test-and-set object in the standard asynchronous shared memory model with n processes. The best lower bound is log n − 1 for obstruction-free and deadlock-free implementations, and recently a deterministic obstruction-free implementation using O(√ n) registers was presented. This paper closes the gap between these existing upper and lower bounds by presenting a deterministic obstruction-free implementation of a one-shot test-and-set object from Θ(log n) registers of size Θ(log n) bits. Combining our obstruction-free algorithm with techniques from previous research, we also obtain a randomized wait-free test-and-set algorithm from Θ(log n) registers, with expected step-complexity Θ(log* n) against the oblivious adversary. The core tool in our algorithm is the implementation of a deterministic obstruction-free sifter object, using only 6 registers. If k processes access a sifter, then when they have terminated, at least one and at most (2k + 1)/3 processes return "win" and all others return "lose" .
Origine : Fichiers produits par l'(les) auteur(s)
Loading...