CPU SCHEDULING

Dr. Sukanta Ghosh

Systems and Architecture
BASIC CONCEPTS
 Maximum CPU utilization obtained with
multiprogramming
 CPU–I/O Burst Cycle – Process execution consists of a
cycle of CPU execution and I/O wait
 CPU burst distribution
CPU SCHEDULER
 Selects from among the processes in memory that are ready to execute,
and allocates the CPU to one of them
 CPU scheduling decisions may take place when a process:

1. Switches from running to waiting state

2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
 Scheduling under 1 and 4 is non-preemptive
 All other scheduling is preemptive
DISPATCHER
 Dispatcher module gives control of the CPU to the process selected by the
short-term scheduler; this involves:
 switching context
 switching to user mode
 jumping to the proper location in the user program to restart that program

 Dispatch latency – time it takes for the dispatcher to stop one process
and start another running
SCHEDULING CRITERIA
 CPU utilization – keep the CPU as busy as possible
 Throughput – # of processes that complete their execution per time unit
 Turnaround time – amount of time to execute a particular process
 Waiting time – amount of time a process has been waiting in the ready
queue
 Response time – amount of time it takes from when a request was
submitted until the first response is produced, not output (for time-sharing
environment)
OPTIMIZATION CRITERIA
 Max CPU utilization
 Max throughput
 Min turnaround time
 Min waiting time
 Min response time
CPU SCHEDULING
ALGORITHMS
 First Come First Serve
 Round Robin
 Shortest Job First
 Shortest Remaining Time First
 Priority Based Scheduling
 Highest Response Ratio Next
PREEMPTIVE SCHEDULING
 Preemptive scheduling allows the operating system to interrupt and
suspend a currently running process in order to assign CPU time to another
process.
 This interruption can occur for various reasons, such as higher-priority
processes becoming ready to execute or the current process exceeding its
allocated time slice.
 Common Preemptive Scheduling Algorithms:
 Round Robin (RR)
 Shortest Remaining Time First (SRTF)
 Priority Scheduling (when implemented as preemptive)
PREEMPTIVE SCHEDULING
 Scenario: Imagine a system with three processes:
• P1: CPU burst time = 8ms
• P2: CPU burst time = 4ms
• P3: CPU burst time = 9ms

 Time Quantum: 4ms

 Execution Order:
1.P1 starts and runs for 4ms (remaining time: 4ms).
2.P2 runs next for its entire 4ms (completes execution).
3.P3 runs for 4ms (remaining time: 5ms).
4.P1 resumes and completes its remaining 4ms.
5.P3 resumes and completes its remaining 5ms.
PREEMPTIVE SCHEDULING
 Advantages:
• Fair CPU Allocation: Each process gets an equal opportunity to execute.
• Good for Time-Sharing Systems: Ensures responsiveness for interactive users.

 Disadvantages:
• Overhead: Frequent context switching can lead to increased overhead.
• Not Optimal for All Workloads: Performance can degrade for processes with
varying CPU burst times.
NON-PREEMPTIVE
SCHEDULING
 Non-preemptive scheduling, also known as cooperative scheduling, ensures
that once a process starts executing on the CPU, it runs to completion or
until it voluntarily relinquishes the CPU (e.g., waiting for I/O operations).
 The operating system does not forcibly remove the process from the CPU.
 Common Non-Preemptive Scheduling Algorithms:
 First-Come, First-Served (FCFS)
 Shortest Job First (SJF)
 Priority Scheduling (when implemented as non-preemptive)
NON-PREEMPTIVE
SCHEDULING
 Scenario: Consider the same three processes:
• P1: Arrival time = 0ms, CPU burst time = 8ms
• P2: Arrival time = 1ms, CPU burst time = 4ms
• P3: Arrival time = 2ms, CPU burst time = 9ms

 Execution Order:
1.P1 arrives at 0ms and starts executing immediately, running for 8ms (completes
at 8ms).
2.P2 arrives at 1ms but waits until P1 finishes. It starts at 8ms and runs for 4ms
(completes at 12ms).
3.P3 arrives at 2ms and waits until P2 finishes. It starts at 12ms and runs for 9ms
(completes at 21ms).
NON-PREEMPTIVE
SCHEDULING
 Advantages:
• Simplicity: Easy to understand and implement.
• Predictable: Processes are handled in the order they arrive.

 Disadvantages:
• Convoy Effect: Shorter processes may be stuck waiting behind longer ones,
leading to inefficient CPU utilization.
• Poor Responsiveness: Not suitable for time-sensitive or interactive systems.
FIRST-COME, FIRST-SERVE
(FCFS) SCHEDULING
 FCFS operates on the principle that the process that arrives first in the
ready queue is the first to be allocated the CPU.
 Key Characteristics:

• Non-Preemptive: Once a process starts executing, it runs to completion

before the next process is scheduled.
• Simple to Implement: FCFS uses a straightforward queue structure where
processes are lined up as they arrive.
• FIFO Order: Processes are handled in a "First In, First Out" order.
HOW FCFS WORKS
 In FCFS scheduling, processes are executed in the order of their arrival
times.
 The CPU is assigned to the process that has been waiting the longest in the
queue.
 This approach ensures fairness in the order of execution but can lead to
inefficiencies, especially when processes have varying CPU burst times.
EXAMPLE (FCFS)
 Consider the following scenario with three processes arriving at different
times and requiring different amounts of CPU time:

Process Arrival Time CPU Burst Time

P1 0 ms 6 ms
P2 2 ms 4 ms
P3 4 ms 2 ms
EXAMPLE (FCFS)
 Step-by-Step Execution:
 P1 arrives first at 0 ms and begins execution immediately. It runs for its full
burst time of 6 ms.
 P2 arrives at 2 ms but must wait until P1 finishes. P1 completes at 6 ms,
and P2 starts immediately afterward.
 P3 arrives at 4 ms and waits in the queue until P2 completes. P2 finishes at
10 ms, and P3 starts next.

P1 P2 P3

0 6 10 12
EXAMPLE (FCFS)
 Completion Time:  Waiting Time: (Turnaround Time -
• P1: 0 ms (start) + 6 ms (burst) = CPU Burst Time)
• P1: 6 ms - 6 ms = 0 ms
6 ms
• P2: 8 ms - 4 ms = 4 ms
• P2: 6 ms (start) + 4 ms (burst) =
• P3: 8 ms - 2 ms = 6 ms
10 ms
• P3: 10 ms (start) + 2 ms (burst) • Total Turnaround Time: 6 + 8 + 8
= 12 ms = 22 ms
 Turnaround Time: (Completion • Total Waiting Time: 0 + 4 + 6 =
10 ms
Time - Arrival Time)
• P1: 6 ms - 0 ms = 6 ms • Average Turnaround Time: 22
ms / 3 processes = 7.33 ms
• P2: 10 ms - 2 ms = 8 ms
• P3: 12 ms - 4 ms = 8 ms • Average Waiting Time: 10 ms / 3
processes = 3.33 ms
EXAMPLE (FCFS)
Process Burst Time
P1 24
P2 3
P3 3
 Suppose that the processes arrive in the order: P , P , P
1 2 3
The Gantt Chart for the schedule is:

P1 P2 P3

0 24 27 30
 Waiting time for P = 0; P = 24; P = 27
1 2 3

 Average waiting time: (0 + 24 + 27)/3 = 17

EXAMPLE (FCFS)
Suppose that the processes arrive in the order
P2 , P3 , P1
 The Gantt chart for the schedule is:

P2 P3 P1

0 3 6 30

 Waiting time for P = 6; P = 0 P = 3

1 2 ; 3

 Average waiting time: (6 + 0 + 3)/3 = 3

 Much better than previous case
 Convoy effect short process behind long process
FCFS ADVANTAGES AND
DISADVANTAGES
 Advantages of FCFS:  Disadvantages of FCFS:

• Simplicity: Easy to understand • Convoy Effect: Shorter

and implement. processes may be delayed by
longer ones, leading to inefficient
• Fairness: All processes are
CPU utilization.
treated equally, in the order they
arrive. • Poor Responsiveness: Not
suitable for time-sharing systems
or interactive applications where
quick response times are needed.
• Non-Preemptive: A long process
can hold the CPU for a significant
amount of time, delaying the
execution of other processes.
SHORTEST-JOB-FIRST (SJF)
SCHEDULING
 Also known as Shortest-Process-Next (SPN), is a CPU scheduling algorithm
that selects the process with the shortest CPU burst time to execute next.
 It can be implemented in two forms:
 non-preemptive
 preemptive (known as Shortest Remaining Time First (SRTF) in the preemptive
case).
 SJF is considered optimal because it minimizes the average waiting time for
processes.
SHORTEST-JOB-FIRST (SJF)
SCHEDULING
 Key Characteristics:
• Optimality: Minimizes average waiting time across processes.
• Non-Preemptive: Once a process starts, it runs to completion without being
interrupted (in the non-preemptive version).
• Preemptive: In the SRTF variant, if a new process arrives with a shorter
remaining burst time than the currently executing process, the CPU is preempted
and assigned to the new process.
• Need for Prior Knowledge: Requires knowledge of the CPU burst time of each
process, which is often difficult to predict accurately.
EXAMPLE: NON-PREEMPTIVE
SJF SCHEDULING
 Consider the following scenario with four processes:

Process Arrival Time CPU Burst Time

P1 0 ms 8 ms
P2 1 ms 4 ms
P3 2 ms 9 ms
P4 3 ms 5 ms
EXAMPLE: NON-PREEMPTIVE
SJF SCHEDULING
 Step-by-Step Execution:

1. P1 arrives at 0 ms and starts executing immediately (since it's the only

process available). It has a burst time of 8 ms.
2. At 1 ms, P2 arrives, but P1 continues to execute.
3. At 2 ms, P3 arrives, and at 3 ms, P4 arrives. Now, when P1 finishes at 8
ms, the scheduler looks at the ready queue, which contains P2, P3, and P4.
4. P2 has the shortest burst time (4 ms), so it is selected next.
5. P2 finishes at 12 ms. The remaining processes are P3 (burst time = 9 ms)
and P4 (burst time = 5 ms).
6. P4 is selected next since it has the shorter burst time (5 ms).
7. P4 finishes at 17 ms. Finally, P3 executes and finishes at 26 ms.
EXAMPLE: NON-PREEMPTIVE
SJF SCHEDULING
 Gantt Chart

P1 P2 P3 P4

0 8 12 17 26
EXAMPLE: NON-PREEMPTIVE
SJF SCHEDULING
 Completion Time:  Waiting Time:
• P1: 0 ms (start) + 8 ms (burst) = 8 • P1: 8 ms - 8 ms = 0 ms
ms • P2: 11 ms - 4 ms = 7 ms
• P2: 8 ms (start) + 4 ms (burst) = 12 • P4: 14 ms - 5 ms = 9 ms
ms • P3: 24 ms - 9 ms = 15 ms
• P4: 12 ms (start) + 5 ms (burst) = 17
ms
• P3: 17 ms (start) + 9 ms (burst) = 26 • Total Turnaround Time: 8 + 11 + 14 +
ms 24 = 57 ms
• Total Waiting Time: 0 + 7 + 9 + 15 = 31
 Turnaround Time:
ms
• P1: 8 ms - 0 ms = 8 ms
• Average Turnaround Time: 57 ms / 4
• P2: 12 ms - 1 ms = 11 ms processes = 14.25 ms
• P4: 17 ms - 3 ms = 14 ms
• Average Waiting Time: 31 ms / 4
• P3: 26 ms - 2 ms = 24 ms processes = 7.75 ms
EXAMPLE: NON-PREEMPTIVE
SJF SCHEDULING
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 SJF (non-preemptive)
P1 P3 P2 P4

0 3 7 8 12 16

 Average waiting time = (0 + 6 + 3 + 7)/4 = 4

EXAMPLE: PREEMPTIVE SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
 SJF (preemptive)
P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

 Average waiting time = (9 + 1 + 0 +2)/4 = 3

ADVANTAGES AND
DISADVANTAGE OF SJF
 Advantages of SJF:  Disadvantages of SJF:
• Minimizes Average Waiting • Starvation: Longer processes may
Time: By executing the shortest suffer from indefinite postponement,
jobs first, SJF reduces the overall especially in a system with many
average waiting time for all short processes (this is particularly a
processes. risk in the preemptive version).
• Efficiency: It tends to optimize • Requires Prior Knowledge: The
CPU utilization, especially in exact CPU burst time must be
environments where jobs vary known in advance, which is often
significantly in length. not possible in practice.
• Complexity: The need to
constantly reorder the queue based
on the shortest remaining time adds
overhead and complexity to the
system.
PRIORITY SCHEDULING
 Priority Scheduling is a CPU scheduling algorithm where each process is
assigned a priority level, and the CPU is allocated to the process with the
highest priority.
 If two processes have the same priority, they are scheduled according to
their arrival time or another scheduling algorithm.
 Priority scheduling can be preemptive or non-preemptive.
PRIORITY SCHEDULING
 Key Characteristics:

• Priority-Based: Each process has a priority, and the CPU is assigned to

the process with the highest priority.
• Preemptive or Non-Preemptive: In preemptive priority scheduling, a
currently running process can be interrupted if a higher-priority process
arrives. In non-preemptive priority scheduling, the running process
continues until it completes, even if a higher-priority process arrives.
• Dynamic or Static Priority: Priority can be static (assigned at the start
and does not change) or dynamic (can change during execution).
HOW PRIORITY SCHEDULING
WORKS
 In priority scheduling, the scheduler selects the process with the highest
priority to execute next.
 The priority is usually represented by a number; lower numbers may
indicate higher priority (e.g., 1 is the highest priority), or vice versa,
depending on the implementation.
EXAMPLE: NON-PREEMPTIVE
PRIORITY SCHEDULING
 Consider the following scenario with four processes:

Process Arrival Time CPU Burst Time Priority

P1 0 ms 5 ms 2
P2 1 ms 3 ms 1
P3 2 ms 8 ms 4
P4 3 ms 6 ms 3
EXAMPLE: NON-PREEMPTIVE
PRIORITY SCHEDULING
 Step-by-Step Execution:

1.P1 arrives at 0 ms and starts executing immediately because it is the only

process available at that time. P1 has a priority of 2.
2.P2 arrives at 1 ms with a higher priority (1) than P1, but since this is non-
preemptive scheduling, P1 continues to execute until it completes at 5 ms.
3.After P1 finishes, P2 (with the highest priority of 1) is selected next and
executes.
4.P3 arrives at 2 ms and P4 at 3 ms, but both have lower priorities than P2,
so they wait.
5.P2 finishes at 8 ms, and the next highest priority process, P4 (priority 3),
starts executing.
6.P4 finishes at 14 ms, and finally, P3 (priority 4) starts and finishes at 22
ms.
EXAMPLE: NON-PREEMPTIVE
PRIORITY SCHEDULING
 Gantt Chart

P1 P2 P4 P3

0 5 8 14 22
EXAMPLE: NON-PREEMPTIVE
PRIORITY SCHEDULING
 Completion Time:  Waiting Time:
• P1: 0 ms (start) + 5 ms (burst) = 5 • P1: 5 ms - 5 ms = 0 ms
ms • P2: 7 ms - 3 ms = 4 ms
• P2: 5 ms (start) + 3 ms (burst) = 8 • P4: 11 ms - 6 ms = 5 ms
ms • P3: 20 ms - 8 ms = 12 ms
• P4: 8 ms (start) + 6 ms (burst) = 14
ms
• P3: 14 ms (start) + 8 ms (burst) = 22 • Total Turnaround Time: 43 ms
ms
• Total Waiting Time: 21 ms
 Turnaround Time:
• P1: 5 ms - 0 ms = 5 ms • Average Turnaround Time: 43 ms
• P2: 8 ms - 1 ms = 7 ms / 4 processes = 10.75 ms
• P4: 14 ms - 3 ms = 11 ms • Average Waiting Time: 21 ms / 4
• P3: 22 ms - 2 ms = 20 ms processes = 5.25 ms
EXAMPLE: PREEMPTIVE
PRIORITY SCHEDULING
 Assume the same processes and priorities, but now if a process with a
higher priority arrives while another process is running, the running
process is preempted.
• P1 starts at 0 ms.
• P2 arrives at 1 ms with a higher priority and preempts P1.
• P2 runs until it finishes at 4 ms.
• P1 resumes at 4 ms and runs until 8 ms.
• P4 arrives at 3 ms but waits until P1 finishes because P1 resumed earlier.
• P4 runs from 8 ms to 14 ms.
• P3 runs last, from 14 ms to 22 ms.
EXAMPLE: PREEMPTIVE
PRIORITY SCHEDULING
 Gantt Chart

P1 P2 P1 P4 P3

0 1 4 8 14 22
ADVANTAGES AND
DISADVANTAGE OF
PRIORITY SCHEDULING
 Advantages of Priority  Disadvantages of Priority
Scheduling: Scheduling:
• Flexibility: Allows important tasks to • Starvation: Low-priority processes
be prioritized, making it suitable for may suffer from starvation, where
systems with varying levels of task they are never executed because
importance. high-priority processes keep arriving.
• Efficiency: High-priority tasks get
• Complexity: Assigning appropriate
quicker access to the CPU, which can priorities can be difficult, and
be crucial in real-time systems.
dynamic priority adjustments can
add overhead.
• Not Always Fair: Prioritizing some
processes over others can lead to
unfairness, especially in systems
• Starvation Solution: Aging – as time
where all tasks are considered
progresses increase the priority of equally important.
the process
ROUND ROBIN (RR)
 Each process gets a small unit of CPU time (time quantum), usually 10-100
milliseconds.
 After this time has elapsed, the process is preempted and added to the end
of the ready queue.
 If there are n processes in the ready queue and the time quantum is q,
then each process gets 1/n of the CPU time in chunks of at most q time
units at once. No process waits more than (n-1)q time units.
 Performance
 q large => FIFO
 q small => q must be large with respect to context switch, otherwise
overhead is too high
ROUND ROBIN (RR)
 Key Characteristics:

• Preemptive: The CPU can switch between processes if they haven't

completed their execution within their allotted time slice.
• Time Quantum: A crucial parameter that determines the maximum time a
process can run before being preempted.
• Fairness: Ensures that all processes get an equal share of the CPU's time.
• Simple to Implement: It uses a circular queue structure, making it easy
to understand and implement.
ROUND ROBIN (RR)
 How Round Robin Works:

1. Processes are added to the ready queue in the order they arrive.
2. The CPU picks the first process in the queue and assigns it the CPU for a
time quantum.
3. If the process completes within the time quantum, it leaves the queue. If
not, it is preempted and placed at the back of the queue.
4. The CPU then moves on to the next process in the queue and repeats the
procedure.
EXAMPLE OF RR WITH TIME
QUANTUM = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
 The Gantt chart is:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

 Typically, higher average turnaround than SJF, but better response

TIME QUANTUM AND
CONTEXT SWITCH TIME
MULTILEVEL QUEUE
 Ready queue is partitioned into separate queues:
 foreground (interactive)
 background (batch)

 Each queue has its own scheduling algorithm

 foreground – RR
 background – FCFS

 Scheduling must be done between the queues

 Fixed priority scheduling; (i.e., serve all from foreground then from background).
Possibility of starvation.
 Time slice – each queue gets a certain amount of CPU time which it can schedule
amongst its processes; i.e., 80% to foreground in RR
 20% to background in FCFS
MULTILEVEL QUEUE
SCHEDULING
MULTILEVEL FEEDBACK
QUEUE
 A process can move between the various queues; aging can be
implemented this way
 Multilevel-feedback-queue scheduler defined by the following parameters:
 number of queues
 scheduling algorithms for each queue
 method used to determine when to upgrade a process
 method used to determine when to demote a process
 method used to determine which queue a process will enter when that process
needs service
EXAMPLE OF MULTILEVEL
FEEDBACK QUEUE
 Three queues:
 Q0 – RR with time quantum 8 milliseconds
 Q1 – RR time quantum 16 milliseconds
 Q2 – FCFS

 Scheduling
 A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives
8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1.
 At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still
does not complete, it is preempted and moved to queue Q2.
MULTILEVEL FEEDBACK
QUEUES
MULTIPLE-PROCESSOR
SCHEDULING
 CPU scheduling more complex when multiple CPUs are available
 Homogeneous processors within a multiprocessor
 Load sharing
 Asymmetric multiprocessing – only one processor accesses the system
data structures, alleviating the need for data sharing
LINUX SCHEDULING
 Two algorithms: time-sharing and real-time
 Time-sharing
 Prioritized credit-based – process with most credits is scheduled next
 Credit subtracted when timer interrupt occurs
 When credit = 0, another process chosen
 When all processes have credit = 0, recrediting occurs
 Based on factors including priority and history

 Real-time
 Soft real-time
 Posix.1b compliant – two classes
 FCFS and RR
 Highest priority process always runs first
THANK YOU