In this example, we will look into a simple example that uses java's synchronized keyword.
Consider the following unsafe shared queue example first.
public class SharedQueueUnsafe
{
private int[] queue;
private int head, tail, num_elems;
private int size;
public SharedQueueUnsafe(int size)
{
this.size = size;
queue = new int[size];
for (int i=0; i<size; i++)
queue[i] = -1;
head = tail = num_elems = 0;
}
public void enqueue(int data)
{
num_elems++;
System.out.println("inserting " + data + " into the queue");
try
{
Thread.sleep(100);
}
catch (InterruptedException ie)
{
}
queue[head] = data;
head = (head + 1) % size;
}
public int dequeue()
{
num_elems--;
int ret = queue[tail];
tail = (tail + 1) % size;
return ret;
}
public int getElementsInQueue()
{
return num_elems;
}
static public void main(String[] args)
{
SharedQueueUnsafe sharedQueue = new SharedQueueUnsafe(10);
Thread insertThread = new Thread()
{
public void run()
{
sharedQueue.enqueue(12345);
}
};
Thread removeThread = new Thread()
{
public void run()
{
while (sharedQueue.getElementsInQueue() <= 0)
;
int element = sharedQueue.dequeue();
System.out.println("retrieved " + element);
}
};
insertThread.start();
try
{
Thread.sleep(50);
}
catch (InterruptedException ie)
{
}
removeThread.start();
}
}
Two threads are created such that one thread is inserting elements while the other is retrieving. To demonstrate racing condition, the enqueue method is designed to be intentionally slow. When I compile and run this, I get
$ javac SharedQueueUnsafe.java && java SharedQueueUnsafe
inserting 12345 into the queue
retrieved -1
This is because the retrieving thread accessed the queue before it was actually inserted, so that it retrieved the initialization value of -1 rather than 12345.
A crude solution to prevent this happening is rather trivial. We simply make sure that enqueue, dequeue, and getElementsInQueue methods to execute exclusively for a single object. That is, however many threads want to access these methods simultaneously, we force only a single thread can actually access only one of the synchronized methods at any given time. This will of course bring up side effect: performance issue, but for not let's not worry about it yet. We just want to solve the racing condition here.
Java language supports keyword synchronized for methods for this purpose. We simply let each method synchronized such that only a single thread can run any one synchronized method at a given time. Other threads must wait until the current thread is done executing the method. This is rather trivial in this case, and the code is as follows:
public class SharedQueueSafe
{
private int[] queue;
private int head, tail, num_elems;
private int size;
public SharedQueueSafe(int size)
{
this.size = size;
queue = new int[size];
for (int i=0; i<size; i++)
queue[i] = -1;
head = tail = num_elems = 0;
}
public synchronized void enqueue(int data)
{
num_elems++;
System.out.println("inserting " + data + " into the queue");
try
{
Thread.sleep(100);
}
catch (InterruptedException ie)
{
}
queue[head] = data;
head = (head + 1) % size;
}
public synchronized int dequeue()
{
num_elems--;
int ret = queue[tail];
tail = (tail + 1) % size;
return ret;
}
public synchronized int getElementsInQueue()
{
return num_elems;
}
static public void main(String[] args)
{
SharedQueueSafe sharedQueue = new SharedQueueSafe(10);
Thread insertThread = new Thread()
{
public void run()
{
sharedQueue.enqueue(12345);
}
};
Thread removeThread = new Thread()
{
public void run()
{
while (sharedQueue.getElementsInQueue() <= 0)
;
int element = sharedQueue.dequeue();
System.out.println("retrieved " + element);
}
};
insertThread.start();
try
{
Thread.sleep(50);
}
catch (InterruptedException ie)
{
}
removeThread.start();
}
}
With this new class, we get correct result.
$ javac SharedQueueSafe.java && java SharedQueueSafe
inserting 12345 into the queue
retrieved 12345
Well, the solution above is only a temporary crude solution. There are some more fixes to be made, but let's not worry about them for now. We will revisit this example in subsequent posts (
part II).
