Scheduling
Algorithms
Process scheduling allows OS to
allocate a time interval of CPU execution for each process. Another important reason
for using a process scheduling system is that it keeps the CPU busy all the
time.
A Process Scheduler schedules
different processes to be assigned to the CPU based on particular scheduling
algorithms. There are six popular process scheduling algorithms.
- First-Come, First-Served (FCFS) Scheduling
- Shortest-Job-Next (SJN) Scheduling
- Priority Scheduling
- Shortest Remaining Time
- Round Robin(RR) Scheduling
- Multiple-Level Queues Scheduling
1. First-Come First-Served Scheduling
It is a simplest CPU scheduling algorithm.
According to this, the process that requests the CPU first is allocated at the
CPU first. FCFS is managed with the help of the FIFO queue. When a process
enters into a ready queue it will link up at the tail of the queue and when the
CPU is free it allocates the process at the head of the queue and by this
running, the process is removed from the queue.
Consider the following process
that arrives at a time 0 with the CPU burst time in milliseconds.
If the process arrives in the
order of P1, P2, P3 in order of FCFS then the Gantt chart
for this will be:
average waiting time will
be : (0+26+28)/3 = 18. The FCFS scheduling algorithm is non
pre-emptive.
2. Shortest Job
first scheduling
According to this algorithm when
the CPU is free, the process will be assigned which will have the smallest next
CPU burst. SJF is optimal which means it will provide the average waiting time
for a given set of processes.
SJF can be either preemptive or
non-preemptive. Preemption occurs when a new process arrives in the ready queue
that has a predicted burst time shorter than the time remaining in the process
whose burst is currently on the CPU. Preemptive SJF is sometimes referred to
as shortest remaining time first scheduling.
Let us consider an example with
the following set of processes, with the length of CPU burst time given in
milliseconds.
i.e. average time by using SJF
is (0+3+9+16)/4 =7 milliseconds. As SJF is an optimal
algorithm which cannot be implemented at the level of short term CPU scheduling
as there is no way to know that the length of the next CPU burst.
3. Priority
Scheduling
In these algorithms, a priority
is associated with a process and by that CPU will be allocated to the process
which will have the highest priority.
Priorities can be assigned either
internally or externally. Internal priorities are assigned by the OS using
criteria such as average burst time, ratio of CPU to I/O activity, system
resource use, and other factors available to the kernel. External priorities
are assigned by users, based on the importance of the job, fees paid, politics,
etc.
Priority scheduling can be either
preemptive or non-preemptive.
Priority scheduling can suffer
from a major problem known as indefinite blocking, or starvation,
in which a low-priority task can wait forever because there are always some
other jobs around that have higher priority.
One common solution to this
problem is aging, in which priorities of jobs increase the
longer they wait. Under this scheme a low-priority job will eventually get its
priority raised high enough that it gets run.
Consider an example with
the following set of the process with the length of the CPU burst time given in
milliseconds.
In this case, the average waiting
time is (0+1+6+16+18)/5 =8.2 milliseconds.
4. Round-Robin
Scheduling
The round-robin (RR) scheduling
algorithm is designed especially for timesharing systems. It is similar to FCFS
scheduling, but preemption is added to enable the system to switch between processes.
A small unit of time, called a time quantum or time slice, is
defined.
When a process is given the CPU,
a timer is set for whatever value has been set for a time quantum.
- If the process finishes its
burst before the time quantum timer expires, then it is swapped out of
the CPU just like the normal FCFS algorithm.
- If the timer goes off
first, then the process is swapped out of the CPU and moved to the back
end of the ready queue.
The ready queue is maintained as
a circular queue, so when all processes have had a turn, then the scheduler
gives the first process another turn, and so on.
RR scheduling can give the effect
of all processors sharing the CPU equally, although the average wait time can
be longer than with other scheduling algorithms.
The performance of RR is
sensitive to the time quantum selected. If the quantum is large enough, then RR
reduces to the FCFS algorithm; If it is very small, then each process gets
1/nth of the processor time and share the CPU equally.
If time quantum is of 4
milliseconds
5. Multilevel Queue
Scheduling
A multilevel queue scheduling
algorithm partitions the ready queue into several separate queues. The
processes are permanently assigned to one queue, generally based on some
property of the process, such as memory size, process priority, or process
type. Each queue has its own scheduling algorithm.
In addition, there must be
scheduling among the queues, which is commonly implemented as fixed-priority
preemptive scheduling.
Another possibility is to
time-slice among the queues. Here, each queue gets a certain portion of the CPU
time,which it can then schedule among its various processes.
6. Multilevel
Feedback-Queue Scheduling
Multilevel feedback queue
scheduling is similar to the ordinary multilevel queue scheduling, except jobs
may be moved from one queue to another for a variety of reasons:
- If
the characteristics of a job change between CPU-intensive and I/O
intensive, then it may be appropriate to switch a job from one queue to
another.
- Aging
can also be incorporated, so that a job that has waited for a long time
can get bumped up into a higher priority queue for a while.
Multilevel feedback queue
scheduling is the most flexible, because it can be tuned for any situation. But
it is also the most complex to implement because of all the adjustable
parameters. Some of the parameters which define one of these systems include:
- The
number of queues.
- The
scheduling algorithm for each queue.
- The
methods used to upgrade or demote processes from one queue to another.
- The
method used to determine which queue a process enters initially.
Thank you sir
ReplyDelete