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<<"-----------Men u--------- ----";
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');
}
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<<"-----------Men
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');
}
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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?
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?
ASKER
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?
#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.
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.).
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.
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/
http://www.artima.com/designtechniques/threadsafety.html
http://msdn.microsoft.com/msdnmag/issues/04/09/BasicInstincts/
ASKER
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;
}
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
-Rx.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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
ASKER
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
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