Scheduling Algorithms

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.