Algorithm Architecture &
Mathematical Models

FCFS represents the most fundamental scheduling heuristic, allocating the central processing unit strictly to the process that requests it first.

Implementation is strictly managed via a FIFO (First-In-First-Out) queue structure. While computationally inexpensive regarding scheduling overhead, FCFS is highly susceptible to the Convoy Effect. This phenomenon occurs when short, I/O-bound processes are forced to wait for heavy, CPU-bound processes to release the core, severely degrading overall system throughput and yielding suboptimal average waiting times.

SJF minimizes the average waiting time for a given set of processes by consistently selecting the waiting process with the smallest execution time.

Mathematically, SJF is provably optimal for minimizing average waiting time. However, it cannot be perfectly implemented at the level of short-term CPU scheduling because exact future burst times cannot be known. Operating systems approximate this by predicting future burst times using exponential averaging of previous CPU bursts. A critical flaw of SJF is the risk of starvation for long processes.

SRTF serves as the preemptive counterpart to SJF. It continuously evaluates the ready queue, preempting the currently executing process if a new arrival possesses a shorter remaining execution time.

This continuous evaluation provides theoretically optimal average waiting times for dynamic systems. However, SRTF introduces substantial overhead due to frequent context switching. It also suffers from the same starvation vulnerabilities as SJF, where continuous streams of short processes can indefinitely delay heavy, CPU-bound tasks.

This algorithm assigns an explicit priority integer to each process, allocating the CPU to the highest-priority process until it voluntarily yields or completes.

Priorities can be defined internally (e.g., memory requirements, time limits) or externally (e.g., user importance, department constraints). In the non-preemptive variant, once a process acquires the CPU, it retains control regardless of subsequent arrivals. A major vulnerability is indefinite blocking (starvation) of low-priority processes, typically mitigated by a technique called aging, which gradually increases the priority of waiting processes.

The preemptive iteration of priority scheduling immediately interrupts a running process if a new process arrives with a strictly higher priority classification.

This responsiveness is critical for real-time operating systems where tasks must meet strict, hard deadlines. The preemption mechanism requires robust context-switching capabilities. Like its non-preemptive counterpart, it necessitates aging protocols to prevent the starvation of low-tier processes under heavy computational loads.

Designed specifically for time-sharing systems, RR assigns a fixed time slice (quantum) to each process in equal portions and in circular order.

The ready queue is treated as a circular structure. If a process burst exceeds the defined time quantum, the process is preempted and appended to the tail of the ready queue. The performance of RR depends heavily on the size of the time quantum. If the quantum is infinitely large, RR reduces to FCFS. If it is extremely small, the context-switching overhead dominates CPU utilization. Response time is strictly bounded.

HRRN is a non-preemptive scheduling discipline designed to balance the trade-off between the efficiency of SJF and the fairness of FCFS by dynamically computing a response ratio for every waiting process.

The response ratio is calculated as (waiting time + burst time) / burst time. As a process waits longer, its ratio climbs, eventually rivaling or exceeding that of freshly arrived short jobs. This self-correcting mechanic effectively prevents the indefinite starvation that plagues pure SJF, while still favoring shorter jobs when queue conditions are otherwise equal.

MLQ partitions the ready queue into several distinct sub-queues, permanently assigning processes to a specific queue based on inherent properties like process type or origin.

Each distinct queue possesses its own scheduling algorithm. For instance, foreground (interactive) processes might utilize Round Robin for rapid responsiveness, while background (batch) processes might employ FCFS. Scheduling must also occur between the queues themselves, typically implemented as absolute preemptive priority (e.g., foreground strictly over background) or through proportional time-slicing among the queues.

MLFQ extends the multilevel queue model by allowing processes to migrate between priority tiers based on observed CPU behavior, rather than fixing them to a single queue for their entire lifetime.

New processes enter the topmost queue, which is granted the shortest time quantum. Should a process fail to complete within that slice, it is demoted to a lower-priority queue with a longer quantum, reflecting its classification as more CPU-bound. Interactive, I/O-heavy processes tend to complete quickly within the high-priority tiers and rarely get demoted, giving the scheduler adaptive responsiveness without requiring any prior knowledge of burst lengths.

Lottery Scheduling reframes CPU allocation as a probabilistic raffle: each process holds a number of tickets proportional to its desired share of the processor, and a winning ticket is drawn at every scheduling decision.

Because selection is randomized, the algorithm avoids the pathological starvation scenarios that can arise in strictly deterministic schedulers, while still honoring proportional shares on average over many rounds. Processes with heavier ticket allocations run more frequently, and additional tickets can be transferred between cooperating processes to implement priority inheritance.

Stride Scheduling delivers the same proportional-share guarantees as Lottery Scheduling but replaces randomness with a fully deterministic bookkeeping mechanism.

Every process is assigned a stride value inversely proportional to its ticket count, and a running pass counter that increases by its stride each time it is scheduled. The scheduler always selects the process with the lowest pass value, ensuring that CPU time is distributed with far less variance than the lottery approach while preserving the same proportional-fairness properties.

Guaranteed Scheduling makes an explicit promise to every process: over time, each of the n active processes will receive approximately 1/n of the available CPU time.

The scheduler continuously tracks how much CPU time each process has actually received versus how much it is owed, then dispatches whichever process has fallen furthest behind its guaranteed share. This produces a self-balancing allocation that adapts automatically as processes arrive and depart the system.

Fair Share Scheduling extends the guaranteed-allocation principle beyond individual processes to groups of processes, ensuring that CPU time is divided fairly among users or departments rather than treating every process as an independent competitor.

A user or group that spawns many processes should not be able to dominate the CPU simply by virtue of having more runnable tasks. The scheduler therefore allocates a share to each group first, and only then divides that group's share among its own member processes, preventing any single owner from crowding out others regardless of process count.

Earliest Deadline First is a dynamic-priority, preemptive scheduling policy built for real-time systems, in which the process with the closest completion deadline is always given the CPU.

Priorities are recomputed continuously as deadlines approach, so a process's urgency automatically increases relative to its peers over time. EDF is provably optimal for meeting deadlines on a single processor when total system utilization remains within capacity, though it degrades unpredictably under overload conditions, where multiple deadlines may be missed in a cascading fashion.

Rate Monotonic Scheduling assigns fixed, static priorities to periodic real-time tasks based purely on how frequently they must run: the shorter a task's period, the higher its priority.

Because priorities never change once assigned, RMS is simpler to analyze and implement than dynamic schemes like EDF. Its schedulability can be verified in advance using well-established utilization bounds, making it a popular choice for hard real-time systems such as embedded controllers, where predictability and low scheduling overhead are paramount.