5 调度

5.1 调度的层次

长程调度（作业调度、高级调度）

• 将已进入系统并处于后备状态的作业按某种算法选择一个或一批，为其建立进程，并进入主机，当该作业执行完毕时，还负责回收系统资源

• 批处理系统需要作业调度，以便将进程分批地装入内存，

• 在分时系统和实时系统中，通常不需要长程调度。

• 它的频率比较低，主要用来控制内存中进程的数量。

中程调度（交换调度、中级调度）

• 将进程从内存或从CPU竞争中移出到外存（挂起），之后它能被重新调入内存（就绪），并从中断处继续执行。

• 这种交换的操作可以调整进程在内存中存在的数量和时机。

• 其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或等待状态的进程交换到外存交换区。

• 主要发生于不使用虚存的系统

短程调度（进程调度、低级调度、微观调度）

• 这也是通常所说的调度，一般情况下使用最多的就是短程调度。

• 它的主要任务是按照某种策略和算法将处理机分配给一个处于就绪状态的进程

1. 非抢占式（non-preemptive）：一个进程只有在自愿放弃CPU或者因为等待某个事件而被阻塞时，操作系统才会将 CPU分配给另一个进程，如多道批处理系统

2. 抢占式（preemptive）：如分时系统、实时系统
• 能有效提高系统吞吐率和响应效率
• 优先权、短进程优先、时间片

5.2 调度的目标

1. 面向用户：单个用户或进程感知到的系统行为
面向系统：处理器的使用的效果和效率

2. 与性能直接相关：定量的
其它：定性的

5.3 典型调度算法

先来先服务（FCFS）调度算法

• 最简单，既可用于作业调度，又可用于进程调度

• 选择最先进入队列的进程，将处理器分配给它

• 效率低，对长作业有力，对短作业无力

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

• 选择（估计）运行时间最短的作业，将它们调入内存运行

• 平均等待时间、平均周转时间最少

• 对长作业不利

最短剩余时间（SRT）

• 抢占+SPN

• 也称最早截止时间

高响应比优先（HRRN）调度算法

• 主要用于作业调度

• 同时考虑每个作业的等待时间和估计的运行时间

• 每次选择响应比最高的进程投入运行

短程调度算法

优先级调度算法

• 每次从就绪队列中选择优先级最高的进程，将处理器分配给它

• 既可用于作业调度，又可用于进程调度

• 多优先级队列

• 动态优先级

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

• 主要适用于分时系统

• 所有就绪进程按照FCFS策略排成一个就绪队列

• 调度程序总是选择队列中第一个进程执行，但又仅能运行一个时间片

• 被剥夺的进程返回就绪队列的末尾重新排队

• 时间片的大小对系统的性能影响很大
• 时间片太小，则进程的切换过于频繁，切换的开销增加
• 时间片太大，进程可能得不到及时的响应

多级队列调度算法

• 设置多个就绪队列，将不同类型或性质的进程固定分配不同的就绪队列

• 每个队列可实施不同的调度算法

多级反馈队列调度算法

• 是时间片轮转调度算法和优先级调度算法的综合发展

• 设置多个就绪队列，为每个队列赋予不同的优先级

• 赋予各个队列的进程运行的时间片大小各不相同，优先级越高的队列，时间片越小，在队列内FCFS

• 在一个队列完成一个时间片后，转入下一级队列等待调度

• 仅当优先级高队列为空时，才能调度下一级队列

例题

这里好像有点问题，t=2时应该继续执行A，时间片还没中断

ChatGPT和我想的一样

5.4 多核处理器调度算法

• 对称多处理器（SMP）：主流处理器，每个CPU自己决定自己的调度算法

• 非对称处理器（ASMP）：一般仅一个处理器能处理系统数据结构，减轻对数据的共享需求。

• 负载平衡问题：每个处理器处理的内容尽量平均

• 亲和性：进程在某个指定的CPU上尽量长时间地运行而不被迁移到其他处理器的倾向性。
• 软亲和性（进程尽量不切换）
• 硬亲和性（进程不切换）

课堂练习

期末真题

2024秋

2020春

• 为了缩短响应时间（提高交互性），调度程序通常优先让短作业或前台进程先运行，比如采用短作业优先（SJF）或高响应比优先（HRRN）算法。 这样用户能很快得到响应，但频繁切换进程、长作业被推迟，会增加调度开销，降低系统总体效率。

• 为了提高吞吐量（单位时间完成的作业数），调度程序往往倾向于让CPU长时间运行同一进程，减少切换次数。
这样系统整体效率高，但响应时间变长，交互性变差。

2014