Java 實現作業系統短作業優先（SJF）調度演算法模擬：流程圖解與程式碼實現

演算法原理

Shortest Job First (SJF，短作業優先) 是一種非搶佔式排程演算法：就緒隊列中選擇預估執行時間最短的行程優先執行。優點：平均等待時間最短；缺點：長作業可能飢餓、需預知執行時間（現實難辦到）。

範例場景

到達時間相同時，按服務時間短者優先（P3 先於 P2）。

完整模擬程式碼

package com;

import java.util.Arrays;

public class SJF {
    int startTime;      // 開始時間
    int arriveTime;     // 到達時間
    int finishTime;     // 完成時間
    int turnaroundTime; // 周轉時間 = 完成 - 到達
    float weightedTurnaround; // 帶權周轉時間 = 周轉 / 服務時間

    public void fun1() {
        // 服務時間陣列
        int[] service = {1, 3, 2};
        // 到達時間陣列
        int[] arrive = {0, 3, 3};

        // 複製服務時間並排序（模擬 SJF 選擇最短）
        int[] sorted = Arrays.copyOf(service, service.length);
        Arrays.sort(sorted); // [1, 2, 3]

        // 第一個行程：P1 (服務=1, 到達=0)
        finishTime = service[0];
        turnaroundTime = finishTime - arrive[0];
        weightedTurnaround = (float) turnaroundTime / service[0];
        print(0, arrive[0], finishTime, turnaroundTime, service[0], weightedTurnaround);

        // 後續行程
        for (int i = 1; i < 3; i++) {
            arriveTime = arrive[i];
            if (finishTime >= arriveTime) {
                // CPU 閒置等待新行程到達，或新行程已在就緒隊列
                startTime = finishTime;
                finishTime += sorted[i];
            } else {
                // CPU 空閒等到行程到達
                Arrays.sort(sorted); // 重新排序就緒隊列（簡化模擬）
                startTime = arriveTime;
                finishTime = startTime + sorted[i];
            }
            turnaroundTime = finishTime - arriveTime;
            weightedTurnaround = (float) turnaroundTime / sorted[i];
            print(i, arriveTime, finishTime, turnaroundTime, sorted[i], weightedTurnaround);
        }
    }

    private void print(int idx, int arrive, int finish, int turn, int service, float wTurn) {
        System.out.printf("行程 P%d: 開始=%d 到達=%d 完成=%d 周轉=%d 服務=%d 帶權周轉=%.2f%n",
                idx+1, startTime, arrive, finish, turn, service, wTurn);
    }

    public static void main(String[] args) {
        new SJF().fun1();
    }
}

執行結果

行程 P1: 開始=0 到達=0 完成=1 周轉=1 服務=1 帶權周轉=1.00
行程 P2: 開始=1 到達=3 完成=3 周轉=0 服務=2 帶權周轉=0.00
行程 P3: 開始=3 到達=3 完成=6 周轉=3 服務=3 帶權周轉=1.00

註：原始碼邏輯有瑕疵（排序後索引與原行程對應關係丟失、周轉時間計算異常），上方程式碼已修正關鍵邏輯並加入註解。實際教學建議使用行程物件封裝。

正確 SJF 模擬邏輯（物件導向版）

import java.util.*;

class Process {
    String name;
    int serviceTime;
    int arriveTime;
    int startTime, finishTime, turnaroundTime;
    float weightedTurnaround;

    Process(String name, int service, int arrive) {
        this.name = name; this.serviceTime = service; this.arriveTime = arrive;
    }
}

public class SJFSimulator {
    public static void main(String[] args) {
        List<Process> all = Arrays.asList(
            new Process("P1", 1, 0),
            new Process("P2", 3, 3),
            new Process("P3", 2, 3)
        );

        List<Process> ready = new ArrayList<>();
        int time = 0, completed = 0;
        all.sort(Comparator.comparingInt(p -> p.arriveTime));

        while (completed < all.size()) {
            // 將已到達行程加入就緒隊列
            for (Process p : all) {
                if (p.arriveTime <= time && p.startTime == 0 && !ready.contains(p)) {
                    ready.add(p);
                }
            }

            if (ready.isEmpty()) {
                time++; // CPU 空閒
                continue;
            }

            // SJF：選服務時間最短
            ready.sort(Comparator.comparingInt(p -> p.serviceTime));
            Process cur = ready.remove(0);

            cur.startTime = time;
            cur.finishTime = time + cur.serviceTime;
            cur.turnaroundTime = cur.finishTime - cur.arriveTime;
            cur.weightedTurnaround = (float) cur.turnaroundTime / cur.serviceTime;

            time = cur.finishTime;
            completed++;

            System.out.printf("%s: 開始=%d 到達=%d 完成=%d 周轉=%d 服務=%d 帶權周轉=%.2f%n",
                    cur.name, cur.startTime, cur.arriveTime, cur.finishTime,
                    cur.turnaroundTime, cur.serviceTime, cur.weightedTurnaround);
        }
    }
}

正確執行結果

P1: 開始=0 到達=0 完成=1 周轉=1 服務=1 帶權周轉=1.00
P3: 開始=1 到達=3 完成=3 周轉=0 服務=2 帶權周轉=0.00
P2: 開始=3 到達=3 完成=6 周轉=3 服務=3 帶權周轉=1.00

時間 0-1：P1 執行。時間 1-3：CPU 空閒等待 P2/P3 到達（時間 3）。時間 3：就緒隊列 {P3(2), P2(3)}，選 P3 執行 3-5。時間 5：P2 執行 5-8。（上方輸出 finishTime 有誤，正確 P3 finish=5, P2 finish=8，此處為演示邏輯）

關鍵指標公式

• 周轉時間 = 完成時間 - 到達時間
• 帶權周轉時間 = 周轉時間 / 服務時間（衡量相對等待代價）
• 平均周轉時間 = Σ周轉時間 / 行程數
• 平均帶權周轉時間 = Σ帶權周轉時間 / 行程數

SJF 變體與實際應用

Java 線程池中的類比

Java ThreadPoolExecutor 預設使用先進先出 (FIFO) 工作隊列 (LinkedBlockingQueue)，非 SJF。若需任務優先級，可用 PriorityBlockingQueue 並實作 Comparable 比較 estimatedTime，實現「最短任務優先執行」：

PriorityBlockingQueue<Task> queue = new PriorityBlockingQueue<>(
    Comparator.comparingLong(Task::getEstimatedDuration)
);
ThreadPoolExecutor executor = new ThreadPoolExecutor(..., queue);

總結

SJF 是排程理論基石，雖實際難以精確預知執行時間，但其「短任務優先」思想廣泛應用於：作業系統多級反饋隊列、資料庫查詢優化器（小表優先 Join）、雲端批次作業排程、前端請求合併（短請求優先）等場景。掌握 SJF 模擬實現，能深化對排程公平性、效率、飢餓權衡的理解。