CPU Scheduling

CPU scheduling is a fundamental concept in operating systems. It's the process of deciding which process in the ready queue will be allocated to the CPU next. The goal is to maximize CPU utilization and improve system performance by keeping the CPU as busy as possible. When a process is running, it can be interrupted by a timer interrupt or an I/O interrupt. If the interrupt is a timer interrupt and the process has used up its allocated time slice, it's preempted and returned to the ready queue. If it's an I/O interrupt, the process might move to the waiting queue.

The operating system's scheduler is responsible for choosing the next process to run. This decision is crucial because it affects the overall responsiveness, throughput, and fairness of the system. Different scheduling algorithms exist, each with its own strengths and weaknesses, making them suitable for different types of systems and workloads.

Scheduling Criteria

To evaluate and compare different CPU scheduling algorithms, several criteria are used. These criteria help us understand how effectively a particular algorithm utilizes the CPU and serves the processes. The primary objective is to optimize these criteria.

1. CPU Utilization

This is perhaps the most important criterion. The objective is to keep the CPU as busy as possible, ideally 100% of the time. A system with only user processes running should aim for high CPU utilization. Idle CPU time represents wasted resources.

2. Throughput

Throughput is the number of processes that are completed per unit of time. For example, if 10 processes are completed in 10 seconds, the throughput is 1 process per second. Maximizing throughput is a common goal, especially in batch processing systems where completing a large number of jobs quickly is important.

3. Turnaround Time

Turnaround time is the total time taken by a process from its arrival in the ready queue until its completion. This includes the time spent waiting in the ready queue, the time spent executing on the CPU, and the time spent on I/O operations. Minimizing the average turnaround time is desirable for interactive systems where users expect quick responses.
Turnaround Time = Completion Time - Arrival Time

4. Waiting Time

Waiting time is the total time a process spends waiting in the ready queue. This is the time the process is ready to execute but is not allocated the CPU. Minimizing waiting time is crucial for system responsiveness, as it directly impacts how quickly a process can make progress.
Waiting Time = Turnaround Time - Burst Time (CPU time required by the process)

5. Response Time

Response time is the time from when a request is submitted until the first response is produced. In interactive systems, this is the time from the user's input until the output is displayed. Unlike turnaround time, response time measures the time to the *first* response, not the completion. Minimizing response time is critical for user satisfaction in interactive environments.

6. Fairness

Fairness ensures that each process gets a fair share of the CPU. No process should be starved indefinitely, meaning it never gets to execute. A scheduling algorithm should prevent excessive variation in waiting times among processes.

CPU Scheduling Algorithms

Various algorithms are used for CPU scheduling, each employing a different strategy to select the next process. These algorithms can be broadly categorized into preemptive and non-preemptive types.

1. First-Come, First-Served (FCFS)

This is the simplest scheduling algorithm. Processes are executed in the order they arrive in the ready queue. It's a non-preemptive algorithm, meaning once a process starts executing, it continues until it completes or voluntarily releases the CPU (e.g., for I/O).

Example:

Consider three processes P1, P2, and P3 arriving at times 0, 1, and 2 respectively, with CPU burst times of 24, 3, and 3 units.

• P1 arrives at time 0, starts execution immediately.
• P1 runs for 24 units, completes at time 24.
• P2 arrives at time 1, waits for P1 to finish.
• P2 starts at time 24, runs for 3 units, completes at time 27.
• P3 arrives at time 2, waits for P1 and P2.
• P3 starts at time 27, runs for 3 units, completes at time 30.

Calculations:

• P1: Waiting Time = 0, Turnaround Time = 24
• P2: Waiting Time = 24 - 1 = 23, Turnaround Time = 27 - 1 = 26
• P3: Waiting Time = 27 - 2 = 25, Turnaround Time = 30 - 2 = 28

Average Waiting Time = (0 + 23 + 25) / 3 = 48 / 3 = 16 units.
Average Turnaround Time = (24 + 26 + 28) / 3 = 78 / 3 = 26 units.

Disadvantages:

FCFS suffers from the "convoy effect," where a long process at the front of the queue can cause a significant delay for all subsequent shorter processes, leading to high average waiting times. It's generally not suitable for time-sharing systems.

2. Shortest Job Next (SJN) / Shortest Process Next (SPN)

This algorithm selects the process with the smallest CPU burst time from the ready queue to execute next. It can be implemented as either non-preemptive or preemptive.

Non-Preemptive SJN:

Once a process starts executing, it runs to completion. The scheduler selects the shortest job only when the CPU becomes free.

Example (using the same processes as FCFS):

Processes P1 (burst 24), P2 (burst 3), P3 (burst 3). Arrival times 0, 1, 2.

• At time 0, only P1 is available. P1 starts.
• At time 1, P2 arrives. P1 is still running.
• At time 2, P3 arrives. P1 is still running.
• At time 24, P1 completes. Now, P2 and P3 are in the ready queue. Both have burst time 3. Let's assume FCFS for tie-breaking, so P2 is chosen.
• P2 starts at time 24, runs for 3 units, completes at time 27.
• P3 starts at time 27, runs for 3 units, completes at time 30.

Calculations:

• P1: Waiting Time = 0, Turnaround Time = 24
• P2: Waiting Time = 24 - 1 = 23, Turnaround Time = 27 - 1 = 26
• P3: Waiting Time = 27 - 2 = 25, Turnaround Time = 30 - 2 = 28

Average Waiting Time = (0 + 23 + 25) / 3 = 16 units. (Same as FCFS in this specific scenario due to P1's long initial burst).

Preemptive SJN (Shortest Remaining Time First - SRTF):

If a new process arrives with a CPU burst length less than the remaining time of the currently executing process, the current process is preempted, and the new process is executed.

Example (using the same processes):

Processes P1 (burst 24), P2 (burst 3), P3 (burst 3). Arrival times 0, 1, 2.

• At time 0, P1 arrives (burst 24). P1 starts execution.
• At time 1, P2 arrives (burst 3). P1 has 23 units remaining. Since P2's burst (3) is less than P1's remaining time (23), P1 is preempted. P2 starts.
• At time 2, P3 arrives (burst 3). P2 has 2 units remaining. P3's burst (3) is not less than P2's remaining time (2). So, P2 continues.
• At time 1+3=4, P2 completes. Now, P1 (remaining 23) and P3 (burst 3) are in the ready queue. P3 has the shortest burst. P3 starts.
• At time 4+3=7, P3 completes. The only process left is P1.
• At time 7, P1 resumes execution (remaining 23 units).
• At time 7+23=30, P1 completes.

Calculations:

• P1: Arrived at 0, Ran from 0-1 (1 unit), Preempted. Resumed at 7, Ran until 30. Total Burst = 24. Waiting time = (7-1) = 6. Turnaround Time = 30 - 0 = 30.
• P2: Arrived at 1, Ran from 1-4 (3 units). Waiting time = (1-1) = 0. Turnaround Time = 4 - 1 = 3.
• P3: Arrived at 2, Ran from 4-7 (3 units). Waiting time = (4-2) = 2. Turnaround Time = 7 - 2 = 5.

Average Waiting Time = (6 + 0 + 2) / 3 = 8 / 3 = 2.67 units.
Average Turnaround Time = (30 + 3 + 5) / 3 = 38 / 3 = 12.67 units.

Disadvantages:

SJN/SRTF can lead to starvation of long processes if there is a continuous stream of short processes arriving. It also requires an estimate of the next CPU burst time, which can be difficult to obtain accurately.

3. Round Robin (RR)

Round Robin is a preemptive scheduling algorithm designed especially for time-sharing systems. It's similar to FCFS but adds preemption based on a time slice called a "quantum". Each process gets the CPU for a small time slice (quantum). If the process is still running at the end of its quantum, it is preempted, and the CPU is given to the next process in the ready queue. The preempted process goes to the end of the ready queue.

Example (using the same processes with a quantum of 5):

Processes P1 (burst 24), P2 (burst 3), P3 (burst 3). Arrival times 0, 1, 2.

• Time 0: P1 arrives, starts.
• Time 1: P2 arrives. P1 has 23 remaining. P1 continues.
• Time 2: P3 arrives. P1 has 22 remaining. P1 continues.
• Time 5: P1's quantum expires. P1 has 19 remaining. P1 goes to the end of the ready queue. P2 is next (arrived first among waiting).
• Time 5-8: P2 runs (burst 3). Completes at time 8.
• Time 8: P3 is next.
• Time 8-11: P3 runs (burst 3). Completes at time 11.
• Time 11: P1 is back at the head of the ready queue.
• Time 11-16: P1 runs (quantum 5). P1 has 14 remaining.
• Time 16-21: P1 runs (quantum 5). P1 has 9 remaining.
• Time 21-26: P1 runs (quantum 5). P1 has 4 remaining.
• Time 26-30: P1 runs (remaining 4). Completes at time 30.

Calculations:

• P1: Arrived 0, Ran 0-5, 11-16, 16-21, 21-26, 26-30. Total time on CPU = 5+5+5+5+4 = 24. Turnaround Time = 30 - 0 = 30. Waiting Time = Turnaround Time - Burst Time = 30 - 24 = 6. (It waited from time 5 to 11, and then after each quantum).
• P2: Arrived 1, Ran 5-8. Burst = 3. Turnaround Time = 8 - 1 = 7. Waiting Time = 7 - 3 = 4. (Waited from time 1 to 5).
• P3: Arrived 2, Ran 8-11. Burst = 3. Turnaround Time = 11 - 2 = 9. Waiting Time = 9 - 3 = 6. (Waited from time 2 to 8).

Average Waiting Time = (6 + 4 + 6) / 3 = 16 / 3 = 5.33 units.
Average Turnaround Time = (30 + 7 + 9) / 3 = 46 / 3 = 15.33 units.

Performance Factors:

The performance of RR is highly dependent on the choice of the quantum size.

• Large Quantum: If the quantum is larger than the longest CPU burst, RR essentially becomes FCFS.
• Small Quantum: If the quantum is very small, the overhead of context switching (saving the state of one process and loading the state of another) becomes significant, reducing overall system throughput.

4. Priority Scheduling

In priority scheduling, each process is assigned a priority value. The CPU is allocated to the process with the highest priority. If two processes have the same priority, FCFS is typically used to break the tie. Priorities can be assigned either internally (based on factors like memory usage, I/O burst frequency) or externally (based on user-defined importance).

Priority scheduling can be either preemptive or non-preemptive.

• Preemptive Priority: If a higher-priority process arrives while a lower-priority process is running, the lower-priority process is preempted.
• Non-preemptive Priority: The currently running process continues until it completes or blocks, even if a higher-priority process arrives.

Example (Preemptive Priority Scheduling):

Processes P1, P2, P3, P4, P5 arrive at times 0, 1, 2, 3, 4 respectively. Burst times: P1=10, P2=1, P3=2, P4=1, P5=5. Priorities (lower number = higher priority): P1=3, P2=1, P3=4, P4=5, P5=2.

• Time 0: P1 arrives (priority 3, burst 10). P1 starts.
• Time 1: P2 arrives (priority 1, burst 1). P2 has higher priority than P1. P1 is preempted (9 remaining). P2 starts.
• Time 2: P2 completes. P3 arrives (priority 4, burst 2). Ready queue: P1 (priority 3), P3 (priority 4). P1 has higher priority. P1 resumes.
• Time 3: P4 arrives (priority 5, burst 1). Ready queue: P1 (priority 3), P3 (priority 4), P4 (priority 5). P1 continues.
• Time 4: P5 arrives (priority 2, burst 5). Ready queue: P1 (priority 3), P3 (priority 4), P4 (priority 5), P5 (priority 2). P5 has higher priority than P1. P1 is preempted (4 remaining). P5 starts.
• Time 4-9: P5 runs (burst 5). Completes at time 9.
• Time 9: Ready queue: P1 (priority 3), P3 (priority 4), P4 (priority 5). P1 has highest priority. P1 resumes.
• Time 9-13: P1 runs (remaining 4). Completes at time 13.
• Time 13: Ready queue: P3 (priority 4), P4 (priority 5). P3 has higher priority. P3 starts.
• Time 13-15: P3 runs (burst 2). Completes at time 15.
• Time 15: Ready queue: P4 (priority 5). P4 starts.
• Time 15-16: P4 runs (burst 1). Completes at time 16.

Calculations:

• P1: Arrived 0, Ran 0-1, Resumed 9-13. Burst 10. Turnaround = 13-0 = 13. Waiting = 13-10 = 3.
• P2: Arrived 1, Ran 1-2. Burst 1. Turnaround = 2-1 = 1. Waiting = 1-1 = 0.
• P3: Arrived 2, Ran 13-15. Burst 2. Turnaround = 15-2 = 13. Waiting = 13-2 = 11.
• P4: Arrived 3, Ran 15-16. Burst 1. Turnaround = 16-3 = 13. Waiting = 13-1 = 12.
• P5: Arrived 4, Ran 4-9. Burst 5. Turnaround = 9-4 = 5. Waiting = 5-5 = 0.

Average Waiting Time = (3 + 0 + 11 + 12 + 0) / 5 = 26 / 5 = 5.2.
Average Turnaround Time = (13 + 1 + 13 + 13 + 5) / 5 = 45 / 5 = 9.

Disadvantages:

Starvation: Low-priority processes may never get to execute if there is a continuous supply of high-priority processes. This can be mitigated using aging, where the priority of a process increases over time if it remains in the system for a long duration.

5. Multilevel Queue Scheduling

This algorithm partitions the ready queue into several separate queues, each with its own scheduling algorithm. For example, a common setup is to have a foreground (interactive) queue and a background (batch) queue.

• Inter-queue Scheduling: Scheduling between the queues is typically done using fixed-priority preemptive scheduling. For example, the foreground queue might have a higher priority than the background queue. A process in the foreground queue will always run before a process in the background queue.
• Intra-queue Scheduling: Within each queue, a specific scheduling algorithm is used. For instance, the foreground queue might use Round Robin, while the background queue uses FCFS.

Example:

Foreground Queue (Interactive processes): RR algorithm. Background Queue (Batch processes): FCFS algorithm. Foreground queue has higher priority.

If a process is in the foreground queue, it will be scheduled before any process in the background queue. If the foreground queue is empty, then a process from the background queue is scheduled. If a new process arrives in the foreground queue while a background process is running, the background process is preempted.

Disadvantages:

This approach is inflexible. Processes are permanently assigned to a queue, usually based on some property of the process (e.g., memory size, type of process). Processes do not move between queues.

6. Multilevel Feedback Queue Scheduling

This is a more flexible variation of the multilevel queue scheduling. It allows processes to move between different queues based on their CPU usage behavior. This prevents starvation and allows the scheduler to adapt to changing process characteristics.

• Multiple Queues: Similar to multilevel queues, there are multiple queues, each with a different priority and scheduling algorithm (e.g., RR with different quantum sizes).
• Process Movement: Processes can move up or down in the priority queues.
• A process that uses too much CPU time (e.g., exceeds its quantum in a higher-priority queue) is moved to a lower-priority queue.
• A process that waits too long in a lower-priority queue might be moved to a higher-priority queue (aging).

This algorithm aims to separate processes based on their CPU burst characteristics. Short interactive processes that frequently I/O will tend to stay in the higher-priority queues, while CPU-bound processes will eventually migrate to lower-priority queues.

Example Setup:

Consider three queues:

1. Q1: RR with quantum 8ms
2. Q2: RR with quantum 16ms
3. Q3: FCFS

Rules:

• A new process enters Q1.
• If it doesn't complete within 8ms, it's preempted and moved to Q2.
• If it runs for 16ms in Q2 (and doesn't complete), it's moved to Q3.
• Processes in Q3 are scheduled using FCFS.
• If a process in Q2 or Q3 sends an I/O request, it might be moved back to Q1 (or a higher priority queue).

This setup ensures that short, interactive processes get fast service in Q1, while longer CPU-bound processes gradually move down to Q3, preventing them from monopolizing the CPU.

Thread Scheduling

Thread scheduling is the process of deciding which thread to execute next when multiple threads exist within a process or across different processes. Operating systems can schedule threads in different ways, depending on whether they are user-level threads or kernel-level threads.

User-Level Threads (ULTs)

In ULTs, the kernel is unaware of the threads. Thread management (creation, scheduling, synchronization) is handled by a thread library within the user space.

• Scheduling: The thread library is responsible for scheduling threads within a process. It typically uses an algorithm like Round Robin or priority scheduling among the threads belonging to that process.
• Multiprogramming: If a process with multiple ULTs is running on a CPU, and one of its threads makes a blocking system call (e.g., for I/O), the entire process blocks because the kernel only sees one entity.
• Multiprocessor: ULTs cannot be run in parallel on multiple processors. If a process has 5 ULTs, it can only run on one CPU at a time.

Kernel-Level Threads (KLTs)

In KLTs, the operating system kernel is aware of the threads. The kernel manages thread creation, scheduling, and synchronization.

• Scheduling: The kernel schedules threads directly. It can schedule threads from different processes on different CPUs.
• Blocking System Calls: If one KLT makes a blocking system call, only that thread is blocked. Other threads within the same process can continue to run on other CPUs or after the blocked thread is rescheduled.
• Multiprocessor: KLTs can run in parallel on multiple processors, significantly improving performance for multithreaded applications.

Hybrid Approaches (e.g., Many-to-One, One-to-One, Many-to-Many)

These models combine aspects of ULTs and KLTs to leverage their advantages.

• Many-to-One: Multiple user threads map to a single kernel thread (like ULTs). Simpler but suffers from blocking and lack of parallelism.
• One-to-One: Each user thread maps to a separate kernel thread (like KLTs). Allows parallelism and avoids blocking but can create many kernel threads, leading to overhead.
• Many-to-Many: A multiplexing approach where a smaller or equal number of kernel threads support a larger number of user threads. Offers a balance between the two.

The scheduling decision for threads depends on the model used. In One-to-One and Many-to-Many models, the kernel's thread scheduler is involved, using algorithms like RR or priority scheduling for threads.

Multiprocessor Scheduling

Multiprocessor scheduling is more complex than single-processor scheduling because it involves multiple CPUs. The main challenge is how to distribute processes or threads across available processors to maximize performance and resource utilization.

Approaches to Multiprocessor Scheduling

1. Asymmetric Multiprocessing (AMP): One processor is designated as the master processor and handles all system tasks, including scheduling. Other processors (slave processors) only execute processes assigned to them. The master processor is a potential bottleneck.
2. Symmetric Multiprocessing (SMP): Each processor is self-scheduling. All processes and threads share a common ready queue, and any processor can pick any process from the queue. This is the most common approach.

Scheduling Issues in SMP

1. Load Balancing: Keeping all processors equally busy is crucial. If one processor is overloaded while others are idle, the system's performance suffers. Load balancing strategies aim to distribute the workload evenly.
2. Processor Affinity: When a process or thread runs on a particular CPU, it often leaves data in its cache. If the process is moved to another CPU, this cached data becomes useless, leading to cache misses and slower execution. Processor affinity (or CPU affinity) tries to keep a process running on the same CPU.

• Soft Affinity: The OS tries to keep a process on the same processor but doesn't guarantee it.
• Hard Affinity: The process is strictly bound to a specific CPU.

3. Mutual Exclusion: When multiple processors access shared data structures (like the ready queue or kernel data), proper synchronization mechanisms (like locks or semaphores) are needed to prevent race conditions and ensure data integrity.

Multiprocessor Scheduling Algorithms

Common algorithms are extensions of single-processor algorithms, often with a focus on balancing load and maintaining affinity.

• Global Scheduling: A single ready queue for all processors. Processes are scheduled from this queue onto any available CPU. This offers good load balancing but can cause more frequent context switches and loss of cache affinity.
• Local Scheduling: Each processor maintains its own private ready queue. Processes are scheduled only onto their assigned processor. This improves cache affinity but can lead to load imbalance.
• Hybrid Scheduling: Combines global and local scheduling. For example, a process might be assigned to a pool of processors and scheduled globally within that pool.

Many modern operating systems use SMP with a global scheduling approach, employing sophisticated techniques to manage affinity and synchronization to achieve high performance.

Real-Time Scheduling

Real-time operating systems (RTOS) are designed to process data and events within strict time constraints. The correctness of a system depends not only on the logical result of computation but also on the time at which these results are produced.

Types of Real-Time Systems

1. Hard Real-Time Systems: These systems have very strict deadlines. Missing a deadline is considered a system failure. Examples include medical monitoring systems, flight control systems, and industrial automation.
2. Soft Real-Time Systems: These systems have deadlines, but missing them occasionally is acceptable. The system's quality of service degrades, but it doesn't lead to catastrophic failure. Examples include multimedia streaming, online gaming, and data acquisition systems.

Real-Time Scheduling Criteria

The primary goal is to meet deadlines. Other criteria include:

• Predictability: The system's behavior must be predictable and deterministic.
• Determinism: The time taken for specific operations should be known and bounded.
• Latency: The time taken to respond to an event must be minimal and bounded.

Real-Time Scheduling Algorithms

These algorithms are designed to guarantee or maximize the probability of meeting deadlines.

1. Rate Monotonic Scheduling (RMS)

RMS is a preemptive, static-priority scheduling algorithm used for periodic tasks.

• Priority Assignment: Tasks with shorter periods (higher rates) are assigned higher priorities. The priority is fixed (static).
• Optimality: RMS is optimal among static-priority algorithms. If a set of periodic tasks can be scheduled by any static-priority algorithm, it can also be scheduled by RMS.
• Schedulability Test: A mathematical test (like the Liu & Layland bound) can determine if a task set is schedulable under RMS. For n tasks, if the sum of their utilization (Ci/Ti, where Ci is computation time and Ti is period) is less than or equal to n(2^(1/n) - 1), the tasks are guaranteed to be schedulable. As n approaches infinity, this bound approaches ln(2) ≈ 0.693.

Example:

Task A: Period = 10ms, Computation = 3ms. Utilization = 3/10 = 0.3. Task B: Period = 20ms, Computation = 5ms. Utilization = 5/20 = 0.25. Total Utilization = 0.3 + 0.25 = 0.55. Number of tasks (n) = 2. Liu & Layland bound = 2 * (2^(1/2) - 1) = 2 * (1.414 - 1) = 2 * 0.414 = 0.828. Since 0.55 <= 0.828, the tasks are schedulable by RMS. Task A (higher rate) gets higher priority.

2. Earliest Deadline First (EDF)

EDF is a dynamic-priority scheduling algorithm.

• Priority Assignment: The task with the earliest absolute deadline (current time + relative deadline) is assigned the highest priority. Priorities are dynamic and can change as deadlines approach.
• Optimality: EDF is optimal among all dynamic-priority algorithms. If a set of tasks can be scheduled by any algorithm, it can be scheduled by EDF.
• Schedulability Test: A set of periodic tasks is schedulable by EDF if and only if the total utilization is less than or equal to 1 (Sum of Ci/Ti <= 1).

Example:

Task A: Period = 10ms, Computation = 3ms. Utilization = 0.3. Task B: Period = 20ms, Computation = 5ms. Utilization = 0.25. Total Utilization = 0.55. Since 0.55 <= 1, the tasks are schedulable by EDF.

Consider deadlines: At time 0, both A and B arrive. A's deadline: 0 + 10 = 10. B's deadline: 0 + 20 = 20. EDF schedules A first. At time 3, A completes. B runs. At time 8, B completes. At time 10, A arrives again. Its deadline is 10 + 10 = 20. B is still running (from 8). At time 13, B completes (ran for 5ms). At time 10, A is running. At time 20, A arrives again. Its deadline is 20 + 10 = 30. At time 20, B arrives again. Its deadline is 20 + 20 = 40. EDF schedules A.

3. Proportional Share Scheduling

This algorithm attempts to provide each process with a certain share of the CPU. It's more about resource allocation fairness over time rather than strict deadline guarantees. It's often used in systems where multiple users or applications need predictable performance.

Challenges in Real-Time Scheduling

• Jitter: Variations in task execution times or arrival times can cause deadlines to be missed.
• Priority Inversion: A high-priority task can be blocked by a lower-priority task holding a resource it needs. This is a critical problem in real-time systems and is often solved using mechanisms like Priority Inheritance Protocol or Priority Ceiling Protocol.