Programación concurrente: ejemplos de clase

Figura 1. Paradigmas de programación concurrente y distribuido

1. Concurrencia compartida imperativa (Phtreads)

La concurrencia de estado compartido, concurrencia de recursos compartidos, o simplemente concurrencia compartida ocurre cuando varios trabajadores (hilos de ejecución) realizan una tarea concurrentemente y pueden acceder a regiones compartidas de memoria porque están dentro del mismo espacio de direcciones de memoria del proceso.

Los hilos de ejecución siguen este esquema, dado que comparten todos los segmentos del proceso (código, datos, y memoria dinámica), excepto el segmento de pila. Por ejemplo, un dato que un hilo escriba en la memoria compartida, otro hilo puede leerlo inmediatamente, sin hacer ninguna preparación especial. De esta forma, la memoria compartida se convierte en un mecanismo directo de comunicación entre los hilos de ejecución.

Se estudiarán en el curso tres tecnologías para implementar concurrencia compartida: Pthreads, OpenMP, y OpenACC. Éste último es de carácter opcional.

Los POSIX Threads es un estándar que permite a los desarrolladores crear y controlar hilos de ejecución en los sistemas operativos basados en Unix. Cree en una carpeta ejemplos/pthreads para los siguientes ejemplos en su repositorio personal de control de versiones para el curso. Para cada ejemplo cree una subcarpeta que utilice el nombre dado entre corchetes.

1.1. Hola mundo (thread)

Actividad 1 [hello]

Escriba un programa que al correr cree dos hilos, el principal y uno secundario. Ambos hilos deben saludar en la salida estándar con el mensaje "Hello from main thread" y "Hello from secondary thread" respectivamente. Utilice un analizador dinámico de código como las herramientas memcheck y helgrind de Valgrind, o los Google Sanitizers, para asegurarse de que su programa no provoca condiciones de carrera.

En la siguiente solución se incluye además un archivo de reglas Makefile que permite a un desarrollador compilar el código fuente sin tener que recordar los argumentos con los que se debe invocar al compilador. Bastará que el programador emita el comando make en la carpeta, y éste invocará al compilador siguiendo la primera regla estipulada en el Makefile.

Table 1. Hola mundo en Pthreads [hello]
Archivo	Descripción	Cambios
hello.c	Dice "hola mundo" desde el hilo principal y desde un hilo secundario.
Makefile	Un archivo para compilar el código fuente sin tener que recordar los argumentos de invocación al compilador. También permite correr pruebas durante el desarrollo como quitar pelusas (linting), revisar accesos inválidos y fugas de memoria (`memcheck`), y revisar condiciones de carrera (`helgrind`).

Para instalar el compilador (GCC), el analizador estático de código (cpplint), el analizador dinámico de código (valgrind), y el compilador Clang que instrumenta código con sanitizers, puede instalar los siguientes paquetes en un Linux basado en Debian:

sudo apt update
sudo apt install build-essential python3-pip valgrind clang
sudo pip3 install cpplint

Para compilar con GCC –o un compilador compatible– código fuente que use Pthreads, se necesita el parámetro -pthread:

cc -g -Wall -Wextra hello.c -o hello -pthread

echo hello > .gitignore
git add hello.c .gitignore

Recuerde siempre ignorar los ejecutables en su repositorio de control de versiones. Para ello, cree o agregue a su archivo .gitignore el nombre del ejecutable. Luego agregue el código fuente y el .gitignore a control de versiones. Los dos últimos comandos de arriba hacen este trabajo. La Resultado de rastrear la memoria del programa hello muestra el resultado final de rastrear la memoria durante la ejecución del código.

Figura 2. Resultado de rastrear la memoria del programa hello

1.2. Hola mundo múltiple (indeterminismo)

Actividad 2 [hello_w]

Modifique el programa de "hola mundo" para crear una cantidad arbitraria de threads. Cada uno de los cuales imprime "Hello from thread %d\n" en la salida estándar y termina su ejecución. Permita al usuario indicar la cantidad de threads como argumento de la línea de comandos. Si este argumento se omite, asuma la cantidad de CPUs disponibles en el sistema.

Table 2. Hola mundo múltiple en Pthreads [hello_w]
Archivo	Descripción	Cambios
hello_w.c	Varios threads dicen "hola mundo" junto con el hilo principal.
Makefile	Utiliza una variable para facilitar la reutilización del `Makefile` en futuros ejemplos.

1.3. Hola mundo numerado (memoria privada)

Actividad 3 [hello_iw_pri]

Cree una nueva versión de su programa "hola mundo" donde cada thread imprime "Hello from thread i of w\n", donde i es el número de thread y w la cantidad total de hilos creada. Está prohibido usar variables en el segmento de datos (globales, estáticas, externas). Sugerencia: cree un registro (estructura) privado para cada thread.

Table 3. Hola mundo numerado [hello_iw_pri]
Archivo	Descripción	Cambios
hello_iw_pri.c	Varios threads saludan indicando su identificador en la salida estándar. Esta versión usa una variable global para el mutex que no es necesario dado que la entrada y salida con formato de C internamente usa exclusión mutua. Se dejó como variable global sólo para silenciar el diagnóstico falso positivo que reporta Helgrind. En el siguiente ejemplo se corrige este problema.
Makefile	El Makefile cambia la variable para especificar el nombre del ejecutable y del archivo fuente que facilita modificaciones.

Actividad 4 [hello_count]

Utilizando los argumentos en línea de comandos, ubique la cantidad máxima de threads que su sistema operativo le permite crear. Escriba el número obtenido en un archivo count.md en su carpeta ejemplos/pthreads/hello_iw_pri, junto con el nombre de su sistema operativo (por ejemplo, Debian 9 64bits o Fedora 30 64bits).

1.4. Hola mundo numerado (memoria compartida)

Actividad 5 [hello_iw_shr]

Cree una nueva versión de su programa "hola mundo numerado" donde cada thread imprime "Hello from thread i of w\n", donde i es el número de thread y w la cantidad total de hilos creada con los siguientes cambios:

Haga que los datos comunes para todos los threads (el número w) estén en un registro (estructura) compartido para cada thread. Mantenga los datos exclusivos para cada thread (i) se mantengan en el registro privado.
Reporte la duración en segundos que los threads toman en saludar.

Table 4. Hola mundo numerado [hello_iw_shr]
Archivo	Descripción	Cambios
hello_iw_shr.c	Varios threads saludan indicando su identificador en la salida estándar.
Makefile	Cambia el nombre de la carpeta usando la variable.

El código en este ejemplo es de suma importancia, porque es el código base para crear programas concurrentes con Pthreads. Este código permite a los hilos tanto compartir memoria como tener su propia memoria privada de trabajo sin incurrir en malas prácticas como el uso de variables globales.

1.5. Hola mundo ordenado (espera activa)

Actividad 6 [hello_order_busywait]

Haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden

Hello from thread 0 of w
Hello from thread 1 of w
Hello from thread 2 of w
...
Hello from thread w of w

Utilice espera activa como mecanismo de sincronización (control de concurrencia).

La espera activa (busy waiting) es un ciclo que hace a un hilo de ejecución esperar repetitivamente hasta que una condición se haga falsa. Por ejemplo, si la variable next_thread indica el número del próximo thread que puede realizar una tarea que debe ser serializada en orden, el código

// Wait until it is my turn
while ( next_thread < my_thread_id )
	; // busy-wait

// Do the ordered-task here
task();

// Allow subsequent thread to do the task
++next_thread;

Table 5. Hola mundo ordenado con espera activa [hello_order_busywait]
Archivo	Descripción	Cambios
hello_order_busywait.c	Varios threads saludan en orden gracias a la espera activa.
Makefile	Obtiene automáticamente el nombre del ejecutable de la carpeta donde se encuentre el `Makefile`. Asume que existe un archivo `.c` con el mismo nombre de la carpeta. Se agregó la regla `gitignore` que crea el archivo `.gitignore` con el nombre del ejecutable.

Actividad 7 [hello_order_rationale]

Ejecute varias veces su solución de hello_order_busywait con la cantidad máxima de threads que el su sistema operativo le permite. ¿Puede estimar la duración de su solución con espera activa? Describa el comportamiento del programa y explique la razón de este comportamiento en un archivo rationale.md dentro de su carpeta hello_order_busywait. Indique en qué condiciones sería apremiante utilizar espera activa, o en caso de no haberlas, sugiera soluciones alternativas.

1.6. Posición en la carrera (mutex)

Actividad 8 [position_race]

Modifique su solución a Actividad 6 [hello_order_busywait] para implementar una carrera de threads. Cada vez que un thread llega a la meta, lo avisa en la salida estándar, como ocurre en la siguiente corrida hipotética:

Thread 0/4: I arrived at position 1
Thread 2/4: I arrived at position 2
Thread 1/4: I arrived at position 3
Thread 3/4: I arrived at position 4

Note que las posiciones tienen que aparecer en orden, no el número de cada thread. Utilice algún mecanismo de control de concurrencia para que el reporte sea correcto.

Table 6. Posición en la carrera [position_race]
Archivo	Descripción	Cambios
position_race.c	Varios threads compiten en una carrera, y reportan el orden en que llegan a la meta. Utilizan exclusión mutua cuando llegan a la meta para incrementar la variable contadora correctamente y para evitar la condición de carrera en la impresión en la salida estándar.
Makefile	Sin cambios respecto a la versión anterior

1.7. Hola mundo ordenado (semáforos)

Actividad 9 [hello_order_semaphor]

Haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden

Hello from thread 0 of w
Hello from thread 1 of w
Hello from thread 2 of w
...
Hello from thread w of w

Utilice una colección de semáforos como mecanismo de sincronización (control de concurrencia).

Table 7. Hola mundo ordenado (semáforos) [hello_order_semaphor]
Archivo	Descripción	Cambios
hello_order_semaphor.c	Utiliza una colección de semáforos, uno para cada hilo de ejecución. Sólo el semáforo para el hilo 0 está en verde. Cuando un hilo pasa su semáforo, saluda en la salida estándar y enciende el semáforo del siguiente. De esta forma, las impresiones se hacen en orden.
Makefile	Agrega variables para el compilador de C (`CC`), las banderas de compilación (`CFLAGS`), y del linker (`LIBS`). Estas variables pueden ser cambiadas desde la línea de comandos cuando se invoca a `make` de la forma `make VAR=value`.

1.8. Hola mundo ordenado (seguridad condicional)

Actividad 10 [hello_order_cond_safe]

Haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden

Hello from thread 0 of w
Hello from thread 1 of w
Hello from thread 2 of w
...
Hello from thread w of w

Evite (si es posible) el control de concurrencia, es decir, trate de usar seguridad condicional (conditionally safe).

Table 8. Hola mundo ordenado (seguridad condicional) [hello_order_cond_safe]
Archivo	Descripción	Cambios
hello_order_cond_safe.c	Imprime en orden sin usar mecanismos de control de concurrencia. Usa una estructura de datos (un arreglo) donde cada hilo de ejecución escribe sus resultados sin afectar a los demás.
Makefile	Sin cambios.

2. Concurrencia de tareas

Los dos tipos de problemas que resuelve el paradigma de programación concurrente son los que requieren incremento de desempeño y separación de asuntos.

El incremento del desempeño se busca principalmente al optimizar algorimos que requieren mucho poder de cómputo o procesar grandes volúmenes de datos. Son de especial interés para otras disciplinas que requieren apoyo de la computación. Se busca principalmente maximizar el paralelismo de datos a través de entes de ejecución (hilos o procesos) y disminuir la cantidad de comunicación entre los entes.
La separación de asuntos o concurrencia de tareas no busca tanto la optimización, sino que los entes realicen tareas distintas de forma correcta. Los problemas en esta categoría son de especial interés para la computación misma, dado que son aplicables a variedad de herramientas como sistemas operativos, motores de bases de datos, servidores web, entre otros. Típicamente los problemas en esta categoría buscan que el paralelismo de tareas genere resultados correctos a través de la aplicación de mecanismos de sincronización.

Esta sección se concentra en problemas del segundo tipo de la lista anterior, muchos de los cuales tienen aspecto de acertijos y resultan muy interesantes para el profesional de la computación. Están basados en el libro libre The Little Book of Semaphores escrito por Allen B. Downey.

2.1. Primitivas

2.1.1. Algoritmos (pseudocódigo)

Notación simplificada de pseudocódigo para expresar la parte concurrente de las soluciones.

// Declares a shared variable by all threads (ie. stored in shared_data record)
shared shared_x := initial_value

// Main subroutine that will be executed by the main thread
main:
	// Create 3 threads that will execute the secondary function concurrently
	// If the number of threads is omitted, 1 thread is created
	// Optional remaning args are passed to the secondary subroutiny
	create_thread(3, secondary, args)
	// Threads are implicitly joined after main() finishes

secondary(args):
	// A subroutine that will be executed by secondary threads

Actividad 11 [execution_paths]

Dos threads ejecutan las siguientes tareas. Liste todas las rutas de ejecución indicando el valor final de la variable x y la salida estándar. Una ruta de ejecución (execution path) es una combinación de instrucciones que depende del orden en que sean ejecutadas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11 main:
	shared x := 0
	create_thread(thread_a)
	create_thread(thread_b)

thread_a:
	x := 5
	print(x)

thread_b:
	x := 7

Table 9. Rutas de ejecución [execution_paths]
Archivo	Descripción	Cambios
execution_paths.md	Lista todas las posibles rutas de ejecución.
execution_paths.pnml	Red de petri que representa el mismo programa que el pseudocódigo dado. Fue elaborado con la aplicación WoPeD.

2.1.2. Redes de Petri

Figura 3. Red de petri que representa las rutas de ejecución

Actividad 12 [for_count]

Suponga que el hilo de ejecución principal crea w=100 hilos secundarios con los siguientes códigos. (1) ¿Cuál es el valor más grande que la variable compartida count podría llegar a obtener? (2) ¿Cuál es el menor valor que la variable compartida count podría llegar a obtener?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10 shared count := 0

main:
	// create 100 threads running secondary()
	create_thread(100, secondary)

secondary:
	for i := 1 to 100:
		temp := count
		count := temp + 1

Table 10. Contador en ciclos [for_count]
Archivo	Descripción	Cambios
for_count.md	Conjetura los potenciales resultados.

2.1.3. Semáforos

La definición original de semáforo por Dijkstra puede variar ligeramente de algunas implementaciones. Para Dijkstra un semáforo es un entero con signo, con tres características:

Cuando se crea un semáforo, éste se inicializa con un entero cualquiera (negativo, cero, o positivo). Pero después de inicializado las únicas dos operaciones que están permitidas es incrementar en uno (signal) y decrementar en uno (wait) al semáforo. No se puede leer el valor actual del semáforo.
Cuando un hilo decrementa un semáforo, si el resultado es negativo, el hilo es bloqueado y no puede continuar hasta que otro hilo incremente el semáforo.
Cuando un hilo incrementa un semáforo, si hay otros threads esperando, uno de ellos será desbloqueado. Tanto el hilo que incrementa el semáforo como el que fue desbloqueado siguen ejecutándose concurrentemente. Si hay varios hilos esperando, no hay forma de saber cuál de ellos será el desbloqueado por el scheduler del sistema operativo. El programador no tiene forma de saber si al incrementar un semáforo, se desbloqueará o no un hilo en espera, dado que no se puede leer el valor actual del semáforo por la regla 1.

El valor actual de un semáforo indica lo siguiente. Si el valor es positivo indica la cantidad de hilos que pueden decrementar el semáforo sin bloquearse. Si es negativo indica la cantidad de hilos que están bloqueados esperando actualmente por el semáforo. Si el valor es cero, indica que no hay hilos esperando por el semáforo, pero si un thread trata de decrementarlo, será bloqueado.

Algunas implementaciones, por ejemplo POSIX, permiten probar la espera (sem_trywait). Esta función nunca bloquea al hilo que la invoca. Si se trata de esperar un semáforo que tiene un valor positivo, se decrementará el semáforo y el hilo continuará ejecutándose como una invocación normal a wait(). Pero si se trata de esperar por un semáforo que quedaría en un valor negativo, la función sem_trywait() no decrementa al semáforo ni bloquea al hilo, sino que retorna de inmediato indicando un código de error (por ejemplo, -1). Dado que el hilo mantiene su ejecución, el programador puede decidir, condicionando (if) el valor de retorno del sem_trywait() y tomar distintas acciones que realice el hilo cuando se pudo o no esperar por el semáforo.

En los siguientes ejemplos se seguirá la definición original de Dijkstra, que no permite probar la espera. Se usará pseudocódigo con la siguiente sintaxis para los hilos y semáforos, con el fin de centrar la atención en estos temas y no en detalles de implementación de una tecnología particular (ej.: Pthreads):

sem := semaphore(3) // Create a semaphore with initial value 3
signal(sem)         // Increment and wake a waiting thread if any
wait(sem)           // Decrement and block if the result is negative

2.2. Patrones básicos

2.2.1. Avisar/notificar (signal)

Actividad 13 [signaling]

Modifique los códigos de los hilos para que la instrucción a1 se ejecute siempre antes que la instrucción b1. Esto es, que un hilo envíe una señal (aviso) a otro (signaling).

1
2
3
4
5
6
7
8
9 main:
	create_thread(1, thread_a)
	create_thread(thread_b)

thread_a:
	statement a1

thread_b:
	statement b1

Table 11. Avisar/notificar [signaling]
Archivo	Descripción	Cambios
signaling.alg.c	Usa un semáforo que indica cuando la instrucción `a1` ha sido ejecutada.
signaling_3.alg.c	Serializa tres hilos usando dos semáforos. El primer hilo avisa/notifica al segundo, y éste al tercero.
signaling_w.alg.c	Generaliza la solución para serializar w hilos de ejecución con w - 1 semáforos. El hilo i notifica al siguiente y el último notifica al primero. Este pseudocódigo representa en pocas líneas la solución hecha al problema Actividad 9 [hello_order_semaphor].

2.2.2. Encuentro (rendezvous)

Actividad 14 [rendezvous]

Modifique los códigos de los hilos para que la instrucción a1 y b1 se ejecuten siempre antes que las instrucciones a2 y b2. Este problema tiene el nombre francés rendezvous que significa encuentro en un punto de ejecución, y ninguno de los dos hilos pueden continuar su ejecución hasta que el otro haya llegado.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11 main:
	create_thread(thread_a)
	create_thread(thread_b)

thread_a:
	statement a1
	statement a2

thread_b:
	statement b1
	statement b2

Table 12. Encuentro [rendezvous]
Archivo	Descripción	Cambios
rendezvous1a.alg.c rendezvous1b.alg.c	Usa dos semáforos para asegurar que dos threads han llegado a cierto punto. En esta solución, los dos threads avisan apenas hayan terminado de ejecutar las instrucciones `a1` o `b1`. Hay dos variantes equivalentes de esta solución que se diferencian en el significado de los semáforos, no en su efecto: a) Las instrucciones `a1` y `b1` ya fueron ejecutadas. b) El hilo `a` y el hilo `b` pueden continuar su ejecución.
rendezvous2a.alg.c rendezvous2b.alg.c	En esta versión un thread primero espera y el otro avisa. Es una solución correcta aunque ligeramente menos eficiente que la versión 1. Hay dos variantes equivalentes: a) El hilo `a` primero avisa y luego espera y el hilo `b` primero espera y luego avisa. b) El hilo `a` primero espera y luego avisa y el hilo `b` primero avisa y luego espera.
rendezvous3.alg.c	En esta versión ambos threads esperan a que el otro haya terminado de ejecutar su instrucción. No es una solución al problema porque genera un bloqueo mutuo (deadlock).

2.2.3. Exclusión mutua con semáforos (mutex)

Actividad 15 [sem_mutex]

Agregue semáforos al pseudocódigo siguiente para forzar a que los incrementos en los hilos se hagan con exclusión mutua.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11 shared count := 0

main:
	create_thread(thread_a)
	create_thread(thread_b)

thread_a:
	count := count + 1

thread_b:
	count := count + 1

Actividad 16 [sem_mutex_sym]

Note que en la actividad anterior ambos threads ejecutaban el código en subrutinas distintas, a lo que se le llama una solución asimétrica (separación de asuntos o paralelismo de tareas). Sin embargo, el código de las subrutinas era el mismo y por tanto podría convertirse en una solución simétrica. En una solución simétrica los hilos ejecutan el mismo código, es decir, la misma subrutina.

Las soluciones simétricas son a menudo más fáciles de generalizar. Agregue semáforos al pseudocódigo siguiente para forzar a que los incrementos hechos por una cantidad arbitraria de hilos sean con exclusión mutua.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10 shared count := 0

main:
	// Read integer from standard input
	thread_count := read_integer()
	create_thread(thread_count, secondary)

secondary:
	// Critical section
	count := count + 1

2.2.4. Exclusión mutua acotada (multiplex)

Actividad 17 [multiplex]

Modifique la solución a la actividad Actividad 16 [sem_mutex_sym] para que permita un límite superior de n threads ejecutando la sección crítica. A este patrón se le llama multiplex y es útil para problemas donde se tienen distintos entes trabajando al mismo tiempo pero con máximo de capacidad.

Por ejemplo, la cantidad de cajeros atendiendo en las ventanillas de un banco o de clientes patinando en la pista del salón de patines. En este último caso, si la capacidad de la pista se agota, algunos clientes tendrán que esperar afuera, y apenas un cliente sale de la pista, otro podrá ingresar de inmediato.

2.2.5. Barrera (barrier)

Actividad 18 [sem_barrier]

Generalice su solución a la actividad Actividad 14 [rendezvous] para asegurar que una cantidad arbitraria de threads no continúen su ejecución hasta que todos hayan alcanzado (ejecutado) el punto de encuentro. Es decir, si se crean n threads, los primeros n - 1 threads que lleguen deberían bloquearse hasta que el thread en la posición n llegue al punto de encuentro. En tal momento todos los n threads podrán continuar ejecutándose concurrentemente. A este patrón se le conoce como barrera (barrier). Sugerencia: puede tomar como punto de partida el siguiente código.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18 // How many threads have arrived to the barrier
shared count := 0
// Protects the increment of the count
shared can_access_count := semaphore(1)
// Locked (0) until all threads arrive, then it is unlocked (1)
shared barrier := semaphore(0)

main:
  thread_count := read_integer()
  create_threads(thread_count, secondary)

secondary:
  Statement A

  // Adapt rendezvous solution here

  // Statement B can be only executed until all threads have run Statement A
  Statement B

Table 13. Barrera de una pasada con semáforos [sem_barrier]
Archivo	Descripción	Cambios
sem_barrier.pseudo	Implementa una barrera de una pasada. Es decir, después de usada, la barrera no se debe reutilizar.

Actividad 19 [sem_barrier_reusable]

Haga que su solución a la actividad Actividad 18 [sem_barrier] sea reusable. Es decir, que la barrera quede lista para volver a usarse, por ejemplo, dentro de un ciclo. Debe asegurarse de que el contador quede en 0, y los threads que salen de la barrera no se combinen con otros que aún están en ella.

Sugerencia: Puede usar el patrón torniquete. Un torniquete (turnstile) es un dispositivo de control de acceso que impide o da paso a una secuencia de personas de acuerdo a ciertas condiciones. Se usa típicamente en instalaciones deportivas, transporte público, acceso a edificios, parques de diversiones y otros. Se puede lograr un torniquete haciendo que los threads esperen por un semáforo, y una vez que pasen, habiliten el paso al siguiente:

1
2
3
4
5
6
7 shared turnstile := semaphore(0)

secondary:
	...
	wait(turnstile)
	signal(turnstile)
	...

La segunda implementación permite reutilizar barreras. Es decir en la solución de nuevos problemas puede suponer que tiene disponible barreras con la siguiente interfaz:

1
2
3
4
5
6
7 main:
	shared my_barrier := barrier(3)

secondary:
	...
	wait(my_barrier)
	...

2.2.6. Carrera de relevos (barrera)

Actividad 20 [relay_race]

Simule una carrera de relevos, donde los competidores son equipos de threads. Cada equipo consta de dos corredores. Un corredor tomará la estafeta (en inglés, baton) y se posicionará en la línea de salida. El otro corredor esperará en la mitad de la pista a que el primer corredor llegue y le transfiera la estafeta. En tal momento, el segundo corredor seguirá a toda velocidad hasta alcanzar la meta. Ganan únicamente los tres primeros equipos en llegar con la estafeta a la meta.

Su simulación recibirá tres parámetros: la cantidad de equipos, la duración en milisegundos que tarda el primer corredor atravesando la etapa 1 de la carrera (entre la salida y la mitdad de la pista), y la duración en milisegundos del segundo corredor atravesando la etapa 2 de la carrera (de la mitad de la pista hasta la meta). Asuma que los corredores de una etapa tardan exactamente esta duración y no un valor generado al azar. Ejemplo de ejecución:

./relay_race 10 300 700
Place 1: team 2
Place 2: team 4
Place 3: team 1
Simulation time: 1.006079000s

La simulación reportará sólo los tres primeros equipos en llegar. Recuerde verificar que su solución no produzca fugas de memoria ni condiciones de carrera.

¿Afecta el orden de creación de los equipos el resultado de la carrera? Modifique su solución para crear los equipos en orden inverso y compare los resultados de las ejecuciones. Sugerencia, utilice metaprogramación para escoger en tiempo de compilación el orden de creación de los equipos.

Table 14. Carrera con relevos [relay_race]
Archivo	Descripción	Cambios
relay_race.pseudo	Diseño de una simulación de carrera de relevos con equipos de hilos de ejecución.
relay_race.c 2020c	Simula una carrera de relevos con equipos de hilos de ejecución en Pthreads.
Makefile	Sin cambios

2.2.7. Misterio (variable de condición)

Actividad 21 [mist]

Rastree la memoria y el procesamiento del siguiente programa en una hoja en blanco o una hoja de cálculo. Luego agregue una imagen o captura del rastro del programa a un archivo mist.md. Use un editor de imágenes (por ejemplo, Gimp) para reducir las dimensiones y cantidad de colores del archivo. La imagen no debería requerir más de 100kB.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71 #include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct
{
	unsigned int counter;
	unsigned int max;
	pthread_mutex_t mutex;
	pthread_cond_t cond_var;
} mist_t;

void mist_init(mist_t* mist, unsigned max)
{
	mist->counter = 0;
	mist->max = max;
	pthread_mutex_init(&mist->mutex, NULL);
	pthread_cond_init(&mist->cond_var, NULL);
}

void mist_destroy(mist_t* mist)
{
	mist->counter = 0;
	pthread_mutex_destroy(&mist->mutex);
	pthread_cond_destroy(&mist->cond_var);
}

void mistery(mist_t* mist)
{
	pthread_mutex_lock(&mist->mutex);
	++mist->counter;
	if ( mist->counter < mist->max )
	{
		// Preferred: while ( pthread_cond_wait(...) != 0 ) /* empty */;
		pthread_cond_wait(&mist->cond_var, &mist->mutex);
	}
	else
	{
		mist->counter = 0;
		pthread_cond_broadcast(&mist->cond_var);
	}
	pthread_mutex_unlock(&mist->mutex);
}

static mist_t mist;

void* run(void* data)
{
	fprintf(stderr, "%zu: before mist()\n", (size_t)data);
	sleep((unsigned)data);
	mistery(&mist);
	fprintf(stderr, "%zu: after mist()\n", (size_t)data);
	return NULL;
}

int main()
{
	mist_init(&mist, 3);

	pthread_t* workers = malloc(3 * sizeof(pthread_t));
	for ( size_t index = 0; index < 3; ++index )
		pthread_create(&workers[index], NULL, run, (void*)index);

	for ( size_t index = 0; index < 3; ++index )
		pthread_join(workers[index], NULL);

	mist_destroy(&mist);

	return 0;
}

¿Qué trabajo realiza la función mistery()? Explique.

2.3. Productor-consumidor

2.3.1. Problema de buffer acotado

Actividad 22 [prod_cons_bound]

El problema del productor-consumidor en computación es un problema clásico de control de concurrencia, propuesto por Edsger Dijkstra. Se suele presentar de forma semi-concreta, lo que ayudar a identificar otros contextos donde su solución se puede aplicar. Hay dos variantes, una de buffer acotado y otra de buffer no acotado. Esta actividad es sobre la primer variante.

El problema lo tienen dos entes concurrentes, uno que produce algo que el segundo consume. Ambos tienen acceso a un espacio finito donde se alojan los productos, comúnmente llamado buffer y de naturaleza circular. Dado que los entes son concurrentes, uno está agregando productos al buffer mientras el otro está al mismo tiempo consumiéndolos (o quitándolos) del buffer. El problema surge cuando ambos entes actúan a diferente velocidad. Si el consumidor es más rápido que el productor, podría consumir productos que aún no se han colocado en el buffer. Si el productor es más rápido que el consumidor, lo alcanza y sobrescribe productos que el consumidor aún no ha procesado.

El problema se resuelve cuando el consumidor procesa todos los productos y en el mismo orden en que el productor los genera. Al igual que ocurre con seres humanos, la solución implica imponer espera. Si el consumidor es más veloz, vaciará el buffer y deberá esperar a que el productor genere el próximo producto. Si el productor es más veloz y satura el buffer, deberá esperar a que el consumidor libere al menos un espacio para poder continuar produciendo.

Cree una simulación del productor-consumidor. Su programa recibirá seis argumentos en la línea de comandos:

El tamaño del buffer.
La cantidad de rondas, vueltas, o veces que se debe llenar y vaciar el buffer.
La duración mínima en milisegundos que el productor tarda en generar un producto.
La duración máxima en milisegundos que el productor tarda en generar un producto.
La duración mínima en milisegundos que el consumidor tarda en consumir un producto.
La duración máxima en milisegundos que el consumidor tarda en consumir un producto.

El programa debe crear un buffer para almacenar números de precisión flotante, usando la notación r.i, donde r es el número de la ronda y i el número del producto en esa ronda, ambos iniciando en 1. Por ejemplo 3.08 es el octavo producto de la tercera ronda.

Generar un producto no es inmediato. El tiempo que el productor tarda depende de la naturaleza del contexto en que se aplique el problema del consumidor-productor. Para efectos de la simulación, los argumentos 3 y 4 sirven de rango para generar números pseudoaleatorios. Cada vez que el productor tiene que construir un producto, se generará una duración pseudoaletoria y el proceso esperará esta cantidad de milisegundos, simulando hasta que el producto esté acabado. Luego el productor agrega el producto al buffer e imprime en la salida estándar el texto r.i generated.

Consumir un producto no es inmediato. El tiempo que el consumidor tarda se genera también en forma pseudoaletoria con los argumentos 5 y 6. Una vez que el consumidor elimina un producto del buffer imprime en la salida estándar el texto r.i consumed. Sugerencia: indente la salida del consumidor para distinguirla de la salida del productor.

En el siguiente ejemplo de ejecución, los entes hacen dos rondas llenando y consumiendo un buffer de 3 elementos. El productor es rápido y tarda máximo 100ms creando un producto. El consumidor es más lento y podría tardar máximo 750ms consumiendo un producto. Como se puede ver en la salida, el productor rápidamente llena el buffer y debe esperar a que el consumidor libere espacio en el buffer para continuar produciendo. En la salida se comprueba que el consumidor procesa todos los datos generados por el productor y en el mismo orden.

$ ./producer_consumer 3 2 0 100 0 750
Produced 1.01
Produced 1.02
Produced 1.03
		Consumed 1.01
Produced 2.01
		Consumed 1.02
Produced 2.02
		Consumed 1.03
		Consumed 2.01
		Consumed 2.02
Produced 2.03
		Consumed 2.03

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 main(argc, argv[]):
	if argc = 3 then
		shared buffer_size := integer(argv[1])
		shared buffer[buffer_size]
		shared rounds := integer(argv[2])

		create_thread(1, producer)
		create_thread(1, consumer)
	end if

producer:
	count := 0
	for round := 1 to rounds do
		for index := 0 to buffer_size do
			buffer[index] := ++count
			print("Produced ", buffer[index])
		end for
	end for

consumer:
	for round := 1 to rounds do
		for index := 0 to buffer_size do
			value := buffer[index]
			print("Consumed ", value)
		end for
	end for

2.3.2. Problema de buffer no acotado

Actividad 23 [prod_cons_unbound]

Modifique la simulación del problema productor-consumidor generalizando las siguientes restricciones.

El buffer no es acotado, sino de tamaño arbitrario o dinámico, definido por los límites de memoria del sistema.
No existe el concepto de ronda. El primer argumento de línea de comandos indica la cantidad de productos a simular. Identifique los productos en orden secuencial.
Varios productores, indicados por el usuario en el segundo argumento de línea de comandos.
Varios consumidores, indicados por el usuario en el tercer argumento de línea de comandos.
Cada productor y consumidor indica su número en la salida estándar.

El siguiente ejemplo de ejecución simula la construcción de 5 unidades de trabajo por 2 productores y 3 consumidores

$ ./producer_consumer 5 2 3 0 100 0 750
0 produced 1
1 Produced 3
		1 consumed 1
0 produced 2
		2 consumed 3
		0 consumed 5
0 produced 5
		1 consumed 2
1 produced 4
		2 consumed 4

Note que no necesariamente los productos se generan en orden secuencial, debido al indeterminismo de los productores. Recuerde, el problema está resuelto si todos los consumidores procesan todos los productos en el mismo orden en que los productores los generan.

2.3.3. Patrón productor-consumidor

Actividad 24 [prod_cons_pattern]

La solución al problema del productor-consumidor es aplicable a una cantidad significativa de contextos. Generalice el código de su solución para que pueda ser reutilizado. Utilice los mecanismos de reutilización de código de su lenguaje de programación, por ejemplo, subrutinas y metaprogramación en C, o programación orientada objetos polimórfica y plantillas en C++.

Cree una simulación de una red de productores, consumidores, y repartidores. Haga que los consumidores sean dueños de las colas de trabajo, de tal forma que haya una relación 1:1 entre una cola y un consumidor.

Agregue a su código el concepto de repartidor. Un repartidor es tanto un productor como un consumidor (hilo de ejecución) cuya funcionalidad es

Table 15. Patrón productor-consumidor-repartidor [prod_cons_pattern]
Archivo	Descripción	Cambios
prod_cons_pattern/	Carpeta con los archivos fuente que simulan una red de un productor, un repartidor, y una cantidad de consumidores dada por argumentos de línea de comandos.
common/	La subcarpeta `common/` contiene clases base genéricas para crear hilos, semáforos, productores, consumidores, y repartidores. Este código reutilizable facilita la implementación del patrón de software.

2.4. Filósofos comensales

(Pendiente)

2.5. Lectores y escritores

El problema de los lectores y escritores es de mucha importancia en la disciplina de la computación porque ocurre en muchos escenarios, como sistemas operativos y bases de datos.

Actividad 25 [readers_writers]

Permita que varios lectores puedan leer de un medio común, pero sólo un escritor puede modificarlo a la vez. Por cada letra R que se lea de la entrada estándar se crea un hilo lector (reader), y por cada W que se lea de la entrada estándar se crea un hilo escritor (writer). Varios hilos pueden invocar la función read() al mismo tiempo, pero sólo un único hilo puede invocar write() a la vez (exlusión mutua).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 main:
  while true:
    case read_char() of:
      'R': create_thread(reader)
      'W': create_thread(writer)
      EOF: return

reader:
  read()

writer:
  write()

2.5.1. Arreglo reentrante y thread-safe (candado de lectura-escritura)

Actividad 26 [array_reentrant]

Haga que la siguiente implementación de un arreglo dinámico en C sea reentrante. Asegúrese de que produzca la salida esperada y no genere fugas de memoria ni accesos inválidos (con memcheck de valgrind):

Descargar Arreglo dinámico versión 1

Actividad 27 [array_thrsafe_mutex]

Modifique su arreglo dinámico en C para que sea thread-safe. Proteja la implementación de cada subrutina pública con un mutex. Note que las subrutinas para incrementar y reducir la capacidad son privadas (no están declaradas en el encabezado .h). El mutex debe ser único para cada instancia de un arreglo, es decir, dos instancias del arreglo no comparten el mismo mutex.

Su implementación debe permitir al siguiente código de prueba correr correctamente sin generar fugas de memoria, accesos inválidos ni condiciones de carrera:

array_thrsafe_mutex/main.c

Actividad 28 [array_thrsafe_rwlock]

Provea una segunda implementación thread-safe de su arreglo dinámico en C. Provea un candado de lectura y escritura (pthread_rwlock_t) para cada instancia del arreglo dinámico. Proteja el código de cada subrutina que no modifica el arreglo bloqueando el candado para lectura. De la misma forma proteja el código de cada subrutina que modifica bloqueando el candado para escritura.

Su implementación debe permitir al código de prueba del ejercicio anterior correr correctamente sin generar fugas de memoria, accesos inválidos ni condiciones de carrera:

Actividad 29 [array_thrsafe_perf]

Copie sus dos implementaciones del arreglo dinámico thread-safe de los dos ejercicios anteriores a la carpeta array_thrsafe_perf. Renombre los símbolos y archivos de la implementación con mutex del prefijo array_ por array_mutex_ y la implementación con candados de lectura y escritura para iniciar con el prefijo array_rwlock_. De esta forma, las dos implementaciones pueden coexistir en un mismo ejecutable. Para probarlas puede usar el siguiente programa:

array_thrsafe_perf/main.c

El programa de pruebas anterior recibe siete argumentos en la línea de comandos:

La cantidad inicial de elementos en el arreglo (size_t).
La cantidad de operaciones a realizar en el arreglo (size_t).
El porcentaje de operaciones que son inserciones en el arreglo (double).
El porcentaje de operaciones que son eliminaciones en el arreglo (double).
El porcentaje de operaciones que son búsquedas en el arreglo (double).
La cantidad de trabajadores (threads) a probar (size_t).
El arreglo a probar ("mutex" o "rwlock").

De acuerdo al último argumento, el hilo principal crea un arreglo thread-safe protegido por un mutex o por un candado de lectura-escritura (rwlock). Luego el hilo principal inserta la cantidad inicial (primer argumento) de elementos aleatorios en el arreglo.

Luego el programa lanza la cantidad de hilos indicada en el sexto argumento. Los hilos se reparten la cantidad de operaciones indicada en el segundo argumento. Cada hilo procura distribuir sus operaciones sobre el arreglo de acuerdo a los porcentajes dados en los argumentos tres a seis. Los hilos escogen estas operaciones al azar, sin ningún orden definido.

Verifique que el programarealice las operaciones sin fugas de memoria o accesos inválidos. Haga varias corridas para replicar los experimentos de (Pacheco 2011 pp.188-9). Con la herramienta gprof (si lo prefiere puede usar perf) mida la duración de cada corrida.

Para ambos experimentos cree arreglos con 1000 elementos iniciales y realice un millón de operaciones con 1 hilo, 1xCPU, 2xCPU, y 4xCPU, donde CPU es la cantidad de CPU disponibles en la máquina donde realiza las pruebas. En el primer experimento realice 10% de inserciones, 10% de eliminaciones, y 80% de búsquedas en el arreglo. Para el segundo experimento realice 0.1% de inserciones, 0.1% de eliminaciones, y 99.8% de búsquedas. Anote las duraciones de cada corrida en una hoja de cálculo con la siguiente estructura:

Table 16. Duraciones
		threads
distribution	array	1 thread	1xCPU	2xCPU	4xCPU
10-10-80	mutex
10-10-80	rwlock
.1-.1-99.8	mutex
.1-.1-99.8	rwlock

Elabore en su hoja de cálculo un gráfico con cuatro series (una por cada fila) que permita comparar el rendimiento de los mutex contra los candados de lectura-escritura (rwlock). ¿En qué circustancia recomendaría usted usar candados de lectura y escritura? Responda con un comentario en la celda "rwlock" correspondiente.

2.6. Otros problemas de sincronización

2.6.1. Parejas de baile (colas con semáforos)

Actividad 30 [dancing_pairs_1]

En una academia de artes los aprendices están entrenando bailes criollos, los cuales se bailan en parejas de un hombre con una mujer. Como es natural, los bailarines no llegan todos al mismo tiempo al salón, sino que cuando se aproximan hacen dos grupos o filas, una de hombres y otra de mujeres. Cuando en ambas filas hay personas, un hombre y una mujer se toman de la mano e ingresan al salón de baile.

Naturalmente si una o varias mujeres llegan a la fila y la fila de hombres está vacía, tendrán que esperar. Lo mismo ocurre si los hombres llegan y encuentran la fila de mujeres vacía. Simule con threads a los bailarines, su espera en las colas, y el ingreso al salón de baile (subrutina dance()). Suponga que los bailarines se leen de la entrada estándar donde W indica una mujer y M un hombre como muestra el siguiente código. Suponga además que el salón tiene capacidad ilimitada para el número de parejas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 main:
	while true:
		case read_char() of:
			'M': create_thread(male)
			'W': create_thread(female)
			EOF: return

male:
	dance()

female:
	dance()

Sugerencia. Un semáforo puede representar una cola de espera. Un valor inicial de 0 indica que la cola está vacía. Un valor negativo indica la cantidad de threads esperando en ella.

Table 17. Parejas de baile (parte 1) [dancing_pairs_1]
Archivo	Descripción	Cambios
dancing_pairs_1a.alg.c 2019b	En el fondo esta solución es simplemente un encuentro (rendezvous). Cuando una persona llega a su fila A, enviará una señal a la otra fila B indicando que está listo para formar pareja. Si la fila B está vacía, la persona se quedará esperando hasta que alguien llegue a la fila B y le envíe una señal. Sin embargo, puede ocurrir que varios hombres bailen sin pareja o entre ellos, o viceversa. Busque una ruta de ejecución que produzca este comportamiento.
dancing_pairs_1b.alg.c 2019b	La versión anterior fue realizada en clase, donde un valor negativo en la cola de hombres significa la cantidad de mujeres esperando a que llegue un hombre (y viceversa). Esta es otra versión simétrica donde un valor negativo en la cola de hombres indica la cantidad de hombres esperando por ella (y viceversa).

Actividad 31 [dancing_pairs_2]

Si es necesario, modifique su solución al problema Actividad 30 [dancing_pairs_1] para asegurarse de que realmente los bailarines entren en pareja al salón de baile. Es decir, que un hombre invoque dance() concurrentemente con una única mujer y viceversa. Suponga que se trata de un examen o audición, y por tanto, sólo una pareja puede estar en el salón de baile a la vez con el fin de que el jurado pueda calificarlos.

Table 18. Parejas de baile (parte 2) [dancing_pairs_2]
Archivo	Descripción	Cambios
dancing_pairs_2a.alg.c 2019b	Solución propuesta por Julián y Roy.
dancing_pairs_2b.alg.png 2019b	Solución propuesta por Kevin Wang Qiu
dancing_pairs_2c.alg.c 2019b	Solución propuesta por Roy Rojas.

Actividad 32 [dancing_pairs_3]

Opcional. Modifique su solución al problema Actividad 31 [dancing_pairs_2] para asegurarse que los bailarines entren en pareja al salón de baile, el cual tiene capacidad ilimitada para la cantidad de parejas.

Actividad 33 [dancing_pairs_4]

Opcional. Modifique su solución al problema Actividad 32 [dancing_pairs_3] para asegurarse que los bailarines entren en pareja al salón de baile, el cual tiene una capacidad limitada para la cantidad de parejas dada en la entrada estándar.

Si el salón está lleno, las nuevas parejas deberán esperar a que se libere espacio. Las parejas en el salón bailan hasta cansarse. Para cada bailarín genere un número pseudoaleatorio que indica la cantidad de minutos que baila. Cuando se conforma una pareja, bailarán por el mínimo de minutos de sus integrantes.

Actividad 34 [dancing_pairs_5]

Opcional. Modifique su solución al problema Actividad 33 [dancing_pairs_4] para que las parejas, después de bailar en el salón, retornen a la sala de espera. Una vez en la sala de espera, la pareja se disuelve y los integrantes pueden hacer pareja con otros, como si llegaran al salón por primera vez.

Reciba en la entrada estándar la cantidad mínima de minutos que un bailarín deberá estar en la pista de baile. En el momento en que todos los bailarines hayan cumplido este tiempo, la simulación termina.

Actividad 35 [dancing_pairs_6]

Opcional. Modifique su solución al problema Actividad 34 [dancing_pairs_5] para un baile criollo donde se forman, no parejas, sino equipos de 4 bailarines compuestos de dos hombres y dos mujeres.

2.6.2. Fumadores de cigarrillos

Originalmente presentado por Suhas Patil. Participan cuatro hilos:

Un agente que representa un sistema operativo que asigna recursos.
Tres fumadores que representan aplicaciones que necesitan los recursos para realizar su labor.

Los cuatro hilos están en un ciclo infinito. Los fumadores esperan por tres ingredientes que representan los recursos: papel, tabaco, y fósforos. Una vez que obtienen los tres ingredientes pueden fabricar un cigarrillo y fumarlo.

El agente tiene un suminitro infinito de todos los tres ingredientes, y cada fumador tiene un suministro infinito de uno de los tres ingredientes. Es decir, un fumador tiene sólo papel, otro tiene sólo tabaco, y el tercero tiene sólo fósforos. Sin embargo, los fumadores no se comunican entre ellos.

El agente repetidamente escoge dos ingredientes al azar y los hace disponible a los fumadores. El fumador con el tercer ingrediente debería recoger los dos disponibles y fabricar su cigarrillo. Por ejemplo, si el agente provee papel y tabaco, el fumador que tiene fósforos debería recogerlos y avisarle al agente que ya puede sacar otros dos ingredientes.

El reto de la solución es permitir a las aplicaciones, que cuentan con los recursos que necesitan, correr concurrentemente, y evitar despertar una aplicación que no puede proceder. Usted tiene el rol de un desarrollador de aplicaciones, quien no puede modificar el código del agente (sistema operativo). Esta es una restricción realista, dado que no se modifica el sistema operativo cada vez que alguien desarrolla una aplicación para el usuario.

El siguiente pseudocódigo provee la implementación del agente, el cual delega trabajo en sub-agentes que proveen los materiales. Se provee una implementación intuitiva para cada fumador. ¿Qué problema presenta esta solución?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 main:
	shared agent_sem := semaphore(1)
	shared match := semaphore(0)
	shared paper := semaphore(0)
	shared tobacco := semaphore(0)

	create_thread(agent)
	create_thread(smoker_with_matches)
	create_thread(smoker_with_paper)
	create_thread(smoker_with_tobacco)


agent:
	create_thread(agent_without_matches)
	create_thread(agent_without_paper)
	create_thread(agent_without_tobacco)

agent_without_matches:
	while true do
		wait(agent_sem)
		signal(paper)
		signal(tobacco)

agent_without_paper:
	while true do
		wait(agent_sem)
		signal(match)
		signal(tobacco)

agent_without_tobacco:
	while true do
		wait(agent_sem)
		signal(match)
		signal(paper)


smoker_with_matches:
	while true do
		wait(paper)
		wait(tobacco)
		make_cigarette()
		signal(agent_sem)
		smoke()

smoker_with_paper:
	while true do
		wait(match)
		wait(tobacco)
		make_cigarette()
		signal(agent_sem)
		smoke()

smoker_with_tobacco:
	while true do
		wait(match)
		wait(paper)
		make_cigarette()
		signal(agent_sem)
		smoke()

Actividad 36 [cigarette_smokers]

Corrija el pseudocódigo dado para que los agentes y fumadores logren su objetivo.

Sugerencia. La solución propuesta por Parnas usa tres hilos asistentes llamados pushers que responden a los avisos (signal) del agente, llevan cuenta de los ingredientes disponibles, y avisaan al fumador apropiado. Esta solución agrega las siguientes variables al código provisto:

1
2
3
4
5
6
7
8
9 main:
	shared mutex := semaphore(1)
	shared is_match := false
	shared is_paper := false
	shared is_tobacco := false

	shared match_sem := semaphore(0)
	shared paper_sem := semaphore(0)
	shared tobacco_sem := semaphore(0)

Las variables booleanas indican si un ingrediente está o no disponible en la mesa. Los pushers usan los semáforos con nombre de ingrediente para avisar al fumador con tal ingrediente que los ingredientes complementarios están disponibles.

Table 19. Fumadores de cigarrillos [cigarette_smokers]
Archivo	Descripción	Cambios
cigarette_smokers_book.alg.c 2019b	Solución propuesta por el autor original del problema. Adaptada del Pequeño libro de los semáforos.

2.6.3. Formar agua

Este problema aparentemente está basado en un ejercicio de libro de programación concurrente de Gregory Andrews, y popularizado en el curso de sistemas operativos de la Universidad de California en Berkeley.

Actividad 37 [build_h2o]

Hay dos tipos de hilos: los de hidrógeno y los de oxígeno. Su objetivo es formar agua con ellos. Usted dispone de un dispositivo, que cuando se coloca en él dos átomos de hidrógeno y uno de oxígeno, y se invoca bond() en cada uno de ellos, se forma agua. El dispositivo no funciona en cualquier otra combinación de átomos.

El dispositivo sólo puede trabajar en una molécula a la vez. Es decir, usted debe garantizar que los tres átomos de una molécula invoquen bond() antes de los hilos de la siguiente molécula. Escriba el código para cada átomo que garantice este comportamiento. Puede tomar el siguiente código como punto de partida.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 main:
	while true do
		case read_char() of
			'H': create_thread(hydrogen)
			'O': create_thread(oxygen)
			EOF: return

hydrogen:
	bond()

oxygen:
	bond()

3. Paralelismo de datos

3.1. Optimización

La optimización es una etapa normalmente opcional del proceso de resolución de problemas (Fase de optimización en el proceso de resolución de problemas), que surge cuando las implementaciones no logran satisfacer los requerimientos de eficiencia de los usuarios. Consiste regresar a la fase de diseño, y encontrar un modelo solución más eficiente. Este modelo típicamente es más elaborado, complejo, con un efecto de hacer más difícil de comprender al código o hacerlo más dependiente de un contexto, por lo que debe tenerse el cuidado de que exista un retorno de la inversión. Resulta muy apremiante realizar esta fase del proceso de resolución de problemas de forma sistemática, por lo que se propone un método para optimizar del Método sugerido para optimizar.

Figura 4. Fase de optimización en el proceso de resolución de problemas

Método sugerido para optimizar

Medir el rendimiento del código antes de realizar las modificaciones.
Analizar el código para detectar las regiones críticas a optimizar (profiling).
Hacer las modificaciones que se cree incrementarán el rendimiento en las regiones críticas.
Asegurarse de que las modificaciones sean correctas (correr el programa de pruebas).
Medir el rendimiento del código después de realizar las modificaciones y comparar para determinar si hubo una ganancia.
Indiferentemente de si se incrementó o no el rendimiento, documentar las lecciones aprendidas, ya que servirán para otros desarrolladores que intenten optimizar la misma sección de código.
Si es realmente requerido incrementar aún más el rendimiento, repetir desde el paso 2.

3.2. Profiling

Para encontrar regiones de código que podrían ser optimizadas por su alto consumo de recursos se puede usar una herramienta de profiling (análisis dinámico de código ejecutable con fines de optimización) como callgrind de valgrind:

# Install tools
sudo apt install build-essential valgrind kcachegrind

# Compile executable including its source code
cc -g -Wall -Wextra source.c -o executable -pthread

# Run the program under callgrind
valgrind --tool=callgrind --separate-threads=yes ./executable args_for_executable

# Visualize the data collected by callgrind in the current directory
kcachegrind &

Callgrind realiza contabilidad de invocaciones de subrutinas y cantidad de instrucciones ejecutadas. Se requiere incluir el código fuente dentro del ejecutable al compilar el programa. Luego se corre el programa con callgrind, el cual crea archivos en la carpeta donde se invoca con nombres como callgrind.PID-TH donde PID es el número de proceso y TH el número de hilo, si se pide separar las estadísticas de cada hilo ejecutado por el programa. Finalmente se requiere un programa de visualización que tome las estadísticas almacenadas en los archivos y los presente de forma que ayude a las personas a comprender el comportamiento del programa, como KCachegrind (en algunas distribuciones de Linux podría llamarse qcachegrind).

Figura 5. Visualización de KCachegrind de las líneas que consumen más procesamiento

KCachegrind permite encontrar rápida y visualmente las líneas de código fuente que consumen más instrucciones de procesador, y por tanto, las líneas críticas que convienen optimizar, incluso en una base de código extensa. En la esquina superior izquierda de la Visualización de KCachegrind de las líneas que consumen más procesamiento muestra un gráfico de consumo por cada hilo de ejecución. En la esquina inferior izquierda muestra las subrutinas que han ejecutado más instrucciones de procesador en porcentajes, isPrime() está seleccionada. En la esquina superior derecha se muestra las líneas de código fuente de isPrime() que consumieron más instrucciones. Se puede ver la invocación a qSqrt() y el operador módulo (%) son los que causan casi la totalidad del procesamiento. Estos son los puntos críticos a optimizar para esta aplicación.

3.3. Métricas

3.3.1. Incremento de velocidad (speedup)

Para determinar en cada iteración de optimización si hubo realmente una ganancia de rendimiento (pasos 1 y 5 del método sugerido), se puede utilizar varias métricas. La medida relativa speedup \$S\$ (incremento de velocidad), se calcula como la relación entre el tiempo que tarda una computación previa a la optimización (\$T_\text{before}\$), contra el tiempo que tarda la misma computación posterior la optimización (\$T_\text{after}\$):

\$S = \frac{T_\text{before}}{T_\text{after}} = \frac{T_\text{serial}}{T_\text{parallel}}\$

La paralización de código serial es una forma de optimización. Una comparación de incremento de velocidad común es el tiempo de ejecución serial (antes) respecto al tiempo de ejecución posterior a la paralización (después). En este caso, el speedup indica la cantidad de veces que la computación paralela es más rápida que la computación serial. Un valor mayor a 1 indica un incremento de velocidad, 1 que la velocidad se mantiene igual, y un valor menor a 1 un decremento en la velocidad.

3.3.2. Eficiencia

El speedup sólo considera los tiempos de ejecución pero no los recursos que se invirtieron en conseguir el incremento de desempeño. La métrica de eficiencia (\$E\$, efficiency) es una relación entre el incremento de velocidad y la cantidad de trabajadores (\$w\$) que tuvieron que involucrarse para conseguirlo:

\$E = \frac{\text{speedup}}{\text{workers}} = \frac{T_\text{serial}}{T_\text{parallel} \cdot \text{w}}\$

La eficiencia es un valor entre 0 y 1, donde 0 indica un sistema no eficiente, y 1.0 es la eficiencia ideal donde todo el trabajo es realizado en paralelo por los trabajadores, en forma equitativa y sin necesidad de control de concurrencia. Sin embargo, es poco probable que un programa logre una eficiencia de 1.0. Normalmente los programas tienen porciones de código secuencial (por ejemplo, antes de crear los hilos de ejecución, o al usar control de concurrencia como exclusión mutua) y porciones de código paralelo, como ocurre en la línea de tiempo de la Gráfico de tiempo de un programa con tres fases: serial inicial, paralela, y serial final.

Figura 6. Gráfico de tiempo de un programa con tres fases: serial inicial, paralela, y serial final

3.3.3. Ley de Amdahl

La Ley de Amdahl establece que el máximo speedup que un programa puede alcanzar por paralelización está acotado por la porción del programa que se mantiene o sólo puede ser serial. Por ejemplo, para la Gráfico de tiempo de un programa con tres fases: serial inicial, paralela, y serial final la duración total del trabajo si se realizara en forma serial sería \$T_s = 1 + 24 + 1 = 26\$ horas. Si se tuviera una paralelización ideal, la fase paralelizable de 24h se podría repartir entre \$w\$ trabajadores y reducir a \$\frac{24}{w}\$ horas, por ejemplo en la Gráfico de tiempo de un programa con tres fases: serial inicial, paralela, y serial final se ilustran \$w = 3\$ trabajadores que reducirían la fase central a \$\frac{24}{3} = 8\$ horas. Por consiguiente la duración total de la versión paralela del programa sería \$2 + \frac{24}{w}\$ horas, y por lo tanto, el incremento de velocidad se obtendría por la relación:

\$S = \frac{T_s}{T_p} = \frac{26}{2 + \frac{24}{w}}\$

Por ejemplo, con \$w = 3\$ trabajadores, el speedup sería \$S = \frac{26}{2 + \frac{24}{8}} = 2.6\$. Con ocho trabajadores se tendría el doble del speedup anterior \$S = 5.2\$. Para maximizar el speedup es natural pensar en incrementar la cantidad de trabajadores \$w\$, procurando que el denominador se acerque a cero. Sin embargo, en caso extremo, cuando \$w\$ tiende a infinito número de trabajadores se obtiene que

\$\lim_{w \to \infty} S = \lim_{w \to \infty} \frac{26}{2 + \frac{24}{w}} = \frac{26}{2 + 0} = 13\$

Es decir, para la situación del programa de la Gráfico de tiempo de un programa con tres fases: serial inicial, paralela, y serial final, el speedup está acotado a 13. Aunque la Ley de Amdahl puede verse como una limitación negativa al paralelismo, también puede usarse a favor. Si se sabe que para un programa concurrente el speedup máximo es 13, con unos pocos hilos o alquilar unas pocas máquinas en la nube, se podría alcanzar un speedup satisfactorio, en lugar de invertir en recursos costosos que poco incrementarían la velocidad, dado a que está acotada como muestra la El incremento de velocidad está acotado por la porción serial de un programa para 100 trabajadores.

Figura 7. El incremento de velocidad está acotado por la porción serial de un programa

3.4. Descomposición y mapeo

En un problema, la descomposición es identificar unidades de trabajo que se pueden realizar de forma independiente. El mapeo es asignar esas unidades de trabajo a los trabajadores.

La Actividad de mapear tres conjuntos de datos a cuatro trabajadores muestra el resultado de la actividad de mapear tres conjuntos de datos de distinta naturaleza, representados como arreglos en fondo celeste. El valor en cada celda celeste significa una unidad de trabajo medida como una potencial duración. Los números sobre el arreglo de fondo celeste indican el índice basado en cero.

Figura 8. Actividad de mapear tres conjuntos de datos a cuatro trabajadores

Debajo de los arreglos celestes en la Actividad de mapear tres conjuntos de datos a cuatro trabajadores se anota el número de trabajador que realiza esa unidad de trabajo. El número varía de acuerdo al mapeo. Los mapeos pueden clasificarse en estáticos o dinámicos. En el mapeo estático la asignación de las unidades de trabajo se conoce de antemano, es decir, antes de iniciar el trabajo, sólo depende de conocer el número total de unidades de trabajo y trabajadores. El mapeo por bloque y cíclico son dos formas de mapeo estático. En el mapeo dinámico la asignación ocurre durante la realización del trabajo, es decir, los trabajadores se asignan las unidades de trabajo conforme ellos terminan las previas. Aunque normalmente consigue mejores distribuciones, es más costoso en recursos que los mapeos estáticos, dado que requiere control de concurrencia y manipulación de estructuras de datos dinámicas.

3.4.1. Mapeo por bloque

El mapeo estático por bloque asigna rangos continuos de trabajo a cada trabajador. Es el mapeo que potencialmente puede disminuir más fallos de caché o false sharing si se trabaja con memoria continua. El bloque de un trabajador \$i\$ está dado por el rango de índices enteros \$[\text{start}, \text{finish}[\$, donde \$\text{start}\$ y \$\text{finish}\$ son funciones dadas por

\$\text{start(i,D,w)} = i\lfloor \frac{D}{w} \rfloor + \min(i, \mod(D, w))\$

\$\text{finish(i,D,w)} = \text{start(i + 1,D,w)\$

donde \$i\$ es el número del trabajador (iniciando en 0), \$D\$ es la cantidad de datos, y \$w\$ es la cantidad total de trabajadores.

3.4.2. Mapeo cíclico

El mapeo estático cíclico asigna al trabajador \$i\$ todas las unidades de trabajo con índice \${i,i+w, i+2w, ...}\$. Puede tener ventajas cuando las unidades de datos presentan algún patrón predecible y que no es apto para el mapeo por bloque. Se puede hacer un híbrido del mapeo cíclico por bloque que reparte no una unidad, sino bloques de unidades de trabajo de igual tamaño de forma cíclica a cada trabajador.

3.4.3. Mapeo dinámico

Actividad 38 [mapping_simulation]

Escriba un programa que recibe de la entrada estándar un conjunto de duraciones de trabajo, y como argumento de línea de comandos la cantidad de trabajadores. El programa debe crear tantos hilos como trabajadores se indicaron en los argumentos (o la cantidad de CPUs disponibles si se omite), y repartir el trabajo de la entrada estándar siguiendo los tres tipos principales de mapeo vistos en clase: estático por bloque, estático cíclico, y dinámico.

Los hilos de ejecución reciben el trabajo asignado por el mapeo y simulan que lo realizan mediante una espera (sleep). Suponga que las duraciones están dadas en milisegundos. Cada hilo debe llevar la estadística de la cantidad de trabajo asignado.

Tras realizar las tres simulaciones (una por cada tipo de mapeo), el programa reporta estadísticas en la salida estándar que le ayudarían a un desarrollador a escoger el tipo mapeo más adecuado a un conjunto de datos de interés. La salida del programa puede tener formato de tabla como el sugerido a continuación, el cual sigue la estructura del ejemplo de la sección Descomposición y mapeo.

$ echo 1 2 1 3 2 1 1 2 1 3 1 2 2 3 2 2 1 1 2 2 2 2 | ./mapping_simulation 4
39         0    1    2    3 Duration Speedup Efficiency
Block     10   10   10    9    10.00    3.90      0.975
Cyclic     9   12    7   11    12.00    3.25      0.813
Dynamic   10   10   10    9    10.00    3.90      0.975

En la línea de encabezado de la salida 39 es la duración serial (suma de todas las duraciones en la entrada estándar), y 0 a 3 son los números de thread. Los números bajo ellos son las duraciones asignadas (trabajo) de cada hilo. La columna duración indica el tiempo tomado por cada tipo de mapeo (tiempo de pared y no el mayor de los hilos). Con esta duración de tiempo de pared se calcula el incremento de velocidad y la eficiencia, respecto a la hipotética versión serial.

3.5. Concurrencia compartida declarativa (OpenMP)

OpenMP es una tecnología desarrollada por varias empresas para implementar concurrencia de manera más declarativa y menos imperativa. Es una especificación para C y Fortran que varios compiladores implementan. Conviene tener a mano la guía de referencia al iniciar con esta tecnología. Para los ejemplos de esta sección cree una carpeta openmp/ en su repositorio personal de control de versiones para el curso.

3.5.1. Hola mundo (región paralela, directivas)

El siguiente es un "Hola mundo" en OpenMP. En adelante se usará C++, aunque OpenMP puede usarse perfectamente con C.

Para compilar con GCC o un compilador compatible debe habilitarse OpenMP con la opción -fopenmp. El Makefile del ejemplo incluye esta bandera:

gcc -g -Wall -Wextra -fopenmp source.c   -o executable
g++ -g -Wall -Wextra -fopenmp source.cpp -o executable

3.5.2. Hola mundo múltiple (funciones de biblioteca)

Actividad 39 [hello_w]

Modifique el programa de "hola mundo" para permitir al usuario indicar la cantidad de threads como argumento de la línea de comandos. Si el usuario omite este argumento, asuma la cantidad de CPUs disponibles en el sistema. Indague en la especificación cómo obtener el número de procesadores disponibles en OpenMP o bien, la cantidad sugerida de threads a iniciar.

3.5.3. Repartir las iteraciones (`omp parallel for`)

La directiva omp parallel crea siempre una región paralela, que implica la creación y destrucción (join) de threads. La instrucción o bloque paralelizado es ejecutado por todos los _threads del equipo. La directiva omp parallel for siempre debe estar seguida por un ciclo por contador (for) estructurado (sin terminaciones abruptas como break, continue, y return). Por ser una región paralela (por la palabra parallel) también crea y destruye threads, pero a diferencia de omp parallel, omp parallel for reparte las iteraciones del ciclo entre los threads creados:

Actividad 40 [parallel_for]

Modifique el programa de Actividad 39 [hello_w] para repartir iteraciones entre threads. El programa debe permitir al usuario indicar en el segundo argumento opcional de la línea de comandos la cantidad de iteraciones. Si el usuario omite este argumento, tome la cantidad de hilos a crear, de tal forma que cada hilo tenga al menos una iteración con que trabajar.

El programa debe imprimir en la salida estándar el número de thread y las iteraciones que realizó. Por ejemplo, para repartir 10 iteraciones entre 3 threads, una salida podría ser:

$ ./parallel_for 3 10
0/3: iteration 0/10
0/3: iteration 1/10
1/3: iteration 4/10
1/3: iteration 5/10
1/3: iteration 6/10
0/3: iteration 2/10
0/3: iteration 3/10
2/3: iteration 7/10
2/3: iteration 8/10
2/3: iteration 9/10

3.5.4. Reutilizar hilos (`omp for`)

Si se tienen varias regiones parallel for una tras otra que utilizan la misma cantidad de threads, es ineficiente crearlos y destruirlos cada vez que se ingresa y sale de estas secciones, de ahí la utilidad de la directiva for.

Actividad 41 [several_for]

Modifique el programa de Actividad 40 [parallel_for] para realizar tres etapas o fases de iteración. Es decir, tres ciclos for independientes uno tras otro. En cada ciclo se realiza la misma cantidad de iteraciones.

Optimice el programa para reutilizar los threads. Es decir, en cada ciclo no cree ni destruya threads, sino que créelos antes del primer ciclo y destrúyalos después del tercer ciclo. En cada ciclo los threads son reutilizados.

El programa debe imprimir en la salida estándar la etapa en la que se encuentra, el número de thread y las iteraciones que realizó. Las etapas siempre deben aparecer en orden y separadas entre ellas por un cambio de línea. Por ejemplo, para repartir 5 iteraciones entre 2 threads en las tres etapas, una salida podría ser:

$ ./several_for 2 5
stage 1: 0/2: iteration 0/5
stage 1: 1/2: iteration 3/5
stage 1: 1/2: iteration 4/5
stage 1: 0/2: iteration 1/5
stage 1: 0/2: iteration 2/5

stage 2: 1/2: iteration 3/5
stage 2: 1/2: iteration 4/5
stage 2: 0/2: iteration 0/5
stage 2: 0/2: iteration 1/5
stage 2: 0/2: iteration 2/5

stage 3: 1/2: iteration 3/5
stage 3: 1/2: iteration 4/5
stage 3: 0/2: iteration 0/5
stage 3: 0/2: iteration 1/5
stage 3: 0/2: iteration 2/5

3.5.5. Ordenamiento par-impar

Actividad 42 [odd_even_sort_serial]

El siguiente código implementa el ordenamiento par-impar (odd-even transposition sort) de un arreglo a con n elementos. Rastree el algoritmo con el arreglo a = [7 4 6 8 3].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15 for ( int phase = 0; phase < n; ++phase )
{
	if ( phase % 2 == 0 )
	{
		for ( int i = 1; i < n; i += 2 )
			if ( a[i - 1] > a[i] )
				swap( &a[i - 1], &a[i] );
	}
	else
	{
		for ( int i = 1; i < n - 1; i += 2 )
			if ( a[i] > a[i + 1] )
				swap( &a[i], &a[i + 1]);
	}
}

Implemente una versión serial del ordenamiento par-impar (odd-even transposition sort) en una subrutina serial_odd_even_sort(size_t n, double arr[n]) que ordena un arreglo de números flotantes. Escriba un programa de pruebas main() que reciba por argumentos de línea de comandos el tamaño n del arreglo, crea un arreglo de números flotantes de doble precisión en la memoria dinámica, y los inicializa con valores aleatorios. El programa de pruebas ordena el arreglo con su implementación de serial_odd_even_sort().

Puede imprimir el arreglo en la salida estándar para comprobar que realmente se haya ordenado, pero luego deshabilite la impresión para realizar las pruebas de rendimiento. Veririque con memcheck y helgrind de que su programa no haga accesos inválidos, fugas de memoria, ni condiciones de carrera.

Actividad 43 [odd_even_sort_parallel_for]

Provea una solución concurrente con OpenMP del ordenamiento par-impar. Conjeture cuál o cuáles ciclos pueden ser paralelizados en este algoritmo de ordenamiento. Utilice la directiva parallel for para paralelizar el o los ciclos. Modifique el programa de pruebas para recibir como segundo argumento de línea de comandos la cantidad de threads que deben emplearse. Asegúrese que su implementación produce resultados correctos y no genere fugas de memoria.

Actividad 44 [odd_even_sort_two_for]

Cree una segunda solución concurrente con OpenMP del ordenamiento par-impar. Cree un equipo de threads y reutilícelo en él o los for que haya paralelizado. Utilice la directiva for para reutilizar el equipo de threads. Asegúrese que su implementación produce resultados correctos y no genere fugas de memoria.

Actividad 45 [odd_even_sort_perf]

Con la herramienta gprof o perf mida el tiempo de ejecución de su implementación serial, parallel-for, y two-for del algoritmo de ordenamiento par-impar con un millón de elementos (ver apartado siguiente). Anote las duraciones obtenidas en una hoja de cálculo, con 1 thread, 0.5xCPU, 1xCPU, y 2xCPU, donde CPU es la cantidad de CPUs disponibles en la máquina donde se realizaron las pruebas.

3.5.6. Medición de duraciones con `gprof` y `perf`

Los siguientes comandos resumen el uso de gprof:

# Compile a modified executable that measures function call durations
gcc -g -Wall -Wextra -pg -no-pie source.c -o executable

# Run the executable as usual, it will generate binary file gmon.out
./executable args

# Generate a report from the gmon.out binary log
gprof ./executable gmon.out > report.txt

La herramienta perf provee información menos detallada que gprof, pero tiene la ventaja de que no es necesario modificar el ejecutable. Para obtener la duración se puede anteceder el comando con perf stat de la forma:

perf stat ./executable args

3.5.7. Descomposición y mapeo (`schedule`)

Actividad 46 [schedule]

Modifique el programa de Actividad 40 [parallel_for] para repartir iteraciones entre threads usando los tipos de mapeo (scheduling) provistos por OpenMP:

static
static,N
dynamic
dynamic,N
guided
guided,N

Recuerde que el programa debe permitir al usuario indicar la cantidad de hilos y de iteraciones como argumentos opcionales en la línea de comandos. Agregue un tercer parámetro que equivale al número N de la lista de arriba, conocido como el "tamaño de bloque". Si se omite, use el tipo de mapeo sin este parámetro.

Cree un arreglo dinámico de enteros, uno para cada iteración. Haga que los hilos marquen en el arreglo las iteraciones que les fueron asignadas, con su número identificador. Por ejemplo si se reparten 7 iteraciones entre 3 hilos, y si al hilo 2 le correspondieron las iteraciones 5 y 6 establecería

arr[5] := 2
arr[6] := 2

Finalmente el programa debe imprimir en la salida estándar una tabla, con el tipo de mapeo en las filas, las iteraciones en las columnas, y los threads en las celdas. Por ejemplo, para repartir 10 iteraciones entre 3 threads, una salida sin N podría ser:

$ ./schedule 3 10
          0 1 2 3 4 5 6 7 8 9
static    0 0 0 0 1 1 1 2 2 2
dynamic   0 1 0 2 1 0 2 1 0 2
guided    0 0 0 0 1 1 2 2 0 1

La siguiente es una salida hipotética con N=2. Haga más corridas y trate de inferir el algoritmo de mapeo de cada planificación provista por OpenMP.

$ ./schedule 3 10 2
          0 1 2 3 4 5 6 7 8 9
static,2  0 0 1 1 2 2 0 0 1 1
dynamic,2 0 0 1 1 0 0 2 2 1 1
guided,2  0 0 0 0 1 1 2 2 0 0

ToDo: Agregar un usleep() en cada iteración dado por parámetro double, que puede ser constante, proporcional a la iteración (un factor), o proporcional al número de thread.

3.5.8. Reducciones (`reduction`)

Actividad 47 [average]

Haga un programa que lea un conjunto arbitrario de números flotantes de la entrada estándar, calcule concurrentemente el promedio y lo imprima en la salida estándar. La cantidad de números no se conoce de antemano. Use reducciones de OpenMP.

Actividad 48 [desc_stats]

Haga un programa que lea un conjunto arbitrario de números flotantes de la entrada estándar, calcule concurrentemente y en una pasada por el arreglo los siguientes estadísticos: valor mínimo, promedio, desviación estándar, y máximo. Imprima cada estadístico en la salida estándar. La cantidad de números no se conoce de antemano. Use reducciones de OpenMP.

Actividad 49 [desc_stats_median]

Modifique su solución al problema anterior para agregar la mediana. Imprímala antes del promedio. Indague en su lenguaje de programación cómo ordenar concurrentemente el arreglo.

4. Concurrencia distribuida

El paradigma de programación distribuido permite crear programas escalables que aprovechan máquinas que pueden correr procesos y pueden comunicarse a través de redes de computadoras. Se distingue de la distribución compartida en que los hilos pueden acceder a la misma memoria y comparten el mismo reloj. En la concurrencia distribuida, los procesos tienen cada uno su propia memoria exclusiva y los relojes pueden ser distintos, por lo que tienen que comunicarse a través de paso de mensajes.

Existen dos variantes de la distribución. En la distribución heterogénea, los ambientes en el que corre el programa son distintos: diferente hardware, sistema operativo, huso horario, etc., lo que forma una malla de computadoras. En la distribución homogénea, el ambiente (tanto el hardware como el software) debe ser idéntico para todos los procesos del programa, lo que se llama un clúster de computadoras. La distribución homogénea logra conseguir los mayores niveles de paralelismo.

4.1. Distribución simétrica (MPI)

Message Passing Interface (MPI) es una tecnología de distribución homogénea creado por un grupo de académicos con el fin de facilitar el parelismo de aplicaciones científicas, que se convirtió en un estándar de facto. Existen otras tecnologías como Charm++ de más alto nivel.

Cree una carpeta ejemplos/mpi/ en su repositorio de control de versiones.

4.1.1. Hola mundo (proceso)

El siguiente es un "Hola mundo" en MPI:

Table 20. Hola MPI [hello]
Archivo	Descripción	Cambios
hello.cpp	Dice "hola mundo" desde uno o varios procesos en una o varias máquinas.
Makefile	Para compilar programas con MPI se requiere instalar una implementación de MPI como `open-mpi` o `mpich`, luego conviene invocar al script `mpicc` o `mpic++` el cual pasa parámetros al compilador de GCC para que ubique los encabezados y las bibliotecas del MPI instalado.
hosts.txt	Si se quiere que el programa corra en varios nodos de un clúster, se requiere un archivo que los liste. Este archivo está diseñado para mpich y el clúster arenal de la ECCI. Después de generado el ejecutable se puede invocar con `mpiexec -n W -f hosts.txt ./hello`, donde `W` es la cantidad de procesos que se quieren correr en el clúster.

4.1.2. Distribución híbrida (proceso-hilo)

Actividad 50 [hello_hybrid]

El ejemplo de "Hola mundo" lanza un único main thread en cada proceso ejecutado. Modifique el programa para que cada proceso lance tantos secundary thread como CPUs hay disponibles en la máquina donde se ejecuta. Cada thread secundario debe imprimir en la salida estándar una línea antecedida por un tabulador en la que salude al usuario. Por ejemplo si se lanzan dos procesos y cada uno crea tres threads, se podría obtener una salida como la siguiente:

Hello from main thread of process 0 of 2 on hostname1
	Hello from thread 0 of 3 of process 0 on hostname1
	Hello from thread 2 of 3 of process 0 on hostname1
	Hello from thread 1 of 3 of process 0 on hostname1
Hello from main thread of process 1 of 2 on hostname2
	Hello from thread 1 of 3 of process 1 on hostname2
	Hello from thread 0 of 3 of process 1 on hostname2
	Hello from thread 2 of 3 of process 1 on hostname2

Dado que existe indeterminismo por la salida estándar (condición de carrera), la salida que obtenga puede ser muy distinta a la anterior. Sugerencia: Puede usar OpenMP junto con MPI para lograr el modelo de concurrencia híbrida solicitada en esta actividad.

Actividad 51 [hybrid_distr_arg]

Modifique el programa de la actividad anterior para que reciba un rango indicado como dos números enteros [a,b[ en los argumentos de línea de comandos. Su programa debe distribuir (particionar) el rango entre los procesos de forma lo más equitativa posible, y dentro de los procesos debe distribuir los subrangos entre los hilos de ejecución.

El hilo principal de cada proceso debe reportar en la salida estándar el rango asignado al proceso. Use la notación hostname:process.thread: message como prefijo para simplificar la salida. Cada hilo secundario debe reportar su rango asignado antecedido por un tabulador. La siguiente podría ser una interacción con su programa en dos nodos de un clúster, cada uno con un proceso por nodo, y cada nodo con tres CPU:

$ mpiexec -n 2 -f hosts.txt ./hybrid_distr_arg 3 20
hostname1:0: range [3, 12[ size 9
	hostname1:0.0: range [3,6[ size 3
	hostname1:0.1: range [6,9[ size 3
	hostname1:0.2: range [9,12[ size 3
hostname2:1: range [12, 20[ size 8
	hostname2:1.0: range [12,15[ size 3
	hostname2:1.1: range [15,18[ size 3
	hostname2:1.2: range [18,20[ size 2

Reporte además el tamaño del rango asignado a cada proceso e hilo de ejecución.

4.1.3. Comunicación punto a punto (send-receive)

La comunicación punto a punto envía mensajes de un proceso a otro. MPI provee una familia de funciones para enviar y recibir mensajes. Las dos más básicas son: MPI_Send y MPI_Recv.

Actividad 52 [send_recv_ord_sem]

Modifique el ejemplo Hola mundo (proceso) para que los procesos saluden en orden por su identificador (rank). Dado que la función de comunicación punto a punto MPI_Recv implica bloqueo, y la espera es el mecanismo fundamental del control de concurrencia, puede usarse para sincronizar procesos, junto con MPI_Send.

Cada proceso debe escribir en la salida estándar su saludo. Controle la concurrencia de esta impresión con comunicación punto-a-punto simulando semáforos.

Actividad 53 [send_recv_ord]

Modifique la solución a la actividad Hola mundo (proceso) para que los procesos saluden en orden por su identificador (rank) a través de un intermediario. Es decir, los procesos envían su saludo a uno del equipo, quien recibe los saludos y los imprime en la salida estándar en orden. Use comunicación punto a punto.

Actividad 54 [send_recv_urd]

Modifique la solución de Actividad 53 [send_recv_ord] para que usando comunicación punto a punto, los procesos saluden al proceso 0 y éste reporte los saludos en el orden en que los recibió.

4.1.4. Lectura distribuida

Actividad 55 [stdin_sendrecv]

Modifique la solución de Actividad 54 [send_recv_urd] para que los procesos lean un arreglo de números en la entrada estándar con los cuales trabajar. Luego cada proceso imprime los números que leyó en la salida estándar. Haga las correcciones para que todos los procesos tengan una copia del arreglo.

MPI permite que sólo el proceso 0 lea de la entrada estándar. Más específicamente, la entrada la lee el comando mpiexec, la captura y la envía al proceso 0. Los demás procesos no reciben la entrada, por tanto si intentan leer, se quedarán bloqueados perennemente. Si un proceso debe leer de la entrada estándar, el proceso 0 tendrá que usar comunicación para enviarla a los demás procesos.

Actividad 56 [hybrid_distr_stdin]

Modifique el programa del rango distribuido (Actividad 51 [hybrid_distr_arg]) para que en caso de que el rango no se especifique en los argumentos de línea de comandos, los lea en la entrada estándar. ¿Qué salida produce al proveer el rango de la actividad anterior en la entrada estándar a su programa?

Haga las modificaciones necesarias para que el programa pueda leer el rango en la entrada estándar y distribuirlo entre los procesos e hilos en el clúster. Sugerencia, use comunicación punto a punto.

4.1.5. Medición de tiempo de pared

Para calcular la duración en segundos del tiempo en la pared use la función MPI_Wtime.

Actividad 57 [stdin_wtime]

Modifique la solución de Actividad 55 [stdin_sendrecv] para que los procesos reporten en la salida estándar la cantidad de segundos en que tarda su ejecución.

Actividad 58 [hybrid_distr_wtime]

Modifique el programa del rango Actividad 56 [hybrid_distr_stdin] para que cada proceso reporte en la salida estándar la cantidad de segundos en que tarda su ejecución. Un ejemplo de salida podría ser el siguiente.

$ mpiexec -n 2 -f hosts.txt ./hybrid_distr_wtime 3 20
hostname1:0: range [3, 12[ size 9 in 0.000123s
	hostname1:0.0: range [3,6[ size 3
	hostname1:0.1: range [6,9[ size 3
	hostname1:0.2: range [9,12[ size 3
hostname2:1: range [12, 20[ size 8 in 0.000342s
	hostname2:1.0: range [12,15[ size 3
	hostname2:1.1: range [15,18[ size 3
	hostname2:1.2: range [18,20[ size 2

4.1.6. Comunicación colectiva: broadcast

Actividad 59 [stdin_bcast]

Modifique la solución de Actividad 59 [stdin_bcast] para que el proceso 0 comparta los valores leídos de la entrada estándar con los demás procesos mediante comunicación colectiva.

Actividad 60 [hybrid_distr_bcast]

Modifique el programa del rango distribuido en la entrada estándar (Actividad 58 [hybrid_distr_wtime]) para que en lugar de usar comunicación punto a punto para enviar el rango, use comunicación colectiva.

4.1.7. Comunicación colectiva: reduce

Actividad 61 [lucky_number_reduce]

Escriba un programa donde cada proceso escoge al azar su número de la suerte entre 00 y 99 inclusive. Haga que el proceso 0 reporte el mínimo, el promedio, y el máximo de los números de la suerte escogidos entre todos los procesos. Puede adaptar su solución a Actividad 52 [send_recv_ord_sem] para que la salida aparezca ordenada. El siguiente puede ser un ejemplo de ejecución:

$ mpiexec -n 5 -f hosts.txt ./{act}
Process 0: my lucky number is 83
Process 0: all minimum: 10
Process 0: all average: 44.20
Process 0: all maximum: 83
Process 1: my lucky number is 56
Process 2: my lucky number is 10
Process 3: my lucky number is 10
Process 4: my lucky number is 62

4.1.8. Comunicación colectiva: all-reduce

Actividad 62 [lucky_number_who]

Escriba un programa donde cada proceso escoge al azar su número de la suerte entre 00 y 99 inclusive, y el mismo proceso reporta si su número es el menor o el mayor de los números escogidos por todos los procesos. El siguiente puede ser un ejemplo de ejecución:

$ mpiexec -n 5 -f hosts.txt ./lucky_number_who
Process 0: my lucky number (83) is greater than the average (36.00)
Process 0: my lucky number (83) is the maximum (83)
Process 1: my lucky number (18) is less than the average (36.00)
Process 2: my lucky number (07) is less than the average (36.00)
Process 2: my lucky number (07) is the minimum (07)
Process 3: my lucky number (46) is greater than the average (36.00)
Process 4: my lucky number (26) is less than the average (36.00)

El reporte de mínimo, máximo y promedio es independiente. Por ejemplo, si sólo un proceso se ejecuta cumplirá los tres criterios:

$ mpiexec -n 1 -f hosts.txt ./lucky_number_who
Process 0: my lucky number (31) is the minimum (31)
Process 0: my lucky number (31) is equals to the average (31.00)
Process 0: my lucky number (31) is the maximum (31)

4.2. Distribución heterogénea: aceleración gráfica

Cree una carpeta ejemplos/gpu en su repositorio personal.

4.2.1. Transmisión de calor

Actividad 63 [heat_perf]

Descargue los siguientes archivos a una carpeta ejemplos/gpu/heat_perf. Agregue la hoja de cálculo a control de versiones, pero no los casos de prueba (archivos .bin). Llene las celdas en blanco de la hoja de cálculo con las duraciones de ejecución de las actividades en esta sección. Actualice la gráfica para incluir los incrementos de velocidad en un eje secundario.

Table 21. Rendimiento de la transmisión de calor [heat_perf]
Archivo	Descripción	Cambios
heat_perf.ods 2019b	Hoja de cálculo para anotar duraciones de ejecución de las actividades siguientes.
heat-tests-large.7z	Algunos casos de prueba binarios.

Actividad 64 [heat_serial]

Descargue los archivos de la solución serial a una carpeta ejemplos/gpu/heat_serial. Agréguelos a control de versiones. Compile la solución. Realice las cuatro ejecuciones de la columna serial de la hoja de cálculo que descargó en Actividad 63 [heat_perf], y anote la cantidad de generaciones y sus duraciones. Un ejemplo de ejecución podría ser:

./heat_serial ../heat_perf/test001.bin 0.1

Sugerencia 1: realice las ejecuciones en terminales distintas simultáneamente. Es decir, no espere a que la anterior finalice para realizar la siguiente.
Sugerencia 2: compare las ejecuciones de su ejecutable generado con GCC y PGI.

Table 22. Transmisión de calor serial [heat_serial]
Archivo	Descripción	Cambios
heat_serial.c 2019b	(Versión serial de libro/documentación)
heat_serial.c 2019b	Recibe dos argumentos: un archivo binario que contiene una matrix de flotantes de doble precisión, y un epsilon. Simula transmisión de calor desde el borde de la matriz sobre toda la superficie, hasta que el calor se equilibre. Es decir, hasta que ninguna diferencia supere el epsilon.
Makefile	Un makefile para compilar con GCC.
Makefile-pgi	Un makefile para compilar con PGI (antiguamente The Portland Group). Establece la variable PATH dependiente del laboratorio 102-IF. Para usarlo use la opción `-f` como en `make -f Makefile-pgi`.

Actividad 65 [heat_openmp]

Copie la solución de Actividad 64 [heat_serial] a la carpeta heat_openmp. Modifique la solución para aprovechar los CPU disponibles en la máquina donde se ejecuta la simulación. Use OpenMP como tecnología para paralelizar la simulación.

Ejecute la solución resultante con los dos casos de prueba de Actividad 63 [heat_perf] y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial.

Actividad 66 [heat_openacc]

Copie la solución de Actividad 64 [heat_serial] a la carpeta heat_openacc_cpu. Modifique la solución para paralelizar la simulación con OpenACC. Adapte el Makefile-pgi para generar un ejecutale unificado (unified binary) que incluya código para CPU y GPU. Revise cuidadosamente la salida del compilador. Realice dos tipos de ejecuciones:

Ejecute la solución resultante en CPU con los dos casos de prueba de Actividad 63 [heat_perf] y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial. Compare las duraciones con OpenMP.
Ejecute la solución resultante en GPU con los dos casos de prueba de Actividad 63 [heat_perf] y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial.

La siguiente podría ser una interacción:

$ make
pgcc -c -g -acc -ta=multicore,tesla -Minfo=accel heat_openacc.c -o heat_openacc.o
pgcc.   -g -acc -ta=multicore,tesla -Minfo=accel heat_openacc.o -o heat_openacc

$ ACC_DEVICE_TYPE=host ./heat_openacc ../heat_perf/test001.bin 0.1
...
$ export ACC_DEVICE_TYPE=nvidia
$ ./heat_openacc ../heat_perf/test001.bin 0.1

Programación concurrente: ejemplos de clase

1. Concurrencia compartida imperativa (Phtreads)

1.1. Hola mundo (thread)

1.2. Hola mundo múltiple (indeterminismo)

1.3. Hola mundo numerado (memoria privada)

1.4. Hola mundo numerado (memoria compartida)

1.5. Hola mundo ordenado (espera activa)

1.6. Posición en la carrera (mutex)

1.7. Hola mundo ordenado (semáforos)

1.8. Hola mundo ordenado (seguridad condicional)

2. Concurrencia de tareas

2.1. Primitivas

2.1.1. Algoritmos (pseudocódigo)

2.1.2. Redes de Petri

2.1.3. Semáforos

2.2. Patrones básicos

2.2.1. Avisar/notificar (signal)

2.2.2. Encuentro (rendezvous)

2.2.3. Exclusión mutua con semáforos (mutex)

2.2.4. Exclusión mutua acotada (multiplex)

2.2.5. Barrera (barrier)

2.2.6. Carrera de relevos (barrera)

2.2.7. Misterio (variable de condición)

2.3. Productor-consumidor

2.3.1. Problema de buffer acotado

2.3.2. Problema de buffer no acotado

2.3.3. Patrón productor-consumidor

2.4. Filósofos comensales

2.5. Lectores y escritores

2.5.1. Arreglo reentrante y thread-safe (candado de lectura-escritura)

2.6. Otros problemas de sincronización

2.6.1. Parejas de baile (colas con semáforos)

2.6.2. Fumadores de cigarrillos

2.6.3. Formar agua

3. Paralelismo de datos

3.1. Optimización

3.2. Profiling

3.3. Métricas

3.3.1. Incremento de velocidad (speedup)

3.3.2. Eficiencia

3.3.3. Ley de Amdahl

3.4. Descomposición y mapeo

3.4.1. Mapeo por bloque

3.4.2. Mapeo cíclico

3.4.3. Mapeo dinámico

3.5. Concurrencia compartida declarativa (OpenMP)

3.5.1. Hola mundo (región paralela, directivas)

3.5.2. Hola mundo múltiple (funciones de biblioteca)

3.5.3. Repartir las iteraciones (omp parallel for)

3.5.4. Reutilizar hilos (omp for)

3.5.5. Ordenamiento par-impar

3.5.6. Medición de duraciones con gprof y perf

3.5.7. Descomposición y mapeo (schedule)

3.5.8. Reducciones (reduction)

4. Concurrencia distribuida

4.1. Distribución simétrica (MPI)

4.1.1. Hola mundo (proceso)

4.1.2. Distribución híbrida (proceso-hilo)

4.1.3. Comunicación punto a punto (send-receive)

4.1.4. Lectura distribuida

4.1.5. Medición de tiempo de pared

4.1.6. Comunicación colectiva: broadcast

4.1.7. Comunicación colectiva: reduce

4.1.8. Comunicación colectiva: all-reduce

4.2. Distribución heterogénea: aceleración gráfica

4.2.1. Transmisión de calor

3.5.3. Repartir las iteraciones (`omp parallel for`)

3.5.4. Reutilizar hilos (`omp for`)

3.5.6. Medición de duraciones con `gprof` y `perf`

3.5.7. Descomposición y mapeo (`schedule`)

3.5.8. Reducciones (`reduction`)