Scheduling

The primary objective of the OS scheduler is to choose the next task to run from the ready queue and dispatch it onto the CPU. The data structure central to this operation is the runqueue (also known as the ready queue), which holds all the tasks ready for execution. The design of the runqueue is tightly coupled with the chosen scheduling algorithm.

Run To Completion is a non-preemptive scheduling model where, once a task is assigned to a CPU, it runs until it is completely finished. Two common algorithms that follow this model are First Come First Serve (FCFS), which schedules tasks in the order of their arrival, and Shortest Job First (SJF), which schedules tasks based on the shortest execution time.

Priority inversion is a scenario where a high-priority task is forced to wait for a lower-priority task to release a required resource, such as a mutex. A common solution is priority boosting, where the scheduler temporarily raises the priority of the resource-holding (lower-priority) task to that of the waiting (higher-priority) task. This allows the lower-priority task to run, release the resource, and then have its priority returned to its original level.

Round Robin is a scheduling policy where tasks of the same priority are scheduled in a rotating, FCFS-like manner. It is enhanced by "timeslicing," a mechanism that interrupts a running task after a set period (a timeslice or time quantum). This allows the scheduler to switch to the next task, ensuring that all tasks are interleaved and get a share of the CPU, which improves system responsiveness.

CPU-bound tasks prefer longer timeslices to minimize the overhead from frequent context switching, thereby maximizing CPU utilization and throughput. Conversely, I/O-bound tasks prefer shorter timeslices, as this allows them to issue I/O requests quickly and keep both the CPU and I/O devices highly utilized, which improves perceived performance by keeping wait times low.

An MLFQ uses multiple queues, each with a different priority level and often a different timeslice length, to categorize tasks based on their behavior. New tasks start in the highest-priority queue (with the shortest timeslice); if a task uses its full timeslice, it is demoted to a lower-priority queue. This feedback mechanism allows the scheduler to learn over time whether a task is I/O-bound (staying in high-priority queues) or CPU-bound (moving to low-priority queues).

The Linux O(1) scheduler is a preemptive, priority-based scheduler that can add or select a task in constant time. It uses two arrays, active and expired, for its runqueue; tasks are scheduled from the active array until it is empty, at which point the arrays are swapped. It uses feedback based on how long a task sleeps to adjust its priority dynamically, boosting interactive tasks and lowering the priority of computationally intensive ones.

The core principle of the Linux CFS scheduler is to provide fairness by ensuring that over a given time interval, each task runs for an amount of time relative to its priority. CFS tracks the vruntime (virtual runtime) of each task and always schedules the task with the lowest vruntime. It uses a self-balancing red-black tree as its runqueue, which allows it to find the task with the minimum vruntime in constant time and add a task in logarithmic time.

Cache affinity is the principle that a process runs faster if it is scheduled on the same CPU it previously ran on, because its state is already present in that CPU's caches. To achieve this, a hierarchical scheduling architecture is used, featuring a high-level load balancer that divides tasks among CPUs. Each CPU then has its own scheduler and runqueue, responsible for scheduling its assigned tasks, which minimizes task migration between CPUs.

Hyperthreading (also called simultaneous multithreading or SMT) is a hardware feature where a single CPU has multiple sets of registers, allowing it to maintain multiple hardware-supported execution contexts and switch between them very quickly. The optimal strategy for maximizing utilization is to co-schedule a mix of memory-bound and CPU-bound threads. This approach hides memory access latency and minimizes contention for the processor pipeline, keeping both CPU and memory components well-utilized.

Modern processors have hardware counters that track execution metrics like cache misses (L1, L2, LLC) and Instructions Per Cycle (IPC) with minimal overhead. Schedulers can access this data through software interfaces to make informed decisions. For example, a high number of Last-Level Cache (LLC) misses can indicate that a thread is memory-bound, allowing the scheduler to pair it with a CPU-bound thread for better system utilization.

The experiments simulating threads with different Cycles Per Instruction (CPI) values concluded that scheduling tasks with mixed CPI values leads to higher platform utilization. Co-scheduling threads with similar CPIs (e.g., all CPU-bound or all memory-bound) on the same core leads to poor utilization due to resource contention or idling. A balanced mix of high-CPI (memory-bound) and low-CPI (CPU-bound) threads ensures the processor pipeline is better utilized, resulting in a higher overall IPC.

The main goal of a proportional-share (or fair-share) scheduler is to guarantee that each job obtains a certain percentage of CPU time, rather than optimizing for turnaround or response time. Lottery scheduling implements this by assigning "tickets" to each process; the percentage of total tickets a process holds represents its share of the CPU. The scheduler then holds a lottery to probabilistically select which process runs next.

Randomized approaches have three key advantages. First, they avoid corner-case behaviors that can cause worst-case performance in deterministic algorithms. Second, they are lightweight and require minimal state to track alternatives. Third, they can be very fast, as making a decision is as quick as generating a random number.

Ticket currency allows a user to allocate tickets to their own jobs in a local currency, which the system then converts to a global ticket value. For example, User A might give their two jobs 500 tickets each (in A's currency), while User B gives their single job 10 tickets (in B's currency). If both users have 100 global tickets, the system converts A's jobs to 50 global tickets each and B's job to 100 global tickets, and the lottery is held over these global values.

Two other useful mechanisms are ticket transfer and ticket inflation. Ticket transfer allows a process to temporarily hand off its tickets to another process, which is useful in client/server interactions to speed up the server's work. Ticket inflation allows a process in a trusted environment to temporarily raise or lower its own ticket count to signal its current need for more or less CPU time.

To make a scheduling decision, the scheduler first picks a random "winning ticket" number between 0 and the total number of tickets. It then iterates through a data structure of processes (commonly a list), summing up their ticket counts until the cumulative sum exceeds the winning number. The process that causes the sum to exceed the winner is the one selected to run.

Stride scheduling is a deterministic alternative to lottery scheduling. Each job is assigned a "stride" value, which is inversely proportional to its number of tickets, and a "pass" value, which is a counter that tracks its progress. The scheduler always picks the process with the lowest pass value to run, and after running, increments that process's pass value by its stride, ensuring proportions are met exactly over time.

The primary advantage of lottery scheduling is that it is stateless regarding individual processes' progress, whereas stride scheduling must maintain a pass value for each job. When a new job enters, lottery scheduling simply adds its tickets to the total and proceeds, making it easy to incorporate new processes sensibly. In stride scheduling, determining the correct initial pass value for a new job is complex and can lead to it either monopolizing the CPU or being starved.

The core principle of CFS is to fairly divide the CPU among all competing processes. It achieves this using a counting-based technique called "virtual runtime" (vruntime), which tracks the amount of time a process has run. When making a scheduling decision, CFS always picks the process with the lowest vruntime to run next.

CFS uses sched_latency to determine a target time window over which all processes should run at least once. It divides this value by the number of running processes to determine a time slice, but to prevent excessive context switching with many processes, it enforces a floor on this value with min_granularity. This ensures that the time slice never becomes too small, balancing near-term fairness with CPU efficiency.

CFS maps a process's nice value (-20 to +19) to a specific weight. This weight is used to scale the rate at which the process's vruntime accumulates; a higher-priority process (lower nice value) has a larger weight, so its vruntime increases more slowly. This causes CFS to pick it more often, effectively giving it a larger share of the CPU.

CFS uses a red-black tree to store all runnable processes, ordered by their vruntime. A red-black tree is a balanced binary search tree, which ensures that operations like insertion and deletion are logarithmic in time, O(log n). This is far more efficient and scalable than searching a simple list, which is an O(n) operation, especially on modern systems with thousands of processes.

When a process that was sleeping wakes up, its vruntime will be much lower than that of continuously running processes. To prevent this newly-awakened process from starving others, CFS does not use its old vruntime. Instead, it sets the process's vruntime to the minimum value currently found in the red-black tree of running jobs.

The MLFQ scheduler tries to simultaneously optimize two conflicting goals without a priori knowledge of job length. First, it aims to optimize turnaround time by running shorter jobs first. Second, it aims to minimize response time to make the system feel responsive to interactive users.

The first two rules establish the core scheduling logic. Rule 1 states that if the priority of job A is greater than the priority of job B, job A runs and job B does not. Rule 2 states that if job A and job B have the same priority, they are run in a Round-Robin (RR) fashion.

An MLFQ scheduler operates on the assumption that a new job might be a short, interactive one, so it places it at the highest priority level (Rule 3). If the job repeatedly uses its entire time allotment (a sign of being CPU-intensive), the scheduler reduces its priority, moving it down the queue hierarchy (Rule 4a). This approach allows MLFQ to learn about a job's characteristics as it runs.

The intent of Rule 4b is to favor interactive jobs that frequently perform I/O operations, such as waiting for keyboard input. By relinquishing the CPU before using their full time slice, these jobs demonstrate interactive behavior. The rule prevents them from being penalized with a lower priority, thus keeping the system responsive.

Starvation occurs when there are so many high-priority interactive jobs that lower-priority, long-running jobs never get to run. To solve this, a priority boost mechanism is introduced (Rule 5). Periodically, the scheduler moves all jobs in the system to the topmost queue, guaranteeing that even long-running jobs get a chance to run.

A user can game the scheduler by tricking it into giving their process more than its fair share of the CPU. A program can achieve this by issuing a trivial I/O operation just before its time allotment expires. This relinquishes the CPU, and under the basic rules, allows the process to remain in a high-priority queue, effectively monopolizing the CPU over time.

To prevent gaming, the rules for priority adjustment are refined into a single, more robust rule (the new Rule 4). This rule states that once a job uses up its total time allotment at a given level, its priority is reduced. This accounting is cumulative, so it does not matter if the time is used in a single long burst or many short ones interrupted by I/O.

The priority boost mechanism periodically moves all jobs in the system to the highest-priority queue. This solves two key problems simultaneously. First, it prevents the starvation of long-running, low-priority jobs by guaranteeing they will eventually run. Second, it gracefully handles jobs that change their behavior over time, such as a CPU-bound process that becomes interactive.

A "voo-doo constant" is a system parameter that is critical to performance but has no obvious or scientifically derivable correct value, appearing to require "black magic" to set correctly. In MLFQ, the time period S for the priority boost is a prime example. If S is too high, jobs can starve; if it is too low, interactive jobs may not get a proper share of the CPU.

Most MLFQ variants assign shorter time slices to high-priority queues and longer time slices to low-priority queues. The reasoning is that high-priority queues are expected to contain interactive jobs, which benefit from rapid switching and good response time. Low-priority queues contain CPU-bound jobs, for which longer quanta are more efficient as they reduce context-switching overhead.

The five rules are: 1) Higher priority runs first. 2) Equal priority jobs run in Round-Robin. 3) New jobs enter at the highest priority. 4) A job's priority is reduced once it uses its total time allotment at a level. 5) After a period S, all jobs are moved to the highest priority queue.

MLFQ achieves its goals by observing a job's behavior over time and using that history to predict its future needs. It initially gives all jobs high priority, which benefits short, interactive jobs by giving them good response time. CPU-intensive jobs are identified as they repeatedly consume their time slices and are moved to lower-priority queues, approximating an SJF-like behavior for optimizing turnaround time.

Temporal locality is the principle that if a piece of data is accessed, it is likely to be accessed again soon. Spatial locality is the principle that if data at address x is accessed, data near x is also likely to be accessed soon. CPU caches are effective because they exploit these principles by storing recently and frequently accessed data in a small, fast memory, making subsequent accesses much quicker.

The cache coherence problem arises when multiple CPUs maintain their own caches of a shared memory, leading to situations where one CPU's cache holds a stale value of data that has been updated in another CPU's cache. A basic hardware solution is bus snooping, where each cache monitors the shared memory bus. When a cache sees an update to a data item it holds, it can either invalidate its own copy or update it with the new value.

Hardware coherence only ensures that individual memory locations have a consistent view, it does not guarantee the atomicity of multi-instruction operations required to update complex data structures. Without synchronization primitives like locks, concurrent updates from different CPUs can lead to race conditions. For example, two threads might try to remove the same element from a linked list, corrupting the list's structure.

Cache affinity is the concept that a process runs more efficiently when it remains on the same CPU, because it builds up state (data and instructions) in that CPU's caches. If the process is moved to a different CPU, this cached state is lost and must be reloaded from main memory, which degrades performance. Therefore, a multiprocessor scheduler should try to keep processes on the same CPU to leverage this benefit.

SQMS is a multiprocessor scheduling approach that uses a single, shared queue for all jobs across all CPUs. Its first major shortcoming is a lack of scalability, as the single queue requires locking for synchronization, which becomes a performance bottleneck as the number of CPUs increases. Its second shortcoming is poor cache affinity, as jobs tend to bounce between different CPUs, preventing them from benefiting from warm caches.

MQMS is an approach where each CPU has its own private scheduling queue. Its main advantages over SQMS are better scalability and intrinsic support for cache affinity. Since each queue is managed independently, there is no centralized lock contention, and because jobs are assigned to a specific CPU's queue, they naturally remain on that CPU.

The fundamental problem with MQMS is load imbalance. This occurs when jobs are not distributed evenly across the per-CPU queues, for example, if one job finishes, leaving its CPU's queue with fewer jobs than others. This can lead to situations where some CPUs are overworked while others are idle, resulting in poor overall system utilization.

Job migration solves the problem of load imbalance by moving jobs from an overworked CPU's queue to an underworked or idle CPU's queue. By dynamically rebalancing the workload across all CPUs, migration ensures that the system's processing power is utilized more evenly and efficiently.

Work stealing is a technique where a queue with few jobs (the source) will proactively look at another, more heavily loaded queue (the target). If the target queue is significantly fuller, the source queue will "steal" one or more jobs from it. This decentralized approach allows for load balancing without a central coordinator.

The key tension in work stealing is balancing the overhead of checking other queues against the risk of load imbalance. If queues check on each other too frequently, the system suffers from high overhead, defeating the purpose of having multiple queues. If they check too infrequently, severe load imbalances can persist, leading to inefficient CPU utilization.

The text mentions three Linux schedulators. The O(1) scheduler and the Completely Fair Scheduler (CFS) are both multi-queue schedulers. The BF Scheduler (BFS) is a single-queue scheduler.

The O(1) scheduler is a priority-based scheduler, similar to MLFQ, which aims to meet objectives like interactivity by dynamically adjusting process priorities over time. In contrast, CFS is a deterministic proportional-share scheduler, similar to Stride scheduling, which focuses on providing fair CPU allocation based on process weights rather than explicit priority levels.

Turnaround time is a performance metric defined as the total time a job spends in the system. It is calculated as the time at which the job completes minus the time at which the job arrived. More formally, T_turnaround = T_completion - T_arrival.

First In, First Out (FIFO) is a simple, non-preemptive scheduling algorithm that processes jobs in the order they arrive. Its major problem is the "convoy effect," which occurs when a long-running job arrives before several shorter jobs. The shorter jobs are forced to wait in a queue behind the "heavyweight" job, leading to a high average turnaround time.

The Shortest Job First (SJF) algorithm is a non-preemptive policy that runs the shortest job first, followed by the next shortest, and so on. By prioritizing short jobs, it ensures they complete quickly instead of getting stuck behind long jobs. This directly mitigates the convoy effect and significantly reduces the average turnaround time compared to FIFO when job lengths vary.

A preemptive scheduler is one that can stop a currently running process to run another one, using mechanisms like context switching. STCF is a preemptive version of SJF; whenever a new job enters the system, STCF compares its remaining time to the remaining time of the currently running job. If the new job is shorter, the scheduler preempts the current job and runs the new one.

Response time is the time from when a job arrives in the system to the first time it is scheduled to run (T_response = T_firstrun - T_arrival). Schedulers like STCF are poor for response time because they are non-interactive and run jobs to completion (or until a shorter job arrives). If several jobs arrive together, later jobs must wait for all shorter jobs to finish completely before they get to run even once.

Round-Robin (RR) is a preemptive scheduling algorithm designed for good response time. It runs a job for a fixed duration called a "time slice" or "quantum" and then switches to the next job in the queue. It cycles through all ready jobs in this manner, ensuring that no job has to wait long before being scheduled for the first time.

The trade-off is between responsiveness and efficiency. A very short time slice improves response time but increases the overhead from frequent context switching, which wastes CPU cycles. A long time slice reduces this overhead (amortizing the cost) but makes the system less responsive, behaving more like a FIFO scheduler.

There is an inherent trade-off between scheduling metrics. Policies like Round-Robin that are "fair" (evenly dividing the CPU on small time scales) achieve good response time but perform poorly on turnaround time because they stretch out every job's execution. Conversely, "unfair" policies like SJF that prioritize certain jobs can achieve excellent turnaround time but at the cost of poor response time for longer jobs.

When a process initiates an I/O operation, it becomes blocked and cannot use the CPU. A scheduler can improve system utilization by scheduling another, CPU-ready job to run during this I/O wait time. This practice of overlapping CPU work with I/O operations ensures the processor does not sit idle, leading to higher overall system efficiency.

To handle I/O, a scheduler can treat each CPU burst of a job as a separate, independent job. For an I/O-bound job, this means it is seen as a series of short CPU tasks. An STCF scheduler would then prioritize these short CPU bursts over longer CPU-bound jobs, allowing the interactive job to run, issue its next I/O, and let the CPU-bound job run while the I/O completes.

The most unrealistic assumption is that the run-time of each job is known to the scheduler in advance. In a general-purpose operating system, the OS has no such oracle or a priori knowledge. This makes implementing perfect SJF or STCF impossible in a real-world system.

Round-Robin performs poorly on turnaround time because it only cares about giving every job a fair, quick turn on the CPU, not about finishing jobs quickly. By switching between all active processes, it actively stretches out the completion time of every single job as long as possible. Since turnaround time only measures when a job is fully complete, this "stretching" leads to a high average.