admin管理员组文章数量:1530061
可持续性(sustainability)可以针对 调度算法 和 可调度性测试 两个而言的。
可持续调度算法(sustainable scheduling algorithm):系统运行前,被判定(也有可能是穷举法等方式来判定)为可调度的了,如果任务的实际运行情况比理论时候(运行前)的参数更好(比如实际的执行时间小于WCET,达到实际周期更长了,截止期更远了,更小的实际释放抖动),此时整个实际系统仍然是可调度的(所有任务截止期照样得到满足)。这个对于实时操作系统开发人员,很重要,因为我们只能设计时用最坏的情况(比如测任务执行时间),所设计的调度系统(即,所使用的调度算法)必须是可持续性的,否则,产生严重后果。
可持续性的可调度性测试(sustainable schedulability test):该测试需要满足如下两个条件,才被成为可持续性的:
- 采用该可调度性测试判定 一个可持续调度算法 为可调度的,那么实际运行行为更好了,那么应该仍然能满足截止期。(我觉得这个条件,依赖于调度算法是不是可持续性的)
- 当把任务模型的参数放宽了(不是运行时行为了),此时再用该可调度性测试进行判定,仍然要能是可调度的。(这个特性也叫做 自可持续性(self-sustainability))
第一个条件针对 任务调度算法 的属性的,第二个是 可调度性测试算法 的属性。
很明显,第一个条件,只要 调度算法是可持续性的,那么就能满足了。但是第二个条件就没那么容易满足了。(注意:不是说只要一个可调度性测试是可持续性的,那么对应的调度算法一定是可持续的了,这两者没有必然关系,举例,全局EDF调度算法关于截止期是是否可持续性悬而未决,但是却已经存在的充分性的全局EDF可调度性测试算法满足截止期模型参数变大后,仍然能判定为可调度,比如本文最后讨论的一个测试算法)
这里举两个例:(因此我们说一个可调度性测试算法不是可持续性的,往往是因为它不具有自可持续性)
1. 在单处理器EDF调度的充分性可调度性测试算法中:sporadic偶发实时任务多核分区动态优先级EDF(或者DM)调度(以及可调度性分析)经典算法详解_标biao的博客-CSDN博客
对于待测试任务 i,Di增大一点,很明显不等式左边项增大幅度更大(因为存在求和项),导致不等式不再成立,就会判定为不可调度。因为实际情况来说,截止期大一点了,应该整个系统照样能调度成功才对呀。所以,该可调度性测试算法不是可持续性的。
2. 精确可调度性测试RTA算法就是可持续性的。
我们设计实际实时系统时选用的调度算法,首先必须是可持续调度算法。其次,关于可调度性测试是否也选用可持续性的,就看我们设计阶段的场景了。比如需要在设计工具里动态的修改模型参数,再探索其它的任务的可调度性,就是需要不断放宽参数来探索的过程,那么,就该设计工具中就需要集成的是可调度性测试。sanjoy书P131页举了个实际系统设计的例子。
已有的一些理论研究成果,关于已有的调度算法和可调度性测试的可持续性到底怎样,可以看这两篇论文:
- Sustainable Scheduling Analysis
- Sustainable multiprocessor scheduling of sporadic task systems
任务参数一般5个:到达偏移,释放抖动,执行时间,截止期,周期,但是一般默认指(C,D,T)这三个参数而已
(Sustainable Scheduling Analysis论文)大概核心内容如下:
- 利用率上界的可调度性测试算法是可持续的,对所有参数成立。比如RM等
- 响应时间RTA可调度性测试算法是可持续的,而且即使有共享资源情况下(有阻塞时间参数)的测试,对所有参数成立
- The Leung and Whitehead test(The exact fixed-priority schedulability test for periodic task)不是可持续的
- 带释放抖动情况下的可调度性分析,仍然是可持续的,比如(D-J)单调调度,J减小了,照样能满足截止期(优先级不改变也ok,实际上可能应该服从新的优先级顺序了)单核处理器实时任务调度中各种最优调度算法汇总_标biao的博客-CSDN博客
(Sustainable multiprocessor scheduling of sporadic task systems论文)大概核心内容如下:
- 对于单核,固定优先级调度(可以指定任意优先级分配)和动态优先级调度(EDF等)对于所有参数,都是可持续性调度算法
- 全局固定优先级调度(带全局字眼的就指全局多核调度策略),关于C, D, T都是可持续性的调度算法
- 全局EDF调度,仅仅关于截止期参数,是不是可持续性的,目前还悬而未决
- 全局EDZL调度,仅仅关于截止期参数,是不是可持续性的,目前还悬而未决
- 尽管EDF, EDZL调度关于截止期的可持续性还未知,但是我们只要按照理论任务模型的截止期去动态分配优先级(尽管运行时任务实际截止期大于任务模型截止期了,但是也别用这个实际的截止期),那么这两个调度算法照样能用,是安全的。
前面几条讲的对调度算法的可持续性,该文章接下来讲了几条关于可调度性测试算法的可持续性:
- 全局可调度性充分性测试算法BCL是不可持续性的,(上面举的第一个例子虽然不是BCL,但是也是类似的例子,只是是分区调度而已),还证实了好几个全局EDF可调度性测试算法都可调度性
- 证实了一个全局可调度性充分性测试算法是可持续性的(包括截止期),(证明核心思想:不等式右侧的减小,不等式整个右侧的值会单调增大,因此截止期变大(实实在在的模型参数变大了,而不是运行时运行情况更好behave better),新任务集照样会被判定为可调度的)如下:
最后该论文提出了两个开放性的问题,大家有兴趣可以去深入研究:
- 剩下的那些全局EDF的充分性可调度性测试算法 的可持续性是怎样的呢?
- 是否能找到个任务集的例子?调度算法是不可持续性的,但是它的可调度性测试是可持续性的。这个也就是上面这个定理5(全局EDF调度关于截止期的可持续性悬而未决,但是却找到了一个关于截止期仍然是可持续性的可调度性测试算法),那么能否实际举出一个任务集例子来看看呢?
版权声明:本文标题:实时调度算法和可调度性测试为可持续性(sustainability)和自可持续性(self-sustainability)基本概念以及作用详解 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1726656361a1080124.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论