前言
关于操作系统，
CSDN有很多的优秀博客。
在这里，
本文摘取其他博客内容，
并附上相关链接，
如有侵权，
联系删除，
仅供学习交流使用
推荐
实验和练习
第三章 进程调度和锁
前言
在多道程序环境下，内存中存在着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地将处理机分配给处于就绪状态的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。对于大型系统运行时的性能，如系统吞吐量、资源利用率、作业周转时间或响应的及时性等，在很大程度上都取决于处理机调度性能的好坏。因而，处理机调度便成为OS中至关重要的部分。
1.处理机调度的层次和调度算法的目标
1.1 处理机调度的层次
1高级调度
高级调度又称长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。
2低级调度
低级调度又称为进程调度或短程调度，其所调度的对象是进程（或内核级进程）。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。
3中级调度
中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。为此应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。
1.2 处理机调度算法的目标
1处理机调度算法的共同目标
(1) 资源利用率。
(2) 公平性。
(3) 平衡性。
(4) 策略强制执行。
2批处理系统的目标
(1) 平均周转时间短。
(2) 系统吞吐量高。
(3) 处理机利用率高。
3分时系统的目标
(1) 响应时间快。
(2) 均衡性。
4实时系统的目标
(1) 截止时间的保证。
(2) 可预测性。
2.作业与作业调度
2.1 批处理系统中的作业
1作业和作业步
(1) 作业(Job)。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
(2) 作业步(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互关系，往往是上一个作业步的输出作为下一个作业步的输入。例如，一个典型的作业可分成：“编译”作业步，“链接装配”作业步和“运行”作业步。
2作业控制块(Job Control Block, JCB)
为了管理和调度作业，在多道批处理系统中，为每个作业设置一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
3作业运行的三个阶段和三种状态
(1) 收容阶段。
(2) 运行阶段。
(3) 完成阶段。
2.2 作业调度的主要任务
作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业队资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度。每次执行作业调度时，都需做出以下两个决定。
1接纳多少个作业
在每一次进行作业调度时，应当从后备队列中选取多少作业调入内存，取决于多道和 序度(Degree of Multiprogramming)，即允许多少个作业同时在内存中运行。对系统来说，希望装入较多的作业，有利于提高CPU的利用率和系统的吞吐量。但如果内存中同时运行的作业太多时，进程在运行时因内存不足所发生的中断就会急剧增加。这将会使平均周转 时间显著延长，影响到系统的服务质量。因此，多道程序度的确定是根据计算机的系统规模、运行速度、作业大小，以及能否获得较好的系统性能等情况作出适当的抉择的。
2接纳哪些作业
应选择后备队列中的哪些作业调入内存，取决于所采用的调度算法。最简单的是先来 先服务调度算法，它是将最早进入外存的作业优先调入内存。较常用的一种算法是短作业 优先调度算法，是将外存上所需执行时间最短的作业优先调入内存。另一种较常用的是基 于作业优先级的调度算法，该算法是将外存上作业优先级最高的作业优先调入内存。比较 好的一种算法是“响应比高者优先”的调度算法。我们将在后面对上述的几种算法作较详细的介绍。
在批处理系统中，作业进入系统后，总是先驻留在外存的作业后备队列上，因此需要 有作业调度，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户 通过键盘输入的命令或数据等都被直接送入内存，因而无需配置上述的作业调度机制，但 也需要有某种接纳控制措施来限制进入系统的用户数目。即如果系统尚有能力处理更多的 任务，将会接纳授权用户的请求，否则，便拒绝接纳。类似地，在实时系统中也不需要作业调度，而必需具有接纳控制措施。
2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法
1先来先服务调度算法
FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业。
2短作业优先调度算法
SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
2.4 优先级调度算法和高相应比优先调度算法
1优先级调度算法(priority-scheduling algorithm, PSA)
在优先级调度算法中，是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的，这样就可以保证紧迫性作业优先运行。
2高相应比优先调度算法(Highest Response Ratio Next, HRRN)
高相应比优先调度算法是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机制调度的性能。
该优先级可表示为：
3.进程调度
3.1 进程调度的任务、机制和方式
1进程调度的任务
(1) 保证处理机的现场信息
(2) 按某种算法选取进程。
(3) 把处理器分配给进程。
2进程调度机制
为了实现进程调度，在进程调度机制中，应具有如下三个基本部分，如下图。
(1) 排队器。为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。
(2) 分派器。分派器依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理器分配给新选出的进程。
(3) 上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作：①第一对上下文切换时，OS将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元，再装入分派程序的上下文，以便分派程序运行；②第二对上下文切换是移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中，以便新选进程运行。
3进程调度方式
(1) 非抢占方式(NonPreemptive Mode)
在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其他进程。
(2) 抢占方式(Preemptive Mode)
这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一个进程。
“抢占”不是一种任意性行为，必须遵循一定的原则。主要原则有：
①优先权原则
②短进程优先原则
③时间片原则
3.2 轮转调度算法
在分时系统中，最简单也是较常用的是基于时间片的轮转(round robin, RR)调度算法。该算法采取了非常公平的处理机分配方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有n个进程，则每个进程每次大约都可获得1/n的处理机时间。
1轮转法的基本原理
在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。
2进程切换时间
在RR调度算法中，应在何时进行进程的切换，可分为两种情况：①若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。②在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。
3时间片大小的确定
一个较为可取的时间片大小是略大于一次经典的交互所需的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。
3.3 优先级调度算法
1优先级调度算法的类型
优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把该算法分成如下两种。
(1) 非抢占式优先级调度算法。
(2) 抢占式优先级调度算法。
2优先级的类型
优先级调度算法的关键在于：应如何确定进程的优先级，以及确定是使用静态优先级还是动态优先级。
(1) 静态优先级
确定优先级大小的依据有如下三个：
①进程类型。
②进程对资源的需求
③用户要求
(2) 动态优先级
动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。
3.4 多队列调度算法
该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
在多处理机系统中，该算法由于安排了多个就绪队列，因此，很方便为每个处理机设置一个单独的就绪队列。这样，不仅对每个处理机的调度可以实施各自不同的调度策略，而且对于一个含有多个线程的进程而言，可以根据其要求将其所有线程分配在一个就绪队列，全部在一个处理机上运行。再者，对于一组需要相互合作的进程或进程而言，也可以将它们分配到一组处理机所对应的多个就绪队列，使得它们能同时获得处理机并行执行。
3.5 多级反馈队列(multileved feedback queue)调度算法
1调度机制
多级反馈队列调度算法的调度机制可描述如下：
(1) 设置多个就绪队列。
(2) 每个队列都采用FCFS算法。
(3) 按队列优先级调度。
2调度算法的性能
在多级反馈队列算法中，如果规定第一个队列的时间片略大于多数人机交互所需处理时间时，便能较好地满足各种类型用户的需要。
(1) 终端型用户。
(2) 短批处理作业用户。
(3) 长批处理作业用户。
3.6 基于公平原则的调度算法
1保证调度算法
保证调度算法是另外一种类型的调度算法，它向用户所做的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间1/n。在实施公平调度算法时系统中必须具有这样的一些功能：
(1) 跟踪计算每个进程自创建以来已经执行的处理时间。
(2) 计算每个进程应获得的处理机时间，即自创建以来的时间除以n。
(3) 计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
(4) 比较各进程获得处理机时间的比率。
(5) 调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。
2公平分享调度算法
在该调度算法中，调度的公平性主要是针对用户而言，是所有用户能获得相同的处理机时间，或所要求的时间比例。然而调度又是以进程为基本单位，为此，必须考虑到每一个用户所拥有的进程数目。例如系统中有两个用户，用户1有4个进程A、B、C、D，用户2只有1个进程E。为保证两个用户能获得相同的处理机时间，则必须执行如下所示的强制调度序列：AEBECEDEAEBECEDE…
如果希望用户1所获得的处理机时间是用户2的两倍，则必须执行如下所示的强制调度序列：ABECDEABECDEABECDE…
各种调度算法总结比较：
4.实时调度
4.1 实现实时调度的基本条件
1提供必要的信息
(1) 就绪时间。
(2) 开始截止时间和完成截止时间
(3) 处理时间
(4) 资源要求
(5) 优先级
2系统处理能力强
在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过，而致使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。
3采用抢占式调度机制
在含有HRT任务的实时系统中，广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。
4具有快速切换机制
为保证硬实时任务能及时运行，在系统中还应具有快速切换机制，使之能进行任务的快速切换。该机制具有如下两方面的能力：
(1) 对中断的快速响应能力。
(2) 快速的任务分派能力。
4.2 实时调度算法的分类
可以按不同方式对实时调度算法加以分类：①根据实时任务性质，可将实时调度算法分为硬实时调度算法和软实时调度算法；②按调度方式，则可分为非抢占调度算法和抢占调度算法。
1非抢占式调度算法
(1) 非抢占式轮转调度算法。
(2) 非抢占式优先调度算法。
2抢占式调度算法
(1) 基于时钟中断的抢占式优先调度算法。
(2) 立即抢占的优先级调度算法。
