当前位置：首页 > news >正文

FCFS，SJF，HRRN三种调度方法详解，先来先服务，短作业优先，最高响应比优先

news 2025/7/21 11:25:44

在评价一个工头的工作方法时，我们主要关心这几点：

这位工头的管理哲学就是“绝对公平”，他手里只有一个排号机，谁先来领号，谁就先被服务。

算法目的：实现最简单、最直观的公平。
算法规则：严格按照任务（进程）到达的先后顺序进行调度。
工作风格：非抢占式。一旦一个任务开始，就必须等它自己主动完成或阻塞，不能中途打断。就像银行柜员，不会办你业务到一半，去给别人办。
优缺点：
- 优点：公平、简单、易于实现。每个任务都有机会被执行，不会有任务被永远遗忘。
- 缺点：效率可能极低。想象一下，一个只需要1分钟的短任务，排在了一个需要2小时的长任务后面，它就得白白等上2个小时。这种情况严重损害了短任务的体验，也拉低了整个系统的平均周转时间。这被称为“队首阻塞”或“护航效应”。
是否导致饥饿：不会。只要你排队了，总有一天会轮到你。

这位工头是个急性子，他的人生信条是“尽快搞定更多的事”。他会扫视所有在等候的任务，然后挑那个最快能完成的先做。

算法目的：追求最低的平均等待时间和平均周转时间。
算法规则：从所有已经到达的、处于就绪状态的任务中，选择一个估计运行时间最短的来执行。
工作风格：
- 非抢占式版本：选定一个短任务后，就让它一口气做完。
- 抢占式版本 (最短剩余时间优先, SRTN)：这是个更“极端”的工头。当一个任务正在执行时，如果来了一个新任务，并且这个新任务所需的总时间比当前任务剩下需要的时间还要短，他会立刻叫停当前任务，转而去执行那个新来的、更短的任务。
优缺点：
- 优点：在“平均等待/周转时间”这个指标上，它被证明是理论上最优的。对短作业非常友好。
- 缺点：不公平。如果系统不断有新的短任务进来，那么那些需要执行很长时间的长任务，可能永远也得不到执行的机会，因为它“不够短”。
是否导致饥饿：会。长作业有被“饿死”的风险。

这位工头吸取了前两位的教训。他既想追求效率，又不想让任何一个任务等得太久而“心生怨念”。于是他发明了一套动态的优先级系统。

算法目的：在SJF的基础上，引入对等待时间的考量，是一种折中和优化方案，旨在避免饥饿。
算法规则：在每次调度时，计算所有就绪任务的“响应比”，然后选择响应比最高的任务来执行。
- 响应比公式： 响应比 = (等待时间 + 要求服务时间) / 要求服务时间
规则解读：
- 这个公式很巧妙。当等待时间相同时，服务时间越短，分母越小，响应比越高。这体现了SJF的优点，偏爱短作业。
- 当服务时间相同时，等待时间越长，分子越大，响应比也越高。这保证了等待很久的长作业，其优先级会随着时间推移而动态提高，最终总有机会被选中。
工作风格：非抢占式。因为每次调度都需要重新计算所有任务的响应比，开销较大，一般不设计成抢占式的。
优缺点：
- 优点：综合了FCFS和SJF的优点。既照顾了短作业，又通过“动态优先级”解决了长作业的饥饿问题，实现了比较好的平衡。
- 缺点：实现相对复杂，每次调度都需要计算所有就绪进程的响应比，有一定的系统开销。
是否导致饥饿：不会。任何任务的等待时间增加，都会使其响应比增加，最终能被调度。