CPU Scheduling

Determines the order in which processes or threads are given access to the processor, aiming to optimize various aspects such as CPU utilization, throughput, turnaround time, waiting time, and response time.

CPU scheduling occurs when a process:

• switches from running to waiting
• switches from running to ready
• switches from waiting to ready
• terminates

CPU-I/O Burst Cycle

Process execution alternate between CPU execution and I/O wait.

I/O Burst

The period during which a process is performing input/output operations. CPU will be waiting for the I/O operation to complete.

CPU Burst

The period when a process is actively executing instructions.

Usually CPU short bursts occur at a higher frequency and long bursts occur at a lower frequency.

Scheduler

The component of the operating system responsible for selecting which process runs at any given time.

Job Scheduler

Aka. long-term scheduler. Decides which jobs are admitted to the system for processing. Runs very infrequently. Controls system load. Avoids memory and CPU overload.

Jobs are kept in job pool, which is on disk.

CPU Scheduler

Aka. short-term schedular. Decides which of the ready, in-memory processes is to be executed next by the CPU. Runs per interrupt, per context switch (very frequently).

Medium-term Scheduler

Aka. swapper. Handles swapping processes in and out of memory to improve process mix. Manages RAM pressure and multiprogramming level.

Types of Scheduling

Non-preemptive

When scheduling takes place only under circumstances 1 (running -> waiting) and 4 (terminates). A running process continues to use the CPU until completion or by switching to the waiting state. Processes cannot be interrupted.

Preemptive

When scheduling is not nonpreemptive. Processes can be interrupted. Might cause race conditions. Commonly used in general purpose OSes.

Dispatcher

A module which gives control of the CPU to the process selected by the CPU scheduler.

Handles:

• Switching context
• Switching to user mode
• Jumpting to the proper location in the user program to resume

Scheduling Criteria

• CPU utilization
  CPU must be kept busy as much as posssible. Max is better.
• Throughput
  Number of processes completing execution per time unit. Max is better.
• Turnaround time
  Total time from thread submission to completion. Min is better.
• Waiting time
  Amount of time a CPU waits in ready queue. Min is better.
• Response time
  Total time from thread submission to first output. Min is better.

Event Latency

Amount of time that elapses from when an event occurs to when it is serviced.

Interrupt Latency

Time from interrupt arrival to start of ISR.

Includes:

• Determining interrupt type
• Context switching

Dispatch Latency

Time to stop running process and switch to another.

Includes:

• Preempting a kernel-mode process
• Releasing resources held by low-priority tasks

Algorithms

Chosen based on the specific goals and requirements of the system, such as fairness, efficiency, and responsiveness.

First-Come First-Served

Aka. FCFS. Processes are scheduled in the order they arrive. Non-preemptive. Turnaround and waiting time depends on order of arrival.

Simple. Might cause longer waiting times.

Convoy Effect

Short process behind long process. Causes high turnaround and waiting times.

Shortest Job First

Aka. SJF. The process with the shortest estimated CPU burst is scheduled next. Non-preemptive. Least average waiting time. Optimal. Can cause starvation.

Length of the next CPU burst must be estimated. Exponential averaging can be used for estimation.

$$\tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n$$

Here:

• $t_n$ - duration of $n$-th CPU burst
• $\tau_n$ - predicted duration of $n$-th CPU burst
• $\alpha \in [0,1]$

Shortest Remaining Time First

Aka. SRTF. Preemptive version of SJF. At any time, the process with the smallest remaining CPU burst gets the CPU. If a new process arrives with a smaller remaining time than the current one, it preempts.

Round Robin

Each process is assigned a fixed time slice (quantum) in a cyclic order. Preemptive. Good for time-sharing systems.

Better response times. Higher average turnaround time than SJF. High fairness.

Time quantum must not be too small (causes too many context switches) and not too big (increases response times for shorter tasks).

Priority Scheduling

Each process is assigned a priority. Scheduler runs the highest-priority process. Can be preemptive (interrupted when a high-priority task arrives) or non-preemptive.

Starvation is possible for low priority threads. Can be solved by aging (increasing priority as time goes) the threads.

Note

SJF is also priority scheduling with:

$$\text{Priority} = \frac{1}{\text{Next CPU burst time}}$$

Priority + Round Robin

High priority processes are run first. When 2 process has same priority, round robin is used.

Multilevel Queue Scheduling

Aka. MLQ. Ready queue is split into multiple separate queues. Each queue has a priority and its own scheduling policy. Processes are assigned to different queues based on priority or type.

Multilevel Feedback Queue Scheduling

Aka. MLFQ. Similar to multilevel queue but allows processes to move between queues based on their behavior and requirements.

A new process starts in a high-priority, short-time-slice queue. If it uses too much CPU (acts CPU-bound), it gets pushed down to lower queues. If it waits too long, it may be moved back up (prevents starvation).

High queues have small time slices → good for interactive tasks. Low queues have larger slices or FCFS → good for batch tasks.

Thread Scheduling

When CPU scheduling happens for kernel-level threads, not processes.

System Contention Scope (SCS):

Process-Contention Scope

Aka. PCS. Scheduling scope in which user-level threads compete only with other threads within the same process. Kernel does not schedule these threads individually. User-level thread library chooses which one runs on the process’s available LWPs.

System-Contention Scope

Aka. SCS. Scheduling scope in which kernel-level threads compete with all other threads in the entire system. The kernel scheduler directly manages these threads as independent schedulable entities (kernel threads / LWPs).

Linux, macOS, Windows use only SCS.

Summary

• Multicore and SMT introduce two-level scheduling.
• RMS → static priority based on period.
• EDF → dynamic priority based on deadline.
• POSIX provides FIFO and RR real-time scheduling.