1961

Round Robin

CTSS was demonstrated at MIT in November 1961 and three people shared one 7090 without any of them being told about the others. The trick is that nobody keeps the processor: a clock interrupts, the running program goes to the back of the queue, and the next one starts. What follows runs that on three jobs and measures what it costs them. Then it runs the algorithm CTSS actually published, which was not this one.

Every program believes it owns the processor

1 Three programs, one processor, and a clock

Three jobs, one processor. Run them to completion in the order they arrive and the short job behind the long one waits for all of it. That is the thing time-sharing is for, and the number to watch is how long each job waits before it first gets to run.

2 The quantum expires and the program goes to the back

Now give each job a fixed slice and put it at the back when the slice runs out. Nothing is ever finished early and nothing is ever starved. Change the quantum and watch both numbers move.

Quantum

3 What that costs the short job and buys the long one

A smaller quantum answers the short job sooner and interrupts more often. Each switch is work the jobs do not get, so the same total work takes longer to finish. This is the whole trade and it has no right answer.

quantum	mean wait before first run	switches	all done at

4 What CTSS actually did, which was not this

CTSS did not do this. Its published algorithm put each program into a level set by how big it was, ran it for two-to-the-level quanta, and moved it down a level when it did not finish, so a big program ran less often and for longer each time. Both are run here on the same jobs.

These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.

Each claim, whether it held, and the values behind it
claim	held	measured
sharing the processor answers the average job sooner than running each to completion	yes	mean wait before first run 6.00 in arrival order, 3.00 shared
and it costs time, because every switch is work the jobs do not get	yes	19 to finish everything, against 25
a smaller quantum answers sooner and switches more	yes	quantum 1: wait 2.00, 11 switches; quantum 8: wait 5.67, 3
no job is starved: every one of them finishes	yes	3 job(s), all finished by 25
and every job gets exactly the processor time it asked for	yes	19 units asked for, 19 units run
the algorithm CTSS published is not this one, and gives the small job a different answer	yes	levels used: 0, 1, 2, 3; longest slice 8 units

What is real here, and what is not

The name on this page is not what CTSS ran

Round robin is the idea the demonstration is remembered for and it is not the algorithm in the paper. Corbato, Merwin-Daggett and Daley describe a multi-level scheme: a program enters at a level set by the log of its size against what can be moved in a quantum, runs for two-to-the-level quanta, and drops a level when it does not finish. The last panel runs that. Calling the 1961 machine a round-robin scheduler would be wrong, and the page would rather show the difference than smooth it over.

The year is the demonstration, not the paper

CTSS was shown at MIT in November 1961; the paper came at the Spring Joint Computer Conference in May 1962. The chronology sorts by the machine running, because that is when the thing existed.

A switch costs one unit here, and it is a made-up unit

Real context switches cost a few microseconds of register saving plus whatever the caches and the TLB lose afterwards, which is usually the larger half and depends on the machine. This page charges a flat unit so that the shape of the trade is visible. The number is a knob, not a measurement, and the ledger says so rather than dressing it as one.

No I/O, no priorities, no arrival times

Every job here is ready at time zero and wants nothing but processor. Real schedulers spend most of their effort on jobs that block, arrive late, or matter more than each other, and none of that is modelled. What is left is the one question the page is about: what does taking the processor away and giving it back cost.

No sound

Nothing here has a duration to hear.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1971-1995 Line ModeYou could telnet to port 80 and be the browser, and then you could not.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Flip-Flop, Punch Cards, Interlace, Bitwise, The Adder, Stored Program, Two's Complement, Trigger, Bit, Nibble, Byte, Transistor, Score Reel, Hamming, Huffman, Core Memory, Hash Table, The Interrupt, CORDIC, Garbage, CRC, The Pipeline, Round Robin, Page Fault, Context Switch, ASCII, Bresenham, CPU Cache, Race, Fifteen Planes, B-tree, Backoff, Checkout, Diffie-Hellman, Zero Address, Fringes, LZ77, Signature, Z-Characters, Merkle Proof, Branch Prediction, Write-Ahead Log, Interleave, Eight Sprites, DNS, Floating Point, Slow Start, Longest Chain, JPEG, UTF-8, Masking, PageRank, Merge Collapse, Merkle DAG, Count Distinct.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.