Concurrency

My Experience:

• Do not assume : user can crazily click UI and cause some nasty things. don't assume before/after...
• If there is wait, there should be notify() otherwise wait (unless time out) will be forever. Makesure notify() or notifyAll() be called - maybe in a finally{} block?
• Don't be stupid as me again - don't confuse lock mechanism and wait/notify mechanism:
  • wait / notify / notifyAll can only be called when the current thread has the lock
  • wait will release the lock when in wait, and get the lock before resume
  • if thread blocked to acquire a lock, when the lock becomes available, it does not need to be notified, but immediately becomes available to resume, although not be chosen (different than wait)
  • exit a synchronized block releases the lock, no need to notify

References: https://docs.oracle.com/javase/tutorial/essential/concurrency

Process vs Thread

• Process
  • isolated data (no direct access),
  • communicate via IPC mechanisms
  • resources (memory and CPU) allocated via OS
  • Java : most implements of JVM run as single process
  • Java: ProcessBuilder can create additional process
• Thread (lightweight process)
  • has own call stack
  • can access shared data and open files
  • has own memory cache (store read shared data)
  • Java: multi-threaded
    • java.util.concurrent provides improved support

Important Issues

• Limit of concurrency gain - consider performance gain
• Visibility issue (read something later changed by another, and not aware of the change)
• Access problem (several threads change same thing at same time)
  • interleave - even single statement can translate into multiple steps (VM)
• As effect of the above two:
  • Liveness -
    • Deadlock
    • Starvation and Livelock
      • starvation - thread unable to gain regular access to shared resources
      • livelock - threads busy responding to each other to resume work
  • Safety / data integrity failure

understanding of happens-before relationship

• a guarantee that memory writes by one specific statement are visible to another specific statement
• actions that create happens-before relationship
  • complete list: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility
  • in one thread (normal case)
  • Thread.start - every statement happens-before also happens-before every statement executed by the new thread (pass on)
  • Thread.join - statements executed by terminated thread happens-before statements following the successful join

Basic Mechanism

Thread objects

• To directly control creation and management, simply instantiate Thread
• To abstract thread management, use Executor (advanced)

Simple Thread creation /Management

• new Thread(Runnable runnable).start() // preferred, no need to subclass a Thread
  • new Thread(()->{}).start()
• subclass Thread (which has an empty run() method)
• static Thread.sleep throws InterruptedException - pauses the current thread
• By convention, any method that exits by throwing an InterruptedException clear interrupt status when it does so
• interrupt method:
  • sets the interrupt flag of a thread
  • for a thread to support interruption, it should
    • frequently invoke methods that throw InterruptedException
      • these methods are designed to cancel their operation and return immediately, if interrupted
    • or, call static Thread.interrupted() frequently
      • returns true if interruption has been received
      • clears the interrupt flag
      • good practice to throw InterceptionException so handling code can be centralized
    • non-static thread.isInterrupted
      • called by one thread to check another's status
      • does not clear the flag

Join

• t.join() where t is a thread
  • cause current thread to pause until t terminates or after a waiting period
  • like sleep, responds to interrupt

Lock & Synchronization

• synchronized (keyword)
  • define
    • a block of code, with a key : synchronized(object_as_key) {...} lock on the key
      • more fine grind to preserve liveness
      • use with care
    • a method (not constructor):
      • lock the object (not possible for two invocations of synchronized methods on the same object to interleave)
      • when synchronized method exits, it happens-before any subsequent invocation of a synchronized method for the same object
      • since constructor cannot be synchronized, do not leak (allow other thread access) the object otherwise other thread can access object before its construction
  • ensures
    • only one thread can execute the block at the same time
    • each thread entering the block sees the effects of all previous modifications that were guarded by the same lock
  • built on mechanism
    • intrinsic lock or monitor lock (or simply "monitor")
      • each object has an intrinsic lock associated with it (for synchronized method)
        • lock associated with the Class object is acquired when call synchronized static method
      • thread acquire lock -> own lock -> release lock (happens-before established)
        • re-entering
          • a thread can acquire a lock it already owns
        • release lock even return from synchronized block is caused by uncaught exception
  • problems
    • liveness

Volatile variable

• read/write - always atomic
• happens-before - any write happebns-before subsequent read (change to volatile variable immediately available to other threads)
  • read a volatile variable also see side-effects of other thread

Atomic Access

• read / write are atomic except for long and double
• read / write are atomic for all declared volatile variables (including long and double)
• even operation could be atomic, memory consistency error (happens-before) still possible

Guarded blocks

• guarded block can proceed AFTER a shared condition becomes true
• pooling (wrong)
  • wasteful
  • happens-before? (my guess)
• object.wait / object.notify / object.notifyAll
  • when a thread invoke d.wait, it must own the intrinsic lock of d, otherwise error is thrown
    • after success, the thread suspends and release the lock
  • only thread owning the obj's monitor can call it's wait() notify() notifyAll()
    • or IllegalMonitorStateException
  • to obtain obj's monitor
    • synchronized(obj) {
    • call synchronized method of the obj
    • call synchronized static method of a Class if the obj is a class
  • resume until another thread issues notification (though the thread may still need to check it's the event it's waiting for)
    • while (!joy) { try {wait();} catch (InterruptedException e){}}; .... now can do something after joy....
    • always invoke wait in a loop that tests for the condition - don't assume, don't expect the condition is still true
  • notifyAll does not immediately start other thread, just make them able to wake up
    • the woken thread can only resume after re-obtain the ownership of the lock
• usually synchronized
  • this is simple to obtain the lock for calling wait

     synchronized (obj) {

         while (<condition does not hold>)

             obj.wait();

         ... // Perform action appropriate to condition

     }

Immutable Objects

• state does not change after constructed - maximum reliance on immutable objects is widely accepted as sound strategy for simple and reliable code
• over-estimated overhead cost of creating new object (comparing to cost to protect mutable obj?)
• strategy for immutable objects
  • no setter
  • all fields final and private
  • no subclass to override methods - final class or private constructor (factory method)
  • do not allow referenced objects change
    • they are also immutable
    • no method to modify
    • don't share reference
    • ...

High Level Concurrency Objects (for massive concurrent applications)

Lock objects

• java.util.concurrent.locks package has more sophisticated locking mechanism
• Lock interface
  • like implicit, intrinsic lock (monitor):
    • can only be owned by one thread
    • supports the wait/notify mechanism through associated Condition objects
  • advantage over implicit locks
    • back out of an attempt to acquire a lock
      • tryLock method backs out if lock not available immediately or before a timeout
      • lockInterruptibly backs out if interrupted (vs. notified)

Executors

• separate thread management and creation from rest of application for large-scale applications
• interfaces
  • Executor interface
    • supports launching new tasks
    • execute(Runnable r)
      • less specific definition
      • depends on implementation
        • may creates a new thread and launches immediately (low level)
        • more likely to use an existing worker thread to run r, or place r in a queue to wait for a worker thread available
  • ExecutorService (extends Executor)
    • adds lifecycle management feature of the individual tasks and the executor itself
    • submit(Runnable / Callable r) method
      • accepts Runnable also Callable objects (Callable allow to return a value)
      • returns a Future object to retrieve the Callable return value and to manage the status of both Callable and Runnable
      • also provides method for submitting large amount of Callable objects
      • provides methods for shutdown of executor
        • tasks should handle interrupts properly
  • ScheduledExecutorService (extends ExecutorService)
    • supports future and/or periodic execution
      • schedule method
      • scheduleAtFixedRate
      • scheduleWithFixedDelay
• Thread Pools
  • most executor implementation use thread pools, contains
    • worker threads
      • exist separately with Runnable / Callable tasks
      • minimizes the overhead due to thread creation
        • significant amount of memory is used by Thread objects
        • large-scale allocating / deallocating has significant overhead
      • common type - fixed thread pool
        • Executors.newFixedThreadPool factory
        • specified number of threads running
        • if a thread is terminated somehow (exception?), a new one automatically replace
        • tasks are submitted to the pool via an internal queue (holds up tasks when more active tasks than threads)
      • benefit
        • degrade gracefully (wait longer but one get served, get served)
• Fork / Join
  • implementation of ExecutorService that help take advantage of multiple processors
  • for work that can be broken into smaller pieces recursively
  • work-stealing algorithm work with abstract class ForkJoinTask<V>
    • worker thread run out of things to do can steal tasks from other threads that are still busy
  • centre of framework is ForkJoinPool (extension of AbstractExecutorService) and execute ForkJoinTask
  • Basic use:

if (my portion of the work is small enough)

  do the work directly

else

  split my work into two pieces

  invoke the two pieces and wait for the results

wrap this code in a ForkJoinTask subclass (usually use one of more specific types, RecursiveTask / RecursiveAction)

After subclass is ready, create the object that represents all work to be done and pass to invoke() of a ForkJoinPool instance

• Concurrent Collections - deal with data consistency problems
  • BlockingQueue - first in first out, blocks when attempt to add to full queue, or retrieve from empty queue
  • ConcurrentMap / ConcurrentHashMap - defines atomic operations, remove/replace key/value pair only if key is present, or add key/value pair only is key is absent.
• Atomic Variables
  • java.util.concurrent.atomic : classes that support atomic operations on single variables.
    • all classes have get/set methods work like read/writes on volatile variables
      • means set happens-before subsequent get on same variable
    • atomic compareAndSet method also has these memory consistency features
    • so do the simple atomic arithmetic methods
  • example:
    • private AtomicInteger c = new AtomicInteger(0);
• ThreadLocalRandom
  • ThreadLocalRandom.current().nextInt(4, 77);
  • results in less contention and better performance