操作系统os08_3.ppt

第三章??处理机调度与死锁 调度的类型和模型 调度算法 先来先服务 短作业优先 最高响应比优先法 优先级调度算法 时间片轮转 多级反馈轮转法 死锁的概念和解决方案 3.1 调度的类型和模型 调度类型 作业调度 (高级调度或长程调度)：根据某种算法，从外存后备队列中选取某些作业调入内存，并为之创建进程、分配资源，再将创建的进程插入就绪队列。 作业、作业步、作业流。 作业控制块JCB：作业在系统中的标志，其中保存了系统对作业进行管理和调度所需要的全部信息。系统按照JCB中的信息对作业运行控制。 作业调度必须决定:1）接纳多少作业，2）接纳哪些作业 进程调度 (低级调度或短程调度) 进程调度程序 保存处理机现场：记录系统中所有进程的执行情况：状态，优先级，所用资源情况等。 按算法选择进程。 分配处理机：进行进程上，下文切换，分配处理机给进程。 进程调度中的三个基本原则 排队器：对就绪队列中的进程进行排队； 分派器：从就绪队列中取出进程分配CPU； 上下切换机制：完成进程切换过程中的上下文处理 进程调度方式 非剥夺方式(非抢占方式) 剥夺方式(抢占方式) 选择性剥夺调度 为每个进程设置特征位Up 和 Vp Up=1：本进程可剥夺其它进程 Up=0：本进程不能剥夺其它进程 Vp=1：可被剥夺 Vp=0：不能被剥夺 中级调度（交换调度或中程调度） 为提高内存利用率和系统吞吐量，按照给定的原则和策略，将处于外存交换区中的就绪状态或阻塞状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区中。 调度和进程状态转换 调度的 层次 调度队列模型 调度准则和算法评价 调度准则 面向用户 周转时间 响应时间 截止时间 可预测性 面向系统 吞吐量 处理机利用率 公平 平衡资源 强制优先级 设计调度算法时考虑的因素 应与系统的整个设计目标一致。 系统资源的均衡使用。 平衡系统和用户要求。 大多数系统都根据用户的需要而采用兼顾某些目标的简单调度算法。 调度性能的衡量 批处理系统：平均周转时间或平均带权周转时间 分时或实时系统：平均响应时间 响应时间 截止完成时间 周转时间： 作业i. Ti = Tei – Tbi = Twi + Tsi Tei: 完成时间 Tbi: 提交时间 Twi : 等待时间 Tsi : 执行时间 有n个作业的作业流，其平均周转时间： ?? T = 1/n [T1 + T2 + ……+ Tn ] 带权周转时间 比较某种调度算法对不同作业流的调度性能。 Wi = Ti/Tsi = Twi/Tsi + 1 平均带权周转时间： ?? W = 1/n [W1 + w2 + …… + Wn ] ? 原则上总是使T或W较小的作业被选中，因为这样资源利用率较高，用户也满意。 例：有四个作业，它们的提交，运行，完成情况如下： 平均周转时间 T=1.725(小时) 平均带权周转时间 W=6.875 3.2 调度算法 先来先服务调度算法 (First-Come-First-Served) 原理 特点 利于长作业，利于CPU 繁忙型的作业。 最短作业（进程）优先调度算法 （ Shortest Process Next ） 原理：选取估计运行时间最短的进程。演示 优点：SPN能有效地降低作业的平均等待时间和提高系统吞吐量。 缺点： 对长作业不利； 不能保证紧迫性作业或进程会得到及时处理； 不一定能真正做到短作业优先。 最高响应比优先算法 （ Highest Response Ratio Next ） HRRN是对FCFS和SJF方式的一种综合平衡。 响应比： R=（W+T）/T = 1+W/T T：估计执行时间 W：等待时间 W+T：响应时间 每当要进行调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。 时间片轮转调度算法 (Round-Robin) 原理 将CPU 的处理时间分成固定大小的时间片，系统将所有就绪进程按先来先服务的原则排成队列。每次调度时，把CPU 分配给队首进程，令其执行一个时间片，时间片用完后，若进程未结束，则重新排入就绪队列尾部。 时间片的划分 时间片 Q=R / Nmax R：响应时间 Nmax： 最大进程数 优先级调度算法 (Priority) 静态优先级 原理：在创建进程时赋予优先级，在进程的生命期中不能改变。 确定进程优先级的一般原则 进程的类型