OS03特殊系统调度.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- OS03 特殊 系统 调度
- 资源描述:
-
,*,实时系统例子,:实验控制、过程控制设备、机器人、空中交通管制、远程通信、军事指挥与控制系统,下一代系统还包括自动驾驶汽车、具有弹性关节的机器人控制器、智能化生产中的系统查找、空间站和海底勘探。,每种实时系统都有若干个实时进程,来反应或控制某个外部事件,它们往往带有某种程度的紧迫性,需要实时系统的调度有特殊处理,所以引入,实时调度,。,实现实时调度的基本条件,实时调度算法的分类,常用的两种实时调度算法,实现实时调度的基本条件,提供必要的信息,开始/完成截止时间,就绪时间,处理时间,资源要求,优先级,实现实时调度的基本条件,系统处理能力强,有,6,个周期性的硬实时任务,处理时间都为,10ms,,周期时间都为,50ms,,判断实时系统是否可调度?,假定系统中有,m,个,周期性,的,硬实时任务,,处理时间为,C,i,,,周期时间为,P,i,(1i m),。,单处理机下必须满足:,实现实时调度的基本条件,思考:提高实时系统处理能力的方法?,为多处理机(,N,个)时,限制条件变为:,实现实时调度的基本条件,采用抢占式调度机制,(硬实时系统),具有快速切换机制,对外部中断的快速响应能力,要求快速,硬件,中断机构、允许中断的间隔短,快速的任务分派能力,系统中的每个运行功能单位适当的小,实时调度算法的分类,根据实时任务,性质,不同可分为,硬实时,调度和,软实时,调度;,根据调度,方式,不同可分,非抢占,调度和,抢占,调度算法;,根据调度,时间,的不同分成,静态,和,动态,调度算法;,在,多处理机,情况下可分为,集中,式和,分布,式调度算法。,实时调度算法的分类,非抢占式调度算法,非抢占式轮转调度算法,非抢占式优先调度算法,抢占式调度算法,基于时钟中断的抢占式优先权调度算法,立即抢占的优先权调度算法,非抢占式轮转调度算法,响应时间在几秒到数十秒 之间。,应用于不太严格的实时控制系统,比如工业生产的群控系统。,Round-robin Non-preemptive Scheduler,非抢占式优先调度算法,当实时任务到达,放在就绪队列队首,等待当前任务的自我终止或运行完成。,响应时间为数百毫秒,适用于较为严格的实时控制系统。,Priority-Driven Nonpreemptive Scheduler,基于时钟中断的,抢占式优先权调度算法,当优先级高于当前任务的实时任务到达,则等到下一个时钟中断,抢占当前任务的处理机。,响应时间为几到数十毫秒之间,应用于较严格的实时系统。,Priority-Driven Preemptive Scheduler on Preemption Points,立即抢占的,优先权调度算法,一旦出现请求中断的 紧急任务,只要当前任务未在临界区,立即抢占它的,CPU,响应时间为,100,微秒到几毫秒之间,系统必须具有快速响应外部中断能力,Immediate Preemptive Scheduler,最早截止时间优先算法,EDF,根据任务的开始截止时间来确定任务的优先级;,可用于抢占式调度和非抢占式调度。,开始截止时间,任务执行,任务到达,t,1,2,3,4,1,3,4,2,1,3,4,2,最低松弛度优先算法,LLF,根据任务的紧急(或松弛)程度确定任务的优先级,松弛度必须完成的时间还需运行的时间,当前时间,松弛度是动态变化的,主要用于可抢占式调度方式,最低松弛度优先算法,LLF,0 20 40 60 80 100 120 140 160,A,1,A,2,A,3,A,4,A,5,A,6,A,7,A,8,B,1,B,2,B,3,t,必须完成时间,B,1,(10)B,1,(15)B,2,(5)B,2,(15),0 10 20 30 40 50 60 70 80,t,t,1,t,2,t,3,t,4,t,5,t,6,t,7,t,8,t,1,=0,A,1,(10)A,2,(10)A,3,(10)A,4,(10),紧密耦合,MPS,和松散耦合,MPS,紧密耦合,MPS:,通常是通过高速总线或高速交叉开关,来实现多个处理器之间的互连,它们共享主存储器和,I/O,设备。,松散耦合,MPS:,通常是通过通道或通信线路,来实现多台计算机之间的互连。,对称,MPS,和非对称,MPS,根据系统中所用处理器的相同与否划分:,对称多处理器系统,(SMPS):,在系统中所包含的处理器在功能和结构上都是相同的。,非对称多处理器系统,:,在系统中有多种类型的处理器单元,一主多从。,进程分配方式,对称多处理器系统,把多处理器看成是一个处理器池。,静态分配方式(,Static Assignment),问题是:处理器会出现忙闲不均,一个进程从开始执行直至其完成,都被固定地配到一个处理器上去执行。,每个处理器设置一个专用的就绪队列。,进程分配方式,对称多处理器系统,动态分配方式(,Dynamic Assignment),优点:,解决了各处理器的忙闲不均现象,缺点:,对于松散耦合系统会增加调度开销,设置一个公共的就绪队列,所有就绪进程都被放在该队列中,分配时可将进程分配到任一处理器,进程分配方式,非对称多处理器系统,主/从式分配方式,优点:,系统处理比较简单、不会出现 处理器的忙闲不均现象,缺点:,具有不可靠性,OS,核心部分驻留在主机,从机只是,用户程序,进程调度由主机完成,每当从机空闲,向主机发送索求进程信号,等待主机为它分配进程,进程(线程)调度方式,自调度方式(,Self-Scheduling),成组调度方式,(,Gang Scheduling),专用处理器分配方式,(,Dedicated Processor Assignment),进程(线程)调度方式,自调度方式(,Self-Scheduling),在系统中设置有一个公共的进程或线程就绪队列,所有处理器在空闲时,都可,自己,到该队列中取得一进程或线程来运行。,采用单处理器下使用的调度算法,如,FCFS,。,进程(线程)调度方式,优点:,系统中的公共就绪队列可按单处理机系统所采用的各种方式加以组织;,调度算法可用单处理机系统所用的算法;,只要有任务,就不会出现处理机空闲的情况。,缺点:,瓶颈问题、低效性、线程切换频繁,自调度方式(,Self-Scheduling),进程(线程)调度方式,成组调度方式(,Gang Scheduling),将一进程中一组线程,分配到一组处理器上去执行,优点:,一组相互合作的进程或线程能并行执行,可有效地减少进,/,线程阻塞情况的发生,从而减少线程的切换;,每次调度可解决一组线程的处理器分配问题,因而可显著减少调度的频率,从而减少调度开销。,进程(线程)调度方式,成组调度方式(,Gang Scheduling),面向所有应用程序平均分配处理器时间,假定系统中有,N,个处理器和,M,个应用程序,每个 应用程序中至多含有,N,个线程,则每个应用程序,至多可占有,N,个处理器的1/,M,时间,。,面向,所有线程,平均分配处理器时间,假定,M,个应用程序共有,L,个线程,则每个线程至多可占有,N,个处理器的1/,L,时间。,进程(线程)调度方式,成组调度方式(,Gang Scheduling),程序,A,程序,B,P1,线程1,线程1,P2,线程2,空闲,P3,线程3,空闲,P4,线程4,空闲,程序,A,程序,B,P1,线程1,线程1,P2,线程2,空闲,P3,线程3,空闲,P4,线程4,空闲,1/2 1/2,4/5 1/5,面向所有应用程序平均分配,面向所有线程平均分配,1/2*3/4=3/8=37.5%,1/5*3/4=3/20=15%,进程(线程)调度方式,专用处理器分配方式,(,Dedicated Processor Assignment),在一个应用程序的执行期间,专门为该应用程序分,配一组处理器,,每一个线程一个处理器,,这组处理,器仅供该应用程序专用,直至该应用程序完成。,虽然会造成处理机的严重浪费,但在,高度并行,的系,统,每个处理器的利用率不是十分重要。,在同时执行的多道应用程序中,其线程总数不应超过系统中处理机的数目。,单机双核调度方案,是否双核一定比单核运行快呢?,死锁举例,死锁产生的原因,死锁产生的必要条件,死锁的基本处理方法,举例,例1:,两个小孩在一起玩耍,一个在玩皮球,另一个玩自动步枪,如果这两个小孩都要对方手中的玩具,而又不肯先放掉自己拿着的玩具,这时就发生了僵持局面。,举例,例2:,设系统有一台打印机和一台扫描仪,进程,P1、P2,并发执行,在某时刻,T,,进程,P1,和,P2,分别占用了打印机和扫描仪。在时刻,T1(T1T),P1,又要申请扫描仪,但由于扫描仪被,P2,占用,,P1,只有等待。在时刻,T2(T2T),P2,又申请打印机,但由于打印机被,P1,占用,,P2,只有等待。如此两进程均不能执行完成。称这种现象为,死锁,。,P1,P2,举例,一组进程中,每个,进程都,无限,等待被该组进程中另一进程所占有的资源,而处于的一种僵持局面,若无外力作用,它们都无法向前推进,这种现象称为,进程死锁(,Deadlock),,,这组进程就称为,死锁进程,。,原因,竞争资源引起进程死锁,可剥夺和,非可剥夺资源,可剥夺资源:进程在获得这个资源后可以在被其它进程或系统剥夺,非可剥夺资源:资源被系统分配给某个进程后就不能强行收回,只能进程自己释放,竞争非可剥夺资源,R,1,R,2,P,1,P,2,原因,竞争资源引起进程死锁,竞争临时性资源(进程通信时,),S,1,S,2,P,1,P,2,S1,、,S2,为消息,箭头分别为发送和接收,原因,进程推进顺序不当引起死锁,P,1,Req(R,1,)P,1,Req(R,2,)P,1,Rel(R,1,)P,1,Rel(R,2,),P,2,Rel(R,1,),P,2,Rel(R,2,),P,2,Req(R,1,),P,2,Req(R,2,),D,必要条件,四者必备,互斥条件,Mutual exclusion,不剥夺条件,no preemption,不能剥夺进程拥有资源,请求保持条件,hold and wait,环路条件,circular wait,进程在等待一新资源时继续占有已分配的资源,涉及的资源是非共享的,必要条件,四者必备,互斥条件,Mutual exclusion,不剥夺条件,no preemption,请求保持条件,hold and wait,环路条件,circular wait,存在一种进程的循环链,链中的每一个进程已获得的资源同时被链中的下一个进程所请求,处理方法,预防死锁,(,deadlock prevention),通过设置某些限制条件,去,破坏死锁四个必要条件中的一个或多个,,来防止死锁。,较易实现,广泛使用。,由于所施加的限制往往太严格,可能导致系统资源利用率和系统吞吐量的降低。,处理方法,避免死锁,(,deadlock avoidance),不事先采取限制去破坏产生死锁的条件,而是,在,资源的动态分配,过程中,用,某种方法,去防止系统进入,不安全状态,,从而避免死锁的发生。,事先只需要,较弱的限制条件,,可获得,较高的,资源,利用率,和系统吞吐量。,实现较难。,处理方法,检测死锁,(,deadlock detection),事先并不采取任何限制,也不检查系统是否进入不安全区,,允许死锁发生,;,但可通过检测机构及时检测出死锁的发生,并精确,确定与死锁有关的进程和资源,,然后采取适当措施,将系统中已发生的死锁清除掉。,处理方法,解除死锁,(,deadlock recovery),与检测死锁相配套,用于将进程从死锁状态解脱,出来。,常用的方法是,撤消或挂起一些进程,。以回收一些,资源,再将它们分配给处于阻塞状态的进程,使,之转为就绪状态。,实现难度大,但可获得较好的资源利用率和系统,吞吐量。,处理方法,鸵鸟算法,(,The Ostrich Algorithm),Pretend there is no problem,Reasonable if,deadlocks occur very rarely,cost of prevention is high,UNIX and Windows takes this approach,It is a trade off between,convenience,correctness,总 结,多处理机调度,进程分配方式,进,/,线程调度方式,实时调度,基本条件,算法分类,EDF,、,LLF,死 锁,定义,产生原因,必要条件,处理方法,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


OS03特殊系统调度.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14770897.html