一、基本概念
- 长程调度：新作业提交时，决定是否将其送入内存，成为一个进程。
- 中程调度：决定把哪些进程在内存与磁盘间交换。
-
短程调度：决定将CPU分配给哪个就绪进程。
三种调度影响进程的状态转换：
二、长程调度
-
在
批处理系统或OS的批处理部分
中，新提交的作业放在磁盘的后备作业队列中，
长程调度选择某些作业送入内存并创建。
-
何时长程调度？
根据
系统并发度决定
，
当老进程结束或CPU空闲超过阈值时
，启动长程调度。 -
到底哪个作业？
根据 先来先服务，优先级，预计时间，组合CPU密集型和I/O密集型、组合不同I/O需求的作业等。 -
注意：
在分时系统中，不需要长程调度。OS总是立即接受用户的交互请求并创建进程，直至系统饱和。
三、中程调度
-
何时长程调度？
与长程调度类似，
系统并发度决定中程调度的时机
。 -
需要考虑换入进程和换出进程的内存空间长度。
四、短程调度
-
何时长程调度？
当前运行进程的时间片用完、阻塞、被抢占时，启动短程调度。 - 调度频繁（毫秒级） = 》 执行速度必须很快。
4.1短程调度准则
-
面向用户的性能指标：对每个进程计算的指标
-
周转时间
：
从作业提交到完成的时间间隔，包括：服务时间
（运行态CPU执行）
+等待时间
（包括后备态等待进入内存、阻塞态等待资源、就绪态等待CPU）。
适合批处理作业。
-
响应时间
：从提交请求到开始响应。适合
分时（交互）
进程。 -
最后期限
：进程完成的截止期限。
适合实时进程。
-
归一化周转时间（带权周转时间）
：周转时间/服务时间。≥1
-
-
面向系统的性能指标：
-
吞吐量
：单位时间内完成的进程个数。 -
处理器利用率
：CPU忙的时间比例,
=工作时间/总运行时间
。
当用户系统和实时系统不看重该指标。
-
4.2调度方式
–
非抢占式：
当前进程一直运行，直至其终止或阻塞时，才再次分配CPU。
–
抢占式：
当其时间片结束或有更高级进程就绪时，将正运行进程转为就绪，再次分配CPU。
4.3选择调度策略
本文的调度算法有：先来先服务（FCFS）、轮转（RR）、最短进程优先（SPN）、最短剩余时间优先（SRT）、最高响应比优先（HRRN）、多级反馈。
-
先来先服务（FCFS）
调度最先进入后备队列/就绪队列的作业/进程，直至运行完或阻塞时，在重新调度。（非抢占式）
-
轮转
（RR）
轮转RR：各进程按提交顺序排成就绪队列，然后按次占用处理机，运行某一时间片。时间片完则排入就绪队列尾。（抢占式）（不利于I/O密集型进程）-
RR的平均周转时间可能较高，但是响应时间更短。
-
时间片的长度：关键参数
- 时间片q太大 =》 相当于FIFS，相应慢。
- 时间片q太小 =》 上下文切换频繁，开销大。
- 时间片应略大于一次典型的交互所需要的时间。
-
-
最短进程优先（SPN）
最短进程优先SPN:调度CPU执行时间预期最短的进程；直至运行完或阻塞时，重新调度。有利于短进程，不利于长进程及紧迫任务。（非抢占式）
通常，进程是“CPU执行和I/O”不断交替的过程，SPN的困难在于：如何预测下一CPU用时长度。（常用：指数平均法）
-
最短剩余时间（SRT）
新进程到达时
，若新进程的预计运行时间比
当前进程的剩余运行时间
更短，则抢占当前进程。（抢占式）
-
最高响应比优先
综合了FCFS和SPN算法。（非抢占式）- 当前进程完成或阻塞时发生调度。每次调度前，计算所有就绪进程的响应比，高者优先。
-
实际上，响应比就是一个进程在某一时刻的“归一化周转时间”（即带权周转时间）。
-
反馈
-
基于
时间片的抢占+动态优先级调度
。（抢占式） - 同一队列内进程按FCFS调度，但末级队列按轮转法调度。
- 当上级队列均无进程就绪时，才调度本级队列内进程；
-
实用，能较好地
满足交互型进程、短进程、长进程的要求
-
基于
-
优先权调度
-
调度优先级高的进程。就绪队列中进程按优先级 递减排列，每次调度高级队列的队首进程。
-
可抢占：新到达的高级进程立即抢占当前进程。
-
静态优先权
：创建进程时确定优先级，保持不变。 - 问题：低优先级进程可能饥饿Starvation。
-
-
动态优先权
：创建进程时赋予进程一个优先权初 值，但随着进程的等待时间延长，其优先级会升高 (称为老化Aging )；随着CPU执行时间的延长，其 优先级会降低