Suppose you have a class that has several member fields and you wish to modify all the fields in one shot (a single transaction) and that we define two simple operations, a Write operation (incrementMembers()) and a Read operation (sumMembers()):
class MyClass {
int a;
int b;
int c;
//
This is a Write operation
void incrementMembers() {
a++;
b++;
c++;
}
//
This is a Read operation
int sumMembers() {
return (a+b+c);
}
}
Making each of the members be an atomic variable is not enough because, a Reader thread could jump in the middle of a Write operation and see an "inconsistent" state of the MyClass instance. For example, let's say that the only valid states are {a=1;b=1;c=1}, {a=2;b=2;c=2}, {a=3;b=3;c=3}... etc, and for example, the following state would be invalid {a=1;b=2;c=2}:
class MyClass {
volatile int a;
volatile int b;
volatile int c;
void incrementMembers() {
a++;
b++;
c++;
}
int sumMembers() {
return (a+b+c);
}
}
The code above is "wrong" because making the members of MyClass atomic (or volatile in Java) would not suffice since a Reader thread could end up seeing an invalid state like {a=1;b=2;c=2} if there is an ongoing call of incrementMembers(), and return a value of 5 from sumMembers() which should not be possible.
The simplest solution to this problem is to wrap the access to each instance with a mutual exclusion lock, or better yet, with a Reader-Writer Lock so that multiple Readers may enter at the same time. The new code would look like this:
class MyClass {
int a;
int b;
int c;
ReentrantReadWriteLock rwlock;
void incrementMembers() {
rwlock.writeLock().lock();
a++;
b++;
c++;
rwlock.writeLock().unlock();
}
int sumMembers() {
int sum = 0;
rwlock.readLock().lock();
sum = a+b+c;
rwlock.readLock().unlock();
return (sum);
}
}
The problem with the RWLock approach is that it is Blocking.
So, how do we do it in a way that is non-blocking?
One way that is very fashionable amongst functional programmers is to make the contents of the class immutable, and whenever we need to change one (or several) of the members, we just make a copy of the entire instance:
class MyClass {
final int a;
final int b;
final int c;
MyClass(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
MyClass incrementMembers() {
return new MyClass(a+1, b+1, c+1);
}
int sumMembers() {
return (a+b+c);
}
}
Notice that incrementMembers() now returns a new instance of MyClass where all the members have been incremented by one.
This immutability technique has been used in many situations, but particularly in the context of Immutable data structures or sometimes also called Persistent data structures. See for example Scala's ImmutableTreeSet or Function Java's TreeMap:
http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.TreeSet
http://functionaljava.googlecode.com/svn/artifacts/3.0/javadoc/fj/data/TreeMap.html
Advantages:
- Non-Blocking (Wait-Free) operations (assuming a single Writer).
- Simple to implement
Disadvantages:
- Allows only a single Writer
- Needs a language with a Garbage Collector
- Slow for large objects
- Lots of churn on the GC
- Even with a single Writer thread it is not really Wait-Free for incrementMembers() because it does memory allocation. Will be realistically Lock-Free at best.
On the next post we will see a variation of this pattern that allows for multiple Writers.
No comments:
Post a Comment