操作系统第三章--处理机调度与死锁
操作系统第三章--处理机调度与死锁
- 处理机调度的基本概念
- 高级、中级和低级调度
- 进程调度
- 解决问题
- WHAT：按什么原则分配CPU--调度算法
- WHEN：何时分配CPU--调度的时机
- HOW：如何分配CPU--调度过程及进程的上下文切换
- 主要功能
- 按某种算法选取进程（调度）
- 保存处理机的现场信息（上下文切换第一步）
- 把处理器分配给进程（上下文切换第二步）
- 三个机制
- 排队器
- 分派器（调度程序）
- 上下文切换机制
- 调度方式
- 非抢占方式：进程不会抢占其他进程已经分派的处理机
- 抢占方式：允许调度程序暂停正在执行的进程
- 抢占原则
- 优先权原则
- 短作业优先原则
- 时间片原则
- 解决问题
- 调度队列模型和调度准则
- 调度队列模型
- 仅有进程调度的调度模型
- 在给定时间片内完成：进入完成状态
- 在给定时间片内未完成：回到就绪队列的末尾
- 因为某事件被阻塞：进入阻塞队列
- 具有高级和低级调度的调度队列模型
- 按照作业调度算法，从外存的后备队列中选择一批作业调入内存，建立进程送入就绪队列
- 具有三级调度的调度队列模型
- 就绪状态分为内存就绪（表示进程在内存中就绪）和外存就绪（进程在外存中就绪）
- 仅有进程调度的调度模型
- 选择调度方式和调度算法的准则
- 调度目标
- 提高处理机的利用率
- 提高系统吞吐量
- 尽量减少进程的响应时间
- 防止进程长期得不到运行
- 准则
- 面向用户的准则
- 周转时间短
- 响应时间快
- 截至时间的保证
- 优先权准则
- 面向系统的准则
- 系统吞吐量高
- 处理机利用率高
- 各类资源的平衡利用
- 面向用户的准则
- 调度目标
- 调度队列模型
- 调度算法
- 先来先服务FCFS（批处理系统）
- 按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度
- 短作业（进程）优先SJ(P)F
- 短作业优先SJF：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行
- 短进程优先SPF：从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度
- 优先权调度算法PSA
- 非抢占式优先权算法（用于批处理、要求不严的实时）
- 抢占式优先权调度（用于要求严格的实时、性能要求较高的批处理和分时）
- 优先权的类型
- 静态优先权：创建进程时确定，运行期间不再变化
- 进程类型
- 进程对资源的需求
- 用户要求
- 动态优先权：权重动态变化
- 静态优先权：创建进程时确定，运行期间不再变化
- 高响应比优先调度算法（动态优先权机制）HRRN
- 优先权随着等待时间的增加而增大
- 优先权=（等待时间+要求服务时间）/要求服务时间
- 基于时间片的轮转调度算法
- 时间片轮转法
- 所有就绪进程按照先来先服务原则，排成队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片；当时间片用完时，由一个计时器发出时钟中断请求，调度程序把它送往就绪队列的末尾。
- 时间片大小的确定
- 太大：退化成FCFS
- 太小：切换开销大
- 考虑因素
- 系统对响应时间的要求
- 就绪队列中的进程数目
- 系统的处理能力
- 时间片轮转法
- 混合多种调度算法--多级队列调度
- 多个就绪队列，不同的队列采用不同调度方法
- 前台的就绪队列是交互性作业的进程，采用时间片轮转
- 后台的就绪队列是批处理作业的进程，采用优先权或短作业优先算法
- 调度方式
- 优先调度前台
- 分配占用CPU的时间比例
- 更成熟的多级队列调度--多级反馈队列
- 任务可以在队列之间移动，更细致的区分任务
- 调度算法
- 设置多个就绪队列，并为各个队列赋予不同的优先级；规定在优先权越高的队列，每个进程的时间片就越小
- 一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度；若将该时间片内未完成，则移入下一队列
- 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行
- 基于公平原则的调度算法
- 保证调度算法（CPU分配给比率最小的进程）
- 进程获得CPU的时间比率=进程已经执行的时间/（进程创建以来经历的时间/n）
- 公平分享调度算法
- 以用户为单位进行调度，保证公平
- 保证调度算法（CPU分配给比率最小的进程）
- 先来先服务FCFS（批处理系统）
- 实时调度
- 实现实时调度的基本条件
- 提供必要的调度信息
- 就绪时间
- 开始截止时间和完成截止时间
- 处理时间
- 资源要求
- 优先级
- 系统处理能力强
- 调度条件：（处理时间/周期时间）之和小于1
- 采用抢占式调度机制
- 具有快速切换机制
- 具有快速响应外部中断的能力
- 快速的任务分派能力
- 提供必要的调度信息
- 实时调度算法的分类
- 非抢占式调度算法
- 非抢占式轮转调度算法
- 非抢占式优先权调度算法
- 抢占式调度算法
- 基于时钟中断的抢占式优先权调度算法
- 立即抢占的优先权调度算法
- 非抢占式调度算法
- 常用的几种实时调度算法
- 最早截止时间优先EDF
- 优先级确定：根据任务的开始截止时间来确定任务的优先级，截止时间越早，优先级越高
- 实时任务就绪队列：按各任务截止时间的早晚排序
- 调度顺序：选择就绪队列中的第一个任务
- 适用范围：抢占式、非抢占式
- 最低松弛度优先LLF
- 松弛度=完成截止时间-剩余运行时间-当前时间
- 松弛度最小的任务排在队列最前面，最早执行
- 可抢占调度
- 抢占时机：当等待任务的松弛度值为0时才进行抢占
- 最早截止时间优先EDF
- 实现实时调度的基本条件
- 产生死锁的原因和必要条件
- 死锁：多个进程因竞争资源或相互通信而造成的一种僵局，都在等待着对方释放出自己所需的资源，但同时又不释放出自己已经占用的资源
- 产生死锁的原因
- 竞争资源
- 竞争不可抢占性资源
- 竞争临时性（消耗性）资源
- 进程间推进顺序不当
- 竞争资源
- 产生死锁的必要条件
- 互斥条件：排它性使用
- 请求和保持条件：保持资源的进程提出新的资源请求
- 不剥夺条件：进程已获得的资源，不可剥夺
- 环路等待条件：存在进程-资源的环形链（有环路不一定死锁）
- 处理死锁的基本方法
- 预防死锁
- 避免死锁
- 检查死锁
- 解除死锁
- 预防死锁的方法
- 摒弃“请求和保持”条件
- 协议1：系统要求所有进程一次性申请需要的全部资源
- 协议2：允许一个进程只获得运行初期所需的资源便开始运行，运行过程中再逐步释放已分配给自己的、且使用完毕的资源，然后请求新的资源
- 摒弃“不剥夺”条件
- 已经保持资源的进程，提出新的资源要求不能被满足时，应释放已有资源
- 摒弃“环路等待”条件
- 系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，按序号递减的次序释放
- 摒弃“请求和保持”条件
- 避免死锁
- 安全状态：系统能按某种进程顺序（安全序列），来为每个进程分配其所需资源，直到满足每个进程对资源的最大需求
- 利用银行家算法避免死锁
- 银行家算法思想--死锁避免策略
- 当前状态下，某进程申请资源
- 系统假设将资源分给该进程，满足它的需求
- 检查分配后的系统状态是否是安全的，如果是安全，就确认本次分配；如果是不安全的，就取消本次分配并阻塞该进程
- 银行家算法中的数据结构
- 可利用资源向量Available[j]
- 最大需求矩阵Max
- 分配矩阵Allocation
- 需求矩阵Need
- 银行家算法
- 1. if Request[j]<=Need[i,j], turn step 2
- 2. if Request[j]<=Available[j], turn step 3
- 3. try to allocate resource to process
- 4. execute secutity algorithm
- 安全性算法Security Algorithm
- 设置两个向量
- 工作向量Work：表示系统可提供给进程继续运行所需的各种资源数目，Work=Available
- Finish：表示系统是否有足够的资源分配给进程，使之运行成功
- Finish[i] = false；Need[i,j]<=Work[j]；
- Work[j] = Work[j] + Allocation[i,j]；Finish[i] = true；
- 设置两个向量
- 银行家算法思想--死锁避免策略
- 死锁的检测与解除
- 死锁的检测
- 资源分配图
- 1. 先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的（系统有足够的空闲资源分配给它）
- 2. 把不阻塞的进程的所有边都去掉，形成一个孤独的点，再把系统分配给这个进程的资源回收回来
- 3. 看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点
- 4. 所有资源和进程都变成孤立的点
- 如果一个图可以完全简化，则不会产生死锁
- 死锁定理：S为死锁状态当且仅当S状态的资源分配图是不可完全简化的
- 资源分配图
- 死锁的解除
- 剥夺资源
- 撤销进程
- 最小代价原则
- 死锁的检测