PROCESS SCHEDULING ALGORITHMS

Process scheduling algorithm

Process scheduling algorithm

In this “PROCESS SCHEDULING ALGORITHMS” article, You can learn First-Come, First-Served (FCFS) Scheduling, Shortest-Job-Next (SJN) Scheduling, Priority Scheduling, Shortest Remaining Time, Round Robin(RR) Scheduling, and Multiple-Level Queues Scheduling algorithms.

PROCESS SCHEDULING ALGORITHMS

A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. There are six popular process scheduling algorithms given below with different arrival times, and priorities. Let’s understand all points.

First-Come, First-Served (FCFS) Scheduling
Shortest-Job-Next (SJN) Scheduling
Priority Scheduling
Shortest Remaining Time
Round Robin(RR) Scheduling
Multiple-Level Queues Scheduling

These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time, whereas preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state.

FIRST COME FIRST SERVE SCHEDULING

It termed as First Come First Serve (FCFS) Scheduling. As its name implies, the process arrives first in front of the CPU for processing, then that process executed first. It is a non-preemptive scheduling algorithm which means in this priority of processing does not matter, i.e., whatever the priority may be – the process executed in the manner they arrived.

It is also known as FIFO, i.e. first in first out. FIFO is page replacement algorithm. Don’t be confuse.

That is, the First process can execute directly, the Second process can execute after completion of the first process, and so on. The waiting time of every process is nothing but the difference between the previous process service time(turnaround time of the previous process) and the arrival time of that process. Completion time of every process is the addition of it’s turn around time with arrival time.

The FCFS scheduling algorithm is cover with arrival and without arrival time in this article.

ADVANTAGE AND DISADVANTAGE OF FCFS SCHEDULING

ADVANTAGE: 1. It is easy to implement. 2. It is easy to understand and remember. 3. Low priority processes can execute with higher priority processes. 4. In real-world, Many ticket counter follows this rule. 5. Less hesitation. 6. Non-preemption Scheduling.

DISADVANTAGE: 1. Non-Preemption scheduling, Long runtime process may cause for delays other process. 2. Higher priority cannot get chance.

What do you mean by convoy effect?

When some processes need to use the resource for a short interval of time but blocked by some other method which is holding the resource for a long time, this situation is known as Convoy Effect. It leads to poor utilization of resources which in result leads to poor performance.

ALGORITHM:

  1. Start the program.
  2. Get the number of processes and their burst time.
  3. Initialize the waiting time for process 1 and 0.
  4. Process for(i=2;i<=n;i++),wt.p[i]=p[i-1]+bt.p[i-1].
  5. The waiting time of all the processes is summed then average value time is calculated.
  6. The waiting time of each process and average times are displayed
  7. Stop the program

WITH OUT ARRIVAL TIME:

When considering without arrival time scenario, Execution of process can be done in a top-to-bottom fashion.

FCFS without Arrival time
FCFS without Arrival time

PYTHON PROGRAM :

bt=[]
wt=[]
tat=[]
avgtat=0
avgwt=0
n=int(input(“Enter the number of process: “))
for i in range(n):
val=int(input(“Enter the burst time “))
bt.append(val)
wt.insert(0,0)
tat.insert(0,bt[0])
for i in range(1,len(bt)):
wt.insert(i,wt[i-1]+bt[i-1])
tat.insert(i,wt[i]+bt[i])
avgwt+=wt[i]
avgtat+=tat[i]
avgwt=int((avgwt)/n)
avgtat=int((avgtat)/n)
print(“\n”)
print(“Process sid\tBT\tWT\tTT”)
for i in range(0,n):
print(“\t”+str(i+1)+”\t”+str(bt[i])+”\t”+str(wt[i])+”\t”+str(tat[i]))
print(“Avg Waiting Time= “+str(avgwt),end=’\t’)
print(“Avg Turn Arount Time= “+str(avgtat))

INPUT/OUTPUT:

enter the no of process 3
enter the burst time 2
enter the burst time 4
enter the burst time 6
Process sid bt wt tt
1 2 0 2
2 4 2 6
3 6 6 12
Avg Waiting time=2 Avg Turnaround time=6

.

WITH ARRIVAL TIME:

When considering without arrival time scenario, Execution of process can be done bt following the arrival time.

FCFS with Arrival Time
FCFS with Arrival Time

PYTHON PROGRAM:

bt=[]
wt=[]
tat=[]
at=[]
avgtat=0
avgwt=0
ct=0
n=int(input(“Enter the number of process: “))
for i in range(n):
print(“Process “,(i+1),”: “)
val=int(input(“Enter the burst time “))
bt.append(val)
val=int(input(“Enter the arrival time “))
at.append(val)
st=[0]*n #service time
st[0]=0
wt.insert(0,0)
tat.insert(0,bt[0])
for i in range(1,len(bt)):
st.insert(i,st[i-1]+bt[i-1])
wt.insert(i,st[i]-at[i])
if(wt[i]<0): # For non-negative constants
wt[i]=0
tat.insert(i,wt[i]+bt[i])
avgwt+=wt[i]
avgtat+=tat[i]
avgwt=int((avgwt)/n)
avgtat=int((avgtat)/n)
print(“\n”)
print(“Process sid\tBT\tWT\tTT\tCT”)
for i in range(0,n):
ct=tat[i]+at[i]
print(“\t”+str(i+1)+”\t”+str(bt[i])+”\t”+str(wt[i])+”\t”+str(tat[i])+”\t”+str(ct))
print(“Avg Waiting time= “+str(avgwt),end=’\t’)
print(“Avg Turn Arount Time= “+str(avgtat))

INPUT/OUTPUT:

Enter the number of process: 3
Process 1 :
Enter the burst time 2
Enter the arrival time 0
Process 2 :
Enter the burst time 4
Enter the arrival time 1
Process 3 :
Enter the burst time 6
Enter the arrival time 2

Process sid BT WT TT CT
1 2 0 2 2
2 4 1 5 6
3 6 4 10 12
Avg Waiting time= 1 Avg Turn Arount Time= 5

Thus the FIFO process scheduling program was executed and verified successfully. The average waiting time is not optimal. The process terminates after the completion of the execution. When the process terminated it is denoted as the Turnaround time. When the process enters into the execution part at that time minus arrival time is noted as Waiting time. Every process has its own waiting time and Turnaround time. The amount of time when the process gets CPU for execution is called Burst time.

SHORTEST JOB FIRST SCHEDULING

This program is to implement CPU scheduling algorithm for shortest job first scheduling. SJF is the short form of Shortest Job First scheduling algorithm. In this scheduling we consider shortest burst time. Process with shortest burst time can able to execute. Basically, Some sorting techniques are used in this program, based on that this scheduling is established.

Mainly note down that there are two approaches i.e. preemptive or non-preemptive. A process with the shortest burst time begins execution. If a process with even a shorter burst time arrives, the current process is removed or preempted from execution, and the shorter job is allocated CPU cycle.

It reduces the average waiting time over FIFO (First in First Out) algorithm. It gives the lowest average waiting time for a specific set of processes. SJF can’t be implemented for CPU scheduling for the short term. It is because there is no specific method to predict the length of the upcoming CPU burst.

In Preemptive Scheduling, there is the overhead of switching the process from ready state to running state, vise-verse, and maintaining the ready queue. Whereas in case of non-preemptive scheduling has no overhead of switching the process from running state to ready state.

NON PREEMPTIVE

ALGORITHM:

  1. Start the program. Get the number of processes and their burst time.
  2. Initialize the waiting time for process1 as 0.
  3. The processes are stored according to their burst time.
  4. The waiting time for the processes are calculated as follows:
    for(i=2;i<=n;i++) wt.p[i]=p[i=1]+bt.p[i-1]
  5. The waiting time of all the processes summed and then the average time is calculated.
  6. The waiting time of each processes and average time are displayed.
  7. Stop the program

C PROGRAM :

INPUT/OUTPUT:

The Output is hopefully clear to you.

PREEMPTIVE

ALGORITHM:

PYTHON PROGRAM:

INPUT/OUTPUT(PREEMPTIVE):

Here, Processes with a minimum remaining time gets the chance to execute. Preemptive means process which comes first gets executed until a process with minimum run time comes. On other hand, the process with the shortest remaining time can execute directly in non-preemptive SJF. Arrival time is another important time which makes all the confusions. Check online solutions if any problem arises.

PRIORITY SCHEDULING

The SJF algorithm is a special case of the general priority scheduling algorithm. A priority is associated with each process and the CPU is allocated to the process with the highest priority.

Equal priority processes are schedule in FCFS order. Priority scheduling can be either preemptive or non-preemptive. When a process arries on the ready queue, it’s parity is compare with the priority of the currently running process. 

A preemptive priority scheduling algorithm will be a preemptive CPU. If the priority of the newly arrived process is lower than the priority of the currently running process.

STARVATION AND AGEING:

A major problem with the priority scheduling algorithm is indefinite blocking. A process that is ready to run but lacking CPU can be considered blocked or waiting for the CPU. This is known as starvation. A solution to the problem of the indefinite blocking edge of low priority processes is Ageing. Ageing is a technique of gradually increasing the priority if process that waits in the system for a long time.


·        Priority scheduling is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems.

·        Each process is assigned a priority. The process with the highest priority is to be executed first and so on.

·        Processes with the same priority are executed on a first-come-first-served basis.

·        Priority can be decided based on memory requirements, time requirements, or any other resource requirement.

PROCESSPRIORITYARRIVAL TIMECPU TIME
P1573
P2111
P3323
P4214
P5452
PRIORITY SCHEDULING: 1 is the highest and 5 is the lowest priority

According to the priority scheduling the Gantt chart will be

P2P4P3P5P1
P2 executes first because it comes first and its priority is 1, P4 comes after P2 so P4 gets a chance at 2nd and its priority is 2, after that, P3 gets a chance and then P5 and then at last P1.

ROUND ROBIN SCHEDULING

In this “ROUND ROBIN SCHEDULING” article, You can learn these portions of round robin.

This type of algorithm is designed only for the time-sharing system. It is similar to FCFS scheduling with preemption condition to switch between processes. A small unit of time called quantum time or time slice is used to switch between the processes. The average waiting time under the round-robin policy is quite long.

The round-robin (RR) scheduling algorithm design specially for the time-sharing systems. It is similar to FCFS scheduling but preemptive is added to switch between processes. A small unit of time is called a Time Quantum or time slice.

  PROCESS   BURST  
P124
P23
P33
Arrival time: 0ms Quantum time: 2ms

Gantt Chart

P1P2P3P1P2P1P1P1P1P1P1P1P1P1P1
Thus, Quantum time: 2ms P1 executes fully when no process are there.

ALGORITHM:

C PROGRAM:

#include<stdio.h>
int main()
{
int count,j,n,time,remain,flag=0,time_quantum;
int wait_time=0,turnaround_time=0,at[10],bt[10],rt[10];
printf(“\nEnter Total Process: “);
scanf(“%d”,&n);
remain=n;
for(count=0;count0)
{
time+=rt[count];
rt[count]=0;
flag=1;
}
else if(rt[count]>0)
{
rt[count]-=time_quantum;
time+=time_quantum;
}
if(rt[count]==0 && flag==1)
{
remain–;
printf(“P[%d]\t|\t%d\t\t\t|\t%d\n”,count+1,time-at[count],time-at[count]-bt[count]);
wait_time+=time-at[count]-bt[count];
turnaround_time+=time-at[count];
flag=0;
}
if(count==n-1)
count=0;
else if(at[count+1]<=time)
count++;
else
count=0;
}
printf(“\nAverage Waiting Time= %f\n”,wait_time1.0/n); printf(“Avg Turnaround Time = %f\n”,turnaround_time1.0/n);
return 0;
}

INPUT/OUTPUT:

Enter Total Process: 3
Process Process Number 1 :
Enter Arrival Time: 0
Enter Burst Time: 24
Process Process Number 2 :
Enter Arrival Time: 0
Enter Burst Time: 3
Process Process Number 3 :
Enter Arrival Time: 0
Enter Burst Time: 3
Enter Time Quantum: 2

Process |Turnaround Time |Waiting Time

P[2] | 9 | 6
P[3] | 10 | 7
P[1] | 30 | 6

Average Waiting Time= 6.333333
Avg Turnaround Time = 16.333333

In Round Robin, Arrival time is another important time which makes all the confusions. Check online solutions if any problem arries.

If want to know about scheduling and schedulers, then please study

PROCESS SCHEDULING AND SCHEDULERS

Hope you learn something new today, enjoy & love 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami