TEMA 1: INTRODUCCIÓN A LA

PROGRAMACIÓN CONCURRENTE

1. Conceptos básicos y Motivación

2. Modelo Abstracto y Consideraciones sobre el Hardware
3. Notaciones para expresar ejecución concurrente
4. Exclusión mutua y Sincronización
5. Propiedades de sistemas concurrentes. Nociones de verificación
 1. Conceptos básicos y Motivación
Conceptos basicos relacionados con la concurrencia

● Programa secuencial: Declaraciones de datos + Conjunto de

instrucciones sobre dichos datos que se deben ejecutar en secuencia.
● Programa concurrente: Conjunto de programas secuenciales ordinarios
que se pueden ejecutar lógicamente en paralelo.
● Proceso: Ejecución de un programa secuencial.
● Concurrencia: Describe el potencial para ejecución paralela, es decir, el
solapamiento real o virtual de varias actividades en el tiempo.
● Programación Concurrente (PC)
Conjunto de notaciones y técnicas de programación usadas para expresar
paralelismo potencial y resolver problemas de sincronización y
comunicación.
– Independiente de la implementación del paralelismo.
– Es una abstracción
 1. Conceptos básicos y Motivación
Programación Paralela, distribuida y de tiempo real

● Programación paralela
Principal objetivo: acelerar resolución de
problemas concretos aprovechando capacidad
harsware paralelo.
● Programación distribuida
Principal objetivo: hacer que varios componentes
software localizados en diferentes ordenadores
trabajen juntos.

● Programación de tiempo real: SISTEMA

Consignas DE Visualización

programación de sistemas reactivos (funcionan CONTROL

datos

continuamente, recibiendo entradas y enviando

salidas a/desde componentes hardware) que Medidas Acciones

trabajan bajo restricciones de respuesta temporal

muy estrictas (sistemas de tiempo real). SISTEMA
CONTROLADO

ENTORNO FÍSICO
 1. Conceptos básicos y Motivación
Motivación

Programación concurrente es más compleja que la progr. secuencial.

¿Por qué es necesario usar la Programación Concurrente?

Básicamente hay dos motivos para el desarrollo de la programación

concurrente:

 Mejora de la eficiencia

 Mejoras en la calidad
 1. Conceptos básicos y Motivación
Mejora de la eficiencia

● Mejora el aprovechamiento de los recursos hardware existentes.

● Sistemas monoprocesador:
– Cuando la tarea que tiene el control dela CPU necesita realizar
una E/S cede el control a otra, evitando espera ociosa CPU.
– Permite que varios usuarios usen el sistema de forma interactiva
(actuales sistemas multiusuario).

● Sistemas multiprocesador (multicore incluidos):

– Reparto de las tareas entre los procesadores permite reducir
tiempo de ejecución (procesamiento paralelo).
– Aceleración aplicaciones costosas computacionalmente.
 1. Conceptos básicos y Motivación
Mejora de la calidad

Muchos programas se modelan mejor en términos de varios procesos

secuenciales ejecutándose concurrentemente que como un único programa
secuencial.
Ejemplos:
– Servidor web para reserva de vuelos: Más natural, considerar cada
petición de usuario como un proceso e implementar políticas para
evitar situaciones conflictivas (superar el límite de reservas en un
vuelo).

– Simulador del comportamiento de una gasolinera: Más sencillo

considerar surtidores, clientes, vehículos y empleados como procesos
que cambian de estado al participar en actividades comunes, que
considerarlos entidades de un único programa secuencial.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Modelos de arquitecturas

Mecanismos de implementación de la concurrencia

● Dependen fuertemente de la arquitectura.
● Consideran una máquina virtual que representa un sistema (multiprocesador o sistema
distribuido), proporcionando base homogénea para ejecución de los procesos concurrentes.
● El tipo de paralelismo afecta a la eficiencia pero no a la corrección.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Concurrencia en Sistemas Monoprocesador

● Multiprogramación: El sistema operativo gestiona cómo múltiples

procesos se reparten los ciclos de CPU.
● Mejor aprovechamiento CPU.
● Servicio interactivo a varios usuarios.
● Permite soluciones de diseño concurrentes.
● Sincronización y comunicación mediante variables compartidas.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Concurrencia en Multiprocesadores de mem. compartida

● Los procesadores pueden compartir o no físicamente la misma memoria,

pero comparten un espacio de direcciones compartido.
● La interacción entre los procesos se puede implementar mediante
variables alojadas en direccciones del espacio compartido: variables
compartidas.
● Ejemplo: PCs con procesadores muticore.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Concurrencia en Sistemas Distribuidos

● Sin memoria común: cada procesador  espacio de direcciones privado.

● Paso de mensajes: procesadores interactúan transfiriéndose datos a
través de una red de interconexión.
● Programación distribuida: además concurrencia, trata otros problemas:
tratamiento fallos, transparencia, heterogeneidad, etc.
● Ejemplos: Clusters de ordenadores, internet, intranet.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Sentencia Atómica

Sentencia atómica (indivisible) de un programa concurrente

Sentencia o instrucción de un proceso que siempre se ejecuta de
principio a fin sin verse afectado su efecto por otras sentencias
en ejecución de otros procesos del programa.
● Efecto en estado de ejecución cuando acaba instrucción no
dependerá de cómo se estén ejecutando otras instrucciones.
● Estado de ejecución de un programa concurrente = {Valores de
variables y registros de todos los procesos}.

● Ejemplos de instrucciones atómicas: instrucciones máquina

del repertorio de un procesador:
➢ Load X, R Add R, v Store R, X
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Ejemplo de Sentencia Atómica

En una sentencia atómica, a partir del estado al inicio, el estado

justo al acabar la instrucción está determinado como función
del estado al inicio.

Estado inicio: {r1=1 ^ r2=2 ^ x=3 }

Store r1 , x Store r2 , x Load x , r2

{x=1} {x=2} {r2=3}

 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Sentencias NO Atómicas

La mayoría de las sentencias en lenguajes de alto nivel son

típicamente no atómicas

1. Load x, r

x := x+1 ; 2. Add r,1

3. Store r , x

El valor de x justo al acabar depende de que haya o no otras

sentencias ejecutándose y escribiendo simultáneamente sobre x.

Indeterminación: no se puede predecir estado final desde inicial.

 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Modelo basado en la Interfoliación de sentencias atómicas

Sea C un programa concurrente: C = PA || PB

● MODELO EJECUCIÓN CONCURRENTE: La ejecución de C
puede dar lugar a cualquiera de las posibles interfoliaciones
de sentencias atómicas de PA y PB que mantenga
consistencia secuencial.

Ordenación sentencias atómicas se establece en función del

instante en el que acaban (cuando tienen efecto).
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Modelo de interfoliación como Abstracción

Modelo basado en estudio de las posibles secuencias de

interfoliación  Abstracción
● Considera solo características relevantes que determinan resultado
ejecución.
● Simplifica análisis y diseño programas concurrentes.
● Ignora detalles no relevantes:
– Áreas de memoria asignadas procesos.
– Registros usados.
– Costo cambios de contexto.
– Política asignación de CPU. de S.O.
– etc.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Independencia del entorno de ejecución

El entrelazamiento preserva la consistencia

● Resultado de instrucción individual sobre un dato no depende circunstancias
ejecución.
{r1=1 ^ r2=2} {r1=1 ^ r2=2}

Store r1 , M Store r2 , M Store r1 , M Store r2 , M

Resultados: M=1 ó M=2 M=3

● En caso contrario, sería imposible razonar acerca de la corrección programas
concurrentes.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Hipótesis del Progreso Finito (1)

Hipótesis del Progreso Finito

No se puede hacer ninguna suposición acerca de las velocidades
absolutas/relativas de ejecución de los procesos, salvo que es mayor
que cero
● Un programa concurrente se entiende en base a sus componentes (procesos)
y sus interacciones, sin tener en cuenta el entorno de ejecución.
● Ejemplo: Un disco es más lento que una CPU pero no se debería asumir eso
al diseñar un programa concurrente.

● Si se hicieran suposiciones temporales:

– Difícil detectar y corregir fallos.
– Corrección dependería de configuración de ejecución, que puede
cambiar.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Hipótesis del Progreso Finito (2)

Progreso finito  Velocidad de ejecución cada proceso 0

2 Consecuencias:
● Punto de vista global
Durante ejecución programa conc., en cualquier momento existirá al
menos 1 proceso preparado (eventualmente se permitirá la ejecución
de algún proceso).

● Punto de vista local

Cuando un proceso concreto de un programa comienza ejecución de
una sentencia, la completará en un intervalo de tiempo finito.
 2. Modelo Abstracto y Consideraciones
sobre el Hardware
Estados e Historias de ejecución

Estado de un programa concurrente

Valores de las variables del programa en un momento dado.
Tanto variables declaradas explícitamente como variables con información de
estado oculta (contador del programa, registros, ...).

● Un programa concurrente comienza su ejecución en un estado inicial S0.

● Los procesos van modificando el estado conforme van ejecutando sus
sentencias atómicas (producen transiciones entre dos estados).

Historia o traza de un programa concurrente

Secuencia de estados S0  S1  . . .  Sn , producida por una secuencia
concreta de interfoliación.
 3. Notaciones para expresar ejecución
concurrente

● Propuestas iniciales: no separan Definición procesos de su sincronización.

● Propuestas posteriores: separan ambos conceptos e imponen estructura.
● Declaración de procesos: rutinas específicas de programacón concurrente
⇒ Estructura del programa concurrente más clara.
● Sistemas Estáticos: Número de procesos
fijado en el código fuente. Se activan al lanzar el P0 P1 P2 P3
programa.
– Message Passing Interface (MPI-1).

● Sistemas Dinámicos: Procesos/hebras se

pueden activar/desactivar en cualquier momento
ejecución. P0 P1 P2 P3
– OpenMP, PThreads, MPI-2.
 3. Notaciones para expresar ejecución
concurrente
Grafo de Sincronización

● Grafo de Sincronización :Grafo Dirigido Acíclico (DAG) donde cada nodo

representa una secuencia de sentencias del programa (actividad).

● Arista desde A hacia B: B no puede

comenzar su ejecución hasta que A
haya finalizado.

● Muestra restricciones de precedencia

entre actividades.
3. Notaciones para expresar ejecución
concurrente
Definición estática de Procesos
Definición Procesos
Vectores de Procesos
individuales
 3. Notaciones para expresar ejecución
concurrente
Creación no estructurada: fork-join

● Fork A: Especifica que la rutina A puede comenzar su ejecución, al mismo

tiempo que comienza la sentencia siguiente (bifurcación).
● Join B: Espera la terminación de la rutina B, antes de comenzar la sentencia
siguiente (unión).

● Ventajas: práctica y potente, creación dinámica.

● Inconvenientes: no estructuración, difícil comprensión de los programas.
 3. Notaciones para expresar ejecución
concurrente
Creación estructurada: cobegin-coend

Las sentencias en un bloque delimitado por cobegin-coend comienzan su

ejecución todas ellas a la vez:
– En coend se espera a que se terminen todas las sentencias.
– Hace explícito qué rutinas van a ejecutarse concurrentemente.

● Ventaja: impone estructura: 1 única entrada y 1 única salida ⇒ Más fácil de entender.
● Inconveniente: menor potencia expresiva que fork-join.
 4. Exclusión mutua y Sincronización

Modelo abstracto  Entrelazamiento completamente arbitrario de sus

secuencias de instrucciones.
Programa Conc: Algunos de los posibles entrelazamientos no son válidos.
● Condición de sincronización: ● Exclusión mutua (Caso particular):
Restricción sobre el orden en el Secuencias finitas de instrucciones que
que se pueden mezclar las deben ejecutarse de principio a fin por un
instrucciones de distintos único proceso, sin que a la vez otro
procesos. proceso las esté ejecutando también.

P1 P2 P3
P1 P2 P3 P4

Espera
 4. Exclusión mutua y Sincronización
Exclusión mutua

Restricción de sincronización: Una o varias secuencias de instrucciones

consecutivas del texto de uno o varios procesos.
● Sección crítica (SC): Secuencias de instrucciones de diferentes procesos que
no pueden entrelazar su ejecución.
● Exclusión mutua (EM): En cada instante de tiempo, debe haber como mucho
un proceso ejecutando cualquier instrucción de la sección crítica.
● Cada secuencia de instrucciones de la SC se ejecuta como mucho por un
proceso de principio a fin, sin que simultáneamente otros procesos ejecuten
ninguna instrucción de su SC.
Ejemplos de Secuencias:
P1 P2 P3 SC de P2
I1 J1 L1 - I1, J1, I2, J2, L1,L2, L3, J3, I3, I4, L4. CORRECTA

I2 J2 L2 - I1, I2, I3, J1, … ERRÓNEA!

SC I3 J3 L3
de
P1 I4 J4 L4 SC de P3
 4. Exclusión mutua y Sincronización
Ejemplos de Exclusión mutua

1. Procesos con memoria compartida que acceden para leer y modificar

variables o estructuras de datos comunes usando operaciones no atómicas
(varias instrucciones máquina)
2. Envío de datos a dispositivos que no se pueden compartir (pantalla, …)
3. Recepción de datos desde dispositivos.
● Ejemplo sencillo: Sección crítica → Secuencias de instrucciones máquina
que se derivan de operación incremento sobre variable entera (x) compartida
x:=x+1.
 4. Exclusión mutua y Sincronización
Ejemplo de Exclusión mutua: x:=x+1

- Suponemos que x=0 inicialmente

- Cada proceso (P0 y P1) tiene su propio registro (r0 y r1)
- Al final x podría valer 1 ó 2 si no se verifica la EM.
 4. Exclusión mutua y Sincronización
Instrucciones compuestas atómicas

En pseudo-código, podemos escribir sentencias compuestas indicando que se

deben de ejecutar de forma atómica, usando los caracteres < y >.

Al acabar, x puede tener un valor Aquí, x siempre finaliza con

cualquiera del conjunto {−1, 0, 1 } el valor 0
 4. Exclusión mutua y Sincronización
Condición de Sincronización. Ejemplo

Condición de sincronización: no son correctas todas las posibles

interfoliaciones de las secuencias de instrucciones atómicas de los procesos.
Típicamente, en un punto de ejecución, uno o varios procesos deben esperar
a que se cumpla una condición global (depende de varios procesos)
Ejemplo: Sincronización Productor-Consumidor
 4. Exclusión mutua y Sincronización
Condición de Sincronización. Ejemplo

Los procesos solo funcionan como se espera si el orden en el que se

entremezclan las sentencias elementales E y L es: E, L, E, L, E, L, . . ..
(1) Consumidor no lee hasta que Productor escriba nuevo valor en x (cada valor producido
es usado una sola vez).
(2) Productor no escribe nuevo valor hasta que Consumidor lea el último almacenado en x
(ningún valor producido se pierde).

L, E, L, E, . . .incorrecta: lectura de
valor indeterminado para x.

E, L, E, E, L, . . . incorrecta: 2
escrituras sin lectura intermedia.

E, L, L, E, L, . . . incorrecta: 2
lecturas del mismo valor.
 5. Propiedades Sistemas Concurrentes
Seguridad y Vivacidad

Propiedad de un programa concurrente: Atributo del programa que es cierto

para todas las posibles secuencias de interfoliación (historias del programa).Hay
2 tipos: seguridad (safety) y vivacidad (liveness).

Propiedades de Seguridad Propiedades de Vivacidad

Condiciones que deben cumplirse Condiciones que deben cumplirse
Siempre: Eventualmente:
“Nunca pasará nada malo” “En algún momento pasará algo bueno”
Requeridas en especificaciones Requeridas en especificaciones
estáticas del programa. dinámicas del programa.
Fáciles de demostrar y para cumplirlas Difíciles de demostrar
se suelen restringir interfoliaciones.
 5. Propiedades Sistemas Concurrentes
Ejemplos de propiedades

Ejemplos Prop. de Seguridad Ejemplos Prop, de Vivacidad

(1) Exclusión mutua: 2 procesos nunca (1) Ausencia de inanición (Starvation-

entrelazan ciertas subsecuencias de freedom): Un proceso o grupo de
operaciones. procesos no puede ser indefinidamente
pospuesto. En algún momento, podrá
(2) Ausencia Interbloqueo (Deadlock- avanzar.
freedom): Nunca ocurrirá que los
procesos se encuentren esperando algo (2) Equidad (Fairness): Un proceso que
que nunca sucederá. desee progresar debe hacerlo con
justicia relativa con respecto a los
(3) Propiedad seguridad en Productor- demás. Más ligado a la implementación
Consumidor: Consumidor debe y a veces incumplida: existen distintos
consumir todos los datos producidos por grados.
Productor en el mismo orden.
 5. Propiedades Sistemas Concurrentes
Verificación de programas concurrentes

¿ Cómo demostrar que un programa cumple una determinada

propiedad ?
 Posibilidad: realizar diferentes ejecuciones del programa y comprobar que se
verifica la propiedad.
 Problema: Sólo considera número limitado de historias ejecución y podría no
mostrar casos indeseables.
 Ejemplo: Comprobar que el proceso P produce al final x = 3:

Varias historias llevan a

x=1 ó x=2, pero
podrían no darse.
 5. Propiedades Sistemas Concurrentes
Enfoque operacional (análisis exhaustivo)

Enfoque operacional: Análisis exhaustivo de casos. Se chequea la

corrección de todas las posibles historias.
 Utilidad muy limitada cuando se aplica a programas concurrentes complejos
 Número de interfoliaciones crece exponencialmente con número de
instrucciones.
 Para programa P (2 procesos, 3 sentencias atómicas por proceso) habría
que estudiar 20 historias diferentes.
 5. Propiedades Sistemas Concurrentes
Verificación. Enfoque axiomático

 Se define un sistema lógico formal que permite establecer propiedades de

programas en base a axiomas y reglas de inferencia.
 Se usan fórmulas lógicas (asertos) para caracterizar un conjunto de
estados.
 Sentencias atómicas → transformadores de predicados (asertos).
 Teoremas en la lógica:

{ P} S { Q }
“Si la ejecución de S empieza en algún estado en el que es verdadero el
predicado P (precondición), entonces el predicado Q (poscondición) será
verdadero en el estado resultante”

● Menor Costo computacional: Costo de la Prueba automática de corrección

es proporcional al número de sentencias atómicas del programa.
 5. Propiedades Sistemas Concurrentes
Invariante global

 Invariante global: Predicado que referencia variables globales

 Cierto en el estado inicial de cada proceso
 Se mantiene cierto ante cualquier asignación dentro procesos.

 Ejemplo: Productor-Consumidor, Invariante global sería:

consumidos ≤ producidos ≤ consumidos + 1