导图社区 计算机操作系统第三章:处理机调度与死锁
计算机操作系统思维导图,包含了处理机调度算法的目标、调度算法、实时调度、死锁概述、预防死锁等内容。
社区模板帮助中心,点此进入>>
英语词性
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
法理
刑法总则
【华政插班生】文学常识-先秦
【华政插班生】文学常识-秦汉
文学常识:魏晋南北朝
【华政插班生】文学常识-隋唐五代
【华政插班生】文学常识-两宋
第三章:处理机调度与死锁
处理机调度算法的目标
处理机调度的层次
高级调度(作业调度)
中级调度(和挂起有关)
低级调度(进程调度)
低级调度的三个基本机制
排队器
分派器
上下文切换
进程调度方式
非抢占方式
抢占方式
优先权原则
短进程优先原则
时间片原则
进程调度的算法
优先级调度算法
优先级调度算法的类型
非抢占式优先级调度算法
抢占式优先级调度算法
优先级的类型
静态优先级
动态优先级
轮转调度算法
多队列调度算法
多级反馈队列调度算法
基于公平原则的调度算法
处理机调度算法的共同目标
资源利用率:CPU的利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
公平性
平衡性
策略强制执行
批处理系统的目标
平均周转时间短
系统吞吐量高
处理机利用率高
分时系统的目标
响应时间快
均衡性
实时系统目标
截止时间的保证
可预测性
调度算法
作业
作业不仅包含程序和数据,还配有一份作业说明书,系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。
作业运行的三个阶段
收容阶段
运行阶段
完成阶段
作业运行的三个状态
后备状态
运行状态
完成状态
作业调度的主要任务
接纳多少个作业
接纳哪些作业
先来先服务(first–come first–served,FCFS)调度算法
高响应比优先调度算法(Highest Response Ratio Next,HRRN)
实时调度
实现实时调度的基本条件
提供必要信息
系统处理能力强
采用抢占式调度机制
具有快速切换机制
实时调度算法的分类
非抢占式调度算法
非抢占式轮转调度算法
非抢占式优先调度算法
抢占式调度算法
基于时钟中断的抢占式优先级调度算法
立即抢占的优先级调度算法
最早截止时间优先EDF(Earliest Deadline First)算法
最低松弛度优先LLF(Least Laxity First)算法
优先级倒置(Priority inversion problem)
死锁概述
定义:如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件,那么该组进程是死锁的
产生死锁的必要条件
互斥条件
请求和保存条件
不可抢占条件
循环等待条件
如果每个资源只有一个实例,则环路等待条件是死锁存在的充分必要条件
预防死锁
静态方法,在进程执行前采取的措施,通过设置某些限制条件,去破坏产生死锁的四个条件之一,防止发生死锁。
预防死锁的策略
破坏"请求和保存"条件
第一种协议
第二种协议
破坏"不可抢占"条件
破坏"循环等待"条件
避免死锁
动态的方法,在进程执行过程中采取的措施,不需事先采取限制措施破坏产生死锁的必要条件,而是在进程申请资源时用某种方法去防止系统进入不安全状态,从而避免发生死锁。如银行家算法
避免死锁的策略
系统安全状态
利用银行家算法避免死锁
银行家算法中的数据结构
可用资源向量 Available[m]:m为系统中资源种类数,Available[j]=k表示系统中第j类资源数为k个。
最大需求矩阵 Max[n,m]:n为系统中进程数,Max[i,j]=k表示进程i对j类资源的最大需求数为中k。
分配矩阵 Allocation[n,m]:它定义了系统中每一类资源当前已分配给每一进程资源数, Allocation[i,j] = k表示进程i已分得j类资源的数目为k个。
需求矩阵 Need[n,m]:它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程i 还需要j类资源k个。Need[i,j]=Max[i,j] - Allocation[i,j]
银行家算法
安全性算法
银行家算法之例
死锁的检测与解除
死锁的检测
资源分配图
简化步骤
选择一个没有阻塞的进程p
将p移走,包括它的所有请求边和分配边
重复步骤1,2,直至不能继续下去
死锁定理
若一系列简化以后不能使所有的进程节点都成为孤立节点
检测时机
当进程等待时检测死锁 (其缺点是系统的开销大)
定时检测
系统资源利用率下降时检测死锁
死锁检测中的数据结构
死锁的解除
抢占资源
终止(或撤销)进程
终止进程的方法
终止所有死锁进程
逐个终止进程
代价最小
付出代价最小的死锁解除算法
是使用一个有效的挂起和解除机构来挂起一些死锁的进程