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

1
votes

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.

1
javamultithreadingatomiclock-freecompare-and-swap
Do you actually have a performance problem which prompts you to try and find a lock free algorithm? Those are very hard to get right. There are plenty of solutions otherwise (semaphores, latches, conditions etc) – fge
@fge in my current approach I use composition of locks and semaphores, it works exactly correct and pretty fast. But I cannot judge what performs better having only one lock-based implementation: nothing to compare with! Lock-free is not easy, right. I hesitate to post easy questions in SO. – Alex Salauyou
There are basically three ways to perform a synchronous update of multiple values: 1) Use a lock, 2) use a "safe sequence" (very difficult to get right, assuming there even is a solution), 3) use some sort of machine facility (such as disabling the dispatcher). But note that there are many forms of "locks" -- counters, semaphores, OS-defined locks, et al. – Hot Licks

1 Answers

1
votes

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