计算机操作系统---第3章 处理机调度与死锁.ppt

本节主要内容： 3.1.1 高级调度 3.1.2 低级调度 3.1.3 中级调度 本节学习目标：掌握处理机调度的三个层次；掌握高级调度、低级调度和中级调度的含义 1.低级调度的功能 （1）保存处理机的现场信息 （2）按某种算法选取进程 （3）把处理机分配给进程 2.进程调度中的三个基本机制 （1）排队器 （2）分派器（分派程序） （3）上下文切换机制 花费较多的处理机时间 进程调度（CPU调度）要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换） 处理机调度总结 对所有系统 公平，各进程公平共享CPU 策略，体现即定的调度策略 平衡，保持系统各部分繁忙 批处理系统 吞吐量，单位时间完成的作业数，越大越好 周转时间，作业从进入到结束的时间，越短越好 充分利用CPU，CPU越忙越好 交互式系统 响应时间，越快越好 均衡，满足用户期望 实时系统 及时，避免丢失数据 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力 3.3.4 进程调度的时机（补充） 当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待状态(等待I/O) 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式） 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语） 3.3.5 进程切换（补充） 进程切换 定义：一个进程让出处理器，由另一个进程占用处理器的过程 进程的切换使系统中的各进程均有机会占用CPU 进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断事件有关 例2 抢占式调度方式用于周期实时任务 描述：有两个周期性任务，A的周期时间为20ms，每个周期的处理时间为10ms；B的周期时间为50ms，每个周期的处理时间为25ms。 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 产生死锁的例子 申请不同类型资源产生死锁 申请同类资源产生死锁（如内存） 设有资源R，R有m个分配单位，由n个进程P1,P2,…,Pn（n m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 申请同类资源产生死锁（如内存） m=2，n=3 资源分配不当导致死锁产生 安全序列： 一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的) 死锁避免定义 定义： 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 安全状态与不安全状态 不安全状态:不存在一个安全序列。不安全状态不一定是死锁状态，但系统处于不安全状态可能发生死锁。 银行家算法 １、提出：Dijkstra〔１９６５〕 ２、来由：将操作系统比作一个银行家，各种资源比作周转资金，申请资源的进程比作向银行贷款的顾客。 一方面银行家贷款给若干顾客，满足顾客对资金的要求，另一方面银行家可以安全收回其全部贷款而不至于破产。就象操作系统能满足各个进程对资源的要求而同时整个系统不会发生死锁。 ３、为保证资金的安全，银行家规定： 　a、当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳顾客； 　b、顾客可以分期贷款，但贷款总额不能超过最大需求量； 　c、当银行家现有的资金不能满足顾客尚需的贷款数额时，对贷款可推迟支付，但要使顾客在有限时间内得到贷款； 　d、当顾客得到所需资金后，一定能在有限时间内归还所有资金。 死锁的检测与解除 检测时机： 当进程等待时检测死锁 （其缺点是系统的开销大） 定时检测 系统资源利用率下降时检测死锁 本章练习题 .最低松弛度优先即LLF(Least Laxity First) 算法 该算法根据任务紧急（或松弛）的程度，来确定任务 的优先级。 例子：一个任务在200ms时必须完成，本身 运行时间有100ms，因此，必须在100ms之 前调度执行； 该任务的紧急程度（松弛程度）为100ms。 该算法主要用于可抢占调度中。 松弛度＝必须完成时间－本身运行时间－ 当前时间 实现该算法时要求系统中有一个按松弛度排序的 实时任务就绪队列，松弛度最低的任务排在队列 最前面，调度程序总是选择就绪队列中的队首任