处理机调度与死锁
2022-03-13 15:04:34 1 举报AI智能生成
处理机调度与死锁
作者其他创作
大纲/内容
资源供应不足而导致出现死锁
CPU
RAM
可剥夺资源
打印机
磁带机
不可剥夺资源
资源分类
竞争资源
进程间推进顺序非法
产生死锁的原因
互斥条件
请求和保持条件
不剥夺掉件
环路等待条件
产生死锁必要条件
死锁概述
互斥条件无法破坏，由资源性质决定
所有进程运行前必须一次性申请完所有需要资源
简单易实现，安全性高
优点
资源浪费，进程延迟运行
缺点
破坏请求和保持条件
等价于“被剥夺”，但实现复杂，系统代价高
破坏不剥夺条件
各类资源按序排列，并赋予不同序号，资源申请按序号提出
各类资源必须相对稳定，会限制新资源的增加
进程使用资源顺序与系统规定不同会导致资源浪费
限制用户简单编程
破坏循环等待条件
破坏死锁的必要条件
预防死锁
允许进程动态申请资源
一定不会出现死锁
安全状态
有可能发生死锁
不安全状态
系统分配资源前先进行安全计算
让系统处于安全状态，实质是系统在资源分配时，如何使得系统不进入不安全状态
基本思想
确保每次分配都不会进入不安全状态
可用资源向量Available
最大需求矩阵MAx
分配矩阵Allocation
需求矩阵Need
数据结构
银行家算法
安全性算法
具体实现
避免死锁
检测死锁
解除死锁
处理死锁的基本方法
死锁
资源分配不均、不合理
原因
按一定算法，将外存中作业调入内存，并创建进程
主要功能
用户希望自己作业周转时间少
系统希望作业平均周转时间少
满足用户要求，并满足系统要求，提高CPU利用率和系统吞吐量
要求
取决于多道程序度
接纳多少作业
取决于调度算法
接纳哪些作业
两大问题
作业调度算法
比程序更广的概念：包含程序+数据+作业说明书，调入内存的基本单位
作业job
加工作业的一个基本步骤
编译
连结装配
运行
经典三步
作业步job step
作业和作业步
保存系统对作业管理和调度的全部信息
作业在系统中的唯一标志
作业标识
资源需求
内容
作业控制块JCB
高级调度：又叫作业调度/长程调度
是最基本的一种调度，且运行频率最高
决定就绪队列中进程获得CPU
保存处理机的现场信息
按算法选取进程
把处理机分配给进程
非抢占式
抢占式
进程调度方式
低级调度：又叫进程调度/短程调度
主要负责内外存对换
提高内存利用率和系统吞吐量
引入目的
把暂时不能运行的进程调至外存上等待，变为挂起状态（静止就绪或驻外存状态）
当进程处于静止就绪且内存空闲时，把外存的进程调度内存，并改状态位为活动状态
功能
实质就是存储器管理中的对换功能
中级调度：又叫内存调度
处理机调度层次
面向用户准则
面向系统准则
选择调度方式准则
取决于操作系统的类型和目标
提高资源利用率（系统吞吐量高）
公平性（进程轮转平等）
各资源平衡利用（提高设备利用率）
策略强制执行
共同目标
周转时间 = 等待时间 + 运行时间 = 作业完成时刻 - 作业提交时刻
平均周转时间 = （T1 +...+ Tn）/n
带权周转时间 = 周转时间/CPU执行时间
周转时间短
单位时间完成作业数高
系统吞吐量高
批处理系统目标
响应时间快
响应时间与请求复杂度相适应
均衡性
分时系统目标
开始截止时间（必须开始最迟时间）
完成截止时间（必须完成最迟时间）
截止时间保证（实时系统性能重要指标）
可预测性（希望连续）
实时系统目标
算法目标
调度的目标
调入最先进入队列的进程或作业
用于作业调度和进程调度
比较有利于长作业，不利于短作业
有利于CPU繁忙，不利于I/O繁忙
特点
先来先服务FCFS
短作业优先SJF
短进程优先SPF
每次选运行时间最短的调入
对长进程不利
没有考虑紧迫程度
运行时间难以估计
短作业/进程优先调度
为了照顾紧迫型作业
创建进程后不再改变
静态
基于某种原则使得优先权随时间而变动
动态
优先权类型
优先权P = 1 + T等待/T服务
作业等待时间相同，服务时间越短，优先权越高
服务时间相同，优先权随等待时间改变，等待越久，优先级越高
每次调度前，需要做响应比计算，增加了系统开销
高响应比优先调度算法
高优先权调度算法
就绪队列按FCFS原则排成队列，每次调度分配CPU給对首进程，执行一个时间片后轮转
基本原理
响应时间的要求/就绪进程数目/系统处理能力
时间片大小确定
时间片轮转法
设置多个就绪队列，并赋予不同优先级，各队列时间片大小不同
时间片轮转法和优先级算法的综合发展
终端性作业用户
短批出来作业用户
长批处理作业用户
满足各类型用户需求
多级反馈队列调度算法
基于时间片的轮转调度算法
调度算法
保存处理机现场信息
按某算法选取进程
进程调度任务
排队器（按算法排）
分排器Dispatcher（依据调度程序选进程）
上下文切换器（执行load和store）
相应机制
处理机分配后直到运行完才分配处理机给其他进程
实现简单，系统开销小
难以满足紧急任务的要求，无法立即执行
根据某种原则暂停正在执行的进程，重新分配给其他进程
能满足实时任务的需求
优点：
调度所付出的开销较大
优先权原则
短作业优先原则
时间片原则
原则
进程调度
就绪时间
开始截止时间和完成截止时间
处理时间
资源要求
优先级
提供必要调度信息
m个任务处理时间除以周期之和小于1
多处理机系统
条件
系统处理能力强
采用抢占式调度机制
具有快速切换机制
实现实时调度的基本条件
硬实时调度算法
软实时调度算法
任务性质
非抢占调度算法
抢占调度算法
调度方式
静态调度算法
动态调度算法
调度时间
集中式调度
分布式调度
多处理机环境
实时调度算法分类
根据任务开始截止时间确定任务的优先级
保持一个实时任务就绪队列，按任务截止时间排序
用于抢占式或非抢占式
固定优先级可能导致某些优先级低的进程错过
最早截止时间优先算法（EDF）
根据任务紧急/松弛程度来确定优先级
任务越紧急优先级越高
主要用于抢占式
松弛度 = 必须完成时间 - 运行时间 - 当前时间
注意：要确定算法查看时间的间隔大小
最低松弛度优先算法（LLF）
常用实时调度算法
实时调度
处理机调度
处理机调度与死锁
0 条评论
回复 删除
下一页
