PPT: CPU Scheduling

 Page 1


CPU Scheduling
Page 2


CPU Scheduling
CPU Scheduling Basics
Arrival Time
Time at which the process arrives in the ready queue
Completion Time
Time at which process completes its execution
Burst Time
Time required by a process for CPU execution
Turn Around Time
Time Difference between completion time and arrival time 
(Completion Time 3 Arrival Time)
Scheduling of processes is done to finish work on time. Waiting Time is the time difference between turn around time and burst time, 
calculated as: Waiting Time = Turn Around Time 3 Burst Time
Page 3


CPU Scheduling
CPU Scheduling Basics
Arrival Time
Time at which the process arrives in the ready queue
Completion Time
Time at which process completes its execution
Burst Time
Time required by a process for CPU execution
Turn Around Time
Time Difference between completion time and arrival time 
(Completion Time 3 Arrival Time)
Scheduling of processes is done to finish work on time. Waiting Time is the time difference between turn around time and burst time, 
calculated as: Waiting Time = Turn Around Time 3 Burst Time
Why Do We Need Scheduling?
The Problem
A typical process involves both I/O time and CPU time. In 
uni programming systems like MS-DOS, time spent 
waiting for I/O is wasted and CPU remains idle during this 
time.
Multi programming systems solve this by allowing one 
process to use CPU while another is waiting for I/O, but 
this requires effective process scheduling.
Objectives
Maximize CPU utilization
Fair allocation of CPU
Maximize throughput
Minimize turnaround time
Minimize waiting time
Minimize response time
Page 4


CPU Scheduling
CPU Scheduling Basics
Arrival Time
Time at which the process arrives in the ready queue
Completion Time
Time at which process completes its execution
Burst Time
Time required by a process for CPU execution
Turn Around Time
Time Difference between completion time and arrival time 
(Completion Time 3 Arrival Time)
Scheduling of processes is done to finish work on time. Waiting Time is the time difference between turn around time and burst time, 
calculated as: Waiting Time = Turn Around Time 3 Burst Time
Why Do We Need Scheduling?
The Problem
A typical process involves both I/O time and CPU time. In 
uni programming systems like MS-DOS, time spent 
waiting for I/O is wasted and CPU remains idle during this 
time.
Multi programming systems solve this by allowing one 
process to use CPU while another is waiting for I/O, but 
this requires effective process scheduling.
Objectives
Maximize CPU utilization
Fair allocation of CPU
Maximize throughput
Minimize turnaround time
Minimize waiting time
Minimize response time
Basic Scheduling Algorithms
First Come First Serve (FCFS)
Simplest algorithm that schedules according to arrival times. Implemented using FIFO queue. Non-preemptive and 
suffers from convoy effect.
Shortest Job First (SJF)
Processes with shortest burst time are scheduled first. If two processes have same burst time, FCFS breaks the tie. 
Non-preemptive algorithm.
Longest Job First (LJF)
Similar to SJF but priority given to process with longest burst time. Non-preemptive in nature - once started, 
process runs to completion.
Page 5


CPU Scheduling
CPU Scheduling Basics
Arrival Time
Time at which the process arrives in the ready queue
Completion Time
Time at which process completes its execution
Burst Time
Time required by a process for CPU execution
Turn Around Time
Time Difference between completion time and arrival time 
(Completion Time 3 Arrival Time)
Scheduling of processes is done to finish work on time. Waiting Time is the time difference between turn around time and burst time, 
calculated as: Waiting Time = Turn Around Time 3 Burst Time
Why Do We Need Scheduling?
The Problem
A typical process involves both I/O time and CPU time. In 
uni programming systems like MS-DOS, time spent 
waiting for I/O is wasted and CPU remains idle during this 
time.
Multi programming systems solve this by allowing one 
process to use CPU while another is waiting for I/O, but 
this requires effective process scheduling.
Objectives
Maximize CPU utilization
Fair allocation of CPU
Maximize throughput
Minimize turnaround time
Minimize waiting time
Minimize response time
Basic Scheduling Algorithms
First Come First Serve (FCFS)
Simplest algorithm that schedules according to arrival times. Implemented using FIFO queue. Non-preemptive and 
suffers from convoy effect.
Shortest Job First (SJF)
Processes with shortest burst time are scheduled first. If two processes have same burst time, FCFS breaks the tie. 
Non-preemptive algorithm.
Longest Job First (LJF)
Similar to SJF but priority given to process with longest burst time. Non-preemptive in nature - once started, 
process runs to completion.
Advanced Scheduling Algorithms
Round Robin
Each process assigned fixed time quantum in cyclic 
way. Designed for time-sharing systems with ready 
queue as circular FIFO queue.
Priority Based
Processes scheduled according to priorities. Highest 
priority first, with arrival time breaking ties. Can cause 
starvation.
Highest Response Ratio Next
Schedules process with highest response ratio. Avoids 
starvation. Response Ratio = (Waiting Time + Burst 
time) / Burst time
Multilevel Queue
Processes placed in different queues by priority. 
Higher priority queues processed first, which can 
cause starvation.
Shortest Remaining Time First (SRTF) is the preemptive version of SJF, while Longest Remaining Time First (LRTF) is the 
preemptive version of LJF. Multilevel Feedback Queue allows processes to move between queues based on CPU usage.