Solved

Threadsafe Circular Queue

Posted on 2007-11-14
21
2,084 Views
Last Modified: 2011-09-20
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');
            }

0
Comment
Question by:niftyhawk
  • 9
  • 4
  • 3
  • +3
21 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 20278490
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
 
LVL 40

Accepted Solution

by:
evilrix earned 300 total points
ID: 20278491
0
 
LVL 40

Expert Comment

by:evilrix
ID: 20278498
0
 
LVL 40

Expert Comment

by:evilrix
ID: 20278501
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 300 total points
ID: 20278526
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
 
LVL 1

Author Comment

by:niftyhawk
ID: 20278572
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
 
LVL 1

Author Comment

by:niftyhawk
ID: 20278641
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
 
LVL 40

Expert Comment

by:evilrix
ID: 20278716
>> 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
 
LVL 53

Expert Comment

by:Infinity08
ID: 20278759
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
 
LVL 40

Expert Comment

by:evilrix
ID: 20278776
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
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 40

Expert Comment

by:evilrix
ID: 20278787
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
 
LVL 1

Author Comment

by:niftyhawk
ID: 20278906
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 50 total points
ID: 20278948
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
 
LVL 30

Assisted Solution

by:Zoppo
Zoppo earned 100 total points
ID: 20278964
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
 
LVL 40

Expert Comment

by:evilrix
ID: 20279015
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
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 50 total points
ID: 20279649
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
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20283051
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
 
LVL 1

Author Comment

by:niftyhawk
ID: 20324303
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
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 20326018
>>>> 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
 

Expert Comment

by:kjehed
ID: 21891283

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
 

Expert Comment

by:kjehed
ID: 21891284

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

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
C++ - Convert a wString to char * 9 428
why "." vs "->" 23 116
C++ get user from AD  (VS6) 7 48
how to convert c++ code to Android App 3 64
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now