说下你知道的调度算法- 题目详情

在操作系统中，调度算法用于决定哪些进程（或线程）在什么时候运行，确保系统资源（如CPU、内存）能够高效地分配给各个进程。调度算法的目标通常是优化系统性能，如减少平均等待时间、提高吞吐量、减少响应时间、避免死锁等。

常见的调度算法有以下几种：

FCFS 是一种最简单的调度算法，它按照进程到达就绪队列的顺序来执行。

特点：
- 按照进程到达时间顺序调度。
- 非抢占式：一旦进程开始执行，直到完成才会被切换。
- 适用于负载较轻的系统。
缺点：
- 不公平：长进程会导致短进程等待很久，产生所谓的“convoy effect”（一大群进程都得跟着长进程等待）。
- 高平均等待时间：长作业会拖慢所有其他进程的执行时间。

SJF 是一种基于进程执行时间的调度算法，优先执行估计执行时间最短的进程。

特点：
- 非抢占式：一旦进程开始执行，直到完成才会被切换。
- 目标是最小化平均等待时间。
- 适用于已知作业时间的情况，或者能够估算执行时间的情况。
缺点：
- 无法预知作业时间：若无法准确知道进程的运行时间，可能会导致算法无法实施。
- 可能导致进程饿死：长作业可能一直被短作业所抢占，导致它永远得不到执行。

优先级调度 是根据进程的优先级来调度进程。每个进程都有一个优先级，系统根据优先级来决定执行顺序。

特点：
- 抢占式或非抢占式：如果是抢占式算法，当一个更高优先级的进程到达时，系统会暂停当前执行的进程并执行高优先级进程。
- 适应性强：可以根据进程的重要性设置不同的优先级。
缺点：
- 进程饿死：低优先级的进程可能永远无法获得CPU时间。
- 需要合理的优先级分配：如果优先级分配不合理，可能导致性能问题。

RR 是一种基于时间片的调度算法，每个进程被分配一个固定的时间片（time quantum），如果进程在时间片内没有完成，则被暂停，转到队列末尾，等待下一次执行。

特点：
- 抢占式：当一个进程的时间片用完时，系统会强制中断该进程，转而执行其他进程。
- 适用于时间共享系统，能保证所有进程轮流得到执行。
- 比较公平：每个进程都有机会获得CPU时间。
缺点：
- 如果时间片设置过长，会退化为FCFS。
- 如果时间片设置过短，频繁的上下文切换会增加系统开销，降低效率。

多级反馈队列调度 是一种结合了优先级调度和时间片轮转特点的调度算法。系统维护多个就绪队列，每个队列有不同的优先级。进程会根据执行情况在这些队列之间移动。

特点：
- 初期，进程会被分配到高优先级队列执行，若某个进程占用过多CPU时间，则会被调度到较低优先级队列。
- 进程在高优先级队列上执行时，分配较小的时间片；在低优先级队列上执行时，分配较大的时间片。
- 动态调整：进程的优先级会根据进程的行为动态调整。
优点：
- 能较好地平衡长作业和短作业的调度，避免了进程饿死的问题。
- 适应不同类型的作业，灵活性高。
缺点：
- 实现复杂。
- 如果没有合理的队列管理和策略，可能会导致性能瓶颈。

SRTF 是最短作业优先（SJF）的抢占式版本。在某个进程正在执行时，如果另一个进程的剩余执行时间更短，那么系统会抢占当前进程，优先执行剩余时间较短的进程。

公平分享调度 是一种基于进程之间资源公平分配的调度算法。系统将CPU时间分配给每个进程（或用户）按比例进行，确保每个用户或进程在总资源中获得公平的份额。

CFS 是Linux操作系统中的调度器，它通过维护一个“红黑树”来实现对进程的公平调度。CFS的目标是使所有进程的CPU时间尽可能平均。

特点：
- 基于时间片：每个进程有一个虚拟运行时间，CFS会根据这个时间来决定哪个进程下一次执行。
- 不使用固定的时间片，而是通过计算虚拟时间来进行动态调整。
- 适应性强，可以平衡低优先级和高优先级进程的调度。
优点：
- 非常适合现代多核处理器系统，能够在多核系统中高效地实现进程调度。
- 提供公平的CPU资源分配，能够动态调整进程优先级。
缺点：
- 相对较为复杂。

问答题【225/1053】说下你知道的调度算法