调度算法
最后更新于
这有帮助吗？
在进程的生命周期中，当进程从一个运行状态到另外一个状态变化的时候，就会触发一次调度。
就绪态 -> 运行态：当进程被创建时，就会进入就绪队列，操作系统会从就绪队列选择一个进程运行
运行态 -> 阻塞态：当进程发生 I/O 事件而阻塞时，操作系统必须从就绪队列中选择另外一个进程运行
运行态 -> 结束态：当进程退出结束后，操作系统得从就读队列中选择另外一个进程运行
根据如何处理时钟中断，把调度算法分为两类：
非抢占式调度算：挑选一个进程，让该进程运行到被阻塞，或者退出，才会调用另外一个进程，不理会时钟中断
抢占式调度算：挑选一个进程，让该进程只运行某段时间，如果该时段结束时，该进程仍在运行，则将其挂起，接着调度程序从就绪队列中挑选另外一个进程。这种抢占式调度处理，需要在时间间隔末端发生时钟终端，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。
原则一：为了提高 CPU 利用率，在这种发送 I/O 事件导致 CPU 空闲的情况，调度程序需要从就绪队列中选择一个进程来运行。
原则二：需要提高系统的吞吐率，调度程序要权衡长任务和短任务进程的运行完成数量。
原则三：如果进程的等待时间很长而运行时间很短，那周转时间就很长，这不是我们所期望的，调度程序应该避免这种情况发生。
原则四：就绪队列中进程的等待时间也是调度程序所需要考虑的原则。
原则五：对于交互式较强的应用，响应时间也是调度程序所需要考虑的原则。
针对上面的五种调度原则，总结成如下：
CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率
系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量
周转时间：周转时间是进程运行和阻塞时间总和，一个进程的周转时间越小越好
等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准
说白了，这么多调度原则，目的就是要使得进程要「快」。
单核 CPU 系统常见调度算法。
每次从就绪队列选择最先进入队列的进程，然后一直运行，知道进程退出或阻塞，才继续从队列中选择第一个进程进行运行。
对长作业有利，适用于 CPU 繁忙型作业的系统，不使用于 I/O 繁忙型作业的系统。
优先选择运行时间短的进程来运行。
容易造成长作业不断往后推，致使长作业长期不被运行。
权衡长作业和短作业，每次进行进程调度，先计算「响应比优先级，然后把「响应比优先级」最高的进程投入运行。
由公式：
如果两个进程『等待时间』相同，则『要求服务时间』越短，级别越高
如果两个进程『要求服务时间』相同，则『等待时间』越长，级别越高，兼顾了长作业进程
每个进程被分配一个时间段，称为时间片（Quantum），允许该进程在该时间段中运行。
如果时间片用完，进程还在运行，则将该进程挂起，并给 CPU 分配另一个进程
如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行分配
值得注意的是：
如果时间片太短，则会导致频繁的进程上下文切换，降低了 CPU 效率
如果时间片太长，又会导致短作业进程相应时间变长，同样降低了 CPU 效率
通常时间片设为 20ms~50ms。
从就绪队列选择优先级最高的进程进行运行。
静态优先级：进程创建时，优先级就已经确定，且保持不变
动态优先级：根据进程的动态变化调整优先级（如进程的运行时间增加，则降低优先级；如果等待时间增加，则提高优先级）
同样也有两种处理优先级的办法，非抢占式和抢占式：
非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程
抢占式：当就绪队列中出现优先级高的进程，则挂起当前进程，调度优先级高的进程运行
但也可能导致优先级低的进程永远不会运行。
多级反馈队列综合了「时间片轮转算法」和「最高优先级」算法。
多级表示多个队列，每个队列优先级从高到低，同时优先级越高时间片最短
反馈表示如果有新的进程进入优先级高的队列，立即停止正在运行的进程，转而运行优先级高的队列
工作原理：
设置多个队列，每个队列的优先级从高到低，同时优先级越高的时间片最短
新的进程会被放入第一个队列的末尾，按先来先服务的原则排队调度，如果在第一级队列规定的时间片没有运行完成，则将其转入第二级队列的末尾，以此类推
当较高优先级的队列为空，才调度较低优先级队列中的进程运行。如果进程运行时，有新进程进入较高优先级队列，则停止当前运行的进程并将其移入原队列末尾，接着让较高优先级的进程运行
可以看到，对于短作业，可以快速的在第一队列处理完成；而对于长作业，如果在第一队列运行不完，可以移入下一队列等待被执行，虽然等待的时间边长了，但是下一级队列也有更长时间片可以运行，该算法兼顾了长短作业，同时有较好的相应时间。
