PROCESS SCHEDULING ALGORITHMS
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:
- Start the program.
- Get the number of processes and their burst time.
- Initialize the waiting time for process 1 and 0.
- Process for(i=2;i<=n;i++),wt.p[i]=p[i-1]+bt.p[i-1].
- The waiting time of all the processes is summed then average value time is calculated.
- The waiting time of each process and average times are displayed
- 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.
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.
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:
- Start the program. Get the number of processes and their burst time.
- Initialize the waiting time for process1 as 0.
- The processes are stored according to their burst time.
- 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] - The waiting time of all the processes summed and then the average time is calculated.
- The waiting time of each processes and average time are displayed.
- Stop the program
C PROGRAM :
#include<stdio.h>
struct process
{
int pid; int bt; int wt; int tt;
}p[10],temp;
int main()
{
int i,j,n; float avg1,avg2,totwt,tottt;
printf("\n***Non Preemptive SJF***\n");
printf("\nEnter the number of process:\t");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
p[i].pid=i; printf("Enter the burst time:\t");
scanf("%d",&p[i].bt);
}
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if(p[i].bt>p[j].bt)
{
temp.pid=p[i].pid;
p[i].pid=p[j].pid; // id swap
p[j].pid=temp.pid;
temp.bt=p[i].bt;
p[i].bt=p[j].bt; // bt swap
p[j].bt=temp.bt;
}
}
}
p[1].wt=0;
p[1].tt=p[1].bt+p[1].wt;// p[1].wt=0
i=2;
while(i<=n)
{
p[i].wt= p[i-1].bt + p[i-1].wt;
p[i].tt=p[i].bt+p[i].wt;
i++;
}
i=1;
totwt=tottt=0.0;
printf("\nPROCESS ID \tBT \tWT \tTT");
while(i<=n){
printf("\n\t%d \t%d \t%d \t%d\n",p[i].pid,p[i].bt,p[i].wt,p[i].tt);
totwt=p[i].wt+totwt;
tottt=p[i].tt+tottt;
i++;
}
avg1=totwt/n;
avg2=tottt/n;
printf("\nAvg WaitingTime= %f\t Avg TurnaroundTime= %f \n",avg1,avg2);
return 0;
}INPUT/OUTPUT:
***Non Preemptive SJF***
Enter the number of process: 3
Enter the burst time: 2
Enter the burst time: 4
Enter the burst time: 6
PROCESS ID BT WT TT
1 2 0 2
2 4 2 6
3 6 6 12
Avg WaitingTime= 2.666667 Avg TurnaroundTime= 6.666667The Output is hopefully clear to you.
PREEMPTIVE
ALGORITHM:
Steps:
1. Start
2. Traverse until all every process completed their execution.
3. In every single time lap find process with minimum remaining time.
4. Decrement its time by 1.
5. Check if its remaining time becomes 0
6. Increment the counter of process completion.
7. Completion time of current process =
current_time +1;
8. Calculate waiting time for each completed
process.
wt[i]= Completion time - arrival_time-burst_time
9. Increment time lap by one.
10. Find turnaround time (waiting_time+burst_time).
11. Print
12. Stop
PYTHON PROGRAM:
# third left bracket is [
print("***Preemptive SJF***")
proc=[[1,6,1],[2, 8, 1], [3, 7, 2], [4, 3, 3]]
n = 4
#avg
wt=[0]*n
tat=[0]*n
#waiting
# burst time is runtime rt
rt=[0]*n
#copy the burst time into rt[]
for i in range(n):
rt[i]=proc[i][1]
complete=0
t=0
minm=9999999999
short=0
check=False
# Until all processes gets completed.
while(complete!=n):
# Find process with minimum remaining
# time among the processes that
# arrives till the current time
for j in range(n):
# [1,5,1],[2, 8, 1], [3, 7, 2] IN NEXT T=2, minm=5
# [1,4,1],[2, 8, 1], [3, 7, 2], [4, 3, 3] IN NEXT T=3, minm=4
# [1,4,1],[2, 8, 1], [3, 7, 2], [4, 2, 3] IN NEXT T=4, minm=2
# [4, 2, 3] ENDS, [1,4,1] ENDS, [3, 7, 2] ENDS, [2, 8, 1] ENDS
if((proc[j][2]<=t) and (rt[j]<minm) and (rt[j]>0)):
minm=rt[j]
short=j
check=True
#when t=0 it doesnot executed.
#check arrival time and process burst time
if(check==False):
t+=1
continue #next iteration in while
#reduce remaining time by 1
rt[short]-=1 # 6-1=5
#Update minimum
minm=rt[short] #minm=5
if(minm==0):
minm=9999999999
# If a process gets completely executed
if(rt[short]==0):
#increment complete
complete+=1
check=False
# find finish time of current process
fint=t+1 # total t or 1sec iteration total
#calculate waiting time
wt[short]=(fint- proc[short][1]- proc[short][2])
if (wt[short] < 0):
wt[short]=0
t+=1 # t=2 in next
#tAT
#calculate turnaround time
for i in range(n):
tat[i]= proc[i][1]+ wt[i]
#avg
print("Processes Burst Time Waiting",
"Time Turn-Around Time")
total_wt = 0
total_tat = 0
for i in range(n):
total_wt = total_wt + wt[i]
total_tat = total_tat + tat[i]
print(" ", proc[i][0], "\t\t", proc[i][1], "\t\t",
wt[i], "\t\t", tat[i])
print("\nAverage waiting time = %.5f "%(total_wt /n) )
print("Average turn around time = ", total_tat / n)
INPUT/OUTPUT(PREEMPTIVE):
***Preemptive SJF***
Processes Burst Time Waiting Time Turn-Around Time
1 6 3 9
2 8 16 24
3 7 8 15
4 3 0 3
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.
| PROCESS | PRIORITY | ARRIVAL TIME | CPU TIME |
| P1 | 5 | 7 | 3 |
| P2 | 1 | 1 | 1 |
| P3 | 3 | 2 | 3 |
| P4 | 2 | 1 | 4 |
| P5 | 4 | 5 | 2 |
According to the priority scheduling the Gantt chart will be
| P2 | P4 | P3 | P5 | 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 |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
Gantt Chart
| P1 | P2 | P3 | P1 | P2 | P1 | P1 | P1 | P1 | P1 | P1 | P1 | P1 | P1 | P1 |
ALGORITHM:
1. Get the number of process and their burst time.
2. Initialize the array for Round Robin circular queue as ‘0’.
3. The burst time of each process is divided and the quotients are stored on the round
Robin array.
4. According to the array value the waiting time for each process and the average
time are calculated as line the other scheduling.
5. The waiting time for each process and average times are displayed.
6. Stop the program
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
Enter Total Process: 3
Process Process Number 1 :
Enter Arrival Time: 0
Enter Burst Time: 2
Process Process Number 2 :
Enter Arrival Time: 0
Enter Burst Time: 4
Process Process Number 3 :
Enter Arrival Time: 0
Enter Burst Time: 6
Enter Time Quantum: 10
Process |Turnaround Time|Waiting Time
P[1] | 2 | 0
P[2] | 6 | 2
P[3] | 12 | 6
Average Waiting Time= 2.666667
Avg Turnaround Time = 6.666667
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
Hope you learn something new today, enjoy & love :)
Comments
Post a Comment