Scheduling types
Non-preemptive Scheduling :
In non-preemptive mode, once if a process enters into running state, it continues to execute until it
terminates or blocks itself to wait for Input/Output or by requesting some operating system service.
Preemptive Scheduling :
In preemptive mode, currently running process may be interrupted and moved to the ready State by the
operating system.
When a new process arrives or when an interrupt occurs, preemptive policies may incur greater
overhead than non-preemptive version but preemptive version may provide better service.
It is desirable to maximize CPU utilization and throughput, and to minimize turnaround time, waiting
time and response time.
Scheduling Algorithms
Scheduling algorithms or scheduling policies are mainly used for short-term scheduling. The main
objective of short-term scheduling is to allocate processor time in such a way as to optimize one or more
aspects of system behavior.
For these scheduling algorithms assume only a single processor is present. Scheduling algorithms decide
which of the processes in the ready queue is to be allocated to the CPU is basis on the type of scheduling
policy and whether that policy is either preemptive or non-preemptive. For scheduling arrival time and
service time are also will play a role.
List of scheduling algorithms are as follows:
First-come, first-served scheduling (FCFS) algorithm
Shortest Job First Scheduling (SJF) algorithm
Shortest Remaining time (SRT) algorithm
Non-preemptive priority Scheduling algorithm
Preemptive priority Scheduling algorithm
Round-Robin Scheduling algorithm
Highest Response Ratio Next (HRRN) algorithm
Multilevel Feedback Queue Scheduling algorithm
Multilevel Queue Scheduling algorithm
For describing various scheduling policies, we would use the following information, present below:
Process|Arrival time|Service time (Burst time)|Priority
P1 |0 |4 |2
P2 |3 |6 |1
P3 |5 |3 |3
P4 |8 |2 |1
First-come First-served Scheduling (FCFS)
First-come First-served Scheduling follow first in first out method. As each process becomes ready, it
joins the ready queue. When the current running process ceases to execute, the oldest process in the
Ready queue is selected for running. That is first entered process among the available processes in the
ready [Link] average waiting time for FCFS is often quite long. It is non-preemptive.
TURNAROUND TIME=WAITING TIME + SERVICE TIME
Advantages
Better for long processes
Simple method (i.e., minimum overhead on processor)
No starvation
Disadvantages
Convoy effect [Link] very small process should wait for its turn to come to utilize the CPU.
Short process behind long process reults in lower CPU utilization.
Throughput is not emphasized.
Shortest Job First Scheduling (SJF)
This algorithm associates ith each process the length of the next CPU [Link]-job-first scheduling
is also called as shortest process next (SPN). The process with the shortest expected processing time is
selected for execution, among the available processes in the ready queue. Thus, a short process will
jump to the head of the queue over long jobs. If the next CPU bursts of two processes are the same then
FCFS scheduling is used to break the [Link] scheduling algorithm is probably optimal. It givs the
minimum average time for a given set of [Link] cannot be implemented at the level of short term
CPU scheduling. There is no way of knowing the shortest CPU burst.
SJF can be premptive or non-preemptive.
A premptive SJF algorithm will preempt the currently executing process if the next CPU burst of newly
arrived process may be shorter than what is left to the currently executing process.
A Non-premptive SJF algorithm will allow the currently running process to [Link] SJF
Scheduling is sometimes called Shortest Remaining Time First algorithm.
Advantages
It gives superior turnaround time performance to shortest process next because a short job is
given immediate preference to a running longer job.
Throughput is high.
Disadvantages
Elapsed time (i.e., execution-completed-time) must be recorded, it results an additional
overhead on the processor.
Starvation may be possible for the longer processes.
Priority Scheduling
The SJF is a special case of general priority scheduling algorithm.
A Priority (an integer) is associated with each [Link] CPU is allocated to the process with the
highest [Link] smallest integer is considered as the highest [Link] priority processes
are scheduled in First Come First serve [Link] can be preemptive or Non-preemptive.
Non-preemptive Priority Scheduling
In this type of scheduling the CPU is allocated to the process with the highest priority after completing
the present running process.
Advantage
Good response for the highest priority processes.
Disadvantage
Starvation may be possible for the lowest priority processes.
Preemptive Priority Scheduling
In this type of scheduling the CPU is allocated to the process with the highest priority immediately upon
the arrival of the highest priority process. If the equal priority process is in running state, after the
completion of the present running process CPU is allocated to this even though one more equal priority
process is to arrive.
Advantage
Very good response for the highest priority process over non-preemptive version of it.
Disadvantage
Starvation may be possible for the lowest priority processes.
Round-Robin Scheduling
This type of scheduling algorithm is basically designed for time sharing system. It is similar to FCFS with
preemption [Link]-Robin Scheduling is also called as time-slicing scheduling and it is a
preemptive version based on a clock. That is a clock interrupt is generated at periodic intervals usually
10-100ms. When the interrupt occurs, the currently running process is placed in the ready queue and
the next ready job is selected on a First-come, First-serve basis. This process is known as time-slicing,
because each process is given a slice of time before being preempted.
One of the following happens:
The process may have a CPU urst of less than the time quantum or
CPU burst of currently executing process be longer than the time quantum. In this case the a
context switch occurs the process is put at the tail of the ready queue.
In round-robin scheduling, the principal design issue is the length of the time quantum or time-slice to
be used. If the quantum is very short, then short processes will move quickly.
Advantages
Round-robin is effective in a general-purpose, times-sharing system or transaction-processing
system.
Fair treatment for all the processes.
Overhead on processor is low.
Overhead on processor is low.
Good response time for short processes.
Disadvantages
Care must be taken in choosing quantum value.
Processing overhead is there in handling clock interrupt.
Throughput is low if time quantum is too small.
Performance of RR Scheduling
If there are n processes in the ready queue and time quantum is q, then each process gets 1/n of
the CPU time in chunks of at most q time units at once.
No process waits for more than (n-1)*q time units until the next time quantum.
The performance of RR depends on time [Link] it is large then it is the same as FCFS. If q is small
then overhead is too high.