Types of Scheduling Algorithms

1) First Come First Served Scheduling : In this Algorithm, Process that request CPU first, CPU is allocated first to that process .i.e. the algorithm is known as first come, first served. It based on FIFO (First in First Out) queue data structure. When a process entered in the ready queue, its Process Control Block (PCB) is added to end of the Queue. When CPU gets free after a process execution, a new process from the head of the queue is removed and enters in running state.

Let us discuss an example, some process p1, p2, p3, and p4 arrived at time 0, with the CPU burst.

Process CPU Burst

P1 20

P2 4

P3 6

P4 4

Gantt Chart Shown the result as below

Waiting time : Waiting time for process P₁=0, P2=20, P3=24 and P₄=30. Average Waiting time = (0+20+24+30)/4=18.4.

Example2 . If we Change the execution order of processes, like P4, P3, P2 and P1 then Gantt chart shown the result.

Waiting time : Waiting time for process P₁=14, P2=10, P3=4, and P₄=0.

Now Average Waiting Time = (0+4+10+14)/4=7

FCFS Scheduling algorithm suffered from Convoy effect. This effect resulted in lower CPU utilization and more waiting time.

In the list of processes, if one significant process gets CPU first, then all small process are waiting for getting the CPU.As a result, average waiting time is more in Example1.But If we talk about Example 2, Average waiting time is less.

FCFS is a non-preemptive algorithm. Once CPU has been allocated to a process, the process keeps the CPU until process itself terminate or any I/O request.

2) Shortest–Job–First Scheduling : SJF is a preemptive and Non-Preemptive algorithm. It based on length of latter’s next CPU burst. If a process acquired CPU and execution is going on, a new process with small CPU burst entered. Then CPU is preempted from current process and will give to further process. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie. Shortest Next CPUburst is also an appropriate term for SJF algorithm because scheduler examines the length of next CPU burst continuously.

Process CPU Burst

P1 20

P2 4

P3 6

P4 4

In above example, two processes P2, P4 have the same length. Now to break their tie FCFS algorithm is being used by system.P2 will process first and P4 follow it.

Gantt Chart Shown the result as below

Waiting time : Waiting time for process P₁=14, P2=0, P3=8 and P₄=4. Average Waiting time = (14+0+8+4)/4 = 6.5.

SJF scheduling algorithm is optimal because it gives average waiting time for a set of processes. If FCFS algorithm solves above example then average waiting time will be 18.4.

In SJF, shortest length run first which decrease the waiting time for small CPU burst process but increase the waiting time of lengthy processes, thus average waiting time decrease. SJF algorithm used in long-term scheduling. We can’t determine the length of next CPU burst, i.e., why it not used in short-term CPU scheduling.

Because of next CPU burst, SJF may be either preemptive or non-preemptive. If a new process arrives in the ready queue with greater CPU burst length, then non–preemptive SJF algorithm allow currently process to continue their execution till the termination. If the new process has shorter CPU burst, then preemptive SJF scheduling algorithm preempt the now process and assign the CPU to new process.Preemptive SJF scheduling also is known as Shortest Remaining Time first Scheduling.

Preemptive Scheduling Algorithm example:

Process CPU Burst (millisecond) Arrival Time

P1 10 0

P2 4 2

P3 6 4

P4 2 5

Gantt Chart Shown the result as below

In above example, Process P1 is running after 2 ms P2 enter in the ready queue with CPU Burst length 4.Now P1 is preempted, P2 gets CPU. In mid between of execution P3 and P4 get to enter with CPU burst 6,2.But P2 is not preempted, because of small burst. Don’t think that P4 process has small CPU burst 2, because till p4 entered into ready queue P2 has only one length CPU burst remain. Now p4, p3, and P1 get executed.

3) Priority Scheduling : SJF is a simple priority algorithm, where we are not considering the smallest next CPU burst, scheduler consider the priority of processes. The priority assigned to each process and CPU allocated to highest priority process. Equal priority processes scheduled in FCFS order.

Priority can be discussed regarding Lower and higher priority.Numbers denote it.We can use 0 for lower priority as well as more top priority.There is not a hard and fast rule to assign numbers to preferences.

Now in this example, we are using low numbers to represent higher priority.

Process CPU Burst Priority

P1 10 4

P2 4 1

P3 6 3

P4 5 2

Gantt Chart Shown the result as below

Average waiting time= (0+4+9+15) /4=28/4=7

Average time is 7 milliseconds.

We can compute the priority to a process by measuring internal or external factors. In Internal factors, we calculate priority by measuring time limits, memory requirements, number of open file and ratio of average I/o burst to average CPU burst of a process.In external factors, we consider the importance of process, amount of fund used for computer use and work type, etc.

Priority scheduling can be either preemptive or non-primitive. When a new process arrives in the ready queue with lower priority, then non–preemptive SJF algorithm allow currently process to continue their execution. If the new process has higher priority, then preemptive SJF scheduling algorithms preempt the currently process and assign the CPU to new process.

Priority Scheduling suffers from a starvation problem. The starvation problem leads to indefinite blocking of a process due to low priority. Every time higher priority process acquires CPU, and Low priority process is still waiting in the waiting queue. The aging technique gives us a solution to overcome this starvation problem in this technique; we increased the priority of process that was waiting in the system for a long time.

4) Round Robin Scheduling : Round Robin Scheduling algorithm designed for time-sharing systems. It is similar to FCFS scheduling but adding preemption to switch the processes after a small unit of time. A small unit of time is called a time quantum. A time quantum might be from 10 to 100 millisecond.

 

Process CPU Burst

P1 3

P2 4

P3 2

In above example, we have taken time quantum equal to 1 millisecond. After completion of time quantum, the process preempted, and the new process gets CPU.

Gantt Chart Shown the result as below

If time quantum is very large than RR scheduling algorithm treat as FCFS and if time quantum is small than RR called processor sharing.Processor sharing show to each process that they have their own processor.

The central concept is time switching in RR scheduling. If the context switch time is 10 percent of the time quantum then about 10 percent time will be spent in context switching.