Lock free atomic circular queue not working properly

Question

I tried to create a lock free atomic circular queue but it is not working properly.

I created 2 threads. One is for pushing into queue and another one is for popping from the queue. But;

Problem: -When push thread running then pop thread does not get chance to run. Pop thread runs after push thread runs completely and vice versa.

I do not know much about C++. So, please can you edit my code so that it works?

I am using GCC 4.8.1

Thanks in advance.

Code:

#include <cstdlib>
#include <iostream>
#include <atomic>
#include <cstddef>
#include <thread>
#include <stdio.h>
#include <unistd.h>

#define capacity 1000



std::atomic<int> _head;
std::atomic<int> _tail;

int array[capacity];

int increment(int size)
{
    return (size+1)%capacity;
}

bool push(int *item)
{
    printf("Inside push\n");
    const int current_tail= _tail.load(std::memory_order_relaxed);
    const int next_tail=increment(current_tail);

    if(next_tail != _head.load(std::memory_order_acquire))
    {
         array[current_tail]=*item;
         _tail.store(next_tail,std::memory_order_release);

         return true;
    }

         return false; //Queue is Full
}

bool pop(int *item)
{   
      printf("Inside pop\n");
      const int current_head=_head.load(std::memory_order_relaxed);

      if(current_head==_tail.load(std::memory_order_acquire))
      {
          return false;//empty queue
      }

      *item=array[current_head];
      _head.store(increment(current_head),std::memory_order_release);

      return true;
}

bool isEmpty()
{
    return(_head.load()==_tail.load());
}

bool isFull()
{
    const int next_tail=increment(_tail);

    return (next_tail==_head.load());
}

bool isLockfree()
{
    return (_tail.is_lock_free() && _head.is_lock_free());
}

void *threadfunction_push()
{
    int item,i;
    bool flag;
    item=0;

    for(i=0;i<10000;i++)
    {
        while(isFull())
        std::this_thread::yield();

        ++item;
        push(&item);
        printf("pushed %d into queue\n",item);
        //usleep(100);

     }

}

void *threadfunction_pop()
{
    int item,i;

    item=0;
    for(i=0;i<10000;i++)
    {
       while(isEmpty())
             std::this_thread::yield();

       pop(&item);
       printf("popped %d from queue\n",item);


    }

     i=isLockfree();
     if(i)
        printf("Queue is lock Free");
}


int main(int argc, char** argv) 
{


    std::thread thread_push(threadfunction_push);
    std::thread thread_pop(threadfunction_pop);

    thread_push.join();
    thread_pop.join();

     return 0;
}

You are aware, that this queue only works for a single producer and a single consumer?The reason, why they are running one after the other is probably that the loops are far too short. By the time the second thread is created and scheduled to run the first has probably already been completed. — MikeMB
Yes, this is single producer and single consumer queue.I tried with increase loop counter but still it is not working. — Deep Parikh
By how much? And how did you determine that it is not working? — MikeMB
I tried to run loop 100000 times but first 100000 times only pop thread runs and after 100000 times push thread runs.I expect that both threads run parallel. — Deep Parikh
That's not how multithreaded programming works. The fact that you have such useless functions like isEmpty suggests you need a better understanding of the basic idea of concurrent programming, possibly from a textbook. — DanielKO

Zhichao Jia Zhichao Jia · Accepted Answer · 2015-07-09T16:42:50

The first thing you need to know is multi-threading on a single-core single-thread processor. If the processor on which the above code runs is a single-core single-thread processor, then there wouldn't be threads running parallel. Multi-threading on such processor is kind of like the multi-process concepts. Only one thread runs at a time, and after a certain period of time, when the first thread has used its time slice, the OS will schedule it to sleep and the other thread to come up and start running. That's why you see "Pop thread runs after push thread runs completely and vice versa."

Actually, @MikeMB has pointed out the root cause, its because the running loop is far too short. If you change your array capacity to 100,000, and increase the loop counter i of both the pop thread and the push thread to 1000 or more, you'll see that pop and push would be running alternately. This is tested on my vmware CentOS 6.4 with gcc4.9.2.

Good luck!

Lock free atomic circular queue not working properly

2 Answers