Process Scheduling in a Multiprogramming Operating System

Process scheduling is the core control function that makes a multiprogramming operating system effective. In multiprogramming, several processes are kept in memory at once, but on a single CPU only one can execute at any instant. The scheduler therefore decides which ready queue process should run next, when a running process should be preempted, and how the CPU is reassigned after an I/O wait, interrupt, or process completion.2

The fundamental role of process scheduling is to keep the CPU busy while processes alternate between CPU burst and I/O burst phases. If one process blocks for I/O, the operating system can immediately dispatch another ready process; this overlap is precisely what allows multiprogramming to improve resource use and overall system performance.2 Without scheduling, the CPU would frequently sit idle during I/O waits, undermining the main objective of multiprogramming: maximizing useful work from available hardware.2

At a systems level, scheduling also determines fairness, responsiveness, and efficiency. The short-term scheduler selects among ready processes very frequently, while long-term and medium-term schedulers influence how many and what kinds of jobs are admitted or swapped, thereby shaping the degree of multiprogramming.2

A useful abstraction is:

$$\text{Effective CPU use} \approx \text{choose ready work quickly} + \text{avoid idle gaps} + \text{balance performance goals}$$

Footnotes

1. Types Of Scheduling - Explains why scheduling is the key to multiprogramming and defines major scheduling criteria. ↩ ↩² ↩³

2. Operating Systems: CPU Scheduling - University course notes covering CPU utilization, throughput, turnaround, waiting, and response time. ↩

3. CPU Scheduling: Principles and Challenges - Summarizes core scheduling metrics and practical CPU utilization ranges. ↩

4. Operating System - Process Scheduling - Describes process scheduling as essential to multiprogramming and outlines long-, medium-, and short-term scheduling. ↩ ↩²

5. Chapter 5: CPU Scheduling - Lecture slides based on standard OS concepts, including dispatcher, dispatch latency, and optimization criteria. ↩

Fundamental Role of Process Scheduling

The scheduler’s first responsibility is CPU utilization: keeping the processor busy as much as possible.2 In real systems, references commonly describe effective CPU usage ranges roughly from $40\%$ on lightly loaded systems to $90\%$ on heavily loaded systems, emphasizing that a good scheduler reduces waste rather than pursuing an unattainable perfect $100\%$.2

Its second responsibility is coordinating competing processes so that the system completes more work per unit time. This is captured by throughput, which rises when the scheduler minimizes unnecessary idle time and chooses work in a way that sustains progress across the workload.2

Its third responsibility is user experience. In interactive systems, a scheduler must not merely finish jobs eventually; it must produce early feedback. That is why response time is often as important as total completion time.2

In short, process scheduling is the policy engine that mediates among these goals:

Because these goals can conflict, scheduling is never just “pick the next process.” It is an optimization problem with trade-offs among efficiency, latency, and fairness.2

Footnotes

1. Operating Systems: CPU Scheduling - University course notes covering CPU utilization, throughput, turnaround, waiting, and response time. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. CPU Scheduling: Principles and Challenges - Summarizes core scheduling metrics and practical CPU utilization ranges. ↩ ↩² ↩³

3. What is Burst time, Arrival time, Exit time, Response time, Waiting time, Turnaround time, and Throughput? - Clarifies the differences among turnaround, waiting, response time, and throughput. ↩ ↩²

Scheduling Criteria: What Makes One Policy Better Than Another?

A scheduling criterion is a metric used to judge how well a scheduling policy performs. Standard operating-systems references consistently evaluate schedulers using criteria such as CPU utilization, throughput, turnaround time, waiting time, and response time.3

Below are five major criteria, with at least three explained in depth as required.

1. CPU Utilization

CPU utilization measures the fraction of time the CPU is actively executing useful work.2 In a multiprogramming system, this is foundational because the entire purpose of keeping multiple processes in memory is to ensure that when one process waits, another can run.2 A scheduling policy that leaves the CPU idle too often wastes system capacity.

2. Throughput

Throughput is the number of processes completed per unit time.2 High throughput is especially desirable in batch-oriented environments, where the system is judged by how much total work it finishes. A scheduler that reduces unnecessary waiting and keeps shorter jobs moving can often improve throughput, though sometimes at the cost of fairness to long jobs.2

3. Turnaround Time

Turnaround time is the total elapsed time from submission to completion.2 It includes waiting in queues, CPU execution, and I/O delays. This criterion matters when users care about full job completion, such as in batch processing, compilation, or analytics workloads.

Formally,

$$\text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time}$$

4. Waiting Time

Waiting time measures only the time spent queued for CPU service, not the time actually running or blocked for I/O.2 Since CPU scheduling directly controls ready-queue delays, this criterion is highly useful for comparing scheduling algorithms.

A common relation is:

$$\text{Waiting Time} = \text{Turnaround Time} - \text{CPU Burst Time}$$

for simplified single-burst examples.

5. Response Time

Response time is the interval from request submission until the first visible response begins.2 In interactive and time-sharing systems, this may be more important than turnaround time, because users perceive the system as responsive when feedback begins quickly even if the full task completes later.2

These metrics point in different directions. For example, favoring short jobs may reduce average waiting time and improve response, but can also create starvation for long or low-priority jobs if fairness controls are absent.

Footnotes

1. Operating Systems: CPU Scheduling - University course notes covering CPU utilization, throughput, turnaround, waiting, and response time. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

2. Chapter 5: CPU Scheduling - Lecture slides based on standard OS concepts, including dispatcher, dispatch latency, and optimization criteria. ↩ ↩² ↩³

3. What is Burst time, Arrival time, Exit time, Response time, Waiting time, Turnaround time, and Throughput? - Clarifies the differences among turnaround, waiting, response time, and throughput. ↩ ↩² ↩³ ↩⁴ ↩⁵

4. CPU Scheduling: Principles and Challenges - Summarizes core scheduling metrics and practical CPU utilization ranges. ↩ ↩²

5. Types Of Scheduling - Explains why scheduling is the key to multiprogramming and defines major scheduling criteria. ↩

6. Operating System - Process Scheduling - Describes process scheduling as essential to multiprogramming and outlines long-, medium-, and short-term scheduling. ↩

7. Chap5 Process Scheduling - Operating System (OS) - Course slides discussing scheduling criteria, starvation, and aging as a fairness mechanism. ↩

Synthesis: Why These Criteria Matter Together

The role of process scheduling in a multiprogramming operating system can be summarized as intelligent CPU allocation under contention. The scheduler ensures continuous progress by selecting from the ready queue whenever the current process blocks or yields, thereby maintaining concurrency in effect even on a single CPU.2

The three most commonly emphasized criteria are CPU utilization, throughput, and turnaround time, but waiting time and response time are equally important in many environments.3 The “best” scheduler therefore depends on workload goals:

• Batch systems often emphasize high throughput and low turnaround time.
• Interactive systems strongly emphasize low response time.2
• General-purpose systems must balance fairness, responsiveness, and efficiency together.2

A concise optimization view is:

$$\text{Goal} = \max(\text{CPU Utilization}, \text{Throughput}) \quad \text{and} \quad \min(\text{Turnaround}, \text{Waiting}, \text{Response})$$

No single policy optimizes all dimensions simultaneously, which is why scheduling remains one of the most important design problems in operating systems.2

Footnotes

1. Types Of Scheduling - Explains why scheduling is the key to multiprogramming and defines major scheduling criteria. ↩

2. Operating System - Process Scheduling - Describes process scheduling as essential to multiprogramming and outlines long-, medium-, and short-term scheduling. ↩

3. Operating Systems: CPU Scheduling - University course notes covering CPU utilization, throughput, turnaround, waiting, and response time. ↩ ↩² ↩³

4. Chapter 5: CPU Scheduling - Lecture slides based on standard OS concepts, including dispatcher, dispatch latency, and optimization criteria. ↩ ↩² ↩³ ↩⁴

5. What is Burst time, Arrival time, Exit time, Response time, Waiting time, Turnaround time, and Throughput? - Clarifies the differences among turnaround, waiting, response time, and throughput. ↩ ↩²

6. Chap5 Process Scheduling - Operating System (OS) - Course slides discussing scheduling criteria, starvation, and aging as a fairness mechanism. ↩