Short learning curve for multi threading Terminology, Concepts
Concurrency vs. Parallelism
Concurrency and parallelism are related concepts, but there are small differences. Concurrency
means that two or more tasks are making progress even though they might not be executing
simultaneously. This can for example be realized with time slicing where parts of tasks are executed
sequentially and mixed with parts of other tasks. Parallelism on the other hand arise when the
execution can be truly simultaneous.
Asynchronous vs. Synchronous
A method call is considered synchronous if the caller cannot make progress until the method returns
a value or throws an exception. On the other hand, an asynchronous call allows the caller to
progress after a finite number of steps, and the completion of the method may be signalled via some
additional mechanism (it might be a registered callback, a Future, or a message).
- Actors are asynchronous by nature: an actor can progress after a message send without waiting for
the actual delivery to happen.
Non-blocking vs. Blocking
We talk about blocking if the delay of one thread can indefinitely delay some of the other threads. A
good example is a resource which can be used exclusively by one thread using mutual exclusion.
Deadlock vs. Starvation vs. Live-lock
Deadlock arises when several participants are waiting on each other to reach a specific state to be
able to progress. In the case of deadlock, no participants can make progress, while in contrast
Starvation happens, when there are participants that can make progress, but there might be one or
more that cannot. Typical scenario is the case of a naive scheduling algorithm that always selects
high-priority tasks over low-priority ones. Livelock is similar to deadlock as none of the
participants make progress. The difference though is that instead of being frozen in a state of
waiting for others to progress, the participants continuously change their state. An example scenario
when two participants have two identical resources available. In the unfortunate case it might
happen that the two participants bounce between the two resources, never acquiring it, but always
yielding to the other.
Race Condition
We call it a Race condition when an assumption about the ordering of a set of events might be
violated by external non-deterministic effects. Race conditions often arise when multiple threads
have a shared mutable state, and the operations of thread on the state might be interleaved causing
unexpected behavior. While this is a common case, shared state is not necessary to have race
conditions. One example could be a client sending unordered packets (e.g UDP datagrams) P1, P2
to a server. As the packets might potentially travel via different network routes, it is possible that the
server receives P2 first and P1 afterwards. If the messages contain no information about their
sending order it is impossible to determine by the server that they were sent in a different order.
Depending on the meaning of the packets this can cause race conditions.
NOTE: The only guarantee that Akka provides about messages sent between a given pair of actors
is that their order is always preserved.
Non-blocking Guarantees (Progress Conditions)
Wait-freedom
A method is wait-free if every call is guaranteed to finish in a finite number of steps. If a method is
bounded wait-free then the number of steps has a finite upper bound. From this definition it follows
that wait-free methods are never blocking, therefore deadlock can not happen. Additionally, as each
participant can progress after a finite number of steps (when the call finishes), wait-free methods are
free of starvation.
Lock-freedom
Lock-freedom is a weaker property than wait-freedom. In the case of lock-free calls, infinitely often
some method finishes in a finite number of steps. This definition implies that no deadlock is
possible for lock-free calls. On the other hand, the guarantee that some call finishes in a finite
number of steps is not enough to guarantee that all of them eventually finish. In other words, lockfreedom is not enough to guarantee the lack of starvation.
Obstruction-freedom
Obstruction-freedom is the weakest non-blocking guarantee discussed here. A method is called
obstruction-free if there is a point in time after which it executes in isolation (other threads make no
steps, e.g.: become suspended), it finishes in a bounded number of steps. All lock-free objects are
obstruction-free, but the opposite is generally not true.
The Java Memory Model
Prior to Java 5, the Java Memory Model (JMM) was ill defined. It was possible to get all kinds of
strange results when shared memory was accessed by multiple threads, such as:
a thread not seeing values written by other threads: a visibility problem
a thread observing impossible behavior of other threads, caused by instructions not being
executed in the order expected: an instruction reordering problem.
With the implementation of JSR 133 in Java 5, a lot of these issues have been resolved. The JMM is
a set of rules based on the happens-before relation, which constrain when one memory access
must happen before another, and conversely, when they are allowed to happen out of order. Two
examples of these rules are:
The monitor lock rule: a release of a lock happens before every subsequent acquire of the same
lock.
The volatile variable rule: a write of a volatile variable happens before every subsequent read of
the same volatile variable
Although the JMM can seem complicated, the specification tries to find a balance between ease of
use and the ability to write performant and scalable concurrent data structures.
Recommended literature
The Art of Multiprocessor Programming, M. Herlihy and N Shavit, 2008. ISBN 978-0123705914
Java Concurrency in Practice, B. Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Holmes and D. Lea,
2006. ISBN 978-0321349606