Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

Posted on 2007-11-14
Medium Priority
2,114 Views
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<<"1.Insertion 2.Deletion 3.Display 4.Exit ";
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
Question by:niftyhawk
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 9
• 4
• 3
• +3

LVL 40

Expert Comment

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

evilrix earned 900 total points
ID: 20278491
0

LVL 40

Expert Comment

ID: 20278498
0

LVL 40

Expert Comment

ID: 20278501
0

LVL 40

Assisted Solution

evilrix earned 900 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

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

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

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

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

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...

-Rx.
0

LVL 40

Expert Comment

ID: 20278787
Articles on writing code that is thread safe -- long but, ostensibly, informative: -

http://msdn.microsoft.com/msdnmag/issues/04/09/BasicInstincts/
0

LVL 1

Author Comment

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

Infinity08 earned 150 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 31

Assisted Solution

Zoppo earned 300 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

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

itsmeandnobodyelse earned 150 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

ID: 20283051

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

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

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

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.

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

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.

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more adâ€¦
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationâ€¦
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month9 days, 21 hours left to enroll