处理机调度与进程死锁
处理机调度与进程死锁笔记整理
处理机调度
1 调度类型
1.1 三类调度
长程调度——作业调度
决定哪个作业可以进入系统
中程调度——内存调度
决定将哪个（些）进程调入内存
换入：取决于管理系统并发度的需求；
换出：进程的存储需求。
短程调度——进程调度
决定哪个进程将获得CPU
- 长程调度程序执行频率较低；
- 中程调度程序执行频率稍高；
- 短程调度程序执行频率最高。
1.2 调度的时机和策略
何时调度？
有任务终止时
处理器的空闲时
终端用户登录时
有更紧急任务到达时
调度哪个？
先来先服务
优先级
实时性
服务时间
I/O需求
1.3 调度算法的评价准则
1.3.1 面向用户，与性能相关
周转时间
从提交到完成之间的时间间隔
响应时间
从提交到开始接收响应之间的时间间隔
截止期限
进程完成的最后期限
1.3.2 面向用户，与性能无关
可预测性
希望提供给用户的服务能够随着时间的流逝展现给用户一贯相同的特性，而与系统执行的其他工作无关。
1.3.3 面向系统，与性能相关
吞吐量
单位时间内完成的进程数目
处理器利用率
处理器处于忙的状态的时间百分比
1.3.4 面向系统，与性能无关
公平性
进程被公平对待
强制优先级
进程被指定优先级，调度策略优先选择高优先级进程
平衡资源
保持系统中所有资源处于繁忙状态，较少适用紧缺资源的进程应该受到照顾
1.4 调度模式
- 抢占（剥夺）——对有实时性或响应时间要求的任务，必须采用抢占式调度
- 非抢占（非剥夺）——对没有响应时间要求的任务，可采用非抢占式调度
1.5 优先级的使用
每个进程被指定一个优先级，调度程序总是选择具有较高优先级的进程。
纯粹的优先级调度方案可能会导致第优先级进程长时间处于饥饿状态
一个进程的优先级可随着它的时间或执行历史而变化
2 调度算法
2.1 几种常用调度算法的比较
| 算法 | FCFS(先来先服务) | RR(轮转) | SPN(最短进程优先) | SRT(最短剩余时间) | HRRN(最高响应比优先) | 优先级高者优先 | 反馈法多队里 |
|---|---|---|---|---|---|---|---|
| 选择依据 | |||||||
| 调度方式 | 非抢占式 | 抢占式（按时间片） | 非抢占式 | 抢占式（进程到达时） | 非抢占式 | 抢占式（时间片） | |
| 响应时间 | 可能很高 | 对于短进程提供良好的响应时间 | 提供较好的响应时间 | 提供较好的响应时间 | 不突出 | ||
| 开销 | 最小 | 低 | 可能高 | 可能高 | 可能高 | 可能高 | |
| 对进程的作用 | 不利于短作业（进程）和I/O繁忙作业 | 公平对待 | 不利于长作业（进程） | 不利于长作业（进程） | 较好均衡个 | 偏爱I/O繁忙型进程 | |
| “饥饿”问题 | 无 | 无 | 可能 | 可能 | 无 | 可能 |
2.2 补充
2.2.1 HRRN
公式：，其中：
R：响应比
w：等待处理器的时间
预计的服务时间
2.2.2 优先级高者优先
- 约定：数小代表优先级高
2.2.3 传统的UNIX调度
多级反馈
每个优先级队列中使用轮转方法
使用1秒抢占方式
每秒都会重新计算每个进程的优先级
2.3 线程调度
负载分配
系统维护一个就绪线程的全局队列，每个处理器只要空闲就从队列中选择一个线程。
组调度
一组相关的线程基于一对一的原则，同时调度到一组处理器上运行。
专用处理器调度
组调度的一种极端形式，在一个应用程序执行期间，把一组处理器专门分配给这个应用程序。
动态调度
某些应用程序允许动态地改变进程中线程数目，需要动态调度。操作系统负责分配处理器给作业，作业自行调度。
3 多机系统与实时系统调度
3.1实时调度
实时计算
系统的正确性不仅取决于计算的逻辑结果，还依赖于产生结果的时间。
实时任务
硬实时任务、软实时任务
周期性任务、非周期性任务
实时系统应用的例子
目前：实验控制、过程控制、机器人、空中交通管制、电信、军事指挥与控制系统。
下一代：自动驾驶汽车、具有弹性关节的机器人控制器、智能化生产中系统查找、空间站和海底勘探。
3.2 实时操作系统的特点
可确定性
按照固定的、预先确定的时间或时间间隔执行操作。
可响应性
为中断提供服务时间。
用户控制
允许用户细粒度地控制任务优先级，指定一些特性等。
可靠性
性能的损失或降低可能产生灾难性的后果。
故障弱化操作
系统在故障时尽可能多地保存其性能和数据的能力。
3.3 实时系统调度的特征
- 快速的进程或线程切换。
- 体积小（只具备最小限度的功能）。
- 迅速响应外部中断的能力。
- 通过诸多信号量、信号和时间之类的进程间通信工具，实现多任务处理。
- 使用特殊的顺序文件，可以快速存储数据。
- 基于优先级的抢占式调度。
- 最小化禁止中断的时间间隔。
- 用于使任务延迟一段固定的时间或暂停/恢复任务的原语。
- 特别的警报和超时设定。
3.4 实时系统调度算法
静态表法
执行关于可行调度的静态分析。分析的结果是一个调度，它用于确定在运行时一个任务何时必须开始执行。
静态优先级抢占法
执行一个静态分析，但是没有制定调度，通过给任务制定优先级，使用传统的基于优先级的抢占式调度。
基于动态规划调度法
在运行时动态地确定可行性，可行性分析的结果是一个调度或规划，可用于确定何时分派这个任务。
动态尽力调度法
不执行可行性分析。系统试图满足所有的最后期限，并终止任何已经开始运行但错过最后期限的进程。
3.5 截止时间调度
实时应用程序通常并不关注绝对速度，它关注的是在最有价值的时间完成（或启动）任务。
截止时间调度：最早最后截止时间优先。
最后期限
开始截止时间：任务必须开始的时间。
完成截止时间：任务必须完成的时间。
3.6 优先级反转
- 在任何优先级调度方案中，系统应该不停地执行具有最高优先级的任务。当系统内的环境迫使一个较高优先级的任务去等待一个较低优先级的任务时，优先级反转就会发生。
- 优先级：，高优先级的被低优先级的占先。
- 解决方案：优先级继承。
进程死锁
1 死锁存在的条件
- 互斥
- 无抢占
- 保持并等待
- 循环等待
