Operating System
provides an interface between a system program and user applications. In a
single processor system, the process waits until the CPU is free. It takes time
and we do not work on multiple programs through this. To resolve this problem
we use multitasking in which multiple processors work concurrently and improve
the efficiency of CPU.The main concept of multitasking is to share the
resources among different processes. Around all the resources are scheduled in
a proper way before using it. Scheduling provides a better and effective way to
enhance the performance of CPU.
CPU scheduling provides a better way to check
which process is to run among all the processes. Need for computer scheduling
is necessary when we want to achieve fast computer system and run multiple
programs on a system.CPU scheduling is important because of its effects on the
resource allocation, CPU utilization, turnaround time, waiting for time,
throughput and other performances.
Existing CPU
scheduling algorithms are First-Come-First-Served (FCFS), Shortest-Job-First
(SJF), Round Robin (RR), and Priority Based Scheduling. These algorithms are
used to improve the efficiency of CPU and minimize the waiting time, turnaround
time, waiting time and number of context switching. There are some scheduling
parameters which determine which scheduling algorithm satisfied all its
parameter and perform better result. These are some scheduling parameter, on
the basis of these parameters we decide that which one algorithm is best.
Scheduling Parameters
These are some
scheduling parameter and we want to use that algorithm which may provide better
result according to situation and environment. These are some as follow:
Context-Switching: It
will happen when one process can interrupt the normal execution of a process.
We want to use that type of schedule which reduces context switching because it
is the wastage of time and memory.
CPU Utilization: CPU
idles when the CPU works on 100% that is not in possible in reality. Real-time
operating system, CP work on 40% to 90% which is said to be lightly loaded too
heavily loaded.
Turnaround Time: Time
required for a particular process to its completion in from ready to its
execution.
Waiting Time: When
the process is in ready queue and waiting for its turn. A process executed
properly after entering its execution queue. We want to use that scheduling
algorithm that reduced the waiting time of a process.
Response Time: It
takes the time to start the execution of a process and CPU perform in it’s an
efficient way when we minimize the response time. To overcome that problem to
achieved the best CPU utilization.
Literature Survey
There are several
techniques works done on CPU scheduling which worked on throughput, arrival
time and response time. Working on CPU scheduling improved with the passage of
time. The author {Chhugani, 2017 #1} worked on dynamic time quantum that
calculates scheduling parameter of CPU. The result shows that how to increase
the time quantum for few processor due to the threshold value. The author
{Rajput, 2012 #2} proposed an algorithm which based on priority based algorithm
and compares with standard round robin. The fuzzy technique based on pre
priority and execution time and compare with the different algorithm and shows
better results in {Kumari, 2017 #3}. V FJFDRR focused on round robin with dynamic
time slice and compare with the different technique and shows the better result
in {Mohanty, 2012 # 4}. {Mohanty, 2012 #5} proposed a new technique that
calculates fit factor and dynamic time slice. Fit factor based on the
combination of FCFS, SJF, and priority algorithm and show the better result as
compared to the other scheduling algorithm. SJFDRR works on time quantum and
improves the efficiency of round robin. In this paper, there are user and
system priority. User priority has important than system priority and reduced
the context switching in {Gupta, 2016 #6}. Self Adjustment Round Robin (SARR)
solves the problem of dynamic time-quantum that adjust the burst time according
to the running process. The Proposed algorithm can also be implemented on a large
processor and the operating system itself will find out the optimal time
quantum in {Matarneh, 2009 #7}. {Mohanty, 2011 #8} represents the algorithm
which is called priority-based dynamic round robin that calculates intelligent
time slice for individual process and changes the time slice before each
execution. FPRRDQ shows the better result as compared to other two which is
based on both the user priority and quantum time change after every execution
according to priority and burst time in {Srivastav, 2012 #9}. Optimum service
time concept for round-robin algorithm works on an optimum priority of each
process and placed in an order of execution according to calculated priority in
{Saxena, 2012 #10}.
FCFS work on the
basis of the FIFO. Each process executed according to its number. FCFS performs
well for smaller values. It shows poor waiting time, turnaround time for large
computation.SJF worked on the basis of shortest CPU burst length. In which short
process enter in execution queue and execute first. SJF perform best for long
processes as compared to FCFS. It is possible that long process waits in the
ready queue for short process that complete its task but sometimes it behaves
like starvation. RR worked in time quantum. RR worked good for short process
and give the result of minimum average time, minimum turnaround time and
minimum throughout. In real time system, the overhead invokes after each
context switching due to context switching increased for short time quantum. In
case of long-time quantum, Process executes within a single time slice and
performs better result. Priority-based algorithm worked on low and high
priority. Sometimes it becomes suffer a major problem called starvation because
low priority did not execute due to high priority.
To avoid the problem
of overhead and starvation, a new technique should be introduced to resolve
this problem and average waiting time, average turnaround time and average
response time should be increased.
Proposed Algorithm
Scheduling is the
technique used to enhance the performance of the CPU. To increase the CPU
utilization and reduced the average waiting time, average turnaround time and
average response time.CPU scheduling algorithm worked on maximize throughput. I
used two CPU scheduling algorithms and combined them in one that is SJF and
round robin. Both can combine and generate new technique that behaves well
effective. In this Technique, the processor is in ready queue in according to
CPU burst length, Shortest burst length is at the top of the queue. We tend to
assume two numbers to represent the burst length of the largest PCB within the
queue and the second one to represent the running time of all the processes
respectively. A Process control block (PCB) of a process is often submitted to
the system which is connected to the ready queue in according to the CPU.
The proposed
algorithm that is executed by the CPU linked to the process from the top of the
queue. Executed Process is expired after a given time quantum, which is defined
by the system. After that, new preemption is as follow:
te = te + quantum
time
Time quantum applies
to boost the efficiency and minimize the average waiting time average
turnaround time and average waiting and context switching between the
processes.
In that case, five
states are in the process which is new, ready, running, block and complete
state. The new state admitted the process and dispatch to the ready state. The
ready queue then moves forwards the process to the running state. If an
interrupt occur on ready state then it will back to the ready state if the
processor requires an I/O device then it moves to the block state and if the
process completed then it moves to the complete state. Block State complete the
requirement for the processor such that I/O and then moved to the ready queue.
Comparison of two numbers is as fellow:
If execution time of
a process te is less than the largest burst length of the PCB to then the
preempted process PCB is joined to the tail of the ready queue. After that, the
next process is then dispatched from the top of the ready queue.
If te ? to
Then the Process
control block (PCB) of the process with the largest CPU burst length is to
start the execution.
In Preemption, SJF is
in the ready queue that’s why shortest job entertained first. The value of te
is reset to 0 and the value of the CPU burst length of the largest PCB is reset
that is lying at the tail of the queue. After that, the next process is then
moving towards from the head of the ready queue.
When a process has
accomplished its task it terminates and deleted from the system. Then te will
be:
te = te + time to complete process
Method and actions
are same as a preempted process.
Result and discussion
Proposed algorithm
based on Round Robin and Shortest Job First. It performs better result and
enhances the performance of CPU. The result of average waiting time, average
turnaround time and average response time increased as compared to other
scheduling algorithms and shows optimum results.