Threadsafe Circular Queue

Hi,

I have the following working code for implementing a Circular Queue. How do I modify it to make it thread safe?

const int MAX = 5;
class CQueueImp
{
      int a[MAX],front,rear;
        
      public :
               void initialize();                // initialize
                  void enqueue(int );
               int dequeue();
               void display();
};




        void CQueueImp ::initialize()
        {
            front=rear=-1;
        }

        void CQueueImp :: enqueue(int val)
        {
             if((front==0 && rear==MAX-1) || (rear+1==front))
                    std::cout<<" Circular Queue is Full";
             else
             {
               if(rear==MAX-1)
                    rear=0;
               else
                   rear++;
               a[rear]=val;
             }
             if(front==-1)
               front=0;
        }
        int CQueueImp :: dequeue()
        {
             int k;
             if(front==-1)
                  std::cout<<"Circular Queue is Empty";
             else
             {
                  k=a[front];
                  if(front==rear)
                     front=rear=-1;
                  else
                  {
                     if(front==MAX-1)
                          front=0;
                     else
                          front++;
                  }
             }
             return k;
        }
        void CQueueImp :: display()
        {
              int i;
              if(front==-1)
                   std::cout<<"Circular Queue is Empty";
              else
              {
                   if(rear < front)
                   {
                        for(i=front;i<=MAX-1;i++)
                           std::cout<<a[i]<<"   ";
                        for(i=0;i<=rear;i++)
                           std::cout<<a[i]<<"   ";
                   }
                   else
                   {
                        for(i=front;i<=rear;i++)
                           std::cout<<a[i]<<"   ";
                        printf("\n");
                   }
              }
        }

        void main()
        {
             CQueueImp c1;
             c1.initialize();

             int ch,val;
             char op;
             do
             {
               std::cout<<"-----------Menu-------------";
               std::cout<<"1.Insertion 2.Deletion 3.Display 4.Exit ";
               std::cout<<"Enter Your Choice <1..4> ?";
               std::cin>>ch;
               switch(ch)
               {
                     case 1 : std::cout<<"Enter Element to Insert ?";
                                std::cin>>val;
                                    c1.enqueue(val);
                                    break;
                     case 2 : val=c1.dequeue();
                                    std::cout<<"Deleted Element :"<<val;
                                    break;
                     case 3 : c1.display();
                                    break;
                  }
                  std::cout<<"Do you want to continue<Y/N> ?";
                  std::cin>>op;
              }while(op=='Y' || op=='y');
            }

LVL 1
niftyhawkAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
evilrixSenior Software Engineer (Avast)Commented:
To make an object thread safe you need to ensure all access to its resources are atomic. This is normally done by protecting that access using a Mutex object or a Critical Section. So, in any functions that read/write to the resource (in this case your queue) you should provide mutex or critical section protection.
0
 
evilrixSenior Software Engineer (Avast)Commented:
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
evilrixSenior Software Engineer (Avast)Commented:
0
 
evilrixConnect With a Mentor Senior Software Engineer (Avast)Commented:
A very Q&D example of using critical section to protect a resource...

class foo
{
public:
      // Constructor to init critical section
      // Destructor to uninit cirtical section

      void write(char const * p)
      {
            EnterCriticalSection(&cs);
            s.assign(p);
            LeaveCriticalSection(&cs);
      }

      void clear()
      {
            EnterCriticalSection(&cs);
            s.clear();
            LeaveCriticalSection(&cs);
      }

private:
      std::string s; // Resource to protect
      CRITICAL_SECTION cs;
};
0
 
niftyhawkAuthor Commented:
Thanks for the suggestions.. I tried to modify my program based on your input...but it seems to hang when inserting an element..


        void CQueueImp :: enqueue(int val)
        {
             if((front==0 && rear==MAX-1) || (rear+1==front))
                    std::cout<<" Circular Queue is Full";
             else
             {
               if(rear==MAX-1)
                    rear=0;
               else
                   rear++;
              EnterCriticalSection(&cs);
               a[rear]=val;
              LeaveCriticalSection(&cs);
             }
             if(front==-1)
               front=0;
        }

It hangs at the EnterCriticalSection part.. Any ideas why? How can I test if it is thread safe or not?
0
 
niftyhawkAuthor Commented:
oops..sorry forgot to initialize critical section.... I modified my class file this way and it seems to work..

#include "windows.h"
const int MAX = 5;
class CQueueImp
{
       private:
        CRITICAL_SECTION cs;
      int a[MAX],front,rear;  
        
      public :
              CQueueImp()
              {
                    InitializeCriticalSection (&cs);
                    initialize();
              }
              ~CQueueImp()
              {
                    DeleteCriticalSection(&cs);
              }
               void initialize();                // initialize
                  void enqueue(int );
               int dequeue();
               void display();
};

But I am not quite sure how I can test this for thread safe?
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> But I am not quite sure how I can test this for thread safe?

Yes, multi-threaded programs by their very definition are non-deterministic, this make testing VERY HARD! I usually plump for ubiquitous about of trace so I get good output that I can then analyze to ensure everything happens as I expect in the order I expect it to.

I think the important thing is to have good unit tests that test each part in isolation -- to destruction (ie. don't just test what works but test what breaks too and make sure you handle it properly). I recommend using CPPUNIT for this -- it's a CPP unit test framework...

http://cppunit.sourceforge.net/cppunit-wiki

-Rx.
0
 
Infinity08Commented:
I see you only protect this :

              EnterCriticalSection(&cs);
               a[rear]=val;
              LeaveCriticalSection(&cs);

but not this :

               if(rear==MAX-1)
                    rear=0;
               else
                   rear++;

and other modifications to the class members (front, rear etc.).
0
 
evilrixSenior Software Engineer (Avast)Commented:
To elaborate on what Infinity08 has said, you must protect all shared resources -- that potentially means anything the class uses. By resource I mean, variables, files, pointer, memory -- anything that is a commodity.

I strongly recommend trying to get hold of a copy of this book...

http://www.oreilly.com/catalog/multithread/

-Rx.
0
 
evilrixSenior Software Engineer (Avast)Commented:
Articles on writing code that is thread safe -- long but, ostensibly, informative: -

http://www.artima.com/designtechniques/threadsafety.html
http://msdn.microsoft.com/msdnmag/issues/04/09/BasicInstincts/
0
 
niftyhawkAuthor Commented:
Thanks for your inputs guys..I am pretty new to threading. Dont you think writing like this is too much code?? It would be so much tedious to keep track of each and every shared variable changing.. True or Am I understanding wrong..

        void CQueueImp :: enqueue(int val)
        {
             if((front==0 && rear==size-1) || (rear+1==front))
                    std::cout<<" Circular Queue is Full";
             else
             {
               if(rear==size-1)
               {
                  EnterCriticalSection(&cs);
                    rear=0;
                  LeaveCriticalSection(&cs);
               }
               else
               {
                   EnterCriticalSection(&cs);
                   rear++;
                   LeaveCriticalSection(&cs);
               }
              EnterCriticalSection(&cs);
               a[rear]=val;
              LeaveCriticalSection(&cs);
             }
             if(front==-1)
             {
              EnterCriticalSection(&cs);
               front=0;
              LeaveCriticalSection(&cs);
             }
        }
        int CQueueImp :: dequeue()
        {
             int k;
             if(front==-1)
                  std::cout<<"Circular Queue is Empty";
             else
             {
                  EnterCriticalSection(&cs);
                  k=a[front];
                  LeaveCriticalSection(&cs);
                  if(front==rear)
                  {
                      EnterCriticalSection(&cs);
                     front=rear=-1;
                     LeaveCriticalSection(&cs);
                  }
                  else
                  {
                     if(front==size-1)
                     {
                          EnterCriticalSection(&cs);  
                          front=0;
                          LeaveCriticalSection(&cs);
                     }
                     else
                     {
                          EnterCriticalSection(&cs);
                          front++;
                          LeaveCriticalSection(&cs);
                     }
                  }
             }
             
             return k;
        }
0
 
Infinity08Connect With a Mentor Commented:
If the processing doesn't take too long (which is the case here), you can put a critical section around the whole method (or for example the else block in the dequeue method).
0
 
ZoppoConnect With a Mentor Commented:
Hi,

you should not do something like this:

...
              if(rear==size-1)
               {
                  EnterCriticalSection(&cs);
                    rear=0;
                  LeaveCriticalSection(&cs);
               }
               else
               {
                   EnterCriticalSection(&cs);
                   rear++;
                   LeaveCriticalSection(&cs);
               }
              EnterCriticalSection(&cs);
               a[rear]=val;
              LeaveCriticalSection(&cs);
 ...

because between the 'rear++' and the 'a[rear]=val;' the value of rear could change in another thread which will lead to wrong functionality, so better would be to synchronize the whole functoinality like this:

 ...
             EnterCriticalSection(&cs);
              if(rear==size-1)
               {
                    rear=0;
               }
               else
               {
                   rear++;
               }
               a[rear]=val;
              LeaveCriticalSection(&cs);
 ...

Regards,

ZOPPO
0
 
evilrixSenior Software Engineer (Avast)Commented:
I'd suggest reading the articles I posted before jumping in feet first into this! There are just too many pot-holes (as you can probably see). Zoppo has pointed out one of the most common Noob mistakes, but there are many others :) MT programming is HARD, finding bugs (such as race conditions) is HARDER... don't rush in, read a little first -- make sure you know your enemy before you attack :)

-Rx.
0
 
itsmeandnobodyelseConnect With a Mentor Commented:
You could do:

class CQueueImp
{
      int a[MAX],front,rear;
      CRITICAL_SECTION cs;
      class Lock
      {
            CRITICAL_SECTION& cs;
            Lock(CRITICAL_SECTION& c_s)
                 : cs(c_s)
            {
                   EnterCriticalSection(&cs);
            }
            ~Lock()
            {
                  LeaveCriticalSection(&cs);
            }
            friend class CQueueImp;
      };  
      public :
               CQueueImp()
                     : front(NULL), rear(NULL)
               {
                     memset(a, 0, MAX * sizeof(int));
                     InitializeCriticalSection(&cs);
               }
               ~CQueueImp()
               {
                      DeleteCriticalSection(&cs);
               }
               void initialize();                // initialize
               void enqueue(int );
               int dequeue();
               void display();
};


void CQueueImp::enqueue(int )
{
      Lock lock(cs);   // enters the critical section
      // put here your current code for enqueue
      ...
      // at end the destructor of Lock will leave the critical section
}

Do the same for

               int dequeue();
               void display();

Remarks:

The initialize normally doesn't need a protection as it was done by the main thread only.

It makes not much sense to only protect parts of the functions that are *writing* to the members. You need to protect reading from the members as well. Assume, you would execute the statement

    if((front==0 && rear==size-1) || (rear+1==front))

in unprotected (non-exclusive) mode by two threads nearly same time.

Then both threads might read 'front ==0' is true and both would set the 'front' to the new node to enqueue. Though the last action was made exclusively by each thread, the second would overwrite 'front' and 'rear' with a new node and the entry made by the first thread was lost.

So, generally, lock all operations made on members of the queue.

Regards, Alex
0
 
itsmeandnobodyelseCommented:
You gave a 'B' grade? May I ask why?

If your q.  was fully answered you should give an 'A'. If not you should ask further so that we can go for an 'A'.

Regards, Alex
0
 
niftyhawkAuthor Commented:
sorry.. I gave the points in a hurry and didnt really look what I was doing.. How do I change it to A grade?
0
 
itsmeandnobodyelseCommented:
>>>> How do I change it to A grade?

You could make a 0 points request in
http://www.experts-exchange.com/Community_Support/General/

but I do not mind if you let it as it is. I only wanted to know whether there is somewhat open.

Regards, Alex
0
 
kjehedCommented:

To clearify: A circular queue can quite easily be made thread-safe without using atomic operations (using Mutex or CriticalSection).

Let me examplify:
* One writer-thread to a circular buffer and one reader-thread - implementing it the right way means that you do not use to secure it with atomic operations.
* Multiple writer-threads and one reader-thread. To do it without 'atomic' operations you need to have each writer-thread have it's own circular queue - and the reader-thread can access them all.

For in-depth detail on how to implement this see:
http://www.ddj.com/cpp/184401814
or my own take at it: www.kjellkod.cc/thread_safe_circular_queue


 to the queue
xample: multiple input threads but one output thread,.. then you can implement it with multiple
0
 
kjehedCommented:

To clearify: A circular queue can quite easily be made thread-safe without using atomic operations (using Mutex or CriticalSection).

Let me examplify:
* One writer-thread to a circular buffer and one reader-thread - implementing it the right way means that you do not use to secure it with atomic operations.
* Multiple writer-threads and one reader-thread. To do it without 'atomic' operations you need to have each writer-thread have it's own circular queue - and the reader-thread can access them all.

For in-depth detail on how to implement this see:
http://www.ddj.com/cpp/184401814
or my own take at it: www.kjellkod.cc/thread_safe_circular_queue


0
All Courses

From novice to tech pro — start learning today.