Evolution of Process Scheduling: From FCFS to Preemptive Multitasking

In the early 1960s, an IBM computer center system engineer faced the challenge of efficiently utilizing a multi‑million‑dollar mainframe, having just introduced a multi‑process environment that allowed several programs to reside in memory simultaneously.

Typical mornings featured three users—finance, R&D, and a physics professor—arguing over which program should run first, exposing fundamental scheduling questions such as order of execution, appropriate time slices, and fair resource utilization.

The first solution implemented was First‑Come‑First‑Served (FCFS), a simple queue where the earliest submitted job received CPU time. While easy to code, FCFS quickly proved inefficient when a long batch job monopolized the CPU for hours, causing interactive users to experience severe latency.

To improve responsiveness, the team tried cooperative multitasking by adding a new system call yield() that allowed a process to voluntarily relinquish the CPU. Programmers were encouraged to insert yield() calls periodically, but the approach failed when developers omitted the call or when buggy loops prevented yielding, leading to system hangs and forced reboots.

Realizing that reliance on user‑level cooperation was unsafe, the engineer introduced preemptive multitasking: a hardware timer generated periodic interrupts that forced the current process to stop after a fixed time slice and switch to the next one. This round‑robin scheduler ensured that even a runaway process could not block the system, dramatically improving interactivity.

As system load grew, the limitation of pure round‑robin became apparent—critical tasks received the same priority as trivial ones. Consequently, a priority‑based scheduler was added, always selecting the highest‑priority process to run. However, this introduced the starvation problem, where low‑priority processes might never get CPU time if high‑priority jobs kept arriving.

The narrative concludes that each scheduling strategy—FCFS, cooperative, preemptive round‑robin, and priority—offers trade‑offs, and that designing a robust scheduler requires combining fairness, responsiveness, and priority handling while avoiding starvation.