Leaky Abstractions

• Each abstraction level obscures implementation details
• Things that happen on lower levels affect high-level behavior
• Some phenomena cannot be explained using high-level terms
• In other words, abstractions leak

Just Another Brick In The Wall

• Accessing RAM can take hundreds of nanoseconds
• Basic instructions are several orders of magnitude faster
• Don't want to stall the CPU much
• Better keep the most frequently used data at hand

Moore's Law

The number of transistors incorporated in a chip will approximately double every 24 months

One Does Not Simply Increase Clock Rate

• Smaller transistors ⇒ more resistance ⇒ smaller frequency
• Less power consumption ⇒ smaller frequency
• We still want the performance to double
• Have "spare" transistors

Parallelize And Conquer

• We can execute more programs concurrently
• Problems can be split into parallelly-executed parts
• But these parts may have some shared state

Cache Coherency

How would processor A know that processor B had modified some value, if A had cached it some time ago?

Cache Coherency Protocols

• The processors must maintain a consistent view of the world
• Always using main memory would ruin performance
• The processors need to communicate with each other
• Various communication protocols are possible

MESI (Just An Example, Mind You)

Each cache entry can have one of the following states:

• Invalid: this cache does not contain the entry
• Exclusive: the entry resides in this cache only
• Modified: this processor has modified the entry
• Shared: more than one cache contains the entry

Store Buffers

• When one processor wants to write something, it tells the other processors to invalidate their copy of it
• But it may take a while to receive all the acknowledgements
• So, the processor buffers the write, and goes on executing stuff
• Only when all the acknowledgements arrive, the write finally gets executed

Invalidate Queues

• Executing an invalidation can take time
• The work of the process executing it will be disrupted
• The processor waiting for acknowledgement will be stalled
• So, the acknowledgements are sent immediately
• The invalidations are queued, to be executed when convenient
• No messages on that cache entry are sent before that moment

Hardware Memory Model

• Hardware engineers cannot know in advance when optimizations could break stuff and when they won't
• Software engineers know how their code should behave
• They need the ability to influence hardware optimizations

Store Memory Barriers In MESI

• Some stores S1 were placed to the Store Buffer
• A Store Memory Barrier was issued
• More stores S2 were executed
•  
• All the stores from S1 will be committed before any store from S2

Load Memory Barriers In MESI

• Some invalidation requests I were placed to the Invalidate Queue
• A Load Memory Barrier was issued
• Some operations OPS come next in the program order
•  
• All the invalidations from I will be executed before
  any operation from OPS

Must Construct Additional Abstractions

• There are many different protocols besides MESI
• Many other things can result in Out Of Order Execution
• Some may have no notion of a Store Buffer or Invalidate queue
• Need to be able to reason about them in general
• The concept of a Load or a Store still remains

For X, Y in [Store, Load]:

For Instance

• Suppose some stores S1 were executed
• A StoreStore memory barrier was issued
• Some more stores S2 follow
•  
• All the stores in S1 will complete before any store in S2 starts
• (Incidentally, this is the Store Memory Barrier in MESI)

Acquire And Release Semantics

• All the memory operations:

  • preceding a release must complete before it starts
  • following an acquire can't start before it completes

If All You Have Is This Presentation

The live demo consisted of the following stuff:

• A demonstration of how things really fail w/o deliberate effort
• Digging through OpenJDK and seeing how volatiles are handled
• Removing the special handling of volatiles from OpenJDK

To catch on, you might want to check out:

• Some video recording of the live demo
• http://gvsmirnov.ru/blog/tech/2014/02/10/jmm-under-the-hood.html

Mere Visibility Is Often Not Enough

class Foo {
    volatile int a;
    //...
    void bar() {
        a++;
    }
}

0: aload_0
1: dup
2: getfield
5: iconst_1
   ← Some other thread
6: iadd
7: putfield
10: return

Mere AtomicStuff Is Not Enough Either

public void execute(Action action, long userId) {
    this.lastResult = action.execute();
    // Please don't observe me here!
    this.lastUserId = userId;
    // Also here, please-please
    this.lastAction = action;
}

Mutual Exclusion

• No two threads are in the same critical section simultaneously
• A lock can be used to enforce it
  • Can be acquired (locked)
  • And released (unlocked)

Synchronization

• Some thread may want to wait for some other thread
• Condition Variables are used to achieve this
  • A condition variable allows to wait for an event
  • And notify a waiting thread of an event happening
• Don't want to burn CPU cycles needlessly when waiting
• Therefore, threads may be parked by the OS

Monitor = Lock + Condition Variable

Can be in one of the following states:

• Thin: has no contention on it, atomics are used to acquire it
• Inflated: threads are parked when waiting for acquisition
• Biased: can be cheaply acquired by one thread, but it is expensive when multiple threads are trying to acquire it

If All You Have Is This Presentation

The live demo consisted of the following stuff:

• A demonstration of how AtomicInteger works
• Synchronized blocks implementation, also j.u.c.locks.*
• wait/notify blocks and CountDownLatch

To catch on, you might want to check out:

• Some video recording of the live demo
• An upcoming entry in my blog, stay tuned!