SJF Scheduling Program in C
SJF Scheduling Program in C
Problem Description:
Write an SJF
scheduling program in C to determine the average waiting time and average
turnaround time given n processes and their burst times.
SJF Scheduling Algorithm in C:
The
CPU scheduling algorithm Shortest Job First (SJF), allocates the CPU to the processes
according to the process with smallest execution time.
SJF uses both preemptive and non-preemptive
scheduling. The preemptive version of SJF is called SRTF (Shortest Remaining Time First). Here we
will discuss about SJF i.e., the non-preemptive scheduling.
Advantages of SJF:
- It has the
minimum waiting time among all the scheduling algorithms.
- A process
having larger burst time may get into starvation but the problem can be
solved using concept of Ageing.
- It is a
greedy algorithm and provides optimal scheduling.
Problem Solution
1.
Enter number of processes.
2. Enter the burst time of all the processes.
3. Sort all the processes according to their burst time.
4. Find waiting time, WT of all the processes.
5. For the smallest process, WT = 0.
6. For all the next processes i, find waiting time by adding burst time of all the previously
completed process.
7. Calculate Turnaround time = WT + BT for all the processes.
8. Calculate average waiting time = total waiting time /
no. of processes.
9. Calculate average turnaround time= total turnaround time
/ no. of processes.
SJF Example:
|
Process |
Arrival Time |
Burst Time |
|
P1 |
0 |
5 |
|
P2 |
0 |
4 |
|
P3 |
0 |
12 |
|
P4 |
0 |
7 |
Gantt Chart:
advertisement
Waiting Time: Time Difference between turnaround time
and burst time.
Waiting Time = Turnaround Time – Burst Time
P1 waiting time: 4
P2 waiting time: 0
P3 waiting time: 16
P4 waiting time: 9
Average Waiting Time = (4 + 0 + 16 + 9)/4 = 29/4 = 7.25
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects.
Participate Now!
Turnaround Time: Difference between completion time and
arrival time.
Turnaround Time = Completion Time – Arrival
Time
P1 turnaround time:
9-0 = 9
P2 turnaround time: 4-0 = 4
P3 turnaround time: 28-0 = 28
P4 turnaround time: 16-0 = 16
Average Turnaround Time = (9 + 4 + 28 + 16)/4 = 14.25
Program/Source Code
Here is the source
code of the C Program to Implement SJF Scheduling. The C program is
successfully compiled and run on a Linux system. The program output is also
shown below.
1.
/*
2.
*
C Program to Implement SJF Scheduling
3.
*/
4.
5.
#include<stdio.h>
6.
int main()
7.
{
8.
int bt[20],p[20],wt[20],tat[20],i,j,n,total=0,totalT=0,pos,temp;
9.
float avg_wt,avg_tat;
10. printf("Enter
number of process:");
11. scanf("%d",&n);
12.
13. printf("\nEnter Burst Time:\n");
14. for(i=0;i<n;i++)
15. {
16. printf("p%d:",i+1);
17. scanf("%d",&bt[i]);
18.
p[i]=i+1;
19. }
20.
21. //sorting of burst times
22. for(i=0;i<n;i++)
23. {
24.
pos=i;
25. for(j=i+1;j<n;j++)
26. {
27.
if(bt[j]<bt[pos])
28.
pos=j;
29. }
30.
31.
temp=bt[i];
32.
bt[i]=bt[pos];
33.
bt[pos]=temp;
34.
35.
temp=p[i];
36.
p[i]=p[pos];
37.
p[pos]=temp;
38. }
39.
40. wt[0]=0;
41.
42. //finding the waiting time of all the
processes
43. for(i=1;i<n;i++)
44. {
45.
wt[i]=0;
46. for(j=0;j<i;j++)
47.
//individual WT by
adding BT of all previous completed processes
48.
wt[i]+=bt[j];
49.
50. //total waiting time
51.
total+=wt[i];
52. }
53.
54. //average waiting time
55.
avg_wt=(float)total/n;
56.
57. printf("\nProcess\t Burst Time \tWaiting
Time\tTurnaround Time");
58. for(i=0;i<n;i++)
59. {
60. //turnaround time of individual processes
61.
tat[i]=bt[i]+wt[i];
62.
63. //total turnaround time
64.
totalT+=tat[i];
65. printf("\np%d\t\t %d\t\t
%d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
66. }
67.
68. //average turnaround time
69.
avg_tat=(float)totalT/n;
70. printf("\n\nAverage Waiting Time=%f",avg_wt);
71. printf("\nAverage Turnaround Time=%f",avg_tat);
72.}
Program Explanation
1.
Initialize two array pid[] and bt[] of size 20.
2. Ask the user for number of processes n.
3. Ask the user for process id and burst time for all n processes and store them into pid[] and bt[] respectively.
4. Sort all the processes according to their burst time.
5. Assign waiting time = 0 to the smallest process.
6. Calculate waiting time of each process by using two loops and adding all the
burst time of previously completed processes.
7. Print Process Id, Burst Time, waiting time and Turnaround time of each
process in tabular manner.
8. Calculate and print turnaround time of each process = bt[i] + wt[i].
9. Add waiting time of all the processes and store it in the variable total.
10. Add turnaround time of all the processes and store it in the variable totalT.
11. Calculate average waiting time as avg_wt = total/n.
12. Calculate average turnaround time as avg_tat = totalT/n;
13. Print average waiting time and average turnaround time.
14. Exit.
Time Complexity: O(n2)
The above program for implementing SJF Scheduling has a time complexity of O(n2), as the for loop runs for n^2 times for
calculating waiting time of each process.
Space Complexity: O(n)
In the SJF Scheduling program, space complexity is O(n) as arrays of size n
have been initialized to store the values in it.
Run Time Testcases
In this case, we enter
“3” as the number of processes, and the burst time are “p1: 5”, “p2: 4”, “p3:
12”, and “p4: 7” to find average waiting time and average turnaround time using
SJF Scheduling algorithm.
Enter number of
process:4
Enter Burst Time:
p1:5
p2:4
p3:12
p4:7
Process Burst Time Waiting Time Turnaround Time
p2 4 0 4
p1 5 4 9
p4 7 9 16
p3 12 16 28
Average Waiting
Time=7.250000
Average Turnaround
Time=14.250000
Comments
Post a Comment