2.4进程调度
第2章课程设计：修改和实现相应功能的调度
进程行为
- 做计算
- 做I/O[磁盘/网络读写]
按CPU计算时间与I/O时间的比例：
- 计算密集型
- I/O密集型
进程的调度一定要 考虑到 负载的特征workload
相应的再实行相应的调度算法
调度时机
- 进程退出
- 进程在I/O或信号量上阻塞
- 创建新进程
- I/O中断发生
- 时钟中断发生
- 抢占式：执行时可以被打断
- 非抢占式
调度算法
- 操作系统决定进程运行的向后顺序
- 调度器：执行
- 调度算法：如何调度
不同的应用场景：[很难有普适的适用于任何场景的调度算法]
- 批处理系统
- 交互式系统
- 实时系统
目标
- 共同的目标：公平策略强平衡
- 批处理系统：最大的吞吐量(批处理没有交互，单位时间内能处理更多，即最大化CPU利用率)
- 交互式系统：立刻有相应，最小化响应时间，均衡性
- 实时系统：截止时间、可预测性(第二次课程设计)
性能指标
面向时间
吞吐量/CPU利用率/各种设备的均衡利用
面向系统
同样的硬件集群好的调度算法可能给10000个用户提供服务
批处理系统调度
先来先服务FCFS
是比较基础的方法
短作业
预计执行时间短的作业进行CPU的分派。
SJF的变形
最短剩余时间优先
最高响应比优先HRRN
响应比：(等待时间+要求执行时间)/要求执行时间
多级调度(三个层次上进行调度)
- 准入调度
- 内存调度
- CPU调度
交互式系统调度
时间片轮转(Round Robin)
- 将系统中所有就绪的进程按照FCFS形成队列
- CPU让进程执行时间片
- 在时间片结束时，发生时钟中断
- 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
- 进程可以未使用完一个时间片，就出让CPU(如阻塞)
时间片长度的确定
时间片长度变化的影响
- 过长->退化为FCFS
- 过短->context switch的开销变大了
对响应时间的要求：
响应时间=进程数目$\times$时间片长度
Trade off between those 2.
影响时间片长度的因素：
- 就绪进程的数目
- 系统的处理能力
优先级调度
谁的优先级高，先调度谁
- 静态优先级
- 动态优先级：在运行时做相应的优先级调整
多类优先级调度
在各类之间采用优先级调度，而各类进程内部采用时间片轮转调度。
多重队列
彩票调度
公平分享调度
实时系统调度
实时调度系统氛围硬实时和软实时
可调度的实时系统
针对多周期的事件流：
若有周期性事件m个，事件i的周期为Pi,其中每个事件需要Ci秒的CPU时间，
$\sum_{i=1}^m\frac{C_i}{P_i}\le1$
调度策略与机制
- 将调度问题分解为调度策略与调度机制
线程调度
- 线程的实现方式决定线程的调度模式：
- 用户
- 内核
- 用户级线程的阻塞会引起整个进程的阻塞
- 在用户级线程方式下，可以为应用定制特定的调度器
2.5 MINIX3进程概述
minix3系统结构
minix3微内核结构，是一组进程的集合，内核功能较少，更多的功能由用户进程实现，进程间通过IPC机制进行通信。
minix3的四层结构
Kernel 层
Device drivers
Server process
User process
内核层
- 负责进程的调度
- 时钟任务
- 系统任务读写I/O，跨地址空间复制数据
- C+汇编
设备驱动层
- 读写I/O端口的数据
- 不同类型设备需要相应的设备驱动程序
- 也可以调用其他内核调用
服务器层
- 进程服务器
- 创建，终止进程:fork, exec,wait
- 信号相关的系统调用:alarm,kill
- 管理内存,brk
- 文件系统服务器
- 执行文件系统的调用,read,mount,chdir
- 再生服务器
- 启动或重启相关的设备驱动程序
用户进程层
- 包含所有的用户进程
- Shell，编辑器，编译器等工具程序
- 用户运行的程序
- 守护进程
设备驱动层和服务器层的进程称为系统进程，是操作系统的组成
内核>设备>服务器>用户
Minix系统启动
启动顺序
Bootstrap[引导程序]->boot(boot image)->Kernel->系统任务、时钟任务->系统进程->Init进程->其它用户进程及…
引导映像(boot image)
- 由boot装载至内存的适当位置
- 包括多个：内核、进程管理器、filesystem
- 每个部分都是独立的程序
进程树初始化
- init进程
MINIX进程间通讯
IPC原语
- 内核将消息从发送者复制到接受者
- 系统进程，时钟任务，系统任务只允许与特定的进程通信
- 当一个进程发送消息，而目标进程尚未开始接收消息时，发送进程将阻塞。
1 | send(dest,&message) |
notify原语
不会阻塞
对于系统进程，用位图来记录其他系统进程发给它的通知
MINIX进程调度
minix3采用多级排队系统，定义为16个队列[16个优先级]
系统任务和时钟任务最高优先级
IDLE最低
当系统无其余有效或就绪时，会使空闲进程在上面跑。
一个进程可以根据不同需要在不同优先级的队列中移动
只有高优先级的队列中没有就绪进程时，才运行低优先级的进程队列。
不同的优先级的时间片长度不一
- 驱动程序进程和服务器进程需要运行其至阻塞
使用一个改进的轮转调度算法
- 进程转为非就绪时，从队列中取出，当它再变回就绪时，将其放在队首，分配的时间片 为上次时间片中的剩余时间
实现不同的调度功能
