C语言实现抢占式短作业优先(PSJF)时出现程序阻塞问题求助

问题概述 #

实现的PSJF调度算法运行时陷入死循环，必须强制终止程序才能退出，核心怀疑点为任务选择的if判断逻辑。

核心问题分析 #

1. 无意义的时间递增导致死循环 #

当所有未完成任务的到达时间均大于当前时间时，代码进入else分支，每次仅将current_time加1。若存在任务到达时间极大或未正确初始化，current_time会无限递增，永远无法触发任务调度，陷入死循环。

2. 错误修改原始任务执行时间 #

结构体中定义了remaining_time用于记录剩余执行时间，但代码直接修改burst_time（原始执行时间），导致后续最短任务判断逻辑混乱，且丢失原始执行时间的基准值。

3. 抢占逻辑的隐性缺陷 #

当前循环结构虽能在每个时间片后重新选择最短任务，但未正确利用剩余时间字段，导致任务执行状态的跟踪出现偏差。

修复方案 #

1. 修复死循环：跳转至下一个任务到达时间 #

替换原else分支的盲目时间递增逻辑，直接跳转到下一个任务的到达时间，避免无意义循环：

else
{
    int next_arrival = INT_MAX;
    for (int i = 0; i < num_tasks; i++)
    {
        if (!tasks[i].completed && tasks[i].arrival_time > current_time && tasks[i].arrival_time < next_arrival)
        {
            next_arrival = tasks[i].arrival_time;
        }
    }
    if (next_arrival != INT_MAX)
    {
        current_time = next_arrival;
    }
    else
    {
        break;
    }
}

2. 使用剩余时间跟踪任务执行状态 #

• 初始化阶段：加载任务后，将原始burst_time赋值给remaining_time：

// 加载任务后添加初始化逻辑
for (int i = 0; i < num_tasks; i++)
{
    tasks[i].remaining_time = tasks[i].burst_time;
    tasks[i].completed = 0;
    tasks[i].waiting_time = 0;
}

• 修改任务选择判断条件：用remaining_time替代burst_time：

if (!tasks[i].completed && tasks[i].arrival_time <= current_time && tasks[i].remaining_time < shortest_job_burst)

• 更新任务执行逻辑：基于remaining_time处理任务执行，保留原始burst_time用于等待时间计算：

if (tasks[shortest_job_index].remaining_time <= TIME_QUANTUM)
{
    current_time += tasks[shortest_job_index].remaining_time;
    fprintf(output_file, "%d\n", current_time);
    tasks[shortest_job_index].waiting_time = current_time - tasks[shortest_job_index].arrival_time - tasks[shortest_job_index].burst_time;
    total_waiting_time += tasks[shortest_job_index].waiting_time;
    tasks[shortest_job_index].completed = 1;
    remaining_tasks_psjf--;
}
else
{
    current_time += TIME_QUANTUM;
    fprintf(output_file, "%d\n", current_time);
    tasks[shortest_job_index].remaining_time -= TIME_QUANTUM;
}

3. 完整修复后的核心循环代码 #

while (remaining_tasks_psjf > 0)
{
    int shortest_job_index = -1;
    int shortest_job_burst = INT_MAX;
    int found_job = 0;

    for (int i = 0; i < num_tasks; i++)
    {
        if (!tasks[i].completed && tasks[i].arrival_time <= current_time && tasks[i].remaining_time < shortest_job_burst)
        {
            shortest_job_index = i;
            shortest_job_burst = tasks[i].remaining_time;
            found_job = 1;
        }
    }

    if (found_job)
    {
        fprintf(output_file, "%s\t%d\t", tasks[shortest_job_index].name, current_time);
        if (tasks[shortest_job_index].remaining_time <= TIME_QUANTUM)
        {
            current_time += tasks[shortest_job_index].remaining_time;
            fprintf(output_file, "%d\n", current_time);
            tasks[shortest_job_index].waiting_time = current_time - tasks[shortest_job_index].arrival_time - tasks[shortest_job_index].burst_time;
            total_waiting_time += tasks[shortest_job_index].waiting_time;
            tasks[shortest_job_index].completed = 1;
            remaining_tasks_psjf--;
        }
        else
        {
            current_time += TIME_QUANTUM;
            fprintf(output_file, "%d\n", current_time);
            tasks[shortest_job_index].remaining_time -= TIME_QUANTUM;
        }
    }
    else
    {
        int next_arrival = INT_MAX;
        for (int i = 0; i < num_tasks; i++)
        {
            if (!tasks[i].completed && tasks[i].arrival_time > current_time && tasks[i].arrival_time < next_arrival)
            {
                next_arrival = tasks[i].arrival_time;
            }
        }
        if (next_arrival != INT_MAX)
        {
            current_time = next_arrival;
        }
        else
        {
            break;
        }
    }
}

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