Browse Prior Art Database

An Efficient Locking Method Disclosure Number: IPCOM000010792D
Original Publication Date: 2003-Jan-22
Included in the Prior Art Database: 2003-Jan-22
Document File: 2 page(s) / 13K

Publishing Venue


This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 2

An Efficient Locking Method

   Disclosed is a method for constructing an efficient spin-suspend lock. The spin-suspend lock constructed in the way described below requires only one atomic operation in the uncontended case, while it achieves high performance even in the contended case.

The spin-suspend lock is constructed using the following data structure.

struct tasuki_t {

thread_t* locker; /* locker */

thread_t* wqueue; /* queue of waiting threads */ }

When no thread holds the lock, the value of the locker field is NULL. When a thread holds the lock, the field contains the thread's identifier, which is the pointer to the thread's data structure in this embodiment. When there is no waiting thread, the value of the wqueue field is NULL. When there is one or more waiting threads, the field contains the pointer to the head of the list of the waiting threads.

The spin-suspend lock uses the following two primitives for low-level synchronization.

void suspend();

   This function suspends the calling thread. When some other thread has already issued a request to resume the thread, it accepts the request and returns immediately. void resume(thread_t *thread); attempts to resume the thread specified as the first argument. When the thread is in the suspend state, it puts the thread in the ready-to-run state Otherwise, it results in a request to resume the thread being issued.

The steps of acquiring and releasing the spin-suspend lock is now described. As shown below, the lock is constructed using the tasuki protocol [1].

When a thread attempts to acquire a spin-suspend lock, it first executes the compare-and-swap operation. The operation succeeds in the uncontended case, while it fails in the contended case and executes the subsequent path, where the thread put itself into the queue and executes again the compare-and-swap operation with the same arguments. When the second attempt fails, it suspends itself.

void tasuki_acquire(tasuki...