By the late 1950s, batch processing had solved the setup-time problem—computers no longer sat idle while programmers set up their jobs. But a new problem had become painfully clear: the CPU was still idle most of the time, waiting for I/O operations to complete.

Consider a typical batch job. It reads data from a tape drive, computes on that data, writes results, reads more data, computes again. The CPU sprints through the computation in microseconds, then waits milliseconds for the next tape read. In effect, the million-dollar processor was a sleeping giant, awake for tiny fractions of each second.

This chapter explores the solution to this crisis: multiprogramming—the revolutionary idea that changed computing forever.

The insight behind multiprogramming is elegantly simple: when one job is waiting for I/O, switch to another job that can use the CPU.

Instead of loading one job into memory, load several. When Job A initiates a tape read and must wait 100 milliseconds, immediately switch to Job B. When Job B initiates a disk write, switch to Job C. By the time you've cycled through several jobs, Job A's tape read has completed, and you can resume it.

The Key Realization:

Different jobs have different resource needs at different times:

By keeping a mix of job types in memory simultaneously, the operating system can ensure that there's almost always a job ready to use the CPU. When an I/O-bound job pauses to read data, a compute-bound job can step in and continue processing.

Mathematical Justification:

Let's model CPU utilization mathematically. Suppose each job spends a fraction p of its time waiting for I/O. If we have n jobs in memory, the probability that ALL jobs are waiting simultaneously is p^n.

CPU Utilization = 1 - p^n

For a typical batch job where p = 0.8 (80% I/O wait):

Multiprogramming introduced a fundamental new problem: how do you fit multiple programs into memory simultaneously, and how do you keep them from interfering with each other?

In batch processing, this was simple—only one job was in memory at a time, and it could use all available memory (except for the resident monitor). Multiprogramming shattered this simplicity.

Early Solutions: Fixed Partitions

The simplest approach divided memory into fixed-size partitions. Each partition could hold one job:

+------------------------+
|   Operating System     | (Always resident)
+------------------------+
|   Partition 1 (64KB)   | ← Job A
+------------------------+
|   Partition 2 (128KB)  | ← Job B
+------------------------+
|   Partition 3 (256KB)  | ← Job C
+------------------------+
|   Partition 4 (256KB)  | ← Empty (waiting)
+------------------------+

This approach had obvious limitations:

Variable Partitions

A more flexible approach allocated exactly as much memory as each job needed:

Initial State:
+------------------------+
|   Operating System     |
+------------------------+
|   Job A (50KB)         |
+------------------------+
|   Job B (100KB)        |
+------------------------+
|   Job C (75KB)         |
+------------------------+
|   Free (275KB)         |
+------------------------+

After Job B completes:
+------------------------+
|   Operating System     |
+------------------------+
|   Job A (50KB)         |
+------------------------+
|   Free (100KB)         | ← Hole left by Job B
+------------------------+
|   Job C (75KB)         |
+------------------------+
|   Free (275KB)         |
+------------------------+

Now the system has two free regions—a fragmented memory layout. If a new 200KB job arrives, it can't run even though 375KB total is free, because neither hole is large enough.

When a programmer writes code, they use symbolic addresses (variable names, function names). The compiler converts these to numeric addresses. But at what point are these addresses finalized?

This question became critical with multiprogramming. A program compiled to run at address 0x1000 couldn't simply be loaded at 0x3000—all its jumps, data references, and pointer calculations would be wrong.

Three Approaches to Address Binding:

The Base Register Solution:

Hardware provided a elegant solution: the base register (also called relocation register). Every memory address generated by a program would have the base register's value added to it automatically by hardware:

Physical Address = Base Register + Logical Address

This meant a program could be compiled assuming it starts at address 0, but actually loaded anywhere in memory. The OS simply sets the base register to the program's actual starting address.

The Address Translation Flow:

            ┌─────────────────────────────────────────────────────────┐
            │                         CPU                              │
            └─────────┬───────────────────────────────────────────────-┘
                      │ Logical Address (0x0500)
                      ▼
            ┌─────────────────────────────────────────────────────────┐
            │              Memory Management Unit (MMU)                │
            │  ┌─────────────┐      ┌───────────────┐                 │
            │  │Limit Reg:   │      │ Base Reg:     │                 │
            │  │  0x1000     │      │  0x5000       │                 │
            │  └─────────────┘      └───────────────┘                 │
            │                                                          │
            │  if (0x0500 < 0x1000):  ✓ Valid                         │
            │     Physical = 0x0500 + 0x5000 = 0x5500                 │
            │  else:                                                   │
            │     TRAP → Protection Fault                             │
            └─────────────────────────┬───────────────────────────────┘
                                      │ Physical Address (0x5500)
                                      ▼
            ┌─────────────────────────────────────────────────────────┐
            │                    Physical Memory                       │
            └─────────────────────────────────────────────────────────┘

This hardware-assisted address translation happened on every memory access—completely transparent to the running program. The program 'thought' it was accessing address 0x0500, but actually accessed 0x5500.

With multiple jobs competing for the CPU, a new responsibility fell upon the operating system: deciding which job runs next. This decision—CPU scheduling—became one of the most important OS functions.

When Does Scheduling Happen?

In multiprogramming systems, scheduling decisions occur when:

Non-Preemptive Scheduling:

Early multiprogramming systems used non-preemptive (also called cooperative) scheduling. A job kept the CPU until it voluntarily gave it up by:

1. Initiating an I/O operation
2. Terminating
3. Explicitly yielding (rare)

This was simple to implement—context switches only occurred at well-defined points. However, it had significant downsides:

Early Scheduling Algorithms:

The simplest scheduling algorithm was First-Come, First-Served (FCFS): jobs ran in arrival order. When Job A blocked on I/O, the system would run Job B (the next in queue), then Job C, and so on.

FCFS worked reasonably well for multiprogramming because the goal was maximize CPU utilization, not minimize response time. As long as some job was always ready to run, the CPU stayed busy.

The Job Pool Concept:

Operators would maintain a job pool—a collection of jobs on disk waiting to be loaded into memory. When a job in memory completed, the OS would select the next job from the pool. Selection criteria included:

• Job priority (higher priority first)
• Memory requirements (fit into available space)
• Required devices (tape drives, printers available?)
• Estimated run time (for deadline scheduling)

Switching from one job to another isn't as simple as jumping to different code. Each job has state—register values, memory pointers, condition flags—that must be preserved so the job can resume exactly where it left off.

The context switch became a fundamental OS operation: saving one job's state and restoring another's.

What State Must Be Saved?

The Process Control Block (PCB):

To manage job state, the OS introduced a data structure that would become fundamental to all operating systems: the Process Control Block (in early systems, often called the Job Control Block or Task State Block).

Each job had an associated PCB containing:

The Context Switch Procedure:

1. Save outgoing job's PC to its PCB
2. Save outgoing job's registers to its PCB
3. Save outgoing job's stack pointer to its PCB
4. Update outgoing job's state (RUNNING → WAITING or READY)
5. Select incoming job (scheduling decision)
6. Restore incoming job's base/limit registers
7. Restore incoming job's general registers from PCB
8. Restore incoming job's stack pointer from PCB
9. Update incoming job's state (READY → RUNNING)
10. Jump to incoming job's PC (resume execution)

This entire sequence had to be performed atomically—partially switching would leave the system in an inconsistent state. Hardware support (interrupt disabling, atomic state save/restore instructions) made this possible.

Multiprogramming amplified a problem that existed in batch systems: device contention. If multiple jobs want to use the printer simultaneously, chaos ensues—output from different jobs would be interleaved nonsensically.

Spooling (Simultaneous Peripheral Operations On-Line) solved this by inserting a buffering layer between jobs and devices:

        Job A output    ─┐
        Job B output    ─┼─→  Disk (Spool area)  ─→  Printer
        Job C output    ─┘           ↑
                                     │
                              OS manages queue,
                              prints complete jobs
                              one at a time

Benefits of Spooling:

1. Virtualization: Each job believes it has exclusive access to the printer
2. Speed: Jobs complete faster (write to disk, not slow printer)
3. Order: Output is coherent and complete
4. Resource Utilization: Printer operates continuously, never waiting for jobs to generate output

Device Drivers and Abstraction:

Multiprogramming also drove the creation of device drivers—OS components that hide hardware details from the rest of the system. Instead of jobs directly programming I/O controllers (dangerous and error-prone), they would request I/O through the OS:

Job → OS (system call) → Device Driver → Hardware Controller → Device

This abstraction meant:

• New hardware could be added without changing jobs
• The OS controlled all device access (security, fairness)
• Common I/O patterns could be implemented once in the driver
• Jobs couldn't crash the system with bad device commands

Several systems made multiprogramming practical and widespread. Understanding these systems illuminates how the concepts we've discussed were realized in practice.

IBM OS/360 (1964):

IBM's OS/360 was the first operating system designed to work across an entire product line—from small to large machines. It introduced or popularized many multiprogramming concepts:

EXEC (CDC):

Control Data Corporation's EXEC operating system for the CDC 6600 (1964) took a different approach. The CDC 6600 was designed for massive scientific computations, and EXEC emphasized:

• Extreme compute performance (the 6600 was the world's fastest computer)
• Efficient handling of large numerical jobs
• Minimal OS overhead to maximize user computation

MCP (Burroughs):

Burroughs' Master Control Program was revolutionary for being written in a high-level language (a variant of ALGOL) rather than assembly. This demonstrated that operating systems didn't have to be low-level artifacts—a controversial idea at the time that would eventually become standard.

Impact on Future Systems:

These multiprogramming systems established patterns that persist today:

Multiprogramming was a watershed moment in computing history. It transformed operating systems from simple job sequencers into sophisticated resource managers. Let's consolidate the key insights:

What's Next:

Multiprogramming maximized CPU utilization for batch jobs—but it didn't help the programmer staring at their desk, waiting hours for results. The next evolution would address this human cost: time-sharing systems that gave users the illusion of having the computer to themselves, with interactive terminals and sub-second response times.