Implementation of the EDF policy in Xenomai

• José Augusto Santos UFBA
• George Lima UFBA

Abstract

The scheduler of Xenomai, a Linux-based real-time operating system, is extended to provide support to the Earliest Deadline First (EDF) scheduling policy. The described EDF implementation is simple, compatible with the current Xenomai scheduler and provides support to hierarchical scheduling. The proposed implementation is evaluated by experiments, which show that task activation latency is not significantly altered.

References

Barreto, L. (2004). “Uma Arquitetura Baseada em Eventos para Desenvolvimento de Políticas de Escalonamento de Processos”. 1o Workshop de Sistemas Operacionais.

Behnam, M., Nolte, T., Shin, I., and Asberg, M. (2008). “Towards Hierarchical Scheduling in VxWorks”. In 4th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, pages 63–71.

Buttazzo, G. C. (2005). “Rate Monotonic vs. EDF: Judgment Day”. Real-Time Systems, 29(1):5–26.

Checchoni, F., Trimarchi, M., and Faggioli, D. (2009). “An Implementation of the Earliest Deadline First Algorithm in Linux”. In 24th ACM Symposium on Applied Computing, pages 1984–1989.

Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2002). Algoritmos: teoria e prática. Editora Campus.

Gerum, P. (2004). “Xenomai - Implementing a RTOS Emulation Framework on GNU/Linux”. Technical report, Xenomai, [link].

Harbour, M. G. and Palencia, J. C. (2003). “Response Time Analysis for Tasks Scheduled Under EDF Within Fixed Priorities”. In 24th IEEE International Real-Time Systems Symposium, page 200. IEEE Computer Society.

Liu, C. L. and Layland, J. W. (1973). “Scheduling Algorithms for Multiprogram in a Hard Real-Time Environment”. Journal of ACM, 20(1):46–61.

Molnar, M. (2006). The EDF Scheduler Implementation in RTEMS Operating System. Master’s thesis, Czech Technical University in Prague. Faculty of Electrical Engineering.

Osman, S., Subhraveti, D., Su, G., and Nieh, J. (2002). “The Design and Implementation of Zap: A System for Migrating Computing Environments”. ACM SIGOPS Operating Systems Review, 36(SI):361–376.

Preempt-RT (2008). Preempt-RT howto. [link].

QNX (2002). “Maximizing Performance with SMP: Design Application to Run on Multiple,Tightly Coupled Processors”. Technical report, QNX Software System.

QNX (2009). Qnx Home Page. [link].

Regnier, P., Lima, G., and Barreto, L. (2008a). “Avaliação do Determinismo Temporal no Tratamento de Interrupções em Plataformas de Tempo Real Linux”. In 5o Workshop de Sistemas Operacionais, pages 13–24.

Regnier, P., Lima, G., and Barreto, L. (2008b). “Evaluation of Interrupt Handling Timeliness in Real-Time Linux Operating Systems”. ACM SIGOPS Operating Systems Review, 42(6):52–63.

RT-Linux (2008a). RT-Linux GPL Home Page. [link].

RT-Linux (2008b). RT-Linux Home Page. [link].

RTAI (2008). RTAI Home Page. [link].

RTEMS (2009). Rtems Home Page. [link].

Stankovic, J. A., Spuri, M., Ramamritham., K., and Buttazzo, G. C. (1998). Deadline Scheduling For Real-Time Systems EDF and Related Algorithms. Kluwer Academic Publishers, 1st edition.

VRTX (2009). Mentor Graphics Home Page. [link].

VxWorks (2009). Wind river Systems Home Page. [link].

Xenomai (2005). “Life with Adeos”. Technical report, Xenomai, [link].

Xenomai (2006). “A Tour of the Native API”. Technical report, Xenomai, [link].

Xenomai (2008a). Xenomai-core Mailing List. [link].

Xenomai (2008b). Xenomai Home Page. [link].