操作系统第7讲

1、操作系统概念第七讲 CPU调度(2)上章回顾周转时间与响应时间的区别SJF的优点和遇到的问题是什么？，如何解决问题？轮转法调度中的时间片是如何设定的？本课总体纲要调度算法多级队列调度多级反馈轮转调度（round robin with multiple feedback)线性优先级调度（selfish round robin)最高响应比优先法(Highest response_ratio next)实时调度算法评估进程调度例题分析多级队列调度就绪队列分为：前台与后台每个队列有自己的调度方法：前台：RR 80后台：FCFS 20调度必须在队列之间完成按优先权进行调度按时间片进行调度多级队列调度多级

2、反馈轮转调度（RRMF)在轮转法中加入到就绪队列的进程有三种情况：时间片用完I/O请求或进程互斥导致阻塞新创建进程进入就绪队列对这些进程区别对待，采用不同的时间片或优先权。多级反馈队列调度本课总体纲要调度算法多级队列调度多级反馈轮转调度（round robin with multiple feedback)线性优先级调度（selfish round robin)最高响应比优先法(Highest response_ratio next)实时调度算法评估进程调度例题分析线性优先级调度(SRR)轮转法调度时，新创建的进程放入就绪队列末尾享受平等的处理机时间片。是否可以采用两种队列进行服务享受服务队列

3、CPU新创建进程队列完成线性优先级调度(SRR)新进程在就绪队列中的优先级：P=a*t (a0)享受服务进程在就绪队列中的优先级：P=b*t(ab0)某进程在t1时刻被创建，在t时刻的优先级：P(t)=a(t-t1)(t1ta0-FCFS如果ab=0RRSRR是对FCFS和RR调度算法的折衷算法本课总体纲要调度算法多级队列调度多级反馈轮转调度（round robin with multiple feedback)线性优先级调度（selfish round robin)最高响应比优先法(Highest response_ratio next)实时调度算法评估进程调度例题分析最高响应比优先法(HR

4、N)最高响应优先法是对FCFS方式和SJF方式的综合平衡响应比定义：R=(W+T)/T=1+W/TT为该作业估计需要的执行时间，W为等待时间本课总体纲要调度算法多级队列调度多级反馈轮转调度（round robin with multiple feedback)线性优先级调度（selfish round robin)最高响应比优先法(Highest response_ratio next)实时调度算法评估进程调度例题分析实时调度操作系统是实时系统中的重要组成部分之一其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。实时操作系统具有以下特点：有限等待时间（决定性）

5、有限响应时间用户控制可靠性高系统出错处理能力强实时调度硬件实时（hard real-time）系统需要在保证的时间内完成任务软件实时(soft real-time)系统要求关键进程比其他进程拥有更高的优先权。实时操作系统具有以下功能：进程或线程切换速度快快速的外部中断响应能力基于优先级的随时抢占性调度策略实时调度基于优先级的调度策略有4种：优先级+轮转调度基于优先级的非抢占调度基于优先级的固定点抢占式调度基于优先级的随时抢占式调度本课总体纲要调度算法多级队列调度多级反馈轮转调度（round robin with multiple feedback)线性优先级调度（selfish round r

6、obin)最高响应比优先法(Highest response_ratio next)实时调度算法评估进程调度例题分析算法评估（1）如何选择适合的CPU调度算法用于特定的系统定义选择算法的准则：最大化CPU使用率，同时要求最大响应时间为1S最大化吞吐量，要求平均周转时间与总的时间成正比算法评估（2）Cpu和IO区间是可以确定的可以用数学公式来描述特定的CPU区间的概率分布对于系统模型只有一个服务器S： ：进程到达率 ：进程服务率 = / :系统内存在的进程的概率n= /(1- ) :系统内进程的算术平均值算法评估（3）Little 公式 n=*R n平均队列长度（进程数） R队列平均响应时间 新

7、进程到达队列的平均到达率e算法评估（4）对于FCFS:短作业和长作业的平均等待时间一样长。Rfc=1/( )对于RR:R(k)=k*q/(1- )对于SRRRsr= 1/( )(1kq )/ ( )本课总体纲要调度算法多级队列调度多级反馈轮转调度（round robin with multiple feedback)线性优先级调度（selfish round robin)最高响应比优先法(Highest response_ratio next)实时调度算法评估进程调度例题分析综合计算例题进程到达时间区间时间P10 10P2529P383P4107P51212研究FCFS、SJF和RR（时间片1

8、0ms）的平均等待时间综合计算FCFS=(0+5+31+32+37)/5=21msSJF(非抢占)（0（13-10）（10-8）（20-12）(32-5）/5=8msSJF(抢占）=(0+2+3+8+27)/5=8msRR=(0+27+12+13+28)/5=16ms进程调度例题分析以下哪些算法与作业的执行时间有关A)优先级调度B)RRC)SJFD)HRNE)FCFS进程调度例题分析作业调度是高级调度，进程调度是低级调度（）在各种作业调度算法中，SJF会使每个作业的等待时间最短（）作业一旦被作业调度选中，即占有CPU（）在一个兼顾分时系统和批处理系统中，通常把终端作业称为前台作业，把批量作业称为后台作业（）总结CPU调度的时机与处理方式？调度算法FCFSSJFRRHRNSRR作业作业调度和进程调度的区别以下调度算法的区别FC