A Thread Safe Ring Buffer in Java
1. Critical Regions: I’m not done yet.
The classic example involves a bank account:
class Account {
private int balance; // in cents.
public Account(int balance) {
this.balance = balance;
}
public int getBalance() { return balance; }
public void deposit(int amount) {
balance += amount;
}
public void withdraw(int amount) {
balance -= amount;
}
}
If you make a deposit and a withdrawal at the same time, one of the two operations could have no effect. Since this code happens to be in Java, there happens to be an easy fix:
class synchronizedAccount {
private int balance; // in cents.
public Account(int balance) {
this.balance = balance;
}
public int getBalance() { return balance; }
public synchronized void deposit(int amount) {
balance += amount;
}
public synchronized void withdraw(int amount) {
balance -= amount;
}
}
Just adding the keyword ‘synchronized’ looks simple enough, though you’re likely to forget it just where you need it. (I know I have.) Furthermore, ‘synchronized’ will only save you from a few woes.
2. Race Conditions: What happens depends on who gets there first.
Here’s is another common case. I’m sending items from from one object to another. The two objects run concurrently. So to reduce wait time, I want to use a simple ring buffer:
class MessageBuffer {
Message[] messages = new Message[BUF_SIZ];
int hd = 0, tl = 0;
synchronized void put(Message mess)
throws BufferOverflowException
{
messages[tl] = mess;
++tl;
if (tl == messages.length) tl = 0;
if (tl == hd) throw new BufferOverflowException(this);
}
synchronized Message get()
throws BufferUnderflowException
{
if (hd == tl) throw new BufferUnderflowException(this);
Message mess = messages[hd];
++hd;
if (hd == messages.length) hd = 0;
return mess;
}
}
As is, if you read messages faster than they’re being sent or send messages faster than they’re being read, you have to do your own exception handling. This is good in some cases: you may want to do something exceptional when the buffer is empty (or full). For example, you might want to make sure that whomever you’ve been talking to hasn’t suffered an untimely death. On the other hand, you usually don’t assume sudden death (at least I don’t). Rather, I just suppose the other party is slow. In that case, I might as well wait. The snippet below folds all the waiting behavior into the buffer class so that I don’t need to deal with it.
class BlockingMessageBuffer {
Message[] messages = new Item[BUF_SIZ];
int hd = 0, tl = 0;
public synchronized void put(Message mess) {
messages[tl] = it;
++tl;
if (tl == messages.length) tl = 0;
if (tl == hd) waitIgnoringInterrupts();
notifyAll(); // Wakes all the threads that are waiting to get.
}
public synchronized Message get() {
if (hd == tl) waitIgnoringInterrupts();
notifyAll(); // Wakes all the threads that are waiting to put.
Message mess = messages[hd];
++hd;
if (hd == messages.length) hd = 0;
return mess;
}
private void waitIgnoringInterrupts() {
while (true) {
try {
wait(); // Puts the current thread to sleep and
// frees synchronization claims on this buffer.
return;
} catch (InterruptedException e) {}
}
}
}
There’s two. Another two come to mind:
3. Deadlock: We’re all waiting on eachother.
4. Starvation: I never get a turn.