C问题中最短作业优先调度算法

Question

我已经创建了一个C程序来模拟非抢占式最短作业优先算法，但它在某些输入上有缺陷。最短作业优先算法程序接受所需数量的过程的到达和突发时间的输入，并将过程安排在两个阶段中。第一阶段涉及根据到达时间来安排节目，第二阶段根据突发时间来安排节目，假设它们的到达时间低于前一过程完成的时间。这一切最终都会被编译并显示出来。

#include <stdio.h>

// n - total processes
// p - process no. array
// bt - burst time array
// at - arrival time array
// wt - the time taken for the process to start from it's arrival time array
// tat - time spent by process in cpu array
int i, n, j, m, min, sum = 0, x = 1, btTally = 0, p[20], bt[20], at[20], wt[20], tat[20], ta = 0;
float tatTally = 0, wtTally = 0;

//function grabs arrival and burst times of each process and stores it in its respective array
void getInput(){
    printf("\nEnter the total number of processes: ");
    scanf("%d", & n);

    // For Loop for user to input info about the processes
    for (i = 0; i < n; i++) {
        p[i] = i + 1;
        printf("\nEnter the arrival time of process %d: ", p[i]);
        scanf(" %d", & at[i]);
        printf("\nEnter the burst time of process %d: ", p[i]);
        scanf(" %d", & bt[i]);
    }
}

//Function arranges processes according to their arrival times
void arrangePhase1(){
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (at[j] > at[i]) {
                m = p[j];
                p[j] = p[i];
                p[i] = m;

                m = at[j];
                at[j] = at[i];
                at[i] = m;

                m = bt[j];
                bt[j] = bt[i];
                bt[i] = m;
            }
        }
    }
}

//Function arranges the processes according to Burst time
void arrangePhase2(){
    for (i = 0; i < n; i++) {
        btTally = btTally + bt[i];
        min = bt[x];
        for (j = x; j < n; j++) {
            if (bt[j] < min && btTally >= at[j]) {
                m = p[x];
                p[x] = p[j];
                p[j] = m;

                m = at[x];
                at[x] = at[j];
                at[j] = m;

                m = bt[x];
                bt[x] = bt[j];
                bt[j] = m;
            }
        }
        x++;
    }
}

//Function calculates the tallies of turnaround time and waiting time
void calcTallies(){
    for (i = 0; i < n; i++) {
        ta = ta + bt[i];
        tat[i] = ta - at[i];
        tatTally = tatTally + tat[i];
    }

    wt[0] = 0;
    for (i = 1; i < n; i++) {
        sum = sum + bt[i - 1];
        wt[i] = sum - at[i];
        wtTally = wtTally + wt[i];
    }

}

//Function displays all of the information about the algorithm running
void showFinal(){
    printf("\nProcess\t Arrival Time\t Burst Time\t Waiting Time\t Turnaround Time");
    for (i = 0; i < n; i++) {
        printf("\n p%d\t %d\t\t %d\t\t %d\t\t %d", p[i], at[i], bt[i], wt[i], tat[i]);
    }

    printf("\nAverage Waiting Time: %.2f", (wtTally / n));
    printf("\nAverage Turn Around Time: %.2f", (tatTally / n));
}

int main() {
    getInput();
    arrangePhase1();
    arrangePhase2();
    arrangePhase2();
    calcTallies();
    showFinal();
    return 0;
}

这些是预期的结果:

这些是我通过我的程序获得的结果：

任何帮助都将不胜感激。谢谢！

Answer 1

我。。。稍微重新排列一下您的程序...

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int p, at, bt, wt, tat;
} Job;
#define maxN (20)
Job jobs[maxN ];
int n, btTally = 0, sum = 0, ta = 0;
float tatTally = 0, wtTally = 0;

#define TestSize (5)
Job Test[TestSize] = {
  { 1, 2, 1, 0, 0 },
  { 2, 1, 5, 0, 0 },
  { 3, 4, 1, 0, 0 },
  { 4, 0, 6, 0, 0 },
  { 5, 2, 3, 0, 0 }
};

void getInput(){
    int i;
    printf("\nEnter the total number of processes: ");
    scanf("%d", & n);

    if (n == 0) {
      for (i = 0; i < TestSize; ++i)
        jobs[i] = Test[i];
      n = TestSize;
      return;
    }

    // For Loop for user to input info about the processes
    for (i = 0; i < n; i++) {
        jobs[i].p = i + 1;
        printf("\nEnter the arrival time of process %d: ", jobs[i].p);
        scanf(" %d", & jobs[i].at);
        printf("\nEnter the burst time of process %d: ", jobs[i].p);
        scanf(" %d", & jobs[i].bt);
    }
}

int compareAT (const void * a, const void * b) {
  Job *jobA = (Job *)a;
  Job *jobB = (Job *)b;

  return ( jobA->at - jobB->at );
}

void arrangePhase1(){
  qsort (jobs, n, sizeof(Job), compareAT);
}

void Swap(int i, int j) {
  Job m = jobs[i];
  jobs[i] = jobs[j];
  jobs[j] = m;
}



void calcTallies(){
    int i;
    for (i = 0; i < n; i++) {
        ta = ta + jobs[i].bt;
        jobs[i].tat = ta - jobs[i].at;
        tatTally = tatTally + jobs[i].tat;
    }

    jobs[0].wt = 0;
    for (i = 1; i < n; i++) {
        sum = sum + jobs[i - 1].bt;
        jobs[i].wt = sum - jobs[i].at;
        wtTally = wtTally + jobs[i].wt;
    }
}

void showFinal(){
    int i;
    printf("\nProcess\t Arrival Time\t Burst Time\t Waiting Time\t Turnaround Time");
    for (i = 0; i < n; i++) {
        printf("\n p%d\t %d\t\t %d\t\t %d\t\t %d", jobs[i].p, jobs[i].at, jobs[i].bt, jobs[i].wt, jobs[i].tat);
    }

    printf("\nAverage Waiting Time: %.2f", (wtTally / n));
    printf("\nAverage Turn Around Time: %.2f", (tatTally / n));
}

void arrangePhase2() {
    int i, j, min, x = 1;

    for (i = 0; i < n; i++) {
        btTally = btTally + jobs[i].bt;
        min = jobs[x].bt;
        for (j = x; j < n; j++) {
            if (jobs[j].bt < min && btTally >= jobs[j].at) {
              Swap(x, j);
              min = jobs[x].bt;
              showFinal();
            }
        }
        x++;
    }
}

int main() {
    getInput();
    arrangePhase1();
    showFinal();
    arrangePhase2();
//    arrangePhase2();
    calcTallies();
    showFinal();
    return 0;
}

并在里面留下了一些测试和指纹。

主要问题是min未更新。尝试将更新添加到您的原始程序中，看看它是否有效。接下来是移动＜code＞int i，j到函数，它现在工作了吗？（如果只添加showFinal（），则没有它就无法工作 测试您的代码）。

现在我做的代码并不是唯一的真实事实，它只是一个几十年来没有编程过C的人的例子。

简短的代码回顾。在C中使用全局变量是不好的，如果您使用全局变量进行循环控制，您很容易遇到循环问题，这里i， j被大量重用。

您可以更多地使用结构，至少对于 3 个主要值，使一些排序更容易一些。在任何一种情况下，具有 Swap 函数都可以使代码更易于检查和理解。

void SwapInt(int *i, int *j) {
  int m = *i;
  *i = *j;
  *j = m;
}

SwapInt(&at[i], &at[j]); // example of calling swapping

第二次调用＜code＞arrangePhase2（）什么都不做。