From FCFS to Preemptive Multitasking: Lessons from 1960s IBM Scheduling

In the early 1960s, an IBM mainframe system engineer faced the challenge of keeping a multi‑million‑dollar computer running efficiently. After introducing multiprocess support, he encountered frequent disputes among users over which program should run first, exposing the core problem of process scheduling.

Key Scheduling Questions

How should the system decide which process runs first—by arrival order, urgency, or importance?

What is a reasonable time slice for a running process?

How can the system ensure fair and efficient use of CPU resources for both CPU‑intensive and I/O‑intensive tasks?

First‑Come‑First‑Served (FCFS)

The team initially implemented a straightforward FCFS queue: the earliest submitted job receives the CPU. This solved the "who runs first" question but quickly revealed a severe flaw—long batch jobs could monopolize the CPU for hours, forcing short interactive tasks to wait and causing user complaints about sluggishness.

Cooperative Multitasking

To improve responsiveness, the team added a voluntary yielding mechanism. They introduced a new system call yield() that processes could invoke to relinquish the CPU, encouraging programmers to insert periodic calls in long‑running code.

However, this relied on programmers’ goodwill. Some developers ignored the call, either out of negligence or malicious intent, leading to runaway processes that locked the CPU and forced a system reboot, losing all users’ work.

Preemptive Multitasking (Round‑Robin)

Realizing voluntary yielding was insufficient, the engineer designed a timer interrupt that periodically preempts the currently running process, switching to the next one in a fixed‑length time slice. This round‑robin scheduler guarantees that even a process stuck in an infinite loop will be interrupted, restoring system responsiveness and fairness.

Priority Scheduling

As system load grew, treating all processes equally became unsafe—critical tasks shared the same priority as trivial games. The solution was to assign each process a priority value and always run the highest‑priority ready process. Yet this introduced the "starvation" problem, where low‑priority jobs might never get CPU time if high‑priority jobs continuously arrive.

These observations highlighted the need for more sophisticated algorithms that balance fairness, responsiveness, and importance, laying the groundwork for modern operating‑system schedulers.