在c中首先调度最短的作业

Question

所以我正在研究调度，包括FCFS和最短作业优先。我首先真的在纠结我最短的工作，我看不到我的逻辑错误。我把它打印出来，有些数字是正确的，但不是全部。我使用的测试文件包含以下文本:

1   0   6
2   3   2
3   5   1
4   9   7
5   10  5
6   12  3
7   14  4
8   16  5
9   17  7
10  19  2

我使用

任何帮助，指针或代码，将不胜感激！

编辑我认为我的问题是基于sfj函数的逻辑。对于输入，第一列是进程id，第二列是到达时间，第三列是突发时间或进程需要cpu多长时间。

我得到的输出是:

Shortest Job First
PID     WAIT    TURNAROUND
1       0       6
2       15      17
3       3       4
4       0       7
5       6       11
6       9       12
7       10      14
8       12      17
9       16      23
10      21      23
Average Wait: 9 Average Turnaround 13

当我真正期望时：

Shortest Job First

Pid     Wait    Turnaround
1       0       6
2       4       6
3       1       2
4       0       7
5       15      20
6       4       7
7       7       11
8       14      19
9       18      25
10      0       2
Average wait: 6.3 Average turnaround: 10.5

//  File.c
//  Project6
//
//  Created by Chris on 6/19/14.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <termios.h>
#include <signal.h>
#include <fcntl.h>
#include <sys/types.h>
#define LINELEN 512
#define MAX_PROCESS 100

typedef struct process
{
    int ID;
    int arrival_time;
    int time_to_completion;
    int wait_time;
    int turn_around;
    int active;

}process;
void fcfs(struct process[MAX_PROCESS], int);
void sjf (struct process[MAX_PROCESS], int);
void srtn(struct process[MAX_PROCESS], int);
void rr (struct process[MAX_PROCESS], int);
void rrc(struct process[MAX_PROCESS], int);
void print_info(struct process[MAX_PROCESS], int);
void sort_by_time(struct process array[MAX_PROCESS], int num_valid_pid);

int main(int ac,char *av[])
{
    int counter=0;
    int p1=0, p2=0, p3=0;
    process array[MAX_PROCESS];
    while ( scanf("%d %d %d", &p1, &p2, &p3) != EOF ){//Get all the info available and put it in array of structs
        array[counter].ID = p1;
        array[counter].arrival_time = p2;
        array[counter].time_to_completion = p3;
        counter++;
    }
    fcfs(array, counter);
    sjf (array, counter);
    /*srtn(array, counter);
    rr (array, counter);
    rrc(array, counter);*/
    return 0;
}
void fcfs(struct process array[MAX_PROCESS], int num_pid){
    //for loop num_pid
    int i;
    int current_time = 0;
    for(i=0; i<num_pid; i++){
    //if arrival is < current time, wait time = current time - arrival
        if(array[i].arrival_time < current_time)
            array[i].wait_time = current_time - array[i].arrival_time;
    //if arrival is >= current time, wait time = 0;
        else if(array[i].arrival_time >= current_time)
            array[i].wait_time = 0;
    //current time = current time + wait time + time to completion
        current_time= current_time + array[i].time_to_completion;
    //turnaround time = wait time + time to completion
        array[i].turn_around = array[i].wait_time + array[i].time_to_completion;
    }
    printf("First Come First Serve\n");
    print_info(array, num_pid);
}
void sjf (struct process array[MAX_PROCESS], int num_pid){
    printf("Shortest Job First\n");//for the output so we know what algorithm
    //create an array of pids that are valid to search.
    int num_valid_processes = 0, current_time=0, i,j, next_process, counter = 0;//declarations
    process to_sort[MAX_PROCESS];

    //we want to do this next loop for as many processes as we have, or num_pid
    for(j=0; j<num_pid; j++){
        //adds all the available processes to the to sort array to be sorted
        //available means that it has arrived, which means it is <= current_time
        //after it gets all the processes, it breaks out of the for loop
        for(i=counter; i<num_pid; i++){
            if(array[i].arrival_time<=current_time){
                to_sort[i]=array[i];
                num_valid_processes++;
                counter++;
            }
            else
                break;
        }
        //sort the to_sort array by the time_to_completion
        sort_by_time(to_sort,num_valid_processes);

        //set the wait time and turnaround time for the next process
        next_process = to_sort[0].ID;
        array[next_process].wait_time = current_time-array[next_process].arrival_time;
        array[next_process].turn_around = array[next_process].wait_time + array[next_process].time_to_completion;
        //change the current_time and continue
        //current time = current time + wait time + time to completion
        current_time= current_time + array[next_process].time_to_completion;

        //delete the process we just worked on so we don't get duplicates.
        num_valid_processes--;
        for(i=0;i<num_valid_processes;i++){
            to_sort[i]=to_sort[i+1];
        }
    }
    //loop back up to get available processes
    //now all the info in out first array is filled out, print it out.
    print_info(array, num_pid);
}

void print_info(struct process array[MAX_PROCESS], int num_pid){
    int i;
    int tot_wait=0, tot_turn = 0;
    printf("\x1b[04mPID\tWAIT\tTURNAROUND\n\x1b[24m");
    for(i=0; i<num_pid; i++){
        printf("%d\t%d\t%d\n", array[i].ID, array[i].wait_time, array[i].turn_around);
        tot_wait=tot_wait+array[i].wait_time;
        tot_turn = tot_turn +array[i].turn_around;
    }
    printf("Average Wait: %d Average Turnaround %d\n", tot_wait/num_pid, tot_turn/num_pid);
}

void sort_by_time(struct process array[MAX_PROCESS], int num_valid_pid)
{
    int i,j;
    for (i = 0; i < num_valid_pid; i++)
    {
        int min = i;
        for (j = i+1; j < num_valid_pid; j++)
            if (array[j].time_to_completion < array[min].time_to_completion)
                min = j;
        process temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}

Answer 1

问题最终出在sjf函数中，赋值的for循环不正确，应该是

for(i=counter; i<num_pid; i++){
        if(array[i].arrival_time<=current_time){
            to_sort[num_valid_process]=array[i];
            num_valid_processes++;
            counter++;
        }
...