systems
A computer shared by fifty
It is 1961 at MIT, and the batch-processing regime is strangling the field: a programmer submits a card deck, waits a day, and learns of a missing comma. The proposal is heresy to the accountants — let fifty people use one multi-million-dollar machine at once, each at a typewriter, each under the illusion the computer is theirs alone. Design the time-sharing system: slice the processor fairly among interactive users, protect each one's memory from the others' bugs, and keep response snappy enough that thought is never interrupted. Get it wrong and either one user's infinite loop freezes everyone, or the scheduling overhead eats the machine — and interactive computing, the precondition for everything from LISP hacking to modern software culture, stays a fantasy.
Who this problem belongs to
The two figures whose methods fit it best, out of 40 in contention.
This is not a hypothetical for McCarthy; it is his own 1959 memorandum to MIT's Long Range Computer Study Group, in which he proposed exactly what this problem describes: let multiple users share one expensive computer interactively, each typing at a console with the illusion of undivided attention, rather than submitting batch card decks and waiting a day for results. His advocacy directly catalyzed MIT's Compatible Time-Sharing System and later Project MAC, the concrete engineering answer to this problem's scheduling-fairness-and-isolation challenge. He also personally designed LISP's environment for interactive use, reinforcing his broader thesis that computing should feel conversational. He did not personally write CTSS's scheduler code, which is the only reason his score stops short of the very top.
Dijkstra's inventions of the semaphore and his foundational work on mutual exclusion, developed for the THE multiprogramming system in the mid-1960s, are the direct technical answer to this problem's core hazard: how to let many processes share memory and processor time without one user's bug corrupting another's session or the whole machine deadlocking. His rigorous, formally provable approach to concurrency control, rather than ad hoc locking tricks, established the discipline every subsequent time-sharing and multiprogramming operating system depends on for correctness. His own THE system's work came a few years after this problem's 1961 MIT setting, and his focus was general multiprogramming rather than MIT's specific interactive time-sharing project, keeping him a hair below McCarthy's direct historical claim.
40 figures are scored on this problem. Draw it in a battle to see where you land.