Concurrent Real-time Schedulers, a Classification Based on Functions

Pedro Guevara-López
National Polytechnic Institute – Higher School of Mechanical and Electrical Engineering
Santa Ana 1000, Mexico City, C. P. 04430, Mexic

Oscar A. Morales-Moreno
National Polytechnic Institute – Research Center for Applied Science and Advanced Technology
Legaria 964, Mexico City, C. P. 11500, Mexico

José S. Falcón-López
Cuautitlán Izcalli Institute of Technology
Nopaltepec S/N, Estado de Mexico, C. P. 54748, Mexico

Abstract:

Real-time Systems (RTS) are generally implemented into digital computers with Real-time Operating Systems (RTOS) where all activities are performed by a set of Concurrent Real-time Tasks (CRTT) which requires attention by a processor through a Concurrent Real-time Task Scheduler (CRTTS). In this sense, this concept is commonly considered as a resource allocator to tasks by means of preset algorithm. However, a RTTCS is a function that maps the Set of Arrival Times (ATS) to the Starting Times Set (STS) of the instances related to CRTTS; this conception is general and independent from the scheduling algorithm used (RM, EDF, FIFO, etc.) and it will be useful to define the working environment of RTS in the analysis of schedulability, reconstruction, fail-safe and predictability. It is also useful to know the scheduler characteristics and determine the type of scheduler we are using in the System.

Keywords:

Real-time Systems, Real-time Tasks, Real-time Schedulers, Arrival Time, Time Constraints.

>>Full text
CITE THIS PAPER AS:
Pedro GUEVARA-LOPEZ, Oscar A. MORALES-MORENO, José S. FAlCON-LOPEZ, Concurrent Real-time Schedulers, a Classification Based on Functions, Studies in Informatics and Control, ISSN 1220-1766, vol. 21 (1), pp. 27-32, 2012. https://doi.org/10.24846/v21i1y201203

1. Introduction

In order to be able to implement an RTS in a digital computer, it is required to have a specific Operating System, in this case, a Real-time Operating System (RTOS); and in this operating system, everything is managed through concurrent Real-time Tasks (RTT). These tasks are in charge of performing all the RTS activities, they have temporary restrictions imposed by the real world and they compete for having processor resources at different temporary intervals; and the one that decides what task will take such resource and when, is the Concurrent Real-time Tasks Scheduler (CRTTS). This paper originates from the need of being able to properly schedule by using a scheduler, since it will help for troubleshooting and to improve scheduling through this rating and behavior analysis.

Within this research area, authors agree on a definition: “Concurrent Real-Time Tasks Scheduler (CRTTS) is an algorithm that allocates processor resources to different areas at different moments” remembering that an algorithm is an orderly and finite set of calculations that allow to find a solution to a problem. This concept is informal, not defining resources, inputs and outputs. For this context, in this work we formally define a Concurrent Real-time Tasks Scheduler. Scheduling algorithms mentioned above are very important to be able to make a general rating of schedulers.

RM algorithm (Rate Monotonic algorithm) as per [1], is a scheduler with fixed priorities that consists of allocating the highest priority to the tasks having the shorter period in the system, and the lowest priority to the tasks with longer periods. A problem with this algorithm is a use of resource lower than 100%. According to [2], EDF algorithm is a dynamic scheduler that selects tasks according to their absolute terms. Tasks with short terms will be executed with high priorities, and tasks with long terms will have low priorities. An advantage of this algorithm is that the usage of the resource is almost of 100% for all the tasks set. FIFO algorithm as per [3], this type of scheduling is executed on demand; the first task that arrives is the first one to be executed, until the last one is finished.

References:

LIU, C., J. LAYLAND, Scheduling Algorithms for Multiprogramming in Hard Real-Time Environment. Journal of the ACM, Vol. 20, No. 4, 1973, pp. 273-250.
BUTTAZZO, G. Hard Real-Time Computing Systems, Scuola Superiore S. Anna, Kluwer Academic Publishers, 1997.
QNX System Architecture System Guide. QNX Software System Ltd, 1997
MEDEL, J. J., P. GUEVARA, D. CRUZ, Temas Selectos de Sistemas en Tiempo Real. Publicado por la editorial Politécnico Registro de Derechos de Autor: 03-2003-012912240400-0,1 ISBN: 978-970-36-0466-1. México Diciembre de 2007.
MÁQUEZ, G. F. UNIX Programación avanzada. Universidad de Alcalá de Henares (Madrid), Addison Wesley Iberoamericana, 1993.
CRUZ, D., Modelo Dinámico para Tareas en Tiempo Real, tesis de Maestría en Ciencias de la Computación, CIC-IPN, 2004. México, Agosto de 2004
CRUZ, D. Modelo para Tiempos de Arribo de Tareas en Tiempo Real Concurrentes, tesis de Doctorado en Tecnología Avanzada, CICATA-IPN, 2007. México, Diciembre.
CRUZ, D., P. GUEVARA, J. MEDEL, Modelo para Tiempos de Arribo de Tareas en Tiempo Real Concurrentes. Revista Computación y Sistemas, ISSN 1405-546, Vol. 12 No. 4, México, Abril.
BOUKEF, H., M. BENREJEB, P. BORNE, Flexible Job-shop Scheduling Problems Resolution Inspired from Particle Swarm Optimization. Studies in Informatics and Control, Volume 17, Issue 3, Bucharest, Romania, 2008, pp. 241-252.
RAJKUMAR, R., P. SHAHABUDEEN, P. NAGARAJ, S. ARUNACHALAM, T. Page, A Bi-Criteria Approach to the M-machine Flowshop Scheduling Problem. Studies in Informatics and Control, Volume 18, Issue 2. Bucharest, Romania, 2009, pp. 127-136
MEJIA, P., Curso de Sistemas En Tiempo Real (Sistemas Operativos). CINVESTAV-IPN, Sección de Computación, México D. F. 2008.
GUEVARA, L. P., J. J. MEDEL J., Introducción a los Sistemas de Tiempo Real. Editorial Politécnico, registro de Derechos de Autor 03-2003-012912240400-01, México, 2003.
MORALES, O., Formalización del Concepto de Planificador de Tareas en Tiempo Real Concurrentes, Tesis de Maestría en Tecnología Avanzada, CICATA-IPN.
GUEVARA, P., G. DUCHEN, O. MORALES, El Concepto de Planificador de Tareas en Tiempo Real Basado en Funciones.CIINDET 2009 VII Congreso Internacional en Innovación y Desarrollo Tecnológico, 7 al 9 de octubre de 2009, Cuernavaca, Morelos. México.
GUEVARA, P., O. MORALES, J. FALCON, Clasificación Basada en Funciones para Planificadores de Tareas en Tiempo Real Concurrentes, XIV Congreso Latinoamericano de Control Automático y XIX Congreso de la Asociación Chilena de Control Automático, Santiago de Chile, Agosto de 2010.