所谓单处理器调度，指的是单个处理器上的调度。主要是单处理器上多道程序设计系统的进程调度，多道程序设计系统中，内存可以同时驻留多个进程
调度类型和进程状态转换：
长程调度决定哪一个程序可以进入系统中处理，因此控制着系统的并发度
在批处理系统或者操作系统的批处理部分，新提交的作业被发生到磁盘，并保存在一个批处理队列中。在长程调度程序运行的时候，从队列中创建相应的进程。这里涉及两个决策：
- 调度程序决定何时操作系统接纳一个进程或者多个进程
- 调度程序决定接收哪个作业或哪些作业，并将其转变成进程
长程调度执行频率较低，并且仅仅是粗略地决定是否接受新进程及接受哪一个
该章剩余内容主要关注短程调度，即处理器选择一个进程执行时的调度决策。短程调度执行得最频繁，并且精确地决定下一次执行哪个进程
调度算法的设计需要考虑如下方面（以下为从一种维度的划分）：
- 面向用户的准则：延迟（侧重于用户）
- 面向系统的准则：效果、利用率、吞吐量（侧重于系统）
- 每个进程被指定一个优先级，调度程序总是优先选择具有较高优先级的进程
- 低优先级进程可能饥饿
- 周转时间：等待时间 + 服务时间
- 归一化周转时间：周转时间/服务时间
1）先来先服务(FCFS)：
- 非抢占
- 对短进程不利（相对于I/O密集型的进程，更利于处CPU密集型的进程）；一种改进是与优先级结合，每个优先级一个队列，同一队列内部使用FCFS
2）轮转(时间片)：
- 抢占
- 以时间片为周期产生时钟中断，切换运行
- 主要设计问题是时间片的长度，太短时间片会带来频繁的进程上下文切换开销。时间片过长(比最长进程还长)，算法就退化成了FCFS
3）最短进程优先(SPN)：
- 非抢占
- 每次调度选择(所需总)处理时间最短的进程。可能饥饿长进程
- 难点在于需要估计每个进程所需要的处理时间
4）最短剩余时间(SRT)：
- 抢占
- 每次选择剩余处理时间最少的进程，可能饥饿长进程
- 也需要估计每个进程所需的处理时间。同时，维护过去的服务时间也会增加开销
5）最高响应比(HRRN)：
- 非抢占
- 调度选择归一化周转时间最大的进程，归一化时间越大说明进程“年龄”越大。当偏向短作业时（小分母产生大比值），长进程由于得不到服务，等待的时间不断增加，从而增大了比值，最终在竞争中可以胜出
- 同样需要预估每个进程所需的处理时间
6）反馈法：
- 抢占
- 反馈法为了解决SPN、SPT和HRRN必须预估进程所需处理时间的问题(不能获得剩余执行时间就关注已经执行了的时间)。通过处罚运行时间较长进程的方法来偏向短进程。进程每被抢占一次(说明进程还未运行完，可能是个长进程)，就移入更低优先级的队列。在这种机制下，短进程在降级过多前就能运行完，长进程会一直降级，如果已经处于最低级队列，则再次被抢占后返回该队列。
- 这种方法的问题是长进程的周转时间可能惊人的增加，导致饥饿，一种方法是可以增加低优先级队列中进程运行的时间片，但仍可能饥饿，还有一种方法是如果在低级队列中时间过长，提升到高优先级队列中
调度策略对比总结：
性能比较
调度策略的性能是选择调度策略的一个关键因素。但是由于相关的性能取决于各种各样的因素，包括各种进程的服务时间分布、调度的效率、上下文切换机制、I/O请求的本质和I/O子系统的性能，因而不可能得到明确的比较结果
给出如下进程以及到达时间和服务时间：
使用各种调度策略：