淘宝网站建设的目标是什么,怎么查网站备案服务商,昆明网页设计,自定义wordpress评论列表第三章:处理机调度与死锁 处理机调度算法的目标
处理机调度算法的共同目标
资源利用率:CPU的利用率CPU有效工作时间/(CPU有效工作时间CPU空闲等待时间)公平性平衡性策略强制执行
批处理系统的目标
平均周转时间短系统吞吐量高处理机利用率高
分时系统的目标
响应时间快均…第三章:处理机调度与死锁 处理机调度算法的目标
处理机调度算法的共同目标
资源利用率:CPU的利用率CPU有效工作时间/(CPU有效工作时间CPU空闲等待时间)公平性平衡性策略强制执行
批处理系统的目标
平均周转时间短系统吞吐量高处理机利用率高
分时系统的目标
响应时间快均衡性
实时系统目标
截止时间的保证可预测性
处理机调度的层次
高级调度作业调度 分时系统无需作业调度因为需要交互批处理系统需要作业调度 中级调度和挂起有关低级调度进程调度 进程调度是最基本的调度任何操作系统都有进程调度。低级调度的三个基本机制 排队器分派器上下文切换 进程调度方式 非抢占方式抢占方式 优先权原则短进程优先原则时间片原则 进程调度的任务 保存处理机的现场信息按某种算法选取进程把处理器分配给进程 进程调度的算法 优先级调度算法 优先级调度算法的类型 非抢占式优先级调度算法 等当前进程执行完以后再执行另一个优先权最高的进程这种调度算法主要用于批处理系统中也可用于某些对实时性要求不严的实时系统中。 抢占式优先级调度算法 不等当前进程结束直接抢处理机常用于要求比较严格的实时系统中 以及对性能要求较高的批处理和分时系统中。 优先级的类型 静态优先级 优先权是在创建进程时确定的且在进程的整个运行期间保持不变。一般地优先权是利用某一范围内的一个整数来表示的例如07或0255中的某一整数 又把该整数称为优先数。可以参考BIOS系统中设置boot的优先级 动态优先级 在创建进程时所赋予的优先权是可以随进程的推进或随其等待时间的增加而改变的以便获得更好的调度性能。 轮转调度算法 基本原理:在轮转(RR)法中系统根据FCFS策略将所有的就绪进程排成一个就绪队列并可设置每隔一定时间间隔(如30ms)即产生一次中断激活系统中的进程调度程序完成一次调度将CPU分配给队首进程令其执行进程切换时机 时间片未用完进程完成时间片到进程未完成 时间片大小的确定 太小利于短作业增加系统切换开销太长就退化为FCFS算法一般选择: q略大于一次交互所需要的时间使大多数进程在一个时间片内完成 一般来说平均周转时间将比SJF长但是有较好的响应时间 多队列调度算法多级反馈队列调度算法 调度机制 设置多个就绪队列每个队列都采用FCFS算法按照队列优先级调度在第n队列中采取按时间片轮转的方式运行 调度算法的性能 对于终端型用户由于作业小感觉满意对于短批处理作业用户周转时间也较小长批处理作业用户也能够得到执行 基于公平原则的调度算法 保证调度算法公平分享调度算法
作业与作业调度
作业
作业不仅包含程序和数据还配有一份作业说明书系统根据说明书对程序的运行进行控制。批处理系统是以作业为单位从外存掉入内存的。
作业控制块JCB
为每个作业设置一个JCB保存了对作业管理调度的全部信息。是作业存在的标志。
作业步
作业步每个作业都必须经过若干相对独立有相互关联的顺序步骤才能得到结果。每一个步骤就是一个作业步。
作业运行的三个阶段
收容阶段运行阶段完成阶段
作业运行的三个状态
后备状态运行状态完成状态
作业调度的主要任务
接纳多少个作业接纳哪些作业
先来先服务(first–come first–servedFCFS)调度算法
比较有利于长作业而不利于短作业。有利于CPU繁忙的作业而不利于I/O繁忙的作业。
短作业优先(short job firstSJF)的调度算法
优点 比FCFS改善平均周转时间和平均带权周转时间缩短作业的等待时间提高系统的吞吐量 缺点 必须预知作业的运行时间对长作业非常不利长作业的周转时间会明显地增长在采用SJF算法时人–机无法实现交互该调度算法完全未考虑作业的紧迫程度故不能保证紧迫性作业能得到及时处理
优先级调度算法(priority–scheduling algorithmPSA)
高响应比优先调度算法(Highest Response Ratio Next,HRRN)
原理 在每次选择作业投入运行时先计算此时后备作业队列中每个作业的响应比RP然后选择其值最大的作业投入运行优先权(等待时间要求服务时间)/要求服务时间响应时间/要求服务时间1等待时间/要求服务时间 特点 如果作业的等待时间相同则要求服务的时间愈短其优先权愈高因而类似于SJF算法有利于短作业当要求服务的时间相同时作业的优先权又决定于其等待时间因而该算法又类似于FCFS算法对于长时间的优先级可以为随等待时间的增加而提高当等待时间足够长时也可获得处理机
实时调度(HRT和SRT任务)
实现实时调度的基本条件
提供必要信息 就绪时间开始截止时间和完成截止时间处理时间资源要求优先级 系统处理能力强 ∑(Ci/Pi)≤1N个处理机:∑(Ci/Pi)≤N 采用抢占式调度机制具有快速切换机制 对中断的快速响应能力快速的任务分派能力
实时调度算法的分类
非抢占式调度算法 非抢占式轮转调度算法非抢占式优先调度算法 抢占式调度算法 基于时钟中断的抢占式优先级调度算法立即抢占的优先级调度算法
最早截止时间优先EDF(Earliest Deadline First)算法
根据任务的开始截至时间来确定任务的优先级 截至时间越早优先级越高 非抢占式调度方式用于非周期实时任务抢占式调度方式用于周期实时任务
最低松弛度优先LLF(Least Laxity First)算法
类似EDF算法根据任务紧急(或松弛)的程度来确定任务的优先级。任务的紧急程度愈高为该任务所赋予的优先级就愈高 以使之优先执行。松弛度例子 例如一个任务在200ms时必须完成而它本身所需的运行时间就有100ms因此调度程序必须在100 ms之前调度执行该任务的紧急程度(松弛程度)为100 ms
优先级倒置(Priority inversion problem)
优先级倒置的形成 高优先级进程被低优先级进程延迟或阻塞。 优先级倒置的解决方法 简单的:假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占实用的:建立在动态优先级继承基础上的
死锁概述
资源问题
可重用性资源 计算机外设 消耗性资源 数据消息 可抢占性资源 不引起死锁CPU内存 不可抢占性资源 光驱打印机
计算机系统中的死锁
竞争不可抢占性资源引起死锁竞争可消耗资源引起死锁进程推进顺序不当引起死锁
死锁的定义必要条件和处理方法
定义:如果一组进程中的每一个进程都在等待仅由该进程中的其他进程才能引发的事件那么该组进程是死锁的产生死锁的必要条件 互斥条件请求和保存条件不可抢占条件循环等待条件 如果每个资源只有一个实例则环路等待条件是死锁存在的充分必要条件 处理死锁的方法 预防死锁 静态方法在进程执行前采取的措施通过设置某些限制条件去破坏产生死锁的四个条件之一防止发生死锁。预防死锁的策略 破坏请求和保存条件 第一种协议 所有进程在开始运行之前必须一次性地申请其在整个运行过程中所需的全部资源优点:简单易行安全缺点 资源被严重浪费严重地恶化了资源的利用率使进程经常会发生饥饿现象 第二种协议 它允许一个进程只获得运行初期所需的资源后便开始运行。进程运行过程中再逐步释放已分配给自己的且已用毕的全部资源然后再请求新的所需资源 破坏不可抢占条件 当一个已经保存了某些不可被抢占资源的进程提出新的资源请求而不能得到满足时它必须释放已经保持的所有资源待以后需要时再重新申请 破坏循环等待条件 对系统所以资源类型进行线性排序并赋予不同的序号例如令输入机的序号为1打印机序号为2磁盘机序号为3等。所有进程对资源的请求必须严格按资源序号递增的次序提出。 避免死锁 动态的方法在进程执行过程中采取的措施不需事先采取限制措施破坏产生死锁的必要条件而是在进程申请资源时用某种方法去防止系统进入不安全状态从而避免发生死锁。如银行家算法避免死锁的策略 系统安全状态 安全状态 某时刻对于并发执行的n个进程若系统能够按照某种顺序如p1,p2…pn来为每个进程分配所需资源直至最大需求从而使每个进程都可顺利完成则认为该时刻系统处于安全状态这样的序列为安全序列 安全状态之例由安全状态向不安全状态的转换 利用银行家算法避免死锁 含义:每一个新进程在进入系统时它必须申明在运行过程中可能需要每种资源类型的最大单元数目其数目不应超过系统所拥有的资源总量。当进程请求一组资源时系统必须首先确定是否有足够的资源分配给该进程。若有再进一步计算在将这些资源分配给进程后是否会使系统处于不安全状态。如果不会才将资源分配给它否则让进程等待银行家算法中的数据结构 可用资源向量 Available[m]m为系统中资源种类数Available[j]k表示系统中第j类资源数为k个。最大需求矩阵 Max[n,m]n为系统中进程数Max[i,j]k表示进程i对j类资源的最大需求数为中k。分配矩阵 Allocation[nm]:它定义了系统中每一类资源当前已分配给每一进程资源数 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移走包括它的所有请求边和分配边重复步骤12直至不能继续下去 死锁定理 若一系列简化以后不能使所有的进程节点都成为孤立节点 检测时机 当进程等待时检测死锁 其缺点是系统的开销大定时检测系统资源利用率下降时检测死锁 死锁检测中的数据结构 死锁的解除 抢占资源终止(或撤销)进程终止进程的方法 终止所有死锁进程逐个终止进程 代价最小 进程的优先级的大小进程已执行了多少时间还需时间进程在运行中已经使用资源的多少还需多少资源进程的性质是交互式还是批处理的 付出代价最小的死锁解除算法 是使用一个有效的挂起和解除机构来挂起一些死锁的进程 解除死锁
XMind: ZEN - Trial Version
