Turing Lecture: The Computer Science of Concurrency: The Early Years | June 2015 | Communications of the Acm
While concurrent program execution had been considered for years, the computer science of concurrency began with Edsger Dijkstra’s seminal 1965 paper that introduced the mutual exclusion problem
He posed the problem of synchronizing N processes, each with a section of code called its critical section, so that the following properties are satisfied:
Mutual Exclusion. No two critical sections are executed concurrently. (Like many problems in concurrency, the goal of mutual exclusion is to eliminate concurrency, allowing us to at least pretend that everything happens sequentially.)
Livelock Freedom. If some process is waiting to execute its critical section, then some process will eventually execute its critical section. Mutual exclusion is an example of what is now called a safety property, and live-lock freedom is called a liveness property.
Dijkstra was aware from the beginning of how subtle concurrent algorithms are and how easy it is to get them wrong. He wrote a careful proof of his algorithm. The computational model implicit in his reasoning is that an execution is represented as a sequence of states, where a state consists of an assignment of values to the algorithm’s variables plus other necessary information such as the control state of each process (what code it will execute next). I have found this to be the most generally useful model of computationfor example, it underlies a Turing machine. I like to call it the standard model.
Although of little if any practical use, the bakery algorithm11 has become a popular example of a mutual exclusion algorithm. It is based on a protocol sometimes used in retail shops: customers take successively numbered tickets from a machine, and the lowest-numbered waiting customer is served next. A literal implementation of this approach would require a ticket-machine process that never halts, violating Dijkstra’s requirements. Instead, an entering process computes its own ticket number by reading the numbers of all other synchronizing processes and choosing a number greater than any that it sees.