How do I make a circular queue thread-safe?

Question

So my Enqueue and Dequeue functions are below. How do I take what I have and make it thread safe? I thought about using a mutex from Windows.h, but I'd like to not limit my program to Windows-only, if possible.

void Queue::Enqueue(int num){
    //increase recorded size
    size++;
    //stick in num
    numbers[nextSpace] = num;
    //find the next available space
    nextSpace = (++nextSpace) % maxSize;
}

int Queue::Dequeue(){
    int temp;
    temp = items[curSpace];
    curSpace = (++curSpace) % maxSize;
    size--;
    return temp;
}

Why reinvent the wheel? Use Boost's `lockfree::queue` or something like that. (Or `spsc_queue`, rather, if you want a circular buffer for one consumer and one producer.) — Kerrek SB, Apr 01 '13 at 20:38
Boost has a portable library for syncronization. See http://www.boost.org/doc/libs/1_53_0/doc/html/thread/synchronization.html — Jeff Paquette, Apr 01 '13 at 20:38
What version of "thread-safe" do you require? STL is thread-safe, you know? — Alex Chamberlain, Apr 01 '13 at 20:41
Your Dequeue() operation doesn't test for an empty queue. You need to test for empty queue and either return an error value, or block waiting for someone else to do the next Enqueue(). If you are okay with returning an error value (and then wasting CPU by repeatedly spinning) look into boost's lockfree queue. If you want a blocking Dequeue operation see [this stack overflow question](http://stackoverflow.com/questions/15278343/c11-thread-safe-queue) and [this web site](http://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html). — Wandering Logic, Apr 01 '13 at 22:07
Can't always use STL; it makes your brain mush :) @ n.m. good call! @WanderingLogic Nice catch! I only pasted the relevant code, there are a few other things going on, including tests for empty and full queues :) — BearInATie, Apr 01 '13 at 22:11
@BearInATie: Testing not-empty and then separately doing a Dequeue will typically lead to a race condition: (thread A tests not-empty (true), thread B tests not-empty (true), thread A calls Dequeue (gets the value), thread B calls Dequeue (gets garbage.) For a thread-safe queue the two operations _must_ be combined into a single critical section. — Wandering Logic, Apr 01 '13 at 22:20
They are- again, the code pasted above has been heavily modified to only show the critical point of the question — BearInATie, Apr 01 '13 at 22:22

score 0 · Answer 1 · edited Apr 01 '13 at 20:50

You can refer this code (with pthreads):

#include<pthread.h> 
#define DEFAULT_SIZE 100
class circularQueue{
 private:
    int *m_queue;
    int p_head;
    int p_tail;
    int m_cap;
    pthread_mutex_t mp = PTHREAD_MUTEX_INITIALIZER; 
    public:
        circularQueue(int size)
        {
            /*in case invalid input*/
            if(size<0)
                size = DEFAULT_SIZE ;

            m_queue = new int[size];
            p_head = 0;
            p_tail = -1;
            m_cap = 0;
            pthread_mutex_init(&mp,NULL);
        }

        bool enqueue(int x)
        {
            bool res= false;
            p_thread_mutex_lock(&mp);
            /*queue is full*/
            if(m_cap == size)
            {
                res = false;
            }
            else
            {
                m_queue[(++p_tail)%size)] = x;
                ++m_cap;
                res = true;
            }
            p_thread_mutex_unlock(&mp);
            return res;
        }
        int dequeue()
        {
            int res=0;

            pthread_mutex_lock(&mp);
            /*empty queue*/
            if(m_cap == 0)
            {    
                throw("empty queue!");
                pthread_mutex_unlock(&mp);
            }
            else{
                res = m_queue[p_head];    
                p_head = (p_head+1)%size;
            }
            pthread_mutex_unlock(&mp);
            return res;
        }    
        ~virtual circularQueue()
        {
            delete[] m_queue;
            m_queue = NULL;
            pthread_mutex_destroy(&mp);
        }
}

The `throw("empty queue!");` renders this code deadlock-capable (a thread could lock the mutex and then throw without unlocking). And even if that's fixed, you still have to consider that if adapted to non-builtin types whose assignment can throw you have the same problem. — Mark B, Apr 01 '13 at 21:37

How do I make a circular queue thread-safe?

1 Answers1