您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

嵌入式操作系统周期任务经典调度算法

时间:2020-11-16 11:11:57  来源:  作者:

引言

随着嵌入式实时操作系统应用的不断深入,多个实时任务并发执行,再加上任务之间不停地动态切换,这对任务调度算法提出了较高的要求。实时操作系统中各个任务的优先级是不同的,而且经常会遇到超负荷的情况.。在这种超载情况下,使任务集内各任务满足各自的时限,嵌入式操作系统必须保证在确定的时间内对事件进行处理,因此必须要有一个良好的任务调度算法。周期任务和非周期任务是实时嵌入式系统中的常见任务类型,系统实时任务调度策略主要包括时间驱动调度策略、优先级驱动调度策略。常见的动态优先级调度算法有最早截止期优先调度算法和最小空闲时间优先算法、单调速率调度算法和最大价值优先算法等。

实时系统的任务按产生请求的频率可分为周期性任务与非周期性任务:周期性任务按照固定的请求间隔持续地产生请求,不同的任务请求间隔不一定相同。 非周期性任务在任意一段时间间隔内可能产生不定数量的请求。按任务优先级分配方式可分为静态优先级任务和动态优先级任务。

1)固定优先级调度算法

在实时调度算法中,固定优先级调度算法事先根据任务的属性,如任务的周期、截止期限等为系统中的所有任务静态分配一个优先级。当任务的截止期限等于周期时,提出了RMS调度算法,它根据任务的执行周期长短的不同来决定优先级,即任务的周期越小优先级越高,任务的周期越大优先级越低。以RMS为代表的固定优先级调度算法,一方面不仅具有运行时间开销小和易于实现的优点,而且在系统超载情况下,仍然可以保证高优先级的任务得到执行;但另一方面却是不能充分地利用系统资源。

2)动态优先级调度算法

在实时调度算法中,动态优先级调度算法根据任务资源需求的变化以及任务的属性,如任务周期、截止期限等动态地决定任务的优先级。当任务的截止期限等于周期时,提出了EDF调度算法,该算法根据就绪队列中任务的截止期限分配优先级,距离绝对截止期限的最近的任务具有最高的优先级,即任务的绝对截止期限越小优先级越高,任务的绝对截止期限越大优先级越低。以EDF为代表的动态优先级调度算法,一方面可以充分地利用系统的资源;但是另一方面在系统负荷严重超载时,系统性能很不稳定,导致大多数任务在截止期限到来之时仍无法满足。

3)静态优先调度算法与动态优先调度算法的比较

静态调度是指系统脱机地进行调度可行性分析后生成一个可调度表,在运行的过程中,调度表中的信息不再发生任何变化。该类调度算法假定系统实时任务的属性是提前已知的并且在执行过程中很少发生变化,特别适合于对那种确定问题的求解,具有较好的可预测性。

单调速率调度算法(Rate Monotonic Algorithm, RM)

单调速率调度算法是一种被广泛使用的调度算法, 并且已被证明是一种最佳的静态优先级算法。单调速率调度(RMS)算法是C.L.Liu和J.W.Layland在1973年引入提出的一种基于周期和多任务的静态优先级可抢占调度算法。RMS是针对周期任务的优先级调度算法,当任务的截止时间等于其周期时,RMS算法已被证明是静态最优的调度算法。

当较低优先级的进程正在运行并且较高优先级的进程可以运行时,较高优先级进程将会抢占低优先级。在进入系统时,每个周期性任务会分配一个优先级,它与其周期成反比,即周期越短,优先级越高;周期越长,优先级越低。这种策略背后的理由是:更频繁地需要 CPU 的任务应分配更高的优先级。此外,单调速率调度假定:对于每次 CPU 执行,周期性进程的处理时间是相同的。也就是说,在每次进程获取 CPU 时,它的 CPU 执行长度是相同的。

嵌入式操作系统周期任务经典调度算法

 

假设有两个进程 P1 和 P2。P1 和 P2 的周期分别为 50 和 100,即 ρ1 = 50 和 ρ2= 100。P1 和 P2 的处理时间分别为 t1 = 20 和 t2 = 35。每个进程的截止期限要求,它在下一个周期开始之前完成 CPU 执行。
首先,P1 开始,并在时间 20 完成 CPU 执行,从而满足第一个截止期限。P2 在这点开始运行,并运行直到时间 50。此时,它被 P1 抢占,尽管它的 CPU 执行仍有 5ms 的时间。P1 在时间 70 完成 CPU 执行,在这点调度器恢复 P2。P1 在时间 75 完成 CPU 执行,也满足第一个截止期限。然后,系统一直空闲直到时间 100,这时,P1 再次被调度。
单调速率调度可认为是最优的,因为如果一组进程不能由此算法调度,它不能由任何其他分配静态优先级的算法来调度。

最早截止时间优先(Earliest DeadlineFirst, EDF)

最早截止时间优先EDF算法是非常著名的实时调度算法之一。EDF调度算法是单处理器环境下调度性能最优的一种动态调度系统任务的算法。EDF调度算法的优先级是以所调度任务的截止期与当前时刻的差值来确定的差值越小证明任务的截止期越早,与其他差值大的任务相比优先级就越高,越需优先执行避免错过任务截止期而导致任务夭折。因此,采用EDF调度算法可以保证当前离截止期最近的任务获得系统资源和控制权,优先进行调度。EDF调度算法最大的优点是大幅度提升处理器的利用率,采用EDF调度算法进行调度时,处理器的利用率可以达到最大值。 但EDF调度算法在进行任务调度时系统开销较大,且任务调度过程中无法对系统负载情况进行量化判断,无法应对系统高负载情况下的任务调度问题。EDF算法在调度过程中存在任务错失截止期的情况,进而影响其他等待调度任务的正常调度,致后续多个任务错失截止期而夭折。在系统超负载的情况下调度算法会导致系统任务调度的成功率大幅度降低,影响嵌入式系统的实时调度性能。

在每一个新的就绪状态,调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务,并将执行该任务所需的资源分配给它。在有新任务到来时,调度器必须立即计算EDF,排出新的定序,即正在运行的任务被剥夺,并且按照新任务的截止时间决定是否调度该新任务。如果新任务的最后期限早于被中断的当前任务,就立即处理新任务。按照EDF算法,被中断任务的处理将在稍后继续进行。该算法的思想是从两个任务中选择截至时间最早的任务,把它暂作为当前处理任务,再判断该任务是否在当前周期内,若不在当前周期内,就让另一任务暂作当前处理任务,若该任务也不在当前周期内,就让CPU空跑到最靠近的下一个截至时间的开始,若有任务在该周期内,就判断该任务的剩余时间是否小于当前截至时间与当前时间的差,若小于,则让该任务运行到结束。否则,就让该任务运行到该周期的截止时间,就立即抢回处理器,再判断紧接着的最早截至时间,并把处理器给它,做法同上,如此反复执行。

最小空闲时间优先算法(Least Slack First,LSF)

最小空闲时间优先LSF算法结合任务执行的缓急程度来给任务分配优先级。任务所剩的空闲时间越少,就越需要尽快执行。最小空闲时间优先调度算法改进了EDF算法的性能,算法中任务优先级由任务空闲时间片数值来决定, 即任务截止时间与剩余执行时间之差,空闲时间片数值越小,任务优先执行的级别越高,LSF调度算法通过紧急任务优先执行策略一定程度上解决了EDF算法存在的问题,但调度算法存在任务调度频繁抢占问题,增加了系统的开销同时也降低了实时系统的性能。



Tags:调度算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
在任务调度的场景中,经常遇到以下需求:1、某个操作失败后,每隔1、2、5、10、20秒去重试2、一篇公众号文章发布之后,要在5分钟之后推送到粉丝终端这种场景当然可以通过 RocketMQ...【详细内容】
2021-05-21  Tags: 调度算法  点击:(206)  评论:(0)  加入收藏
引言随着嵌入式实时操作系统应用的不断深入,多个实时任务并发执行,再加上任务之间不停地动态切换,这对任务调度算法提出了较高的要求。实时操作系统中各个任务的优先级是不同的...【详细内容】
2020-11-16  Tags: 调度算法  点击:(170)  评论:(0)  加入收藏
linux内核调度程序很先进很强大,管理你的LINUX上跑的大量的乱七八糟的进程,同时还保持着对用户操作的高灵敏响应,如果可能,为什么不把这种思想放到自己的应用程序里呢?或者,有没...【详细内容】
2020-11-11  Tags: 调度算法  点击:(126)  评论:(0)  加入收藏
摘要:ETL是将业务系统的数据经过抽取、清洗转换之后加载到数据仓库的过程,是构建数据仓库的重要一环,用户从数据源抽取出所需的数据,经过数据清洗,最终按照预先定义好的数据仓库...【详细内容】
2020-09-27  Tags: 调度算法  点击:(67)  评论:(0)  加入收藏
明确先来先服务FCFS、时间片轮转RR、优先级三种常用的调度算法的实现思想,并在此基础上计算周转时间、带权周转时间、平均周转时间和平均带权周转时间。(一)先来先服务先来先服...【详细内容】
2020-07-27  Tags: 调度算法  点击:(141)  评论:(0)  加入收藏
一、轮叫调度(Round­Robin Scheduling )(1)轮叫的方式依次将请求调度不同的服务器(2)算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。二、加...【详细内容】
2019-09-25  Tags: 调度算法  点击:(143)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条