Scheduling of Strictly Periodic Tasks in Real-Time Systems
Abstract
The very important subsystem in a real-time system is a task scheduler. Classical algorithms for periodic tasks scheduling imply that release points of each task may vary inside different periods of the task. However, nowadays, some systems require a scheduler that can build schedules where release points of each task form an arithmetic progression. Such an additional requirement does not allow using classical scheduling algorithms. In this paper, we present a scheduling algorithm that takes into account this additional requirement and builds a schedule close to optimal (in the sense of minimization of total number of tasks interruptions) in acceptable time.
References
1. А.С.Косачев, И.Б.Бурдонов, В.Н.Пономаренко. Операционные системы реального времени. // Препринт Института системного программирования РАН, 2006, № 14. http://citforum.ru/operating_systems/rtos/
2. Liu J.W.S. Real-Time Systems. // Prentice Hall, Englewood Cliffs, NJ, 2000. 600 p.
3. Cottet F., Kaiser J., Mammeri Z. Scheduling in Real-Time Systems. // John Wiley & Sons Ltd. 2002. 282 p.
4. N.N. Kuzjurin. Multiprocessor scheduling and expanders. Information Process. Letters, 1994, v. 51, № 6, 315–319.
5. Н. Н. Кузюрин. Многопроцессорные расписания и комбинаторные конфигурации. Дискретная математика, 1995, т. 7, № 2, 77–87.
6. S. Zhuk, A. Tchernykh, N. Kuzjurin, A. Pospelov, A. Shokurov, A. Avetisyan, S. Gaissaryan, D. Grushin. Comparison of Scheduling Heuristics for Grid Resource Broker. Proc. of the Third International Conference on Parallel Computing Systems (PCS2004). IEEE Computer Society Press, 2004, 388–392.
7. A. Tchernykh, J. M. Ramirez, A. Avetisyan, N. Kuzjurin, D. Grushin, S. Zhuk. Two Level Job-Scheduling Strategies for a Computational Grid. Proc. of the Second Grid Resource Management Workshop. LNCS 3911, 2006, 774–781.
8. A. Tchernykh, U. Schwiegelsohn, R. Yahyapour, N. Kuzjurin. On-line Hierarchical Job Scheduling in Grids with admissible allocation. J. of Scheduling. 2010, v. 13, № 5, 545–552.
9. Liu C. and Layland J.W. Scheduling algorithms for multiprogramming in a hard real-time environment. // Journal of ACM , 20(1): 46–61, 1973.
10. И.М.Виноградов. Основы теории чисел. // М.-Л.: Гостехиздат, 1952. 180 стр.
Review
For citations:
Zelenov S.V. Scheduling of Strictly Periodic Tasks in Real-Time Systems. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2011;20. (In Russ.)
Email this article 