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

操作系统中的任务调度算法

news 来源：原创 2025/5/18 7:02:12

在多任务操作系统中，任务调度算法（Task Scheduling Algorithm）是决定CPU资源如何分配给进程或线程的核心机制。优秀的调度算法需要平衡响应时间、吞吐量和公平性，同时适应不同的应用场景。

任务调度的核心目标

CPU利用率最大化：减少空闲时间
降低等待时间：提升用户体验
公平性：合理分配时间片
优先级处理：区分实时任务与普通任务
避免饥饿：确保所有任务最终被执行

经典调度算法详解

先来先服务（FCFS）

算法思想：主要从“公平”的角度考虑，先到先服务。

算法规则：先进入系统的作业/进程优先被挑选。

用于作业 / 进程调度：

用于作业调度时，考虑的是哪个作业先到达后备队列；
用于进程调度时，考虑的是哪个进程先到达就绪队列。

是否可抢占：非抢占式

优点：公平、算法实现简单。

缺点：对长作业有利，对短作业不利。
排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。
是否导致饥饿：不会

最短作业优先调度算法（SJF）

算法规则：每次调度时选择当前已到达且运行时间最短的作业/进程。

是否可抢占：非抢占式

优点：

最小化平均等待时间，提高系统的吞吐量。
对短作业有较好的响应性，能够快速执行短作业。

缺点：

需要预先知道每个进程的执行时间，对实时系统不太适用。
可能会导致长作业饥饿，即长作业一直等待短作业执行完毕而无法执行。

最短剩余时间优先调度算法（SRTF）

算法规则：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

是否可抢占：抢占式

优点：对比非抢占式的短作业优先算法，抢占式的短作业优先算法的平均等待时间、平均周转时间、平均带权周转时间都更低。

响应比最高者优先调度算法（HRRF）

算法思想：选择等待时间和要求服务时间都较短的作业/进程优先调度。

算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。

响应比
= 响应时间/要求服务时间
= （等待时间+要求服务时间）/ 要求服务时间
= 1 + 等待时间/作业处理时间
（作业要求服务时间由用户给出，是一个常量）

优点：

提高系统对用户请求的响应速度。
特别适用于交互式应用，能够快速响应用户输入。

缺点：

长时间等待的作业可能被短作业抢先执行，导致长作业的响应时间延长，可能出现饥饿现象。
需要频繁计算响应比，增加了系统的开销。

时间片轮转调度算法（RR）

算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
调度程序每次把CPU分配给就绪队列首进程/线程使用一个时间间隔（称为时间片），就绪队列中的每个进程/线程轮流运行一个时间片。

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（每次选择的都是排在就绪队列队头的进程）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

时间片的选取：时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。

常用轮转法：

最常用的轮转法是等时间片轮转法，每个进程轮流运行相同时间片。
改进的轮转法对于不同的进程分配不同的时间片，时间片的长短可以动态修改。

优点：

公平性：所有就绪进程都有机会执行，避免了长时间占用CPU的情况。
响应时间：对于每个进程，响应时间通常较快，因为它们在队列中等待的时间有限。

缺点：

上下文切换开销：频繁的上下文切换会增加系统开销。
时间片大小选择：如果时间片过小，可能会导致过多的上下文切换；如果时间片过大，可能会影响系统的响应速度。

多级反馈队列调度算法 (MLFQ)

算法思想：对其他调度算法的折中权衡。

算法规则：

建立多级就绪进程队列，各级队列优先级从高到低，时间片从小到大。每个队列赋予不同优先级，较高优先级队列一般分配给较短的时间片。
新进程到达时先进入第1级队列，按先来先服务原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾；若此时已经在最下级的队列，则重新放回该队列队尾。
处理器调度每次先从高优先级就绪队列中选取可占有处理器的进程，只有在选不到时，才从较低优先级就绪队列中选取进程。即只有第k级队列为空时，才会为k+1级队头的进程分配时间片。

优点：

动态调整：根据进程的执行情况，系统可以动态调整优先级和时间片长度，提高了系统的适应性。
公平性：通过多级队列的方式，能够合理分配CPU时间，避免长时间占用CPU的情况，增强了公平性。
响应时间：对于短作业或优先级较高的进程，响应时间通常较短，提高了系统的响应速度。

缺点：

实现复杂性：管理多个队列、动态调整优先级和时间片长度增加了算法的实现复杂性。
上下文切换开销：频繁的队列调度和进程移动可能会增加系统的上下文切换开销，降低系统性能。