[concurrency-interest] Volatile happens before question

Raph Frank raphfrk at gmail.com
Wed Jan 18 19:40:35 EST 2012


Would this class work?

The principle is to add a getAndAdd(0x80000000) call instead of a
.get() for the tryReadLock method and then ignore the MSB for most
purposes.

The 2 lock method return an int which is passed to the matching unlock
method.  The static isLocked(int) method can be used to see if the
lock was successful.  It just checks if the sequence number is even.

readUnlock returns true if the lock wasn't write locked while the read
lock was being held.

Write locks follows the sequence of

sequence -> UNSTABLE -> (sequence + 2)

- MSB ignored
- even sequences are considered stable
- UNSTABLE = 1

public class OptimisticLock {

  private final int UNSTABLE = 1;

  private final AtomicInteger seq = new AtomicInteger(0);

  public final int tryReadLock() {
    return seq.get() & 0x7FFFFFFF;
  }

  public final boolean readUnlock(int seq) {
    return (this.seq.getandAdd(0x80000000) & 0x7FFFFFFF) == seq;
  }

  public final int tryWriteLock() {
    return seq.getAndSet(UNSTABLE) & 0x7FFFFFFF;
  }

  public final void writeUnlock(int seq) {
    seq.set(seq + 2);
  }

  public static public boolean isLocked(int seq) {
    return (seq & 0x00000001) == 0;
  }

}

The read-lock sequence is

R1) seq.get() (volatile R)
R2) read from non-volatile objects
R3) seq.getAndAdd() (volatile R/W)

The write-lock sequence is thus

W1) seq.getAndSet() -> volatile(R/W)
W2) write to non-volatile objects
W3) seq.set -> volatile(W)

Steps 1 and 3 for both are "synchronization actions", and so are ordered.

R1 -> check if stable (R)
R3 -> check is changed (R/W)

W1 -> check if write lock (R/W)
W3 -> sets counter to stable (W)

There are 6 possible sync sequences:

R1 -> R3 -> W1 -> W3

W1 is a read and R3 is a write, so R2 happens before W2, so read success

R1 -> W1 -> R3 -> W3

R3 is a read and W1 is a write, so R3 happens after W1, so the read
unlock will fail

R1 -> W1 -> W3 -> R3

R3 is a read and W3 is a write, so R3 happens after W3, so the read
unlock will fail

W1 -> W3 -> R1 -> R3

R1 is a read and W3 is a write, so W2 happens before R2, so read success

W1 -> R1 -> W3 -> R3

R1 is a read and W1 is a write, so W1 happens before R1, so the read
lock will fail (R3 won't happen)

W1 -> R1 -> R3 -> W3

R1 is a read and W1 is a write, so W1 happens before R1, so the read
lock will fail (R3 won't happen)


More information about the Concurrency-interest mailing list