第三章 处理机调度与死锁
3.1处理机调度的层次
在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机
的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利
用率及改善系统性能(吞吐量、响应时间)，在很大程度上取决于处理机调度性能的好坏，因
而，处理机调度便成为操作系统设计的中心问题之一。
3.1.1 高级调度
高级调度又称为作业调度或长程调度，主要功能是：根据某种算法，把外存上处于后备队列中的那些作业调入内存
作业和作业步
(1) 作业。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据， 而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
(2) 作业步。通常，在作业运行期间，每个作业都必须经过若干个相对独立， 又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步， 各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。
(3)作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。
作业控制块 JCB
进程控制块是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在 JCB 中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、 要求内存大小、要求 I/O 设备的类型和数量等)、进入系统时间、开始处理时间、作业完成 时间、作业退出时间、资源使用情况等。
每当作业进入系统时，系统便为每个作业建立一个 JCB，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入
内存。在作业运行期间，系统就按照 JCB 中的信息对作业进行控制。当一个作业执行结束
进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。
作业调度
作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建
进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也 把作业调度称为接纳调度。
对用户而言，总希望自己作业的周转时间尽可能的少，最好周转时间就等于作业的执行时间。然而对系统来说，则希望作业的平均周转时间尽可能少，有利于提高 CPU 的利用
率和系统的吞吐量。为此，每个系统在选择作业调度算法时，既应考虑用户的要求，又能
确保系统具有较高的效率。在每次执行作业调度时，都须做出以下两个决定。
1) 决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多道程序度， 即允许多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。
2) 决定接纳哪些作业 应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比高者优先”的调度算法。
在批处理系统中，作业进入系统后，总是先驻留在外存的后备队列上，因此需要有作业调度的过程，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都是被直接送入内存的，因而无需再配置上述的作业调度机制，但也需要有某些限制性措施来限制进入系统的用户数。
3.1.2 低级调度
通常也把低级调度称为 进程调度或短程调度，它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的 OS 中，都必须配置这级调度。
低级调度的功能
(1) 保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。
(2) 按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。
(3) 把处理器分配给进程。由分派程序把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。
进程调度中的三个基本机制
(1) 排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地找到它。
(2) 分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配给它。
(3) 上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。在第一对上下文切换时，操作系统将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行；在第二对上下文切换时，将移出分派程序，而把新选进程的 CPU 现场信息装入到处理机的各个相应寄存器中。
上下文切换将花去不少的处理机时间，即使是现代计算机，每一次上下文切换大约需要花费几毫秒的时间，该时间大约可执行上千条指令。为此，现在已有通过硬件(采用两组或多组寄存器)的方法来减少上下文切换的时间。一组寄存器供处理机在系统态时使用，另一组寄存器供应用程序使用。在这种条件下的上下文切换只需改变指针，使其指向当前寄存器组即可。
进程调度方式
（1）非抢占方式
在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。
在采用非抢占调度方式时，可能引起进程调度的因素可归结为如下几个：
(1) 正在执行的进程执行完毕，或因发生某事件而不能再继续执行；
(2) 执行中的进程因提出 I/O 请求而暂停执行；
(3) 在进程通信或同步过程中执行了某种原语操作，如 P 操作(wait 操作)、Block 原语、 Wakeup 原语等。 这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但 它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求 比较严格的实时系统中，不宜采用这种调度方式。
（2）抢占方式(Preemptive Mode)
这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占方式的优点是，可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的 实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。抢占调度方式是基于一定原则的，主要有如下几条：
(1) 优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到 达时，如果其优先权比正在执行进程的优先权高，便停止正在执行(当前)的进程，将处理机分配给优先权高的新到的进程，使之执行；或者说，允许优先权高的新到进程抢占当前进
程的处理机。
(2) 短作业(进程)优先原则。当新到达的作业(进程)比正在执行的作业(进程)明显的短时，将暂停当前长作业(进程)的执行，将处理机分配给新到的短作业(进程)，使之优先执行；或者说，短作业(进程)可以抢占当前较长作业(进程)的处理机。
(3) 时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处理系统。
3.1.3 中级调度
中级调度又称中程调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能。
在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是 10～100 ms 便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的 CPU 时间，进程调
度算法不宜太复杂。作业调度往往是发生在一个(批)作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。
3.2 调度队列模型和调度准则
3.2.1 调度队列模型
前面所介绍的高级调度、低级调度以及中级调度，都将涉及到作业或进程的队列，由 此可以形成如下三种类型的调度队列模型。
仅有进程调度的调度队列模型
在分时系统中，通常仅设置了进程调度，用户键入的命令和数据都直接送入内存。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，至于到底采用其中哪种形式，则与 OS 类型和所采用的调度算法有关。
每个进程在执行时都可能出现以下三种情况：
(1) 任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态； (2) 任务在本次分得的时间片内尚未完成，OS 便将该任务再放入就绪队列的末尾；
(3) 在执行期间，进程因为某事件而被阻塞后，被 OS 放入阻塞队列。
图 3-1 示出了仅具有进程调度的调度队列模型。
具有高级和低级调度的调度队列模型
在批处理系统中，不仅需要进程调度，而且还需有作业调度，由后者按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。
图 3-2 示 出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。
(1) 就绪队列的形式。在批处理系统中，最常用的是最高优先权优先调度算法，相应地， 最常用的就绪队列形式是优先权队列。进程在进入优先级队列时，根据其优先权的高低， 被插入具有相应优先权的位置上，这样，调度程序总是把处理机分配给就绪队列中的队首 进程。在最高优先权优先的调度算法中，也可采用无序链表方式，即每次把新到的进程挂在链尾，而调度程序每次调度时，是依次比较该链中各进程的优先权，从中找出优先权最高的进程，将之从链中摘下，并把处理机分配给它。显然，无序链表方式与优先权队列相 比，这种方式的调度效率较低。
(2) 设置多个阻塞队列。对于小型系统，可以只设置一个阻塞队列；但当系统较大时， 若仍只有一个阻塞队列，其长度必然会很长，队列中的进程数可以达到数百个，这将严重影响对阻塞队列操作的效率。故在大、中型系统中通常都设置了若干个阻塞队列，每个队列对应于某一种进程阻塞事件。
同时具有三级调度的调度队列模型
当在 OS 中引入中级调度后，人们可把进程的就绪状态分为内存就绪和外存就绪。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。
图 3-3 示出了 具有三级调度的调度队列模型。
3.2.2 选择调度方式和调度算法的若干准则
- 面向用户的准则
(1) 周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：
作业在外存后备队列上等待 (作业)调度的时间，
进程在就绪队列上等待进程调度的时间，
进程在 CPU 上执行的时间，
进程等待 I/O 操作完成的时间。
其中的后三项在一个作业的整个处理过程中可能会发生多次。
对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。
平均周转时间描述：
作业的周转时间 T 与系统为它提供服务的时间 T s 之比，即 W = T/Ts ，称为带权周转时间，
平均带权周转时间：
(2) 响应时间快。常把响应时间的长短用来评价分时系统的性能，这是选择分时系统中进程调度算法的重要准则之一。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。 它包括三部分时间：
从键盘输入的请求信息传送到处理机的时间，
处理机对请求信息进行处理的时间，
将所形成的响应信息回送到终端显示器的时间。
(3) 截止时间的保证。这是评价实时系统性能的重要指标，因而是选择实时调度算法的 重要准则。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预 料的后果。
(4) 优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则， 以便让某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢占式调度 方式，才能保证紧急作业得到及时处理。
面向系统的准则
(1) 系统吞吐量高。这是用于评价批处理系统性能的另一个重要指标，因而是选择批处理作业调度的重要准则。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度具有密切关系。对于大型作业，一般吞吐量约为每小时一道作业；对于中、小型作业，其吞吐量则可能达到数十道作业之多。作业调度的方式和算法对吞吐量的大小也将产生较大影响。事实上，对于同一批作业，若采用了较好的调度方式和算法， 则可显著地提高系统的吞吐量。
(2) 处理机利用率好。对于大、中型多用户系统，由于 CPU 价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法对处理机的利用率起 着十分重要的作用。在实际系统中，CPU 的利用率一般在 40%(系统负荷较轻)到 90%之间。 在大、中型系统中，在选择调度方式和算法时，应考虑到这一准则。但对于单用户微机或 某些实时系统，则此准则就不那么重要了。
(3) 各类资源的平衡利用。在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外存和 I/O 设备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。 但对于微型机和某些实时系统而言，该准则并不 重要。
3.3 调度算法
3.2.1 先来先服务和短作业（进程）优先调度算法
先来先服务调度算法 FCSF
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用 FCFS 算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件 而阻塞后才放弃处理机。
FCFS 算法比较有利于长作业(进程)，而不利于短作业(进程)。
下表列出了 A、B、C、 D 四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间， 并计算出各自的周转时间和带权周转时间。
短作业（进程）优先调度算法SJ§F
短作业(进程)优先调度算法 SJ§F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从 就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直 执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
为了和 FCFS 调度算法进行比较，我们仍利用 FCFS 算法中所使用的实例，并改用 SJ§F 算法重新调度，再进行性能分析。由图 3-4 中的(a)和(b)可以看出，采用 SJ§F 算法后，不 论是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业 D，其周 转时间由原来的(用 FCFS 算法时)11 降为 3；而平均带权周转时间是从 5.5 降到 1.5。这说明 SJF 调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
SJ§F 调度算法也存在不容忽视的缺点：
(1) 该算法对长作业不利，如作业 C 的周转时间由 10 增至 16，其带权周转时间由 2 增 至 3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序 总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。
(2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
(3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能 会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先 调度。
======第三章处理机调度与死锁======（2）https://developer.aliyun.com/article/1415803?spm=a2c6h.13148508.setting.32.188b4f0evtcvhF
