进程调度和死锁
进程调度的时机
- 进程结束运行
- 进程阻塞
- 中断返回
- 在支持抢占式调度的系统中有比当前进程优先级更高的进程到来
- 当前进程时间片用尽
调度算法准则
1.周转时间短 2.响应时间快 3.系统吞吐量高 4.截止时间的保障 5.处理机利用率高
- 周转时间短
- 作业被提交给系统开始到作业完成为止的时间, 包括: 在后备队列上等待调度的时间, 在就绪队列上等待调度的时间, 进程在CPU上执行的时间, 进程等待IO操作完成的时间
- 平均周转时间: T 等于 n个作业的周转时间之和除以n
- \(T = \frac{1}{n} \sum_{i=1}^nT_i\)
- 带权周转时间: 作业的周转时间T与系统为它提供服务的时间 \(T_s\) 之比为 \(W=T/T_s\)
- 平均带权周转时间 \(W = \frac{1}{n} \sum_{i=1}^n \frac{Ti}{Ts}\)
- \(T_s\)是一个作业在CPU上执行的总时间, \(T_i\) 是这个作业的周转时间
- 响应时间快(重要指标): 从用户提交一个请求直至系统首次产生相应的时间为止的一段时间
- 截止时间的保障: 某个任务必须开始执行的最迟时间, 或必须完成的最迟时间
- 系统吞吐量高: 吞吐量单位时间完成的作业数
- 处理机利用率好
先来先服务调度 FCFS
从就绪队列的队首选择最先到达就绪队列的进程, 为它分配CPU
分析
- 适合长进程, 不利于短进程, 平均周转时间长
- 适用于CPU繁忙, 不适用于IO繁忙
短进程优先调度 SPF
从就绪队列中选择估计允许时间最短的进程, 将处理机分配给, 立刻运行直到完成, 或发生某件事被阻塞放弃处理机时再重新调度
分析
- 对比 FCFS: 可以降低进程平均等待时间 提高吞吐量
- 缺点: 对长进程不利, 不能保证紧迫进程的及时处理, 进程的长短根据用户的估计而定, 不一定能做到真正的短进程优先
优先权调度算法 Priority Scheduling Algorithm
抢占式
- 抢占式切换方式
- 立即切换
- 基于时钟中断的抢占策略, 在最近一次时钟中断到来时进行进程切换
非抢占式
难以保障高优先级得到及时调度
- 优先权类型
- 静态优先权
- 动态优先权
- 无穷阻塞问题, 饥饿问题
- 解决方案
- 老化: 逐渐增加在系统中等待时间很长的进程的优先权
- 解决方案
时间片轮转调度算法 RR Round-Robin
早期的时间片轮转调度算法中, 系统将所有的就绪进程按照先来先服务的原则, 排成一个队列, 每次调度把CPU分配个队首进程, 执行一个时间片, 时间片用完后, 终止当前进程, 移送到就绪队列的队尾
- 广泛采用于 UNIX, Linux, Windows
- 时间片大小的确定
- 系统对响应时间的要求: 响应时间越短, 时间片取值越小
- 就绪列队中进程的数目
- 进程越多响应时间越长
- 设定最长响应时间后, 时间片大小与最大进程数成反比
- 系统的处理能力
多级列队调度
进程根据不同的特点分类, 每一类进程属于一个就绪列队
- 将就绪列队分成多个独立列队
- 根据进程的某些属性 如需要占用的内存大小, 进程优先权, 进程被永久的分配到一个列队
- 每个列队有自己的调度算法
- 不同的列队优先权不同, 调度算法也可能不同
多级反馈列队调度
多级队列 固定 分配列队会导致饥饿问题
- 有多个优先权不同的列队, 优先级越高, 时间片越短
- 同一列队采用时间片轮转调度算法
- 使用CPU过多的进程会被移到优先权较低的列队
- 较低优先权列队中等待时间过长的进程会被转移到高优先级列队中
实时系统中的调度
不能满足调度要求时可以加强单个处理机的性能, 或者增加多个处理机
基本条件/实时调度需要具备的条件
- 提供必要的调度信息
- 系统处理能力强
- 采用抢占式调度机制
- 具有快速切换机制
- 提供必要的调度信息
- 就绪时间
- 开始截止和完成截止时间
- 处理时间
- 资源要求
- 优先权
- 系统处理能力强
- 单处理机情况下必须满足的条件
- \(\sum_{i=i}^{m}\frac{C_i}{P_i} <= 1\)
- m 为周期性的硬实时进程, 他们的处理时间为 \(C_i\), 周转时间为 \(P_i\)
- n个处理机的限制条件
- \(\sum_{i=i}^{m}\frac{C_i}{P_i} <= n\)
- 单处理机情况下必须满足的条件
- 采用抢占式调度机制
- 基于时钟中断的抢占式优先权调度算法
- 立即抢占的抢占式优先权调度算法
- 具有快速切换机制
- 对外部中断的快速响应能力
- 快速的进程切换能力
调度算法
- 最早截止时间优先 EDF
- 根据进程的开始截时间确定进程的优先级
- 支持抢占式调度或者非抢占式
- 最低松弛度优先 LLF
- \(L = T - T_c - T_s\)
- \(T\) 截止时间
- \(T_c\) 当前时间
- \(T_s\) 进程还需要的时间
- 把进程按照松弛度排序, 让松弛度最小的进程位于就绪队列队首
进程切换步骤
P98
多处理器调度
分类1 耦合性
- 紧密耦合的多处理系统
- 处理器系统通过高速总线或交叉开关实现多个处理器之间的互联
- 共享 主存储系统 IO设备
- 松弛耦合的多处理系统
- 通常使用通道或通信线路来实现多态计算机之间的互联
- 每个计算机都有自己的存储器和IO设备
分类2 对称性
- 对称多处理器系统(绝大多数大多数)
- 对称多处理器系统进程分配方式
- 静态分配: 每一个处理器建立一个专门的就绪队列
- 动态分配: 动态调度, 每次获得的不一定是同一个处理器
- 对称多处理器系统进程分配方式
- 非对称多处理器系统
进程调度
自调度(最常用)
系统中设有 一个公共 的就绪列队, 任何一个空闲的处理器都可以自行从该就绪列队中选取一个进程或者一个线程来运行
- 优点: 易移植有利于提高CPU的利用率
- 缺点
- 瓶颈问题: 整个系统中只有一个必须互斥访问的公共就绪列队
- 低效性: CPU的高速缓存命中率较低
- 线程切换频繁
成组调度
由系统将一组互相合作的进程或线程同时分配到一组处理器上, 进程与处理器一一对应
- 优点: 减少线程切换 改善系统性能, 减少调度开销
- 时间分配
- 面向所有应用程序平均分配处理器时间
- 面向所有线程平均分配处理器时间
专用处理器分配
- 加速了应用程序的运行速度
- 避免了进程切换
死锁
多个进程竞争 共享资源 而引起的进程不能向前推进的僵死状态
- 死锁原因: 竞争共享资源且分配资源的顺序不当
死锁条件(同时发生):
- 互斥条件: 一个进程在访问资源的过程中, 其他进程不能访问该资源
- 请求和保持条件: 进程以及至少保持了一个资源, 又提出了新的要求, 新请求的i资源已经被占用, 进程阻塞但不释放以获得的资源
- 不剥夺条件: 进程已经获得的资源不能被剥夺只能进程自己释放
- 环路等待条件: 死锁发生时必然存在一个进程申请资源的环形链
处理死锁的预防
- 摒弃请求和保持条件
- 要求一次性申请在整个运行过程所需要的全部资源
- 或一个进程在请求其他资源时要求该进程必须释放以及分配的所有其他资源
- 摒弃不剥夺条件
- 一个已保持了某些资源的进程, 当它再提出新的资源要求而不能立即满足时, 必须释放它已保持的资源
- 摒弃环路等待条件
- 进程必须按照规定的顺序申请资源, 对所有不同类型的资源排序, 要求每个进程按照规定的顺序申请资源
- 缺点
- 限制了新设备增加
- 系统为资源分配的序号与进程时间使用资源的顺序不同, 造成资源浪费
- 给用户编程带来了麻烦
死锁的避免
- 系统的安全状态
- 当系统能找到一个进程执行序列, 只要按照次序列为每个进程分配资源, 就可以保证进程的资源分配和执行顺利完成, 不会发生死锁
- 如果不存在这样一个安全序列那么就处于不安全状态
- 不安全状态不一定就是死锁
- 实质:在于让系统处于安全状态
死锁的检测和解除
- 何时调用检测算法: 死锁可能发生的频率, 死锁发生时受影响的进程数
- 使用资源分配图检测死锁
- 由一组节点和一组边构成, 圆圈代表一个进程, 方框代表资源
- 死锁定理: S为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的
死锁解除
- 进程终止: 终止所有进程 / 一次只终止一个处于死锁的进程
- 资源抢占:
- 抢占那个进程和那些资源
- 回滚
- 饥饿
- 忽略死锁问题