Shortest Remaining Time First (SRTF) Program in C++ || dot clu

Shortest Remaining Time First (SRTF) Program in C++ || dot clu

Shortest Remaining Time First (SRTF)

Shortest Remaining Time First (SRTF) Algorithm is preemptive version of Shortest Job First Algorithm. In this current process is executed until it is completed or a new process is added having lower burst time compare to the the remaining time for current process.

SRTF algorithm may lead to starvation, if processes with lower burst time continues to add to cpu scheduler then the current process will never get a chance to get executed.

For example consider the following table

Process	Arrival Time	Burst Time
P1	0	10
P2	1	6
P3	2	9
P4	3	4

At time t=0, Process P1 will start get executing as it is only the process present at that time. Then at t=1, Process P2 added to the CPU scheduler, at this time remaining time(Burst time) for Process P1 gets 9, as Burst time of P2 is less than the remaining time of other processes (for now there is only process P1) therefore process P1 is preempted and P2 is alloted the CPU.

This process is repeated until all process get executed. This is known as Shortest Remaining Time First Algorithm. Now lets see how to implement it in a computer program.

SOURCE CODE:

1. # include<stdio.h>
2. # include<conio.h>
3. #include<iostream>
4. 
   
5. # define max1 10      //MAX PROCESSES
6. # define r 6          //MAX RESOURCES
7. 
   
8. using namespace std;
9. 
   
10. void sort(int st,int a[],int b[],int pr[],int np)
11. {       int i,j,t,p,z;
12. for(i=0;i<np-1;i++)
13. {
14. for(j=st;j<np-i-1;j++)
15. {
16. if(a[j]>a[j+1])
17. {
18.     t=a[j];      z=b[j];        p=pr[j];
19.     a[j]=a[j+1]; b[j]=b[j+1]; pr[j]=pr[j+1];
20.     a[j+1]=t; b[j+1]=z; pr[j+1]=p;
21. }
22. }
23. }
24. }
25. /* SHEDULING ALGO-SHORTEST REMAINING TIME FIRST-PREEMTIVE */
26. 
    
27. void srtf()
28. {
29. int p1[max1],t1[max1],i,ch,np;
30. int arr[max1];
31. int tat[max1];
32. int wt[max1];
33. int resp[max1];
34. float rdelay[max1];
35. float atat;
36. float awt;
37. float aresp;
38. float ardelay;
39. int pgant[max1];
40. int tgant[max1];
41. int tex=0;
42. int j,k,count,c,a;
43. int trem[max1];
44. cout<<"\nEnter no. of processes  : ";
45. cin>>np;
46. for(i=0;i<np;i++)
47. {
48. cout<<"\nEnter the Process  :- ",i;
49. p1[i]=i;
50. cout<<"\nExecution time : ";
51. cin>>t1[i];
52. cout<<"\nArrival time   : ";
53. cin>>arr[i];
54. }
55. cout<<"\nPROCESSES\t\tEXECUTION TIME\t\tARRIVAL TIME";
56. for(i=0;i<np;i++)
57. {
58. cout<<"\n p "<<p1[i]<<"  \t\t\t"<<t1[i]<<"  \t\t\t"<<arr[i];
59. }
60. for(i=0;i<np;i++)
61. { tex=tex+t1[i];
62. trem[i]=t1[i];
63. }
64. sort(0,arr,p1,t1,np);
65. tgant[0]=0;
66. j=0,k=0,count=0,c=0;
67. while(count!=tex)
68. {
69. if(j!=np)
70. {       j=k;
71. for(i=k;i<np;i++)
72. {
73. if(arr[i]<=count)
74. j++;
75. else
76. break;
77. }
78. if((j-k)>1)
79. sort(k,trem,p1,arr,j);
80. }
81. while(trem[k]==0)
82. k++;
83. c++;
84. pgant[c-1]=p1[k];
85. if(j==np)
86. a=trem[k];
87. else
88. { if(trem[k] < (arr[j]-tgant[c-1]) )
89. a=trem[k];
90. else
91. a=arr[j]-tgant[c-1];
92. }
93. tgant[c]=tgant[c-1]+a;
94. count=tgant[c];
95. trem[k]=trem[k]-(tgant[c]-tgant[c-1]);
96. if(c>1)
97. {
98. if(pgant[c-1]==pgant[c-2])
99. { tgant[c-1]=tgant[c];
100. c--;
101. }
102. }
103. }
104. sort(0,arr,p1,trem,np);
105. for(i=0;i<np;i++)
106. {
107. wt[i]=0;
108. tat[i]=0;
109. resp[i]=-1;
110. }
111. for(i=0;i<c;i++)
112. {
113. for(j=0;j<np;j++)
114. {
115. if(pgant[i]==p1[j])
116. {
117. wt[j]=wt[j]+tgant[i]-tat[j];
118. if(resp[j]==-1)
119. resp[j]=tgant[i];
120. tat[j]=tgant[i+1] ;
121. break;
122. }
123. }
124. }
125. for(i=0;i<np;i++)
126. {
127. wt[i]=wt[i]-arr[i];
128. tat[i]=tat[i]-arr[i];
129. resp[i]=resp[i]-arr[i];
130. rdelay[i]=(float)tat[i]/t1[i];
131. }
132. atat=0; awt=0; aresp=0; ardelay=0;
133. for(i=0;i<np;i++)
134. {
135. atat=atat+tat[i];
136. awt=awt+wt[i];
137. aresp=aresp+resp[i];
138. ardelay=ardelay+rdelay[i];
139. }
140. atat=atat/np;
141. awt=awt/np;
142. aresp=aresp/np;
143. ardelay=ardelay/np;
144. 
     
145. cout<<"\nGANTT CHART:- ";
146. for(i=0;i<c;i++)
147. cout<<"   P"<<pgant[i]<<"  ";
148. 
     
149. for(i=0;i<=c;i++)
150. cout<<"    "<<tgant[i];
151. 
     
152. cout<<"\n\nAverage waiting time      : "<<awt;
153. cout<<"\nAverage turn arround time : "<<atat;
154. cout<<"\nAverage response time     : "<<aresp;
155. cout<<"\nAverage relative delay    : "<<ardelay;
156. getch();
157. }
158. 
     
159. int main()
160. {
161.       srtf();
162.      getch();
163. }