搜索
第四章处理器调度1.调度及其类型*关于调度①调度是操作系统的基本功能，几乎所有的系统资源在使用前都要经过调度。②处理器是计算机系统中最重要的资源，其调度策略常表征操作系统的某种特征。*调度类型1.1作业调度（高级调度、宏观调度、长期调度）主要工作和任务①根据某种策略或算法，从后备作业中选择若干作业，分配必要的资源，建立相应进程，加载相应的程序和数据并等待进程调度为其指派处理器。②作业完成后的善后工作。时间尺度分钟、小时、天。1.2中级调度（进程对换、中期调度、交换调度）设置原因内存资源缺乏、进程阻塞、进程数目过多。主要工作和作用①内存与外存间进程交换。②系统短期调整。③常用于具有虚拟存贮技术的系统或分时系统中。1.3进程调度（微观调度、低级调度、短期调度）主要工作和要求①选择就绪进程占用处理器并实现转接。②常驻内存。③对系统性能影响重大。时间尺度毫秒级。1.4三级调度之间的关系①作业身份的转换。②竞争CPU过程中内存资源紧张或不足的处理。③处理器的真正指派。*调度实例1MULTICS系统其调度方案为①限定后备状态作业数≤60。②限定内存作业道数≤8，定时交换（2秒）。说明①小范围内多道。②大范围内分时。2UNIX系统其调度方案为①核心程序中的sched程序段负责进程映象的换入换出，相当于中级调度。②核心程序中的swtch程序段负责分配CPU，相当于进度调度。2.调度性能评价2.1调度的实质与操作系统的设计目标调度的实质是为了达到主观上某些设计目标。设计目标①尽可能多的作业。②处理器忙。③I/O设备充分利用。④公平合理。2.2设计调度算法的因素①选择算法应与系统的整个设计目标一致。②注意系统资源的均衡使用。③防止某些作业长期得不到调度。④尽量公平合理。⑤算法不应过于复杂。2.3有关指标说明与用户相关的指标①周转时间指作业从提交到完成（得到结果）所经历的时间。②响应时间指用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。③公平性指调度算法不会因作业或进程本身的特性而使上两个指标过分恶化。与系统相关的指标①吞吐量指单位时间内所完成的作业数。②作业平均周转时间T=(∑Ti)/n其中n为被测定作业流中的作业数，Ti=Tci-Tsi(即作业执行时间+等待调度时间),Tci=作业i的完成时刻，Tsi作业i的提交时刻。③作业平均带权周转时间W=(∑Wi)/n,其中Wi=Ti/tRi,tRi=作业i的实际执行时间。④系统利用率指处理器的利用率及各种设备的均衡利用率。ni=1ni=13.作业调度3.1单道批处理系统的调度算法①先来先服务算法FCFS按作业到达的先后次序进行调度，优先考虑在系统中等待时间最长的作业，而不论其要求的执行时间的长短。示例假定四个作业的到达顺序如下：1#：要求运行时间2秒。2#：要求运行时间60秒。3#：要求运行时间2秒。4#：要求运行时间2秒。忽略四个作业在机外的等待时间，计算T与W。T=48.5W=16.76②短作业优先算法SJF优先调度要求运行时间最短的作业。上例T=19.5W=1.8③响应比高者优先算法HRN响应比Rp=作业响应时间tR/要求执行时间其中tR=到此次调度时已等待时间+要求执行时间故Rp=1+作业已等待时间/要求执行时间1）防止无限制调度延迟。2）照顾先来后到。3）照顾短作业。3.2多道批处理系统的调度算法需要考虑的因素①CPU对I/O等待时间问题②T与W的定量计算问题算法讨论①基于先来先服务算法②基于优先级调度算法示例B5500计算机操作系统实行由用户根据作业的紧急程度在其作业申请表中指定一个优先数，系统依据这个优先数将作业的JCB插入相应的优先级队列中。示例IBM360/370系统中按作业的类别划分优先级。如图A类：I/O繁忙的作业B类：I/O和CPU均衡的作业C类：CPU繁忙的作业D类：其它一般的作业…21AA类优先级0A、B、C类B、C类X类优先级1优先级2优先级3优先级高优先级低…21B…21C…21D调度规则1）用户说明其作业类别及该类中的优先数。2）作业注册程序对作业先按类排列，同类中按优先数排序。3）主存用户区分区，规定各分区接纳的作业类型。4）作业调度从相应类的作业中挑选优先级高的作业投入运行。③分时和优先级相结合调度算法用于分时系统及某些引入分时机制的多道批处理系统中。示例MULTICS系统采用分时和优先级结合的调度算法。1）后备作业按优先级分成多个队列。2）作业指定一个优先级范围（L1,L2），任何时刻作业的优先级Li都满足1≤L1LiL2≤n。3）会话型作业（分时作业）优先级从1到P1，非会话型（批处理）作业优先级从P2到n，允许P2P1(P值越小，优先级越高）。4）每一后备作业队列分配相应时间片qi,且qi+1=2qi。5）调度优先当前最高优先级队列的作业，若其分配的时间片用完，则返回低一级后备队列等待下次调度。④综合考虑资源要求调度算法综合考虑一个作业的对资源的要求。4.进程调度4.1进程调度的功能①记录系统中所有进程的执行情况。②选择占有处理器的进程。③进行进程上下文切换。4.2进程调度的时机与引起进程调度的原因及进程调度的方式有关。引起进度调度的原因①当前执行进程执行完毕。②当前执行进程由于请求某个事件受阻。③分时系统中时间片用完。④强占式系统中高优先级进程就绪。进程调度的方式①可强占式（剥夺式）调度。②不可强占式（非剥夺式）调度。4.3进程调度性能评价定性指标①调度的可靠性②调度的简洁性定量指标①CPU的利用率。②进程在就绪队列中的等待时间与执行时间比率。4.4进程调度算法①简单轮转法（时间片轮转法，时间片时钟法)遵循FCFS原则形成一个队列，每次选择队首进程并给定固定值的时间片q投入运行；若时间片到而未完成的进程将再次进入队尾，等待下一轮调度。关于时间片q其中T是系统的响应时间，N是系统规定的同时就绪的进程数。1）与系统响应速度2）与系统要求N值3）与CPU性能4）与进程切换时间i执行特点简单、方便、公平、缺乏灵活性。首尾就绪队列IO阻塞队列时间片到进程结束作业调度建立进程IO完成IO请求调度选中②固定周期轮转法（时间片可变）当就绪进程数目不足时，保持T不变，增大q值，使短作业尽快完成，减少进程切换次数，减轻系统开销。③优先级高者优先调度设定优先级（数）方式1）静态优先级（数）法进程建立时由系统指定并在其生命期中一直保持不变。。按进程类型。按资源需求量。外部标准2）动态优先级（数）法进程建立时所指定的优先级在进程运行过程中可不断变化，以获得更好的调度性能。线性修改优先级固定时刻增加或修改进程优先级。。进程I/O请求受阻时适当增加。。进程长期用满时间片而中断，适当降低。非线性修改优先级进程初期其优先级不变或线性改变，若某种情况出现，则突然增加其优先级。④多级队列调度按优先级高低不同设立两级或多级队列，进程调度先从高优先级队列挑选，同一队列实行FCFS或轮转法调度。高优先级就绪队列中优先级就绪队列低优先级就绪队列执行时间片完时间片完时间片完q=50msq=100msq=500ms⑤带反馈多级队列调度依据进程运行的不同情况进行带反馈的调整，改变其所在队列。执行低优先就绪队列高优先就绪队列中优先就绪队列阻塞队列阻塞队列阻塞队列时间片完q=500msq=100msq=50msIO完成IO完成IO完成盘IO终端IO页面IO进程创建4.5进程调度的实现①就绪队列组织包括FIFO、优先级排序队列、优先级无序链表方式。②分派程序dispatch算法参见教材。第四章处理机调度（作业）1、下面调度算法哪些适合于作业调度，哪些适合于进程调度？1）先来先服务2）轮转法3）短作业优先4）优先级高者优先5）长作业优先2、试述多级队列调度算法中不同队列具有大小时间片的优点。3、解释下面算法对短作业的优待程度。1）FCFS2）轮转法3）多级队列反馈4、许多调度算法是参数化的，下面各对算法间有什么联系？1）优先级与SJF2）多级队列反馈与FCFS3）优先级与FCFS4）轮转法与FCFS5、某动态优先级调度算法：当作业等待CPU时（在就绪队列中），其优先级以a速率改变；当作业运行时（占据CPU），其优先级以b速率改变。下面情况中，将是什么算法？1）若ba02）若ba0。6、给定一组作业J1，J2，...，Jn，它们的运行时间分别是T1，T2，...,Tn。假定这些作业同时到达，并将在一台CPU上按单道方式运行。证明：按SJF，则平均周转时间最短。7、有四道作业情况如下：作业号提交时间（小时）运行时间（小时）18.002.0028.500.5039.000.1049.500.20采用单道运行，按下面调度算法，分别计算作业的平均周转时间T和平均带权周转时间W:1）FCFS2）SJF3）HRN。8、比较下面算法对短作业的优待程度和对长作业的虐待程度。1）FCFS2）SJF3）HRN9、设某系统调度如图，q=50ms。系统中有两进程A和B，执行逻辑如图。假定t=0时刻，A、B在就绪队列中，A在B先，忽略进程切换时间，P、V操作本身时间不计。按下表填写两进程从t=0时刻到t=170ms间的状态变化。执行就绪阻塞调度超时P(S)V(S)P(S)20ms30msAV(S)30ms20msB初值S=0时间执行态进程就绪态进程阻塞态进程发生事件t=0AB10、设某系统调度如图，系统中有两作业A和B，执行逻辑如图，其中磁带IO系统立即响应并须在500ms完成，磁盘IO系统立即响应并须在100ms完成。假定t=0时刻作业A执行、B在高优先就绪队列中就绪，忽略进程切换时间，系统工作时间不计。按下表填写两作业的执行情况。作业A计算计算计算带IO带IO带IO150ms150ms150ms作业B计算计算盘IO盘IO250ms150ms执行低优先就绪阻塞30ms超时盘IO完成高优先就绪阻塞带IO申请盘IO申请带IO完成100ms时间运行带IO阻塞发生事件t=0A盘IO阻塞高优先就绪低优先就绪11、假定进程状态变迁如图。试问1）什么时间引起每种状态变迁？2）什么条件下，一个进程的变迁3能立即引起另一个进程的变迁1？3）什么情况下将发生下列因果变迁？2-1；3-2；4-1。执行就绪阻塞123412、设某系统进程调度算法为：IO多的进程高优先级，使用CPU时间多的进程低优先级；进程按优先级高者优先调度原则，在同一优先级上按先进先出FIFO原则调度。试从下列方面实现上述调度算法：1）设计就绪队列；2）各进程何时进入就绪队列？在队列中的排序顺序如何？3）进程调度流程。