Subject: Re: [linux-audio-dev] Lock Free FIFOs
From: Dominique Fober (fober_AT_grame.fr)
Date: Wed Dec 06 2000 - 18:23:13 EET
>Does anyone have an example of a Lock Free FIFO. Puesdo code /quite/
>acceptable.
>
>TIA,
>Paul
>
>--
>e: paul_AT_sladen.org t: 0115 922 7162
Hi,
We have recently designed a new optimized lock-free fifo algorithm, intended to operate within MidiShare (http://www.grame.fr/MidiShare), a real-time multi-tasks MIDI operating system.
Our algorithm is based on Michael-Scott implementation but optimizes memory allocation and provides better performances.
The FIFO queue is implemented as a linked list of cells with head and tail pointers. Each pointer have an associated counter, ocount and icount, wich maintains a unique modification count of operations on head and tail. A cell can be anything provided it starts with a pointer available to link together the cells of the queue:
structure cell { next: pointer to next cell, value: data type }
strcuture fifo {
head: pointer to head cell,
ocount: unsigned integer
tail: pointer to tail cell,
icount: unsigned integer
}
The algorithm relies on an atomic primitive such as compare-and-swap which takes as argument the address of a memory location, an expected value and a new value. If the location holds the expected value, it is assigned the new value atomically. A boolean value indicates whether the replacement occurred.
A variation of the compare-and-swap primitive can also operate in memory on double-words. To differenciate between the two primitives in the following pseudo-code I'll refer to them with:
CAS (mem, old, new) for single word operations
where mem is a pointer to a memory location
old and new are the expected and the new value
and
CAS2 (mem, old1, old2, new1, new2) for double word operations
where mem is a pointer to a memory location
old1, old2 and new1, new2 are the expected and the new values
The queue consistency is maintained by cooperative concurrency: when a process trying to enqueue a cell detects a pending enqueue operation, it initialy tries to complete the pending operation before enqueing the cell. The dequeue operation also ensures that the tail pointer does not point to the dequeued cell and if necessary, tries to complete any pending enqueue operation. Here is the commented pseudo-code for the fifo queue operations:
initialize (ff: pointer to fifo, dummy: pointer to dummy cell)
dummy->next = NULL # makes the cell the only cell in the list
ff->head = ff->tail = dummy # both head and tail point to the dummy cell
enqueue (ff: pointer to fifo, cl: pointer to cell)
E1: cl->next = NULL # set the cell next pointer to NULL
E2: loop # try until enqueue is done
E3: icount = ff->icount # read the tail modification count
E4: tail = ff->tail # read the tail cell
E5: if CAS (&tail->next, NULL, cl) # try to link the cell to the tail cell
E6: break; # enqueue is done, exit the loop
E7: endif
# tail was not pointing to the last cell, try to set tail to the next cell
E8: CAS2 (&ff->tail, tail, icount, tail->next, icount+1)
E9: endloop
# enqueue done, try to set tail to the enqueued cell
E10: CAS2 (&ff->tail, tail, icount, cl, icount+1)
dequeue (ff: pointer to fifo): pointer to cell
D1: loop # try until dequeue is done
D2: ocount = ff->ocount # read the head modification count
D3: icount = ff->icount # read the tail modification count
D4: head = ff->head # read the head cell
D5: next = head->next # read the next cell
D6: if ocount == ff->oc # ensures that next is a valid pointer
# to avoid failure when reading next value
D7: if head == ff->head # is queue empty or tail falling behind ?
D8: if next == NULL # is queue empty ?
D9: return NULL # queue is empty: return NULL
D10: endif
# tail is pointing to head in a non empty queue, try to set tail to the next cell
D11: CAS2 (&ff->tail, head, icount, next, icount+1)
D12: else
D13: value = next->value # read the next cell value
# try to set head to the next cell
D14: if CAS2 (&ff->head, head, ocount, next, ocount+1)
D15: break # dequeue done, exit the loop
D16: endif
D17: endif
D18: endloop
D19: head->value = value # set the head value to previously read value
D20: return head # dequeue succeed, return head cell
I can also send the source code for a linux Intel implementation.
At last, here are some references concerning lock-free fifo queues:
[Herlihy, Wing 1987] M. P. Herlihy, J. M. Wing. "Axioms for concurrent objects." In Proceedings of the 14th ACM Symposium on Principles of Programmmg Languages,Jan. 1987, pp. 13-26.
[Herlihy, Wing 1990] M. P. Herlihy, J. M. Wing. "Linearizability: A Correctness Condition for Concurrent Objects." ACM Transactions on Programming Languages and Systems, Vol. 12, No. 3, July 1990, pp. 463-492.
[Herlihy 1993] M. P. Herlihy. "A methodology for implementing highly concurrent data objects." ACM Trans. Program. Lang. Syst. 1993, Vol. 15, No.5, pp. 745-770.
[Michael, Scott 1996] M. M. Michael and M. L. Scott. "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms." 15th ACM Symp. on Principles of Distributed Computing (PODC), May 1996. pp. 267 - 275
[Michael, Scott 1998] M. M. Michael and M. L. Scott. "Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors." Journal of Parallel and Distributed Computing, 1998, pp. 1-26.
[Valois 1994] John D. Valois. "Implementing Lock-Free Queues." Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, Las Vegas, October 1994, pp. 64-69
Dominique Fober
----------------------------------------------
Dominique Fober <fober_AT_grame.fr>
----------------------------------------------
GRAME - Centre National de Creation Musicale -
9 rue du Garet 69001 Lyon France
tel:+33 04 720 737 00 fax:+33 04 720 737 01
This archive was generated by hypermail 2b28 : Wed Dec 06 2000 - 19:09:46 EET