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没有更新。尝试将更新添加到您的原始程序中，看看它是否有效。接下来是将 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

第二次调用 arrangePhase2(); 没有做任何事情。

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

Shortest Job First Scheduling Algorithm in C issues

c

sorting

algorithm

operating-system

scheduling