Unit - 4
Job and Processor Scheduling in Operating Systems
Scheduling Levels in the OS
1. Long-Term Scheduler (Job Scheduler)
Purpose: Controls which jobs (processes) are admitted into the system from disk into
memory.
Frequency: Invoked infrequently (seconds to minutes).
Function: Regulates system degree of multiprogramming by selecting a mix of CPU-
bound and I/O-bound jobs
Example: In a batch environment, only some jobs are admitted at a time to prevent
overload.
2. Medium-Term Scheduler (Swapper)
Purpose: Temporarily removes processes from memory (swapping out) or brings them
back (swapping in).
Frequency: Invoked occasionally to optimize memory usage .
Function: Improves process mix and handles memory constraints, avoiding thrashing.
3. Short-Term Scheduler (CPU Scheduler)
Purpose: Selects which ready process gets the CPU next.
Frequency: Invoked very frequently (milliseconds)
reddit.com+14sacredchaos.com+14en.wikipedia.org+14slideplayer.com.
Function: Ensures high CPU utilization, responsiveness, and fairness.
Examples of algorithms: FCFS, SJF (non-preemptive or preemptive), Priority
Scheduling (with aging), Round-Robin (time quantum), Multilevel Queue, Multilevel
Feedback Queue
Objectives of Scheduling
Maximize throughput – more processes completed per unit time
Provide acceptable response time – especially for interactive users
Minimize resource utilization overhead – keep system efficient
Avoid indefinite postponement – ensure fairness, avoid starvation
Enforce priorities – ensure higher-priority jobs get scheduled
Ensure predictability – consistent performance under similar loads
Minimize overhead – scheduling decisions should be lightweight
Scalability – handle growing numbers of processes gracefully
CPU scheduling is a process used by the operating system to decide which
task or process gets to use the CPU at a particular time. This is important
because a CPU can only handle one task at a time, but there are usually
many tasks that need to be processed. The following are different purposes
of a CPU scheduling time.
Maximize the CPU utilization
Minimize the response and waiting time of the process.
What is the Need for a CPU Scheduling Algorithm?
CPU scheduling is the process of deciding which process will own the CPU
to use while another process is suspended. The main function of CPU
scheduling is to ensure that whenever the CPU remains idle, the OS has at
least selected one of the processes available in the ready-to-use line.
In Multiprogramming, if the long-term scheduler selects multiple I/O binding
processes then most of the time, the CPU remains idle. The function of an
effective program is to improve resource utilization.
Terminologies Used in CPU Scheduling
Arrival Time: The time at which the process arrives in the ready queue.
Completion Time: The time at which the 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.
Turn Around Time = Completion Time – Arrival Time
Waiting Time(W.T): Time Difference between turn around time and burst
time.
Waiting Time = Turn Around Time – Burst Time
Things to Take Care While Designing a CPU
Scheduling Algorithm
Different CPU Scheduling algorithms have different structures and the
choice of a particular algorithm depends on a variety of factors.
CPU Utilization: The main purpose of any CPU algorithm is to keep the
CPU as busy as possible. Theoretically, CPU usage can range from 0 to
100 but in a real-time system, it varies from 40 to 90 percent depending
on the system load.
Throughput: The average CPU performance is the number of processes
performed and completed during each unit. This is called throughput. The
output may vary depending on the length or duration of the processes.
Turn Round Time: For a particular process, the important conditions are
how long it takes to perform that process. The time elapsed from the time
of process delivery to the time of completion is known as the conversion
time. Conversion time is the amount of time spent waiting for memory
access, waiting in line, using CPU and waiting for I/O.
Waiting Time: The Scheduling algorithm does not affect the time required
to complete the process once it has started performing. It only affects the
waiting time of the process i.e. the time spent in the waiting process in the
ready queue.
Response Time: In a collaborative system, turn around time is not the
best option. The process may produce something early and continue to
computing the new results while the previous results are released to the
user. Therefore another method is the time taken in the submission of the
application process until the first response is issued. This measure is
called response time.
Different Types of CPU Scheduling Algorithms
There are mainly two types of scheduling methods:
Preemptive Scheduling: Preemptive scheduling is used when a process
switches from running state to ready state or from the waiting state to the
ready state.
Non-Preemptive Scheduling: Non-Preemptive scheduling is used when
a process terminates , or when a process switches from running state to
waiting state.
CPU Scheduling Algorithms
FCFS - First Come, First Serve
SJF - Shortest Job First
SRTF - Shortest Remaining Time First
Round Robin
Priority Scheduling
FCFS Scheduling
FCFS Scheduling is a non-preemptive algorithm, meaning once a process
starts running, it cannot be stopped until it voluntarily relinquishes the CPU,
typically when it terminates or performs I/O.
1. Arrival: Processes enter the system and are placed in a queue in the
order they arrive.
2. Execution: The CPU takes the first process from the front of the queue,
executes it until it is complete, and then removes it from the queue.
3. Repeat: The CPU takes the next process in the queue and repeats the
execution process.
This continues until there are no more processes left in the queue.
Example of FCFS CPU Scheduling:
To understand the First Come, First Served (FCFS) scheduling algorithm
effectively, we'll use two examples -
one where all processes arrive at the same time,
another where processes arrive at different times.
Scenario 1: Processes with Same Arrival Time
Consider the following table of arrival time and burst time for three processes
P1, P2 and P3
Process Arrival Time Burst Time
p1 0 5
p2 0 3
p3 0 8
Step-by-Step Execution:
1. P1 will start first and run for 5 units of time (from 0 to 5).
2. P2 will start next and run for 3 units of time (from 5 to 8).
3. P3 will run last, executing for 8 units (from 8 to 16).
Gant Chart:
Step 1
Step 2
Step 3
Step 4
Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time
AT : Arrival Time
BT : Burst Time or CPU Time
TAT : Turn Around Time
WT : Waiting Time
Scenario 2: Processes with Different Arrival Times
Consider the following table of arrival time and burst time for three processes
P1, P2 and P3
Process Burst Time (BT) Arrival Time (AT)
P1 5 ms 2 ms
P2 3 ms 0 ms
P3 4 ms 4 ms
Step-by-Step Execution:
P2 arrives at time 0 and runs for 3 units, so its completion time is:
Completion Time of P2=0+3=3
P1 arrives at time 2 but has to wait for P2 to finish. P1 starts at time 3 and
runs for 5 units. Its completion time is:
Completion Time of P1=3+5=8
P3 arrives at time 4 but has to wait for P1 to finish. P3 starts at time 8 and
runs for 4 units. Its completion time is:
Completion Time of P3=8+4=12
Step 2
step 3
Step 4
Advantages of FCFS
The simplest and basic form of CPU Scheduling algorithm
Every process gets a chance to execute in the order of its arrival. This
ensures that no process is arbitrarily prioritized over another.
Easy to implement, it doesn't require complex data structures.
Since processes are executed in the order they arrive, there’s no risk
of starvation
It is well suited for batch systems where the longer time periods for each
process are often acceptable.
Disadvantages of FCFS
As it is a Non-preemptive CPU Scheduling Algorithm, FCFS can result in
long waiting times, especially if a long process arrives before a shorter
one. This is known as the convoy effect, where shorter processes are
forced to wait behind longer processes, leading to inefficient execution.
The average waiting time in the FCFS is much higher than in the others
Since FCFS processes tasks in the order they arrive, short jobs may have
to wait a long time if they arrive after longer tasks, which leads to poor
performance in systems with a mix of long and short tasks.
Processes that are at the end of the queue, have to wait longer to finish.
It is not suitable for time-sharing operating systems where each process
should get the same amount of CPU time.
Shortest Job First :
Shortest Job First (SJF) or Shortest Job Next (SJN) is a scheduling
process that selects the waiting process with the smallest execution time to
execute next.
Implementation of SJF Scheduling
Sort all the processes according to the arrival time.
Then select that process that has minimum arrival time and minimum
Burst time.
After completion of the process make a pool of processes (a ready queue)
that arrives afterward till the completion of the previous process and
select that process in that queue which is having minimum Burst time.
