A Dialogue on Concurrency

Part II 💬 Dialogue OSTEP pp. 285–286 · ~5 min read

Every race in this part will live in the gap the student spots: the moment between seeing a peach and closing your hand on it.

Why this matters

A queue does not coordinate the grabbing, it abolishes it — one hand at a time is correct because nothing overlaps. Nearly all of Part II tries to keep the overlap and be correct anyway; the one approach that gives it up arrives filed under heresy.

The second pillar begins — as these things must — with fruit.

Professor:And thus we reach the second of our three pillars of operating systems: concurrency.
Student:I thought there were four pillars…?
Professor:Nope, that was in an older version of the book. Anyhow — imagine we have a peach —
Student:(interrupting) Peaches again! What is it with you and peaches?
Professor:Ever read T.S. Eliot? The Love Song of J. Alfred Prufrock — “Do I dare to eat a peach,” and all that fun stuff?
Student:Oh yes! In English class. Great stuff! I really liked the part where —
Professor:(interrupting) This has nothing to do with that — I just like peaches. Imagine a table full of peaches, and a crowd who wish to eat them. Each eater identifies a peach visually, then tries to grab it. What’s wrong with this approach?
Student:Hmmm… you might see a peach that somebody else also sees. If they get there first — when you reach out, no peach for you!

The peach table, three ways: the whole of Part II in fruit

grab at will🫱🫲⚡ conflict!fast, but sometimes: no peach for youform a line🧍🧍🧍🧍correct, but one at a time — quite a bit slowerfast AND correct?locks, condition variables, semaphores… — Part II
Professor:Exactly! So what should we do about it?
Student:Probably form a line — when you get to the front, grab a peach and get on with it.
Professor:Good! But what’s wrong with your approach?
Student:Sheesh, do I have to do all the work? …OK. We used to have many people grabbing at once, which is fast. My way goes one at a time — correct, but quite a bit slower. The best approach would be fast and correct, probably.
Professor:You are really starting to impress. You just told us everything we need to know about concurrency!
Student:I did? I thought we were just talking about peaches. Remember, this is usually the part where you make it about computers again.
Professor:Indeed — one must never forget the concrete. There are programs we call multi-threaded applications; each thread is an independent agent running around in the program, doing things on its behalf. But threads access memory, and for them, each spot of memory is one of those peaches. Without coordinating access, the program won’t work as expected.
Student:Kind of makes sense. But why do we talk about this in an OS class? Isn’t that just application programming?
Professor:Good question! First, the OS must support multi-threaded applications, with primitives such as locks and condition variables — coming soon. Second, the OS itself was the first concurrent program — it must access its own memory very carefully, or many strange and terrible things happen. Really, it can get quite grisly.
Student:I see. Sounds interesting. There are more details, I imagine?
Professor:Indeed there are…

If you remember only three things

  • A peach is consumed and memory is not. Two eaters cannot share one peach, but two threads reading the same location get in nobody’s way — the trouble starts when one of them writes, so the primitives ahead care what a thread does and not merely where it looks.

  • The operating system appears twice in this story. It must provide the coordination primitives that applications call, and it was itself the first program to need them — the provider and the customer of one abstraction.

  • Nothing in the parable involves a computer. A table, some fruit, and several hands reaching at once — the shape holds wherever independent agents go for the same thing at the same moment, so the answers ahead read alike whether the sharer is a kernel or a web server.

The road through Part II

Threads and their API; then the great primitives — locks, concurrent data structures, condition variables, semaphores; then the bugs that haunt them all (races, deadlock); and a heretical alternative, event-based concurrency. Fast and correct — that’s the whole game.

Check yourself

1.The naive peach protocol — see a peach, then grab it — fails. What exactly goes wrong, and what is the computing translation?

2.The student's fix — form a line — works. Why isn't it the end of the story?

3.Why does concurrency belong in an OS course rather than just an application-programming one?

3 questions