Lock-Free Queue?
Hello,
I had a go a while back at making a lock-free queue (one thread will not be held up waiting for the other to finish what it's doing). This is based around the idea of one and only one thread adding items to the queue and one and only one thread removing items from it.
It works around the idea of two lists. At any time, one list is available to each thread to add/remove items.
When the producing thread is finished adding it manually calls QueueFlush() to swap the lists. (I couldn't work out an automatic way of doing this that was efficient. Swapping the lists every time something was added seemed inefficient)
The consuming thread calls QueueRecv() to retrieve a pointer to its list. The pointer is removed from the queue structure, thus preventing the other thread from accidentally getting access to it.
The only problem is, it works, some of the time...Code:typedef struct { t_list *plistQueue; t_list *plistSwap; } t_msgqueue; int QueueRecv(t_msgqueue *pQueue, t_list **pplistMsgs) { t_list *plist; *pplistMsgs = NULL; if (!pQueue) return -1; // plistQueue is what we want to retrieve plist = InterlockedExchangePointer(&pQueue->plistQueue, pQueue->plistSwap); InterlockedExchangePointer(&pQueue->plistSwap, plist); if (plist->uiCount > 0) { *pplistMsgs = plist; return plist->uiCount; } else return 0; } int QueueSend(t_msgqueue *pQueue, unsigned int uiMsgID, int iParam1, void *pParam2) { t_msg *pMsg; if (!pQueue) return -1; pMsg = lalloc(sizeof(*pMsg)); if (!pMsg) return -1; pMsg->uiMsgID = uiMsgID; pMsg->iParam1 = iParam1; pMsg->pParam2 = pParam2; linsert(pQueue->plistQueue, pMsg, NULL); return 0; } void QueueFlush(t_msgqueue *pQueue) { // swap pointers InterlockedExchangePointer(&pQueue->plistSwap, InterlockedExchangePointer(&pQueue->plistQueue, pQueue->plistSwap)); }
Any ideas?
Originally Posted by CommonTater
