Introduction
This post is mostly a copy - bar formatting - of an answer I gave to a question on [a]synchronous programming by my niece. The question was,
Is asynchronous programming tied to concurrency? Are they related concepts? How do they differ?
Synchrony
In colloquial programming usage, a synchronous operation typically blocks until it completes (waits for completion). An asynchronous operation typically does not block, and the initiator can discover its completion at a later point in time, by some other mechanism(s).
In computer science theory, however, the usage of the terms is different. The terms are most useful in distributed systems, where a completely asynchronous model is one where there is no concept of time. Messages are eventually delivered, and processes eventually respond, but no statement is made on how long that could take. See Lamport and Lynch’s “Chapter on Distributed Computing”, 1989. In contrast, the concept of time may be introduced by making some statement on how long message transmission takes, for example by introducing upper bounds on propagation / processing delays. An algorithm can take advantage of those statements to improve on its time or message complexity, or make useful trade-offs between the two.
A common misconception is that synchronous/asynchronous execution implies blocking/non-blocking
operation, but this is not the case. Blocking operations can be asynchronous, and not every
non-blocking operation is asynchronous. For instance, a send operation which blocks until the
receiver has acknowledged the message is blocking but not synchronous, since the acknowledgement may
never come. Additionally, a receive operation can be non-blocking and synchronous: in Xinu,
recvclr immediately returns with a message if it is available, otherwise returns a value
indicating there are no messages (similar to a combined poll and recv, in POSIX terms).
Blocking / non-blocking behaviour characterises an operation. The characterisation synchronous / asynchronous applies to a system as a whole. For a useful introductory application of a synchronous model in a real-world setting see Magee’s “Analyzing Synchronous Distributed Algorithms”.
What about concurrency?
Informally, concurrent execution means that tasks are executed in an arbitrary, possibly interleaved order. The tasks are not executed simultaneously. In contrast, parallel execution means that the tasks are executed simultaneously by multiple threads of execution - in concurrent execution there may be only a single thread of execution interleaving task operations. A system may employ both parallelism and concurrency - this is the case with modern multiprocessor systems.
From the above description, we characterised synchronous/asynchronous as descriptions of a system, part of its design, or contract. On the other hand, concurrency / parallelism are properties of an execution environment. So the concept of [a]synchronous systems is orthogonal to concurrent or parallel execution, which if we wanted to describe in other terms, we would say:
- Parallel is the opposite of serial
- Concurrent is the opposite of sequential
[see Patterson & Hennessy (2013), Computer Organization and Design: The Hardware/Software Interface]
Oh no. What is this serial and sequential stuff?
Let’s get formal
To explain the difference between the terms serial and sequential, we’ll have to take a look into consistency models. Before we do, let’s read Leslie Lamport’s paper Time, Clocks, and the Ordering of Events in a Distributed System. Lamport defines concurrency between events: two events in the same process are concurrent if neither can causally affect the other. A process is previously defined as a set of events, with an a priori total ordering between them.
With that definition in mind, it’s easy to see that if all events in a process are causally ordered - the paper defines it in terms of the “happens-before” order - there is no room for concurrency. Instead, the events form a sequence, where every “a” occurs before “b”.
In the context of the paper, what is needed is to evaluate the correctness of an execution schedule/history
In a system with some rules that relate to its operations and its state, the history of operations in the system should always follow that set of rules. When that happens, we call this set of rules a consistency model; a model of how the system should behave, as a definition of correctness. The consistency model could be as simple as “There are no rules at all; any and all operations are permitted”; every system obeys this trivially. In a more formal way, we could say a consistency model is the set of allowed (execution) histories of operations.
There are some very useful consistency models:
- linearisability
- sequential consistency
- serialisability
Linearisability
There are some bounds in the order of events. We can’t send messages back in time, so an operation cannot take effect before its invocation, and no operation may take effect after its completion. A global observer can thus place the time the effects of all operations taking place in a time series and obtain a nice linear order. We call this consistency model linearisability. Linearisability is a pretty simple and powerful model, but is very lax. Put some stronger assumptions in place, we’ll get better guarantees.
Sequential consistency
We can allow for more histories that mirror our every day activities. Let’s say I post multiple messages on Twitter. Twitter has a bunch of caching systems in place, which means it might take some time for various followers around the globe to see my tweets. However, they will all see them in the order I tweeted them. More formally, operations may take effect before their invocation, or after their completion, as long as operations from the same process retain their relative order.
This is sequential consistency. I can never be seen to put some sugar in my tea before I heat the water. Multiple observers can see me brewing tea at different times, though.
Serialisability
We can go further. Say the history of operations is equivalent to one that took place in some single atomic order, but place no restrictions on relative invocation and completion times. This is a very weak model. It allows programs like:
x = 1
x = x + 1
print x
to print either 0, 1, or 2! Since serialisability permits many histories, it might seem particularly useless, but consider what histories it can prohibit:
print x if x = 3
x = 1 if x = 0
x = 2 if x = 1
x = 3 if x = 2
this program does not have an allowed event history in which the state of x changes in an order
other than 0 → 1 → 2 → 3. Isn’t that cool.
This is serialisable consistency. You’ll notice it doesn’t place any timeliness constraints on the ordering of operations. Serialisability does not imply any kind of deterministic order, it simply requires that some equivalent serial execution exists.
We can combine serialisability and linearisability to yield strict serialisability:
- the operation schedule is equivalent to some serial execution, and
- the serial order corresponds to a real time (wall clock) order
For example, say I begin operation T1, which writes to item x, and you later begin operation T2, which reads from x. A system providing strict serialisability for these ops will place T1 before T2 in the serial ordering, and T2 will read T1’s write: the ops appear to take effect in program order. A system providing serialisability, but not strict serialisability, could order T2 before T1.
Let’s now back up and see what parallel and concurrent mean, by contrasting them.
Let’s imagine two tasks T and S. T wants to insert element 4 in a list L after element 3, and S wants to insert element 5 in the same list after element 3.
T and S are serialisable, since there is a sequence of operations which produces a list with elements 3, 4, and 5, with 4 following 3 and 5 following 3. Since the order between 4 and 5 is unspecified, we can conclude there are at least two such schedules.
These schedules can be executed by a single thread of execution in serial, to produce the desired effect(s). A serial execution history is either “T → S”, or “S → T”.
We said earlier that parallel is the opposite of serial. A parallel execution employs at least two threads of execution (not necessarily “threads” as opposed to “processes”), one of which executes T and the other executes S.
A parallel execution of T and S, however, can lead into a list which does not contain element 4 (see Yan Solihin’s Fundamentals of Parallel Multicore Architecture, Chap. 5, where this exact example is explained in detail, step-by-step). Therefore these list insertions can’t be fully parallelised! This is not a general rule; there are mitigating circumstances where we can still achieve parallel execution, but our space is limited. Hah! just kidding, I’m bored.
A concurrent (and serial) execution of T and S means their operations could be interleaved in more than one order, as long as they happen in the order each task specifies.
T and S can be executed alternately (serial and concurrent). Concurrent execution produces a history in which the same effects are always observable. Keep in mind that serialisability implies that operations “appear” to take place atomically. There is no way, in this consistency model, to interleave sub-operations of T and sub-operations of S. For the thread executing S, this implies:
- it can observe L containing 3
- it can observe L containing 3 and 4
but no other state. Perhaps you can now prove to yourself; what sort of assumptions would you have to make to guarantee a concurrent and serial execution?
Conclusion?
Synchrony conditions and concurrency models are two orthogonal ideas. They very often overlap in very interesting ways. As an example, see Peterson and Fischer’s “Economical solutions for the critical section problem in a distributed system”, where they describe a collection of algorithms for mutual exclusion, and a way to obtain provable time complexity bounds for asynchronous parallel algorithms. Both are central in distributed systems theory, which already pervades the design of modern processors, and hopefully soon our operating systems.
« Past Future »