amino::LockFreeQueue< T > Class Template Reference

This queue implementation is based on the algorithm defined in the follwoing paper: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms by Michael, M. M. and Scott, M. L. 1996. PODC96 ABA prevention: Maged M. Michael's SMR way The following paper pointed out that Maged Michael's queue doesn't scale well. Moir, M., Nussbaum, D., Shalev, O., and Shavit, N. 2005. Using elimination to implement scalable and lock-free FIFO queues. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Las Vegas, Nevada, USA, July 18 - 20, 2005). SPAA '05. ACM Press, New York, NY, 253-262. More...

#include <queue.h>

List of all members.

Public Member Functions
	LockFreeQueue ()
	constructor
	~LockFreeQueue ()
	destructor
void	enqueue (T d)
	insert an element into the tail of queue. Thread-safe
bool	dequeue (T &ret)
	remove and return an element from the head of queue. Thread-safe.
bool	empty ()
	Check to see if queue is empty. Thread-safe.
int	size ()
	Get the size of the queue at this point. compute on the fly. Not thread-safe.
bool	peekFront (T &top)
	Get the first element of the queue. If the queue is empty return false, else return true and assign the first to the parameter. Thread-safe.
Classes
class	Node

---

Detailed Description

template<typename T>
class amino::LockFreeQueue< T >

This queue implementation is based on the algorithm defined in the follwoing paper: Simple, fast, and practical non-blocking and blocking concurrent queue algorithms by Michael, M. M. and Scott, M. L. 1996. PODC96 ABA prevention: Maged M. Michael's SMR way The following paper pointed out that Maged Michael's queue doesn't scale well. Moir, M., Nussbaum, D., Shalev, O., and Shavit, N. 2005. Using elimination to implement scalable and lock-free FIFO queues. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (Las Vegas, Nevada, USA, July 18 - 20, 2005). SPAA '05. ACM Press, New York, NY, 253-262.

However, from its performance test, SPAA05's scales much better than PODC96's when number of CPU cores are large, but performs slower when few CPU cores available. We decide to implement PODC96's for its simplicity and applicability

Performance tuning tips: 1 backoff mechanism. 2 Eliminate redundant memory barriers, implied by the atomics. Use atomic_xx_xx instead of neat C++ APIs, which are easy to use, but always imply full barriers currently. TODO: 1 code it in STL code style

Author:

Mo Jiong Qiu

Xiao Jun Dai

Template Parameters:

T

The type of the element which is stored in the queue

---

Constructor & Destructor Documentation

template<typename T>

amino::LockFreeQueue< T >::LockFreeQueue

(

)

[inline]

constructor

template<typename T>

amino::LockFreeQueue< T >::~LockFreeQueue

(

)

[inline]

destructor

---

Member Function Documentation

template<typename T>

void amino::LockFreeQueue< T >::enqueue

(

T

d

)

[inline]

insert an element into the tail of queue. Thread-safe

Parameters:

d

The element to be added

template<typename T>

bool amino::LockFreeQueue< T >::dequeue

(

T &

ret

)

[inline]

remove and return an element from the head of queue. Thread-safe.

Returns:

return the head element of queue; return NULL(or 0) if queue is empty

template<typename T>

bool amino::LockFreeQueue< T >::empty

(

)

[inline]

Check to see if queue is empty. Thread-safe.

Returns:

true if empty, or false.

template<typename T>

int amino::LockFreeQueue< T >::size

(

)

[inline]

Get the size of the queue at this point. compute on the fly. Not thread-safe.

Returns:

the number of elements in the queue

template<typename T>

bool amino::LockFreeQueue< T >::peekFront

(

T &

top

)

[inline]

Get the first element of the queue. If the queue is empty return false, else return true and assign the first to the parameter. Thread-safe.

Parameters:

ret

The first element of the queue. It is valid if return true.

Returns:

If the queue is empty return false, else return true.

---

The documentation for this class was generated from the following file:

• include/amino/queue.h