Monday, November 24, 2008

The Atomic Nugget Design Pattern: Part II

The Atomic Nugget design pattern is a way of encapsulating some action that a client wants to perform atomically with respect to a provider class. The idea is that the client will write a "first-class function," in the form of an anonymous inner class, and then give that action to the provider, who will then internally acquire and release the necessary synchronization. In order to make this work, we will need an interface for our first-class functions:

public interface Lambda<T1, T2> {
public T2 eval(T1 t);
}

This interface is the type of first-class functions that take one argument and return one argument. The next thing we'll need is an interface that signifies the fact that my provider class is an atomic nugget, which will allow client's code to be run atomically. As I previously mentioned, and like the lock/unlock solution, this requires some forsight from the developer.

public interface AtomicNugget<T> {
public <S> S atomic(Lambda<T,S> operation);
}

This interface allows the implementer to take a client operation, in the form of a lambda from elements of 'this' type to elements of some other type, and execute that operation atomically. Here's how it might look in some kind of thread-safe stack:

public class AtomicStack<T> implements AtomicNugget<AtomicStack<T>> {
private final Deque<T> stack = new LinkedList<T>();
public synchronized T pop() {
return stack.pop();
}
public synchronized void push(T e) {
stack.push(e);
}
public synchronized boolean isEmpty() {
return stack.isEmpty();
}
public synchronized <S> S atomic(Lambda<AtomicStack<T>, S> operation) {
return operation.eval(this);
}
}
This particular case is pretty simple. Note how AtomicStack<T> implements AtomicNugget<AtomicStack<T>>. This will ensure that the first argument of the lambda is the stack itself. The client is free to return any type they want from their atomic operation, which we allow by parameterizing the atomic method. Every public method of the AtomicStack is synchronized, including atomic, so that when a client calls atomic, everything that is executed inside of the operation will be done in the confines of that synchronized block. Here's a client side use:

AtomicStack<Integer> stack = new AtomicStack<Integer>();
Integer got =
stack.atomic(new Lambda<AtomicStack<Integer>,Integer>() {
public Integer eval(AtomicStack<Integer> t) {
if( !t.isEmpty() ) return t.pop();
else return null;
}});

In this example, the client creates an anonymous inner class, the "first-class function," which consists of an isEmpty check and a call to pop. This new object is then passed as an argument to the atomic method of the newly created stack. The "lambda" returns the dequed item to the outer context. This is a pretty straightforward example. Here's something a little more interesting. There is a classic problem in concurrency relating to bank accounts. How can I, as a client, using two thread-shared bank accounts withdraw money from one and deposit the money to the other all in one atomic operation? Deadlock is an important concern in this sort of example. Well, we can solve it using AtomicNugget2, which takes two elements of the same type. Internally we are free to synchronize on both object according to our deadlock prevention scheme (in this example, I use the hash code as an ID to determine ordering of lock acquire). First, here is AtomicNugget2:

public interface AtomicNugget2<T> {
public <S> S atomic(Lambda2<T,T,S> operation, T withRespectTo);
}

Pretty similar to AtomicNugget. Now, here is our bank account, which implements the interface:
public class BankAccount implements AtomicNugget2<BankAccount> {
private long amount;
public synchronized void withdraw(long amt) {
amount -= amt;
}
public synchronized void deposit(long amt) {
amount += amt;
}
public <S> S atomic(Lambda2<BankAccount, BankAccount, S> operation,
BankAccount withRespectTo) {
// We acquire locks in order of hash code
if( System.identityHashCode(this) < System.identityHashCode(withRespectTo)) {
synchronized( this ) {
synchronized( withRespectTo ) {
return operation.eval(this, withRespectTo);
}
}
}
else {
synchronized( withRespectTo ) {
synchronized( this ) {
return operation.eval(this, withRespectTo);
}
}
}
}
}

Note how we reverse the order of the synchonized blocks depending on the hash ids of the bank accounts. However, we still pass the two bank accounts as arguments to the lambda in the same order. This is crucial for clients who need to know, for example, which is the deposit account and which is the withdrawal account. Finally, here's a client:

BankAccount b1 = //...
BankAccount b2 = // ...
b1.atomic(new Lambda2<BankAccount,BankAccount,VOID>(){
public VOID eval(BankAccount t1, BankAccount t2) {
t1.withdraw(500);
t2.deposit(500);
return VOID.instance;
}}, b2);

The atomic nugget has some problems. Notably, the provider has to be aware that the client's calls will almost certainly be reentrant. If you are using semaphores or some kind of non-reentrant locks, this could be a problem. There are others. Nonetheless, I think in many cases this is a good way to go, and if you are already programming Java in a functional style (a good, if verbose way of doing things) it will seem very natual.

No comments:

Post a Comment