4.1.1 长程调度
一个进程从创建、执行到结束需要经过以下三级调度：长程调度、中程调度和短程调度
本小节讲解长程调度。
1．概念
长程调度决定哪个作业或用户程序可以进入系统运行，因此又称为作业调度。长程调度它控制着系统的并发度：进入系统的进程越多系统的并发度就越高。
作业或用户程序一旦进入系统，就为该作业或用户程序创建进程，添加到队列中等待长程调度。
2．调度时机
内存中能同时容纳的进程数决定了系统的并发度。进程数越多，每个进程可以执行的时间就越短。长程调度可以限制系统的并发度。
当一个进程结束时，或处理器的空闲时间片超过了一定的阈值时，都可能启动长程调度程序。
3．调度策略
可以基于先来先服务的原则，或基于优先级等调度策略进行调度
中程调度是存储器管理中交换功能的一部分,又称交换调度。它决定内存和外存之间的数据交换，其功能包括：
（1）适时地将外存中哪些进程的哪些代码和哪些数据交换到内存，以满足进程执行的要求；
（2）适时地将内存中那些在近期内不再执行的进程的代码和数据交换到外存，以便给其它进程的执行留出更多的内存空间。
不同的存储管理方法有不同的中程调度策略和算法。我们在第 5 章详细讲述。
4.1.3 短程调度
一、概念
短程调度程序也叫分派程序、进程调度、低级调度，它将决定哪一个就绪进程将获得处理器。
短程调度的目的是按照一定的策略和方法将处理机分配给某个就绪进程并为该进程的执行准备环境。
二、调度的功能
1．记录系统中所有进程的执行情况；
2．选择占有处理机的进程——调度策略与算法；
3．进程上下文切换——保存正在执行进程的现场，为将要执行的进程准备现场；
4．处理机回收——进程被撤消后须回收被占用的处理机。
三、进程调度的时机
在下述时机可以进行进程调度：
1．正在执行中的进程执行完毕；
2．正在执行中的进程被阻塞；
3．分时系统中时间片用完；
4．执行完系统调用等系统程序后返回用户进程时；
5．更高优先级的进程处于就绪状态。
四、进程调度中的上下文切换
1．进程在其上下文所确定的环境中运行，当执行的进程发生改变或出现进程调度时，需要进行上下文切换。
2．上下文切换的内容
1)决定是否做或是否允许做上下文切换；
2)切换上下文——原则是不破坏原进程的上下文；
3)处理机切换。
短程调度（处理机调度）是决定哪一个就绪进程将获得处理器。只有获得处理器的进程才能运行。因此，短程调度确定了哪个进程在什么时刻可以运行。
在操作系统中，通过调度算法来实现调度。不同类型的操作系统其调度目标并不完全一样。
1．总体调度目标
（1）公平性：指相对公平地给每个进程分配资源。也即是，使每个进程都有在合理的时间内获得处理机的可能性，以防止进程饥饿。
（2）平衡性：指通过调度使计算机系统的资源能得到平衡而充分的使用，以提高整个系统的效率。例如，在系统中同时调度计算密集型和 I/O 密集型的进程，使处理机和 I/O 设备能够并行工作。
（3）实现策略：指在设计时制定的调度策略能够在实施时得到贯彻。
2．批处理系统调度目标
（1）吞吐量：指单位时间内完成的进程（作业）数。例如，每小时完成的作业数。系统的吞吐量越高越好。
（2）周转时间：指从进程创建（作业提交）到完成的全部时间。就每个进程（作业）来讲，周转时间越短越好。
（3）CPU 利用率：指单位时间内 CPU 占用时间的比例。CPU 利用率越高越好。
3．分时系统调度目标
（1）响应时间：指用户发出指令到获得系统响应所花的时间。例如，用户点击按钮开始到系统产生给出输出之间的时间。响应时间越短越好。
（2）合理性：指满足用户对进程（作业）执行的期望程度。例如，进程执行时间期望，系统使用费用的期望等。
4．实时系统调度目标
（1）及时性：指系统满足用户对系统响应或处理的时间限制程度。例如，要求实时数据采集系统在每隔 2 秒中采集和处理一组数据，系统能否满足。
（2）可预测性和稳定性：指能否提前预测可能出现的性能瓶颈。
4.2.2 批处理系统中的调度
一、调度算法
常见的短程调度算法包括以下几种。
1．先来先服务（FCFS，first come first service）
（1）算法思想
按照进程进入就绪队列的先后顺序来调度进程。获得处理机的进程，未遇到其他情况时，一直运行下去。系统只需具备一个先进先出的队列，这种方法是一种最常见策略，并且在没有其他信息时，也是一种最合理的策略。
（2）优点：实现简单。
（3）缺点：对那些执行时间较短的进程来说，将等待较长的时间，从而降低 CPU 的利用率。
（5）在实际操作系统中，FCFS 算法常常和其它的算法配合起来使用，例如，基于优先级的调度算法就是对具有同样优先级的进程采用 FCFS 算法。
2．轮转调度（RR，round robin）
（1）算法思想
将就绪进程按达到的先后次序插入就绪队列中，处理机取出就绪队列中的第一个进程，并赋予一个固定的执行时间片（如 100 毫秒），执行该进程。运行的进程，当未遇到任何阻塞时一直运行。如果在规定的时间片内进程运行结束，那么将处理机分配给就绪队列当前的第一进程；如果规定时间片用完而运行的进程未结束，那么剥夺当前进程占用的处理机，并将该进程置就绪状态放入就绪队列尾，同时将处理机分配给当前就绪队列的第一个进程。
（2）优点：实现较简单，只要是处于就绪队列中的进程，迟早总可以分得处理机投入运行。
（3）缺点：需要较长运行时间的进程要多次运行和放入就绪队列。
（4）轮转法只能用来调度分配那些可抢占资源。可抢占资源可以随时剥夺，而且可以将它们再分配给别的进程。CPU 是可抢占的资源的一种。但打印机等是不可抢占的资源。另外，时间片长度的选择是根据系统对响应时间的要求和就绪队列中所允许的最大进程数确定的。
3．多级反馈轮转法（RRMF，round robin with multiple feedback）
（1）算法一
1）把所有就绪进程按下述方法排成多个队列
● 新创建的与时间片用完的进程队列
● 发生 I/O 请求的队列
● 其它情况的队列
2）每个队列分配不同的时间片（如，t,2t,3t,……）
3）这些队列中轮流进行进程调度
（2）算法二
1）把所有就绪进程按下述方法排成 n 个队列
● 第 k 次被调度的进程时间片用完后被放入第((k+1) mod n)+1 个队列
● 新创建的进程放入第一个队列
2）每个队列分配不同的时间片（如，t,2t,3t,……）
3）依次调度第一个，第二个，……，第 n 个队列中的进程执行
4．优先级算法
（1）算法
1）为每个进程分配一个优先级，调度时总是调度优先级最高的进程执行。
2）当出现比当前正在执行的进程优先级更高的就绪进程时，调度该进程执行，原执行进程的状态转换为就绪。
（2）优先级确定方法
1）静态优先级的确定
● 用户指定作业的优先级，与之相关的进程有相同的优先级
● 系统进程比用户进程有更高的优先级
● 系统根据进程的类别设置优先级，如：I/O 繁忙类，CPU 繁忙类，I/O 与 CPU 均衡类，……
2） 动态优先级的确定
● 进程占有 CPU 时间越长，被阻塞后再次称为就绪状态时，优先级越低
● 就绪进程等待执行的时间越长，其优先级越高
二、调度算法评价
1．定性评价
（1）调度算法可靠性：是否会引起系统故障，上下文破坏等。
（2）调度算法简洁性：算法实现是否容易等。
2．定量评价
对调度算法的定量评价可以从 CPU 利用率、进程响应时间、进程在就绪队列中的等待时间与执行时间之比等角度来评价。
定量评价的难度在于：由于进程进入就绪队列的随机模型很难确定，而且进程上下文的切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的。一般情况下大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。有兴趣的同学可以参考相关的文献资料。
本章学习了操作系统分级调度的思想、调度目标及调度算法。特别针对短程调度，学习了调度的总目标以及不同类型操作系统调度的目标。所学习的处理机调度算法是一些主要算法，它们有不同的特征，适应不同的调度需求。
