Link to home
Start Free TrialLog in
Avatar of niftyhawk
niftyhawk

asked on

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');
            }

Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

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.
ASKER CERTIFIED SOLUTION
Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of niftyhawk
niftyhawk

ASKER

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?
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?
>> 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.
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.).
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.
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/
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;
        }
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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
sorry.. I gave the points in a hurry and didnt really look what I was doing.. How do I change it to A grade?
>>>> How do I change it to A grade?

You could make a 0 points request in
https://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

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

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