目录
前言
重点
一、处理机调度的层次 和调度算法的目标？
处理机调度的层次
1.高级调度（作业调度）
- 高级调度(High Level Scheduling)又称为作业调度或长程调度(LongTerm Scheduling)，其 主要功能是OS根据某种算法，把外存上处于后备队列中的那些作业调入内存，并执行它们。
- 高级调度的调度对象是作业。
2.低级调度（进程调度，也包括线程调度）
- 低级调度（Low Level Scheduling）为进程调度，也叫短程调度（Short-Term Scheduling）。
- 它用来决定就绪队列中的哪个进程/(内核)级线程应获得处理机，然后再由分派程序(Dispatcher)把处理机分配给该进程的具体操作。
- 进程调度是最基本的一种调度，在除了单道系统的OS中，都必须配置这级调度
3.中级调度（交换调度/内存调度）
- 中级调度实际上就是存储器管理中的对/交换功能 ，因此中级调度又被称为对/交换(Swap)调度。也叫内存调度。
- 中级调度又称中程调度(Medium-Term Scheduling)。引入的主要目的是为了提高内存利用率和系统吞吐量。
- 把那些暂时不能运行的进程调至外存上去等待，当它们重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把哪些外存就绪进程重新调入内存，并修改其状态，挂在就绪队列上等待调度
处理机调度算法的目标
?1.衡量调度策略的指标
- 周转时间 一个作业从提交给系统后到该作业的结果返回给用户所需要的时间。 由执行时间和等待（2调度+1 I/O）时间组成。
- 平均周转时间 系统内所有作业的周转时间的平均数。
- 带权周转时间 周转时间Ti与服务时间Tsi的比。
- 平均带权周转时间 系统内所有作业的平均带权周转时间的平均数。
- 吞吐量 指在给定的时间内，系统所完成的总工作量。
- 设备利用率 主要指I/O设备的使用情况。
- 响应时间 指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。 包括：输入时间；处理时间；输出时间。
- CPU利用率? ?
?
2. 共同目标
(1) 资源利用率。为提高系统资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，资源利用率要高。
(2) 公平性。公平性是指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。但特殊问题区别对待。
(3) 平衡性。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。
(4) 策略强制执行。对所制订的策略（其中包括安全策略），只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。
3. 批处理系统目标
（1） 平均周转时间短 和 平均带权周转时间短。
（2）系统吞吐量大。
（3）处理机利用率高。
4. 分时系统目标
(1) 响应时间快。 让用户感觉很快。
(2) 均衡性。 让系统的响应时间与用户所请求服务的复杂性相适应。 让每个用户都感觉很快
5. 实时系统目标
(1) 截止时间的保证。 在指定时间开始或到规定时间完成。
(2) 可预测性。 避免不可知性，提高实时性，保证实时任务的完成。
二、作业与作业调度
- 在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。
- 操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。
- 再由调度程序将其从外存调入内存。
先来先服务调度算法
- 每次都选择来的最早者执行，是一种最简单的调度算法。既可用于作业调度，也可用于进程调度。
- 用于作业调度时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业并执行之。
- 用于进程调度时，则每次调度都是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。
- 有利于长作业(进程)，而不利于短作业(进程)?
短作业/进程优先调度算法?
- 短作业/进程优先调度算法SJF/ SPF，是指对短作业或短进程优先调度的算法。可分别用于作业调度和进程调度。
- 用于作业调度时，是从后备队列中选择一个或若干个估计运行时间最短的作业。
- 用于进程调度时，则是从就绪队列中选出一估计运行时间最短的进程。
高优先权优先调度算法??
1.优先级调度算法（PSA：Priority-Scheduling Algorithm）
作业的优先级：
对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。 对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。
- 在优先级调度算法中，则是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。
- 这样就可以保证紧迫性作业优先运行。 优先级调度算法可作为作业调度算法，也可作为进程调度算法。
- 当把该算法用于作业调度 时，系统是从后备队列中选择若干个优先级最高的作业装入内存。
2.高响应比优先调度算法（HRRN： Highest Response Ratio Next）?
响应比定义：
高响应比优先级的可描述为：以响应比作为动态的优先级，谁的优先级高调度谁执行。
三、进 程 调 度
- 进程调度是OS中必不可少的一种调度。
- 在三种类型的OS中，都无一例外地配置了进程调度。
- 此外，它也是对系统性能影响最大的一种处理机调度，相应的，有关进程调度的算法也较多。
进程调度的任务、机制和方式
1. 进程调度的任务
(1) 保存处理机的现场信息。
(2) 按某种算法选取进程。
(3) 把处理器分配给进程。
2.进程调度机制
为了实现进程调度，在进程调度机制中，应具有如下三个基本部分。
(1) 排队器。 (2) 分派器。 (3) 上下文切换器
(1)排队器 将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能快速地找到它。
(2)分派器(分派程序) 把由进程调度程序所选定的进程，从就绪队列中取出，然后进行上下文切换，将处理机分配给它。
(3)上下文切换器 当对处理机进行切换时，会发生两对上下文切换操作。在第一对上下文切换时，OS将保存当前进程的上下文，而装入分派程序的上下文，让分派程序运行；在第二对时，移出分派程序，恢复新选进程的现场信息，将处理机分配给它。
?3.进程调度方式
1) 非抢占方式
- 一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞，决不允许某进程抢占已经分配出去的处理机。
- 优点是实现简单、系统开销小，适用于大多数的批处理系统环境，但它难以满足紧急任务的要求。
- 在要求比较严格的实时系统中，不宜采用
2) 抢占方式
抢占方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
抢占的原则有:
(1)优先权原则。允许优先权高的新到进程抢占当前进程的处理机。
(2)短作业(进程)优先原则。
(3)时间片原则。各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。
多级反馈队列调度算法
- 根据不同情况，设置不同的就绪队列。当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及被创建之后，将进入不同的就绪队列。
- 每个队列按FCFS原则排列，各队列之间的进程赋予不同的优先级，但同一队列内进程享有相同优先级。
?多级反馈队列调度算法的实施过程
(1) 设置多个就绪队列。并为各个队列赋予不同的优先级。优先级越高时间片越短。
(2) 每个队列采用FCFS算法。当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便结束；否则该进程转入下一队列末尾； 如此等等…。
(3) 按队列优先级调度。调度程序首先调度高优先级运行。当前一队列空闲时，则调度下一队列中的进程运行；如果处理机正在当前某队列服务时，又有新进程进入前面任何队列，则按(1)(2)的描述进行，等到达该队列时加入当前队列的末尾，把处理机分配给新到的高优先权进程。
