How OSs Work: Scheduling

Surely the essence of any operating system is something called the "scheduler." How does the computer run all those programs, all at the same time. Surly it must be done by some terribly technical computer science equivalent of rocket science, way beyond the understanding of the lay person, gnostic knowledge reserved only for the operating system internals priesthood.

What is a program?

Well, actually, scheduling is quite simple in essence. To understand scheduling, first we must understand the concept of program.

Some define a program as a collection of bugs flying in formation, that occasionally does something useful enough to live with the cyber-insects, but we'll not mention that.

It's all about instructions, a sequence of them, a never ending cycle. All the orders for the automaton that controls a set of CPU registers and the arithmetic/logic unit (ALU) get snatched from DIMMs and impaled into a special hidden register called, appropriately enough, the instruction register.

The bits from the instruction register, plus the constant ticking of the metronome-like processor clock, usually blazing along at multiple billion ticks per second, control all the goings on of the registers and ALU. Words are fetched, or stored, registers are added, or anded, or shifted, or mutilated in some way thought to eventually be useful, all at the expressed, if semiconscious, deliberations of the programmer.

The last thing that happens in this never ending cycle of drag from DDR, decode, and do, is to fetch of the next instruction to be impaled into to the instruction register. Last wish is for three more wishes. But how does the CPU keep track of which instruction is next?

Something inappropriately called the program counter (PC) contains the address of the next instruction to be fetched. The PC doesn't actually count programs, so the name is a bit odd. But I digress.

After every gyration of the control section, ALU, the PC is incremented by the size of the just arrested, tried, and executed instruction, leaving the PC ready to point to its next victim. Unless, of course, the PC has been changed by a jump or call instruction. Those instruction merely change the value of the PC and viola, you're going to start executing a new sequence of instruction. Simple, eh?

What if I have two programs and want them both to work at the same time?

This was the question people asked back in the early days, when the fastest computer was also the slowest, because it was the only computer, back when it was barely out of the diapers of vacuum tubes and into the OshKosh ByGosh shorts of early transistors and out of those memories of mercury filled tubes or long conical tubes filled with nothing that was the electrostatic CRT memories, to those new and wonderful iron-ceramic donuts of core memory.

What ever else the darn primitive thing was, it was hugely expensive. Price tag in the mid 1950's was around $2,000,000. That's about $18,000,000 in 2018 dollars. It was worth as much as the buildings it was in.

And it spent most of its time sitting around waiting for the stupid tape drive to read its six-bit characters off its seven-bit tape real at a blazingly slow 75 inches a second. (The disk drive was a couple of years away.) Programs did a little bit, then waited for the data. It did a bit more when that data arrived and waited for some more data. That's a lot of money to wait around.

Can't we do something else while waiting?

Well, yes, they thought. Let's put two (or more) of those pesky programs into our spacious four kilo-word (thirty-six bits, or six six bit characters. Ever wonder why FORTRAN variables are only six character long?) core storage and run both. How?

Let's wire a clock to some really stable time source, for some values of "really stable," and use it to interrupt the computer after a period of time. The best and most stable time source was the AC power coming out of the wall outlet. It was about as stable a 60 Hz as one could every find. And cheap, too. But I digress again.

When we get an interrupt from the time source, lets save the registers of the currently running program into a specially set aside place and load the registers for the program we want to run now from where we've saved before.

The most important register to save and restore later is...the program counter.

I once wrote a very tiny operating system, which fit into the 1 K of memory of that machine, that did just that. That was in 1979. The microprocessor saved all its generous register space (sarcasm alert), so all I had to do was to save the PC and load the other program's PC, and return from the interrupt.

The simplest schedulers I've ever seen was in a Control Data mini-computer operating system of the 1970's. The operating system actually dated back at least a dozen years before that. It consisted of a few dozen words of memory, each of which could contain a PC, and two variables which indexed into this memory. One variable was used for inserting a new PC into the space and one was used to pull out the PC for the next program to run. It was the run queue. That was all there was to it, two pointers and a small array of integers.

That was for a machine didn't have a stack. In those days programing languages were not recursive, and you simply put variables into memory. Todays languages use a stack to keep local variables for each function, New function, new stack frame. Allocating data for the stack is just a matter of subtracting a value from the stack pointer.

So day, we have to save both the PC and the stack pointer (SP). In EthOS, like any other modern operating system, a Label is the pair, PC and SP. Instead of just saving the PC, we save both. But that's it.

Well, so much for being rocket science. In essence, scheduling is just taking the next PC and SP off a queue. One can get much fancier, often to no real benefit except for trying to obscure how simple things really are and thereby preserve the unholy priesthood of operating systems gurus. But the essence of scheduling is just taking the next PC off a queue.

Speaking of which, I hope they don't come ofter me for letting the truth out.

If you enjoyed this muse, you might appreciate my storage products, the Coraid EtherDrive SRX and VSX. Please check them out.