CPU scheduling
Preemptive
In preemptive scheduling, the CPU can be taken away from a running process if
a higher priority process arrives.
The OS forcibly switches the CPU from one process to another.
Example: Imagine two processes:
P1 with burst time 8
P2 with burst time 4 (arrives after 2 units)
If P1 is running and P2 (with higher priority or shorter time) arrives, P1 will be
paused, and P2 will run first.
Preemptive Scheduling Algorithms:
1. Round Robin (RR)
2. Shortest Remaining Time First (SRTF)
3. Preemptive Priority Scheduling
etc.
Non - preemptive
In non-preemptive scheduling, once a process starts executing, it runs till
completion.
The CPU is not taken away even if another higher priority process arrives.
Example: P1 with burst time 8
P2 with burst time 4 (arrives after 2 units)
Even if P2 arrives, P1 will not be interrupted. P2 has to wait until P1 finishes.
Non-Preemptive Scheduling Algorithms:
1. First Come First Serve (FCFS)
2. Shortest Job First (SJF)
3. Non-Preemptive Priority Scheduling
etc.
Scheduling criteria
Scheduling criteria are the set of rules or goals used to measure the performance
and efficiency of CPU scheduling algorithms in an Operating System.
These help the OS decide which scheduling algorithm is better for a given
situation.
Arrival Time (AT)
The arrival time is the time at which a process enters the ready queue
(i.e., when it becomes ready for execution).
If a process P1 arrives in the system at time 2, its arrival time = 2.
Burst Time (BT)
Burst Time is the total time required by a process to execute on the
CPU without [Link]’s the actual processing time of a process.
If process P1 needs 5 units of CPU time to complete,
then Burst Time = 5
Completion Time (CT)
Completion Time is the time at which a process finishes its execution on the CPU.
Turnaround Time (TAT)
Turnaround Time is the total time taken by a process from arrival to completion.
TAT = CT - AT
Waiting Time (WT)
Time a process waits in the ready queue before getting the CPU.
WT = TAT - BT
Response Time (RT)
Time between arrival of a process and the first time it gets the CPU.
Response Time = Start Time - Arrival Time
Note: RT ≠ WT if the process is preempted.
FCFS (First-Come, First-Served)
In FCFS, the process that arrives first in the ready queue is executed first. It
is a non-preemptive scheduling algorithm.
How It Works:
The CPU is assigned to the process that arrives first.
Once a process starts execution, it runs till completion.
Other processes wait in the queue.
Example:
Process Arrival Time Burst Time
P1 0 ms 4 ms
P2 1 ms 3 ms
P3 2 ms 1 ms
Execution order: P1 → P2 → P3
SJF (Shortest Job First)
SJF is a CPU scheduling algorithm where the process with the shortest burst
time is executed first. It can be non-preemptive or preemptive (also called
Shortest Remaining Time First in that case).
How It Works (Non-Preemptive):
Among all the processes that have arrived, the one with the least burst time is
selected.
Once a process starts, it runs till completion.
Example :
Process Arrival Time Burst Time
P1 0 ms 8 ms
P2 1 ms 4 ms
P3 2 ms 2 ms
P4 3 ms 1 ms
Step-by-step Execution -
At time 0: only P1 is available → Run P1
P1 RUNS FROM 0 TO 8
At time 8: P2, P3, and P4 have arrived → P4 has the shortest burst time → Run P4
P4 runs from 8 to 9
Then P3 (2 ms) → runs from 9 to 11
Then P2 (4 ms) → runs from 11 to 15
SRTF (Shortest Remaining Time First)
SRTF is the preemptive version of SJF (Shortest Job First).
At any moment, the CPU is given to the process that has the least remaining
burst time.
How It Works:
When a new process arrives, if it has a shorter remaining time than the current
running process, the CPU is preempted (interrupted) and the new process runs.
Example :
Process Arrival Time Burst Time
P1 0 ms 8 ms
P2 1 ms 4 ms
P3 2 ms 2 ms
P4 3 ms 1 ms
Execution Steps:
Time 0: Only P1 → Run P1
Time 1: P2 arrives (4 ms < 7 remaining of P1) → Switch to P2
Time 2: P3 arrives (2 ms < 3 remaining of P2) → Switch to P3
Time 3: P4 arrives (1 ms < 1 remaining of P3) → Switch to P4
Time 4: P4 finishes → Go back to P3 (1 ms left)
Time 5: P3 finishes → Go back to P2 (3 ms left)
Time 8: P2 finishes → P1 resumes (7 ms left)
Time 15: P1 finishes
RR (Round Robin)
Round Robin (RR) is a preemptive CPU scheduling algorithm.
Each process is given a fixed time slice called a time quantum.
If a process doesn't finish in its time quantum, it's interrupted and added back
to the end of the queue.
How It Works:
1. All processes are placed in a ready queue.
2. The CPU runs a process for a fixed time (e.g., 2 ms).
3. If the process finishes within the quantum, it's removed.
4. If not, it's paused and moved to the end of the queue.
Example:
Assume Time Quantum = 2 ms
Process Arrival Time Burst Time
P1 0 ms 5 ms
P2 1 ms 3 ms
P3 2 ms 1 ms
Step-by-Step Execution:
Time 0: P1 runs for 2 ms → 3 ms left
Time 2: P2 runs for 2 ms → 1 ms left
Time 4: P3 runs for 1 ms → finishes
Time 5: P1 runs for 2 ms → 1 ms left
Time 7: P2 runs for 1 ms → finishes
Time 8: P1 runs for 1 ms → finishes
Priority Scheduling Algorithm
Priority Scheduling is a CPU scheduling algorithm where each process is
assigned a priority, and the CPU is given to the process with the highest
priority (lowest number = highest priority).
How It Works:
Processes are scheduled based on priority values.
If two processes have the same priority, FCFS is used to decide.
It can be either:
Preemptive: If a new process arrives with a higher priority, it interrupts the
current one.
Non-Preemptive: Once a process starts, it runs till completion, even if a
higher-priority one arrives.
Example:
Process Arrival Time Burst Time Priority
P1 0 ms 4 ms 2
P2 1 ms 3 ms 1
P3 2 ms 1 ms 3
Step-by-Step Execution: (Non-Preemptive)
Time 0: Only P1 is available → Run P1
Time 4: P2 and P3 are in the queue → P2 has higher priority → Run P2
Time 7: Run P3
Execution: (Preemptive)
Time 0: P1 arrives → starts running
Time 1: P2 arrives (higher priority than P1) → preempts P1, P2 runs from 1 to 4
Time 4: P1 resumes → runs from 4 to 7
Time 7: P3 runs from 7 to 8
Multiple Processor Scheduling
Multiple Processor Scheduling is used in computer systems that have more
than one CPU. The Operating System decides which process will run on
which processor.
two types -
1. Symmetric Multiprocessing (SMP)
In SMP, all processors are equal. They share the same memory and run the
same copy of the operating system.
All CPUs work together and are treated equally.
Each CPU has access to the same memory and I/O devices.
Each CPU runs its own copy of the scheduler.
Processes can be run on any CPU.
Example: Windows, Linux, Android.
High reliability (if one CPU fails, others can continue).
2. Asymmetric Multiprocessing (AMP)
In AMP, one CPU is the master, and the others are slaves. Only the master
CPU controls all system activities.
Master CPU manages the system and assigns tasks.
Slave CPUs only perform tasks given by the master.
Simple design but less efficient than SMP.
Example: Older embedded systems, some real-time systems.
If master CPU fails, the whole system may crash.
Easy to design.
Less complexity in scheduling.
Important concepts
1. Load Balancing
Load balancing ensures that the workload is evenly distributed across
all processors, preventing any CPU from being overburdened or idle.
2. Processor Affinity
Processor affinity refers to the tendency of processes to be assigned
to the same CPU they were initially executed on, to optimize
performance by using the CPU's cache memory efficiently.
3. Synchronization
Synchronization ensures that multiple processors do not access
shared resources simultaneously, avoiding data inconsistency and
errors.
Real-Time CPU Scheduling
In a real-time system, the operating system must ensure that processes are
executed within strict time limits (deadlines). In real-time CPU scheduling,
the focus is not only on maximizing CPU utilization or fairness, but on meeting
the timely execution of tasks.
1. Hard Real-Time Systems:
Tasks must meet their deadlines without exception. Missing a deadline can
lead to catastrophic consequences (e.g., medical devices, airbag systems).
2. Soft Real-Time Systems:
Deadlines are important but not strictly enforced. Missing a deadline may
cause performance degradation, but it doesn't result in system failure (e.g.,
video streaming, online gaming).
Queue Scheduling
Queue Scheduling in Operating Systems is a method for managing the
execution of processes using different types of queues. In queue scheduling,
processes are assigned to queues based on their priority or other criteria,
and the operating system uses these queues to schedule processes for
execution.
Multilevel Queue Scheduling (MLQ)
In Multilevel Queue Scheduling, processes are divided into multiple queues,
each with its own scheduling algorithm. Each queue has a specific priority
level, and the operating system selects processes from the queues based on
their priority.
How it Works:
Multiple Queues: The processes are divided into different queues based
on their attributes (e.g., interactive processes, CPU-bound processes,
batch processes).
Each queue has its own scheduling algorithm (e.g., Round Robin for
interactive tasks, FCFS for batch tasks).
Fixed Priority: The queues are typically arranged with fixed priorities.
The highest-priority queue is processed first, and processes are
scheduled according to the queue's specific algorithm.
No Process Movement Between Queues: Once a process is assigned to a
queue, it remains there for its entire lifetime.
Example:
Queue 1 (high-priority): Interactive tasks (uses Round Robin).
Queue 2 (medium-priority): CPU-bound tasks (uses FCFS).
Queue 3 (low-priority): Batch tasks (uses FCFS).
In this case, processes in Queue 1 will be given higher priority and executed
before processes in Queue 2 and Queue 3.
Multilevel Feedback Queue Scheduling (MLFQ)
Multilevel Feedback Queue Scheduling is an extension of Multilevel
Queue Scheduling, but with dynamic adjustment of the priority of
processes. Processes can move between queues based on their behavior,
ensuring fairer scheduling and helping avoid starvation.
How it Works:
Multiple Queues: Like MLQ, processes are divided into different
queues based on priority and scheduling algorithm. Each queue may
have different time slices (e.g., a lower-priority queue could have
longer time slices).
Dynamic Feedback: Unlike MLQ, in MLFQ, a process can move up or
down between queues based on how much CPU time it has consumed.
For example:
If a process uses too much CPU time (CPU-bound), it may be moved
to a lower-priority queue.
If a process does not use much CPU time (interactive), it may be
moved to a higher-priority queue.
Aging: If processes in lower-priority queues wait too long, they may
age and move to higher-priority queues to avoid starvation.
Example:
Queue 1 (high-priority, time slice = 2ms): Interactive processes (uses
Round Robin).
Queue 2 (medium-priority, time slice = 5ms): CPU-bound processes that
used less CPU time (uses Round Robin).
Queue 3 (low-priority, time slice = 10ms): CPU-bound processes that have
been using a lot of CPU time (uses FCFS).
A process that was initially placed in Queue 3 for being CPU-bound may be
moved to Queue 1 if it becomes interactive or waits too long in the lower-
priority queue.
What is starvation ?
Starvation in the context of Operating Systems refers to a situation where
a process is never granted CPU time or is continuously delayed because
other higher-priority processes keep getting scheduled before it. As a
result, the process may never get a chance to execute, leading to
inefficiency and unresponsiveness in the system.
Rishabh vijaypuriya
- creator