Scheduling Algorithms

Scheduling Criteria

Scheduling Algorithms – Different scheduling algorithms of CPU have different properties and the choice of the specific algorithm may favor one class or processor over other. Properties of algorithms are given as:

Scheduling Algorithms

There is a problem with CPU scheduling that is which process should be allocated to the CPU from ready queue there are several different CPU scheduling algorithms.

First Come, First Server(FCFS) Scheduling

In this scenario CPU will be allocated to the process which request first. Whenever a process enters into the ready queue its PCB is linked with the tail of the queue.

Suppose that processes arrive in ready queue in order P1, P2, P3, P4. The Gantt chart represent the scheduling of the above processes as

Average waiting time: 0+14+22+31= 67

FCFS scheduling algorithm is a type of non-preemptive scheduling. Convoy Effect can be used which is described as shortest process is behind long process. According to the above given example convoy effect will work as

Average waiting time: 19+2+10+0=31. It reduces the avg. waiting time.

The FCFS scheduling algorithm is basically non-preemptive, once the CPU has been allocated to a process, that process retains the CPU while waiting for it to releases the CPU, either by requesting I/O or by terminating. The FCFS algorithm is hence mostly troublesome for time-sharing systems, where it is important that each user get a share of the CPU at regular intervals.

Shortest-Job-First(SJF) Scheduling

This SJF algorithm links with each process the length of the process’s next CPU burst. When the CPU is free, it is allocated to the process that has the smallest next CPU burst. FCFS scheduling is used to break the tie, in case if the next CPU bursts of two processes are the equivalent.

SJF scheduling chart shown as:

Average waiting time = (6+12+2+0) / 4 = 5

The SJF scheduling algorithm is proven optimal, that provides the minimum average waiting time for a given set of processes. Moving a short process before a long one reduces the waiting time of the short process more than it increases the waiting time of the long process this is the drawback of SJF scheduling algorithm. Preemptive version called shortest-remaining-time-first

Priority Scheduling

The SJF algorithm is a superior case of the general priority schedulingalgorithm.A priority is linked with each process and the CPU is assigned to theprocess with the top priority. In case of equal priority processes FCFS order is used for scheduling. SJF algorithm is basically a priority algorithm in which the priority (p) is theinverse of the (predicted) next CPU burst. The longer the CPU burst, thelesser the priority, and vice versa.

NOTE: Priorities are usually specified by some fixed range of numbers, such as 0 to 7 or 0 to 4,095.

The average waiting time is 6.8 milliseconds.

A most important drawback of priority scheduling algorithms is unlimited blocking, or starvation.
Starvation: A process which is ready to run but waiting for the CPU may be considered blocked or in starvation condition. A priority scheduling algorithm may leave some low priority processes waiting for an indefinite period. In case of  starvation low priority processes may never execute. A solution of infinite blockage of low-priority processes is aging. Aging is a technique of slowly increasing the priority of processes that wait in the system for a long time

Round-Robin Scheduling

This algorithm is designed especially for timesharing system its identical with FCFS but preemption is added to switch b/w processes. A time quantum or time slice generally from 10 to 100 milliseconds which is basically a small unit of time. Each and every process gets a small unit of CPU time (time quantum q), After this time has passed, the process is preempted and added to the end of the ready queue. Two things happen when a CPU (1 q) allocated to a process, the process can have a CPU burst of less than 1-time quantum. In this situation, the process itself will release the CPU voluntarily. Then the scheduler will proceed to the next process in the ready queue.

In this if the burst is more than 1 q time then the timer will go off and will generate an interrupt to the operating system. A context switch will be executed, and the process will be set to the tail of the queue ready. The CPU scheduler will then select the following process in the

queue ready. Let’s take an example with time quantum 4

The Gantt chart is shown as:

CPU Scheduling