【山东理工大学操作系统课件】第3章 处理机调度与死锁.ppt

本节主要内容： 3.1.1 高级调度 3.1.2 低级调度 3.1.3 中级调度 本节学习目标：掌握处理机调度的三个层次；掌握高级调度、低级调度和中级调度的含义 如何判断调度算法的好坏-幼儿园老师给孩子喂饭的过程 前提：孩子较小，需要老师协助进食；老师数量较少，不可能一对一；孩子要在有限的时间完成进餐 法一：孩子沿饭桌围成一圈，老师按座位顺序逐个喂食小孩，每人一口，喂完一圈，从头继续； 法二：孩子排成一列，一个小孩喂完再喂下一个；（排在后面的会长时间饥饿）而且，老师喂完一口饭后，孩子有咀嚼、吞咽的过程，老师必须等待； 法三：不按顺序，谁吃的快先喂谁； 法四：按饭量由小到大的顺序喂饭； …… 小结： 采用的调度算法不同，带来的后果也不同 调度目标归结为4个方面： ①防止进程长期不能获得调度； ②尽量提高处理器的利用率； ③提高系统吞吐量； ④尽量减少进程的响应时间。 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〔１９６５〕 ２、来由：将操作系统比作一个银行家，各种资源比作周转资金（美元、欧元），申请资源的进程比作向银行贷款的顾客。 1）银行家贷款给若干顾客，满足顾客对资金的要求； 2）银行家可以安全收回其全部贷款而不至于破产。 就象操作系统能满足各个进程对资源的要求而同时整个系统不会发生死锁。 ３、为保证资金的安全，银行家规定： 　a、当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳顾客； 　b、顾客可以分期贷款，但贷款总额不能超过最大需求量； 　c、当银行家现有的资金不能满足顾客尚需的贷款数额时，对贷款可推迟支付，但要使顾客在有限时间内得到贷款； 　d、当顾客得到所需资金后，