如何计算抢占式优先级调度中的进程开始时间StartedAt

现有逻辑的核心问题 #

• 抢占调度阶段逻辑错误：仅按优先级静态排序，在进程交换时直接计算剩余突发时间的方式不符合抢占调度的时间推进逻辑，没有考虑不同进程到达时间的先后顺序对运行时长的影响，导致remBurstTime计算存在误差。
• FCFS初始StartedAt取值错误：直接将排序后首个进程的到达时间作为FCFS的起始时间，没有覆盖抢占阶段已经消耗的时间，最终导致周转、等待时间计算偏差。

修复代码实现 #

1. 重写抢占式优先级调度方法 #

该方法将模拟时间推进过程，计算正确的剩余突发时间，同时返回抢占阶段结束后的时间点作为FCFS的初始启动时间：

public static int PriorityPreemptive(ProcessInfo[] process) {
    int n = process.length;
    for (ProcessInfo p : process) p.remBurstTime = p.BurstTime;
    int currentTime = 0;
    int completed = 0;
    while (completed < n) {
        // 找到当前时间已到达、未完成的最高优先级进程
        int highestPrioIdx = -1;
        int minPriority = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (process[i].ArrivalTime <= currentTime 
                && process[i].remBurstTime > 0 
                && process[i].Priority < minPriority) {
                minPriority = process[i].Priority;
                highestPrioIdx = i;
            }
        }
        if (highestPrioIdx == -1) {
            // 没有可执行进程，时间跳转到下一个进程的到达时间
            int nextArrival = Integer.MAX_VALUE;
            for (ProcessInfo p : process) {
                if (p.remBurstTime > 0 && p.ArrivalTime < nextArrival) {
                    nextArrival = p.ArrivalTime;
                }
            }
            currentTime = nextArrival;
            continue;
        }
        // 计算当前进程可以运行的时长：要么运行完，要么运行到下一个更高优先级进程到达
        int runTime = process[highestPrioIdx].remBurstTime;
        for (int i = 0; i < n; i++) {
            if (process[i].ArrivalTime > currentTime 
                && process[i].Priority < minPriority 
                && (process[i].ArrivalTime - currentTime) < runTime) {
                runTime = process[i].ArrivalTime - currentTime;
            }
        }
        process[highestPrioIdx].remBurstTime -= runTime;
        currentTime += runTime;
        if (process[highestPrioIdx].remBurstTime == 0) {
            completed++;
            process[highestPrioIdx].CompletionTime = currentTime;
        }
    }
    // 返回抢占阶段结束的时间，作为FCFS的初始启动时间
    return currentTime;
}

2. 修正FCFS方法的StartedAt逻辑 #

移除原有初始StartedAt的判断逻辑，改为接收外部传入的初始启动时间，同时增加进程到达时间判断避免时间计算错误：

// 新增入参initialStartedAt，为抢占阶段结束后的时间点
public static void FCFS(ProcessInfo[] process, int initialStartedAt) {
    double totalWaitTime = 0;
    double totalTurnAroundTime = 0;
    int startedAt = initialStartedAt;
    for (ProcessInfo processInfo : process) {
        if (processInfo.remBurstTime <= 0) continue; // 跳过已经在抢占阶段完成的进程
        // 进程实际开始时间取当前时间和进程到达时间的最大值，避免进程未到达就提前计算
        int actualStart = Math.max(startedAt, processInfo.ArrivalTime);
        processInfo.CompletionTime = actualStart + processInfo.remBurstTime;
        startedAt = processInfo.CompletionTime;
        processInfo.TurnAroundTime = processInfo.CompletionTime - processInfo.ArrivalTime;
        processInfo.WaitTime = processInfo.TurnAroundTime - processInfo.BurstTime;
        totalWaitTime += processInfo.WaitTime;
        totalTurnAroundTime += processInfo.TurnAroundTime;
        System.out.println("Started :\t " + actualStart + "  Completion :\t " + processInfo.CompletionTime + "  TurnAround :\t " + processInfo.TurnAroundTime + "  WaitTime :\t" + processInfo.WaitTime);
    }
    double avgWaitingTime = totalWaitTime / process.length;
    double avgTurnAroundTime = totalTurnAroundTime / process.length;
    System.out.println("平均等待时间为 :\t" + avgWaitingTime + "\n平均周转时间为 :\t " + avgTurnAroundTime);
}

调用示例 #

int initialStartedAt = PriorityPreemptive(processList);
FCFS(processList, initialStartedAt);

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