Tema 1: Conceptos fundamentales

Introducción

Concepto de programación concurrente

• Avances en HARDWARE (procesadores específicos de E/S)
• Nuevos SO que optimizan el uso del procesador (E/S concurrente)
• Nuevos problemas de sincronización
• Programación concurrente como disciplina

Los primeros sistemas concurrentes fueron los propios sistemas operativos, donde un solo procesador atendía a múltiples usuarios.

• Hitos principales:

  • Aparición del concepto de thread o hilo de ejecución, que permite que los programas se ejecuten más rápido y con menor sobrecarga que usando únicamente procesos independientes.
  • Aparición de lenguajes de propósito general como Java que dan soporte directo a la programación concurrente.
  • Aparición de Internet: campo abonado para el desarrollo y la utilización de programas concurrentes (navegadores, servidores web, chats, etc.).

• Concurrencia (RAE): Acaecimiento o concurso de varios sucesos en un mismo tiempo.

• Si sustituimos suceso por proceso obtenemos la definición de concurrencia en computación.

Programa ≠ Proceso

• Programa:

  • Conjunto de instrucciones.
  • Estático (para que pueda realizar acciones debe ponerse en ejecución).
  • Secuencia de líneas de código que especifican qué hacer con un conjunto de datos.
  • Comparable con una clase en Programación Orientada a Objetos (POO).

• Proceso:

  • Programa en ejecución (instancia en memoria).
  • Dinámico.
  • Representado por el valor del contador de programa (PC), registros del procesador, una pila (stack) y una sección de datos (heap y variables globales).
  • Comparable con un objeto/instancia en POO.
  • Pueden existir múltiples procesos ejecutando el mismo programa (al igual que existen múltiples objetos instanciados a partir de una misma clase).

• Analogía con POO:

  • POO: Una sola clase → Muchas instancias de objetos.
  • Programación Concurrente: Un solo programa → Múltiples procesos ejecutando dicho programa.
  • Un proceso no tiene por qué abarcar todo un programa completo; un programa puede dividirse en varios procesos concurrentes ejecutando partes diferentes (ej. navegadores como Chrome o Firefox).

Concurrencia vs. Paralelismo

• Concurrencia:

  • Dos procesos son concurrentes cuando la primera instrucción de uno de ellos se ejecuta después de la primera instrucción del otro y antes de la última.
  • Existe solapamiento en la línea temporal de ejecución, aunque no necesariamente se ejecuten en el mismo instante físico.

• Paralelismo:

  • Si dos o más procesos se ejecutan exactamente al mismo tiempo en hardware diferente (múltiples núcleos/procesadores) → Programación paralela.
  • La programación concurrente ofrece un paralelismo potencial. Que sea real o simulado dependerá del hardware subyacente.

Definición clásica de Rob Pike (co-creador de Go y Plan 9): "La concurrencia trata sobre estructurar un programa para manejar muchas cosas a la vez. El paralelismo trata sobre la ejecución simultánea de muchas cosas a la vez."

Figura 1: Representación de la ejecución concurrente.

• Cuando varios procesos se ejecutan concurrentemente pueden:

  • Colaborar para resolver una tarea común.
  • Competir por recursos finitos del sistema.

• En ambos casos es imprescindible introducir mecanismos de comunicación y sincronización.

• Programación Concurrente:

  • Disciplina que permite especificar la ejecución concurrente de las acciones de un programa, así como diseñar las técnicas para resolver los problemas inherentes a dicha ejecución (mecanismos de comunicación y sincronización).
  • Es intrínsecamente más compleja que la programación secuencial tradicional.

David Baron (nota en su oficina de Mozilla):

---

Beneficios de la programación concurrente

• ¿Cuáles son los beneficios clave de adoptar la programación concurrente?

  • Mejor aprovechamiento de la CPU: Evita que el procesador quede inactivo durante operaciones lentas de Entrada/Salida (I/O).
  • Mayor velocidad de ejecución: En sistemas con múltiples procesadores o núcleos, cada proceso/hilo puede ejecutarse en paralelo (ej. cálculo numérico, procesamiento de imágenes, compilación paralela con make -j o cargo).

• Solución a problemas inherentemente concurrentes:

  • Sistemas de control en tiempo real.
  • Tecnologías web (servidores HTTP, plataformas de chat, navegadores).
  • Aplicaciones con interfaz gráfica de usuario (GUI) y videojuegos (separando el renderizado de la lógica).
  • Simulación de sistemas físicos.
  • Sistemas Gestores de Bases de Datos (SGBD) para mantener la integridad en transacciones simultáneas.

---

Concurrencia y arquitecturas hardware

Según el número de procesadores del sistema:

• Sistemas monoprocesador: 1 solo procesador/núcleo.
• Sistemas multiprocesador: 2 o más procesadores/núcleos.

La programación concurrente aporta beneficios en ambas arquitecturas:

• Arquitecturas monoprocesador:

  • Existe ejecución concurrente intercalando el tiempo de CPU entre los procesos → Multiprogramación / Time-sharing.
  • La ilusión de simultaneidad se logra mediante el rápido cambio de contexto (context switch) realizado por el sistema operativo.
  • Todos los procesos e hilos comparten la memoria principal. La comunicación y sincronización se realiza mediante variables compartidas.

• Arquitecturas multiprocesador:

  • Permiten paralelismo real. Se clasifican en:
    • Fuertemente acopladas: Procesadores conectados a un bus común con acceso a una memoria compartida → Multiproceso.
    • Débilmente acopladas: No existe memoria compartida; cada nodo tiene su memoria local y se comunican a través de red → Procesamiento distribuido (mediante paso de mensajes).

• El paso de mensajes también puede aplicarse en sistemas multiproceso y monoprocesador.

---

Cuadro resumen

• Programa Concurrente: Conjunto de acciones que pueden ser ejecutadas de forma solapada o simultánea.
• Programa Paralelo: Programa concurrente ejecutado sobre una arquitectura multiprocesador/multinúcleo.
• Programa Distribuido: Programa paralelo ejecutado sobre sistemas sin memoria compartida.

Procesadores / Memoria	Memoria Compartida	Sin Memoria Compartida
1 Procesador	Multiprogramación	—
N Procesadores	Multiproceso (Paralelismo real)	Programación distribuida

---

Especificación de ejecución concurrente

• ¿Qué instrucciones pueden ejecutarse concurrentemente?
  • No todas las partes de un programa son independizables:

Dependiente (Secuencial)	Independiente (Concurrente)
x := 1;	x := 1;
y := x + 2;	y := 2;
z := y + 1;	z := 3;

• En la primera columna, la segunda instrucción lee x modificado por la primera (dependencia de datos).
• En la segunda columna, las instrucciones son totalmente independientes y su orden de ejecución no altera el resultado.

Condiciones de Bernstein

Permiten determinar formalmente si dos conjuntos de instrucciones $S_i$ y $S_j$ pueden ejecutarse de manera concurrente.

Dado un conjunto de instrucciones $S_k$:

• $L(S_k)$: Conjunto de lectura (variables leídas o referenciadas por $S_k$).
• $E(S_k)$: Conjunto de escritura (variables modificadas o escritas por $S_k$).

Dos bloques $S_i$ y $S_j$ se pueden ejecutar concurrentemente si y solo si cumplen las tres condiciones de Bernstein:

1. $L(S_i) \cap E(S_j) = \varnothing$ (Lo que lee $S_i$ no lo escribe $S_j$)
2. $E(S_i) \cap L(S_j) = \varnothing$ (Lo que escribe $S_i$ no lo lee $S_j$)
3. $E(S_i) \cap E(S_j) = \varnothing$ (Ninguno escribe en la misma variable)

Ejemplo práctico

Dadas las siguientes instrucciones:

S1: a := x + y;
S2: b := z - 1;
S3: c := a - b;
S4: w := c + 1;

1. Conjuntos de lectura y escritura:

Bloque	$L(S)$ (Lectura)	$E(S)$ (Escritura)
$S_1$	$\{x, y\}$	$\{a\}$
$S_2$	$\{z\}$	$\{b\}$
$S_3$	$\{a, b\}$	$\{c\}$
$S_4$	$\{c\}$	$\{w\}$

2. Matriz de compatibilidad concurrente (Sí / No):

	$S_1$	$S_2$	$S_3$	$S_4$
$S_1$	—	Sí	No (escribe $a$, $S_3$ lee $a$)	Sí
$S_2$	—	—	No (escribe $b$, $S_3$ lee $b$)	Sí
$S_3$	—	—	—	No (escribe $c$, $S_4$ lee $c$)
$S_4$	—	—	—	—

Ejercicio 1

Usando las condiciones de Bernstein, construye una tabla de compatibilidad para el siguiente conjunto de instrucciones:

S1: cuad := x * x;
S2: m1   := a * cuad;
S3: m2   := b * x;
S4: z    := m1 + m2;
S5: y    := z + c;

---

Orden de ejecución e Indeterminismo

• Programas secuenciales: Orden total. Para unas mismas entradas, la secuencia de ejecución es siempre fija y predecible.

• Programas concurrentes: Orden parcial. La velocidad relativa de los hilos/procesos depende del planificador (scheduler) del SO.

El orden parcial introduce el concepto de indeterminismo: ejecutar el mismo programa con los mismos datos de entrada puede producir resultados diferentes en cada ejecución. El indeterminismo está en la raíz de los principales problemas de la programación concurrente.

---

Problemas inherentes a la programación concurrente

Exclusión mutua

Garantía de que un recurso compartido o región de código (recurso crítico) solo puede ser accedido por un único proceso o hilo a la vez.

¡Atención! Lo que se ejecuta concurrentemente a bajo nivel son las instrucciones máquina generadas por el compilador. Una instrucción de alto nivel como x = x + 1 no es atómica; genera tres instrucciones ensamblador:

LOAD  X, R1   ; 1. Leer X en registro
ADD   R1, 1   ; 2. Incrementar registro
STORE R1, X   ; 3. Escribir registro en X

Si dos hilos ejecutan x = x + 1 al mismo tiempo sin protección, las instrucciones ensamblador pueden entrelazarse de forma que uno de los incrementos se pierda (condición de carrera). Por ello, ese bloque debe definirse como Sección Crítica.

Condición de sincronización

Situación en la que un proceso debe detener su ejecución hasta que ocurra un determinado evento o cambio de estado provocado por otro proceso.

Ejemplo de tubería de procesamiento:

• Lector: Almacena imágenes capturadas en un buffer.
• Gestor: Lee del buffer, procesa la imagen y la pone en la cola de impresión.
• Impresor: Lee de la cola de impresión e imprime.

def lector():
    while True:
        imagen = captura_imagen()
        buffer.add(imagen)

def gestor():
    while True:
        imagen = buffer.get()
        imagen = procesar(imagen)
        cola_impresion.add(imagen)

def impresor():
    while True:
        imagen = cola_impresion.get()
        imprimir(imagen)

Problemas no resueltos en esta solución ingenua:

• ¿Qué ocurre si el lector intenta añadir una imagen pero el buffer está lleno?
• ¿Qué ocurre si el gestor intenta leer del buffer pero este está vacío?

Es necesario implementar condiciones de sincronización para bloquear a los procesos cuando las condiciones no se cumplen y despertarlos cuando se produce el evento esperado.

---

Propiedades de los programas concurrentes

Un programa concurrente correcto debe garantizar dos categorías de propiedades:

1. Propiedades de Seguridad (Safety): Garantizan que "nada malo va a ocurrir" durante la ejecución.
2. Propiedades de Vivacidad (Liveness): Garantizan que "algo bueno terminará ocurriendo" eventualmente.

Analogía: El Juego del Pañuelo

• Dos equipos (A y B) y un juez con un pañuelo.
• El juez dice un número; los jugadores asignados de ambos equipos corren hacia el pañuelo.
• El primero que lo coge debe volver a su base sin ser tocado.

Propiedades de seguridad

• Exclusión mutua: El recurso crítico solo puede ser adquirido por un único proceso/hilo a la vez (si ambos acceden a la vez, se rompe la integridad).
• Sincronización: Un proceso solo puede avanzar después de que ocurra un evento o cambio de estado provocado por otro proceso.

Propiedades de vivacidad

• Ausencia de Interbloqueo (Deadlock): Garantiza que el sistema siempre podrá realizar algún progreso global y no quedará atrapado indefinidamente en un estado donde ningún proceso pueda avanzar.

  Ejemplo: Si en el juego del pañuelo un jugador coge el pañuelo y se va a su casa, el juez esperaría eternamente a que le devuelvan el pañuelo y los demás a que diga número, congelando el juego.

• Ausencia de Interbloqueo activo (Livelock): Garantiza que el sistema realiza progreso real, evitando situaciones donde los procesos cambian de estado continuamente sin avanzar.

  Ejemplo: Dos jugadores que amagan continuamente con coger el pañuelo pero ninguno llega a cogerlo jamás.

• Ausencia de Inanición (Starvation): Garantiza que ningún proceso individual queda privado indefinidamente de la CPU o del recurso compartido. Requiere equidad (fairness).

  Ejemplo: Ocurriría si el juez jamás menciona el número de un determinado jugador.

Cuadro resumen: Defectos vs. Propiedades

Defecto / Problema	Tipo	Propiedad Violada	Definición breve
Condición de carrera (Race condition)	Safety	Exclusión mutua	Varios hilos modifican el mismo dato de forma no sincronizada
Interbloqueo (Deadlock)	Liveness	Ausencia de Interbloqueo	Dos o más procesos se bloquean esperando recursos cruzados
Interbloqueo activo (Livelock)	Liveness	Ausencia de Livelock	Procesos ejecutan operaciones y cambian de estado sin progresar
Inanición (Starvation)	Liveness	Ausencia de Inanición (Equidad)	Proceso relegado indefinidamente por falta de asignación de CPU

---

Ejemplo práctico de condición de carrera en Python

El siguiente script en Python lanza 5 hilos que compiten por incrementar una variable global x compartida. Al intercalar la lectura y la escritura entre hilos, se produce una condición de carrera que evidencia el indeterminismo (código disponible en carrera.py):

import threading
import time

x = 0
N_ITERACIONES = 1000
N_HILOS = 5

def incrementador():
    global x
    for _ in range(N_ITERACIONES):
        v = x
        time.sleep(0.000001)  # Forzar el cambio de contexto entre hilos
        x = v + 1

# Crear y lanzar 5 hilos concurrentes
hilos = [threading.Thread(target=incrementador) for _ in range(N_HILOS)]

for h in hilos:
    h.start()

for h in hilos:
    h.join()

print(f"Valor final de x: {x} (Esperado: {N_HILOS * N_ITERACIONES})")

Salidas reales de ejecuciones sucesivas en terminal:

$ python3 carrera.py
Valor final de x: 1003 (Esperado: 5000)

$ python3 carrera.py
Valor final de x: 1001 (Esperado: 5000)

$ python3 carrera.py
Valor final de x: 1007 (Esperado: 5000)

Ejercicio 2: Análisis de traza de ejecución

Consideremos la versión simplificada del programa anterior en la que dos hilos (incrementa5a e incrementa5b) realizan 5 incrementos sobre la variable global x:

x = 0

def incrementa5a():
    global x
    i = 0
    while i < 5:
        i = i + 1
        x = x + 1

def incrementa5b():
    global x
    i = 0
    while i < 5:
        i = i + 1
        x = x + 1

Cuestiones:

1. Plantea una traza de ejecución entrelazada que haga que x valga 5 al final de la ejecución de ambos hilos.
2. ¿Qué rango de valores posibles podría tener x al finalizar?
3. ¿De qué propiedades de las estudiadas adolece este programa?

Casos reales

Los errores de concurrencia (condiciones de carrera, interbloqueos y fallos de sincronización) son difíciles de detectar mediante pruebas tradicionales debido a su naturaleza no determinista y a la dependencia del entrelazado de instrucciones. A continuación se presentan algunos casos reales representativos:

• Therac-25 (1985–1987):
  • Una condición de carrera en la interfaz del acelerador de electrones permitía emitir el haz de radiación a máxima potencia sin colocar el filtro de tungsteno si la operadora modificaba los parámetros en menos de 8 segundos.
  • Provocó sobredosis masivas de radiación en varios pacientes.
  • Más información: https://es.wikipedia.org/wiki/Therac-25
• Gran apagón del noreste de EE.UU. y Canadá (2003):
  • Una condición de carrera en la adquisición de un cerrojo (mutex) provocó que el hilo de procesamiento de alarmas (XA/21) se congelara en silencio sin notificar la sobrecarga en las líneas de alta tensión.
  • Desencadenó una falla en cadena que afectó a 50 millones de personas.
  • Más información: https://es.wikipedia.org/wiki/Apag%C3%B3n_del_noreste_de_Estados_Unidos_de_2003
• Mars Pathfinder (1997):
  • Ocurrió un problema de inversión de prioridades (priority inversion) en el sistema operativo VxWorks: un hilo de baja prioridad retenía un recurso compartido y fue preentendido por hilos de prioridad media, impidiendo ejecutar al hilo de alta prioridad del bus de comunicaciones.
  • Provocó reinicios continuos de la sonda en Marte.
  • Más información: https://www.rapitasystems.com/blog/what-really-happened-to-the-mars-pathfinder-spacecraft
• Dirty COW (CVE-2016-5195):
  • Una condición de carrera en el subsistema de gestión de memoria virtual del kernel de Linux (en la operación Copy-on-Write) permitía a un usuario no privilegiado escribir en páginas de memoria de solo lectura.
  • Otorgaba privilegios de root en el sistema.
  • Más información: https://dirtycow.ninja/

---

Referencias y lecturas recomendadas

• Las transparencias son un resumen guía; debes ampliar y profundizar los conceptos mediante las lecturas recomendadas.
• Ficha docente oficial: Guía Docente de Programación Concurrente.
• Web oficial de la asignatura: DLSI - Programación Concurrente.