Non-Blocking Algorithm - FIFO Queue

hellwolf · 发表于 2008-12-5 06:53:32

原文： http://blog.chinaunix.net/u/8057/showart_1680274.html

Author: ZC Miao <>

Revision:

- 2008-12-04

First revision.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Problem
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Provide a non-blocking algorithm that provides a FIFO Queue with the following
interface:

- void InitFIFO(void)

FIFO queue initialization.

- bool Enqueue(DATA data)

Push a data into the FIFO queue. Return TRUE if success, return FALSE only if
the FIFO is full.

- bool Dequeue(DATA* pdata)

Pull a data from the FIFO queue. Return TRUE if success, return FALSE only if
the FIFO is empty.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Link-List Structure
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The algorithm introduced here is based on a link-list structure[1]. It's a
single link-list with head and tail pointers. It looks like:

+-------+ +-------+ +-------+ +-------+
| | | | | | | |
| -+---->| -+---->| -+---->| -+---->NULL
| | | | | | | |
+---^---+ +-------+ +-------+ +---^---+
| |
| |
| |
HEAD TAIL

复制代码

New data is pushed to the tail, and old data is pulled from head.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Dequeue Data, first thought
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

To dequeue a data, first read the HEAD value, and use CAS to swap the HEAD
pointer to it's next pointer. And the old HEAD value is the data that
dequeued. To avoid ABA problem[3], we should use SLOTID_CAS which described in
the "Fix-size Slots Management"[2].

+-------+ +-------+ +-------+ +-------+
| | | | | | | |
| -+---->| -+---->| -+---->| -+----> NULL
| | | | | | | |
+-------+ +---^---+ +-------+ +---^---+
| |
| |
| |
HEAD TAIL

复制代码

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Enqueue Data
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Enqueue operation is more complicated than dequeue operation, because it has to
change two state: the next pointer of the tail slot, and the tail pointer. If we
have MCAS(Multi CAS) or at least Double CAS[4], then the problem is easy to
solve. But since DCAS is not widely available in computer system, so a so-called
cooperative method is introduced firstly by Valois[5].

In cooperative method, enqueue operation first allocates a new slot, and sets
next pointer of tail slot to the new slot. Then set tail pointer to new
slot. All theses set operation use SLOTID_CAS, so the second step can fail, if
someone others enters in, and set the tail pointer. Which leaves the FIFO in a
intermediate state:

+-------+ +-------+ +-------+ +-------+
| | | | | | | |
| -+---->| -+---->| -+---->| -+---->NULL
| | | | | | | |
+---^---+ +-------+ +---^---+ +-------+
| |
| |
| |
HEAD TAIL

复制代码

To complete the intermediate state:

1. The next enqueue operation should try to move the TAIL forward, until the
TAIL at the end, the enqueue operation should not change the TAIL slot next
pointer.

2. The next dequeue operation should also try to move the TAIL forward when the
head meets the tail pointer.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Algorithm
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

This algorithm uses CAS version of "Fix-size Slots Management"[2].

typedef struct
{
DATA data;
SLOTID next;
} Node;
SLOTID head;
SLOTID tail;
void InitFIFO(void)
{
Node *sentinel;
/* This algorithm relies on the fix-size slots management */
InitSlots();
/* Sentinel slots */
head = tail = GetSlot();
sentinel = DecodeSlotID(head);
sentinel->next = NULL_ID;
}
/*
Origin Algorithm:
E01: node = new node()
E02: node->value = value
E03: node->next.ptr = NULL
E04: loop
E05: tail = Q->Tail
E06: next = tail.ptr->next
E07: if tail == Q->Tail
E08: if next.ptr == NULL
E09: if CAS(&tail.ptr->next, next, <node, next.count+1>)
E10: break
E11: endif
E12: else
E13: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
E14: endif
E15: endif
E16: endloop
E17: CAS(&Q->Tail, tail, <node, tail.count+1>)
*/
bool Enqueue(DATA data)
{
SLOTID newid;
Node *newnode;
SLOTID oldtail;
Node *oldtailnode;
SLOTID nextid;
Node *nextnode;
/* E01 */
newid = GetSlot();
newnode = DecodeSlotID(newid);
if (newnode == NULL) return FALSE;
/* E02 */
newnode->data = data;
/* E03 */
newnode->next = NULL_ID;
/* E04 */
do {
/* E05 */
oldtail = tail;
oldtailnode = DecodeSlotID(oldtail);
/* E06 */
nextid = oldtailnode->next;
nextnode = DecodeSlotID(nextid);
/* E07 */
if (oldtail == tail)
{
/* E08 */
if (nextnode == NULL)
{
/* E09 */
if (SLOTID_CAS(&oldtailnode->next, next, newid))
{
/* E10 */
break;
/* E11 */
}
}
/* E12 */
else
{
/* E13 */
SLOTID_CAS(&tail, oldtail, next);
/* E14 */
}
/* E15 */
}
/* E16 */
} while(1);
/* E17 */
SLOTID_CAS(&tail, oldtail, newid);
return TRUE;
}
/*
Origin Algorithm:
D01: loop
D02: head = Q->Head
D03: tail = Q->Tail
D04: next = head->next
D05: if head == Q->Head
D06: if head.ptr == tail.ptr
D07: if next.ptr == NULL
D08: return FALSE
D09: endif
D10: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11: else
D12: *pvalue = next.ptr->value
D13: if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14: break
D15: endif
D16: endif
D17: endif
D18: endloop
D19: free(head.ptr)
D20: return TRUE
*/
bool Dequeue(DATA *pdata)
{
SLOTID oldhead
Node *oldheadnode;
SLOTID oldtail;
Node *oldtailnode;
SLOTID next;
Node *nextnode;
/* D01 */
do {
/* D02 */
oldhead = head;
oldheadnode = DecodeSlotID(oldhead);
/* D03 */
oldtail = tail;
oldtailnode = DecodeSlotID(oldtail);
/* D04 */
next = oldhead->next;
nextnode = DecodeSlotID(next);
/* D05 */
if (oldhead == head)
{
/* D06 */
if (headnode == tailnode)
{
/* D07 */
if (nextnode == NULL)
{
/* D08 */
return FALSE;
/* D09 */
}
/* D10 */
SLOTID_CAS(&tail, oldtail, next);
}
/* D11 */
else
{
/* D12 */
*pdata = nextnode->data;
/* D13 */
if (SLOTID_CAS(&head, oldhead, next)
{
/* D14 */
break;
/* D15 */
}
/* *D16 /
}
/* D17 */
}
/* D18 */
}
/* D19 */
PutSlot(oldhead);
/* D20 */
return TRUE;
}

复制代码

In enqueue, E13 is the cooperative operation.

In dequeue, D10 is the cooperative operation.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  Array Based Algorithm
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Valois also introduced a array based Non-Blocking FIFO algorithm[6], but it's
not feasible on real machine because it requires CAS on unaligned memory region.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  Conclusion
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

This article introduces a link-listed based Non-Blocking algorithm for FIFO
queue. It's based on the "Fix-size Slots Management"[2], and feasible on the
platforms that support CAS.

==================== Footnote ====================
[1]  Maged M. Michael Michael L. Scott, Simple, Fast, and Practical Non-Blocking
  and Blocking Concurrent Queue Algorithms,, Department of Computer Science
  University of Rochester, 1995.
[2]  ZC Miao, Non-Blocking Algorithm - Fix-size Slots Management, revision
  2008-12-04
[3]  ABA problem from Wikipedia
  http://en.wikipedia.org/wiki/ABA_problem
[4]  Double Compare And Swap from Wikipedia
  http://en.wikipedia.org/wiki/Double_Compare_And_Swap
[5]  J.D. Valois, Lock-Free Data Structures PhD Thesis, Rensselaer Polytechnic
  Institute, Department of Computer Science, 1995.
[6]  J.D. Valois, Implementing Lock-Free Queues

		自动登录	找回密码
密码			注册