抢占式SJF调度代码异常：等待/周转时间计算错误原因排查

我实现了抢占式最短作业优先（SJF）调度算法，但程序输出的等待时间（wait_time）和周转时间（turnaround_time）数值异常偏大，无法得到预期结果。以下是我的代码：

/** PREEMPTIVE SHORTEST JOB FIRST SCHEDULING */

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

/** global variables */
int burst_time[MAX];
typedef struct
{
    int arrival_time;
    int burst_time;
    int turnaround_time;
    int wait_time;
} Process;

void main(){
    Process p[MAX];
    int i,n;
    printf("\n  SHORTEST JOB FIRST");
    printf("\n  ------------------");
    printf("\n\n  Enter no of processes? ");
    scanf("%d",&n);
    printf("\n\t ARRIVAL TIME      BURST TIME");
    for(i=0;i<n;i++){
        printf("\n  Process %d: ",i+1);
        scanf("%d %d",&p[i].arrival_time,&p[i].burst_time);
    }

    p[0].turnaround_time=p[0].burst_time+p[0].wait_time;
    /** calculate waiting time and turnaround time of each process */
    for(i=0;i<n;i++){
        p[i].wait_time=p[i].arrival_time-p[i-1].turnaround_time;
        p[i].turnaround_time=p[i].burst_time+p[i].wait_time;
    }

    /** Print details of each process */
        printf("\n  +------------+--------------+--------------+------------+-----------------+");
        printf("\n  | PROCESS ID | ARRIVAL TIME | WAITING TIME | BURST TIME | TURNAROUND TIME |");
        printf("\n  +------------+--------------+--------------+------------+-----------------+");
        for(i=0;i<n;i++){
            printf("\n  |     %2d    |      %2d     |      %2d     |     %2d    |       %2d       |",i+1,p[i].arrival_time,
               p[i].wait_time,p[i].burst_time,p[i].turnaround_time);
        }
        printf("\n  +------------+--------------+--------------+------------+-----------------+");
}

问题根源 #

1. 未初始化变量：p[0].wait_time未初始化，初始值为内存随机垃圾值，直接导致第一个进程周转时间计算错误，后续所有计算连锁出错。
2. 调度逻辑完全错误：当前循环中p[i].wait_time = p[i].arrival_time - p[i-1].turnaround_time的公式不符合抢占式SJF逻辑。抢占式SJF需要动态跟踪当前时间、已到达进程的剩余执行时间，每次选择剩余时间最短的进程执行，而非按输入顺序简单计算。
3. 冗余全局变量：全局数组burst_time未被使用，属于无效代码。
4. 函数返回值不规范：main函数应返回int类型而非void，不符合C语言标准。

修正后的代码 #

/** PREEMPTIVE SHORTEST JOB FIRST SCHEDULING */

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

typedef struct
{
    int arrival_time;
    int burst_time;
    int turnaround_time;
    int wait_time;
    int remaining_time; // 跟踪进程剩余执行时间
} Process;

int main(){
    Process p[MAX];
    int i, n, current_time = 0, completed = 0, shortest = -1;
    int total_wait = 0, total_turnaround = 0;
    int is_process_arrived;

    printf("\n  SHORTEST JOB FIRST");
    printf("\n  ------------------");
    printf("\n\n  Enter no of processes? ");
    scanf("%d", &n);
    printf("\n\t ARRIVAL TIME      BURST TIME");
    for(i=0; i<n; i++){
        printf("\n  Process %d: ", i+1);
        scanf("%d %d", &p[i].arrival_time, &p[i].burst_time);
        p[i].remaining_time = p[i].burst_time;
        p[i].wait_time = 0;
        p[i].turnaround_time = 0;
    }

    // 抢占式SJF核心调度逻辑
    while(completed < n){
        is_process_arrived = 0;
        // 找到当前时间已到达且剩余时间最短的进程
        for(i=0; i<n; i++){
            if(p[i].arrival_time <= current_time && p[i].remaining_time > 0){
                is_process_arrived = 1;
                if(shortest == -1 || p[i].remaining_time < p[shortest].remaining_time){
                    shortest = i;
                }
            }
        }

        if(!is_process_arrived){
            current_time++; // 无进程到达，推进时间
            continue;
        }

        // 执行选中进程1个时间片
        p[shortest].remaining_time--;
        current_time++;

        // 进程执行完成时计算时间
        if(p[shortest].remaining_time == 0){
            completed++;
            int completion_time = current_time;
            p[shortest].turnaround_time = completion_time - p[shortest].arrival_time;
            p[shortest].wait_time = p[shortest].turnaround_time - p[shortest].burst_time;

            total_wait += p[shortest].wait_time;
            total_turnaround += p[shortest].turnaround_time;
            shortest = -1; // 重置最短进程索引
        }
    }

    // 输出结果表格
    printf("\n  +------------+--------------+--------------+------------+-----------------+");
    printf("\n  | PROCESS ID | ARRIVAL TIME | WAITING TIME | BURST TIME | TURNAROUND TIME |");
    printf("\n  +------------+--------------+--------------+------------+-----------------+");
    for(i=0; i<n; i++){
        printf("\n  |     %2d    |      %2d     |      %2d     |     %2d    |       %2d       |",
               i+1, p[i].arrival_time, p[i].wait_time, p[i].burst_time, p[i].turnaround_time);
    }
    printf("\n  +------------+--------------+--------------+------------+-----------------+");
    printf("\n\n  Average Waiting Time: %.2f", (float)total_wait/n);
    printf("\n  Average Turnaround Time: %.2f\n", (float)total_turnaround/n);

    return 0;
}

修正说明 #

1. 新增剩余时间跟踪：添加remaining_time字段，用于动态记录进程未执行的时间，支撑抢占式调度判断。
2. 正确调度逻辑：通过循环实时跟踪当前时间，每次选择已到达且剩余时间最短的进程执行1个时间片，模拟抢占过程。
3. 变量初始化：所有时间相关变量均初始化为合理值，避免垃圾值干扰计算。
4. 正确时间计算：
   • 周转时间 = 完成时间 - 到达时间
   • 等待时间 = 周转时间 - 原始burst时间
5. 规范代码格式：将main函数改为返回int类型，符合C语言标准；移除冗余全局变量。
6. 添加平均时间统计：计算并输出平均等待/周转时间，方便结果验证。

内容的提问来源于stack exchange，提问作者John Philip