2.处理机调度

2.1.调度的概念、层次

1.调度：处理机有一堆程序需要处理，根据某种规则决定处理的顺序

2.调度的三个层次：

①高级调度（作业调度）：从外存的作业中选择一个作业调入内存，并创建进程；每个作业只调入和调出一次；调入时建立PCB，调出时撤销PCB

②低级调度（进程调度/处理机调度）：从就绪队列中选择一个进程上处理机；频率很高

③中级调度（内存调度）：将处于挂起状态的进程重新调入内存

挂起状态：内存不够，将某些进程的数据调入外存

2.2.进程调度的时机、切换与过程、方式

2.2.1.进程调度的时机

1.正在运行的进程主动请求：①正常终止 ②发生异常终止 ③请求阻塞

2.正在运行的进程被动放弃：①时间片用完 ②更紧急事件需要处理（I/O中断等） ③更高优先级进程进入就绪队列

3.不能进行调度的时机：①处理中断的过程中 ②操作系统内核临界区中 ③原子操作过程中

4.临界资源：一段时间内只允许一个进程使用的资源（互斥访问）

临界区：访问临界资源的代码（各个进程需要互斥的进入临界区）

内核程序临界区一般用来访问某种内核的数据结构：例如进程的就绪队列

5.设进程A处于内核程序临界区，并且该临界区访问的是进程的就绪队列，在访问前进程A将会将就绪队列上锁（达到互斥访问的效果）；此时若发生进程调度，就需要访问就绪队列，但是就绪队列被A上锁，因此无法发生进程调度——因此，进程在操作系统内核临界区中不能进行调度和切换

6.本质上是若进程访问的是操作系统内核的临界区，操作系统希望进程能够尽快的完成访问操作，从而不影响操作系统的正常工作，因此，通过不允许进程调度和切换的方式达到这一目的；而若进程访问的是慢速I/O设备，即不会影响操作系统的情况下，就允许进行进程调度和切换，并且还有一个角度可以解释，即此情况下若不允许进行进程的调度和切换，将会严重影响操作系统的运行效率，其他进程需要等待此慢速I/O设备的完成

2.2.2.进程调度的切换过程

1.狭义的进程调度：从就绪队列中选择一个要运行的进程

广义的进程调度：①选择一个进程 ②进程切换

2.进程切换：一个进程让出处理机，另一个进程使用处理机

进程切换的过程：①对原进程各种数据的保存 ②对新进程各数据的恢复

进程切换带有系统开销，频繁的进程切换将会导致系统效率降低

2.2.3.进程调度的方式

1.非剥夺调度方式（非抢占式）：只允许进程主动放弃处理机

缺点：无法及时处理紧急事件

2.剥夺调度方式（抢占式）：进程可以被更高优先级的进程剥夺处理机使用权

优点：可以优先处理紧急事件，并且可以实现进程按时间片轮流执行

2.3.调度器和闲逛进程

2.3.1.调度器/处理程序

1.调度器/调度程序是操作系统的一个程序模块

2.①就绪态→运行态：被调度程序选中

②运行态→就绪态：时间片用完

①和②的状态的转换由调度程序完成

3.调度程序根据调度算法决定让哪个进程运行，根据时间片大小决定让该进程运行多长时间

4.调度时机，即什么事件会触发调度程序

①创建新进程：就绪队列发生改变，新进程若优先级更高，可能抢占处理机

②进程退出：进程退出导致处理机空闲，调度程序需要决定接下来让哪个进程上处理机运行

③正在运行的进程阻塞：阻塞导致处理机空闲，调度程序需要决定接下来让哪个进程上处理机运行

④I/O中断发生：某个之前处于阻塞态的进程转换到就绪态，就绪队列发生改变，该进程若优先级更高，可能抢占处理机

若是非抢占式调度策略，则仅②③会触发调度程序；抢占式，则每间隔若干个时钟周期就会触发一次调度程序（用于检查就绪队列是否有新进程出现）

2.3.2.闲逛进程

1.若就绪队列中没有其他进程，调度程序则选择闲逛进程上处理机运行

2.闲逛进程特点：①优先级 ②0地址指令（占用完成的指令周期，即带有中断周期，在中断周期例行唤醒调度程序，用来检查就绪队列中是否有新进程出现） ③能耗低

2.4.调度算法的评价指标

1.CPU利用率 = 忙碌时间 / 总时间

2.系统吞吐量 = 总共完成多少作业 / 总共花了多少时间（表示单位时间内完成作业的数量）

3.周转时间：指从作业被提交给系统开始到作业完成为止的时间

周转时间由四个部分组成：

①作业在外存中等待作业调度（高级调度）的时间

②进程在就绪队列上等待进程调度（低级调度）的时间（就绪态）

③进程在CPU上运行的时间（运行态）

④进程等待I/O操作完成的时间（阻塞态）

②③④可能发生多次，而①只会有一次

（1）周转时间 = 作业完成时间 - 作业提交时间

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

（3）带权周转时间 = 作业周转时间（即作业完成时间 - 作业提交时间） / 作业实际运行的时间

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

4.等待时间：作业/进程等待处理机时间之和

①对于进程：等待I/O完成的期间（阻塞态）也是在被服务的，因此不计入等待时间

②对于作业：不仅需要考虑作业建立进程后的等待时间，还要考虑调入内存前的等待时间

5.响应时间：从提出请求到首次响应的时间

2.5.调度算法

2.5.1.先来先服务（FCFS）

2.5.2.短作业优先（Shortest Job First）

1.非抢占式短作业优先

2.抢占式短作业优先（最短剩余时间优先）

2.5.3.高响应比优先（Highest Response Ratio Next）

2.5.4.时间片轮转调度算法（Round-Robin）

1.时间片大小为2：时间片设置太小将会导致频繁切换，从而系统开销增大

2.时间片大小为5：时间片选择太大，则会退化成FCFS算法

2.5.5.优先级调度算法

1.非抢占式：仅进程主动放弃处理机时调度

2.抢占式：①进程主动放弃处理机时 ②就绪队列发生改变时

3.补充

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

1.P1（1）：0时刻，P1到达，放入第一级队列，P1执行1个时间片后，放入第二级队列队尾

2.P2（1）：1时刻，P2到达，放入第一级队列，P2执行1个时间片后，放入第二级队列队尾（第二级：P1→P2）

3.P1（2）：2时刻，第一级队列为空，执行第二级队列的队首进程，P1执行2个时间片后，放入第三季队列队尾（第二级：P2；第三级：P1）

4.P2（1）：4时刻，第一级队列为空，执行第二级队列的队首进程，P2执行1个时间片后，P3到达，P3优先级大于P2，P2被剥夺处理机的使用权，并放回第二级队列队尾（第二级：P2；第三级：P1）

5.P3（1）：5时刻，P3到达，放入第一级队列，P3执行1个时间片后，P3进程结束，调出内存（第二级：P2；第三级：P1）

6.P2（2）：6时刻，第一级队列为空，执行第二级队列的队首进程，P2执行2个时间片后，P2进程结束，调出内存（第三级：P1）

7.P1（4）：8时刻，第一级、第二级队列为空，执行第三级队列的队首进程，P1执行4个时间片后，将P1重新放回第三级队列的队尾（第三级：P1）

8.P1（1）：12时刻，第一级、第二级队列为空，执行第三级队列的队首进程，P1执行1个时间片后，P1进程结束，调出内存

2.5.7.调度算法的对比

2.5.8.多级队列调度算法

1.系统设置多个就绪队列，调度方式：①选中队列→②选中该队列中进程

2.选中队列的方式：①优先级高低 ②时间片轮转

3.每个队列中选中进程的方式可以不同