Jump to content
  • Advertisement
Sign in to follow this  
BeanDog

Threads filling a queue

This topic is 4651 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am writing a program that has several threads that process different data. However, each thread outputs the same data structure, which should then be processed by the main thread. I've never written a complicated multithreaded application before, but I've considered doing something like the following: The queue would be represented by a singly-linked list. Each worker thread has access to the main thread's queue. When one is ready to add an item to the queue, it first enters a critical section that represents the *last* item in the queue. It then updates the "next" pointer in the last item in the queue to be its newly-created data object. This new object has NULL as its "next" pointer. The worker thread then exits the critical section. The main thread would not have to enter the critical section unless it had arrived at the last item in the queue (the queue length would be kept track of by InterlockedIncrement and InterlockedDecrement). What do you think? Is there a tried-and-true way of doing this that I've missed? Some code for queueing up data from a thread:
void b3dPlayPacketQueue::EnqueuePacket(b3dPlayPacket *pPacket)
{
	EnterCriticalSection(&m_csPacket);
	if(m_pHeadPacket)
	{
		//TODO: optimize this loop out.
		b3dPlayPacket *pTail = m_pHeadPacket;
		while(pTail->m_pNext)
			pTail = pTail->m_pNext;

		//pTail is now the tail node.
		pTail->m_pNext = pPacket;
	}
	else
		m_pHeadPacket = pPacket;

	LeaveCriticalSection(&m_csPacket);
}
And some code for dequeueing a packet from the queue:
	b3dPlayPacket *ret = NULL;
	if(m_pHeadPacket)
	{
		//Unless this is the tail node, we don't have to go into a
		//critical section to remove it from the list.
		if(m_pHeadPacket->m_pNext)
		{
			ret = m_pHeadPacket;
			m_pHeadPacket = m_pHeadPacket->m_pNext;
		}
		else
		{
			EnterCriticalSection(&m_csPacket);
			ret = m_pHeadPacket;
			m_pHeadPacket = NULL;
			LeaveCriticalSection(&m_csPacket);
		}
	}
	
	return(ret);
Do you see any obvious threading problems in the above code? ~BenDilts( void ); [Edited by - BeanDog on September 25, 2005 1:43:26 PM]

Share this post


Link to post
Share on other sites
Advertisement
Yes there is a threading problem. What if m_pHeadPacket->m_pNext becomes NULL after the if, i.e. between the { and EnterCriticalSection(&m_csPacket); in the else?
You end up setting m_pHeadPacket to NULL, dropping what was just added by the other thread.

The "test if I should bother to lock" strategy is very unsafe in general.
You should always lock the whole list while each thread (including the main thread) is accessing it. That would be far safer. By all means, minimise the time that the main thread accesses it for, but I don't think it'll hurt performance one iota anyway. If all you're doing is popping nodes off each time then you can simply lock it for each pop.

Also, why not use std::list, or possibly std::deque?

Share this post


Link to post
Share on other sites
If you protect the entire list, when the main thread reads the list, you could simply splice the list nodes from the input queue to a non-protected list that the main thread could read. This should prevent some of the nastier corner cases that your implementation seems to suffer from.

Share this post


Link to post
Share on other sites
With a bit of magic the Win32 API can actual provide lock-free singly linked lists.
You may want to use them instead if portability isn't much of an issue or if this is a very frequent operation.

Clicky

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
If you protect the entire list, when the main thread reads the list, you could simply splice the list nodes from the input queue to a non-protected list that the main thread could read. This should prevent some of the nastier corner cases that your implementation seems to suffer from.
Wow, I was actually considering suggesting doing the same thing using splice also! I don't know why I didn't now.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!