操作系统--进程调度与死锁 |
3. 进程调度与死锁
调度动机与时机
功能
按某种算法从就绪态进程为当前CPU选择其上运行的新进程
时机
进程结束
进程阻塞
中断返回
更高优先级的进程到来
当前运行进程的时间片用完
进程切换 7步
1.保存pc,和其他寄存器的cpu上下文环境
2.更新被替换的进程的pcb
3.修改进程状态,把之形态改为就绪态
4.被替换进程的PCB移到就绪或阻塞队列
5.执行新进程,更新该进程的PCB
6.更新内存管理的数据结构
7.恢复被调度程序选中的进程的硬件上下文
调度算法
选择依据
周转时间短
响应时间快
截止时间的保证
吞吐量高
处理机利用率好
算法类型
1.先来先服务
优点:
利于长进程
利于CPU繁忙型进程(科学计算)
缺点:
不利于短进程
系统平均周转时间比较长
2.短进程优先
优点:
降低进程的平均等待时间
提高系统的吞吐量
缺点:
不利于长进程
不能保证紧迫进程及时处理
进程长短根据用户的估计而定,不一定真正做到短进程优先
3.优先权调度
算法类型
非抢占式
抢占式
优先权类型
静态优先权
动态优先权
问题与方案
无穷阻塞(饥饿)
老化技术
4.时间片轮转
时间片大小确定
响应时间的要求
就绪队列中进程数量
系统的处理能力
5.多级队列调度
将就绪队列分为多个独立队列(永久不可变)
进程某些属性
占内存大小
进程优先权
进程类型
6.多级反馈队列调度
优先权越高,时间片越短
等待时间长的进程会被转移到优先级高的就绪队列
实时系统的调度
基本条件
1、提供必要的调度信息
就绪时间
开始截止时间和完成截止时间
处理时间
资源要求
优先级
2. 系统处理能力强
3.采用抢占式调度机制
基于始终中断抢占
立即抢占
4.具有快速切换机制
对外部中断的快速响应能力
快速的进程切换能力
常用调度算法
最早截止时间有限EDF
最低松弛度优先 LLF
死锁
产生原因
竞争共享资源
分配资源的顺序不当
必要条件
互斥条件
请求和保持
不剥夺
环路等待
处理死锁
预防死锁
摒弃三分之一个必要条件
避免死锁
安全状态
不安全状态
银行家算法
检测并解除死锁
何时调用
死锁可能发生的频率
死锁发生时受影响的进程数量
死锁定理
用于检测资源分配状态S是否为死锁状态
当前仅当S状态的资源分配图是不可完全简化的
死锁的解除
终止进程
1.终止所有死锁进程
2.一次只终止一个处于死锁的进程
资源抢占
1.抢占哪个进程和哪些资源?
死锁进程所拥有的资源数量
2.回滚
回滚到某个安全状态
3.饥饿
进程因长时间不能获得所需要的资源而无线等待
忽略死锁
多处理器调度
类型
耦合度
紧耦合
共享主存储器系统 I/O设备
松耦合
每台都有自己的存储器和I/O
通过通道或通信线路来实现多台计算机间互连
对称
对称
结构类似
非对称
一主多从
进程分配方式
对称
静态分配
为每个处理器建立一个专门的就绪队列
一个进程只在一个处理器上运行
优点
调度开销小
缺点
不能动态的平衡各处理器的负载,忙闲不均
动态分配
每次进程调度获取的不是一个处理器
设置公共就绪队列
优点
考虑了负载平衡
把进程分给当前空闲的处理器
非对称
主机上调度程序,从机上用户程序
优点
系统处理比较简单
缺点
单点问题
进程调度方式
自调度
优点
易移植
cpu利用率高
缺点
瓶颈问题
低效性
线程切换频繁
成组调度
讲一组相互合作的线程或进程分配到一组处理器上
优点
减少线程切换,提高性能
减少调度开销
时间分配
面向所有的应用程序平均分
面向所有的线程平均分
专用处理器分配
每个线程一个专用处理器
一个进程一组专用处理器
优点
加速了应用程序的运行速度
避免了进程切换
缺点
浪费资源