In this post, let us give a quick review of different types of algorithms used in CPU scheduling. I will concentrate more on coding part than theory.
why scheduling?
All Modern computers have the multi-programming capability. This intuitively says that there should be a means of giving the CPU control to different processes. This is done through scheduling. We examine different algorithms and then code them.
types of scheduling:
There are two types of scheduling.
Non-preemptive Scheduling:In this method, once a process is given the control of CPU, it returns back to the operating system only after it gets terminated or switches to waiting state(due to some I/O operation).
Preemptive Scheduling:In this method, the operating system may take control and give it to other process even if the former one was in running state.
Properties of Scheduling Algorithms:
In order to decide which algorithm is the best, we need to have some criteria to compare them. They include the following:
CPU Utilization:
The CPU must be kept as busy as possible. In other words, the scheduling algorithm should not waste the CPU cycles unnecessarily. It should be in the range of 40% for lightly loaded system to 90% for heavily loaded systems.
Throughput:
The number of processes that have completed their execution per unit time is called throughput.
Turnaround time:
It is the measure of how much time a process took to finish its execution starting from its submission into the ready queue.
Waiting Time:
It is the measure of how much time a process has spend waiting for the CPU through out its execution.
Response time:
It indicates the time elapsed from its submission into the ready queue, until it has got the CPU for the first time. This parameter is useful for interactive systems.
Algorithms:
First-come First-served:
In this algorithm, the CPU is given to that process which has arrived first, irrespective of its Burst Time (Burst time is the measure of how long a process requires the CPU between I/O waits). Remember that, this algorithm is Non-preemptive.
Suppose, there is a process with huge burst time has arrived first, followed by processes with low burst time. Intuitively, we can see that the waiting time of the later processes is high. There will also be a convoy effect which states that either cpu or I/O device will be busy while the other will be ideal.
Clearly, this is not what we desire. The next algorithm we see will reduce the waiting time by large amount. The C code to implement this algorithm is as follows:
#include <stdio.h>
int main()
{
int n, *p,*w;
int sum=0;
system("clear");
printf("Enter the number of processes:");
scanf("%d", &n);
p=(int*)malloc(n*sizeof(int));
w=(int*)malloc(n*sizeof(int));
for(int i=0; i<n; i++)
{
printf("Burst time for process %d:", i+1);
scanf("%d", &p[i]);
w[i]=sum;
sum+=p[i];
}
system("clear");
sum=0;
printf("\t\tProcess\t\tWaiting Time\n");
for(int i=0; i<n; i++){
printf("\t\t%d\t\t%d\n", i+1, w[i]);
sum+=w[i];
}
printf("Average waiting time:%d sec\n", sum/n);
return 0;
}
/*
Output:
Enter the number of processes:4
Burst time for process 1:12
Burst time for process 2:5
Burst time for process 3:8
Burst time for process 4:1
Process Waiting Time
1 0
2 12
3 17
4 25
Average waiting time:13 sec
*/
Shortest Job First Scheduling:
In this algorithm, the process with the minimum CPU burst is chosen to execute first. If this is the scenario, we can expect that the waiting time on average is greatly reduced. Note that this is also a Non-preemptive algorithm.
The C code for this algorithm is as follows:
#include <stdio.h>
int main()
{
int n, *p,*w,*re;
int sum=0;
system("clear");
printf("Enter the number of processes:");
scanf("%d", &n);
p=(int*)malloc(n*sizeof(int));
w=(int*)malloc(n*sizeof(int));
re=(int*)malloc(n*sizeof(int));
for(int i=0; i<n; i++)
{
printf("Burst time for process %d:", i+1);
scanf("%d", &p[i]);
re[i]=i;
}
system("clear");
for(int i=0; i<n; i++)
{
for(int j=0; j<n-1; j++)
{
if(p[j] > p[j+1])
{
int tmp=p[j];
p[j]=p[j+1];
p[j+1]=tmp;
tmp=re[j];
re[j]=re[j+1];
re[j+1]=tmp;
}
}
}
sum=0;
for(int i=0; i<n; i++)
{
w[i]=sum;
sum+=p[i];
}
printf("\t\tProcess\t\tWaiting Time\n");
sum=0;
int cnt=0;
while(cnt!=n)
{
for(int i=0; i<n; i++)
{
if(cnt==re[i])
{
printf("\t\t%d\t\t%d\n", cnt+1, w[i]);
sum+=w[i];
cnt++;
}
}
}
printf("Average waiting time:%d sec\n", sum/n);
return 0;
}
/*Output:
Enter the number of processes:4
Burst time for process 1:12
Burst time for process 2:5
Burst time for process 3:8
Burst time for process 4:1
Process Waiting Time
1 14
2 1
3 6
4 0
Average waiting time:5 sec
*/
You can see the significant decrease in the average waiting time for the above algorithm. There is a preemptive version of this and it is called shortest-remaining-time-first scheduling.
Shortest-remaining-time-first scheduling:
The small difference from the previous one is that CPU preempts the current process if it finds another process with smaller burst time than this one. This reduces the waiting time to some extent. The C code for this is as follows:
#include <stdio.h>
struct proc
{
int b_time; //burst time
int a_time; //arrival time
};
struct proc *p;
int n;
int give_min_idx(int upto)
{
int min=1000, idx=-1;
for(int i=0; i<n; i++)
{
if(p[i].b_time!=-1 && p[i].a_time<=upto && min>p[i].b_time)
{
min=p[i].b_time;
idx=i;
}
}
return idx;
}
int main()
{
int *w;
int time=0;
int sum=0;
system("clear");
printf("Enter the number of processes:");
scanf("%d", &n);
p=(struct proc*)malloc(n*sizeof(struct proc));
w=(int*)calloc(n,sizeof(int));
for(int i=0; i<n; i++)
{
printf("Burst & arrival time for process %d:", i+1);
scanf("%d%d", &p[i].b_time, &p[i].a_time);
}
system("clear");
int idx;
while((idx=give_min_idx(time))!=-1)
{
p[idx].b_time--;
if(p[idx].b_time==0)
p[idx].b_time--;
time++;
for(int i=0; i<n; i++)
{
if(p[i].b_time!=-1 && i!=idx && p[i].a_time<time)
w[i]++;
}
}
sum=0;
printf("\t\tProcess\t\tWaiting Time\n");
for(int i=0; i<n; i++){
printf("\t\t%d\t\t%d\n", i+1, w[i]);
sum+=w[i];
}
printf("Average waiting time:%d sec\n", sum/n);
return 0;
}
/*
output:
Enter the number of processes:4
Burst & arrival time for process 1:8 0
Burst & arrival time for process 2:4 1
Burst & arrival time for process 3:9 2
Burst & arrival time for process 4:5 3
Process Waiting Time
1 9
2 0
3 15
4 2
Average waiting time:6 sec
*/
Priority scheduling:
In this algorithm, each process is given some priority and that process is completely executed and then next one is chosen and so on. The C code is as follows:
#include <stdio.h>
struct proc
{
int b_time;
int prio;
};
int give_min(struct proc f[], int n)
{
int min=1000,idx=-1;
for(int i=0; i<n; i++)
{
if(f[i].prio!=-1 && f[i].prio < min)
{
min=f[i].prio;
idx=i;
}
}
return idx;
}
int main()
{
struct proc *g;
int n, *p,*w;
int sum=0;
system("clear");
printf("Enter the number of processes:");
scanf("%d", &n);
g=(struct proc*)malloc(n*sizeof(struct proc));
w=(int*)malloc(n*sizeof(int));
for(int i=0; i<n; i++)
{
printf("Burst time & priority for process %d:", i+1);
scanf("%d%d", &g[i].b_time, &g[i].prio);
}
system("clear");
sum=0;
int idx;
while((idx=give_min(g,n))!=-1)
{
w[idx]=sum;
sum+=g[idx].b_time;
g[idx].prio=-1;
}
sum=0;
printf("\t\tProcess\t\tWaiting Time\n");
for(int i=0; i<n; i++){
printf("\t\t%d\t\t%d\n", i+1, w[i]);
sum+=w[i];
}
printf("Average waiting time:%d sec\n", sum/n);
return 0;
}
/*output:
Enter the number of processes:5
Burst time & priority for process 1:10 3
Burst time & priority for process 2:1 1
Burst time & priority for process 3:2 4
Burst time & priority for process 4:1 5
Burst time & priority for process 5:5 2
Process Waiting Time
1 6
2 0
3 16
4 18
5 1
Average waiting time:8 sec
*/
Round-Robin scheduling:
In this type of scheduling, each process is given the CPU for some small interval known as quantum and this is repeated in round robin fashion until all the processes are completely executed. The C code is as follows:
#include <stdio.h>
int main()
{
int n, *p,*w,qu;
int sum=0;
system("clear");
printf("Enter the number of processes:");
scanf("%d", &n);
p=(int*)malloc(n*sizeof(int));
w=(int*)calloc(n,sizeof(int));
for(int i=0; i<n; i++)
{
printf("Burst time for process %d:", i+1);
scanf("%d", &p[i]);
}
printf("Enter the time Quantum:");
scanf("%d", &qu);
system("clear");
sum=0;
int ptr=0,cnt=0,tmp;
sum=0;
while(cnt!=n)
{
if(p[ptr]==0)
{
cnt++;
ptr=(ptr+1)%n;
continue;
}
if(p[ptr]>=qu){
tmp=qu;
p[ptr]-=qu;
}
else
{
tmp=p[ptr];
p[ptr]=0;
}
for(int i=0; i<n; i++)
{
if(i!=ptr && p[i]!=0)
w[i]+=tmp;
}
ptr=(ptr+1)%n;
}
printf("\t\tProcess\t\tWaiting Time\n");
for(int i=0; i<n; i++){
printf("\t\t%d\t\t%d\n", i+1, w[i]);
sum+=w[i];
}
printf("Average waiting time:%d sec\n", sum/n);
return 0;
}
/*Output:
Enter the number of processes:3
Burst time for process 1:24
Burst time for process 2:3
Burst time for process 3:3
Enter the time Quantum:4
Process Waiting Time
1 6
2 4
3 7
Average waiting time:5 sec
*/
There are two more algorithms Multilevel Queue Scheduling and its variation Feedback Queue Scheduling. These can be implemented by the combination of the above described algorithms and I leave it as an exercise to the reader.
No comments:
Post a Comment