【操作系统】(六):处理机调度和死锁
【操作系统】(六):处理机调度和死锁
处理机调度的层次
高级调度:作业一开始阶段——决定那几个作业调入内存——多道批处理系统
低级调度:决定就绪队列中哪个进程应获得处理机——多道批处理、分时、实时都要有
中级调度:提高内存利用率和系统吞吐量
处理机调度算法的目标
处理机调度算法的共同目标
- 资源利用率
C P U 的 利 用 率 = C P U 有 效 工 作 时 间 C P U 有 效 工 作 时 间 + C P U 空 闲 等 待 时 间 CPU的利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间} CPU的利用率=CPU有效工作时间+CPU空闲等待时间CPU有效工作时间 - 公平性
- 平衡性
- 作业强制执行
批处理系统目标
- 平均周转时间短
- 系统吞吐量高(单位时间里完成作业的数量)
- 处理机利用率高
分时系统目标
- 响应时间快
- 均衡性
实时系统的目标
- 截止时间的保证
- 可预测性
作业调度
选择几个作业进入内存
批处理系统中的作业
作业:包含了通常的程序和数据,还配有一份作业说明书
作业步:作业运行期间,每个作业发生的若干个相对独立,又相互关联的顺序加工步骤
上一个作业步的输出作为下一个作业步的输入
作业运行的三个阶段和状态
- 收容阶段——用户提交的作业到后备中
- 运行阶段——就绪状态到运行结束(就绪、阻塞、运行)
- 完成状态——作业运行完成、或发生异常提前结束
作业调度的主要任务
- 接纳多少个作业
- 接纳哪些作业
先来先服务(FCFS)
根据作业到达系统的时间,优先考虑在系统中等待时间最长的作业
完成时间=到达时间+服务时间
周转时间=作业完成时刻-作业到达时刻;
带权周转时间=周转时间/服务时间;
平均周转时间=作业周转总时间/作业个数;
平均带权周转时间=带权周转总时间/作业个数
短作业优先(SJF)
作业越短,优先级越高
当前时间到达的最短作业
优先级调度算法
作业等待时间就是作业的优先级,等待时间越长,优先级越高
基于作业的紧迫程度,由外部赋予作业相应的优先级,根据该优先级调度
高响应比优先调度算法
即考虑了作业等待时间,又考虑了作业运行时间的调度算法
等待时间相同时,类似于短作业优先
服务时间相同,类似于先来先服务
但是计算开销较大
进程调度
就绪队列上的进程,选择一个分配CPU
进程调度的任务
- 保存处理机的现场信息
- 按某种算法选取进程
- 处理机分配给进程
进程调度的机制
进程调度方式
- 非抢占方式——一直运行
- 抢占方式——暂停正在执行,重新分配另一个进程
轮转调度算法
按FCFS排成一个就绪队列,每隔30ms便产生一次中断,每个程序分给你一个时间片,有两种情况:
- 时间片还没有用完,立即**调度程序,删除,再启动一个新的时间片
- 没运行完的送至队尾
时间片的选择:q=1太短又频繁,q=4太长退化成FCFS
略大于
典型交互时间比较好
优先级调度算法
把处理机分配给就绪队列中优先级最高的进程
算法类型:
- 非抢占式优先级调度算法
- 抢占式优先级调度算法
优先级类型: - 静态优先级——进程的整个优先级不变
- 动态优先级——要变
多队列调度算法
多个队列
手机上有考点
死锁
一组进程中的每一个进程都在等待该组进程中的其他进程才能引发的事件,改组则是死锁的
资源问题
- 可重用的资源和可消耗资源
可供用户重复使用,但是不允许多个进程共享 - 可抢占和不可
某进程获得后,还可以收回
引起死锁
- 竞争不可抢占资源
- 竞争可消耗资源
- 进程推进次序不当
死锁必要条件
- 互斥条件——资源互斥性
- 请求和保持条件——保持了某个资源再请求
- 不可抢占条件
- 循环等待条件——每个进程