实时新任务的插入问题研究
发布时间：2021-04-10 01:49
在一个单处理器的实时调度系统中,任务加速或者新任务插入所导致的超负荷可以通过任务压缩来应对,这就是弹性调度中的带宽转让。但是为了避免实际的新任务插入过程中可能会发生的截止期丢失,就有必要采用平滑插入方法,而平滑插入问题的关键就是最早平滑时刻的求取。现有一个初步的最早平滑时刻求取方法——Simple way,该方法的核心就是在逐步延迟的释放过程当中试探新任务的平滑插入点,本文以文献研究和仿真实验等方法对该问题做了进一步的考察,获得了比该方法更先进的研究结果。基于EDF（Earliest Deadline First）算法,本文首先在多任务的带宽转让情形下将实时周期任务的模型简化为一个由执行时间,初始周期和受压后周期所组成的三元组,并且以此为基础重新描述了弹性调度中的实时多任务带宽转让过程和过渡过程。然后对现行任务的压缩过程做了细致的分析,分析了该过程中的处理器需求计算方法,接着提出了一个准则——延迟判断准则,在该准则的证明过程中,本文指出新任务的插入所导致的截止期丢失只有两种情况,第一种是现行任务的截止期丢失,第二种是新任务的截止期丢失,并且最终证明了该准则在这两种情形下都成立。延迟判断...
【文章来源】：湖南师范大学湖南省 211工程院校
【文章页数】：57 页
【学位级别】：硕士
【部分图文】：
速率固定算法调度模拟
硕士学位论文10以支持更高的使用率，最理想的情形则是：任务周期之间“两两调和”——即任意选一对任务，它们的周期都存在整数倍数关系，此时RM的可调度使用率可以达到1[58]。但是现实的任务往往是随机的，很难满足上述条件。因此公式（2.1）限定了RM在一般情形下的使用率上界，如果任务周期之间不存在调和关系，那么随着任务数量的增加，RM的可调度上限将会逼近ln2≈0.69，意味着接近30%的处理器资源无法被利用，如图2-2：图2-2：RM的可调度上限与任务数量的关系此外，在RM调度中，最高优先级的任务总是不会丢失截止期，因为其总是能够优先得到足够的资源，而在一般情况下，只要任务集的使用率满足公式（2.1），那么就是RM可调度的，但是如果系统载荷超过该值时，调度就会发生不可预测的截止期丢失，因此RM无法充分的利用处理器资源，因而也就无法应用于高负载情形[59]。2.3.2最早截止期优先调度算法最早截止期优先调度算法即EDF调度算法，是一种可抢占式的动态优先级调度算法，和RM相比，EDF的主要优点在于其对系统资源的利用率更高。EDF的动态优先级意味着任务的优先级会随着任务的运行而变化，在任意时刻，任务的优先级都由其截止期决定，截止期越近意味着该任务的处理需求越紧急，因此相应的任务优先级就越高[60]。在EDF调度中，任务的优先级会随着调度过程的进行而变化，具体的，由于EDF算法中，任务的优先级取决于该任务当前作业的截止期，截止期越近的任务被执行的优先级就越高，而当本周期的执行量完成之后，该任务的截止期就会回到最初的初始优先级，而其它优先级更高的任务会被选择执行[1]。因此每个任务的优先级都会随着调度的进行而变化，而且由于实时任务的周期性特点，这个变化也呈现出周期性。下面举一个简单的例子来说
硕士学位论文12图2-3：最早截止期优先算法调度示例图2-3的上面三行表示三个任务的调度执行，在每一行的最左边为任务名，如τ0[1,4]表示该任务的名称为τ0，执行量为1，周期为4，竖的实线表示该任务的周期线，黑色的矩形表示该任务在该时刻被执行，最后一行time表示时间轴，部分调度过程如前面所述。由于任务总是周期性的发起请求，因此，每个任务的相对截止期是不断变化的。显然，维护一个不断更新的优先队列需要付出巨大的开销，因此EDF一般只在调度事件发生时才选取截止期最接近的任务，这就意味着每个任务都要维护自身的截止期数据，在每个周期开始时都要重置自身的截止期数据，并且在运行时不断更新其截止期数值。虽然在EDF中，任务的优先级是随着任务截止期的变化而变化的，但是EDF的调度逻辑从根本上依然是基于优先级的，因此EDF和RM在实现时的主要区别在于，EDF需要实现额外的截止期的维护工作。当然，EDF和RM算法的区别和特点还有许多，此处不再过多赘述。如果不考虑任务的中断、迁移等操作所引入的额外开销，且没有实时新任务的情况下（即所有任务都在时刻0释放），那么对于EDF算法，有定理2.1成立[61]。定理2.1（EDF可调度准则）：如果一个实时周期任务集的使用率之和不大于1，那么就是EDF可调度的。因此，EDF对处理器资源的利用率更高，能够很好的适应高负载情形下的实时调度环境。2.4弹性调度与平滑插入弹性调度（ElasticScheduling）一种基于EDF的实时调度模型，是一种能够根据外部环境或实际需要的变化来动态调整任务集合的自适应模型，其弹性概念的引入可以很好的适用于有动态计算需求的实时应用程序。在弹性调度模型中，
【参考文献】：
期刊论文
[1]最晚截止期优先带宽转让算法[J]. 钱光明,杨扬. 计算机工程. 2013(09)
[2]实时任务调度算法最早可行时刻的求取模式[J]. 钱光明,姜辉,陈湘华. 计算机工程. 2012(04)
[3]平滑而快速地插入新任务[J]. 钱光明. 湖南文理学院学报(自然科学版). 2008(02)
[4]一种改进的时间片轮转调度算法[J]. 肖建明,张向利. 计算机应用. 2005(S1)
[5]四种嵌入式实时操作系统关键技术分析[J]. 季志均,马文丽,陈虎,郑文岭. 计算机应用研究. 2005(09)
[6]实时系统任务模型初探[J]. 钱光明. 仪器仪表用户. 2005(04)
博士论文
[1]实时系统动态优先级任务调度算法的研究[D]. 巴巍.大连理工大学 2010
硕士论文
[1]实时多任务压缩和插入问题的研究[D]. 梁丽稳.湖南师范大学 2019
[2]EDF算法中任务对带宽转让问题的研究[D]. 周垠宇.湖南师范大学 2017
本文编号：3128717
【文章来源】：湖南师范大学湖南省 211工程院校
【文章页数】：57 页
【学位级别】：硕士
【部分图文】：
速率固定算法调度模拟
硕士学位论文10以支持更高的使用率，最理想的情形则是：任务周期之间“两两调和”——即任意选一对任务，它们的周期都存在整数倍数关系，此时RM的可调度使用率可以达到1[58]。但是现实的任务往往是随机的，很难满足上述条件。因此公式（2.1）限定了RM在一般情形下的使用率上界，如果任务周期之间不存在调和关系，那么随着任务数量的增加，RM的可调度上限将会逼近ln2≈0.69，意味着接近30%的处理器资源无法被利用，如图2-2：图2-2：RM的可调度上限与任务数量的关系此外，在RM调度中，最高优先级的任务总是不会丢失截止期，因为其总是能够优先得到足够的资源，而在一般情况下，只要任务集的使用率满足公式（2.1），那么就是RM可调度的，但是如果系统载荷超过该值时，调度就会发生不可预测的截止期丢失，因此RM无法充分的利用处理器资源，因而也就无法应用于高负载情形[59]。2.3.2最早截止期优先调度算法最早截止期优先调度算法即EDF调度算法，是一种可抢占式的动态优先级调度算法，和RM相比，EDF的主要优点在于其对系统资源的利用率更高。EDF的动态优先级意味着任务的优先级会随着任务的运行而变化，在任意时刻，任务的优先级都由其截止期决定，截止期越近意味着该任务的处理需求越紧急，因此相应的任务优先级就越高[60]。在EDF调度中，任务的优先级会随着调度过程的进行而变化，具体的，由于EDF算法中，任务的优先级取决于该任务当前作业的截止期，截止期越近的任务被执行的优先级就越高，而当本周期的执行量完成之后，该任务的截止期就会回到最初的初始优先级，而其它优先级更高的任务会被选择执行[1]。因此每个任务的优先级都会随着调度的进行而变化，而且由于实时任务的周期性特点，这个变化也呈现出周期性。下面举一个简单的例子来说
硕士学位论文12图2-3：最早截止期优先算法调度示例图2-3的上面三行表示三个任务的调度执行，在每一行的最左边为任务名，如τ0[1,4]表示该任务的名称为τ0，执行量为1，周期为4，竖的实线表示该任务的周期线，黑色的矩形表示该任务在该时刻被执行，最后一行time表示时间轴，部分调度过程如前面所述。由于任务总是周期性的发起请求，因此，每个任务的相对截止期是不断变化的。显然，维护一个不断更新的优先队列需要付出巨大的开销，因此EDF一般只在调度事件发生时才选取截止期最接近的任务，这就意味着每个任务都要维护自身的截止期数据，在每个周期开始时都要重置自身的截止期数据，并且在运行时不断更新其截止期数值。虽然在EDF中，任务的优先级是随着任务截止期的变化而变化的，但是EDF的调度逻辑从根本上依然是基于优先级的，因此EDF和RM在实现时的主要区别在于，EDF需要实现额外的截止期的维护工作。当然，EDF和RM算法的区别和特点还有许多，此处不再过多赘述。如果不考虑任务的中断、迁移等操作所引入的额外开销，且没有实时新任务的情况下（即所有任务都在时刻0释放），那么对于EDF算法，有定理2.1成立[61]。定理2.1（EDF可调度准则）：如果一个实时周期任务集的使用率之和不大于1，那么就是EDF可调度的。因此，EDF对处理器资源的利用率更高，能够很好的适应高负载情形下的实时调度环境。2.4弹性调度与平滑插入弹性调度（ElasticScheduling）一种基于EDF的实时调度模型，是一种能够根据外部环境或实际需要的变化来动态调整任务集合的自适应模型，其弹性概念的引入可以很好的适用于有动态计算需求的实时应用程序。在弹性调度模型中，
【参考文献】：
期刊论文
[1]最晚截止期优先带宽转让算法[J]. 钱光明,杨扬. 计算机工程. 2013(09)
[2]实时任务调度算法最早可行时刻的求取模式[J]. 钱光明,姜辉,陈湘华. 计算机工程. 2012(04)
[3]平滑而快速地插入新任务[J]. 钱光明. 湖南文理学院学报(自然科学版). 2008(02)
[4]一种改进的时间片轮转调度算法[J]. 肖建明,张向利. 计算机应用. 2005(S1)
[5]四种嵌入式实时操作系统关键技术分析[J]. 季志均,马文丽,陈虎,郑文岭. 计算机应用研究. 2005(09)
[6]实时系统任务模型初探[J]. 钱光明. 仪器仪表用户. 2005(04)
博士论文
[1]实时系统动态优先级任务调度算法的研究[D]. 巴巍.大连理工大学 2010
硕士论文
[1]实时多任务压缩和插入问题的研究[D]. 梁丽稳.湖南师范大学 2019
[2]EDF算法中任务对带宽转让问题的研究[D]. 周垠宇.湖南师范大学 2017
本文编号：3128717
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3128717.html
