导图社区 处理机调度与死锁知识点总结
操作系统之处理机调度与死锁知识点总结，归纳了作业与作业调度、进程调度、实时调度、预防死锁等相关内容，知识全面详细，干货满满，赶紧收藏！
操作系统之磁盘存储器管理知识点总结，归纳了外存的组织方式、文件存储空间的管理、数据一致性控制等相关内容，知识全面详细，干货满满，赶紧收藏！
操作系统之文件管理知识点总结，归纳了文件和文件系统、文件的逻辑结构、文件目录、文件共享等相关内容，知识全面详细，干货满满，赶紧收藏！
操作系统之输入输出系统知识点总结，归纳了I/O系统的功能、模型和接口，I/O设备和设备控制器，设备驱动程序等相关内容，知识全面详细，干货满满，赶紧收藏！
社区模板帮助中心，点此进入>>
英语词性
法理
刑法总则
【华政插班生】文学常识-先秦
【华政插班生】文学常识-秦汉
文学常识：魏晋南北朝
【华政插班生】文学常识-隋唐五代
民法分论
日语高考動詞の活用
第14章DNA的生物合成读书笔记
处理机调度与死锁
3.1处理机调度的层次和调度算法的目标
处理机调度的层次
高级调度（作业调度）
又称为长程调度、作业调度
作业调度用于决定把外存 上处于作业后备队列上的哪些作业 调入内存 ，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。
高级调度主要用于批处理系统，分时系统 和 实时系统 无 需作业调度。
在每次执行作业调度时，都须做出以下两个决定
接纳多少个作业
接纳哪些作业
低级调度（进程调度）
又称进程调度、短程调度
进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。
中级调度
又称中程调度
引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量
把那些暂时不能运行的进程调至外存上去等待，此时进程状态称为挂起状态
当这些进程重新具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，放入就绪队列上等待进程调度。
三级调度

处理机调度算法的目标
处理机调度算法的共同目标
资源利用率
公平性：进程能合理获得CPU 时间
平衡性：系统资源利用的平衡性
策略强制性：对所指定的策略必须执行，如安全策略
批处理系统的目标
平均周转时间：
平均带权周转时间
Ti 作业 i 的周转时间； Ts 作业的服务时间
系统吞吐量高
评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系
处理机利用率高
对于大中型多用户系统，由于CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的十分重要指标，
分时系统的目标
响应时间快
响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间
均衡性
复杂任务响应时间长，简单任务短，做到响应时间与任务复杂度相适应
实时系统的目标
截止时间保证
截止时间是某任务必须执行的最迟时间，或完成的最迟时间。
可预测性
为下一步处理提前准备
3.2作业与作业调度
批处理系统中的作业
作业和作业步
作业控制块
为每个作业设置一个JCB，保存了对作业管理调度的全部信息。是作业存在的标志。
作业运行的三个阶段和三种状态
三个阶段
收容：作业输入到硬盘，建立JCB ，放入后备队列
运行：分配必要资源，建立进程
完成：作业完成或异常退出，回收资源，输出结果
三种状态
后备状态
运行状态
完成状态
作业调度的主要任务
从后备队列调入若干作业
调入越多，有利于提高CPU利用率和吞吐量；但会内存紧张，导致平均周转时间延长
需要根据计算机系统规模，内存多少，运行速度和作业大小做适当选择
从后备队列中选择哪些作业调入内存，取决所采用的调度算法
先来先服务（FCFS）和短作业优先（SJF）调度算法
先来先服务调度算法FCFS
最简单的调度算法， 按先后顺序进行调度， 作业进程都适合
按照作业提交或进程变为就绪状态的先后次序，分派CPU
当前作业或进程占用CPU ，直到执行完或阻塞，才出让 CPU （非抢占方式）。
在作业或进程唤醒后（如I/O 完成），并不立即恢复执行，通常等到当前作业或进程出让出CPU
特点
比较有利于长作业，而不利于短作业。
有利于CPU 繁忙的作业，而不利于 I/O 繁忙的作业
短作业优先调度算法SJF
对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业
优点
比FCFS 改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
提高系统的吞吐量
缺点
对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级；
难以准确估计作业（进程）的执行时间，从而影响调度性能
FCFS和SJF调度算法的性能
优先级调度算法和高响应比优先调度算法
优先级调度算法（PSA）
高响应比优先调度算法（HRRN）
在每次选择作业投入运行时，先计算此时后备作业队列中每个作 业的响应比RP然后选择其值最大的作业投入运行
如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业
当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机
3.3进程调度
进程调度的任务、机制和方法
进程调度的任务
保持处理机现场信息
按某种算法选取进程
把处理机分配给进程
进程调度机制
排队器
分派器
上下文切换
进程调度方式
非抢占式优先权算法
抢占式优先算法
轮转调度算法
轮转法的基本原理
就绪进程按先来先服务的原则排成一个队列，调度时，把CPU分配给队首进程，执行一个时间片，就绪队列中的所有进程均能获得一时间片的处理机执行时间。
时间片的大小从几ms到几百ms
进程切换机制
时间片未用完，进程完成
时间片到，进程未完成
时间片大小的确定
q越大 → 先来先服务
q越小 → 有利于短作业，但进程切换所花费的开销越大
一般选择：q 略大于一次交互所需要的时间，使大多数进程在一个时间片内完成
优先级调度算法
优先级调度算法的类型
优先级的类型
静态优先权
优先权是在创建进程时确定的，且在进程的整个运行期间保持不变
依据
进程类型（系统进程优先级较高）
对资源的需求（对 CPU 和内存需求较少的进程，优先级较高）
用户要求（紧迫程度和付费多少）
动态优先权
动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随 其等待时间的增加而改变的，以便获得更好的调度性能。
多队列调度算法
多级反馈队列
调度机制
调度算法的性能
多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展
为提高系统吞吐量和缩短平均周转时间而照顾短进程
为获得较好的I/O 设备利用率和缩短响应时间而照顾 I/O 型进程
不必估计进程的执行时间，动态调节
基于公平原则的调度算法
保证调度算法
公平分享调度算法
例如用户1有4个进程A、B、C、D，用户2有1个进程E，为保证用 户获得相同处理机时间，则调度方式如下 A E B E C E D E A E B E C E D E ….
例题（ppt）
3.4实时调度
实现实时调度的基本条件
提供必要的信息
就绪时间。（周期和非周期任务情况下，都是可以预知的）
开始截止时间和完成截止时间。
处理时间。
资源要求。
优先级。
系统处理能力强
采用抢占式调度的机制
具有快速切换机制
对外部中断的快速响应能力
快速硬件中断机构
快速的任务分派能力
系统中每个运行功能单位适当的小，减少任务切换时间
实时调度算法的分类
非抢占式调度算法
抢占式调度算法
最早截止时间优先EDF算法
非抢占式调度方式用于非周期实时任务
抢占式调度方式用于周期实时任务
最低松弛度优先LLF算法
优先级倒置
优先级倒置的形成
优先级倒置的解决方法
1、将程序代码进行适当的组织安排，避免优先级倒置的发生（确 保临界资源不被处于不同优先级的线程所共享）
2、优先级置顶协议（priority ceiling protocol）:占有互斥资源的进程 在运行时的优先级比任何其它可以访问该互斥资源的进程的优先级 都要高。
3.5死锁概述
资源问题
可重用性资源和消耗性资源
每个可重用资源的单元只能分配给一个进程使用，不允许多进程共享
进程使用时，必须按照请求资源，使用资源，释放资源的顺序
可重用资源的单位数量是相对固定，进程不能创建和删除
可抢占性资源和不可抢占性资源
可抢占性资源：CPU ，内存
不可抢占性资源：光驱，打印机
计算机系统中的死锁
竞争不可抢占性资源引起的死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁
死锁的定义、必要条件和处理方法
死锁的定义
多个进程在运行过程中因为竞争资源而造成的一种僵局，其中，每个进程继续执行需要获得另一个进程占有的资源，结果，若无外力作用，所有进程都不能继续执行
产生死锁的必要条件
互斥条件
不可抢占条件
请求和保持条件
环路等待条件
处理死锁的方法
死锁的预防
静态方法，在进程执行前采取的措施，通过设置某些限制条件，去破坏产生 死锁的四个条件之一，防止发生死锁。
死锁的避免
动态的方法，在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安 全状态，从而避免发生死锁。如银行家算法
死锁的检测和解除
预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系 统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统正常工作。
3.6预防死锁
破坏“请求和保持”条件
第一种协议
所有进程在开始运行时，必须一次性申请在整个运行过程中全部资源
第二种协议
进程只获得运行初期所需资源开始运行，运行过程中逐步释放已分配且已用毕的全部资源，再请求新的资源
破坏“不可抢占”条件
破坏“循环等待”条件
3.7避免死锁
系统安全状态
安全状态
某时刻，对于并发执行的n个进程，若系统能够按照某种顺序如<p1,p2…pn>来为每个进程分配所需资源，直至最大需求，从而使每个进程都可顺利完成，则认为该时刻系统处于安全状态，这样的序列为安全序列
安全状态之例
由安全状态向不安全状态的转换
3.8死锁的检测与解除
死锁的检测
资源分配图
死锁定理
死锁检测中的数据结构
死锁的解除
终止进程的方法
剥夺资源
从其他进程剥夺足够数量的资源给死锁的进程，解除死锁状态
撤销进程
一种是撤消全部的死锁进程，这显然会断开死锁环路，但代价太大
另一种方法是逐个终止死锁的进程直至死锁环路消除。
付出代价最小的死锁解除算法
练习题
