操作系统第7讲课件

操作系统概念

第七讲 CPU调度(2)OperatingSystemConceptionDavidfu上章回顾周转时间与响应时间的区别SJF的优点和遇到的问题是什么？，如何解决问题？轮转法调度中的时间片是如何设定的？OperatingSystemConceptionDavidfu本课总体纲要调度算法多级队列调度多级反馈轮转调度（roundrobinwithmultiplefeedback)线性优先级调度（selfishroundrobin)最高响应比优先法(Highestresponse_rationext)实时调度算法评估进程调度例题分析OperatingSystemConceptionDavidfu多级队列调度OperatingSystemConceptionDavidfu多级反馈轮转调度（RRMF)在轮转法中加入到就绪队列的进程有三种情况：时间片用完I/O请求或进程互斥导致阻塞新创建进程进入就绪队列对这些进程区别对待，采用不同的时间片或优先权。OperatingSystemConceptionDavidfu多级反馈队列调度OperatingSystemConceptionDavidfu线性优先级调度(SRR)轮转法调度时，新创建的进程放入就绪队列末尾享受平等的处理机时间片。是否可以采用两种队列进行服务享受服务队列CPU新创建进程队列完成OperatingSystemConceptionDavidfu线性优先级调度(SRR)新进程在就绪队列中的优先级：P=a*t(a>0)享受服务进程在就绪队列中的优先级：P=b*t(a>b>0)某进程在t1时刻被创建，在t时刻的优先级：P(t)=a(t-t1)(t1<t<t1’)在t1’时刻进入享受服务队列，在时刻t，进程的优先级：P(t)=a*(t1’-t1)+b(t-t1’)OperatingSystemConceptionDavidfu线性优先级调度(SRR)何时进行队列间的调度：新创建进程队列的头一个进程的优先权与享受服务队列中最后一个进程的优先权相等时享受队列为空如果b>a>0-FCFS如果a>b=0RRSRR是对FCFS和RR调度算法的折衷算法OperatingSystemConceptionDavidfu最高响应比优先法(HRN)

最高响应优先法是对FCFS方式和SJF方式的综合平衡响应比定义：R=(W+T)/T=1+W/TT为该作业估计需要的执行时间，W为等待时间OperatingSystemConceptionDavidfu本课总体纲要调度算法多级队列调度多级反馈轮转调度（roundrobinwithmultiplefeedback)线性优先级调度（selfishroundrobin)最高响应比优先法(Highestresponse_rationext)实时调度算法评估进程调度例题分析OperatingSystemConceptionDavidfu实时调度操作系统是实时系统中的重要组成部分之一其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。实时操作系统具有以下特点：有限等待时间（决定性）有限响应时间用户控制可靠性高系统出错处理能力强OperatingSystemConceptionDavidfu实时调度基于优先级的调度策略有4种：优先级+轮转调度基于优先级的非抢占调度基于优先级的固定点抢占式调度基于优先级的随时抢占式调度OperatingSystemConceptionDavidfu本课总体纲要调度算法多级队列调度多级反馈轮转调度（roundrobinwithmultiplefeedback)线性优先级调度（selfishroundrobin)最高响应比优先法(Highestresponse_rationext)实时调度算法评估进程调度例题分析OperatingSystemConceptionDavidfu算法评估（1）如何选择适合的CPU调度算法用于特定的系统定义选择算法的准则：最大化CPU使用率，同时要求最大响应时间为1S最大化吞吐量，要求平均周转时间与总的时间成正比OperatingSystemConceptionDavidfu算法评估（3）Little公式n=λ*Rn－平均队列长度（进程数）R－队列平均响应时间

λ－新进程到达队列的平均到达率OperatingSystemConceptionDavidfue算法评估（4）对于FCFS:短作业和长作业的平均等待时间一样长。Rfc=1/(μ–λ)对于RR:R(k)=k*q/(1-ρ)对于SRRRsr=1/(μ–λ)－(1－kqμ)/(μ–λ)OperatingSystemConceptionDavidfu本课总体纲要调度算法多级队列调度多级反馈轮转调度（roundrobinwithmultiplefeedback)线性优先级调度（selfishroundrobin)最高响应比优先法(Highestresponse_rationext)实时调度算法评估进程调度例题分析OperatingSystemConceptionDavidfu综合计算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=16msOperatingSystemConceptionDavidfu进程调度例题分析以下哪些算法与作业的执行时间有关A)优先级调度B)RRC)SJFD)HRNE)FCFSOperatingSystemConceptionDavidfu作业作业调度和进程调度的区别以下调度算法的区别FCFSSJFRRHRNSRROperatingSystemConceptionDavidfu作业分别计算以下两种算法的平均周转时间T和响应比R(1)FCFS