java12-fundamentals-nonblocking-stack-workshop

Reference

preface

it may be worth to take a look here first: https://github.com/mtumilowicz/java-concurrency-compare-and-swap
the main goal of this workshops is to introduce compare-and-swap and show how it could be used in practice
(by implementing non-blocking and concurrent stack)
answers with correctly implemented workshop tasks are in answers package

introduction

exclusive locking (synchronized keyword) is a pessimistic technique
- it asks you to first guarantee that no other thread will interfere
the optimistic approach
- you proceed with an update, being hopeful that you can complete it without interference
- it relies on collision detection to determine if there has been interference
  from other parties during the update, in which case the operation fails and
  can be retried (or not)
- “it is easier to obtain forgiveness than permission”
nearly every modern processor has some form of atomic read-modify-write instruction,
- compare-and-swap
- load-linked/store-conditional
CAS has three operands
- MEM: a memory location on which to operate
- OLD: the expected old value,
- NEW: the new value
- CAS atomically updates MEM to NEW, but only if the value in MEM matches OLD
  - otherwise it does nothing
  - the variant called compare-and-set instead returns whether the operation
    succeeded
The typical pattern for using CAS is
1. read the value OLD from MEM,
2. derive the new value NEW from OLD,
3. and then use CAS to atomically change MEM from OLD to NEW
  - provided no other thread has changed OLD to another value in the meantime
CAS is an optimistic technique
- it proceeds with the update in the hope of success
- can detect failure if another thread has updated the variable since it was last examined
when multiple threads attempt to update the same variable simultaneously
using CAS - only one wins
- but the losers are not punished by suspension (contrary to failure when acquiring a lock)
  - they can simply try again
  - because a thread that loses a CAS is not blocked, it can decide
    whether it wants to try again, take some other recovery action, or do nothing
    - doing nothing may be a perfectly sensible - a failed CAS means that someone else already did the
      work you were planning to do

ABA problem

https://en.wikipedia.org/wiki/ABA_problem

summary

the language syntax for locking may be compact, but the work done by the
JVM and OS to manage locks is not
- locking entails traversing a relatively complicated code path in the
  JVM and may entail OS-level locking, thread suspension, and context switches
- in the best case, locking requires at least one CAS (using locks moves the
  CAS out of sight)
java’s traditional synchronization mechanism (synchronized keyword)
impacts hardware utilization and scalability:
- multiple threads constantly competing for a lock =
  frequent context switching (can take many processor cycles)
- when a thread holding a lock is delayed (e.g., because of a scheduling delay),
  no thread that requires that lock makes any progress
executing a CAS from within the program involves no JVM code,
system calls, or scheduling activity
the primary disadvantage of CAS is that it forces the caller to deal with contention
(by retrying, backing off, or giving up)
- locks deal with contention automatically by blocking until the lock is available
in Java 5.0, low-level support was added to expose CAS operations on int, long,
and object references, and the JVM compiles these into the most efficient means
provided by the underlying hardware
- the runtime inlines them into the appropriate machine instructions
- if a CAS-like instruction is not available the JVM uses a spin lock

digression

note that before java 8, to perform some function on atomic value (for example - double it)
we have to use compareAndSet in an do-while loop

int prev;
do {
    prev = atom.get();
} while (!atom.compareAndSet(prev, prev * 2));

now, we have dedicated methods in atomic classes: updateAndGet and accumulateAndGet