SJF 非抢占式调度算法

Question

我对这些调度算法很熟悉。我已经习惯了SJF的非抢占性，我从纸笔甘特图的角度理解它，但从编程的角度却不太理解。我的代码在下面，虽然它运行成功，但我的数学不正确。我该如何修复它？

测试案例过程突发到达P1 20 0 P2 3 3 P3 2 5

预期输出 平均等待时间为 11.3 平均周转时间为 19.6 平均响应时间为 10.6

实际输出平均等待时间为 8.3 平均周转时间为 6.6 平均响应时间为 14

    #include <iostream>
    using namespace std;

    void SJF_NP(int n, int burst[], int arrival[], int throughput)
    {
      cout << "Output for SJF_Non_Preemptive scheduling algorithm" << endl;

      int i, j, temp, temp2;
      double tot, avgwait, avgturnaround, avgresponse, tp;

      //array instantiations                                                                                          
      int start[n], end[n], wait[n];

      //calculations                                                                                                  
      for(i=1;i<=n;i++)
        {
          for(j=i+1;j<=n;j++)
            {
              if (i>=2 && burst[i-1]>burst[j-1])
                {
                  temp = burst[i-1];
                  temp2 = arrival[i-1];
                  burst[i-1]=burst[j-1];
                  arrival[i-1]=arrival[j-1];
                  burst[j-1]=temp;
                  arrival[j-1]=temp2;
                }
            }
          if(i==1)
            {
              start[0]=0;
              end[0]=burst[0];
              wait[0]=0;
            }
          else
            {
              start[i-1]=end[i-2];
              end[i-1]=start[i-1]+burst[i-1];
              wait[i-1]=start[i-1]+arrival[i-1];
            }
          //throughput                                                                                                
          if (start[i+1] <= throughput)
            tp = i+1;
        }

      //output                                                                                                        
      cout << "\n\nPROCESS \t BURST TIME\tARRIVAL TIME\tWAIT TIME\tSTART TIME\tEND TIME\n";
      for (i=0;i<n;i++){
        cout << "\nP[" << i + 1 << "]" << "\t\t" << burst[i] << "\t\t" << arrival[i] << "\t\t" << wait[i] << "\t\t" << start[i] << "\t\t" << end[i];
      }
      //avg wait time                                                                                                 
      for(i=1,tot=0;i<n;i++){
        tot+=wait[i-1];
        avgwait=tot/n;
      }
      //avg turnaround time                                                                                           
      for(i=1,tot=0;i<n;i++){
        tot+=end[i-1];
        avgturnaround=tot/n;
      }
      //avg response time                                                                                             
      for(i=1,tot=0;i<n;i++){
        tot+=start[i-1];
        avgresponse=tot/n;
      }
      cout << "\n\nAverage Wait Time: " << avgwait;
      cout << "\nAverage Response Time: " << avgturnaround;
      cout << "\nAverage Turnaround Time: " << avgresponse;
      cout << "\nThroughput for (" << throughput << "): " << tp << endl;
    }

Answer 1

#include<iostream>
using namespace std;
struct Process
{
    int pid,at,bt,wt,tt,ct; //at=arrival time;bt=burst time
                                 //wt=waiting time; tt=turnaround time
                                //ct=completion time
};

//to swap processes
void swap(struct Process *t ,struct Process *w )
{
struct Process v;
v=*t;
*t=*w;
*w=v;
}
 //sort according to arrival time
 void sort1(struct Process *t,int p)
{
int i,j;
struct Process *q,s;

for(i=0;i<p;i++,t++)
{
for(j=i+1,q=t+1;j<p;j++,q++)
{
 if((t->at)>(q->at))
 {
 s=*t;
 *t=*q;
 *q=s;
 }
 }
}
}

//sort according to burst time
void sort2(struct Process *t,int p)
{
int i,j;
struct Process *q,s;
if(t->pid==p)
{
    return;
}
for(i=1;i<p;i++,t++)
{
for(j=i+1,q=t+1;j<p;j++,q++)
{
 if((t->bt)>(q->bt))
 {
 s=*t;
 *t=*q;
 *q=s;
 }
 }
}
}

int main()
{
    int n;
    struct Process p[80];
    int at,bt;
    cout<<"Enter number of processes";
    cin>>n;
    for (int i=0;i<n;i++)
      {
        cout<<"for process"<<i+1<<"\n";
        cout<<"pid";
        cin>>p[i].pid;
        cout<<"at";
        cin>>p[i].at;
        cout<<"bt";
        cin>>p[i].bt;
      } 


    sort1(p,n);
    p[0].wt=0;
    p[0].ct=p[0].bt;
    p[0].tt=p[0].ct;



    cout<<"ProcessId\t"<<"Arrival time\t"<<"Burst time\t";
    for(int i=0;i<n;i++)
    {
        cout<<p[i].pid<<"\t\t"<<p[i].at<<"\t\t"<<p[i].bt<<"\n";
    }

    int t=1;
    do{

    int diff=p[t].at-p[t-1].ct;
    if(diff<=0)
    {
      sort2(&p[t],n);   
      for( int i=t+1;i<n;i++)
      {
        if(p[t].bt==p[i].bt&&p[i].at<p[t].at)
        {
            swap(&p[t],&p[i]);
            break;
        }

      }

      p[t].ct=p[t-1].ct+p[t].bt;
      p[t].tt=p[t].ct-p[t].at;
      p[t].wt=p[t].tt-p[t].bt;
    }

    else
    {
        p[t].ct=p[t].at+p[t].bt;
        p[t].tt=p[t].ct-p[t].at;
        p[t].wt=0;
        sort2(&p[t+1],n);
    }
    t++;

    }   
    while(t < n);
    //Output
    cout<<"ProcessId\t"<<"Arrival time\t"<<"Burst time\t"<<"Waiting Time\t"      
    <<"Turnaround Time\n";
    for(int i=0;i<n;i++)
    {
        cout<<p[i].pid<<"\t\t"<<p[i].at<<"\t\t"<<p[i].bt<<"\t\t"
        <<p[i].wt<<"\t\t"<<p[i].tt<<"\n";
    }

    return 0;
}