计算机操作系统（汤小丹）--处理机调度-笔记
单道环境下,CPU利用率非常低,于是引入多道程序设计。
在多道程序环境下，主存中有多个进程，其数目往往多于处理机数目。这就要求系统能按照某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。
衡量调度的标准
不同的调度算法有各自不同的属性,侧重点是不一样的.
调度准则用于比较不同的调度算法.根据不同的调度准则进行比较,则得出的比较结果是不同的.
- CPU利用率:使CPU尽可能的忙碌
- 吞吐量（Throughput）：单位时间内运行完的进程数
- 周转时间(Turnaround time):从提交到运行结束的全部时间
- 等待时间:进程在就绪队列中等待调度的时间总和
- 响应时间:从进程提出请求到首次被响应的时间段[在分时系统环境下不是输出完结果的时间]
优化标准：最大的CPU利用率、最大的吞吐量、最短的周转时间、最短的等待时间、最短的响应时间。
处理机调度的层次
高级调度–作业调度
概念
调度对象是作业。
作业：是比程序更为广泛的概念，不仅包含了通常的程序和数据，而且应该还配有一份作业说明书，系统根据说明书来对程序的运行进行控制。
- 决定把外存输入井上处于作业后备队列的那些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。
- 在批处理系统中，作业是先驻留在外存的输入井上的，因此需要有作业调度。
- 在分时系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。
作业的状态
作业从进入到运行结束，一般需要经历“提交”、“后备”、“运行”和“完成”四个阶段。
低级调度–进程调度
- 决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。
- 是最基本的调度，任何OS都有进程调度。
- 低级调度由每秒可执行许多次的处理机调度程序(Scheduler)执行，处理机调度程序应常驻内存。
- 调度对象是进程（或者内核级线程）。在多批道处理、分时和实时三种类型的OS中都必须配置这种低级调度。
进程调度的功能
- 保存处理机的现场信息
- 按照某种算法选择进程
- 把处理器分配给进程
进程调度的三个基本机制
- 排队器：把系统中所有就绪程序按照一个方式排队，以便最快找到它
- 分派器：把进程调度程序所选定进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配给它。
- 上下文切换机制
进程调度方式
非抢占式方式（nonpreemptive）
把处理机分配给某进程后，便让其一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，不允许其他进程抢占已经分配出去的处理机。优点：实现简单、系统开销小，适用于大多数批处理系统环境
缺点：难以满足紧急任务的要求，不适用于实时、分时系统要求抢占式方式（Preemptive）
允许调度程序根据某个原则，去停止某个正在执行的进程，将处理机重新分配给另一个进程。需要基于一定的原则：
- 优先权原则
通常对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行 - 短作业（进程）优先原则
当到达的进程比正在执行的进程明显短的时候，将暂停当前长进程的执行，将处理机分配给新到的短作业，使之优先执行。 - 时间片原则
各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这个原则适用于分时系统
优点：可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是对响应时间有着严格要求的实时任务。
缺点：额外开销- 优先权原则
中级调度–中程调度
- 引入中级调度的目的是为了提高主存利用率和系统吞吐量
- 把暂时不能运行的进程调至外存上去等待，此时的状态就称为绪驻外存状态或者挂起状态。当这些进程重新又具备运行条件且内存又稍有空闲的时候，由中级调度来决定把外存上那些又具备运行条件的就绪程序重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。
- 中级调度实际上就是存储器管理中的对换功能。
总的三种调度方式：
在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是10~100ms便进行一次调度，因此称为短程调度。为避免进程调度占用过多的CPU时间，进程调度算法不宜太复杂。
作业调度往往发生在一个批处理运行完毕，退出系统，而需要重新调入一个批作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此称为长程调度。由于其运行频率较低，允许作业调度算法花费较多时间。
中级调度运行频率介于两者之间，因此称为中程调度。
调度队列模型
仅有进程调度的队列模型
系统可以把处于就绪状态的进程组织成栈、树或者一个无序链表，到底采用哪种形式，则与OS类型以及所采用的调度算法有关。例如分时系统通常用FIFO队列，按时间片轮转法运行。
具有作业调度和进程调度的调度队列模型
在多道批处理系统中，一般CPU管理需设置作业和进程两级调度。
模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程，并分配资源，将它排入内存进程就绪队列末尾。
该模型与上一个模型的主要区别是：
- 就绪队列的形式：由于批处理最常用的是最高优先权调度算法，相应的常用就绪队列的形式是优先权队列。
- 设置多个阻塞队列
具有进程调度和中级调度的队列模型
在具有虚拟存储器的分时系统中，一般采用具有进程调度和中级调度的模型
该模型比仅有进程调度模型增加了中级调度:增加了静止就绪队列和静止阻塞队列
同时具有三级调度的队列模型
通用OS同时支持批处理、分时和实时处理，一般采用具有三级调度的调度队列模型.
在OS引入中级调度后，人们可以把进程的状态分为内存就绪（表示进程在内存中就绪）和外存就绪（进程在外存中就绪），类似的阻塞状态也分成内存阻塞和外存阻塞，在中级调度的作用下又可以外存就绪转为内存就绪。
选择调度方式和调度算法的若干准则
- 面向用户准则
- 周转时间短：指作业从被提交给系统开始到作业完成为止的这段时间间隔。
- 响应时间快：提交请求到首次响应时间
- 截止时间的保证：必须开始执行的最迟时间或者必须完成的最迟时间
- 优先权准则：紧急作业得到处理
- 面向系统的准则：
- 系统吞吐量高：单位时间内系统完成作业数
- 处理机利用率好：
- 各类资源平衡利用
调度算法
根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和目标通常采用不同的算法。如：批处理系统中，为了保证为数众多的短作业，短作业优先算法；分时系统中，为了保证系统有合理的响应时间，采用轮转法进行调度。
先来先服务调度算法（FCFS）
- 先来先服务First-Come-First-Served:
最简单的调度算法
可用于作业或进程调度
算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程） - FCFS算法属于非抢占方式:一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。
- FCFS算法易于实现，表面上很公平，实际上有利于长作业，不利于短作业；有利于CPU繁忙型（科学计算），不利于I/O繁忙型（大多数事务）。
短进程（作业）优先调度算法
- Shortest-Job-First (SJF) Scheduling
根据每个作业下次要运行的估计时间，调度最短的作业 - SJF是最优的 – 对一组指定的进程而言，它给出了最短的平均等待时间
- 采用SJF有利于系统减少平均周转时间,提高系统吞吐量。
- 一般情况下SJF调度算法比FCFS调度算法的效率要高一些, 但实现相对要困难些。
缺点： - 有可能出现饥饿现象
例如，系统中有一个运行时间很长的作业JN，和几个运行时间小的作业，然后，不断地有运行时间小于JN的作业的到来，这样，作业JN就因得不到调度而饿死。 - 未完全考虑作业的紧迫程度
高优先权调度算法
静态优先权
静态优先权在进程创建时确定，且在整个生命期中保持不变。
确定进程优先权的依据有：
- 进程类型，通常系统进程的优先权高于一般用户进程的优先权
- 进程对资源的需求，如进程执行时间及内存需要少的进程应赋予较高的优先权；
- 根据用户要求，由用户的紧迫程度及用户所付费用的多少来确定进程的优先权。
系统中有两类进程，系统进程和用户进程。
系统进程的优先级比用户进程的优先级高，特别是某些系统进程，必须赋予它一种特权，当它需要处理机时，应尽快得到满足。例如，设备管理中的I/O进程便是如此。这不仅是为了保证I/O设备尽可能忙碌，以提高设备利用率，更主要的是为了避免由于响应不及时，造成信息的丢失。- 在用户进程中，I/O繁忙的进程应优先于CPU繁忙的进程，以保证CPU和I/O设备之间的并行操作。
- 在分时系统中，前台进程应优先于后台进程。
采用静态优先权时, 高优先权的进程可能导致一个低优先权的进程长时间甚至永远得不到CPU。
或者那个低优先权的进程最终得到运行
或者某一时刻系统崩溃从而使所有低优先权的进程得不到运行。
动态优先权
动态优先权是指进程的优先权可以随进程的推进而改变，以便获得更好的调度性能
- 改变优先权的因素
进程的等待时间
已使用处理机的时间
资源使用情况
高响应比优先调度算法
折衷了短作业和作业到达的先后次序，HRRN算法实际上是FCFS算法和SJF算法的折衷
在每次选择作业投入运行时，先计算后备作业队列中每个作业的响应比RP,然后选择其值最大的作业投入运行。
RP值定义为：
RP＝（已等待时间＋要求运行时间）／要求运行时间
＝1＋已等待时间／要求运行时间。
优点：
等待时间相同，则SJF；
要求的服务时间相同，则FCFS；
长作业的优先级随着等待时间的增加而提高，不会出现得不到响应的情况。
缺点:
作业调度程序要统计作业的等待时间，作浮点运算（这是系统程序最忌讳的）浪费大量的计算时间。
基于时间片的轮转调度算法（Round-Robin）
分时系统为了保证响应用户的请求，必须采用基于时间片的轮转式进程调度算法。早期采用的是简单的时间片轮转法；90年代后采用多级反馈队列调度算法。
时间片轮转法
- 每个进程将得到小单位的CPU时间[时间片]，通常为10-100毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾
- 假定就绪队列中有n个进程、时间量为q, 则每个进程每次得到1/n的、不超过q单位的成块CPU时间，没有任何一个进程的等待时间会超过(n-1) q单位
- 一般,RR的平均周转时间比SJF长，但响应时间要短一些）.
- q相对于切换上下文的时间而言应该足够长，否则将导致系统开销过大
- 一组进程的平均周转时间并不一定随着时间片的增大而降低。一般来说，如果大多数（80%）进程能在一个时间片内完成，就会改善平均周转时间
多级反馈队列调度算法
按进程的属性来分类，如进程的类型、优先权、占用内存的多少,每类进程组成一个就绪队列，每个进程固定地处于某一个队列
就绪队列分为:前台[交互式]， 后台[批处理]
每个队列有自己的调度算法：前台–RR；后台–FCFS
调度须在队列间进行:
- 一种方案：不同队列间的调度为基于固定优先权的抢占式调度
固定优先级调度，即前台运行完后再运行后台。有可能产生饥饿. - 另一种方案：队列间采用时间片调度
给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如，80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度
- 存在多个就绪队列，具有不同的优先级，各自按时间片轮转法调度
- 各个就绪队列中时间片的大小各不相同，优先级越高的队列时间片越小。
- 当一个进程执行完一个完整的时间片后被抢占CPU，被抢占的进程优先级降低一级而进入下级就绪队列，如此继续，直至降到进程的基本优先级。而一个进程从阻塞态变为就绪态时要提高优先级
应用：
终端型作业
短批处理作业
长批处理作业
对几种调度算法的评述
- 时间片轮转调度算法：常用于分时系统的调度算法，只适用于一般实时信息处理系统，而不能用于实时要求严格的实时控制系统。
- 非抢占的优先级调度算法：常用于多道批处理系统的调度算法，也可用于实时要求不太严格的实时控制系统。
- 基于时钟中断抢占的优先级调度算法：用于大多数的实时系统中。
立即抢占的优先级调度算法：适用于实时要求比较严格的实时控制系统。
实时调度
- 实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。
- 实时处理任务要求计算机在用户允许的时限范围内给出响应信号。
- 实现:首先,系统要实现基于优先级的调度,实时进程须具有最高优先级,且不能随着时间的推移降低优先级; 其次,调度延迟必须很小.
代表性的实时调度算法：
最早截止任务优先算法(EDF: Earliest Deadline First)：以满足用户要求时限为调度原则。
处理开始时限（开始截止时间）
处理结束时限（完成截止时间）
最短周期优先算法(RMS:rate monotonic scheduling)：广泛用于多周期性实时处理。其基本原理是周期越长的任务优先级越低。
线程调度
用户级线程要运行的话,需通过LWP映射到某个内核级线程
局部调度– 线程库决定将哪个线程连至有效的LWP
全局调度 – 内核决定下一个运行的内核线程
各种操作系统采用的调度算法例子
Solaris Scheduling
- 采用基于优先级的进程调度
- 按调度的优先级定义了4类:实时、系统、分时、交互，对每一类有不同的优先级和调度算法
- 默认的调度类是分时。分时调度动态地改变线程的优先级，赋予不同的时间片长度
- 分时和交互采用相同的调度策略,但交互式线程有较高的优先级
- 系统类的优先级是不会改变的,其调度策略是不分时的
- 实时类具有最高的优先级
Windows XP Scheduling
- 基于优级的,可抢占的调度算法
- 线程按时间片来使用CPU
- 32个优先级来确定线程的执行顺序，优先级相同的线程按RR调度
- 非实时优先级是动态调整的
线程从等待操作被唤醒时,提高其优先级(如I/O结束)
延长时间片:给前台任务更长的时间片,以提高响应速度 - 实时优先级是固定不变的
Linux Scheduling
- Linux提供二种进程调度算法
分时:实现进程间的公平可抢占调度
实时:按优先级调度
java线程调度
- JVM使用基于优先级的抢占式调度算法
- 对多个相同优先级的线程将使用FIFO队列来调度
