操作系统操作系统课件 (4).pdf
第四部分 处理机调度操作系统目录一、处理机调度概念二、处理机调度算法（一）三、处理机调度算法（二）四、处理机调度算法应用一、处理机调度概念第四部分 处理机调度内容1.基本概念2.调度术语3.调度的层级4.进程调度的功能5.进程调度的时机6.进程调度的性能评价1.基本概念 CPU调度：进程调度程序按照一定的策略，进程调度程序按照一定的策略，动态的将动态的将CPU分配给某个进程，并使之执行CPU分配给某个进程，并使之执行 目的：以使CPU资源利用率最高以使CPU资源利用率最高 进程执行由CPU执行与IO等待周期组成 进程执行由CPU执行与IO等待周期组成2.调度术语 CPU利用率：使CPU尽可能忙，实现高效使CPU尽可能忙，实现高效 吞吐量：(throughput)单位时间中完成的进程(throughput)单位时间中完成的进程 周转时间：运行该进程所花费的时间运行该进程所花费的时间 等待时间：在就绪队列中等待所花费的时间在就绪队列中等待所花费的时间 响应时间：从用户提交请求到产生第一个响应的：从用户提交请求到产生第一个响应的时间时间3.调度的层次当CPU变为空闲时当CPU变为空闲时，操作系统就必须从就绪，操作系统就必须从就绪的队列中选择一个进程来执行的队列中选择一个进程来执行系统调度分为4级：作业调度（宏观调度/高级调度）作业调度（宏观调度/高级调度）交换调度（中级调度交换调度（中级调度）进程调度进程调度（微观调度（微观调度/低级调度/低级调度）线程调度线程调度4.进程调度功能 功能包括：记录系统中所有进程的执行情况记录系统中所有进程的执行情况选择占有处理机的进程选择占有处理机的进程进行进程上下文切换进行进程上下文切换5.进程调度时机进程执行完毕进程执行完毕进入睡眠等待状态进入睡眠等待状态执行进程中调用了P,V原语执行进程中调用了P,V原语执行中进程提出I/O请求执行中进程提出I/O请求分时系统中时间片已经用完分时系统中时间片已经用完系统进程执行完毕，调度用户进程系统进程执行完毕，调度用户进程就绪队列中某进程优先权高于当前执行的进程就绪队列中某进程优先权高于当前执行的进程进程上下文切换 进程上下文切换包括四个步骤：决定是否做上下文切换决定是否做上下文切换保存当前执行的进程上下文保存当前执行的进程上下文采用合理的调度算法，选择一个处于就绪状态进程采用合理的调度算法，选择一个处于就绪状态进程恢复所选进程的上下文，将控制权交给所选进程 恢复所选进程的上下文，将控制权交给所选进程 6.进程调度性能评价 进程调度性能的衡量是操作系统设计的一个重要指标定性：调度的可靠性、简洁性定性：调度的可靠性、简洁性定量：CPU利用率，进程的等待/执行率定量：CPU利用率，进程的等待/执行率方法：对进程调度的解析是十分困难的，方法：对进程调度的解析是十分困难的，一般采用模拟或测试系统响应时间的方法一般采用模拟或测试系统响应时间的方法二、处理机调度算法（一）第四部分 处理机调度内容1.优先权调度2.轮转法调度1.优先权调度 每个进程都有优先权 具有最高优先权的进程分配给CPU SJF算法作为优先权算法的特例。优先权为下一个CPU区间的倒数。CPU区间越大，优先权越小 导致的问题：饥饿（starvation)低优先权的进程可能永远也不会运行（无穷阻塞）解决方案：老化(aging)逐渐增加在系统中等待很长时间的进程的优先权2.轮转法调度（Round-Robin)轮转法调度：专门为分时系统设计,每个进程得到一个较专门为分时系统设计,每个进程得到一个较小的时间单元:时间片小的时间单元:时间片（time quantum），时间片通常time quantum），时间片通常（10ms100ms)（10ms100ms)系统给每个进程分配若干个时间片系统给每个进程分配若干个时间片，被调度的进程运行完，被调度的进程运行完时间片后，系统就发生调度时间片后，系统就发生调度如果有n个进程，如果有n个进程，时间片为时间片为q，那么每个进程会得到1/n的q，那么每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过CPU的时间不会超过（n-1）q个时间单元，n-1）q个时间单元，直到下一个时直到下一个时间片为止间片为止两种情况：CPU区间小于时间片CPU区间小于时间片CPU区间大于时间片CPU区间大于时间片2.轮转法调度1.只能调度分配可抢占资源1.只能调度分配可抢占资源：如：如CPU、内存CPU、内存、外存、外存2.作业调度不适用轮转法2.作业调度不适用轮转法3.时间片长度的确定3.时间片长度的确定：q=R/Nmax2.轮转法调度ProcessBurst TimeP1 53P2 17P3 68P4 24 时间片q20ms（毫秒）P1P2P3P40ms20ms40ms60ms531768242.轮转法调度ProcessBurst TimeP153P2 17P368P4 24P1P2P3P402057773797117 121134154162P1P2P3P40ms20ms40ms60ms531768242.轮转法调度Process Burst TimeP153P2 17P368P4 24 甘特图为（时间片q20ms):特点：平均等待时间较高平均等待时间较高，但响应较好，但响应较好P1P2P3P4P1P3P4P1P3P302037577797117121134154162甘特图甘特图（Gantt chart）又称为横道图又称为横道图、条状图。其、条状图。其通过条状图来显示项目，进度，和其他时间相关的通过条状图来显示项目，进度，和其他时间相关的系统进展的内在关系随着时间进展的情况。以提出系统进展的内在关系随着时间进展的情况。以提出者亨利L甘特先生的名字命名者亨利L甘特先生的名字命名2.轮转法调度 时间片与上下文时间的关系2.轮转法调度 不同时间片的平均等待时间统计轮转法性能轮转法性能 q若较大若较大FIFO q若较小若较小 q的长度要的长度要比上下文切换时间长，比上下文切换时间长，否则造成浪费。否则造成浪费。80的的CPU区间应该小于区间应该小于时间片时间片三、处理机调度算法（二）第四部分 处理机调度内容1.多级队列调度2.多级反馈轮转调度（round robin with multiple feedback)3.线性优先级调度（selfish round robin)4.最高响应比优先调度1.多级队列调度 就绪队列分为：前台与后台 每个队列有自己的调度方法：前台：RR 后台：FCFS 调度必须在队列之间完成 按优先权进行调度 按时间片进行调度1.多级队列调度2.多级反馈轮转调度（RRMF)在轮转法中加入到就绪（等待）队列的进程有三种情况：时间片用完 I/O请求或进程互斥导致阻塞 新创建进程进入就绪队列对这些进程区别对待，采用不同的时间片或优先权2.多级反馈队列调度多级队列调度与多级反馈队列调度的区别 多级反馈队列调度中就绪队列的设置不是象中就绪队列的设置不是象多级多级队列调度队列调度一样按作业性质划分，而是按时间片的一样按作业性质划分，而是按时间片的大小划分 大小划分 多级队列调度中的进程固定在某一个队列中，而中的进程固定在某一个队列中，而多级反馈队列调度多级反馈队列调度中的进程不固定 中的进程不固定 多级队列调度中每个队列按作业性质不同而采用中每个队列按作业性质不同而采用不同的调度算法，而不同的调度算法，而多级反馈队列调度中除了个中除了个别队列外，均采用相同的调度算法别队列外，均采用相同的调度算法3.线性优先级调度(SRR)轮转法调度：新创建的进程放入就绪队列末尾享受：新创建的进程放入就绪队列末尾享受平等的处理机时间片平等的处理机时间片 线性优先级调度：采用两种队列进行服务：采用两种队列进行服务享受服务队列CPU新创建进程队列完成P=a*t(a0)P=a*t(a0)P=b*t(ab0)P=b*t(ab0)3.线性优先级调度(SRR)某进程在t1时刻被创建，在t时刻的优先级：P(t)=a*(t-t1)(t1tt1)在t1时刻进入享受服务队列，在时刻t，进程的优先级：P(t)=a*(t1-t1)+b*(t-t1)(t1ta0，SRR如果ba0，SRRFCFSFCFS如果ab=0，SRR 如果ab=0，SRR RRRRSRR是对FCFS和RR调度算法的折衷算法SRR是对FCFS和RR调度算法的折衷算法4.最高响应比优先调度(HRN)最高响应优先调度是对FCFS方式和SJF方式的最高响应优先调度是对FCFS方式和SJF方式的综合平衡综合平衡响应比定义：响应比定义：R=(W+T)/T=1+W/TR=(W+T)/T=1+W/TT为该作业估计需要的执行时间T为该作业估计需要的执行时间，W为等待时间W为等待时间四、处理机调度算法应用第四部分 处理机调度内容1.实时调度2.算法评估3.综合计算1.实时调度 操作系统是实时系统中的重要组成部分之一其处理和控制的正确性不仅仅取决于计算的逻其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时辑结果，而且取决于计算和处理结果产生的时间间 实时操作系统具有以下特点：有限等待时间（决定性有限等待时间（决定性）有限响应时间有限响应时间用户控制用户控制可靠性高可靠性高系统出错处理能力强系统出错处理能力强1.实时调度 硬件实时（hard real-time）系统需要在保证的时间内完成任务系统需要在保证的时间内完成任务 软件实时(soft real-time)系统要求关键进程比其他进程拥有更高的优先系统要求关键进程比其他进程拥有更高的优先权。权。实时操作系统具有以下功能：进程或线程切换速度快进程或线程切换速度快快速的外部中断响应能力快速的外部中断响应能力基于优先级的随时抢占性调度策略基于优先级的随时抢占性调度策略1.实时调度基于优先级的调度策略有4种基于优先级的调度策略有4种：优先级+轮转调度优先级+轮转调度基于优先级的非抢占调度基于优先级的非抢占调度基于优先级的固定点抢占式调度基于优先级的固定点抢占式调度基于优先级的随时抢占式调度基于优先级的随时抢占式调度2.算法评估（1）如何选择适合的CPU调度算法用于特定的如何选择适合的CPU调度算法用于特定的系统系统定义选择算法的准则：定义选择算法的准则：最大化CPU使用率，同时要求最大响应时间最大化CPU使用率，同时要求最大响应时间为1S为1S 最大化吞吐量，要求平均周转时间与总的时最大化吞吐量，要求平均周转时间与总的时间成正比间成正比算法评估（2）CPU和IO区间是可以确定的CPU和IO区间是可以确定的可以用数学公式来描述特定的CPU区间的概率分布可以用数学公式来描述特定的CPU区间的概率分布对于系统模型只有一个服务器S：对于系统模型只有一个服务器S：进程到达率：进程到达率：进程服务率：进程服务率=/:系统内存在的进程的概率=/:系统内存在的进程的概率n=/(1-):系统内进程的算术平均值n=/(1-):系统内进程的算术平均值2.算法评估（3）Little 公式：n=*Rn：平均队列长度（进程数）R：队列平均响应时间：新进程到达队列的平均到达率2.算法评估（4）对于FCFS:短作业和长作业的平均等待时间一样长Rfc(k)=1/*/(1-)=1/()对于RR:Rrr(k)=k*q/(1-)=kq/()对于SRR:Rsr(k)=1/()(1kq)/()3.综合计算 例题 进程到达时间区间时间 P1 0 10 P2 5 29 P3 8 3 P4 10 7 P5 12 12计算FCFS、SJF和RR（时间片10ms）的平均等待时间综合计算 FCFS=(0+5+31+32+37)/5=21ms SJF(非抢占)(0(13-10)(10-8)(20-12)(32-5)/5=8ms SJF(抢占）=(0+2+3+8+27)/5=8ms RR=(0+27+12+13+28)/5=16ms进程调度例题分析 以下哪些算法与作业的执行时间有关A.优先级调度B.RRC.SJFD.HRNE.FCFS作业作业调度和进程调度的区别作业调度和进程调度的区别以下调度算法的区别以下调度算法的区别 FCFS SJF RR HRN SRR
