19 Nov 2008

Generic Atomic Object (GAO) - A Non-Blocking FIFO Queue

Problem

Implement a FIFO Queue used by concurrent writers and readers, which is lock-free algorithm and with non-blocking interface.

GAO Based Algorithm

Here we use a GAO based algorithm to solve the problem.

Data Structures

LINK_NODE

A link node has these data fields:

  {
    DATA                 data;
    SHPOINTER<LINK_NODE> next_node;
  }

FIFO_STATE

FIFO_STATE is a type of GAO Object that atomically maintains a data structure with these data fields:

  {
    SHPOINTER<LINK_NODE> header;
    SHPOINTER<LINK_NODE> tail;
    LINK_NODE            new_node;
  }

Pseudo Code

/* Init state */
FIFO_STATE current_state =
{
  .header = NULL;
  .tail   = NULL;
}

/* Lambda object for GAO::ReserveAndLoad */
FIFO_STATE FIFO_STATE_Load(FIFO_STATE data)
{
}

DATA FIFO_State_Store(FIFO_STATE data)
{
}

FIFO_Enqueue(Data d)
{
  FIFO_STATE tmp_state;
  TOKEN      r;

  r = current_state.ReserveAndLoad(FIFO_STATE_Load, &tmp_state);
}

See Also

"Implementing lock-free queues" by John D. Valois

Creative Commons License

A First-Principles-Driven Life by Miao, ZhiCheng is licensed under a Creative Commons Attribution 3.0 License.