Advertisement
Published in:
2005 | OriginalPaper | Chapter
Efficiently Implementing LL/SC Objects Shared by an Unknown Number of Processes
Authors : Prasad Jayanti, Srdjan Petrovic
Published in: Distributed Computing – IWDC 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Over the past decade, a pair of instructions called load-linked (LL) and store-conditional (SC) have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS (e.g., UltraSPARC, Itanium) or restricted versions of LL/SC (e.g., POWER4, MIPS, Alpha). To bridge this gap, a flurry of algorithms that implement LL/SC from CAS have appeared in the literature. Some of these algorithms assume that
N
, the maximum number of participating processes, is fixed and known in advance. Others make no such assumption, but are either non-blocking (not wait-free), implement small LL/SC objects, or require that a process performs
O
(
N
) work to join the algorithm. Specifically, no constant-time, word-sized, wait-free LL/SC algorithm that does not require the knowledge of
N
exists. In this paper, we present such an algorithm.