OS-2.2 CPU调度方式
2.2 CPU调度
一 . 处理机调度概念、层次
“调度”概念
假设一堆人需要服务，就需要有某种规则（先后，VIP等）来决定谁先谁后。
三个层次
高级调度
又称作业调度。
按照某种规则，把作业从外存调入内存，并创建进程。
- 每个作业在生命周期中，只会调入一次，调出一次。
- 作业调入时建立PCB，调出时撤销PCB。
（现代的分时/实时系统中，用户进程直接由交互式命令直接创建，一般没有独立的作业调度模块了。）
低级调度
- 又称进程调度（处理机调度）
- 按照某种算法进行 – 进程间的调度。
- 进程调度的频率最高。
中级调度
又称内存调度。
按照某种策略，把暂存到外存的、挂起状态 的进程，重新调回 内存。
- 存在原因：内存不够时，一些进程的数据会被调出外存。
- 一个进程可能会被多次调入调出，所以中级调度发生的频率比高级调度高。
进程状态的补充
挂起态
挂起态：暂时调到外存等待的进程的状态。
有两种挂起态：就绪挂起和阻塞挂起
回顾
二 . 进程调度的时机，切换与过程，调度调度方式
**进程调度的时机 **
–什么时候 需要进行进程调度？（当前运行的进程 主动或被动 放弃处理机时候）
–什么时候 不能进行进程调度？（中断处理，原子操作，进程在OS内核程序临界区）
临界资源：一个时间段内只允许一个进程使用的资源。（所以各进程需要互斥地访问临界资源）。
临界区：访问临界资源的那段代码。
内核临界区一般是用来访问某种内核数据结构的（eg进程的就绪队列）
进程处于操作系统内核临界区中，不能进行调度与切换。
VS对比：进程在普通临界区中是可以进行调度、切换的。（比如请求打印机，此时主动放弃CPU）
进程调度的方式
==非抢占式：==只允许进程主动放弃处理机。即即使有紧迫的任务，依旧不管，只执行现在的进程（till进程终止或主动进入阻塞态）。
- 不可以处理紧迫任务。实现简单，开销小。适合早期的批处理系统。
==抢占式：==允许进程被动放弃处理机。时钟中断后 / 有更紧迫的任务，新任务可以抢占当前的进程的处理机（BY OS），当前进程暂停。
- 可以处理紧迫任务。适合分时操作系统，实时操作系统。
狭义的进程调度：只包括从就绪队列选出一个要运行的进程。（这个进程可以是当前的进程，也可以是别的进程 – 此时就需要进程切换。
广义的进程调度：包括选一个进程和进程切换两个步骤。
上下文，上下文切换
调度是决策行为。（上下文）切换是执行行为/实现手段。
⭐进程的上下文：由PCB表示。包括①CPU的所有寄存器的值（值就是进程现场信息），②进程状态和控制信息（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，≈长作业）
就绪队列可能有多个，按优先级组织，就可以把优先级高的放在队头了。
③多级反馈队列调度算法
算法规则：（同时可调优先级和时间片，更加通用）
回顾
多级队列调度算法
其他：基于公平原则的调度算法
保证调度算法：每个进程，获得相同的cpu时间
公平分享调度算法：每个用户，获得相同的cpu时间
六 . 多处理机调度
非对称处理机：主CPU负责决策调度，其他CPU负责执行任务。
对称处理机（此处探讨的）：CPU地位平等。
单处理机调度：①只用决定让哪个就绪进程优先上处理机
多处理机调度：① + ②还需决定被调度的进程上哪一个处理机。
多处理机调度，额外的两个目标：
- 负载均衡：尽量让每个CPU都忙碌
- 处理机亲和性：尽量让同一个进程在同一个CPU运行（让cpu的cache发挥作用）
解决方案一：公共就绪队列
所有CPU共享一个就绪进程队列。
负载均衡（√）
亲和性的解决方案：
- 软亲和：进程调度程序，尽量保证亲和性
- 硬亲和：（用户进程提供系统调用，）请求OS保证亲和性。
解决方案二：私有就绪队列
每一个CPU都有自己的就绪队列。
亲和性（√）
解决负载均衡：
- push策略：一个特定的系统程序，周期性检查每一个cpu的负载，（if负载高）push忙碌的cpu的进程去别的cpu
- pull策略：CPU运行调度程序时，周期性检查自身负载，（if自己负载低）pull高负载CPU的进程来自己这。
回顾
其他：
调度算法考虑的：资源利用率，平均周转时间等等。
调度算法不考虑的：互斥，互斥是一种同步机制。