Критерий существования бесконфликтного расписания для системы строго периодических задач
https://doi.org/10.15514/ISPRAS-2017-29(6)-10
Abstract
В критических системах выполнение жестких требований по времени взаимодействия между задачами обеспечивается строгой периодичностью запуска задач, когда каждая задача стартует через равные промежутки времени. При планировании строго периодических задач с прерываниями наиболее трудным этапом является выбор начальных стартовых точек задач. В настоящей работе предлагается новый подход к анализу расписаний, основанный на изучении раскрасок графов периодов задач и на решении систем линейных сравнений. Основным результатом является критерий существования бесконфликтного расписания для произвольного количества строго периодических задач с прерываниями на одном процессоре. Критерий позволяет либо направленно найти стартовые точки, либо быстро установить, что расписание построить невозможно.
About the Authors
S. A. Zelenova
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
S. V. Zelenov
Ivannikov Institute for System Programming of the Russian Academy of Sciences; National Research University Higher School of Economics (HSE)
Russian Federation
Russian Federation
References
1. A. A. Zykov. Fundamentals of Graph Theory. BCS Associates, 1990.
2. N. Christofides. Graph Theory. An Algorithmic Approach. Academic Press, 1975.
3. O. Ore. Theory of graphs. American Mathematical Society, 1962.
4. I.M. Vinogradov. Elements of Number Theory. Dover Publications Inc. 1954.
5. S.V. Zelenov. Scheduling of Strictly Periodic Tasks in Real-Time Systems. Trudy ISP RAN/Proc. ISP RAS, vol. 20, 2011, pp. 113-122 (in Russian).
6. A.V. Tretyakov. Automation of scheduling for periodic real-time systems. Trudy ISP RAN/Proc. ISP RAS, vol. 22, 2012, pp. 375-400 (in Russian). DOI: 10.15514/ISPRAS-2012-22-20.
7. Kermia O., Sorel Y. Schedulability Analysis for Non-Preemptive Tasks under Strict Periodicity Constraints. Proceedings of the 2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2008, p. 25-32.
8. Liu C.L., Layland J.W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM, 1973, No 20, p. 46-61.
9. Liu J.W.S.W. Real-Time Systems. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edn. 2000.
10. Marouf M., Sorel Y. Schedulability conditions for non-preemptive hard real-time tasks with strict period. Proceedings of 18th International Conference on Real-Time and Network Systems, RTNS'10, 2010, p. 50-58.
11. Yomsi P.M., Sorel Y. Non-Schedulability Conditions for Off-line Scheduling of Real-Time Systems Subject to Precedence and Strict Periodicity Constraints. Proceedings of 11th IEEE International Conference on Emerging technologies and Factory Automation, ETFA'06, WIP, Prague, Czech Republic, September 2006.
12. Yomsi P.M., Sorel Y. Schedulability Analysis for non Necessarily Harmonic Real-Time Systems with Precedence and Strict Periodicity Constraints using the Exact Number of Preemptions and no Idle Time. Proceedings of the 4th Multidisciplinary International Scheduling Conference, MISTA'09, Dublin, Ireland, August, 2009.
Review
For citations:
Zelenova S.A., Zelenov S.V. . Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(6):183-202. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(6)-10
Email this article 