PDF de programación - Programación Concurrente y Tiempo Real

Programación Concurrente y Tiempo Real

Tercera Edición

Programación
Concurrente y
Tiempo Real

Tercera Edición

David Vallejo Fernández
Carlos González Morcillo
Javier A. Albusac Jiménez

Programación Concurrente y Tiempo Real

Título:
Edición: 3ª Edición - Enero 2016
Autores: David Vallejo Fernández, Carlos González

ISBN:
Edita:

Morcillo y Javier A. Albusac Jiménez
978-1518608261
David Vallejo Fernández

Printed by CreateSpace, an Amazon.com company
Available from Amazon.com and other online stores

Este libro fue compuesto con LaTeX a partir de una plantilla de Carlos
González Morcillo y David Villa Alises.

Creative Commons License: Usted es libre de copiar, distribuir y comunicar públicamente la obra, bajo
las condiciones siguientes: 1. Reconocimiento. Debe reconocer los créditos de la obra de la manera
especificada por el autor o el licenciador. 2. No comercial. No puede utilizar esta obra para fines
comerciales. 3. Sin obras derivadas. No se puede alterar, transformar o generar una obra derivada a
partir de esta obra. Más información en: http://creativecommons.org/licenses/by-nc-nd/3.0/

Autores

David Vallejo (2009, Doctor Europeo en Informática,
Universidad de Castilla-La Mancha) es Profesor
Ayudante Doctor e imparte docencia en la Escuela de
Informática de Ciudad Real (UCLM) en asignaturas
relacionadas con Informática Gráfica, Programación y
Sistemas Operativos desde 2007. Actualmente, su
actividad investigadora gira en torno a la Vigilancia
Inteligente, los Sistemas Multi-Agente y el Rendering
Distribuido.

Carlos González
(2007, Doctor Europeo en
Informática, Universidad de Castilla-La Mancha) es
Profesor Titular de Universidad e imparte docencia en
la Escuela de Informática de Ciudad Real (UCLM) en
asignaturas relacionadas con
Informática Gráfica,
Síntesis de Imagen Realista y Sistemas Operativos
desde 2002. Actualmente, su actividad investigadora
gira en
los Sistemas Multi-Agente, el
Rendering Distribuido y la Realidad Aumentada.

torno a

Developer.

Ingeniero

David Villa (2009, Doctor
Informático,
Universidad de Castilla-La Mancha) es Profesor
Ayudante Doctor e imparte docencia en la Escuela de
Informática de Ciudad Real (UCLM) en materias
relacionadas con
las redes de computadores y
Javier Albusac (2009, Doctor Europeo en Informática,
sistemas distribuidos desde el 2002. Sus intereses
Universidad de Castilla-La Mancha) es Profesor
profesionales se centran en los sistemas empotrados
Ayudante Doctor e imparte docencia en la Escuela de
en red, los sistemas ubicuos y las redes heterogéneas
Ingeniería Minera e Industrial de Almadén (EIMIA) en
y virtuales. Es experto en métodos de desarrollo ágiles
las asignaturas de Informática, Ofimática Aplicada a la
y en los lenguajes C++ y Python. Colabora con el
Ingeniería y Sistemas de Comunicación en Edificios
proyecto Debian como maintainer de paquetes
desde 2007. Actualmente, su actividad investigadora
oficiales.
gira en torno a la Vigilancia Inteligente, Robótica Móvil
y Aprendizaje Automático.

2.3.4. El puente de un solo carril
. . . . . . . . . . . . . . . . . . . . .
2.3.5. El barbero dormilón . . . . . . . . . . . . . . . . . . . . . . . .
2.3.6. Los caníbales comensales
. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
2.3.7. El problema de Santa Claus

3. Paso de Mensajes

3.2.

3.1. Conceptos Básicos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. El concepto de buzón o cola de mensajes
. . . . . . . . . . . . .
3.1.2. Aspectos de diseño en sistemas de mensajes . . . . . . . . . . . .
3.1.3. El problema de la sección crítica . . . . . . . . . . . . . . . . . .
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. El problema del bloqueo . . . . . . . . . . . . . . . . . . . . . .
3.3. Problemas Clásicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1. El buffer limitado . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2. Los filósofos comensales . . . . . . . . . . . . . . . . . . . . . .
3.3.3. Los fumadores de cigarrillos . . . . . . . . . . . . . . . . . . . .
3.3.4. Simulación de un sistema de codificación . . . . . . . . . . . . .

61
63
66
68

73
73
75
75
78
79
85
87
88
88
90
92

4. Otros Mecanismos de Sincronización

95
96
. . . . . . . . . . . . . . . . . . . . . . . . .
4.1. Motivación . . . . . . . .
97
4.2. Concurrencia en Ada 95 . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. Tareas y sincronización básica . . . . . . . . . . . . . . . . . . .
98
4.2.2. Los objetos protegidos . . . . . . . . . . . . . . . . . . . . . . . 103
4.3. El concepto de monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.3.1. Monitores en POSIX . . . . . . . . . . . . . . . . . . . . . . . . 111
4.4. Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5. Planificación en Sistemas de Tiempo Real

Introducción . . . . . .

5.1.
5.2. El concepto de tiempo real

117
. . . . . . . . . . . . . . . . . . . . . . . . . . . 117
. . . . . . . . . . . . . . . . . . . . . . . . . 118
5.2.1. Mecanismos de representación . . . . . . . . . . . . . . . . . . . 119
5.2.2. Control de requisitos temporales . . . . . . . . . . . . . . . . . . 124
5.3. Esquemas de planificación . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.3.1. Modelo simple de tareas . . . . . . . . . . . . . . . . . . . . . . 128
5.3.2. El ejecutivo cíclico . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.3. Planificación basada en procesos . . . . . . . . . . . . . . . . . . 131

5.4. Aspectos relevantes de un planificador . . . . . . . . . . . . . . . . . . . 132
5.4.1. Sistema de asignación de prioridades
. . . . . . . . . . . . . . . 132
5.4.2. Modelo de análisis del tiempo de respuesta . . . . . . . . . . . . 133
5.4.3. Extendiendo el modelo simple de tareas . . . . . . . . . . . . . . 139
5.4.4. Consideraciones finales . . . . . . . . . . . . . . . . . . . . . . . 150

A. El puente de un solo carril

A.1. Enunciado . . . . . . . . .
A.2. Código fuente . . .

151
. . . . . . . . . . . . . . . . . . . . . . . . . 151
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

B. Filósofos comensales

B.1. Enunciado . . . . . . . .
B.2. Código fuente . . .

159
. . . . . . . . . . . . . . . . . . . . . . . . . . 159
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

C. La biblioteca de hilos de ICE

165
C.1. Fundamentos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
C.2. Manejo de hilos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
C.3. Exclusión mutua básica . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
C.3.1. Evitando interbloqueos . . . . . . . . . . . . . . . . . . . . . . . 172
C.3.2. Flexibilizando el concepto de mutex . . . . . . . . . . . . . . . . 174
. . . . . . . . . . . . . . . . . . . . . . . . . . 174
C.4.1. Ejemplo de uso de monitores . . . . . . . . . . . . . . . . . . . . 176

C.4. Introduciendo monitores

[2]

Capítulo 1 :: Conceptos Básicos

carga del ejecutable

en memoria

instr_1

instr_2

instr_3

…

instr_i

…

instr_n

programa

pila

memoria

datos

texto

proceso

Figura 1.1: Esquema gráfico de un programa y un proceso.

1.1. El concepto de proceso

Informalmente, un proceso se puede definir como un programa en ejecución. Ade-
más del propio código al que está vinculado, un proceso incluye el valor de un contador
de programa y el contenido de ciertos registros del procesador. Generalmente, un proce-
so también incluye la pila del proceso, utilizada para almacenar datos temporales, como
variables locales, direcciones de retorno y parámetros de funciones, y una sección de da-
tos con variables globales. Finalmente, un proceso también puede tener una sección de
memoria reservada de manera dinámica. La figura 1.1 muestra la estructura general de un
proceso.

1.1.1. Gestión básica de procesos

A medida que un proceso se ejecuta, éste va cambiando de un estado a otro. Cada
estado se define en base a la actividad desarrollada por un proceso en un instante de
tiempo determinado. Un proceso puede estar en uno de los siguientes estados (ver figura
1.2):

Nuevo, donde el proceso está siendo creado.

En ejecución, donde el proceso está ejecutando operaciones o instrucciones.

En espera, donde el proceso está a la espera de que se produzca un determinado
evento, típicamente la finalización de una operación de E/S.

Preparado, donde el proceso está a la espera de que le asignen alguna unidad de
procesamiento.

Terminado, donde el proceso ya ha finalizado su ejecución.

En UNIX, los procesos se identifican mediante un entero único denominado ID del
proceso. El proceso encargado de ejecutar la solicitud para crear un proceso se denomina
proceso padre, mientras que el nuevo proceso se denomina proceso hijo. Las primitivas
POSIX utilizadas para obtener dichos identificadores son las siguientes:

1.1. Concepto de Proceso

[3]

nuevo

admitido

interrupción

terminado

salida

preparado

en ejecución

terminación E/S

en espera

espera E/S

Figura 1.2: Diagrama general de los estados de un proceso.

Listado 1.1: Primitivas POSIX ID Proceso

1 #include <sys/types.h>
2 #include <unistd.h>
3
4 pid_t getpid (void); // ID proceso.
5 pid_t getppid (void); // ID proceso padre.
6
7 uid_t getuid (void); // ID usuario.
8 uid_t geteuid (void); // ID usuario efectivo.

Las primitivas getpid() y getppid() se utilizan para obtener los identificadores de un

proceso, ya sea el suyo propio o el de su padre.

Recuerde que UNIX asocia cada proceso con
un usuario en particular, comúnmente denominado
propietario del proceso. Al igual que ocurre con los
procesos, cada usuario tiene asociado un ID único
dentro del sistema, conocido como ID del us