参考
陈向群操作系统 ppt简要整理
正文
CPU调度:
即按一定的调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程
如果没有就绪进程，系统会安排一个系统空闲进程或idle进程
进程切换：
是指一个进程让出处理器，由另一个进程占用处理器的过程
主要做了两项工作：
- 切换全局页目录以加载一个新的地址空间
- 切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息，如CPU相关寄存器
场景：进程A下CPU，进程B上CPU
- 保存进程A的上下文环境（程序计数器、程序状态字、其他寄存器……）
- 用新状态和其他相关信息更新进程A的PCB
- 把进程A移至合适的队列（就绪、阻塞……）
- 将进程B的状态设置为运行态
- 从进程B的PCB中恢复上下文（程序计数器 、程序状态字、其他寄存器……）
上下文切换开销
直接开销：内核完成切换所用的CPU时间
- 保存和恢复寄存器……
- 切换地址空间（相关指令比较昂贵）
间接开销
高速缓存(Cache)、缓冲区缓存(Buffer Cache)和TLB(Translation Look-aside Buffer)失效
调度算法
FIFO 先来先服务
按照进程就绪的先后顺序使用CPU
非抢占
短作业优先(SJF)
具有最短完成时间的进程优先执行
非抢占式
最短剩余时间优先
SJF抢占式版本，即当一个新就绪的进程比当前运行进程具有更短的完成时间时，系统抢占当前进程，选择新就绪的进程执行
容易产生饥饿现象
最高相应比优先
调度时，首先计算每个进程的响应比R；之后，总是选择 R 最高的进程执行
等待时间越久，补偿越大
响应比R = 周转时间 / 处理时间
=（处理时间 + 等待时间）/ 处理时间
= 1 +（等待时间 / 处理时间）时间片轮转
每个进程分配一个时间片
时钟中断 → 轮换
虚拟轮转法
不记录了
最高优先级
选择优先级最高的进程投入运行
优先级反转
多级反馈队列
是UNIX的一个分支BSD （加州大学伯克利分校开发和发布的）5.3版所采用的调度算法
- 设置多个就绪队列，第一级队列优先级最高
- 给不同就绪队列中的进程分配长度不同的时间片，第一级队列时间片最小；随着队列优先级别的降低，时间片增大
- 当第一级队列为空时，在第二级队列调度，以此类推
- 各级队列按照时间片轮转方式 进行调度
- 当一个新创建进程就绪后，进入第一级队列
- 进程用完时间片而放弃CPU，进入下一级就绪队列
- 由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列(阻塞完成后的进程优先级比较高)
比较
FCFS:FIFO
Round Robin:
SJF:短作业有限
SRTN:最短时间优先
HRRN:最高响应比
Feedback:多级反馈队列Linux调度算法
Windows线程调度
- 调度单位是线程
- 采用基于动态优先级的、抢占式调度，结合时间配额的调整
调度策略
- 主动切换
- 抢占
- 时间配额用完
I/O完成后的线程优先级提升
- 在完成I/O操作后，Windows 将临时提升等待该操作线程的优先级，保证该线程能更快上CPU运行进行数据处理
- 优先级的提升值由设备驱动程序决定，提升建议值保存在系统文件“Wdm.h”或“Ntddk.h”中
- 优先级的提升幅度与对I/O请求的响应时间要求是一致的，响应时间要求越高，优先级提升幅度越大
- 设备驱动程序在完成I/O请求时通过内核函数IoCompleteRequest来指定优先级提升的幅度
- 为避免不公平，在I/O操作完成唤醒等待线程时会将该线程的时间配额减1
饥饿线程的优先级提升
- 系统线程“平衡集管理器(balance set manager)”每秒钟扫描一次就绪队列，发现是否存在等待时间超过300个时钟中断间隔的线程
- 平衡集管理器将这些线程的优先级提升到15，并分配给它一个长度为正常值4倍的时间配额
- 当被提升的线程用完它的时间配额后，立即衰减到它原来的基本优先级
ending
