Abstract

This project gives the graphical representation of three operating system scheduling algorithms.
CPU scheduling is a process which allows one process to use the CPU while the execution of
another process is on hold(in waiting state) due to unavailability of any resource like I/O etc,
thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient,
fast and fair. To decide which process to execute first and which process to execute last to
achieve maximum CPU utilisation, computer scientists have defined some algorithms, they
are:

1. First Come First Serve(FCFS) Scheduling

2. Shortest-Job-First(SJF) Scheduling
3. Priority Scheduling
4. Round Robin(RR) Scheduling
5. Multilevel Queue Scheduling
6. Multilevel Feedback Queue Scheduling

We will be discussing First Come First Serve(FCFS) Scheduling, Shortest-Job-First(SJF)

Scheduling, Round Robin(RR) Scheduling algorithms

Introduction:
A typical process involves both I/O time and CPU time. In a uni programming system like
MS-DOS, time spent waiting for I/O is wasted and CPU is free during this time. In multi
programming systems, one process can use CPU while another is waiting for I/O. This is
possible only with process scheduling.

Process scheduling is done so that maximum CPU utilization [Keep CPU as busy as
possible],fair allocation of CPU, maximum throughput [Number of processes that complete
their execution per time unit], minimum turnaround time [Time taken by a process to finish
execution],minimum waiting time [Time a process waits in ready queue] ,minimum response
time [Time when a process produces first response.]

The three scheduling algorithms implemented by our project is

1. First Come First Serve(FCFS) Scheduling

Simplest scheduling algorithm that schedules according to arrival times of processes. First
come first serve scheduling algorithm states that the process that requests the CPU first is
allocated the CPU first. It is implemented by using the FIFO queue. When a process enters
the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is
allocated to the process at the head of the queue. The running process is then removed from
the queue. FCFS is a non-preemptive scheduling algorithm. First Come First Serve (FCFS) is
an operating system scheduling algorithm that automatically executes queued requests and
processes in order of their arrival. It is the easiest and simplest CPU scheduling algorithm. In
this type of algorithm, processes which requests the CPU first get the CPU allocation first.
This is managed with a FIFO queue. The full form of FCFS is First Come First Serve.

As the process enters the ready queue, its PCB (Process Control Block) is linked with the tail
of the queue and, when the CPU becomes free, it should be assigned to the process at the
beginning of the queue.

2. Shortest-Job-First(SJF) Scheduling

Process which have the shortest burst time are scheduled first.If two processes have
the same bust time then FCFS is used to break the tie. It is a non-preemptive
scheduling algorithm. In this algorithm in which the process having the smallest
execution time is chosen for the next execution. This scheduling method can be
preemptive or non-preemptive. It significantly reduces the average waiting time for
other processes awaiting execution. It is associated with each job as a unit of time to
complete.This algorithm method is helpful for batch-type processing, where waiting
for jobs to complete is not critical.It can improve process throughput by making sure
that shorter jobs are executed first, hence possibly have a short turnaround time. It
improves job output by offering shorter jobs, which should be executed first, which
mostly have a shorter turnaround time.
3. Round Robin(RR) Scheduling

Each process is assigned a fixed time(Time Quantum/Time Slice) in cyclic way.It is designed
especially for the time-sharing system. The ready queue is treated as a circular queue. The CPU
scheduler goes around the ready queue, allocating the CPU to each process for a time interval
of up to 1-time quantum. To implement Round Robin scheduling, we keep the ready queue as
a FIFO queue of processes. New processes are added to the tail of the ready queue. The CPU
scheduler picks the first process from the ready queue, sets a timer to interrupt after 1-time
quantum, and dispatches the process. One of two things will then happen. The process may
have a CPU burst of less than 1-time quantum. In this case, the process itself will release the
CPU voluntarily. The scheduler will then proceed to the next process in the ready queue.
Otherwise, if the CPU burst of the currently running process is longer than 1-time quantum,
the timer will go off and will cause an interrupt to the operating system. A context switch will
be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will
then select the next process in the ready queue.

Some key points to note:

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

Motivation
In the sixth semester course work of our engineering curriculum apart from computer
graphics and visualization we also have operating systems as one of our subjects. CPU
scheduling and CPU scheduling algorithms are an important topic included in the
operating systems syllabus. Therefore by implementing the above given scheduling
algorithms we get a better understanding of how the CPU scheduler works.
Therefore by combining the concepts we learn in operating systems we can implement it
using the function and other utilities we are taught in computer graphics. This way we are
putting to use what we are taught and implementing the same. Apart from the above
mentioned reasons CPU scheduling algorithms provide a great opportunity to implement
graphics. The gantt chart produced by each algorithm can be produced through the
various graphics utilities. By producing the gantt chart through graphics we get a clear
and descriptive chart that clearly highlights the arrival time of the processs, the time slice
the process can execute for and the burst time of the process split into the respective time
slice. Hence we are implementing a complex operating system concept in such a
mechanism that allows anybody with basic operating system knowledge to easily
comprehend the working of process scheduling.

Existing System:
The current systems available for the implementation of CPU scheduler algorithms are
either simple programs that just take in the number of processes along with their arrival
time and burst time and merely display the waiting time and turnaround time. These
programs are usually written in C,C++,Java or other programming languages.
The existing system takes in a finite number of processes and will compute the average
waiting time and turnaround time.
Another system in existence for the implementation of CPU scheduling algorithms is a
hardcoded program , that has pre-defined values for the process arrival time and the user
can merely just enter the burst time for each process. Upon which the program will
perform the calculations using formulas that have been given , to compute the average
waiting time, or the waiting time of the of each process , the average turnaround time or
the turnaround time for each process.

Limitations of Existing System:

The drawbacks or limitations of the above mentioned system are:
• Concept of Gantt chart does not come into picture.
• The concepts of pre-emption and non pre-emption are not clearly distinguished
• Given a time slice , or time quantum user is not aware of the order of process
execution
• There is no graphical representation , thereby making the working of the
algorithm unclear.
• Only the final result is displayed, the intermediate calculations are unclear or not
displayed
• In programs where arrival time is hard coded , the implementation of most the
algorithms are restricted.