Java Concurrency: Under The Hood

#volatile #membar #dragons #openjdk #mesi

#jmm #store #load #omg #internals

#cachecoherency

#jugru

Gleb Smirnov

me@gvsmirnov.ru

Leaky Abstractions

Just Another Brick In The Wall

Yay Caches!

Moore's Law

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

— Gordon Earle Moore, 1964

One Does Not Simply Increase Clock Rate

Yay Multi-Core!

Parallelize And Conquer

Cache Coherency

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

— A Dangerously Curious Dude

Cache Coherency Protocols

MESI (Just An Example, Mind You)

Each cache entry can have one of the following states:

Store Buffers

void executedOnCpu0() {
    value = 10;
    finished = true;
}
void executedOnCpu1() {
    while(!finished);
    assert value == 10;
}

What could possibly go wrong?

finished: Exclusive
value: Invalid
finished: Invalid
value: Exclusive
while(!finished);
← read(finished)
value = 10;
- store_buffer(value)
← invalidate(value)
finished = true;
- finished: Modified

→ read(finished)
← read_response(finished, true)
- finished: Shared
→ read_response(finished, true)
- finished: Shared (true)
assert value == 10;

Assertion fails

→ invalidate(value)
- value: Invalid
← invalidate_ack(value)

Invalidate Queues

void executedOnCpu0() {
    value = 10;
    finished = true;
}
void executedOnCpu1() {
    while(!finished);
    assert value == 10;
}

What else could go wrong?

finished: Exclusive
value: Shared
finished: Invalid
value: Shared
while(!finished);
← read(finished)
value = 10;
- store_buffer(value)
← invalidate(value)
finished = true;
- finished: Modified
→ invalidate(value)
← invalidate_ack(value)
- invalidate_queue(value)
→ read(finished)
← read_response(finished, true)
- finished: Shared
→ read_response(finished, true)
- finished: Shared (true)
assert value == 10;

Assertion fails

- value: Invalid

Hardware Memory Model

Store Memory Barriers In MESI

Load Memory Barriers In MESI

void executedOnCpu0() {
    value = 10;
    Magic.storeMemoryBarrier();
    finished = true;
}
void executedOnCpu1() {
    while(!finished);
    Magic.loadMemoryBarrier();
    assert value == 10;
}

Everyone loves magic (and unicorns)!

finished: Exclusive
value: Shared
finished: Invalid
value: Shared
while(!finished);
← read(finished)
value = 10;
- store_buffer(value)
← invalidate(value)

Magic.storeMemoryBarrier();
→ invalidate(value)
← invalidate_ack(value)
- invalidate_queue(value)
→ invalidate_ack(value)
- writeback(value, 10)
- value: Exclusive

finished = true;
- finished: Modified

→ read(finished)
← read_response(finished, true)
- finished: Shared
→ read_response(finished, true)
- finished: Shared (true)

Magic.loadMemoryBarrier();

- value: Invalid

assert value == 10;
← read(value)
→ read(value)
← read_response(value, 10)
- value: Shared
→ read_response(value, 10)
- value: Shared (10)

Assertion passes

Must Construct Additional Abstractions

For X, Y in [Store, Load]:

All the X operations that precede an XY barrier will complete

before

Any Y operation that succeeds the XY barrier starts

For Instance

Acquire And Release Semantics

Write Once

Run Anywhere

LIVE DEMO TIME!

If All You Have Is This Presentation

The live demo consisted of the following stuff:

To catch on, you might want to check out:

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

Yay AtomicStuff

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; }

That's a Critical Section!

Mutual Exclusion

Synchronization

Monitor = Lock + Condition Variable

Can be in one of the following states:

If All You Have Is This Presentation

The live demo consisted of the following stuff:

To catch on, you might want to check out: