Skip to main content

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
ProcessArrival TimeBurst Time
P1010
P216
P329
P434
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>

  5. # define max1 10      //MAX PROCESSES
  6. # define r 6          //MAX RESOURCES

  8. using namespace std;

  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 */

  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;

  145. cout<<"\nGANTT CHART:- ";
  146. for(i=0;i<c;i++)
  147. cout<<"   P"<<pgant[i]<<"  ";

  149. for(i=0;i<=c;i++)
  150. cout<<"    "<<tgant[i];

  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. }

  159. int main()
  160. {
  161.       srtf();
  162.      getch();
  163. }

Labels:

Comments

  1. Felipe18 November 2018 at 08:01

    Could you explain the code with comments?

    ReplyDelete
  2. Aman Kr. Thakur9 March 2019 at 02:39

    hey...Please explain code with comments.
    Its difficult to understand variables used in this code.

    ReplyDelete
  3. Unknown14 May 2019 at 11:59

    🙄

    ReplyDelete

Post a Comment

Popular posts from this blog

C++ Program For PRIORITY WITH NON - PREEMPTIVE Scheduling Algorithm || dot clu

C++ Program For PRIORITY WITH  NON - PREEMPTIVE Scheduling Algorithm It is important to distinguish  preemptive  from  non - preemptive scheduling algorithms.  Preemption  means the operating system moves a process from running to ready without the process requesting it. Without  preemption , the system implements ``run to completion (or yield or block)''. Non-Preemptive Scheduling Non-Preemptive Scheduling means once a process starts its execution or the CPU is processing a specific process it cannot be halted or in other words we cannot preempt (take control) the CPU to some other process. A computer system implementing this cannot support the execution of process in a multi task fashion. It executes all the processes in a sequential manner. It is not practical as all processes are not of same priority and are not always known to the system in advance. Source Code: #include <iostream> using namespace std; int main(...
Post a Comment
Read more

Round Robin Scheduling Program in C++ || dot clu

Round Robin Scheduling Program in C++ Process scheduling is an important component for process management. In a multi-user and a time-sharing system, response time is one of the most important objective to be accomplished. Round Robin Scheduling Algorithm 1. The queue structure in ready queue is of First In First Out (FIFO) type. 2. A fixed time is allotted to every process that arrives in the queue. This fixed time is known as time slice or time quantum. 3. The first process that arrives is selected and sent to the processor for execution. If it is not able to  complete its execution within the time quantum provided, then an interrupt is generated using an automated timer. 4. The process is then stopped and is sent back at the end of the queue. However, the state is saved and context is thereby stored in memory. This helps the process to resume from the point where it was interrupted. 5. The scheduler selects another process from the ready queue and dispa...
4 comments
Read more