c - C 中的调度算法 最短剩余时间 Next

Question

我正在研究“最短剩余时间下一个调度”，我必须每1个时间单位检查一次，看看是否有另一个作业的剩余时间更短，如果相等则保留当前进程。对于我使用的输入:

PID     ArrivalTime Burst/ExecutionTime
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

我的输出:(左边是我得到的，右边是应该的):

PID     WAIT    TURNAROUND              PID     WAIT    TURNAROUND
1       0       9                       1       0       9
2       0       2                       2       0       2
3       0       1                       3       0       1
4       0       26                      4       0       26
5       0       14                      5       0       5
6       0       3                       6       3       6
7       1       5                       7       4       10
8       8       13                      8       8       13
9       18      25                      9       18      25
10      0       2                       10      0       2

Average Wait: 2.7 Ave Turnaround 10.0  Average Wait: 3.3 Average Turnaround 9.9

我无法缩小问题出在 srtn 函数中的范围，除了 3 个输出之外，所有输出都是正确的，这更加令人困惑!任何帮助将不胜感激!

#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
#define TIME_QUANTUM 1
typedef struct process
{
    int ID;
    int arrival_time;
    int time_to_completion;
    double wait_time;
    double turn_around;
    double time_wait;
    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;
        array[counter].active = 0;
        counter++;
    }
    //fcfs(array, counter);
    //sjf (array, counter);
    srtn(array, counter);
    /*rr (array, counter);
    rrc(array, counter);*/
    return 0;
}
void srtn(struct process array[MAX_PROCESS], int num_pid){
    printf("Shortest Remaining Time Next\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, fin_pid = 0, keep_going=0;//declarations
    process to_sort[MAX_PROCESS];
    //we want to do this next loop for as many processes as we have, or num_pid
    while(keep_going!=1){
        //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[num_valid_processes]=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-1;
        if(array[next_process].active==0){//the id hasn't had the wait time calculated yet
            array[next_process].wait_time = current_time-array[next_process].arrival_time;
            array[next_process].active=1;
            array[next_process].time_wait = current_time;
        }
        if(array[next_process].time_to_completion <= TIME_QUANTUM){
            array[next_process].turn_around = array[next_process].wait_time + (current_time-array[next_process].time_wait)+array[next_process].time_to_completion;
            fin_pid++;
            //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];
            }
        }
        else{
            array[next_process].time_to_completion = array[next_process].time_to_completion - TIME_QUANTUM;
            //to_sort[0].time_to_completion = to_sort[next_process].time_to_completion - TIME_QUANTUM;
        }
        current_time = current_time+TIME_QUANTUM;
        if(fin_pid==num_pid)
            keep_going=1;
    }
    print_info(array, num_pid);
}


void print_info(struct process array[MAX_PROCESS], int num_pid){
    int i;
    double tot_wait=0, tot_turn = 0;
    printf("\x1b[04mPID\tWAIT\tTURNAROUND\n\x1b[24m");
    for(i=0; i<num_pid; i++){
        printf("%d\t%.0f\t%.0f\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: %.1f Average Turnaround %.1f\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;
            if (array[j].time_to_completion == array[min].time_to_completion){
                if(array[j].ID<array[min].ID)
                    min = j;
            }
        }
        process temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}

Answer 1

问题发生在时间 12——pid 6 显示需要 3 秒，而 pid 5 正在运行，还剩 3 秒。如何解决需要相同剩余时间的进程之间的联系？支持 pid 6 会得到左边的结果，支持 pid 5 会得到右边的结果。鉴于您的问题定义较弱，两者都可能是正确的。