CPU Scheduling

1. Introduction:
• What is Operating System:
An operating system acts as an intermediary between the user of a computer and computer
hardware. The purpose of an operating system is to provide an environment in which a user
can execute programs conveniently and efficiently.
An operating system is software that manages computer hardware. The hardware must
provide appropriate mechanisms to ensure the correct operation of the computer system
and to prevent user programs from interfering with the proper operation of the system. A
more common definition is that the operating system is the one program running at all times
on the computer (usually called the kernel), with all else being application programs.
An operating system is concerned with the allocation of resources and services, such as
memory, processors, devices, and information. The operating system correspondingly
includes programs to manage these resources, such as a traffic controller, a scheduler, a
memory management module, I/O programs, and a file system.

• Characteristics of Operating Systems:

Let us now discuss some of the important characteristic features of operating systems:
1. Device Management: The operating system keeps track of all the devices. So, it is
also called the Input/Output controller that decides which process gets the device,
when, and for how much time.
2. File Management: It allocates and de-allocates the resources and also decides who
gets the resource.
3. Job Accounting: It keeps track of time and resources used by various jobs or users.
4. Error-detecting Aids: These contain methods that include the production of dumps,
traces, error messages, and other debugging and error-detecting methods.
5. Memory Management: It keeps track of the primary memory, like what part of it is
in use by whom, or what part is not in use, etc. and It also allocates the memory
when a process or program requests it.
6. Processor Management: It allocates the processor to a process and then de-allocates
the processor when it is no longer required or the job is done.
7. Control on System Performance: It records the delays between the request for a
service and the system.
8. Security: It prevents unauthorized access to programs and data using passwords or
some kind of protection technique.
9. Convenience: An OS makes a computer more convenient to use.
10. Efficiency: An OS allows the computer system resources to be used efficiently.
11. Ability to Evolve: An OS should be constructed in such a way as to permit the
effective development, testing, and introduction of new system functions at the
same time without interfering with service.
12. Throughput: An OS should be constructed so that It can give maximum throughput
(Number of tasks per unit time).

2. Course outcomes:

1
CPU Scheduling

• Explain characteristics of the given type of OS

• Identify types of OS suitable for the given type of application
• Execute command on command line for the given task.

3. Literature review

1). Operating System lies in the category of system software. It basically

manages all the resources of the computer. An operating system acts as an
interface between the software and different parts of the computer or the
computer hardware. The operating system is designed in such a way that it can
manage the overall resources and operations of the computer.
Operating System is a fully integrated set of specialized programs that handle
all the operations of the computer. It controls and monitors the execution of all
other programs that reside in the computer, which also includes application
programs and other system software of the computer. Examples of Operating
Systems are Windows, Linux, Mac OS, etc.

2). An operating system (OS) is system software that manages computer

hardware and software resources, and provides common services for
computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system
and may also include accounting software for cost allocation of processor time,
mass storage, peripherals, and other resources.
For hardware functions such as input and output and memory allocation, the
operating system acts as an intermediary between programs and the computer
hardware,[1][2] although the application code is usually executed directly by the
hardware and frequently makes system calls to an OS function or is interrupted
by it. Operating systems are found on many devices that contain a computer –
from cellular phones and video game consoles to web servers and
supercomputers.

3). An operating system (OS) is system software that manages computer

hardware and software resources and provides common services for computer
programs. Nearly every computer program requires an operating system to
function. The two most common operating systems are Microsoft Windows
and Apple’s macOS. This course’s main focus will be Windows 10 and
7.Although this class will be focusing on Windows 10 and 7, the things you
will learn in this module can be done by any version of Windows or macOS. If
you are not running Windows
10 or 7, you can find directions online by searching for the task you are trying
to do and the name of your operating system. (For example, you might search
for “create folder windows vista.”)

4. CPU Scheduling in Operating Systems

2
CPU Scheduling

Scheduling of processes/work is done to finish the work on time. CPU Scheduling

is a process that allows one process to use the CPU while another process is delayed
(in standby) due to unavailability of any resources such as I / O etc, thus making
full use of the CPU. The purpose of CPU Scheduling is to make the system more
efficient, faster, and fairer.
Whenever the CPU becomes idle, the operating system must select one of the
processes in the line ready for launch. The selection process is done by a temporary
(CPU) scheduler. The Scheduler selects between memory processes ready to
launch and assigns the CPU to one of them.

• What is a process?
In computing, a process is the instance of a computer program that is being executed
by one or many threads. It contains the program code and its activity. Depending
on the operating system (OS), a process may be made up of multiple threads of
execution that execute instructions concurrently.
• What is the need for 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 the 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 an idle. The function of
an effective program is to improve resource utilization.
If most operating systems change their status from performance to waiting
then there may always be a chance of failure in the system. So in order to
minimize this excess, the OS needs to schedule tasks in order to make full
use of the CPU and avoid the possibility of deadlock.

• What are the different terminologies to take care of in any CPU

Scheduling algorithm?
• 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.
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?

3
CPU Scheduling

Different CPU Scheduling algorithms have different structures and the choice of a particular
algorithm depends on a variety of factors. Many conditions have been raised to compare CPU
scheduling algorithms.

• What are the 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.

Let us now learn about these CPU scheduling algorithms in operating systems one by one:

1. First Come First Serve:

FCFS considered to be the simplest of all operating system scheduling algorithms. First
come first serve scheduling algorithm states that the process that requests the CPU first is
allocated the CPU first and is implemented by using FIFO queue. Characteristics of
FCFS:
• FCFS supports non-preemptive and preemptive CPU scheduling algorithms.
• Tasks are always executed on a First-come, First-serve concept.
• FCFS is easy to implement and use.
• This algorithm is not much efficient in performance, and the wait time is quite high.
Advantages of FCFS:
• Easy to implement
• First come, first serve method
Disadvantages of FCFS:
• FCFS suffers from Convoy effect.
• The average waiting time is much higher than the other algorithms.
• FCFS is very simple and easy to implement and hence not much efficient. To learn about
how to implement this CPU scheduling algorithm, please refer to our detailed article on
First come, First serve Scheduling.

2.Shortest Job First(SJF):

4
CPU Scheduling

Shortest job first (SJF) is a scheduling process that selects the waiting process with the
smallest execution time to execute next. This scheduling method may or may not be
preemptive. Significantly reduces the average waiting time for other processes waiting to be
executed. The full form of SJF is Shortest Job First.

Characteristics of SJF:
• Shortest Job first has the advantage of having a minimum average waiting time among all
operating system scheduling algorithms.
• It is associated with each task as a unit of time to complete.
• It may cause starvation if shorter processes keep coming. This problem can be solved
using the concept of ageing.
Advantages of Shortest Job first:
• As SJF reduces the average waiting time thus, it is better than the first come first serve
scheduling algorithm.
• SJF is generally used for long term scheduling
Disadvantages of SJF:
• One of the demerit SJF has is starvation.
• Many times it becomes complicated to predict the length of the upcoming CPU request
To learn about how to implement this CPU scheduling algorithm, please refer to our
detailed article on Shortest Job First.
2. Longest Job First(LJF):
Longest Job First(LJF) scheduling process is just opposite of shortest job first (SJF), as the
name suggests this algorithm is based upon the fact that the process with the largest burst
time is processed first. Longest Job First is non-preemptive in nature.
Characteristics of LJF:

5
CPU Scheduling

• Among all the processes waiting in a waiting queue, CPU is always assigned to the
process having largest burst time.
• If two processes have the same burst time then the tie is broken using FCFS i.e. the
process that arrived first is processed first.
• LJF CPU Scheduling can be of both preemptive and non-preemptive types.
Advantages of LJF:
• No other task can schedule until the longest job or process executes completely.
• All the jobs or processes finish at the same time approximately.
Disadvantages of LJF:
• Generally, the LJF algorithm gives a very high average waiting time and average
turnaround time for a given set of processes.
• This may lead to convoy effect.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on the Longest job first scheduling.
3. Priority Scheduling:
Preemptive Priority CPU Scheduling Algorithm is a pre-emptive method of CPU scheduling
algorithm that works based on the priority of a process. In this algorithm, the editor sets the
functions to be as important, meaning that the most important process must be done first. In the
case of any conflict, that is, where there are more than one processor with equal value, then the
most important CPU planning algorithm works on the basis of the FCFS (First Come First
Serve) algorithm.
Characteristics of Priority Scheduling:
• Schedules tasks based on priority.
• When the higher priority work arrives while a task with less priority is executed, the
higher priority work takes the place of the less priority one and The latter is
suspended until the execution is complete.
• Lower is the number assigned, higher is the priority level of a process.
Advantages of Priority Scheduling:
• The average waiting time is less than FCFS Less complex
Disadvantages of Priority Scheduling:
• One of the most common demerits of the Preemptive priority CPU scheduling algorithm
is the Starvation Problem. This is the problem in which a process has to wait for a longer
amount of time to get scheduled into the CPU. This condition is called the starvation
problem.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on Priority Preemptive Scheduling algorithm.
4. Round robin:
Round Robin is a CPU scheduling algorithm where each process is cyclically assigned a
fixed time slot. It is the preemptive version of First come First Serve CPU Scheduling
algorithm. Round Robin CPU Algorithm generally focuses on Time Sharing technique.
Characteristics of Round robin:
• It’s simple, easy to use, and starvation-free as all processes get the balanced CPU
allocation.
• One of the most widely used methods in CPU scheduling as a core.
• It is considered preemptive as the processes are given to the CPU for a very limited time.
Advantages of Round robin:

6
CPU Scheduling

• Round robin seems to be fair as every process gets an equal share of CPU.
• The newly created process is added to the end of the ready queue.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on the Round robin Scheduling algorithm.
5. Shortest Remaining Time First:

Shortest remaining time first is the preemptive version of the Shortest job first which we have
discussed earlier where the processor is allocated to the job closest to completion. In SRTF
the process with the smallest amount of time remaining until completion is selected to
execute.
Characteristics of Shortest remaining time first:
• SRTF algorithm makes the processing of the jobs faster than SJF algorithm, given it’s
overhead charges are not counted.
• The context switch is done a lot more times in SRTF than in SJF and consumes the CPU’s
valuable time for processing. This adds up to its processing time and diminishes its
advantage of fast processing.
Advantages of SRTF:
• In SRTF the short processes are handled very fast.
• The system also requires very little overhead since it only makes a decision when a
process completes or a new process is added.
Disadvantages of SRTF:
• Like the shortest job first, it also has the potential for process starvation.
• Long processes may be held off indefinitely if short processes are continually added. To
learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on the shortest remaining time first.
6. Longest Remaining Time First:
The longest remaining time first is a preemptive version of the longest job first scheduling
algorithm. This scheduling algorithm is used by the operating system to program incoming
processes for use in a systematic way. This algorithm schedules those processes first which
have the longest processing time remaining for completion. Characteristics of longest
remaining time first:
• Among all the processes waiting in a waiting queue, the CPU is always assigned to the
process having the largest burst time.
• If two processes have the same burst time then the tie is broken using FCFS i.e. the
process that arrived first is processed first.
• LJF CPU Scheduling can be of both preemptive and non-preemptive types.
Advantages of LRTF:
• No other process can execute until the longest task executes completely.
• All the jobs or processes finish at the same time approximately.
Disadvantages of LRTF:
• This algorithm gives a very high average waiting time and average turn-around time for a
given set of processes.
• This may lead to a convoy effect.
To learn about how to implement this CPU scheduling algorithm, please refer to our
detailed article on the longest remaining time first.
7. Highest Response Ratio Next:

7
CPU Scheduling

Highest Response Ratio Next is a non-preemptive CPU Scheduling algorithm and it is

considered as one of the most optimal scheduling algorithms. The name itself states that we
need to find the response ratio of all available processes and select the one with the highest
Response Ratio. A process once selected will run till completion.
Characteristics of Highest Response Ratio Next:
• The criteria for HRRN is Response Ratio, and the mode is Non-Preemptive.
• HRRN is considered as the modification of Shortest Job First to reduce the problem of
starvation.
• In comparison with SJF, during the HRRN scheduling algorithm, the CPU is allotted to
the next process which has the highest response ratio and not to the process having less
burst time.
Advantages of HRRN:
• HRRN Scheduling algorithm generally gives better performance than the shortest
job first Scheduling.
• There is a reduction in waiting time for longer jobs and also it encourages shorter
jobs.
Disadvantages of HRRN:
• The implementation of HRRN scheduling is not possible as it is not possible to
know the burst time of every job in advance.
• In this scheduling, there may occur an overload on the CPU.
To learn about how to implement this CPU scheduling algorithm, please refer to our
detailed article on Highest Response Ratio Next.
8. Multiple Queue Scheduling:
Processes in the ready queue can be divided into different classes where each class has
its own scheduling needs. For example, a common division is a foreground
(interactive) process and a background (batch) process. These two classes have
different scheduling needs. For this kind of situation Multilevel Queue Scheduling is
used.

The description of the processes in the above diagram is as follows:

• System Processes: The CPU itself has its process to run, generally
termed as System Process.
Advantages of HRRN:

8
CPU Scheduling

• HRRN Scheduling algorithm generally gives better performance than the shortest
job first Scheduling.
• There is a reduction in waiting time for longer jobs and also it encourages shorter
jobs.
Disadvantages of HRRN:
• The implementation of HRRN scheduling is not possible as it is not possible to know the
burst time of every job in advance.
• In this scheduling, there may occur an overload on the CPU.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on Highest Response Ratio Next.
9. Multiple Queue Scheduling:
Processes in the ready queue can be divided into different classes where each class has its own
scheduling needs. For example, a common division is a foreground
(interactive) process and a background (batch) process. These two classes have different
scheduling needs. For this kind of situation Multilevel Queue Scheduling is used.

The description of the processes in the above diagram is as follows:

• System Processes: The CPU itself has its process to run, generally termed as System
Process.
• Interactive Processes: An Interactive Process is a type of process in which there should
be the same type of interaction.
• Batch Processes: Batch processing is generally a technique in the Operating system that
collects the programs and data together in the form of
a batch before the processing starts.
Advantages of multilevel queue scheduling:
The main merit of the multilevel queue is that it has a low scheduling overhead.
Disadvantages of multilevel queue scheduling:
• Starvation problem
• It is inflexible in nature
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on Multilevel Queue Scheduling.
9. Multilevel Feedback Queue Scheduling:

9
CPU Scheduling

Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling is like Multilevel Queue
Scheduling but in this process can move between the queues. And thus, much more efficient
than multilevel queue scheduling.
Characteristics of Multilevel Feedback Queue Scheduling:
• In a multilevel queue-scheduling algorithm, processes are permanently assigned to a
queue on entry to the system, and processes are not allowed to move between queues.
• As the processes are permanently assigned to the queue, this setup has the advantage of
low scheduling overhead, But on the other hand disadvantage of being inflexible.
Advantages of Multilevel feedback queue scheduling:
• It is more flexible
• It allows different processes to move between different queues
Disadvantages of Multilevel feedback queue scheduling:
• It also produces CPU overheads
• It is the most complex algorithm.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed
article on Multilevel Feedback Queue Scheduling.

5. Conclusion
Scheduling algorithms should not affect the behavior of the system (same results regardless
of schedule). However, the algorithms do impact the system's efficiency and response time.
The best schemes are adaptive.
Priority scheduling is one of the most common scheduling algorithms in batch systems.
Each process is assigned a priority. The process with the highest priority is to be executed
first and so on. Processes with the same priority are executed on a first-come first served
basis.

References

10
CPU Scheduling

1).https://www.geeksforgeeks.org/what-is-an-operating-system
2).https://en.wikipedia.org/wiki/Operating_system
3).https://courses.lumenlearning.com/wm-compapp/chapter/identifyingyouroperating-
system-os/

11