CS INTERACTIVE WORKSHOP

Una carrera justa

Los dos algoritmos ordenan exactamente el mismo arreglo. En cada tic, cada uno hace una sola operación: comparar dos valores o escribir uno. Gana el que necesita menos operaciones para terminar.

¿Cuánto cuesta cada uno?

Así crece el trabajo cuando el arreglo crece.

Para que la carrera sea justa

• Dale a cada algoritmo una copia del mismo arreglo, nunca uno ya ordenado por el anterior.
• Usa una semilla fija para poder repetir el experimento.
• Compila con -O2 y corre varias veces: la primera vuelta suele ser más lenta.
• Cuenta operaciones además de medir tiempo: el tiempo cambia de máquina a máquina, las operaciones no.

Lo que vas a notar

• Con n grande, un n² pierde siempre contra un n log n.
• Con n pequeño o casi ordenado, Insertion Sort puede ganarle a cualquiera.
• Dos algoritmos con la misma O pueden tardar distinto por la caché y las constantes.

Mutex

La llave de un baño: una persona a la vez, y quien la toma la devuelve.

Protege secciones críticas cortas. Tiene dueño: solo el hilo que hizo lock puede hacer unlock.

Semáforo

Un parqueo con N espacios: si hay campo entras, si no esperas.

Un contador sin dueño. Sirve para limitar capacidad y para que un hilo le avise a otro.

Barrera

El guía del tour: nadie sigue hasta que llegue todo el grupo.

Sincroniza fases. La simulación de calor la usa para que ningún hilo empiece la iteración siguiente antes de tiempo.

Atómicos

Un torniquete: avanza de un clic, sin candados.

Operaciones que el procesador hace de una sola vez. Ideales para contadores y banderas compartidas.

Consejos

• Toma los recursos siempre en el mismo orden. Es la forma más sencilla de evitar deadlocks.
• Mantén las secciones críticas cortas: nada de printf ni E/S con un mutex tomado.
• Cada sem_init y pthread_mutex_init lleva su destroy.
• Nunca uses espera activa (while(!listo);): bloquea con un semáforo o una variable de condición.

Para depurar

• Compila con -fsanitize=thread para detectar condiciones de carrera.
• valgrind --tool=helgrind ./prog encuentra errores de sincronización.
• Si sospechas de un deadlock, adjunta gdb y mira dónde está cada hilo con thread apply all bt.

Dos placas, no una

Copiar la tarea del compañero mientras él la sigue corrigiendo sale mal.

Se lee siempre de la placa vieja y se escribe en la nueva (doble búfer). Así ningún hilo lee un valor a medio actualizar, y el resultado es idéntico con 1 o con 8 hilos, sin importar en qué orden terminen.

Repartir la placa

Cada hilo recibe una franja de filas contiguas. Para calcular el borde de su franja necesita leer una fila del vecino (las "filas fantasma"). No hay problema: esa fila está en la placa vieja, que nadie modifica durante la iteración.

La barrera

El guía del tour: nadie avanza hasta que llegue todo el grupo.

Antes de intercambiar las placas, todos los hilos deben terminar. La barrera hace esperar a los rápidos, así que el más lento marca el ritmo. Activa "El hilo 0 va más lento" o el reparto desbalanceado y mira cuánto tiempo se pierde esperando.

¿Cuándo parar?

Cada hilo guarda el cambio más grande de su franja. Después de la barrera se toma el máximo de todos (una reducción) y, si es menor que ε, la placa llegó al equilibrio.

Estabilidad: r ≤ 1/4

r mide qué tan grande es cada paso en el tiempo. Si r pasa de 1/4, cada iteración amplifica el error en vez de suavizarlo y aparecen ondas que crecen sin control. Sube r a 0.30 y míralo explotar.

La barrera que gira

void spin_barrier_wait(spin_barrier_t* b, int* local) {
  int mine = !*local; *local = mine;
  if (atomic_fetch_sub(&b->remaining, 1) == 1) {
    atomic_store(&b->remaining, b->total);
    atomic_store(&b->sense, mine);   // abre
  } else {
    while (atomic_load(&b->sense) != mine)
      if (++spins > 2000) sched_yield();
  }
}

Lo mismo con OpenMP

#pragma omp parallel
while (!done) {
  #pragma omp for schedule(static) reduction(max:step)
  for (int i = 1; i < rows - 1; ++i)
    step = fmax(step, heat_step_rows(cur, next, cols, r, i, i + 1));
  #pragma omp single
  { swap(&cur, &next); done = step <= eps; step = 0; }
}

Consejos

• Compara siempre contra la versión serial celda por celda: con doble búfer deben ser idénticas.
• Una barrera por iteración basta si la reducción usa dos juegos de casillas (par e impar).
• Separa las casillas de cada hilo en líneas de caché distintas para evitar el false sharing.
• Nunca imprimas dentro del ciclo de cálculo, y mide con CLOCK_MONOTONIC.
• Busca condiciones de carrera con -fsanitize=thread.

Pruébalo en tu máquina

cd core-c-engines/concurrency/simulations/heat-diffusion
make -C pthreads && make -C openmp
./pthreads/bin/heat_pthreads 400 400 4 0.05 --compare
./pthreads/bin/heat_pthreads 400 400 4 0.05 --compare --sleep-barrier
./openmp/bin/heat_openmp 400 400 4 0.05 --compare

--compare corre también la versión serial e imprime la aceleración y si las placas son idénticas.

El saludo de tres vías

"¿Me oyes?" "Sí, ¿y tú a mí?" "Sí." Y ya pueden hablar.

SYN, SYN-ACK y ACK sincronizan los números de secuencia de ambos lados. Desde ahí, cada byte enviado tiene un número, y el ack dice "ya recibí todo hasta aquí".

Anatomía de HTTP

Un mensaje HTTP es texto plano: una primera línea (método y ruta, o código de estado), encabezados Nombre: valor, una línea vacía y después el cuerpo. Cada línea termina en \r\n.

Tu servidor no envía Content-Length en las figuras: el cliente sabe que terminó cuando el servidor cierra la conexión (Connection: close).

Un hilo por cliente

Cada cliente que entra recibe su propio mesero.

El hilo principal solo hace accept(). Por cada conexión crea un std::thread(task, client) que lee, responde y cierra. Así un cliente lento no bloquea a los demás. Con miles de clientes conviene un pool fijo de hilos.

Segmentos y MSS

TCP no manda mensajes, manda un flujo de bytes partido en segmentos. En Ethernet con IPv6 cada segmento lleva como máximo 1440 bytes de datos (el MSS). Pide charizard y verás la respuesta llegar en varios pedazos.

¿Quién cierra primero?

Tu servidor llama a Close() apenas termina de escribir, así que él envía el primer FIN. Por eso es el servidor el que queda en TIME_WAIT: un detalle que importa cuando reinicias el servidor y el puerto parece ocupado.

Consejos

• recv puede devolver menos bytes de los que esperas. Lee en ciclo hasta tener el mensaje completo.
• Usa htons/ntohs para puertos: la red es big-endian.
• SO_REUSEADDR evita el error «Address already in use» al reiniciar el servidor.
• Revisa el valor de retorno de cada llamada. Un -1 ignorado es un bug escondido.

Para probar

• curl -v http://localhost:1234/GET/batman muestra la petición y la respuesta completas.
• nc localhost 1234 te deja escribir HTTP a mano.
• Wireshark con el filtro tcp.port == 1234 te enseña cada paquete real.