C语言SPN进程调度模拟器startTime计算错误求助

问题概述 #

• 已实现支持FCFS、SRT、SPN三种调度算法的进程调度模拟器，其中FCFS和SRT功能正常，但SPN算法的start_time计算存在异常
• 测试输入进程信息：
  • 进程A：到达时间0，服务时间3
  • 进程B：到达时间2，服务时间6
  • 进程C：到达时间4，服务时间4
  • 进程D：到达时间6，服务时间5
  • 进程E：到达时间8，服务时间2
• 实际输出与SPN调度规则的期望结果偏差较大，已尝试调试spn函数但未定位到问题，以下为完整代码：

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

typedef struct {
    char name;
    int arrival_time;
    int service_time;
    int start_time;
    int finish_time;
    int waiting_time;
    int turnaround_time;
    int completed;
} Process;

void spn(Process proc[], int n) {
    int current_time = 0;
    int completed = 0;
    while (completed < n) {
        int idx = -1;
        int shortest = INT_MAX;
        // 寻找已到达且未完成的最短服务时间进程
        for (int i = 0; i < n; i++) {
            if (proc[i].arrival_time <= current_time && proc[i].completed == 0) {
                if (proc[i].service_time < shortest) {
                    shortest = proc[i].service_time;
                    idx = i;
                }
            }
        }
        if (idx == -1) {
            current_time++;
            continue;
        }
        proc[idx].start_time = current_time;
        proc[idx].finish_time = current_time + proc[idx].service_time;
        proc[idx].turnaround_time = proc[idx].finish_time - proc[idx].arrival_time;
        proc[idx].waiting_time = proc[idx].turnaround_time - proc[idx].service_time;
        proc[idx].completed = 1;
        completed++;
        current_time = proc[idx].finish_time;
    }
}

void fcfs(Process proc[], int n) {
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        if (current_time < proc[i].arrival_time) {
            current_time = proc[i].arrival_time;
        }
        proc[i].start_time = current_time;
        proc[i].finish_time = current_time + proc[i].service_time;
        proc[i].turnaround_time = proc[i].finish_time - proc[i].arrival_time;
        proc[i].waiting_time = proc[i].turnaround_time - proc[i].service_time;
        current_time = proc[i].finish_time;
        proc[i].completed = 1;
    }
}

void srt(Process proc[], int n) {
    int current_time = 0;
    int completed = 0;
    int remaining_time[n];
    for (int i = 0; i < n; i++) {
        remaining_time[i] = proc[i].service_time;
    }
    while (completed < n) {
        int idx = -1;
        int shortest = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (proc[i].arrival_time <= current_time && proc[i].completed == 0 && remaining_time[i] < shortest) {
                shortest = remaining_time[i];
                idx = i;
            }
        }
        if (idx == -1) {
            current_time++;
            continue;
        }
        remaining_time[idx]--;
        if (remaining_time[idx] == 0) {
            completed++;
            proc[idx].finish_time = current_time + 1;
            proc[idx].turnaround_time = proc[idx].finish_time - proc[idx].arrival_time;
            proc[idx].waiting_time = proc[idx].turnaround_time - proc[idx].service_time;
            proc[idx].completed = 1;
        }
        current_time++;
    }
}

void print_results(Process proc[], int n) {
    printf("进程名\t到达时间\t服务时间\t开始时间\t完成时间\t周转时间\t等待时间\n");
    for (int i = 0; i < n; i++) {
        printf("%c\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n", 
               proc[i].name, proc[i].arrival_time, proc[i].service_time,
               proc[i].start_time, proc[i].finish_time, proc[i].turnaround_time,
               proc[i].waiting_time);
    }
}

int main() {
    Process proc[] = {
        {'A', 0, 3, 0, 0, 0, 0, 0},
        {'B', 2, 6, 0, 0, 0, 0, 0},
        {'C', 4, 4, 0, 0, 0, 0, 0},
        {'D', 6, 5, 0, 0, 0, 0, 0},
        {'E', 8, 2, 0, 0, 0, 0, 0}
    };
    int n = sizeof(proc)/sizeof(proc[0]);
    
    printf("SPN调度结果:\n");
    spn(proc, n);
    print_results(proc, n);
    
    // 重置进程状态
    for (int i = 0; i < n; i++) {
        proc[i].start_time = 0;
        proc[i].finish_time = 0;
        proc[i].waiting_time = 0;
        proc[i].turnaround_time = 0;
        proc[i].completed = 0;
    }
    
    printf("\nFCFS调度结果:\n");
    fcfs(proc, n);
    print_results(proc, n);
    
    // 重置进程状态
    for (int i = 0; i < n; i++) {
        proc[i].start_time = 0;
        proc[i].finish_time = 0;
        proc[i].waiting_time = 0;
        proc[i].turnaround_time = 0;
        proc[i].completed = 0;
    }
    
    printf("\nSRT调度结果:\n");
    srt(proc, n);
    print_results(proc, n);
    
    return 0;
}

问题定位与修复方案 #

1. 就绪进程判断逻辑漏洞 #

原代码中当当前时间无已到达进程时，仅逐次递增current_time，可能导致进程到达时机判断延迟，甚至遗漏。优化为直接跳转到下一个未完成进程的最早到达时间：

if (idx == -1) {
    int next_arrival = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (proc[i].completed == 0 && proc[i].arrival_time > current_time) {
            next_arrival = (proc[i].arrival_time < next_arrival) ? proc[i].arrival_time : next_arrival;
        }
    }
    current_time = next_arrival;
    continue;
}

2. start_time赋值逻辑错误 #

原代码未处理进程到达时间晚于当前时间的情况，需确保start_time取当前时间与进程到达时间的较大值：

proc[idx].start_time = (current_time < proc[idx].arrival_time) ? proc[idx].arrival_time : current_time;
proc[idx].finish_time = proc[idx].start_time + proc[idx].service_time;
current_time = proc[idx].finish_time;

3. 进程选择优先级冲突处理 #

当多个进程服务时间相同时，需优先选择到达时间更早的进程，避免调度顺序混乱：

if (proc[i].arrival_time <= current_time && proc[i].completed == 0) {
    if (proc[i].service_time < shortest || 
        (proc[i].service_time == shortest && proc[i].arrival_time < proc[idx].arrival_time)) {
        shortest = proc[i].service_time;
        idx = i;
    }
}

验证SPN期望结果 #

根据测试输入，SPN（非抢占式短进程优先）的正确调度时序与参数为：

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