3.1处理机调度的层次和调度算法的目标
3.1.1 处理机的调度层次
3.1.2 处理机调度算法的目标
1．面向用户的准则
(1) 周转时间短。
周转时间：从作业被提交给系统开始，到作业完成的时间间隔。
2) 响应时间快。
是分时系统中进程调度算法选择重要准则之一。
响应时间：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。
(3) 截止时间的保证。
是选择实时调度算法的重要准则。
(4) 优先权准则。
优先权+抢占式调度
2．面向系统的准则
(1) 系统吞吐量高。
吞吐量：单位时间内系统所完成的作业数。
是选择批处理作业调度的重要准则。
(2) 处理机利用率好。
(3) 各类资源的平衡利用。
在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外存和I/O设备等。
3. 2 作业与作业调度
3.2.1批处理系统中的作业
1．作业和作业步
(1) 作业(Job)：程序和数据+作业说明书。
作业说明书由作业控制语言编写，随同作业一起提交给系统
(2) 作业步(JobStep)：
每个作业分成若干个相对独立，又相互关联的顺序加工步骤，每一个加工步骤称为一个作业步。
作业可分成三个作业步：
①“编译”:源程序编译后产生若干个目标程序段；
②“连结装配”:将多个目标程序段装配成目标程序；
③“运行”:将可执行目标程序读入内存运行；
(3) 作业流：若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。
2．作业控制块JCB(JobControl Block)
1个作业设置1个JCB，其中保存了系统对作业进行管理和调度所需的全部信息，是作业在系统中存在的标志。
JCB中所包含的内容因系统而异，通常包含：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。
3．作业调度/接纳调度
按照一定的算法从外存的后备队列中选取某些作业调入内存，并为之创建进程、分配必要的资源。
系统在选择作业调度算法时，既应考虑用户的要求，又能确保系统具有较高的效率。
每次执行作业调度时，都须做出以下两个决定：
1) 决定接纳多少个作业
取决于多道程序度。不能太多也不能太少。
多道程序度的确定应根据系统的规模和运行速度等。
2) 决定接纳哪些作业
应将哪些作业从外存调入内存，取决于所采用的调度算法。
常用作业调度算法：
FCFS调度算法；
SCF调度算法；
基于作业优先级的调度算法；
“响应比高者优先” 调度算法。
分时系统、实时系统中不需要作业调度。
3.2.3 先来先服务和短作业优先调度算法
1．先来先服务调度算法
先来先服务(FCFS):最简单的调度算法，既可用于作业调度，也可用于进程调度。
例：四个作业（进程）按先后顺序到达，已知要求服务的时间，求各自的周转时间及带权周转时间
2．短作业(进程)优先调度算法
SJ(P)F算法：既用于作业调度也用于进程调度。
例：有五个进程A、B、C、D、E，它们到达的时间分别是0、1、2、3和4，所要求的服务时间分别是4、3、5、2和4，计算每个进程的周转时间和带权周转时间。
并将SJ(P)F算法与FCFS算法做对比。
结果分析：
1)采用SJ(P)F算法，短作业D周转时间由原来的(用FCFS算法时)11降为3；而平均带权周转时间从5.5降到1.5。
2)系统平均周转时间由9变为8，平均带权周转时间由2.8变为2.1。
结论：采用SJF调度算法，系统不论是平均周转时间还是平均带权周转时间，都有较明显的改善，SJF能有效地降低作业的平均等待时间提高系统吞吐量。
3.2.4 优先级调度算法和高响应比优先调度算法
1．优先权调度算法(HPF)的类型
为了照顾紧迫型作业。
既是作业调度算法，也是进程调度算法。
该算法又可进一步分成如下两种：
1) 非抢占式优先权算法
一旦分配处理机不允许剥夺。每次调度都找优先权最高的进程（作业）。
主要用于批处理系统中和某些对实时性要求不严的实时系统中。
2) 抢占式优先权调度算法
2．高响应比优先调度算法（动态优先权）
1)若等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
(2)当要求服务的时间相同时，等待时间愈长，其优先权愈高，因而实现是先来先服务。
(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。
