OS-2.2 CPU调度方式

2.2 CPU调度

一 . 处理机调度概念、层次

==“调度”==

==假设一堆人需要服务，就需要有某种规则（先后，VIP等）来决定谁先谁后。==

三个层次

==高级调度==

又称作业调度。
按照某种规则，**==把作业从外存调入内存，并创建进程。==**
- ==每个作业在生命周期中，只会调入一次，调出一次。==
- 作业调入时建立PCB，调出时撤销PCB。
（现代的分时/实时系统中，用户进程直接由交互式命令直接创建，一般没有独立的作业调度模块了。）

==低级调度==

又称进程调度（处理机调度）
按照某种算法进行 – ==进程间的调度。==
==调度频率最高==

==中级调度==

又称**==内存调度==**。
按照某种策略，**==把暂存到外存的、挂起状态 的进程，重新调回内存。==**
- 存在原因：内存不够时，一些进程的数据会被调去外存。
- 一个进程可能会被多次调入调出，所以中级调度发生的频率比高级调度高。

进程状态的补充

挂起态

==挂起态==：==暂时调到外存等待的进程==的状态。
有两种挂起态：就绪挂起和阻塞挂起。

回顾

二 . 进程调度的时机，切换与过程，调度调度方式

**1.进程调度的时机 **

**–==什么时候需要进行进程调度？==**（当前运行的进程主动或被动放弃处理机时候）

–==什么时候不能进行进程调度？==（中断处理，原子操作，进程在OS==内核==程序临界区）

临界资源：一个时间段内只允许一个进程使用的资源。（所以各进程需要互斥地访问临界资源）。

==临界区==：访问临界资源的==那段代码==。

内核临界区一般是用来访问某种内核数据结构的（eg进程的就绪队列）

进程处于操作系统内核临界区中，不能进行调度与切换。
VS对比：进程在普通临界区中是可以进行调度、切换的。（比如请求打印机，此时主动放弃CPU）

2.进程调度的方式

==非抢占式：==只允许进程主动放弃处理机。即即使有紧迫的任务，依旧不管，==只执行现在的进程（till进程终止或主动进入阻塞态）==。

不可以处理紧迫任务。实现简单，开销小。适合早期的批处理系统。

==抢占式：==允许进程被动放弃处理机。时钟中断后 / 有更紧迫的任务，==新任务可以抢占当前的进程的处理机==（by OS），当前进程暂停。

可以处理紧迫任务。适合分时操作系统，实时操作系统。

狭义的进程调度：只包括从就绪队列选出一个要运行的进程。（这个进程可以是当前的进程，也可以是别的进程 – 此时就需要进程切换。

广义的进程调度：包括选一个进程和进程切换两个步骤。

3.上下文，上下文切换

调度是决策行为。==（上下文）切换是执行行为。==

⭐**==进程的上下文==：由PCB表示。包括**

①CPU的所有寄存器的值（值就是进程现场信息）（eg，栈基址寄存器（一个线程一个栈））
②进程状态和控制信息（OS管理状态）（eg，页表基址寄存器（进程相关））
③堆栈中的内容（运行时的数据）

注：中断向量不属于上下文，是一组指向中断处理程序的指针，存放在内存中。

==上下文切换==：==将CPU切换到另一个进程，需保存当前的状态，并恢复另一个进程（新进程）的状态。==

⭐上下文切换的流程：

将当前CPU的各个寄存器的旧内容保存到当前进程的PCB中。
将新进程的现场信息装入CPU的各个寄存器
将控制转至新进程执行，即更新程序计数器PC的值。

注：进程调度和切换是有代价的，所以不是调度越频繁并发度越高。

例题：切换同一个进程内的线程时：

需要做的：

一个线程一个栈。

保存然后更新线程的程序计数器的值

不需要做的：

不需要更新页基址寄存器的值（因为线程共享进程的虚拟地址空间）

不需要更新进程的打开文件表（一个进程打开的文件也是被线程共享的）

回顾

三 . 调度程序、闲逛进程

调度程序

需要调度算法（让谁运行）
需要确定时间片大小（运行多久）

调度程序的组成：排队器，分派器，上下文切换器。

什么时候触发“调度程序”：

①创建新进程
②进程退出
③运行的进程阻塞
④IO中断发生（唤醒某些阻塞进程）

注：

不支持内核级线程的OS，调度程序的处理对象是进程

支持内核级线程的OS，调度程序的处理对象是内核线程

闲逛进程idle

就绪队列没有别的进程的时候，调度程序就会调度闲逛进程工作。

优先级是最低的。

四 . 调度算法的评价指标

CPU利用率

让CPU尽可能工作。

==利用率 = 工作时间 / 总时间==

系统吞吐量

单位时间完成作业的数量。

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

周转时间

作业被提交给系统开始，到作业完成结束之间的时间。

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

周转时间 =

作业在外存后备队列等待作业调度（高级调度）的时间 + （一次）

进程在就绪队列上等待进程调度（低级调度）的时间 + （多次）

进程在CPU上执行的时间 + （多次）

进程等待IO操作的时间（多次）

平均周转时间 = 各个作业周转时间之和 / 作业数（OS更关心的）

（周转时间并不能很好地代表时间，有的运行时间短，但是等待时间很长。所以提出了带权周转时间）

==带权周转时间 = 作业周转时间 / 作业实际运行时间==

等待时间

进程 / 作业处于等待处理机状态时间的和。

==进程等待时间== = ==周转时间-运行时间-IO操作时间。==

==作业等待时间== = 进程等待时间 + 作业在外存等待调度时间。

（一个作业被CPU服务多久的，被IO设备服务多久一般是确定不变的，因此调度算法只会影响作业/进程的等待时间）

响应时间

==用户提交请求到首次相应的时间。==

==响应比== =【等待时间 + “运行时间” 】/ “运行时间”

回顾

五 . 调度算法

①先来先服务FCFS

first come first serve

开销是最小的，无需判断/比较别的东西。

②短作业优先SJF

shortest job first

注：题目没提及，默认是非抢占式的。

抢占式的短作业/进程优先调度算法的==平均等待时间、平均周转时间最少。==
在所有进程几乎同时到达 时，采用SJF调度算法的评价等待时间、平均周转时间最少。（题目选项没有别的很明显错误的话，只能选它了）

③高响应比优先HRRN

FCFS算法对短作业不友好（考虑的是等待时间最长的）
SJF算法对长作业不友好（考虑的是运行时间最短的）
有没有一种算法，综合一点的？（考虑both等待时间和运行时间）
HRRN考虑的是：==响应比== =【等待时间 + “运行时间” 】/ “运行时间”
- （加“ ”是因为运行时间可能是进程虚假上报的哈哈哈）

回顾

上面三个算法不考虑任务的紧急程度/重要性，==只考虑等待时间和运行时间==。适合早期的批处理系统。
**之后学到的算法能够 ==响应最新的任务==**，==即考虑响应时间==，适合现代交互式系统。

①时间片轮转RR

绝对是抢占式的哦。

新来的或者被剥夺的放队尾

如果时间片太大(∞)，就退化成了先来先服务算法了。

如果时间片太小，频繁切换进程浪费时间。

②优先级算法

优先级又可以分为：

静态优先级
动态优先级。

优先级是怎么设置的：

系统进程优先级高于用户进程
==前台进程优先级== 高于 ==后台进程== 【交互型＞非交互型】
==IO型繁忙型进程== 高于 ==CPU繁忙型进程==（cpu繁忙型即频繁使用CPU，≈长作业）（io繁忙型即频繁请求io）

就绪队列可能有多个，按优先级组织，就可以把优先级高的放在队头了。

③多级反馈队列调度算法

算法规则：（==同时可调优先级和时间片==，更加通用）

==肯定是抢占式的。==

多级队列。各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第1级队列，按照先来先服务原则排队等待分配时间片。如果用完时间片进程还未结束，则进程进入下一级队列队尾。如果已经是最下级的队列了，就重新放回最下级队列队尾。
只有第k级队列为空时，才会为k+1级队头的进程分配时间片。
被抢占处理机的进程重新放回原队列末尾。（被抢占：上一级有新任务到来）