恶补《操作系统》2_2——王道学习笔记

2.2_1 处理机调度的概念、层次

基本概念：通常进程数量大于处理机数量，所以要按照一定的算法选择一个进程，并将处理机分配给它运行，以实现进程的并发执行

1 三个层次

1. 高级调度（作业调度）

辅助外存与内存之间的调度，作业调入时会建立相应的PCB，作业调出时才撤销PCB，调入可由操作系统决定，调出由作业运行结束才调出

1. 中级调度（内存调度）

将暂时不用的进程放到外存（PCB不外放），提高内存利用率和系统吞吐量，进程状态为挂起状态，形成挂起队列。（发生频率比高级的要高）

1. 低级调度（进程调度）

最基本，用算法为进程分配处理机资源，几十ms一次

2 三层调度的联系、对比

七状态模型=五状态+就绪挂起+阻塞挂起

（五状态前面学了，进程的“挂起态”分为就绪挂起、阻塞挂起）

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

进程调度就是上一节中的低级调度。

1、时机

什么时候需要进程调度？

• 主动放弃（进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞）
• 被动放弃（分给进程的时间片用完、有更紧急的事需要处理、有更高优先级的进程进入就绪队列）

什么时候不能进行进程调度？

• 在处理中断的过程中
• 在操作系统内核程序临界区中
• 临界资源：一个时段段内各进程互斥地访问临界资源；
• 临界区：访问临界资源的那段代码；
• 内核程序临界区：用来访问某种内核数据结构，如会访问就绪队列，导致其上锁；
• 在原子操作过程中（原语）

2、切换与过程

“狭义的调度”与“进程切换”的区别？

• 狭义：选择一个要运行的进程
• 广义：狭义+进程切换（一个让出 另一个占用）

进程切换的过程需要做什么？

• 对原来运行进程各种数据的保存
• 对新的进程各种数据的恢复

3、方式

非剥夺调度方式（非抢占式）

• 只允许进程主动放弃处理机

剥夺调度方式（抢占式）

• 进程被动放弃，可以优先处理紧急任务，适合分时操作系统、实时操作系统

2.2_3 调度算法的评价指标

1、CPU利用率

CPU利用率=CPU忙碌的时间/总时间

其他设备同理：利用率=忙碌的时间/总时间

例：

2、系统吞吐量

系统吞吐量=总共完成了多少道作业/总共花了多少时间

3、周转时间

（1）周转时间（提交作业的时间-完成作业花费的时间）

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

（3）带权周转时间（作业周转时间/作业实际运行的时间）

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

（1）和（3）都是越小越好

4、等待时间

进程或作业等待处理机状态时间的和

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

作业：建立后的等待时间+作业在外存后备队列中等待的时间

5、响应时间

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

2.2_4 FCFS、SJF、HRRN调度算法（适合早期批处理）

1、先来先服务（FCFS）

先到达先进行服务

作业-后备队列；进程-就绪队列；

非抢占式

公平、算法简单

对长作业有利、对短作业不利（如：排队买奶茶）、不会饥饿

2、短作业优先（SJF，shortest job first）

最短（服务时间最短）的作业优先得到服务，时间相同，先到达的先被服务

（1）非抢占式（SJF）：选最短需要时间的作业先进入运行态

（2）抢占式（SRTN）：有新作业进入就绪队列或有作业完成了，考察队列中的最小需要时间的作业

在所有进程都几乎同时到达时，采用SJP调度算法的平均等待时间、平均周转时间最少

若无红色前提，抢占式的短作业/进程的平均时间最少

优点：“最短的”平均等待时间，平均周转时间

缺点：对短作业有利，对长作业不利，可能产生长作业饥饿现象

3、高响应比优先（HRRN）

要综合考虑作业/进程的等待时间和要求服务的时间

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

响应比=（等待时间+要求服务时间）/要求服务时间

非抢占式

进程主动放弃CPU时，需要该算法选取就绪队列的作业

不会饥饿

2.2_5 时间片轮转、优先级调度、多级反馈队列

（适合交互式系统的调度算法）

1、时间片轮转算法（RR）

（1）算法思想：公平轮流地位各个进程服务，让每个进程在一定时间间隔内都可以得到响应

（2）算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列对位重新排队。

（3）优点：响应块，适用于分时操作系统

（4）缺点：由于高频率的进程切换，因此有一定的开销；不区分任务的紧急程度

不会饥饿

（5）时间片不能太大，会增大进程响应时间，可能会退化为先来先服务调度算法。

2、优先级调度算法

（1）算法思想：根据任务的紧急程度来决定处理顺序

（2）算法规则：每个进程/作业有各自的优先级，调度时选择优先级最高的作业/进程；当优先级相同，就选择先到达的；

（3）适用：作业/进程/IO

（4）抢占式/不可抢占均有（不可抢占：注意进程主动放弃处理机的情况；抢占式：如果到达发现自己优先级最高，可以抢占处理机）

（5）通常：系统进程优先级高于用户进程，前台进程优先级高于后台进程，操作系统更偏好I/O进程

（6）可以从追求公平、提升资源利用率等角度考虑改变优先级

（7）可能会饥饿

3、多级反馈队列调度算法

（1）算法思想：对其它算法调度的这种权衡

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

（3）优点：对各个进程相对公平（FCFS的优点），每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可以完成（SPF的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、IO密集型进程

默认抢占式；会饥饿；