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