Last week, I wrote about Vivek Haldar’s reading of Dijkstra’s famous paper, “Go to Statement Considered Harmful.” It turns out that Haldar has a series of posts like that in which he reads a foundational paper from Computer Science. One recent example is his reading of another Dijkstra paper, Solution of a problem in concurrent programming control.
The paper is from 1965 and offered the first solution to locking critical code regions. That seems like old news today. You protect the critical region with a semaphore but back in 1965 computers didn’t have the specialized “test and set” instructions that we use to implement semaphores. At the time Dijkstra wrote his paper, it was an open question as to how to implement what we now know as semaphores.
Haldar does a great job in covering the paper. Dijkstra’s papers are always dense but this one is particularly difficult. The code that Dijkstra presents is in ALGOL or at least is ALGOL-like and the syntax is easy to understand. Although comprising only 16 lines it’s very difficult to figure out what’s going on. Haldar refactors the code a bit and explains what’s happening.
It’s amazing how something we now consider elementary, if not trivial, was once considered so hard that it was an open problem. Of course, a lot of that is that once it was understood that a semaphore was what was needed, hardware primitives were introduced to make implementing them simple.