Process and Thread Scheduling: Algorithms, Strategies, and Goals

Scheduling

When a computer runs a multiprogramming system, many processes or threads compete for CPU time slices. The operating system uses a scheduler that selects which process/thread runs next based on a scheduling algorithm . Although some details differ, most techniques for process scheduling also apply to thread scheduling.

Introduction to Scheduling

Early batch systems simply executed jobs sequentially on magnetic tape. Modern multiprogramming systems must decide which ready process gets the CPU, often distinguishing between compute‑bound and I/O‑bound processes.

Process Behavior

Processes alternate between CPU bursts and I/O waits. Compute‑bound processes use the CPU for long periods, while I/O‑bound processes spend most of their time waiting for devices. As CPU speeds increase faster than storage, more workloads become I/O‑bound, making their timely scheduling increasingly important.

When to Schedule

Scheduling decisions occur at several events: creation of a new process, termination of a process, when a process blocks for I/O or a semaphore, on I/O completion interrupts, and on periodic clock interrupts. These events lead to two major classes of algorithms: non‑preemptive and preemptive.

Classification of Scheduling Algorithms

Different environments require different algorithms. Three typical environments are:

Batch

Interactive

Real‑time

Batch systems prioritize throughput and turnaround time; interactive systems aim to minimize response time; real‑time systems must meet deadlines.

Batch Scheduling Algorithms

First‑Come, First‑Served (FCFS) : Processes are run in arrival order using a simple ready‑queue. Easy to implement but can cause long waits for compute‑bound jobs.

Shortest Job First (SJF) : Assumes known run times and selects the shortest job, minimizing average turnaround time. Its preemptive version is Shortest Remaining Time Next (SRTN).

Round‑Robin : Assigns each process a time quantum; if the quantum expires, the process is pre‑empted and placed at the queue tail. The quantum length balances context‑switch overhead against response time.

Priority Scheduling : Each process receives a priority; higher‑priority processes run first. Priorities can be static or dynamic (e.g., based on recent CPU usage).

Multilevel Queue : Processes are divided into priority classes, each with its own scheduling policy (often round‑robin). Higher classes are served before lower ones, preventing starvation with aging.

Lottery Scheduling : Processes hold tickets; a random draw selects the winning ticket, giving each process a share of CPU proportional to its tickets. This provides probabilistic fairness and easy priority adjustments.

Interactive System Scheduling

Interactive systems rely heavily on round‑robin and priority scheduling to keep response times low. The quantum is typically set between 20 ms and 50 ms to avoid excessive context switches while still providing prompt feedback.

Real‑Time Scheduling

Real‑time systems are divided into hard and soft categories. Hard real‑time must meet strict deadlines; soft real‑time tolerates occasional misses. Scheduling must guarantee that the sum of CPU utilizations of all periodic tasks is ≤ 1, otherwise the system is unschedulable.

Scheduling Strategies

Static scheduling decides the order before execution, suitable when task execution times and deadlines are known. Dynamic scheduling makes decisions at run time, adapting to actual workloads.

Thread Scheduling

When processes contain multiple threads, the kernel may schedule at the process level (user‑level threads) or at the thread level (kernel‑level threads). Kernel‑level threads allow the scheduler to pre‑empt individual threads, improving responsiveness but incurring higher context‑switch costs.

Scheduling Goals

Key objectives include fairness (equal CPU share for equal‑priority processes), high CPU utilization, maximizing throughput, minimizing turnaround and response times, and meeting real‑time deadlines. Balancing these goals often requires trade‑offs, such as adjusting quantum length or employing aging to prevent starvation.

Conclusion

The article summarizes classic and modern scheduling techniques, highlights their applicability to batch, interactive, and real‑time systems, and discusses how metrics like throughput, turnaround time, and CPU utilization guide the design of effective schedulers.