Making thread safe queue

[Kanoisa]

Hi all,

I'm currently thinking about how to make a thread safe queue. Specified as such:

• Single reader
• Multiple writers
• Dynamically sized
• Suitable for both a reader sleeping on a queue or as a polled queue

So what I'm looking at so far (pseudo)code wise is the following

#define unsigned long u32_t;

struct stElement
{
   u32_t  size;
   u32_t* pData;
};

class clTSQueue
{
public:
void       SetSleepSignal( signal* _signal); /* signal so the reader can sleep on this Q */
void       Push( stElement* _element );
stElement* Pop( void );
u32_t      GetNumElements( void ); /* if not sleeping on the queue will definitely want to know this */

protected:
std::list<stElement*> m_elements;
mutex                 m_hMutex;
signal*               m_pSignal;
};

void clTSQueue::Push( stElement* _element )
{
   /* make a copy of the data passed in */
   stElement* cpOfElem = new u32_t[_element->size];
   memcpy(cpOfElem->data, _element->data, _element->size);
   cpOfelement->size = _element->size;

   mutex_lock( m_hMutex ); /* lock the resource */

   m_elements.push_back( cpOfElem );  /* append the new copy to the queue */

   if( NULL != m_pSignal ) /* if we have a valid signal then signal it */
   {
      set_signal( m_signal ); 
   }

   mutex_unlock( m_hMutex ); /* unlock the resource */
}

stElement* clTSQueue::Pop( void ) 
{
   return m_elements.pop_front();
}

This brings me to the question at hand then. Is having a write lock enough as only one reader reading from the front of the queue should not interfere with writers? or is that a misplaced way of thinking?

If anyone can give any advice, opinions or improvements on this mock up code then I would really appreciate it.

many thanks
Kano

[Ancient Dragon]

Yes I think its misplaced thinking. What if there are no items in the queue, and reader tries to read while writer tries to write? Everyone needs to be locked out while writer tries to write to the queue. Depending on how your code is written there could be more than one reader at the same time. But writer should have exclusive use of the queue data.

There are several ways to accomplish that. One way is setting up a mutex. Under MS-Windows another way is via CRITICAL_SECTION.

[Kanoisa]

I am going to write the code so each queue will definately only have one reader, as the queues are to be used to send messages between modules with each module having its own queue and messages posted to these queues via an observer pattern.

Just to check if i understand correctly you reccommend then that the reader must also lock the mutex during a read operation to ensure only one thread can access the resource?

Thanks for replying

edit: just curious then. I dont think i need the ability but having the read function also using a mutex would make it safe for multiple readers as well?

[Ancient Dragon]

Yes the reader should also lock with the mutex. I suppose you could have just one queue for all readers, as long as the objects in the queue have something to tell you what message goes to whom. Something like that is what MS-Windows does with the windows messages -- each message contains a handle to the destination window.

[mike_2000_17]

Normally, you do need to lock both the reader and writer such that their operations are mutually exclusing (with a mutex or critical section(windows), personally I would recommend Boost.Thread since it uses the best mechanisms for whatever OS you use). And, if you lock all read and write operations, then there is, of course, no issue with having multiple readers and multiple writers. But be careful not to introduce deadlocks. Also make sure you don't lock for more time than needed, because you can easily destroy performance (i.e. you end up with a number of threads lined-up, sleeping, when they could be doing useful work).

You probably also want to use a condition_variable to wake up the reader when a new element is available (in fact you can use the same mutex in the condition_variable). This is going to avoid needless decisions on how to poll for new elements to read (do you use a tight loop that repeatedly checks for new elements, or do you sleep X amount of time between checks). The condition_variable will allow you to put the reader thread to sleep until the queue has a new element.

Finally, if this is anywhere near to being a performance-sensitive implementation, then there are alternatives that allow you to avoid locking (almost) completely. This article presents a nice and simple lock-free queue implementation. Operating systems often rely on a form of RCU to have lock-free readers in a single-writer / multiple-readers problem.

[Kanoisa]

Thanks to you both, i think i am going to go for a hybrid approach.

based on the above i think i will go for a multi reader/multi writer queue for broadcast messages, and non time critical messaging and try to impliment a lock free single reader multiple writer queue for time critical operations.

I dont mean to sound offensive mike i do respect you and your opinions as always are appreciated, but did you look at my code at all?

You probably also want to use a condition_variable to wake up the reader when a new element is available (in fact you can use the same mutex in the condition_variable). This is going to avoid needless decisions on how to poll for new elements to read (do you use a tight loop that repeatedly checks for new elements, or do you sleep X amount of time between checks). The condition_variable will allow you to put the reader thread to sleep until the queue has a new element.

My Queue implimentation supports both sleeping on a signal and polling methods already.

However that said in the first line you totally answer my question,a nd the lock free queue information is quite interesting thanks for that useful insight.

I think that wraps up what im looking for here so once again thanks for the responses, case closed!