Search code examples
javamultithreadingatomiclock-freecompare-and-swap

How to update 2 objects atomically in a lock-free manner?

I'm working on class that implements hash-code based atomic locking by multiple objects. The main purpose is to unpark a waiter thread as soon as all required locks become available, thus reducing overall waiting time.

Its lockAndGet(List objects) returns a single "composite lock" that involves all listed objects. After the caller finishes his job, it calls unlock().

The main components are: 1) common lock table--int[] array showing which locks are held now; 2) deque of waiter threads.

Algorithm is quite simple:

  1. When a thread calls lockAndGet(), it is marked for parking, then new waiter object with the state LOCKED containing this thread is created and added to the tail of the queue, after which makeRound() method is invoked;
  2. makeRound() traverses the deque starting from the head, trying to find which waiters can acquire their locks. When one such waiter is found, lock table is updated, waiter state is changed to UNLOCKED and removed from the deque, waiter's thread is unparked. After traversal, if current thread is marked for parking, it is parked;
  3. When unlock() is called on some composite lock, lock table state is updated and makeRound() is invoked.

Here, to avoid race conditions, update of the state of lock table must be performed atomically with update of the state of a waiter. Now, it is achieved by synchronization on common exclusive Lock, and it works well, but I'd like to implement similar mechanism in free-lock manner using CAS operations, making waiter queue lock-free. It is pretty simple for step 1, but problematic for step 2.

Since DCAS isn't supported by Java, does anyone know how can be achieved update of the queue node (change of waiter's state and mark for deletion) atomically with update of other object (lock table), using only CAS? I don't ask for code, just some hints or approaches that could help.

Solution

  • You can try to implement a multi-word CAS using the available CAS, however this is dependent on how much of a performance hit you are willing to take in order to achieve this.

    You can look at Harris' http://www.cl.cam.ac.uk/research/srg/netos/papers/2002-casn.pdf