compare-and-swap

compare-and-swap (CAS) addresses the problem of implementing atomic read-modify-write sequence without locking.

volatile are lighter synchronization because it doesn’t involve context switches or thread scheduling. volatile have limitation compare to locking–

They can not be used to construct compound atomic actions, i.e. when one variable is dependent on another or when variable needs to know its current value to update its value. Increment operation ++i is 3 distinct operations and therefore can not be used with volatile variables

  1. Fetch the current value of the variable
  2. add one on it
  3. then write and update value back

In order to not lose an update, the entire read-modify-write operation must be atomic.

When locks are held so briefly, being put to sleep is harsh penalty for asking for the lock at wrong time.

Disadvantage of Locking

Lock Protocol Whichever thread holds the lock guarding a set of variables has exclusive access to those variables, and that the changes made to those variables are visible to other threads that subsequently acquire the lock.

Modern VM can optimize uncontended lock acquisition and release fairly efficiently. But multiple thread request the lock at the same time the JVM needs help from Operating System.

In case of thread contention on same lock, only one thread will win and rest will be suspended and resume later. But suspension is heavy penalty for lock contention, because in order to resume, it may have to wait for other threads to finish their scheduling quota before it is actually scheduled.

How JVM knows its time to wake up (resume) a thread that was put to sleep because it asked for lock at wrong time. I don’t know, may be when it wake up by OS it check for lock and if it can’t get it goes to sleep again.

Sometime JVM can use profiling data to decide how long a lock has been held in previous run and if that time is short enough JVM will keep spining thread rather then suspending (put to sleep) it.

CAS

compare-and-swap (CAS) addresses the problem of implementing atomic read-modify-write sequence without locking.

CAS

  1. Operands: a memory location V on which to operate, expected old value A , new value B
  2. Operation: update V to the new value B, only if the value in V matches the expected old value V otherwise do nothing.
  3. Return: the value currently in V or a boolean flag, true if value was updated.

All this happen in one atomic-operation.

When multiple threads attempt to update the same variable simultaneously using CAS, one wins and update the variable value, and rest lose. But there is no synchronization so losers are not punished by thread suspension, usually code that tries to update the variable has logic to deal with failure, by (1) retrying until success, or (2) do nothing because what this thread wanted to do some other thread has done it.

CAS support in Java

In java 5.0, low-level support was added to expose CAS operation on int, long and Object reference, and JVM compiles these into the most efficient means provided by the underlying hardware.

On the platform supporting CAS, the runtime inlines them into appropriate machine instruction(s), in the worst case, if a CAS-like instruction is not available the JVM uses a spin lock.

The low-level JVM support is used by the atomic variables classes to provide an efficient CAS operation on numeric and reference type.

Atomic Variables

Atomic variables limit the scope of contention to single variable. The fast (uncontented) path for updating an atomic variable is no slower than the fast path for acquiring lock because it does not involve suspending and rescheduling threads. Atomic arrays classes are array of whose elements can be updated atomically. A volatile array has volatile semantic only for the array reference, not to its element.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s