Shortest remaining time CPU scheduling algorithm

Question

swissknife007 3 Junior Poster in Training

14 Years Ago

#include<stdlib.h>
#include<conio.h>
#include<stdio.h>
#include<iostream.h>
struct pro
{
       int no;
       int btime;
       int atime;
       int stime;
       int etime;
       int wtime;
       int ttime;
       int rtime;
       
}proc[100],junk;

void sort(int n)
 {
 pro temp;
 for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 {
         if(proc[j].atime>proc[j+1].atime)
         {
       temp=proc[j];
         proc[j]=proc[j+1];
          proc[j+1]=temp;
         }
 } 

}
 pro min(int n,int & t)
 { sort(n); 
   pro temp; pro  mint;
    for(int i=0;i<n;i++)
    for(int j=0;j<n-i-1;j++)
       {      
         if(proc[j].rtime>proc[j+1].rtime)
         {
          temp=proc[j];
          proc[j]=proc[j+1];
          proc[j+1]=temp;
         }
     
      }
 int i;int flag=0;
 for( i=0;i<n;i++)
 {
                 if(proc[i].rtime>0&&proc[i].atime<=t&&flag==0)
                {  
                   cout<<"return proc id"<<proc[i].no<<endl;
                   return proc[i];
                   flag++;
                }
                 
 }
  for(int k=0;k<n;k++)
 {
          cout<<endl<<proc[k].rtime<<" remaining time of process "<<proc[k].no<<endl;
 }
 if(flag)
 {
     return mint;
}
 if(proc[n-1].atime>t)
 {
                      
          cout<<"no such process exists"<<endl;
          junk.no=-100;
          return junk;
 }
 
}
int main()
{
junk.no=-100;

 int to_time=0,n;
 float avgwtime=0,avgtatime=0;
 int total=0;
 printf("Enter no of processes you want");
 cin>>n;
 if(n<=0)
 {
         printf("\nInvalid no of processes\n");
         return 1;
 }   
 
 
 for(int i=0;i<n;i++)
 {
          printf("\nEnter arrival time of process t   %d\t",i+1);cin>>proc[i].atime; 

          printf("\nEnter burst time of process t   %d\t",i+1);cin>>proc[i].btime; 
          proc[i].rtime=proc[i].btime;
          proc[i].no=i+1; proc[i].ttime=0;
          total+=proc[i].btime;
 }



 int t=0 ;
 pro current;
 int i=0;
while(t<=total)
 {
   if((min(n,t)).no==junk.no)
   
        {
           t++;
        }
   else{
        
       
         current=min(n,t);
         cout<<"cuurent proc id"<<current.no<<endl;
        }

   
   
   while(current.rtime>0&& (min(n,t)).no==(current).no)
   
   {
     current.rtime--;
     for(int l=0;l<n;l++)
     { if(proc[l].no==current.no)
       {
         proc[l].rtime=current.rtime;                       
       }
     }
     cout<<"running time of current process "<<current.no <<" is"<<current.rtime<<endl;
     t++; 
    
    }
    if((current).rtime==0)
    {
       cout<<endl<<"process over now"<<endl;
       
    }
    else
    {
        cout <<endl<<"process needs to be preemted"<<endl;
    }
 

   cout<<"current time is :"<<t<<endl;
   if((min(n,t)).no==junk.no)
   
        {
        
        }
   else{
        
       
        current=min(n,t);
         cout<<"cuurent proc id"<<current.no<<endl;
        }

 }
 /*
 for(int i=1;i<n;i++)
 {    
     
     proc[i].stime=proc[i-1].etime;
      proc[i].etime=proc[i].stime+proc[i].btime;
      proc[i].wtime=proc[i].stime;
     proc[i].ttime=proc[i].wtime+proc[i].btime;
     
 }
 for(int i=0;i<n;i++)

 {printf("\nThe Process  %d \n\t\tStart Time: %d \n\t\t\n\t\tWaiting Time: %d \n\t\tTurnaround Time: %d \n\t\tEnd Time :%d \n",proc[i].no,proc[i].stime,proc[i].wtime,proc[i].ttime,proc[i].atime,proc[i].etime);
avgwtime+=proc[i].wtime;avgtatime+=proc[i].ttime;
}
avgwtime/=n;
avgtatime/=n;
printf("\nThe average waiting time is %f    \n",avgwtime);
printf("The average turn around time is %f",avgtatime);
*/
 getch();
 return 0;   
}

I am trying to implement SRTF CPU scheduling algorithm .I am inputting the process arrival time and the process burst time from the user.
Currently I am trying to just display the correct remaining time for the processes.
Kindly ignore the part of code that is commented.
The problem I am facing is that suppose I run 3 processes,then it shows the first 2 processes running correctly but it doesn't show the thirsd one running correctly.In fact the third one doesn't start.Here is the relevant output.

Enter no of processes you want3

Enter arrival time of process t   1     0

Enter burst time of process t   1       5

Enter arrival time of process t   2     5

Enter burst time of process t   2       5

Enter arrival time of process t   3     10

Enter burst time of process t   3       5
return proc id1
return proc id1
cuurent proc id1
return proc id1
running time of current process 1 is4
return proc id1
running time of current process 1 is3
return proc id1
running time of current process 1 is2
return proc id1
running time of current process 1 is1
return proc id1
running time of current process 1 is0

process over now
current time is :5
return proc id2
return proc id2
cuurent proc id2
return proc id2
return proc id2
cuurent proc id2
return proc id2
running time of current process 2 is4
return proc id2
running time of current process 2 is3
return proc id2
running time of current process 2 is2
return proc id2
running time of current process 2 is1
return proc id2
running time of current process 2 is0

process over now
current time is :10

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
running time of current process 2 is0

process over now
current time is :11

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
running time of current process 2 is0

process over now
current time is :12

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
running time of current process 2 is0

process over now
current time is :13

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
running time of current process 2 is0

process over now
current time is :14

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
running time of current process 2 is0

process over now
current time is :15

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
running time of current process 2 is0

process over now
current time is :16

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2

0 remaining time of process 0

0 remaining time of process 1

0 remaining time of process 2
cuurent proc id2

Any possible help/suggestion would be great ......
Please help me someone.

algorithm-pseudocode c++

1 Contributor
1 Reply
3K Views
6 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by swissknife007

Dani AI

Generated 11 Months Ago

the third job never runs because the scheduler keeps corrupting state and reselecting an already-finished process. Two concrete issues jump out:

Off-by-one in your arrival-time bubble sort writes past the end of the array (j < n then reading proc[j+1]). That can trash memory, including rtime of the third process.
min(...) both re-sorts the whole table and returns a copy of pro. You then try to push the copy’s rtime back into the array while the array order keeps changing. That makes the chosen record drift and you end up cycling on the wrong PID. There is also a path in min(...) that reaches the end without a return, which is undefined behavior.

Quick fix: stop sorting every tick and return an index into proc[] instead of a struct. Also, when no job is ready, jump time to the next arrival to avoid busy loops.

int pick_ready_with_min_rtime(int n, int t) {
    int best = -1;
    for (int i = 0; i < n; ++i) {
        if (proc[i].rtime > 0 && proc[i].atime <= t) {
            if (best == -1 || proc[i].rtime < proc[best].rtime) best = i;
        }
    }
    return best; // -1 means CPU is idle
}

void run_srtf(int n) {
    int t = 0, finished = 0;
    while (finished < n) {
        int i = pick_ready_with_min_rtime(n, t);
        if (i == -1) {
            int next = INT_MAX;
            for (int k = 0; k < n; ++k)
                if (proc[k].rtime > 0 && proc[k].atime > t) next = std::min(next, proc[k].atime);
            t = (next == INT_MAX) ? t + 1 : next; // jump to next arrival
            continue;
        }
        proc[i].rtime--;  // run 1 time unit
        t++;
        if (proc[i].rtime == 0) finished++;
        // optional: print remaining times here
    }
}

If you keep your bubble sort for something else, fix the bounds: outer i < n-1, inner j < n-i-1. Finally, cache the result of pick_ready_with_min_rtime(...) for the current tick rather than calling it repeatedly inside the same step.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

swissknife007 3 Junior Poster in Training · Answer 1 · 2012-01-27T21:59:47+00:00

swissknife007 3 Junior Poster in Training

14 Years Ago

Why no one is answering?