操作系统调度算法 SJF 与 SRTF：从非抢占到抢占的效率追求

两个追求"极致效率"的调度算法：用最短作业优先（SJF）压低平均周转时间，用最短剩余时间优先（SRTF）再压一截——代价是长作业可能"饿死"。

引言

之前聊过 FCFS（先来先服务） 的公平和 RR（时间片轮转） 的响应。这次要讲的是在"效率"上追求极致的思想——短作业优先（SJF） 及其抢占式版本 SRTF。

如果说 FCFS 是"先来后到"，RR 是"人人有份"，那 SJF 的核心就是 “能者多劳，短者先上”。它追求的是 最小化系统的平均等待时间和平均周转时间。

1. 短作业优先（SJF）：非抢占式的"效率至上"

SJF 是一种非抢占式调度算法。规则很简单：在所有已到达的就绪进程中，选择预计运行时间（CPU 突发时间）最短的那个来执行。

一旦一个进程开始运行，即使后面来了更短的进程，也必须等当前进程执行完毕或被阻塞。

1.1 一个具体例子

四个进程几乎同时到达（到达时间均为 0）：

进程	到达时间	服务时间
A	0	8
B	0	4
C	0	2
D	0	1

SJF 调度顺序：D(1) → C(2) → B(4) → A(8)

进程	完成时间	周转时间	带权周转时间
D	1	1	1.0
C	3	3	1.5
B	7	7	1.75
A	15	15	1.875

• 平均周转时间 = (1+3+7+15)/4 = 6.5
• 平均带权周转时间 = (1+1.5+1.75+1.875)/4 = 1.53

对比 FCFS（顺序 A→B→C→D），平均周转时间是 (8+12+14+15)/4 = 12.25。SJF 直接砍掉近一半，效率优势非常明显。

2. 最短剩余时间优先（SRTF）：抢占式的"极致效率"

SRTF 是 SJF 的抢占式版本。规则：每当有新进程到达就绪队列时，系统比较新进程和当前正在运行进程的"剩余所需时间"。如果新进程剩余时间更短，立即抢占 CPU。

一个长作业可能被多个后到的短作业反复打断。

2.1 一个具体例子

进程在不同时间到达：

进程	到达时间	服务时间
A	0	8
B	1	4
C	2	2
D	3	1

推演过程：

• 0~1：只有 A 到达，A 运行 1 个时间单位，剩余 7
• 1：B 到达（需 4），A 剩余 7，A 继续运行
• 2：C 到达（需 2），A 剩余 6，A 继续运行
• 3：D 到达（需 1），A 剩余 5。D 剩余时间(1) < A 剩余时间(5)，D 抢占 A
• 3~4：D 运行，完成
• 4：就绪队列有 A(剩 5)、B(4)、C(2)，C 最短，C 运行
• 4~6：C 运行，完成
• 6：就绪队列有 A(5)、B(4)，B 最短，B 运行
• 6~10：B 运行，完成
• 10~15：A 运行，完成

最终完成顺序：D → C → B → A

进程	完成时间	周转时间
D	4	1
C	6	4
B	10	9
A	15	15

• 平均周转时间 = (1+4+9+15)/4 = 7.25

如果用非抢占 SJF，顺序是 A(8) → D(1) → C(2) → B(4)，平均周转时间是 8.25。SRTF 又优化了一截。

3. SJF vs SRTF 对比

特性	SJF（非抢占）	SRTF（抢占）
核心机制	选已到达最短作业运行至结束	新作业剩余更短时抢占当前进程
平均周转时间	最小	更小
缺点	长作业可能饥饿	长作业饥饿风险更高；上下文切换开销更大
实现难度	中等	较高，需处理抢占逻辑
适用场景	批处理系统	对平均周转时间要求极高的系统

4. Java 代码实现

4.1 SJF 实现（非抢占）

import java.util.*;

class SJFScheduler {

    static class Process {
        String pid;
        int arrival;
        int burst;
        int finishTime;

        Process(String pid, int arrival, int burst) {
            this.pid = pid;
            this.arrival = arrival;
            this.burst = burst;
        }
    }

    public static void sjf(List<Process> processes) {
        // 按到达时间排序
        processes.sort(Comparator.comparingInt(p -> p.arrival));
        int time = 0;
        int completed = 0;
        int n = processes.size();
        boolean[] isCompleted = new boolean[n];

        while (completed < n) {
            int idx = -1;
            int shortestBurst = Integer.MAX_VALUE;

            // 在已到达且未完成的进程中找最短的
            for (int i = 0; i < n; i++) {
                Process p = processes.get(i);
                if (!isCompleted[i] && p.arrival <= time && p.burst < shortestBurst) {
                    shortestBurst = p.burst;
                    idx = i;
                }
            }

            if (idx == -1) {
                // 无进程可运行，CPU 空闲，跳到下一个进程到达时间
                time++;
                continue;
            }

            Process current = processes.get(idx);
            time += current.burst;
            current.finishTime = time;
            isCompleted[idx] = true;
            completed++;
        }
    }

    public static void main(String[] args) {
        List<Process> procs = Arrays.asList(
            new Process("A", 0, 8),
            new Process("B", 0, 4),
            new Process("C", 0, 2),
            new Process("D", 0, 1)
        );
        sjf(procs);
    }
}

4.2 SRTF 实现（抢占）

import java.util.*;

class SRTFScheduler {

    static class Process {
        String pid;
        int arrival;
        int burst;          // 剩余运行时间
        int originalBurst;  // 原始运行时间
        int finishTime;

        Process(String pid, int arrival, int burst) {
            this.pid = pid;
            this.arrival = arrival;
            this.burst = burst;
            this.originalBurst = burst;
        }
    }

    public static void srtf(List<Process> processes) {
        processes.sort(Comparator.comparingInt(p -> p.arrival));
        int n = processes.size();
        int completed = 0;
        int time = 0;
        Process current = null;

        while (completed < n) {
            // 找就绪队列中剩余时间最短的进程
            int shortestIdx = -1;
            int shortestRemaining = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                Process p = processes.get(i);
                if (p.burst > 0 && p.arrival <= time && p.burst < shortestRemaining) {
                    shortestRemaining = p.burst;
                    shortestIdx = i;
                }
            }

            if (shortestIdx == -1) {
                // 无进程可运行，CPU 空闲
                time++;
                continue;
            }

            current = processes.get(shortestIdx);
            // 执行一个时间单位（也可优化为运行到下一个事件点）
            current.burst--;
            time++;

            // 检查当前进程是否完成
            if (current.burst == 0) {
                current.finishTime = time;
                completed++;
            }
        }
    }

    public static void main(String[] args) {
        List<Process> procs = Arrays.asList(
            new Process("A", 0, 8),
            new Process("B", 1, 4),
            new Process("C", 2, 2),
            new Process("D", 3, 1)
        );
        srtf(procs);
    }
}

5. 总结

SJF 和 SRTF 是追求极致效率的调度算法，理论上能达到最优的平均周转时间。

但这种效率的代价也很明显：

• 长作业可能永远得不到执行（饥饿）
• 需要预先知道每个进程的运行时间——这在现实中往往难以做到

这些缺陷使得 SJF 和 SRTF 在现代通用操作系统中很少被单独使用。但它们"优先服务短任务以提高效率"的思想被广泛继承，成为更复杂调度算法（如多级反馈队列）的重要组成部分。