处理机调度典型调度算法

调度的概念

多道程序系统中，进程的数量往往多余处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法(以公平高效为原则)选择一个进程并将处理机分配给这个进程运行，以实现进程的并发执行。

调度层次：一个作业从提交直到运行完成，往往要经离三级调度，分别是：

1.高级调度(作业调度)

​ 按照一定的原则从外存上处于后备队列的作业中挑选一个，给它分配内存、输入/输出设备等必要的资源，并建立相应的进程，让它获得竞争处理机的权力。作业调度就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。

​ 作业时从用户角度出发，由用户提交，以用户任务为单位；

2.中级调度(内存调度)

​ 为了提高内存利用率和系统吞吐量，引入中级调度。将那些暂时不能运行的进程调至外存进行等待，此时进程的状态称为挂起态。当它们已经具备运行条件而且内存又有空闲的时候，由中级调度来决定把外存上的哪些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪态队列上等候。中级调度实际上是存储器管理中的对换功能。

3.低级调度(进程调度)

​ **按照某种算法从就绪队列中选取一个进程，将处理机分配给它。**进程调度是最基本的一种调度，在各种操作系统中都必须配置这级调度。进程调度的频率很高，一般几十毫秒一次。

作业调度从外存的后被队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度就是从就绪队列中选出一个进程，把处理机分配给它并把它的状态改为运行态。中级调度是为了提高内存的利用率，把一些暂时不能运行(阻塞态)的进程放到外存里挂起来。

1. 作业调度为进程活动做准备，进程调度让进程正常活动起来(作业调度是将作业拿进来并建立进程，建立PCB，分配除了处理机以外的所有作业需要的资源)
2. 中级调度将暂时不能运行的进程挂起，提高内存的利用率和系统吞吐量。
3. 作业调度次数少，中级调度(内存调度)次数一般，进程调度次数最多
4. 进程调度是不可或缺的，最基本的

​ 进程从操作系统出发，由系统生成，时曹祖系统的资源分配和独立运行的基本单位。

调度的目标

为了比较处理机调度算法的性能，有以下几种评判标准：

CPU利用率：我们需要尽可能让CPU处于忙碌的状态，也就是尽可能提高CPU利用率
$$CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$$
系统吞吐量：单位时间内CPU完成作业的数量。长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量。而对于短作业，需要消耗的处理机时间较短，因此能提高系统的吞吐量。调度算法和方式的不同会影响系统吞吐量。

周转时间：指从作业提交到作业完成所经历的时间。周转时间的计算方式如下：
$$周转时间=作业完成时间-作业提交时间$$
​ 平均周转时间指的是多个作业周转时间的平均值：
$$平均周转时间=\frac{作业1的周转时间+作业2的周转时间+作业3的周转时间+...}{n}$$
​ 带权周转时间指的是作业周转时间与作业实际运行时间的比值：
$$带权周转时间=\frac{作业周转时间}{作业实际运行时间}$$
​ 平均带权周转时间是指多个作业的带权周转时间的平均值。

等待时间：指进程处于等待处理机资源的时间之和。等待时间越长，用户满意度越低。处理机调度算法实际上不影响作业执行输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，往往只需要简单的考察等待时间。

响应时间：指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不是最好的评价标准，一般采用响应时间作为衡量调度算法的重要准则之一。

调度的实现

调度器(调度程序)：

操作系统中，用于调度和分派CPU的组件被称为调度程序，通常由三部分组成：

1. 排队器：将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态的时候，排队器就把它插入到相应的队列中。
2. 分派器：依据调度程序所选的进程，将这个进程从就绪队列中取出，将CPU分配给新进程
3. 上下文切换器：在对处理机进行切换的时候，会发生两对上下文的切换操作。第一对是将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行。第二对是移出分派程序的上下文，将新的进程的CPU现场信息装入处理机的各个相应寄存器。

调度时机，切换与过程

调度程序是操作系统内核程序，请求调度的事件发生后，才可能运行调度程序。调度了新的就绪进程后，才会进行进程切换。现代操作系统中，不能进行进程的调度和切换的情况有以下几种：

1. **在处理中断的过程中。**中断处理过程复杂，且中断处理时系统工作的一部分，逻辑上不属于某一个进程，不应该被剥夺处理及资源
2. 进程在操作系统内核临界区中。进入临界区后，需要独占式地访问，理论上必须加锁，防止其他进程会并行进入。在解锁前不应切换到其他进程。
3. **其他需要完全屏蔽中断的原子操作过程中。**如加锁、解锁、中断现场保护等原子操作。在原子过程中，会屏蔽中断，当然也会屏蔽进程的调度和切换

如果在上面三个事件发生的过程中引起了调度的事件，不能马上进行进程调度与切换，只有等上述的三个事件完成之后，才能进行进程切换

应该进行进程调度与切换的情况如下：

1. 发生引起调度条件且当前进程无法继续进行下去的时候，可以马上进行调度与切换。如果操作系统之在这个情况下进行进程调度，那么我们称之为非剥夺调度。
2. 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，如果发现了请求调度标志，就可以立马进行进程调度与切换。如果操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度。

进程切换往往在调度完成之后立刻发生，它要求保存原进程当前断电的现场信息，回复被调度进程的现场信息。现场切换的时候，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针，重设PC寄存器等相关工作后，开始运行新的进程。

进程调度方式

通常由两种进程调度方式：

1.非抢占调度方式，又称为非剥夺方式。是指当一个进程正在处理机上执行的时候，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程运行完成或发生某个事件而进入阻塞态的时候，才把处理机分给别的进程

2.抢占调度方式，又称剥夺方式。是指当一个进程正在处理机上运行的时候，如果有某个更为重要或紧迫的进程需要使用处理机，则允许调度程序根据某种原则去暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。

抢占调度方式对提高系统吞吐率和相应效率有明显的好处，但抢占不是一个任性的行为，必须遵循一定的原则，主要有优先权、段进程优先和时间片原则等。

闲逛进程

在进程切换的时候，如果系统中没有运行程序，就会调度闲逛进程(idle)运行，并且在执行过程中测试中断。只要有进程就绪，就会立即让出处理机。闲逛进程不需要CPU以外的资源，它不会被阻塞

两种线程的调度

1.用户级线程调度：由于内核并不知道线程的存在，所以内核还是和以前一样，选择一个进程，并赋予一定的运行时间片，如果超出了时间片，就会强制挂起这个进程

2.内核级线程调度：内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。给被选择的线程赋予一定的运行时间，如果超出了时间，就强制挂起这个线程

用户级线程的线程切换在统一进程中，只需要少量的机器指令。内核级线程的切换需要完整的上下文切换，修改内存映像这就导致了一定的延迟。

典型调度算法

FCFS-先来先服务算法

最简单的调度算法，既可以用于作业调度，又可以用于进程调度。

作业调度中，每次从后备作业队列中选择最先进入队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

进程调度中，每次从就绪队列中选择最先进入队列的进程，将处理机分配给这个进程，直到；这个进程运行完成或因为某种原因而阻塞的时候才释放处理机(例如请求I/O)。

FCFS算法属于不可剥夺算法。且不会产生饥饿现象。

从表面上看，FCFS对所有的作业都是公平的，但如果一个长作业先到达系统，就会使后面的很多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。

特点：

1. 算法简单，但是效率低
2. 对长作业比较有利，但是对短作业不利(此处不利是相对于SJF算法)
3. 有利于CPU繁忙型作业，而不利于I/O繁忙型作业

SJF-短作业优先算法(非抢占版本)

对短作业(或段进程)优先进行调度的算法。

作业调度中，从后备队列中选择一个或多个估计运行时间最短的作业，将它们调入运行

进程调度中，从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给这个进程，直到完成或发生某时间而阻塞的时候，才释放处理机

缺点：

1. 对长作业不利，即长作业的周转时间会增加。如果有长作业进入队列，由于调度程序总是优先调度那些(即使是后面进来的)短作业，将导致长作业长期不被调度，会发生饥饿现象
2. 算法完全不考虑作业的紧迫程度，所以不能保证紧迫性高的作业会被及时处理
3. 由于作业的长短是根据用户的估计执行时间而定的，所以会有造假现象。

特点：平均等待时间，平均周转时间最少

优先级调度算法

既可用于作业调度，又可用于进程调度。算法中的优先级用于描述作业紧迫程度。

作业调度中，优先级调度算法每次从后备队列中选择优先级最高作业，将其调入内存并分配必要的资源。

进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它。

根据新的更高优先级进程是否能够抢占处理机，分为了以下两类调度算法：

1.非抢占式优先级调度算法

​ 当一个进程正在处理机上面运行的时候，即使有某个优先级更高的进程进入就绪队列，仍让正在运行的进程继续运行，知道由于其自身原因而让出处理机的时候(任务完成或等待事件)，才把处理机分配给就绪队列中优先级最高的进程

2.抢占式优先级调度算法

​ 当一个进程正在处理机上运行的时候，如果有某个优先级更高的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给优先级更高的进程。

根据进程创建后优先级是否可以改变，可以将优先级分为以下两种：

1.静态优先级

​ 在进程创建时确定，且在整个进程运行的过程中不可改变。确定优先级的主要依据有进程类型，进程对资源的要求、用户要求

2.动态优先级

​ 进程运行的过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据有占用CPU时间的长短、进程就绪等待CPU时间的长短。

一般来说，进程优先级的设置可以参照以下原则：

1. 系统进程>用户进程。系统进程作为系统的管理者，理应拥有更高的优先级
2. 交互型进程>非交互型进程(前台进程>后台进程)。正在前台运行的程序应该更快速地进行响应。
3. I/O型进程>计算型进程。I/O型进程指会平凡使用I/O设备的进程，而计算型进程指会平凡使用CPU的进程。让I/O型进程提早工作，可以提高系统的整体效率

高响应比优先算法HRRN

高响应比优先算法主要用于作业调度，是对FCFS算法和SJF算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。在每次进行作业调度的时候，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

响应比的计算公式为：
$$响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}$$
根据公式可以知道：

1. 等待时间相同的情况下，要求服务时间越短，响应比越高，有利于短作业(SJF)
2. 要求服务时间相同的情况下，等待时间越长，响应比越高(FCFS)
3. 只要等待时间足够长，长作业也能获得处理机，所以不会出现饥饿现象

时间片轮转调度算法

主要用于分时系统。系统将所有就绪进程按FCFS策略排列成一个就绪队列，调度程序总是选择队列的第一个进程执行，但仅能运行一个时间片。使用完时间片后，即使进程没有完成执行，也必须释放处理机给下一个进程。而失去了处理机的进程则返回到就绪队列的末尾重新排队，等待再次运行。

时间片的大小对系统性能的影响很大，如果时间片足够大，以至于所有的进程能在一个时间片内执行完成，那么时间片轮转调度算法就变成了FCFS算法。如果时间片很小，则处理机将在进程之间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间减少。

时间片的长短由以下两个因素确定：

1. 系统的响应时间
2. 就绪队列中的进程数目和系统的处理能力

时间片轮转增加了系统开销，所以它并不会使系统高效运行。时间片轮转的主要目的是使得多个交互的用户能够得到及时响应。

多级队列调度算法

上述调度算法只设置一个进程队列，而且调度算法固定单一，无法满足系统中不同用户对进程调度策略的不同要求。多处理机系统中，这个缺点更为突出，而多级队列调度算法能在一定程度上弥补这个缺点。

该算法在系统中设置多个就绪队列，将不同的类型或性质的进程固定分配到不同的就绪队列。每个队列可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。同一队列的进程中可以设置不同的优先级，不同的队列本身也可以设置不同的优先级。在多处理机系统中，可以很方便地为每个处理机设置一个单独的就绪队列，每个处理及可以实施各自不同的调度策略，这样能根据用户需求将多线程分配到一个或多个处理机上运行

多级反馈队列调度算法

融合了前面几种算法的优点。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。

实现思想如下：

1. 设置多个就绪队列，并为每个队列赋予不同的优先级。第一级的优先级最高，第二级的优先级次之，其余队列的优先级逐个降低
2. 赋予各个队列的进程运行时间片的大小各不相同。优先级越高的队列中，每个进程获得的时间片就越小。
3. 每个队列都采用FCFS算法。当新进程进入内存之后，首先要将它放入第1级队列的末尾，按FCFS原则等待调度。轮到该进程运行的时候，就开始运行，运行结束后将该进程放到下一级就绪队列的末尾。如此重复执行。
4. 按队列优先级调度，只有当第1级队列为空的时候，才调度第二级队列中的进程进行运行；只有当第i-1层队列为空的时候，才会调度第i层队列的进程去运行。如果允许第i级队列的进程时突然又有进程进入了优先级较高的队列，那么就把正在运行的进程放回第i级末尾，转而去执行刚进入高优先级队列的那个进程。

特点：

1. 终端型作业用户：短作业优先
2. 短批处理作业用户：周转时间短
3. 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理

算法特点总结

进程切换

进程的切换在内核的支持下实现。

任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

上下文切换

上下文指某一时刻CPU寄存器和程序计数器的内容。进行上下文切换的时候，内核会将就进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。

实质上是处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化。上下文切换的流程如下：

1. 挂起一个进程，保存CPU上下文，包括程序计数器和其它寄存器
2. 更新PCB信息
3. 把进程的PCB移入相应的队列，如就绪队列，阻塞队列
4. 选择另一个进程执行，并更新其PCB
5. 跳转到新进程PCB中的程序计数器所指向的位置执行。
6. 恢复处理机上下文

上下文切换的消耗

上下文切换通常是计算密集型的，即它需要相当可观的CPU时间。也就是说，上下文切换对系统来说意味着消耗大量的CPU时间。有些处理器提供多个寄存器组，这样，上下文切换就只需要改变当前寄存器组的指针

上下文切换与模式切换

模式切换与上下文切换是不同的，模式切换时，CPU逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态，如果进程因中断或异常进入核心态，执行完后又会回到用户态刚被中断的进程运行。用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程，上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性

调度和切换的区别：调度是指决定资源分配给哪个进程的欣慰，是一种决策行为；切换是指实际分配的行为，是执行行为。一般来说现有资源的调度，然后才有进程的切换。