PintOS: Operating System as OrcheStra

First week of PintOS, I read the thread code. The functions themselves weren't hard. What was hard was the space between them. Why does this function stop here? Where does a stopped thread go, and who wakes it again? To gather the scattered answers, I drew the flow as a map and staring at the finished map, I closed my eyes.

I heard music. Threads were players, each with a melody of their own; the timer interrupt, a metronome keeping the beat; the scheduler, a conductor choosing the next sound.

The first question the map answered was: where is a thread right now? Running, it is RUNNING — the only one on the CPU. Able to run but not its turn, it stands in the ready_list as READY. Unable to run, it becomes BLOCKED and stays where it needs to be: in the sleep_list if waiting for its wake-up time, in a sema's waiters if waiting for a lock. State was not an attribute. It was a location.

The second answer was the rule of falling asleep. thread_block() doesn't merely stop a thread; it lifts the thread out of the flow of execution. So there is a condition: before sleeping, a thread must be registered somewhere. A thread that falls asleep written down nowhere can never be woken. That is why sema_down() writes the current thread into the waiters before it ever calls thread_block(). thread_block() itself doesn't know why it is going to sleep. It simply trusts that whoever put it to sleep has arranged a place for its waking.

The same goes for waking. thread_unblock() only makes a thread READY; whether it runs is the scheduler's decision. Exits rest on trust between players. Entrances belong to the conductor.

The beat is kept by the timer interrupt. Every tick, execution pauses for an instant: time is counted, threads due to wake are pulled from the sleep_list, and a thread that has run too long is put on notice to yield. No thread can play on forever outside this beat. On top of all that trust, schedule() picks the next thread and hands over the CPU with do_iret(). At the exact point where the last run ends, the next one begins.

There is a moment when code becomes flow, and flow becomes order. I was searching for a name for that order when I realized the answer had been in the spelling all along.

OrcheStra. Keep only the capitals: OS.