Departamento de Ciencias de la Computación

UNIVERSIDAD DE ALCALÁ

La programación paralela es un paradigma de programación de computadores que permite explotar el paralelismo implícito de determinados algoritmos y conseguir, con ello, una mayor estructuración del software y una reducción de su tiempo de ejecución en sistemas informáticos con múltiples procesadores. En este libro se presentan los fundamentos de esta forma de desarrollar programas, así como los constructores necesarios en los lenguajes de programación para poder llevarla a cabo.

Se dedica un primer capítulo al estudio de los conceptos básicos sobre paralelismo y su implementación en los computadores. También se analizan dos posibles formas de desarrollar programas paralelos: utilizando un lenguaje de programación paralela, o utilizando un lenguaje de programación secuencial que acceda a las facilidades de multiproceso que ofrecen los sistemas operativos.

Los cinco capítulos siguientes tratan sobre las herramientas características de los dos tipos de programación paralela que habitualmente se consideran, según se asuma que el sistema informático sobre el que se ejecutarán los programas dispone de memoria compartida o de memoria distribuida. Aunque no existe una unificación terminológica en este campo, en el libro, como hacen otros autores, se adoptará el término programación concurrente para el primer tipo de programación paralela, y programación distribuida para el segundo.

  Los capítulos 2, 3, 4 y 5 se dedican a la programación concurrente; en el primero se estudian sus fundamentos, y en los tres siguientes los constructores más utilizados: los semáforos, las regiones críticas y los monitores. En el capítulo 6, dedicado a la programación distribuida, se consideran dos formas de desarrollar programas distribuidos: mediante el intercambio explícito de mensajes o mediante llamadas a procedimientos remotos.

En el último capítulo se analizan brevemente algunos lenguajes reales de programación paralela, comenzando con los que permiten realizar programas concurrentes, y continuando con los lenguajes de programación distribuida.

El libro incluye más de cuarenta ejercicios resueltos que pueden ayudar a asimilar los conceptos tratados en cada uno del los capítulos.

Finalmente, se han incorporado dos anexos y un apartado de referencias bilbiográficas. En el primer anexo se realiza un resumen del lenguaje de programación utilizado en los diferentes ejemplos prácticos que aparecen en el texto, se trata de una versión paralela del lenguaje Pascal. En el segundo anexo se muestra la posibilidad de realizar programación distribuida en Internet utilizando un mecanismo denominado socket. La bibliografía que se presenta al final puede servir de referencia para ampliar los conocimientos sobre los diferentes temas tratados.

1.1 CONCEPTOS BÁSICOS SOBRE PARALELISMO 5

1.2 COMUNICACIÓN Y SINCRONIZACIÓN 8

1.3 TIPOS DE PROGRAMACIÓN PARALELA 9

1.4 PROGRAMACIÓN PARALELA Y SISTEMAS OPERATIVOS 10

1.5 PROGRAMACIÓN PARALELA

Y PROGRAMACIÓN EN TIEMPO REAL 11

1.6 TÉCNICAS DE REPRESENTACIÓN DEL PARALELISMO 13

1.6.1 Lenguaje de programación paralela 13

1.6.2 Diagrama de precedencia 15

1.7 IMPLEMENTACIÓN DEL PARALELISMO

EN LOS COMPUTADORES 16

1.7.1 Niveles de paralelismo en un computador 16

1.7.2 Arquitectura de Computadores Paralelos 17

1.8 EJERCICIOS PROPUESTOS 19

1.9 SOLUCIÓN DE LOS EJERCICIOS PROPUESTOS 21

2.1 EL CONCEPTO DE MEMORIA COMPARTIDA 23

2.2 EL PROBLEMA DE LA EXCLUSIÓN MÚTUA 25

2.3 TÉCNICAS PARA ASEGURAR LA EXCLUSIÓN MÚTUA 29

2.3.1 Algoritmo de Dekker 30

2.3.2 Algoritmo de Dijkstra 34

2.3.3 Constructores de lenguajes de programación 34

2.4 EJERCICIOS PROPUESTOS 35

2.5 SOLUCIÓN DE LOS EJERCICIOS PROPUESTOS 36

3.1 CONCEPTO DE SEMÁFORO 43

3.2 OPERACIONES CON SEMÁFOROS 45

3.3 SINCRONIZACIÓN Y COMUNICACIÓN CON SEMÁFOROS 46

3.3.1 Sincronización controlada por semáforos binarios 46

3.3.2 Comunicación sincronizada con semáforos binarios 49

3.3.3 Comunicación sincronizada con semáforos con contador 53

3.4 EL PROBLEMA DEL INTERBLOQUEO (DEADLOCK) 55

3.5 SEMÁFOROS Y PROGRAMACIÓN EN TIEMPO REAL 56

3.6 EJERCICIOS PROPUESTOS 57

3.7 SOLUCIÓN DE LOS EJERCICIOS PROPUESTOS 64

4.1 CONCEPTO DE REGIÓN CRÍTICA 73

4.2 EQUIVALENCIA REGIÓN CRÍTICA - SEMÁFORO 77

4.3 REGIONES CRÍTICAS CONDICIONALES 77

4.4 EL PROBLEMA DEL INTERBLOQUEO 80

4.5 EJERCICIOS PROPUESTOS 81

4.6 SOLUCIÓN DE LOS EJERCICIOS PROPUESTOS 83

5.1 CONCEPTO DE MONITOR 91

5.2 EXCLUSIÓN MÚTUA Y SINCRONIZACIÓN 96

5.3 EMULACIÓN DE SEMÁFOROS 100

5.4 EL PROBLEMA DEL INTERBLOQUEO 101

5.5 EJERCICIOS PROPUESTOS 102

5.6 SOLUCIÓN DE LOS EJERCICIOS PROPUESTOS 109

6.1 EL CONCEPTO DE INTERCAMBIO DE MENSAJES 123

6.2 TIPOS DE PROCESOS EN PROGRAMACIÓN DISTRIBUIDA 126

6.3 EL CONCEPTO DE ESPERA SELECTIVA 127

6.4 COMUNICACIÓN ASÍNCRONA MEDIANTE BUZONES 128

6.5 COMUNICACIÓN SÍNCRONA MEDIANTE RENDEZ-VOUS 134

6.5.1 Intercambio explícito de mensajes 135

6.5.2 Llamadas a procedimientos remotos 140

6.6 PROGRAMCIÓN DISTRIBUIDA Y PROG. EN TIEMPO REAL 148

6.7 EJERCICIOS PROPUESTOS 150

6.8 SOLUCIÓN DE LOS EJERCICIOS PROPUESTOS 158

7.1 LENGUAJES DE PROGRAMACIÓN CONCURRENTE 177

7.1.1 Concurrent Pascal 178

7.1.2 Modula-2 181

7.1.3 Parallel Fortran 193

7.1.4 Java 198

7.2 LENGUAJES DE PROGRAMACIÓN DISTRIBUIDA 201

7.2.1 CSP 202

7.2.2 Occam 204

7.2.3 Ada 206

7.2.4 Concurrent C/C++ 210