Circular Linked List and Thread Safety ?

Question

I was working on Circular Queue of integers, I was wondering if someone can give me an example how to implement Circular quere which is (thread safe) and use user defined array size. How to do initialize(), enqueue(), dequeue()...

Thanks,

Jerry

Answer 1

ok heres a class in psuedo code and explanation after

__class queu__
{
int array[];
int nextPointer;
int lastPointer;
int sizee;

constructor queu(int size){ array=new int[size] array;
nextPointer=size-1; lastPointer=0; sizee=size; }

void enqueu(int toQueu) {lockmutext(a);
array[lastpointer]= toQueu;
lastPointer= inc(lastPointer); unlockmutex(a); }

int dequeu() {int a; lockmutex(b);
if a=inc(nextPointer)==lastPointer return null;
nextPointer= a; unlockmutex(b);
return array[nextPointer]; }

int inc(int a) {
if a==size-1 then return 0
else return a++; }
}

A non circular queue would just be foolish, as everything in the queu would have to be shifted every time something was removed. As for thread safe, I assume you meant multi thread safe, which is the reason for the mutual exclusion thingies in add and remove from queu. Without them the same value could be returned twice or 2 different values could be put into one spot (thus overwriting one). Sorry for the messy code but I really am not good with syntax lol.

And that first answerer was kind of lame lol. Anyways I'm just 16 this is really not complicated at all.

Answer 2

I think the easiest way to do this is the lock the whole list long enough to get locks on the nodes you need to operate on. Otherwise, you are going to have a host of race conditions and deadlock problems.

1. Lock whole list
2. Get locks on nodes before and after (if the linkages go both ways)
3. Release gobal lock
4. Do operations
5. Release node locks

If you cannot get the all the node locks you need in step 2 then release all the node locks you recieved, global and node. Then try again with step1.

Answer 3

I assume it is Java, some college uses C# in freshman year you did not say.

Can't believe you are dealing with thread safety by now. But it entails no more than declaring synchronized in every declaration. I'm trying to talk in freshman level.

A simple circular queue was in my first year comp-sci lecture note that I had to get (since this is not programming intro but comp-sci intro I had no confidence in ace the course without material) if you are in the area drop in University of Toronto or search online.