OS - CPU Scheduling

CPU Utilization

The percentage of time the CPU is being used.

Turnaround-Time

The time between the process being loaded and finishing its execution.

System Throughput

The number of processes completed per unit of time.

Waiting Time

Sum of time spent waiting in the Ready-Queue while another process is running.

Response Time

Amount of time between when the user does an action and when they see a response.

Fairness

Each process should get an equitable use of the CPU.

Preemptive-Scheduling Category

May interrupt the current process to dispatch the CPU to another process.:

- Interrupt-Event Driven

- Time-based

Non-Preemptive Scheduling Category

We wait for the current process to be done before dispatching the CPU to another process.

What causes starvation in CPU scheduling?

1. Infinite blocking

2. Infinite incoming processes

FCFS

Processes are executed in the order in which they arrive. Non-preemptive in nature

Pros of FCFS

1. Fair, as in, first come first serve principle.

2. Simple to implement (literally a queue)

3. Resolves the infinite-arrival starvation.

Cons of FCFS

Low Performance as a long CPU job could make al the other processes wait for a long-time.

Infinite-Blocking

A process infinitely-loops, causing the process to infinitely hog the CPU.

Infinite-Arrival

A continuous stream of newly arriving processes keeps getting selected ahead of an existing process, so that process is never chosen to run.

Shortest-Job First Principle

We execute the shortest-CPU jobs in increasing-order. Seen in both preemptive and non-preemptive.

Shortest Remaining Time First (SRFT)

Currently executing process may be interrupted by the new arrival of a process.

1. Low CPU burst time > arrival time gets priority.

Pros of SRFT

Low-CPU processes get executed first, which is more efficient than sequentially going through processes in a queue.

Cons of SRFT

1. Can lead to infinite-arrival as new processes keep interrupting, which prevents any process from being completed.

Turnaround Time

Completion Time - Arrival Time

Tie-breaker for SRFT and FCFS

If two processes have the same CPU burst time, we prioritize the one who arrived earlier.

Priority Scheduling Algorithim

Processes get an attached priority number that can be based on anything the user wants to prioritize. This can be based on CPU utilization ratio, time, random number, etc.

Round-Robin

The classic time-slicing concurrency algo.

Multi-level Queue

Multi-Level Feedback

CPU-hoggers get demoted (lower priority) while CPU-waiters get promoted (get higher priority).

Scheduler Components

Long, medium, short scheduler

Long Scheduler

It decided which newly created process gets admitted first.

Medium Scheduler

Swaps process from RAM to disk and vice versa.

Short Scheduler

It decides which process should be acted on by the CPU. Uses a set algorithim like SRFT, FCFS, etc.

Pros of Priority

1. We can differentiate based on semantic importance.

2. Allows preemptive & non-preemptive

Cons of Priority

1. Subject to both infinite-blocking and infinite-arrival starvations.

Pros of Round-Robin

1. Starvation Free (Everyone gets a turn)

2. Provides fairness

3. Establishes an upper-bound

Cons of Round-Robin

1. If time-quantum too large, it degrades to a FCFS algorithm

What if the time quantum is too small in Round-Robin scheduling?

We spend more time context-switching than actually working on processes.

Round-Robin Ratio

(dispatch latency) / (time-quantum + dispatch latency)

Multilevel Processing

We have multiple queues that may have different dispatch algorithms.