Monday, September 16, 2013

Atomicity and mutual exclusion

1What is "atomic"?¶

Essentially, it varies by context, but still, some things are expected to be same anywhere.

For exemple, y = 1 is atomic in most cases, e.g. if the expression deals with a 32-bit value on a 32-bit architecture.

However, if the value is larger than the natural word size of the architecture, a simple assignment is expected not to be atomic, e.g. long long x on a 32-bit machine, as it is a 64-bit variable.

Usually, the machine will deal with assignments in such cases by splitting them in parts i.e.upper and lower in our previous exemple. This incurs some concurrency issues. For exemple, say two threads want to execute x = 0 and x = -1, respectively:

This may yield the following results: 0000000000000000, 00000000FFFFFFFF, FFFFFFFF00000000 or FFFFFFFFFFFFFFFF.

In Java and C, assignment (of natural word size) will be atomic. For exemple, in the statement x = y + 3, y + 3 may not be atomic, but the assignment itself (giving a value to x) will be.

Nb: Assignment to a long in Java is not necessarily atomic (except when using a 64-bit JVM on a 64-architecture), unless you declare volatile. This keyword will be explored more in depth later in the course.

1.1Appearing atomic¶

Consider the statement x = y where the value must be loaded in a register, then assigned to x, thus being, formally, not atomic.

However, if the RHS is not being altered by another thread, it can "appear" atomic.

Formally:

Consider the statement x = e where e is an expression.

e has a critical reference if e uses a variable some other threads may change or write.

x = e satisfies an "at-most-one" property if either of two properties hold:

1. e has at most 1 critical reference and x is not used by another thread.
2. e has no critical reference ( x may be read by another thread.)

Exemple 1: Let x = y = 0;, the thread T₀ execute x = y + 1; and the thread T₁ execute y = y + 1;. Are any of those last two statements at-most-one?

1. x is not read in the other thread, so it is allowed to have 1 critical reference. Yes, it is at-most-one.
2. y is read in the other thread, but this thread is the only one to alter y. Yes, it is at-most-one.

We thus have those two scenarios:

You could look at the machine code instructions, but those two scenarios are still the only two possibilities.

Example 2: Let x = y = 0; again, the thread T₀ execute x = y + 1; and thread T₁ execute y = x + 1; Are any of those last two statements at-most-one?

1. No. The LHS is a critical reference in T₁.
2. No, for the same reason.

Let's look at the different scenarios at the level of single instructions:

At the machine code level, however, things are different (remember that each thread has its own registers, either through context switching, with each CPU physically having its own set, or both):

Any of those 6 instructions could be executed in different orders. As such, for $n$ threads that do $m$ atomic operations, there are

$$ \frac{(nm)!}{m!^{n}} \text{ possible interleavings}$$

In our case, $n = 2$ and $m = 3$. This gives us $20$ different scenarios.

2Mutual-exclusion¶

This is when we make sure that only 1 thread at a time can execute some code, called the critical section.

|----------| enter protocol
 |        |
 |        |  critical section (mut. ex)
 |  code  |
 |        |
 |        |
|----------| exit protocol

2.1Ways to achieve mutual exclusion¶

There is more than one way to achieve mutual exclusion. Say we have 2 threads, each with their own thread ID (0 and 1, in our case) and they can access it (through the id variable).

No matter the method, a common protocol has to be followed:

1. Init: Which happens only once, before anything else
2. Enter: In which a thread must wait before entering the critical section
3. Exit: In which the thread has finished, and may allow another thread to enter the critical section

2.1.1First way¶

• Works.

However,

• It is over-constrained.
• There is a strict alternation that requires T₀ to be the first to execute. T0 -> T1 -> T0 -> T1 works. Doesn't work: T0 -> T0 -> T1 -> ...

2.1.2Second way¶

Trying to improve on the first way...

Does this work?
No. They could both do the check at the same time and both enter.

2.1.3Third way¶

Trying to fix the second way...
Key: signal the intention of going into c.s., rather than going in directly.

Does this work?
Sort of

If those instruction happen as follows: T₀.0; T₁.0; T₀.1; T₁.1 (Z-pattern), then neither threads gets in the critical section. So:

• Enforces m.t.
• May deadlock (actually, livelock, because they're still doing work...)

2.1.4Fourth way¶

Trying to fix the third way.

This somewhat works, if delay is not identical. Otherwise both threads might wait the same amount of time and cause the previous problem.

2.1.5Fifth way: Dekkers' algorithm¶

Either I slept through this whole section, or the prof told us to look it up ourselves.

2.1.6Sixth way: Peterson 2-processes tie breaker¶

2.1.7Kessel's single writes alg¶

• "Split up" turn.

also add load[0], load[1]

T0 only writes to flag[0], turn[0], load[0]. Single writer solution (a single-writer register is a register that can be written by a single process only).

2.2Nb: Performance and patterns¶

[TODO: Decipher, image]

What we are looking for:

1. Mutual exclusion
2. Absence of deadlock
3. No unnecessary delay
4. Eventual entry (starvation-free)

1, 2 and 3 concern safety whereas 4 concerns liveness.