This report will be about simulations of
CPU scheduling (Algorithm Evaluation). The central processing unit or as it
referred to the CPU is a processor that is responsible for giving instructions
to the computer so it would know what to do. The CPU lets the computer know
when it should follow out certain instructions which as people know is a
program. This program will receive information and will input all of the
information from a device and process all of it so the computer could
understand it and output the information. Most technology nowadays has a CPU
built into it the most commonly known products are mobile phones and computers
however many other devices also have a CPU such as washing machines, DVD
players, printers and many more. Most CPUs are contained on a singular
integrated circuit chip they are very small but very powerful. However you can
get multicore processors as well but they are still a single chip but they
contain a few CPUs on it which is classed as cores. This report will talk about
the importance of scheduling and how it’s a fundamental to operating systems.
It will also contain information on how to get a more accurate evaluation of
scheduling algorithms by using simulations. The report will talk about how to
create a simulation, how it will work and how it will process information. Will
show how and why when variables value is increased the simulator modifies the
system state to reflect the activities of the devices, the process and the
scheduler that keeps everything intact and running smoothly.
Scheduling is very important
to an operating system it is a necessity and fundamental function for an
operating system to be able to run. A queue is created when the CPU is not in
use and the operating system is left to figure out which process it needs to
get ready to execute. So how does the CPU know which process should be carried
out first? Well the CPU works out the order and importance of a process by the
helpful hand of the short term scheduler. The short term scheduler selects
which process should be carried out. The short term scheduler creates a queue
where it lines up all the processes waiting to run on the CPU. When priorities
are acquired the information will be passed onto the dispatcher. A dispatcher
is another fundamental. Dispatchers hand over control to the processes so they
can run on the CPU that is selected by the short term scheduler.
The purpose of this
assignment is to simulate algorithms to achieve a more accurate and precise
evaluation on how a choice of certain scheduling algorithms can effect CPU
utilization and how effective schedulers are when they assign processors to any
process. There are a few different scheduling algorithms that run differently
and have different properties from each other some may run better than others
on selected scenarios. As different processes need to run at different times
and different orders so the selection of different algorithms can help select
which one is best for the case.
A system always has a strategy which is called
a Process scheduling Policy what this does is it decides which is going to run
at a given time. So when a system has a choice of which process to execute the
process scheduling policy steps in and decides what should be dealt with first.
However there is also a scheduler and a dispatcher that also have jobs to do.
These two the scheduler and dispatcher assign a processor to the selected
process. Every process has its own
identity and own address which consists of three things which is the stack
region, data region and the data region. These three things help identify each
process and give it individuality. The stack region stores all the instruction
and local variables that are used for active procedure calls. The contents of
the stack tend to grow as the process issues are issued and then get smaller
when the procedures return. The data region works by storing all the variables
and dynamically allocated memory that process uses during execution. The text
region works by storing all the codes that processor has to execute.
What is a scheduling algorithm? Well a
scheduling algorithm is a method which gives certain things access to system
resources so threads, processes or data flows can get access to processor time
and communications bandwidth. Scheduling algorithms are used to meet target
quality and to be the most effective. As all CPUs need to be able to multi task
there needs to be some sort arrangement for the CPU to be able to carry out all
the tasks that it needs too. More than one process needs to be executed at a
time so the algorithms help set priorities and keep things running smoothly.
There are a few CPU scheduling algorithms out there but this
report will be focused on FCFS (First Come First serve), Non preemptive SJF (Shortest
Job First) and RR (Round Robin). Each of the algorithms work in different ways.
FCFS (First Come First Serve) – Is very self-explanatory and
works in a simple basic fashion. As suggested in the name the first process to
arrive will be processed. This scheduling algorithm is definitely one of the simplest
for sure. So the process first to request the CPU will be allocated it first.
When the first process in the front of the queue is dealt with it is removed
from queue and it moves onto the next one in line. However FCFS has issues
because it produces long waiting times. This is because it may take a while for
the process in the front of the queue to come through.
Non preemptive SJF
(Shortest Job First) – non preemptive means a one in one out basis. So one task
will be carried out until it is completely finished before another one will get
started. No interruptions will occur to the current process that is running.
The process will be kept in the scheduler until it is completely finished and
ready to move onto the next one. This will generally cause a big queue to pile
up which would equal to longer waiting times. This algorithm is also very
straight forward it says it all in the name. SJF will work by picking the smallest
and fastest little job to do first and get it out the way and then move onto
the next smallest and fastest job in the queue. This works by picking the next
shortest CPU burst and not the overall process time. Priorities are set in SJF
so the smaller jobs have priority over others so the larger the CPU burst the
lower priority it has.SJF can be proven to be one of the faster algorithms
however it has a fault of not knowing how long the next CPU burst will be which
RR (Round Robin) – Round Robin scheduling works very similar to
FCFS however it adds quantum timing to it. This means that CPU bursts are assigned
time quantum’s. This means that when a process is assigned the CPU a timer is
set for as long as the value has been set for time quantum. A time quantum is
usually somewhere between 10 to 100 milliseconds long. This works by the
scheduler going through the queue of processes waiting in line and allocates
each process a time interval it can use. This means that each process in the
queue will be added in the queue with a timer so the scheduler selects a process
to go first and when it starts getting processed a timer is set for how long it
can process until the time quantum nterrupts and dispatches the process.
FCFS (First Come First Serve) results – As mentioned before
usually FCFS is waiting times turn out to be longer and this simulation proved
the point. The waiting time did end up being longer. This happened because if a
process is longer then it will take up more time. So if a longer process is
first in the queue it will be allocated processor time and if the processing
time is long it will hold up the CPU. This means that other processes will be
waiting for long amount of times until the process is finished and is ready to
move onto the next one in the queue.
Non preemptive SJF
(Shortest Job First) – This algorithm had its advantages as it gave shorter
processes preference. This would mean all the shorter processes would be done
and finished and out of the way. So this would give it an advantage as it would
be done with all the short easy jobs and then could move on faster. This means that
the average waiting times would decrease using this algorithm however this
would increase the throughput in the system.
RR (Round Robin) results – Round Robin results showed that the process
time is minimised if the CPU bursts finish with in one quantum. However if a
time quantum is made too large then this means that it will just turn into a FCFS
algorithm. This shows that RR is very sensitive to the time quantum and it
needs to be set right. However RR establishes fairness to the processes because
all the processes are treated equally. If the time quantum is kept low then RR
performs well and reduces waiting times.