Hey, My longer explanation is outdated, so I'll just say this: I'm working on a lockless queue implementation to use in cross-thread informing of events in a server; the code is below. This queue is designed to work only in the case of one reader, one writer--IE, one and only one thread calling pop(), and one and only one thread calling push(). I *think* I have the problems that were in it worked out, although for now please ignore: 1. The lack of a memory lock in the position specified in push(), and a way to handle creation/deletion of nodes other than the default operators--I'll implement these when I'm sure the logic of the algorithm is right. 2. The possibility of first and last being written to the same cache line and being unreadable at the same time. 3. The current lack of any sort of size() method and the fact that it only stores pointers right now (didn't want to get into error handling for calls to pop() on an empty queue and junk up the code until I got it working at all). 4. The lack of optimization, although of course tips are nice :). Thanks! -Akhilleus

template<typename T>
class Queue
{
public:
	Queue() : last(new QNode(0, true, SAFE, 0)), first(new QNode(0, false, SKIP_NEXT, last))
	{}
	void push(T *data)
	{
		/////////////////////////////////////////////////////////////////////////////////////////////////
		//shared variables read:
		//	(N/A)
		//shared variables written:
		//	prev->tail (if read during write, value read is guaranteed to be meaningful and equal to the
		//				correct or the previous value, as only one bit is actually changed on any write,
		//				because tail is only ever 0 or 1)
		//notes:
		//	1.  the pointer last is never read or written by pop()
		//	2.  the object *last is only accessed by pop() when reading its tail and/or data values
		//	3.  the original object *last is released to full access by pop() by the operation
		//		prev->tail = 0, after which it is never accessed by push() again
		/////////////////////////////////////////////////////////////////////////////////////////////////

		last->next = new QNode(data);
		QNode* prev = last;
		last = const_cast<QNode*>(last->next);
		//memory barrier here so that this line get run last
		prev->tail = 0;
	}
	//unnecessary in the current code, as pop() returns a pointer (NULL if the queue is empty)
	//bool pop_safe()
	//{
	//	return(first->status != SKIP_NEXT || first->next->tail != 1);
	//}
	T *pop()
	{
		/////////////////////////////////////////////////////////////////////////////////////////////////
		//shared variables read:
		//	last->tail (always in the form first->next->tail)
		//shared variables written:
		//	(N/A)
		//notes:
		//	1.  the pointer last is never read or written by pop()
		//	2.  the object *last is only accessed by pop() when reading its value status (atomic)
		//	3.  the original object *last is released to full access by pop() by the atomic operation
		//		prev->status = SAFE, after which it is never accessed by push() again
		/////////////////////////////////////////////////////////////////////////////////////////////////
		while(true)
		{
			if(first->next->tail)
			{
				switch(first->status)
				{
					case(SAFE) :
						//return first's data without popping
						first->status = ALREADY_READ;
						return(first->data);
					case(ALREADY_READ) :
						//return last's data without popping
						first->status = SKIP_NEXT;
						return(first->next->data);
					default: //SKIP_NEXT (first->status never equals TAIL)
						//return nothing, as all values have been popped and the queue is empty
						return(0);
				}
			}
			else //next node is not the tail
			{
				T* to_return;
				QNode* prev;
				switch(first->status)
				{
					case(SAFE) :
						//pop first from the queue
						to_return = first->data;
						prev = first;
						first = const_cast<QNode*>(first->next);
						delete prev;
						return(to_return);
					case(ALREADY_READ) :
						//move on to the next node
						prev = first;
						first = const_cast<QNode*>(first->next);
						delete prev;
						break;
					default: //SKIP_NEXT
						//set next node to ALREADY_READ and move on to it
						first->next->status = ALREADY_READ;
						prev = first;
						first = const_cast<QNode*>(first->next);
						delete prev;
				}
			} //end if
		}
	}
private:
	//classes & constants
	static const char SAFE = 0;
	static const char ALREADY_READ = 1;
	static const char SKIP_NEXT = 2;;
	struct QNode
	{
		QNode(T *d = 0, bool is_tail = true, char node_status = SAFE, QNode* next_node = 0)
			: data(d), tail(is_tail ? 1 : 0), status(node_status), next(next_node)
		{}
		T *data;
		volatile char tail;
		char status;
		QNode volatile *next;
	};
	//local data
	QNode *last;	//WARNING: do not switch declaration order with first (see init. list)
	QNode *first;
};
template<typename T> const char Queue<T>::SAFE;
template<typename T> const char Queue<T>::ALREADY_READ;
template<typename T> const char Queue<T>::SKIP_NEXT;

[Edited by - Akhilleus on June 12, 2009 5:13:45 PM]

The short, sweet, and nice answer is your code is not thread safe, it's not lock-free, and it's definitely not even a queue implementation (what happens if you call push more than once?). [wink]

Accomplishing a lockless data structure is quite tricky and takes quite a bit of low level research and work, especially if you want it to work on both x64 and x86 computer architectures. Material on the topic itself is quite limited, so I don't have any links, but I would suggest do some more extensive research on what lockless/lockfree algorithms are.

The best article to start with that I know of would be: Lockless Programming Considerations for Xbox 360 and Microsoft Windows. You might also be interested in>this thread: Double-check my lock-free voodoo.

Good luck!

Quote:The short, sweet, and nice answer is your code is not thread safe, it's not lock-free, and it's definitely not even a queue implementation (what happens if you call push more than once?).

Oops! push() does work more than once, I just seem to have accidentally erased the line resetting the last pointer. Fixed.

But for the thread-safety, it isn't designed to be thread-safe; it's only designed to work with threads if exactly one uses push() and only push, and exactly one uses pop() and only pop(). If it isn't safe for that, could you let me know where it will encounter problems (if it's completely botched, at least the first vulnerability or too so I can see where it went wrong)?

Quote:The volatile keyword should stop the compiler from breaking your code with optimisations, but stopping the CPU from doing so is a lot harder (x86 CPUs re-order instructions internally!!!). You need to learn about memory barriers (aka memory fences, aka interlocked operations) to make this safe.


Also, the default implementation of 'new' will probably be grabbing a mutex internally, which defeats the entire purpose of the lock-free queue :/
Try and do all your memory allocation up-front if possible, and then use placement-new if constructors are required.

Ahh, well I'll definitely do some research on memory barriers then. As for new, I'm aware of the possible problem, but I was planning on defining my own version to pull objects from a preallocated pool, if the Queue code itself is viable.

Okay, I've tried to take all the errors (both specific and in the overall design) pointed out here to rewrite the code, except that I unfortunately haven't had time to address the serial line problem mentioned by Hodgman. I realize it would probably be better to find a pre-implemented queue with the properties I want, or to follow one of the online to tutorials to make one, but now that I'm learning about the problems in designing one it's too interesting not to try and complete. I have been reading articles and information about the concept and related ones, however, as you all suggested.

The new code is in my first post replacing the old code now. I went ahead and fixed the problem whereby the code was relying on assignments to a pointer to be atomic; now pop() NEVER accesses last, even to read (likewise, push() never accesses first). Instead, I've changed the way QNode deals with statuses; one member holds whether the node is safe, already read, or whether it and the next node are both already read (as it was in the old code). There is also a second member, tail, that initializes to 1, indicating that the node is the tail, and is changed to zero by push() when another node is pushed onto it. This is the value that pop() uses to determine whether a node is the tail, instead of comparing that node's address with last. Because tail is always either 0 or 1 (it's a char, not a bool, so I ensure that numerical implementation myself), only one bit ever changes. So if push() is interrupted by pop() when the value is only half-written (if for some reason the machine isn't using aligned chars), pop() will access it but still get a valid value (the current value, if the 1 has already been written, or the previous value, if not). Obviously the only side effect of this is that pop() will in some cases think it's reached the end of the list when actually there's one more node in the process of being added, which is an unimportant side effect.

Again, I'm still very appreciative of comments, suggestions, and errors being pointed out.