Programación concurrente y computación intensiva

Sección 1: Introducción a la concurrencia

• Un programa secuencial es un conjunto de declaraciones de datos e instrucciones que se ejecutan en secuencia.
• Un programa concurrente es un conjunto de programas secuenciales que pueden ejecutarse lógicamente en paralelo.
• Proceso se refiere a la ejecución de un programa secuencial.
• Concurrencia describe el potencial de ejecución paralela permitiendo el traslape real o virtual de actividades en el tiempo.
• Programación concurrente (PC) abarca las notaciones y técnicas usadas para expresar el paralelismo y resolver la sincronización y comunicación.
• PC es una abstracción independiente de la implementación del paralelismo.

Programación paralela, distribuida y de tiempo real

• La programación paralela busca acelerar la resolución de problemas mediante el uso de la capacidad de procesamiento en paralelo del hardware actual.
• La programación distribuida tiene como objetivo que varios componentes de software en diferentes ordenadores trabajen juntos.
• La programación de tiempo real se enfoca en sistemas que operan continuamente, con estrictas restricciones temporales en la respuesta.

Motivación de la programación concurrente

• La programación concurrente es más compleja que la secuencial, ofreciéndo mejoras en eficiencia y calidad.
• Permite aprovechar mejor los recursos hardware existentes.
• En sistemas monoprocesador, evita la espera ociosa del procesador al permitir que otra tarea tome el control cuando la tarea actual necesita realizar una operación de E/S.
• Facilita el uso interactivo del sistema por varios usuarios gracias a los sistemas operativos multiusuario.
• En sistemas multiprocesador, permite repartir tareas entre procesadores, reduciendo el tiempo de ejecución y acelerando cálculos numéricos complejos.

Mejora de la calidad

• Permite entender y modelar programas en términos de procesos secuenciales que se ejecutan concurrentemente.
• Por ejemplo, un servidor web para reserva de vuelos puede tratar cada petición de usuario como un proceso aparte facilitando la implementación de políticas para evitar conflictos
• Un simulador del comportamiento de una gasolinera puede considerar los surtidores, clientes y empleados como partes separadas

Programas de cálculo intensivo

• Actualmente existen múltiples aplicaciones de cálculo intensivo que se benefician de la programación concurrente y distribuida.
• En el cálculo intensivo en CPUs múltiples, un programa concurrente usa varias CPUs de forma coordinada, a diferencia de un programa secuencial.
• El cálculo intensivo en GPUs, el uso de la programación concurrente permite aprovechar el hardware con unidades de cálculo flotante.
• Sistemas distribuidos de cálculo permite cálculos intensivos en varios ordenadores conectados a una red.

Aplicaciones del cálculo intensivo

• La programación concurrente es una herramienta esencial en áreas que requieren cálculo intensivo.
• Se usa en videojuegos, realidad virtual y aumentada para visualización, simulación física e I.A. de personajes.
• Se usa en la inteligencia artificial para el entrenamiento de redes neuronales y sistemas de IA.
• Se usa en animación y rendering para la creación de efectos especiales en películas.
• Se usa en simulación de sistemas físicos como predicción meteorológica o simulación de estructuras.
• También se usa en el cálculo de estructura moleculares

Programación Web o en Internet

• La programación distribuida es fundamental para las aplicaciones web, donde los procesos se comunican mediante el paso de mensajes.
• La comunicación distribuida sigue el modelo cliente-servidor, donde las modalidades de envío de mensajes varia.
• La programación asíncrona en clientes web permite simultanear el procesamiento, las transferencias de datos y la interacción con el usuario.
• Usa concurrentemente varias CPUs en un cliente Web coordinando la comunicación mediante el paso de mensajes.

Sección 2: Modelo abstracto y consideraciones sobre el hardware para programación concurrente

• Los mecanismos de implementación de la Concurrencia dependen fuertemente de la arquitectura.
• Se considera una máquina virtual con una base homogénea para la ejecución de procesos concurrentes en un sistema (multiprocesador o distribuido).
• El tipo de paralelismo afecta la eficiencia sin afectar la corrección.

Concurrencia en sistemas monoprocesador

• La multiprogramación permite que el sistema operativo reparta los ciclos de la CPU entre los procesos.
• Se logra un mejor aprovechamiento de la CPU, un servicio interactivo a varios usuarios y la utilización de soluciones de diseño concurrentes.
• La sincronización y comunicación se realizan mediante variables compartidas en la memoria.

Concurrencia en multiprocesadores de memoria compartida

• Los procesadores pueden compartir físicamente la memoria o un espacio de direcciones compartido.
• En estos espacios se usan variables compartidas para la comunicación entre varios procesos.
• Un ejemplo son las PCs con procesadores multicore.

Concurrencia en sistemas distribuidos

• En sistemas distribuidos cada procesador tiene un espacio de direcciones privado, sin embargo, la comunicación se hace a través de la red por el paso de mensajes
• La programación distribuida además de tratar la concurrencia debe tomar en cuenta los fallos, la transparencia y la heterogeneidad entre otros aspectos.
• Los Clusters de ordenadores, el internet y la intranet son ejemplos comunes

Modelo abstracto de un programa secuencial

• Un programa secuencial incluye declaraciones de variables y sentencias que deben ejecutarse en secuencia.
• "Secuencial" significa ordenada en el tiempo: hasta que no acaba la ejecución de una sentencia, no comienza la siguiente.

Sentencias, estados y procesos sencuenciales.

• Una sentencia modifica el valor de una o varias variable del programa, al ejecutarse.
• Un estado es el conjunto de valores de las variables del programa, en un instante determinado
• Un proceso secuencial es la ejecución de un programa secuencial en un tiempo definido.
• En programa cambia las variables desde un estado inicial hasta un estado final.

Accesos a variables en una sentencia

• Un acceso a una variable es una operación realizada por el procesador que lee o escribe una variable durante la ejecución de un programa.
• Se consideran accesos a variables de tipos primitivos como lógicos, enteros, carácter o flotantes.
• Cuando se ejecuta una sentencia, se producen uno o varios accesos de forma secuencial.
• Las sentencias más simples producen un único acceso de escritura, como x:=34
• Las asignaciones más complejas suelen tener más de un acceso.

Variables accedidas por una sentencia

• V(S) es el conjunto de variables que se leen o escriben al ejecutar una sentencia S.
• La sentencia x:=x+1 accede a la variable x (lee y escribe).
• La sentencia y:=2*y+x+1 accede a las variables x e y (lee ambas y escribe y).
• La sentencia print(x,y) accede a las variables x e y (las lee).

Traza y ejemplo

• La historia o traza de una ejecución de un proceso secuencial es la secuencia de sus estados.
• Para evaluar el comportamiento, se utiliza un pseudo-código donde se distinguen las sentencias, que tienen fondo gris, y los estados, con fondo rojo.

Tradución de expresiones aritméticas. Registros.

• En el pseudo-código se usan expresiones aritméticas enteras, flotantes o lógicas.
• Para poder evaluarlas, una CPU necesita operandos aritmético-lógicos (+,-,*, and, or, etc.) guardados en los registros del procesador.
• Cada proceso secuencial cuenta con variables implícitas llamadas registros y se usan evaluar expresiones r0, r1, r2, etc.
• Por cada referencia a una variable en una expresión, se debe leer y escribir en un registro.
• Los valores de los registros forman parte del estado del proceso secuencial.

Traducción de expresiones aritméticas. Registros.

• La instrucción x:=x+1 se descompone en r0 := x (lectura de x y escritura en r0) y x := r0+1 (lectura de r0, cálculo y escritura en x).
• En expresiones complejas se necesitan más registros
• En la declaración y:=2*y+x+1 hace falta usar 2 registros

Sentencias compuestas y traza

• La traza puede escribirse en forma de tabla donde se muestra el estado inicial, la sentencia y el estado después de ejecutarse.

El proceso secuencial como una secuencia de acceso

• La ejecución de un proceso secuencial se puede modelar como una secuencia finita y ordenada de accesos a las variables iniciada en el estado inicial.
• Se asume que esta secuencia es finita porque cada proceso solo tiene un estado final, no entra en un bucle infinito.
• Este modelo sirve para analizar el comportamiento de programas concurrentes con memoria compartida

Modelo abstracto de ejecución concurrente

• Un programa concurrente incluye declaraciones de variables (compartidas) y sentencias que determinan cómo dos o más procesos secuenciales se pueden ejecutar concurrentemente.
• "Concurrentemente" quiere decir que la ejecución de las sentencias puede solaparse en el tiempo.
• Los procesos acceden (leen o escriben) las variables compartidas.
• Cada proceso secuencial puede tener sus propias variables locales y sus propios registros (no accesibles por otros procesos).
• Existen dos procesos secuenciales: NomUno y NomDos, y ambos acceden a las variables compartidas x e y.
• Antes de empezar a ejecutar los porcesos NomUno y NomDos, hay que inicializar las variables compartidas

Variables locales y registros

• Cada proceso secuencial puede declarar variables locales, accesibles sólo dentro del proceso.
• Dos variables locales de dos procesos secuenciales distintos podrían tener el mismo nombre.
• Cada proceso secuencial usa sus propios registros.

Notación abreviada para ejecución secuencial o concurrente.

• SA; SB denota la sentencia que primero ejecuta SA completa y luego SB completa (secuencialmente).
• SA||SB denota la sentencia que ejecuta SA y SB de forma simultánea (concurrentemente) y termina cuando ambas terminam
• La sentencia SA||SB es equivalente a SB||SA, pero SA; SB no es igual a SB; SA.

Accesos a variables compartidas: consistencia secuencial

• Es necesario que la propiedad de la consistencia secuencial estricta se cumpla simpre
  • Todos los accesos a variables se realizan en un orden determinado, sin solapamientose
  • Se dice entonces que la totalidad de los accesos realizados desde el inico hasta el final ocurre en un orden determinado
  • Los accesos se pueden mezclar, sin que se empiecen los accesos hasta que no hayan acabado otros
  • El orden determinado puede cambia en cada ejecución.
  • los accesos realizados siempre debe ejecutarse en el orden que tienen en el programa sin importar la interfoliación

Estados de un programa concurrente

• Un estado de un programa concurrente es el conjunto de valores de las variables (compartidas
• Se puede hablar de las trazas de un código concurrente, donde se pueden consultar los accesos de las variables compartidas

Ejecución de sentencias de forma concurrente

• La ejecución de una sentencia S₁, puede interactuar con otra sentencia S₂ que acceda a las mismas variables compartidas
• Si ocurre el resultado final depende de los datos, el orden en que las sentencias están interfolliadas y también los datos de entrada
• Es esencial tener esto en cuenta para le diseño de programas.

Ejemplo de ejecución concurrente de sentencias

• Dos procesos secuenciales comparten x, si tienen el mismo registros y e ejecutan a la vez la sentencia X := X + 1 con X = 1, los procesos pueden acceder al mismo tiempo a los registreos por lo que puede acabar siendo diferente a la salida correcta.

Sentencias atómicas y no atómicas (1/2)

• Para facilitar el análisis y diseño de programas concurrentes, definimos los estados atómicos
• Una sentencia S se considera atómica si no produce estados intermedios en las variables
• Hay un estado intermedio si no es ni el inicial ni el final en los accesos
• Un estado es accesible si contiene valores que se pueden Leer o Escribir por otros procesos distinto P.

Sentencias atómicas y no atómicas (2/2)

• Si tenemos P donde la ejecución atómica de S, otros procesoso no pueden leer o modificar, ni leer las variables durante la ejecución. solo los cambios de valores de las variables.
• Las declaraciones se ejecutan para la variable atómica solo una unica vez para el resto de procesos

Ejemplos de sentencias atómicas

• Sentencias que no producen estados intermedios y que hacen un único acceso a una Variable Compartida.
• Lectrura y escritura de forma exclusiva en un variable local
• Esto se traduce en código fuente a una única intrucción, nos es irrelevante si el la concurrencia es atómica, abstraemos los detalles para poder usar las intrucciones de máquina
• Otra variables atómicas, son las Variables con mucho accesos, pero solo si se usas en una sola variable compartida.
• Tambien opearaciones compuestas y o bloques con mucha operaicón pueden ser atomicas si cambian los datos de entrada y salida.

Ejemplos de sentencias no atómicas

• Cuando existen estados intermedios

Ejemplo de solapamiento en estructuras atómicas.(1/2)

• Para asegurar el comportamiento del programa a traves de secuencias se usan variable Locales que en conjunto valan cero.

Ejemplo de solapamiento de instrucciones atómicas (2/2)

• Si en la siguiente diapositiva vemos dos trazas que dan lugar a los dos valores de b posibles. Escribe, el resto de trazas y verifica que el valor final solo depende del orden de los accesos a x

Solapamiento de sentencias atómicas

Puesto que S0 y S1 son atómicas, la ejecución concurrente de ambas es equivalente a la secuencial, es decir el estado posterior siempre será uno cualquiera de estos dos: Estado resultado de ejecutar S0 completa, seguida de S1. Estado resultado de ejecutar S1 completa, seguida de S0. Es decir: si S0 y S1 son ambas atómicas, entonces cada vez que se ejecuta la sentencia S0||S1 el resultado será equivalente a ejecu- tar S0; S1 o bien a ejecutar S1; S0. Por tanto, en general, podemos analizar el comportamiento de un programa concurrente suponiendo que las instrucciones atómicas no se solapan (aunque realmente sí lo hagan).

Interfoliación de sentencias atómicas

uno ejecuta la secuencia de instr. atómicas A1 A2 A3 A4 A5, y otro ejecuta la secuencia de instr. atómicas B1 B2 B3 B4 B5. Entonces, al ejecutar el programa concurrente C, puede ocurrir cualquier interfoliación de sentencias atómicas que respete el orden dentro de cada proceso secuencial.

El número de posibles interfoliaciones

El proceso P₁ ejecuta n₁ instr. atómicas, y el proc. P₂ ejecuta n2: Hay tantas posibles interfoliaciones de P₁ y P₂ como posibles subconjuntos (de n₁ elementos) del conjunto {1,2,..., n₁ + n2} (es igual si consideramos subconjuntos de n₂ elementos). Luego el núm. de interfoliaciones es este coeficiente binomial: n1 + n2 (n1) = (n1+n2)! /n1!.n2! Si tenemos k procesos se usa el coeficiente multinomial: (n₁+n₂+...+nk / n₁, n₂,..., nk) = (n+n: +...+ nk)! / n! n₂!... nu! Por ejemplo, para n₁ = 10 y n₂ = 15 hay 3.286.760 interf. Conclusión: el número de posibles interfoliaciones es muy ele- vado incluso para programas cortos

Abstracción

Se consideran exclusivamente las características relevantes que determinan el resultado del cálculo Esto permite simplificar el análisis y diseño de los programas concurrentes. Se ignoran los detalles no relevantes para el resultado, por ejemplo: Las áreas de memoria asignadas a los procesos. Los registros particulares que están usando. El costo de los cambios de contexto entre procesos. La política del S.O. relativa a asignación de CPU. Las diferencias entre entornos multiprocesador o monoprocesador.

Velocidad de ejecución. 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 normalmente más lento que una CPU, pero no podemos suponer que siempre es así para diseñar un programa. Si se hicieran suposiciones temporales: Sería difícil detectar y corregir fallos La corrección dependería de la configuración de ejecución, que puede cambiar

Hipótesis del progreso finito

Si se cumple la hipótesis, la velocidad de ejecución de cada proceso será no nula, lo cual tiene estas dos consecuencias:

• Punto de vista global Durante la ejecución de un programa concurrente, en cualquier momento existirá al menos 1 proceso preparado, es decir, eventualmente se permitirá la ejecución de algún proceso.
• Punto de vista local Cuando un proceso concreto de un programa concurrente co-mienza la ejecución de una sentencia, completará la ejecución de la sentencia en un intervalo de tiempo finito.
• Sistemas Concurrentes y Distribuidos- Curso 2024-25

Notación para expresar ejecución concurrente. Tipos.

• Usaremos una notación (la llamamos pseudo-código) para expresar el código y la sincronización de los distintos procesos secuenciales
• Distinguimos dos tipos de sistemas concurrentes en función de las posibilidades para especificar cuáles son sus procesos:
• Sistemas Estáticos
  • Número de procesos fijado en el fuente del programa.
  • Los procesos se activan al lanzar el programa.
  • Ejemplo: Message Passing Interface (MPI-1).
• Sistemas Dinámicos
  • Número variable de procesos/hebras que se pueden activar en cualquier momento de la ejecución.
  • Ejemplos: OpenMP, PThreads, Java Threads, MPI-2.

Grafo de Sincronización

• Un Grafo de Sincronización es un Grafo Dirigido Acíclico (DAG) donde cada nodo representa una secuencia de sentencias del programa

Definición estática de procesos

• El número de procesos (arbitrario) y el código que ejecutan no cambian entre ejecuciones.
• Cada proceso se asocia con su identificador y su código mediante la palabra clave process.

Definición estática de vectores de procesos

• Se pueden usar definiciones estáticas de grupos de procesos similares que sólo se diferencian en el valor de una constante
• la estructura de los vectores de procesos hace uso del nombre de los procesos que hay en la ejecución.
• Cobegin - Coend: Es una herramienta para la creación de procesos que hace uso de un principio-fin para procesos

Notación para atómicidad

Sea una variable , entonces <s> es otra notación para la misma variable que sea atómica para su definición

• Hace que en la memoria se reserven las sentencias para una operación atómica

Sección 3: Exclusión mutua y sincronización

• Al ser operaciones atómicas se permite coordinaciones.

Condición de sincronización. Exclusión Mutua

• Condición de Sincronización Imponer una restrictiva o condición sobre el orden de interlevar las instrucciones atómicas de distintos procesos.
• la exclusión mutua son condiciones/instrucciones que deben ejecutarse en función a como fue programada - la coordinación se debe realizar si se desea que la condición se realice de la manera en la que fue programad

Exclusión Mútual y Sincronización

• En principio es impredecible la interfolliasión y el tiempo en las secuencias
• Sinc embargo los procesos secuenciales no son completamente independientes, debiendo llevar cierta coordinación sino se necesitará la secuencialidad.

Exclusión Mutua

• Una restricción sobre la operaciones consecutivas en el texto de 1 o varios procesos
• Se crea una Sección Crítica(SC) y sobre esta sección se realiza exclusión mutua.

Ejemplos de exclusión multiple

• Actualizaciones de datos en meoria compartida para evitar problemas de concurrencia

Un ejemplo sencillo de exclusión mutua

• Con la exclusión mutua se permite crear operaciones aritmeticas elementales sin generar redundanci

Tradicción y ejecución de asingaciones

• se declaran las variables/registros de dos procesos/variables para que no se sobreescriban al mismo tiempo

Posibles Secuencias de Instrucciones

• Existen diversas trazan pero la función valida debe asegurar la condicion sincronizada

Para garantizar atomicidad

La sentencia ` es de nuevo de un tipo nuevo de sentencia atómica, ya que puede hacer más de un acceso al mismo tiempo