目录

一、处理机调度

1.处理机调度的概念

2.处理机调度的三个层次

高级调度

中级调度

低级调度

三种调度的比较

3.进程调度

时机、切换与过程

方式

4.调度算法的目标和评价指标

处理机调度算法的共同目标

批处理系统的目标

评价指标

二、调度算法

1.先来先服务（FCFS）

2.短作业优先（SJF）

3.高相应比优先（HRRN）

4.时间片轮转（RR）

5.优先级调度算法

6.多级反馈队列调度算法

---

一、处理机调度

1.处理机调度的概念

调度：当有多个任务需要处理，由于资源有限，这些任务无法同时处理，这时需要某种规则来决定处理这些任务的顺序。

处理机调度：从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

2.处理机调度的三个层次

高级调度

高级调度又称长程调度或作业调度，调度对象是作业。根据某种算法决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。

中级调度

中级调度又称为内存调度。操作系统会把暂时不能运行的进程，调至外存等待，此时进程的状态称为挂起状态。PCB不会被调入外存，PCB常驻内存。中级调度就是决定哪个挂起态的进程被重新调入内存。引入内存调度的主要目的是，提高内存利用率和系统吞吐量。

低级调度

低级调度又称为进程调度和短程调度，其所调度的对象是进程（或内核级线程）。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的操作系统中都必须配置这级调度。

三种调度的比较

3.进程调度

时机、切换与过程

1.进程主动放弃处理机

• 进程正常终止
• 运行过程中发生异常而终止
• 进程主动请求阻塞（如 等待 I/O）

2.进程被动放弃处理机

• 分给进程的时间片用完
• 处理更紧急的事（如I/O中断）
• 有更高优先级的进程进入就绪队列

3.不能切换进程的情况：

• 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
• 进程在操作系统内核程序临界区中。
• 在原子操作过程中（原语）。原子操作不可中断。
   

进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。
 

方式

非抢占式：只允许进程主动放弃处理机。在运行过程中即便有更紧急的任务到达，当前进程依旧会继续使用处理机，直到该进程终止或主动要求进入阻塞。

抢占式：当一个进程正在处理机上执行时，如果有一个更紧急或更重要的需要使用处理机，就立刻暂停正在执行的进程，把处理机分配给更重要紧急的那个进程。

4.调度算法的目标和评价指标

处理机调度算法的共同目标

 1.资源利用率高

CPU的利用率 =  CPU有效工作时间 / CPU有效工作时间 + CPU空闲等待时间
 2.公平性

使所有进程都获得合理的CPU时间，不会发生进程饥饿现象。
 3.资源的平衡利用
由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。

 4.策略的强制执行

对所制定的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

批处理系统的目标

•  周转时间短

每个用户都希望自己的周转时间短，系统希望平均周转时间短。

• CPU利用率高

尽量选择计算量大的作业。

• 系统吞吐量高

吞吐量指在单位时间内系统所完成的作业数。

系统的吞吐量 = 总共完成的作业数 / 总共花费的时间

评价指标

周转时间：某一作业提交系统的时间到该作业完成的这段时间间隔。（作业完成时间 - 作业提交时间）

包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间

平均周转时间 = 各作业周转时间之和 / 作业数

带权周转时间 = 作业周转时间 / 作业实际允许时间  = 作业完成时间 - 作业提交时间 / 作业实际允许时间 （>=1 越小用户体验越好）

平均周转时间 = 各作业带权周转时间之和 / 作业数

等待时间：进程/作业 等待被服务的时间之和

响应时间：从用户提交请求到首次产生响应所用的时间

---

二、调度算法

1.先来先服务（FCFS）

按照到达的先后顺序调度，类似于队列先进先出的特点。

 不会导致饥饿，因为在队列中就算等待时间再长也会到达队头进行执行。

 例题：

2.短作业优先（SJF）

优先处理短作业（服务时间短）

 例题：

3.高相应比优先（HRRN）

 

0时刻，只有p1一个进程，p1被处理机调度

7时刻（p1主动放弃CPU）：就绪队列中有 p2（响应比：(5+4)/ 4 = 2.25）p3（相应比：(3+1)/1 = 4 ）p4(响应比 ：(2+4) / 4 = 1.5)    p3响应比最高被处理机调度

8时刻（p3完成）：p2（2.5）、 p4(1.75)   p2被调度执行

12时刻(p2完成) ： p4被调度执行

注:这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很差。因此这三种算法一般适合用于早期的批处理系统。
 

4.时间片轮转（RR）

 

 时间片大小为2

 时间片大小为5

注：如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少，因此时间片也不能太小。
 

时间片大小的选取一般要略大于一次典型的交互所需要的时间。

5.优先级调度算法

例题：

非抢占式

                优先数越高，优先级越大

抢占式

当然这是静态优先级：创建进程时确定，之后一直不变。还有动态优先级，创建进程时有一个初始值，之后会一直变化。 例如每次执行一个时间片优先级就 -1

6.多级反馈队列调度算法

1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。
3.只有第k级队列为空时，才会为k+1级队头的进程分配时间片被抢占处理机的进程重新放回原队列队尾。

例题：

参考《王道考研 操作系统》 《计算机 操作系统》（汤小丹 第四版）