AtomicReference + immutable = lockfree

Q: what does atomic mean?
A: “within this method between first and last access to some shared object, no other thread can modify it without me knowing.”

For a mutable bean like Account, we’d love atomic operations like addInterest(). Note there’s no AtomicFloat class.

Note AtomicReference is a wrapper/bridge of the raw pointer. Somewhat similar to how a smart pointer wraps a raw pointer. Our AtomicAccount.java could be a bigger wrapper around the AtomicRefernce wrapper.

Note the cornerstone method AtomicReference.compareAndSet() works solely with addresses, in the comparison and the reseating. Much simpler and faster than equals(), esp. in a lockfree atomic context.

Q: Can we use AtomicReference to add thread safety without locking?

Suppose someone supplies a mutable Account class. We will construct an AtomicAccount class meeting these requirements all without locking —

– Req: List getStocks() to atomically return all the stock symbols held in the account. Without locking, it’s possible to see an invalid list undergoing simultaneous changes in 2 threads.
– Req: addInterest() and addFund(double). Without locking or atomic classes, you can lose updates.
– Req: getBalance()

% assumption: we have strict access control over the Account instance. No thread should use a naked Account reference to access its state.

A key design principle — “If RAW-POINTER wrapped in the AtomicReference is not _reseated_, then the pointee object state is intact.” In other words, account is mutable only by creating a new object. —

Achieved by wrapping Account instance in an ImmutableAccount instance. Change to Account results in a new ImmutableAccount wrapping a new Account. New ImmutableAccount then replaces pointer in the AtomicReference.

Now you realize an AtomicReference is a thread-safe lookup table with just one key-value pair. Key is the unnamed default key; value is an address. Salient features:
* compareAndSet in a loop, lockfree.
* immutables
* optimistic.
* layers of wrapper[1] to give the lockfree advantage

[1] In our example, 3 wrappers on Account ) ImmutableAccount ) AtomicReference ) AtomicAccount

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s