Java Language Spec

Chapter 17: Threads and Locks

Preface

  • memory model defines behaviors that are allowed
    • JVMs are free to optimize (as long as they only generates allowed behavior)

17.1 Synchronization

  • 'most basic' synchronization mechism
  • implemented with monitor
  • monitor:
    • exists in each Java object
    • reentrant
    • only belongs to 1 thread at any time
  • synchronized

    • try to lock on the monitor before run
    • automatically unlocks when (return OR throw)
    • no non-blocking try or timeout
  • JVM is NOT obliged to detect OR prevent deadlock

17.2 Wait Sets and Notification

  • Wait Set: a set of threads that are waiting "on" the monitor of one object
  • only affacted by Object.wait() / Object#notify / Object#notifyAll

17.2.1 Object#wait

if

  • caller thread (currentThread) MUST have locked the monitor
  • currentThread MUST NOT be interrupted

then

  • unlock the monitor
  • add currentThread to wait set
  • block currentThread until it gets removed from wait set
    • removal may happen if:
      • currentThread gets interrupted
      • notify() called
      • notifyAll() called
      • timed wait && timeout
  • lock the monitor again
  • (if block ended due to interruption) `wait() throws InterruptedException

17.2.2 Object#notify() / Object#notifyAll()

  • currentThread must have locked the monitor
  • remove 1 or all threads from wait set
    • in case of notifyAll, ONLY 1 thread would be able to lock again
  • NOTE: this DOES NOT unlock the monitor (so NO thread removed from Wait Set can succeed until currentThread unlocks)

17.2.3 Interruptions

17.2.4 Interactions of waits / notifation / interruption

17.3 Sleep and Yield

Thread.sleep() / Thread.yield()

  • sleep DOES NOT lose ownership of monitors
  • NEITHER Thread.sleep NOR have synchronization semantics

17.4 Memory Model

"possible behaviors of a program"

  • whether an execution trace (instructions?) is a legal execution of the program (code?)
  • "legal" := each read MUST observe some write that is valid according to certain rules

  • intra-thread semantics

    • semantics for single-threaded programs

17.4.1 Shared Variables

  • "shared variable": instance fields / static fields / array elements
    • in contrast to single-threaded : local variables / method params / execution handler params
  • "conflicting": two accesses to the same variable if at least 1 of them is write

17.4.2 Actions

inter-thread action or simply "action": an action that can be detected or directly-influenced by another thread

intra-thread actions do not concern us: all threads need to obey intra-thread semantics

possible (inter-thread) actions:

  • non-volatile read
  • non-volatile write
  • synchronized actions
    • volatile read
    • volatile write
    • lock of monitor
    • unlock of monitor
    • first and last action of a thread
    • actions that start a thread, or detect termination of a thread
  • "external" action
    • an action that may be observable outside of an execution (side effect ?), and have a result based on an environment external to the execution (RealWorld ?)
  • thread divergence action, or "dead loop"

17.4.3 Programs and Program Order

(program order of thread t): a total order that obeys intra-thread semantics of t

a set of actions is sequentially consistent if

  • the actions occur in a total order "execution order that is consistent with program order
  • AND each read r of variable v sees (last write to v in execution order)

"sequential consistency" as a language model prohibits many compiler optimizations

17.4.4 Synchronization order

a synchronization order is a total order over all the synchronization actions of an execution.

For each thread t, the synchronization order of synchronization actions in t is consistent with the program order of t.

Synchronization actions induce synchronized-with relation relation of actions:

  • unlock synchronized-with all subsequent lock
  • a volatile write synchronized-with all subsequent volatile read
  • starting a thread synchronized-with first action in that thread
  • final action of a thread T synchronized-with actions of thread T2, if T2 dectes T has terminatedd
  • interruption of thread blah blah
  • write of default value synchronized-with first action in every thread
    • "conceptually every object is created at start of program"

17.4.5 Happens-before order

2 actions can be ordered by a happens-before relationship

If x happens before y, then: x is visible to y AND is ordered before y

x happens before y if:

  • x and y are actions of the same thread, and x comes before y in program order
  • OR: x is (end of constructor) and y is (start of finalizer)
  • OR: x synchronized-with y
  • OR: x happens-before some z, and z happens-before y (i.e. happens-before is a transitive relation)

NOTE: happens-before does not require certain order in execution (implementation may reorder as long as all observations obeys happens-before)

happens-before relation defines data races: if 2 conflicting accesses are not ordered by a happens-before relationship, the program is said to contain a data race.

a program is correctly synchronized IFF all sequentially consistent executions are free of data races.

if a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent

read r of varable v is allowed to observe a write w if

happens-before consistency: