PDF de programación - Kernel de tiempo real basado en Linux para una PDA

Centro de Investigación y de Estudios

Avanzados

del Instituto Politécnico Nacional

Departamento de Ingeniería Eléctrica

Sección Computación

Kernel de tiempo real basado en Linux para

una PDA.

Tesis que presenta

Francisco Javier Zuluaga Ramírez

para obtener el Grado de

Maestro en Ciencias

en la Especialidad de

Ingeniería Eléctrica

Director de la Tesis
Dr. Predro Mejía Álvarez

México, D.F.

2005

ii

Resumen

Durante los últimos cinco años la cantidad de dispositivos móviles exis-
tentes en el mercado ha crecido bastante, lo que ha generado la necesidad
de desarrollar un mayor número aplicaciones para este tipo de dispositivos.
Algunas de estas aplicaciones requieren cumplir con ciertas restricciones de
tiempo. Como por ejemplo, la comunicación de datos entre dispositivos o el
procesamiento de contenido multimedia, lo cual implica que el sistema ope-
rativo con el que se cuente en el dispositivo móvil ofrezca soporte a procesos
de tiempo real.

Linux es un sistema operativo de código abierto muy popular, lo que per-
mite un estudio minucioso de su arquitectura y no nos impone restricción
alguna para la modificación de su kernel.

Esta tesis presenta el diseño e implementación de un kernel basado en
Linux para una PDA (Personal Digital Assistant) que ofrece soporte para
procesos de tiempo real, permitiendo el manejo de tareas periódicas y ape-
riódicas. Nuestro kernel incluye políticas de planificación especiales, tales
como, Rate Monotonic (RM) y Earliest Deadline First (EDF), así como di-
ferentes mecanismos de comunicación y sincronización entre procesos, como
semáforos y paso de mensajes mediante buzones.

iii

iv

Abstract

During the last years the amount of mobile devices available at the
market-place has increased. It has generated the necessity of developing more
applications for this kind of devices. Some of these applications have some
timing restrictions, for example, the data transference between devices or the
processing of multimedia content; therefore the operating system implemen-
ted in the mobile device must offer support for real time processes.

Linux is a very popular open source operating system, that allows to
study in detail its architecture, and does not impose any restriction on ma-
king modifications to the kernel.

This thesis presents the design and implementation of a kernel based on
Linux for a PDA (Personal Digital Assistant), which has a support for real
time processes, allowing the existence of periodic and non periodic tasks. The
kernel includes scheduling policies of specific purpose, such as Rate Monoto-
nic (RM) and Earliest Deadline (EDF), as well as mechanisms for communi-
cation and synchronization between processes, like semaphores and messages
passing across mailboxes.

v

vi

Agradecimientos

Le agradezco a Dios por la vida, y por todo lo que de ella tengo.

Quiero dar las gracias a todas las personas e instituciones que de una u

otra forma estuvieron involucradas en este trabajo.

El doctor Pedro Mejía Álvarez con sus consejos, regaños y paciencia du-
rante el tiempo que he trabajado con él, hizó posible la culminación de esta
tesis.

De manera especial agradezco a los doctores Adriano de Luca y Jorge

Buenabad por los comentarios hechos para la mejora de mi trabajo.

A los doctores Sergio Chapa, Francisco Rodríguez, Guillermo Morales,
Arturo Díaz, Gerardo de la Fraga, profesores de la Sección de Computación,
y al compañero Amilcar Viveros por haber compartido sus conocimientos
conmigo y ser parte de mi formación académica.

Siento un gran placer poder agracer a mis compañeros de la Sección de
Computación por su amistad y el tiempo compartido, especialmente a Abi-
gail, Claudia, Grettel, Luis, Mario I. Florentino, Mónica, Rocio, Rosario y
Ulises.

A Juan Manuel y Omar por las charlas y consejos, que tan útiles me fue-

ron al desarrollar mi tesis.

Edith, Gary e Israel, además de ser tres excelentes personas y amigos
mios, su punto de vista fue muy valioso al momento de redactar este docu-
mento.

vii

viii

Quiero agradecer y hacer un reconocimiento a las personas cuyo trabajo
me sirvió como base o como guia. A Douglas Comer por Xinu, a Jorge Bue-
nabad por Xinix, a Paolo Mantegazza y su equipo de trabajo por RTAI y a
Linus Torvalds por Linux.

Debo destacar que el apoyo económico del CONACyT y del CINVESTAV
fueron muy importantes e indispensables para que yo pudiera realizar mis es-
tudios de maestria.

A los seres más importantes en mi vida,

mi mamá Ma. del Carmen,

mi papá Francisco,

y mis hermanos Adrián, Nadia y Liseth.

ix

x

Índice general

Índice de figuras

Índice de tablas

1. Introducción

1.3.
1.4. Organización de la tesis

XIII

XVII

1.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Trabajos relacionados
. . . . . . . . . . . . . . . . . . . . . .
Sistemas operativos de tiempo real comerciales . . . .
1.2.1.
1.2.2. Sistemas operativos de tiempo real de desarrollo
. . .
Implantación del kernel de tiempo real en la PDA . . . . . . .

1
2
3
3
5
8
. . . . . . . . . . . . . . . . . . . . . 11

2. Tiempo real

2.1. Definición de sistema de tiempo real
2.2. Elementos de un sistema de tiempo real
2.3. Características de los sistemas de tiempo real
2.4. Clasificación de los sistemas de tiempo real

13
. . . . . . . . . . . . . . 13
. . . . . . . . . . . . 14
. . . . . . . . . 16
. . . . . . . . . . 17
2.4.1. Sistemas de tiempo real críticos (hard real time systems ) 17
2.4.2. Sistemas de tiempo real acríticos (soft real time systems

) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5. ¿Qué es un sistema operativo de tiempo real? . . . . . . . . . 18
2.6. Proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6.1. Definición de proceso . . . . . . . . . . . . . . . . . . . 19
2.6.2. Definición de quantum . . . . . . . . . . . . . . . . . . 19
2.6.3. Parámetros de un proceso de tiempo real . . . . . . . . 19
2.6.4. Estado del proceso . . . . . . . . . . . . . . . . . . . . 20
2.6.5. Transiciones entre estados . . . . . . . . . . . . . . . . 21
2.6.6. PCB (Process Control Block)
. . . . . . . . . . . . . . 22

xi

xii

ÍNDICE GENERAL

2.7. Elementos de un sistema operativo de tiempo real

. . . . . . . 23
2.7.1. Manejador de procesos . . . . . . . . . . . . . . . . . . 23
2.7.2. Manejador de memoria . . . . . . . . . . . . . . . . . . 25
2.7.3. Manejador de reloj
. . . . . . . . . . . . . . . . . . . . 25
2.7.4. Mecanismos de sincronización y comunicación . . . . . 26
2.7.5. Manejador de entradas/salidas . . . . . . . . . . . . . . 30
. . . . . . . . . . . . 30
2.8. Planificación en sistemas de tiempo real
2.9. Tareas de tiempo real . . . . . . . . . . . . . . . . . . . . . . . 30
2.9.1. Clasificación de las tareas de tiempo real
. . . . . . . . 31
2.9.2. Tipos de restricciones de las tareas de tiempo real . . . 33
2.10. Definición del problema de planificación . . . . . . . . . . . . . 35
2.11. Clasificación de políticas de planificación
. . . . . . . . . . . 35
2.12. Planificador cíclico . . . . . . . . . . . . . . . . . . . . . . . . 36
2.13. Planificadores basados en prioridades

estáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.13.1. Rate Monotonic (RM)
. . . . . . . . . . . . . . . . . . 38
2.13.2. Deadline Monotonic (DM) . . . . . . . . . . . . . . . . 41

2.14. Planificadores basados en prioridades

dinámicas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.14.1. Earliest Deadline First (EDF) . . . . . . . . . . . . . . 42
2.14.2. Least Laxity First (LLF) . . . . . . . . . . . . . . . . . 43

3. Kernel de tiempo real en la PDA

47
3.1. RTAI en la PDA . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.
Interrupciones en el procesador PXA250 . . . . . . . . . . . . 49
3.3. Procesamiento de interrupciones en Linux . . . . . . . . . . . 51
3.3.1. Manejadores de excepción . . . . . . . . . . . . . . . . 51
3.3.2. Manejadores de interrupción . . . . . . . . . . . . . . . 51
3.4. Capa de abstracción de hardware . . . . . . . . . . . . . . . . 53
3.5. Cambios realizados en el kernel de Linux . . . . . . . . . . . . 54
. . . . . . . . . . . . . . . . . . . . 54

3.5.1. La estructura rthal
3.5.2. Funciones para habilitar y deshabilitar

interrupciones

. . . . . . . . . . . . . . . . . . . . . . 55
3.5.3. Cambios en el manejo de excepciones . . . . . . . . . . 55
3.5.4. Cambios en el manejo de interrupciones
. . . . . . . . 55

ÍNDICE GENERAL

xiii

4. Diseño del kernel de tiempo real

59
. . . . . . . . . . . . . . . . . . . . . . . 60
4.1. Arquitectura general
. . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2. Procesos (tareas)
. . . . . . . . . . . . . . 61
4.3. Bloque de control del proceso (BCP)
. . . . . . . . . . . . . . . 62
4.4. Estados de los procesos en el kernel
4.5. Transiciones entre estados
. . . . . . . . . . . . . . . . . . . . 63
4.6. Manejadores del kernel y llamadas al sistema . . . . . . . . . 64
4.6.1. Manejador de colas . . . . . . . . . . . . . . . . . . . . 64
4.6.2. Manejador de procesos . . . . . . . . . . . . . . . . . . 67
4.6.3. Manejador de semáforos
. . . . . . . . . . . . . . . . . 72
. . . . . . . . . . . . . . . . . . 75
4.6.4. Manejador de buzones
4.6.5. Manejo del procesador . . . . . . . . . . . . . . . . . . 77
4.6.6. Manejo de errores . . . . . . . . . . . . . . . . . . . . . 82
4.7. Configuración e inicialización del kernel . . . . . . . . . . . . . 83
. . . . . . . . . . . . . . . . . 83
Inicialización del kernel . . . . . . . . . . . . . . . . . . 84

4.7.1. Configuración del kernel
4.7.2.

5. Resultados

85
5.1. Entorno de pruebas . . . . . . . . . . . . . . . . . . . . . . . . 85
. 85
5.1.1. Compilación del kernel de Linux con soporte a RTAI
5.1.2. Compilación e instalación de RTAI
. . . . . . . . . . . 87
5.1.3. Compilación del kernel de tiempo real . . . . . . . . . . 87
. . . . . . . . . . . . . . . .