Universidad de Costa Rica
Escuela de Ciencias de la Computación e Informática
San Pedro, Montes de Oca

Prof. Jeisson Hidalgo-Céspedes
Prof. Allan Berrocal Rojas
Prof. José Andrés Mena Arias
Recurso Peso Descripción

Carta al estudiante

 — 

Programa del curso y acuerdos

Ejemplos de clase

 — 

Ejemplos de programas realizados durante las lecciones

Material del curso

 — 

Material de referencia

Aula virtual

 — 

En Mediación Virtual

Quices

25%

En el aula virtual

Tareas

25%

Enunciados en el aula virtual

Proyecto01

25%

Servidor web concurrente. Enunciados de avances en el aula virtual

Proyecto02

25%

Concurrencia declarativa. Enunciados de avances en el aula virtual

Introducción

Material de referencia

  1. Crear un repositorio de Git. Claves SSH

  2. Clonar repositorio de Git. Moverse por los directorios con comandos

  3. Linux: Prompt PS1. Configuración .bashrc

  4. Mínimo programa en C. Compilar en línea de comandos. Geany

  5. Git: .gitignore, commit, push | Referencia de Git

  6. Linter para C/C++

  7. Makefiles. PHONY | Referencia a GNU Make

  8. Valgrind. Memcheck. Helgrind | Referencia a Valgrind

  9. Reglas para memcheck y helgrind en Makefile

  10. Jerarquía de archivos .gitignore

  11. Pruebas de caja negra

  12. px. wget. PATH. history. .bashrc. icdiff

  13. Documentación de código con Doxygen | Referencia a Doxygen

  14. Buenas prácticas de programación

Paradigmas concurrente y distribuido

k06-abr

  1. Presentación del curso. Carta al estudiante

  2. Enunciado tarea01: goldbach_serial

  3. Paradigmas de programación concurrente y distribuida

Concurrencia imperativa

Concepto de hilo de ejecución

v09-abr

  1. Hardware y software concurrente. Ejemplo de una necesidad: sonidos de peces

  2. Hola mundo en C. Editar y compilar desde línea de comandos.

  3. POSIX Threads (Pthreads). Git ignore, commit, push.

  4. Hola mundo en Pthreads (código)

  5. Compilar y correr hola mundo en Pthreads. Indeterminismo

  6. Diferencia entre concurrencia de tareas y paralelismo de datos en Pthreads

  7. Análisis dinámico de código: Valgrind (memcheck, helgrind)

  8. Instrumentalización de código: Google Sanitizers

  9. Rastreo de memoria. Concepto de hilo de ejecución

Familias de hilos

k13-abr

  1. Makefile: Reglas PHONY, reglas para GCC, Clang, Google Sanitizers

  2. Makefile linter (Google cpplint). Filtrar reglas

  3. .gitignore. Valgrind en el Makefile (memcheck, helgrind)

  4. Diferencia entre los sanitizers: asan, msan, tsan, ubsan

  5. Adaptar archivos para nuevo ejemplo. Comando copiar directorios. Variables en makefile

  6. hello_w: arreglos de threads. sysnconf. Serialización de hilos con join

  7. Preguntas sobre sysnconf. Diferencia entre cantidad de CPUs y de hilos

  8. Explicación y corrección de la serialización por join

  9. Convertir texto a números con sscanf(). Validación con errno

Datos privados y compartidos

v16-abr

  1. Anuncios: autodiáctica, taller de C

  2. Vulnerabilidad arreglo de longitud variable en la pila

  3. Memoria dinámica en C. Fuga de memoria. Máxima cantidad de hilos por proceso

  4. Concepto de registro de memoria. Variables en makefiles

  5. Variables globales. Structs en C. Registro de datos privados de hilos

  6. Registro de datos compartidos entre hilos

Taller de C++ a C

s17-abr

  1. Filosofía de la computación. Paradigmas de programación: procedimental

  2. Problema de ejemplo: comando estadísticas

  3. Cómo implementar un objeto controlador en C

  4. Archivo encabezado (lo público), fuente (privado). Registro opaco (atributos privados)

  5. Assert. Imprimir argumentos de línea de comandos

  6. Comparación de textos en C. Múltiples puntos de retorno de subrutina. Imprimir ayuda

  7. Preguntas de estudiantes. Análisis del argumento -b (binario)

  8. Una cola de nombres de archivos

  9. Agregar a la cola. Eliminar la cola

  10. Trabajar tanto con archivos como la entrada estándar y en binario

  11. Leer (flotantes) de archivos de texto y binarios

  12. Implementación de un arreglo dinámico en C

  13. Redimensionar el arreglo: explicación de realloc y memset

  14. Uso del arreglo dinámico. Ejemplo de ejecución

  15. Explicación rápida del Makefile. Renombrar con git

Espera activa

k20-abr

  1. Repaso ejemplo hello_iw. Make -j: concurrencia

  2. Tiempo de pared, de CPU, de programa (usuario), y de sistema

  3. Medición de tiempo de pared clock_gettime, eficiencia división vs multiplicación

  4. Control de flujo vs control de concurrencia. Makefile obtiene nombre de carpeta

  5. Espera activa

  6. El efecto nocivo de la espera activa

  7. Compilación concurrente (make -jN)

  8. Condición de carrera. Ejemplo position_race

Exclusión mutua y semáforo

v23-abr

  1. Condición de carrera en el ciclo de instrucción

  2. Exclusión mutua (candado). Metáfora del puente angosto

  3. Implementación de mutex en Pthreads

  4. Solución al problema position_race

  5. Preguntas: dos mutex, arreglos de mutex, no liberar un mutex

  6. Semáforo y su metáfora. Incremento. Decremento

  7. Arreglo de semáforos. Semáforos vs mutex

  8. Implementación con semáforos (semaphore.h)

Seguridad condicional

k27-abr

  1. Seguridad condicional: problema

  2. Seguridad condicional: implementación

  3. Seguridad condicional: ejecución. Crear/destruir matrices en C

  4. Seguridad condicional: preguntas

Concurrencia de tareas

Algoritmos y redes de Petri

k27-abr

  1. Rutas de ejecución: pseudocódigo

  2. Redes de Petri: lugares, transiciones, aristas

  3. Rutas de ejecución: solución con red de petri

  4. Simulación de una red de petri: tokens

  5. Fork y join en una red de petri

Avisar/notificar (signaling)

v30-abr

  1. Notación de pseudocódigo

  2. Ejemplo for_count

  3. Red de petri de for_count

  4. Definición original de semáforo

  5. signaling: solución pseudocódigo

  6. Generalización de signaling

  7. (Lineamientos de revisión de tareas)

  8. signaling: modelo en redes de Petri

  9. multiplex y mutex en una red de Petri

Encuentro (rendezvous)

k04-may

  1. Repaso: avisar/notificar (signaling)

  2. Rendezvous solución 1: avisar luego esperar

  3. Rendezvous solución 2: un hilo avisa, el otro espera

  4. Rendezvous: bloqueo mutuo (deadlock)

  5. Rendezvous: red de Petri

  6. Simular operadores lógicos con semáforos. Generalización del rendezvouz (barrera)

Mutex, multiplex

k04-may (cont.)

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

v07-may

  1. Exclusión mutua (mutex) con redes de Petri

  2. Pregunta: objetivo de las redes de Petri y pseudocódigo

  3. Exclusión mutua simétrica: pseudocódigo

  4. Exclusión mutua simétrica: red de Petri

  5. Exclusión mutua múltiple (multiplex): pseudocódigo

  6. Exclusión mutua múltiple (multiplex): red de Petri

Productor-consumidor de buffer acotado

v07-may (cont.)

  1. Problema del productor-consumidor de buffer acotado

  2. Pseudocódigo dado

  3. Solución en red de Petri

  4. Solución en pseudocódigo

  5. Implementación inicial en Pthreads

k11-may: reentrante, thread_safe

  1. Repaso de la solución en pseudocódigo

  2. Implementación de la simulación

  3. Implementación del productor

  4. Generar números aleatorios y pseudoaleatorios

  5. Impl. del consumidor. Regla por defecto del Makefile. Extensión VSCode pseudocódigo

  6. Reentrante vs thread-safe

  7. Generador lineal congruente de números pseudoaleatorios

  8. Ideas para un generador pseudoaleatorio reentrante y thread-safe

Productor-consumidor de buffer NO acotado

v14-may: diseño

  1. El problema del productor-consumidor de buffer no acotado

  2. Pseudocódigo del hilo principal

  3. Pseudocódigo del productor (versión 1)

  4. Pseudocódigo del productor (versión 2)

  5. Cola thread-safe (el buffer no acotado)

  6. Pseudocódigo del consumidor. Problema de detener los consumidores

  7. Detener a los consumidores con contadores

  8. Detener los consumidores cuando la cola está vacía

  9. Detener los consumidores con un valor especial en la cola

  10. Redes de Petri base para productor-consumidor

k18-may: implementación (parte 1)

  1. Una solución del productor-consumidor en redes de Petri

  2. Repaso del diseño en pseudocódigo

  3. Modularización del código de buffer acotado

  4. Makefile para código modularizado (múltipes archivos fuente)

  5. Reglas para debug/release y Sanitizers en Makefile

  6. Implementación de la futura cola thread-safe (parte 1)

v21-may: implementación (parte 2)

  1. Correcciones hechas al Makefile

  2. Implementación de la cola serial (parte 2)

  3. Cola thread-safe: implementación de init() y queue_is_empty()

  4. Implementación dequeue(): unlock prematuro, bloqueo mutuo, y sus correcciones

  5. Implementación de queue_clear(). ¿Es queue_is_empty reentrante?

  6. Usar la cola. Implementación de la simulación con varios productores y consumidores

  7. Implementación de los productores

  8. Implementación de los consumidores

  9. Dificultad de depurar código concurrente y distribuido

Paralelismo de datos

Descomposición y mapeo

k25-may

  1. Anuncio 1: Encuesta de avance 1

  2. Anuncio 2: cronograma. Importancia de la calidad de código

  3. Descomposición. Instrucciones del ejercicio de mapeo

  4. Mapeo estático por bloque

  5. Mapeo estático cíclico

  6. Mapeo estático cíclico con bloques

  7. Mapeo dinámico

  8. Comparación de los métodos de mapeo. Incremento de velocidad (speedup)

Proyecto01: servidor web

v28-may

  1. Proyecto01: servidor web de Goldbach

  2. Código dado: estructura, Makefile

  3. Patrón modelo-vista-controlador

  4. Metáfora del banco para aceptar conexiones de clientes web

  5. Metáfora de trámite bancario para solicitudes HTTP

  6. Responsabilidades del HttpConnectionHandler

  7. Mensajes de solicitud y respuesta HTTP. Enrutamiento. HTML

  8. Probar que el servidor web es serial. TO-DOs para el proyecto

  9. Bitácoras. Patrón singleton

  10. Diseño preliminar del servidor web en red de Petri

Patrón productor-consumidor

k01-jun

  1. Comparación de los tipos de mapeo (bloque, cíclico, dinámico)

  2. Método recomendado de optimización

  3. Simulación de red con el patrón productor-consumidor

  4. Clase controladora de la simulación de red

  5. Cola genérica thread-safe. Clase Semaphore

  6. Clase genérica Producer. Clase abstracta Thread. Clase NetworkMessage

  7. Clase genérica Consumer. Clase base Assembler. Ejercicio con Assembler

  8. Clase base Dispatcher (repartidor)

Profiling. Eficiencia. Ley de Amdahl. Barrera

v04-jun

  1. Profiling. Valgrind. Callgrind

  2. Visualización con Kcachegrind

  3. Profiling en el método sugerido de optimización

  4. Métrica de eficiencia

  5. Ley de Amdahl (máximo speedup teórico)

  6. Ejercicio de simulación de mapeo

  7. Barrera: diseño en pseudocódigo

  8. Concepto de barrera. Barreras en Pthreads

  9. Por qué el pseudocódigo de sem_barrier no es reusable