Concurrencia y paralelismo

1. Dos palabras que se confunden

En lenguaje corriente «concurrente» y «paralelo» suenan a lo mismo. En sistemas operativos significan cosas diferentes, y la diferencia importa:

Concurrencia es la propiedad de un programa o sistema de tener varias tareas en curso al mismo tiempo: todas han empezado y ninguna ha terminado, aunque en un instante dado solo una esté ejecutándose. Es una cuestión de estructura: cómo se organiza el trabajo en tareas independientes.

Paralelismo es ejecutar varias tareas literalmente en el mismo instante, cada una en su propio procesador o núcleo. Es una cuestión de ejecución: requiere hardware con más de una unidad de cálculo.

De ahí se desprenden tres consecuencias. Se puede tener concurrencia sin paralelismo: un solo núcleo que alterna entre tareas, dándole a cada una un turno corto, como hacía cualquier sistema de tiempo compartido de los años setenta. Se puede tener paralelismo sin concurrencia en sentido interesante: una operación vectorial que suma cuatro pares de números en una sola instrucción. Y lo habitual hoy es tener las dos: muchas tareas concurrentes que el sistema reparte sobre varios núcleos. Este diagrama compara el tiempo de dos tareas, A y B, en los dos escenarios:

Vamos a verlo con números. Los dos experimentos siguientes usan hilos de la biblioteca pthreads, que ya conoces de Procesos e Hilos: pthread_create lanza una función en un hilo nuevo y pthread_join espera a que termine.

2. Experimento: repartir un cálculo

El primer programa tiene un trabajo fijo, mil doscientos millones de sumas, y lo reparte en partes iguales entre tantos hilos como se le pida. Los hilos no comparten ningún dato: cada uno acumula en su propia variable local, por lo que no hay nada que coordinar. Al final mide el tiempo transcurrido (el «de pared», como el de un reloj colgado de la pared) y el tiempo de CPU consumido por el proceso entero:

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TOTAL 1200000000UL            /* sumas en total, repartidas entre los hilos */

static double segundos(clockid_t reloj)
{
    struct timespec t;
    clock_gettime(reloj, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

static void *trabajo(void *arg)
{
    unsigned long vueltas = *(unsigned long *)arg;
    volatile unsigned long suma = 0;          /* variable local: solo este hilo la toca */
    for (unsigned long i = 0; i < vueltas; i++)
        suma += i;
    return NULL;
}

int main(int argc, char *argv[])
{
    int n = argc > 1 ? atoi(argv[1]) : 1;
    if (n < 1 || n > 64)
        return 1;
    pthread_t hilos[64];
    unsigned long vueltas = TOTAL / n;

    double inicio = segundos(CLOCK_MONOTONIC);
    for (int i = 0; i < n; i++)
        if (pthread_create(&hilos[i], NULL, trabajo, &vueltas) != 0) {
            fprintf(stderr, "no se pudo crear el hilo %d\n", i);
            return 1;
        }
    for (int i = 0; i < n; i++)
        pthread_join(hilos[i], NULL);
    double real = segundos(CLOCK_MONOTONIC) - inicio;
    double cpu = segundos(CLOCK_PROCESS_CPUTIME_ID);

    printf("%2d hilo(s): pared %5.2f s   CPU total %5.2f s\n", n, real, cpu);
    return 0;
}

Todos los hilos reciben la misma dirección &vueltas, pero solo la leen: leer un dato compartido que nadie modifica es seguro. Compilamos con -pthread y ejecutamos con 1, 2, 4 y 8 hilos. Primero obligando al proceso a usar un único núcleo con taskset -c 0, y después dejándolo usar los 16 que tiene la máquina de pruebas:

$ gcc -std=c17 -Wall -Wextra -pthread -o calculo calculo.c
$ nproc
16
$ for n in 1 2 4 8; do taskset -c 0 ./calculo $n; done
 1 hilo(s): pared  2.14 s   CPU total  2.14 s
 2 hilo(s): pared  2.20 s   CPU total  2.20 s
 4 hilo(s): pared  2.06 s   CPU total  2.06 s
 8 hilo(s): pared  2.05 s   CPU total  2.03 s
$ for n in 1 2 4 8; do ./calculo $n; done
 1 hilo(s): pared  2.09 s   CPU total  2.09 s
 2 hilo(s): pared  1.10 s   CPU total  2.18 s
 4 hilo(s): pared  0.55 s   CPU total  2.18 s
 8 hilo(s): pared  0.29 s   CPU total  2.29 s

Los dos bloques cuentan historias opuestas:

• Con un solo núcleo hay concurrencia pero no ganancia. Los ocho hilos existen a la vez y el planificador los alterna, pero la CPU solo puede hacer 2 segundos de trabajo en 2 segundos. El tiempo de pared no baja; más bien sube un poco por el costo de cambiar entre hilos.
• Con varios núcleos hay paralelismo y el tiempo baja casi en proporción. Con 2 hilos tarda 1,10 s (aceleración de 2,09 / 1,10 ≈ 1,9); con 4, 0,55 s (≈ 3,8); con 8, 0,29 s (≈ 7,2). La aceleración es casi lineal porque el trabajo se divide en partes totalmente independientes.
• El tiempo de CPU total no baja nunca. Sigue siendo de unos 2 segundos, o un poco más. El paralelismo no hace que se haga menos trabajo: lo reparte entre más núcleos para que termine antes en el reloj de pared.

3. Experimento: solapar esperas

Si la concurrencia sin paralelismo no acelera los cálculos, ¿para qué sirve? Para algo muy frecuente: cuando las tareas pasan la mayor parte del tiempo esperando. Una petición a un servidor remoto, una lectura de disco o un clic del usuario dejan a la tarea bloqueada, sin usar CPU. Mientras una espera, otra puede avanzar. Este segundo programa lanza n hilos y cada uno simula una operación de entrada/salida lenta durmiendo medio segundo:

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double segundos(void)
{
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

/* Simula una operación de entrada/salida lenta: medio segundo de espera. */
static void *peticion(void *arg)
{
    (void)arg;
    struct timespec medio = { 0, 500000000L };
    nanosleep(&medio, NULL);
    return NULL;
}

int main(int argc, char *argv[])
{
    int n = argc > 1 ? atoi(argv[1]) : 1;
    if (n < 1 || n > 64)
        return 1;
    pthread_t hilos[64];

    double inicio = segundos();
    for (int i = 0; i < n; i++)
        if (pthread_create(&hilos[i], NULL, peticion, NULL) != 0) {
            fprintf(stderr, "no se pudo crear el hilo %d\n", i);
            return 1;
        }
    for (int i = 0; i < n; i++)
        pthread_join(hilos[i], NULL);

    printf("%2d peticiones de 0,5 s: pared %4.2f s\n", n, segundos() - inicio);
    return 0;
}

Lo ejecutamos otra vez con taskset -c 0, es decir, con un único núcleo:

$ gcc -std=c17 -Wall -Wextra -pthread -o espera espera.c
$ for n in 1 4 10; do taskset -c 0 ./espera $n; done
 1 peticiones de 0,5 s: pared 0.50 s
 4 peticiones de 0,5 s: pared 0.50 s
10 peticiones de 0,5 s: pared 0.50 s

Diez peticiones de medio segundo tardan medio segundo, no cinco. Con un solo núcleo, y sin ningún paralelismo, los tiempos de espera se solapan: los diez hilos se duermen casi al mismo tiempo y el núcleo apenas trabaja. Si el programa las hubiera atendido una tras otra, habría tardado 5 segundos. Esta es la ventaja que da la concurrencia por sí misma, y es el motivo por el que un servidor web atiende miles de conexiones con unos pocos núcleos.

Reunimos las dos lecciones en una regla práctica:

4. Cuánto se puede acelerar: la ley de Amdahl

En calculo.c todo el trabajo se podía repartir. En un programa real casi siempre queda una parte que solo puede hacerse en serie: leer los datos de entrada, combinar los resultados parciales, escribir la salida. Esa parte limita la ganancia sin importar cuántos núcleos se añadan. Gene Amdahl lo formuló en 1967. Si una fracción f del tiempo de ejecución en un núcleo es paralelizable y el resto, 1 − f, es serie, entonces con n núcleos:

Aceleración = 1 / ((1 − f) + f / n). Cuando n crece sin límite, la aceleración tiende a 1 / (1 − f).

Fíjate en el límite: si solo el 90 % del programa es paralelizable, jamás se podrá ir más de 10 veces más rápido, aunque se usen mil núcleos, porque el 10 % serie siempre estará ahí. La tabla muestra la aceleración para tres programas distintos:

Con 16 núcleos, un programa que es 90 % paralelizable acelera 6,4 veces, no 16: usa el 40 % de la potencia disponible. La lección práctica es que, antes de paralelizar, hay que medir cuánto del tiempo corresponde a código que sí se puede repartir. Y la lección técnica, que es la que nos ocupa en este curso, es que la parte «serie» suele ser precisamente la coordinación: los hilos que esperan turno para entrar a una sección protegida con un candado son, de hecho, tiempo serie. Cuanto más se sincroniza, menos se acelera.

5. Probar con un simulador

Este simulador aplica la ley de Amdahl a un trabajo que en un núcleo dura 100 unidades de tiempo. La primera barra muestra ese trabajo con un núcleo, dividido en su parte serie (gris) y su parte paralelizable (azul). La segunda muestra cómo queda con n núcleos: la parte paralelizable se encoge, la serie no, y el espacio vacío es el tiempo que se ahorra. Los valores iniciales, 90 % y 4 núcleos, reproducen una fila de la tabla anterior.

Prueba tres cosas. Pon 100 % y comprueba que la aceleración es igual al número de núcleos: es el caso de calculo.c. Pon 50 % y sube los núcleos a 1024: la aceleración nunca llega a 2. Y con 90 %, compara 8 y 16 núcleos: duplicar el hardware mejora la aceleración solo de 4,7 a 6,4, y la eficiencia cae del 59 % al 40 %.

6. De dónde viene la concurrencia

Los hilos no son la única fuente de concurrencia. Dentro de un sistema operativo hay varias, y todas obligan a pensar en lo mismo: qué ocurre cuando dos actividades tocan un dato a la vez.

El caso que más se estudia, y el que usaremos en los ejemplos, son los hilos de un proceso, porque comparten todo el espacio de direcciones (variables globales, montón) y por eso son los más fáciles de usar y los que más errores producen. Los procesos aislados están protegidos por el sistema de memoria virtual; los hilos no. Los mismos principios, bajo nombres diferentes, sirven para señales, para el núcleo y para sistemas distribuidos.

7. El precio de la concurrencia

Hasta aquí todo fueron ventajas, y las dos que vimos son reales: aprovechar varios núcleos y solapar esperas. El inconveniente es que, en cuanto las tareas concurrentes comparten datos que se pueden modificar, el resultado deja de depender solo del programa. Depende además del orden exacto en que el planificador intercala las instrucciones de cada hilo, y ese orden cambia en cada ejecución, según la carga de la máquina, el número de núcleos o el tamaño de la caché.

Los problemas de la programación concurrente se agrupan en tres familias, y cada una ocupa una parte del curso:

1. Corrección: las condiciones de carrera. Dos hilos leen y escriben el mismo dato y se pisan: se pierden actualizaciones, se leen valores a medias. El programa no falla con un error claro, simplemente da resultados incorrectos algunas veces. Es el tema de los bloques 1 a 3. datos
2. Vivacidad: los interbloqueos. Al arreglar lo anterior con candados aparece el problema contrario: dos hilos que esperan cada uno algo que tiene el otro, para siempre. El programa no da resultados incorrectos, sino que deja de avanzar. Es el tema del bloque 8. progreso
3. Rendimiento: la contención. Cada candado convierte código paralelo en serie, y la ley de Amdahl se aplica sin piedad: un programa con demasiada sincronización puede ser más lento con ocho hilos que con uno. Se trata a lo largo de todo el curso, sobre todo en los bloques 3 y 4. velocidad

Lo difícil de estos errores es que son no deterministas: pueden no aparecer en las pruebas, desaparecer al añadir una línea de depuración y presentarse solo en producción, con carga. No se resuelven con prueba y error, sino razonando sobre todos los intercalados posibles y usando herramientas que los impidan o los detecten. Por eso el curso empieza por entender el problema con precisión (temas 2 a 5) antes de ofrecer las soluciones.

8. Ver los hilos en Linux

Antes de estudiar cómo coordinar hilos conviene saber dónde mirarlos. Linux los trata como una especie de proceso ligero, y ofrece varias formas de observarlos. Para probarlas usamos un programa auxiliar que lanza tres hilos que no hacen otra cosa que contar sin parar, y se queda dormido 30 segundos para dar tiempo a inspeccionarlo:

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

static void *girar(void *arg)
{
    (void)arg;
    volatile unsigned long n = 0;
    for (;;)
        n++;
    return NULL;
}

int main(void)
{
    pthread_t h[3];
    for (int i = 0; i < 3; i++)
        pthread_create(&h[i], NULL, girar, NULL);
    printf("pid %d\n", getpid());
    fflush(stdout);
    sleep(30);
    return 0;
}

Lo ejecutamos en segundo plano y miramos el estado del proceso, sus hilos y el directorio /proc/PID/task, donde el núcleo crea una carpeta por cada hilo:

$ gcc -std=c17 -Wall -Wextra -pthread -o vivos vivos.c
$ ./vivos &
pid 752
$ grep Threads /proc/752/status
Threads:	4
$ ps -L -o pid,lwp,nlwp,psr,stat,pcpu,comm -p 752
    PID     LWP NLWP PSR STAT %CPU COMMAND
    752     752    4   5 Sl+   0.0 vivos
    752     754    4   9 Rl+  99.0 vivos
    752     755    4  11 Rl+  99.0 vivos
    752     756    4  13 Rl+  99.0 vivos
$ ls /proc/752/task
752
754
755
756

El proceso tiene 4 hilos: el hilo principal más los tres creados. Cada fila de ps -L es un hilo. PID es el mismo para todos (es el proceso); LWP (lightweight process) es el identificador de cada hilo, y el del hilo principal coincide con el PID; NLWP es el número de hilos del proceso. Las columnas más interesantes son las dos últimas: los tres hilos de cálculo están en estado R (ejecutándose) con un 99 % de CPU cada uno, y PSR indica que cada uno está en un núcleo diferente (9, 11 y 13). Eso es paralelismo real, observado desde fuera. El hilo principal, dormido en sleep, está en estado S y no consume CPU.

9. Cómo trabajaremos

El curso se apoya en lo que sabes de Procesos e Hilos y en el C de Programación en C para Sistemas Operativos. Combina tres tipos de actividad:

1. Programas con pthreads en C: cada herramienta de sincronización se prueba con un programa real, primero mostrando el problema y después la solución. Compilan con gcc -std=c17 -Wall -Wextra -pthread. C
2. Simuladores en JavaScript: como los errores de concurrencia no se reproducen a voluntad, los simuladores permiten recorrer los intercalados paso a paso, forzar el peor caso y ver el estado de cada hilo, el valor de cada semáforo o el ciclo de un interbloqueo. JavaScript
3. Herramientas de análisis: ThreadSanitizer y Helgrind detectan carreras y mal uso de candados en programas reales; ps -L, top -H y /proc permiten observar los hilos. Linux

$ sudo apt install build-essential procps util-linux valgrind
# build-essential trae gcc y make; procps trae ps y top;
# util-linux trae taskset y lscpu; valgrind trae Helgrind

10. El mapa del curso

Los 47 temas van del problema a las soluciones y de las soluciones a sus propios fallos. Cada bloque responde una pregunta:

Los bloques 1 y 2 definen el problema con rigor; el 3 baja al hardware; del 4 al 6 se aprenden las herramientas de la más simple a la más expresiva; el 7 las aplica a los problemas clásicos; el 8 estudia el peor fallo que ellas permiten; y los dos últimos amplían la visión y cierran con proyectos.

11. Resumen

• Concurrencia es tener varias tareas en curso al mismo tiempo (estructura); paralelismo es ejecutarlas en el mismo instante en distintos núcleos (ejecución). Se puede tener la primera sin el segundo.
• Con un solo núcleo, repartir un cálculo entre hilos no lo acelera (2,14 s con 1 hilo, 2,05 s con 8); con 16 núcleos, 8 hilos lo bajan de 2,09 s a 0,29 s, casi 7,2 veces menos.
• El paralelismo no reduce el trabajo total: el tiempo de CPU sumado se mantiene en unos 2 s; lo que baja es el tiempo de pared.
• Con tareas que esperan E/S, la concurrencia solapa las esperas aun con un núcleo: diez peticiones de 0,5 s tardaron 0,5 s en total, no 5 s.
• Para tareas limitadas por la CPU conviene un hilo por núcleo; para tareas limitadas por la E/S, muchas tareas en curso.
• Ley de Amdahl: aceleración = 1 / ((1 − f) + f/n). La parte serie fija un tope: con f = 90 %, nunca más de 10 veces. La sincronización excesiva convierte código paralelo en serie.
• La concurrencia viene de procesos, hilos, señales e interrupciones, E/S asíncrona y del propio núcleo. Los hilos de un proceso son el caso más delicado porque comparten todo el espacio de direcciones.
• Su precio son tres familias de problemas: corrección (condiciones de carrera), vivacidad (interbloqueos) y rendimiento (contención). Son no deterministas y exigen razonar sobre todos los intercalados.
• En Linux, nproc cuenta los núcleos, /proc/PID/status y ps -L muestran los hilos de un proceso, y la columna PSR indica en qué núcleo corre cada uno.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Compila calculo.c y ejecútalo con 1, 2, 4, 8 y 16 hilos, con y sin taskset -c 0. Calcula la aceleración de cada caso y compárala con el número de hilos. ¿Qué ocurre con más hilos que núcleos? Pruébalo con el doble de nproc.
2. Usa taskset -c 0,1 para limitar el programa a dos núcleos y repite el experimento con 1, 2, 4 y 8 hilos. ¿Cuál es el máximo que logras y por qué?
3. Modifica espera.c para que cada hilo haga primero 0,1 s de cálculo y después duerma 0,5 s. Ejecútalo con un solo núcleo y con varios, con 1 y con 10 hilos. ¿En qué momento deja de solaparse todo?
4. Calcula a mano la aceleración con 8 núcleos de un programa 75 % paralelizable. Compruébala con el simulador y averigua con cuántos núcleos se alcanza el 90 % de la aceleración máxima.
5. Ejecuta vivos y mira con top -H -p PID los hilos del proceso. ¿Qué ves en la columna de CPU? Comprueba con taskset -a -c 0 -p PID (limita todos los hilos a un núcleo) cómo cambia el reparto.
6. Cuenta con ps -eL --no-headers | wc -l y con ps -e --no-headers | wc -l cuántos hilos y cuántos procesos hay en tu sistema. ¿Qué proceso tiene más hilos? Pista: ps -eo nlwp,comm --sort=-nlwp | head.