Introducción

Concepto de programación concurrente

  • Avances en HARDWARE (procesadores específicos de E/S)
  • Nuevos SO que optimizan 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, un solo procesador atendía multiples usuarios

  • Hitos:

    • Aparición del concepto de thread o hilo de ejecución, que permite que los programas se ejecuten más rápido que los que utilizan el concepto de proceso
    • 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, chats, etc…, están programados usando técnicas de programación concurrente

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

  • Si sustituimos suceso por proceso ya tenemos la definición de concurrencia en computación

  • Programa ≠ proceso

  • Programa:

    • Conjunto de instrucciones
    • Estático (para que pueda hacer algo hay que ponerlo en ejecución)
    • Secuencia de líneas de código que dicen qué hacer con un conjunto de datos
    • Comparable con una clase en POO

  • Proceso:

    • Programa en ejecución (definición incompleta)
    • Dinámico
    • Representado por un valor de contador de programa, el contenido de los registros del procesador, una pila y una sección de datos que contiene variables globales.
    • Se puede comparar con un objeto en POO
    • Puede haber múltiples procesos que corresponden al mismo programa igual que pasa en POO muchos objetos que provienen de una misma clase.

  • POO: Una sola clase y muchos objetos instancias de la clase

  • PC: Un solo programa y muchos procesos que corresponden al mismo programa

    • Un proceso no tiene por qué ser todo un programa en ejecución sino que puede ser una parte de él. Por ejemplo un programa, al ponerse en ejecución puede dar lugar a más de un proceso, cada uno de ellos ejecutando una parte del programa (navegador Firefox, Chrome, etc…).

  • Concurrencia:

    • Dos procesos serán concurrentes cuando la primera instrucción de uno de ellos se ejecute después de la primera instrucción del otro y antes de la última

      • Existe solapamiento en la ejecución de sus instrucciones, aunque no se ejecuten al mismo tiempo

    • Si los proceso se ejecutan exactamente al mismo tiempo → programación paralela

    • La programación concurrente es un paralelismo potencial, no real. Dependerá del hardware subyacente

concurrencia.png

Figure 1: Programación concurrente.

  • Cuando varios procesos se ejecutan concurrentemente pueden

    • Colaborar
    • Competir por recursos

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

  • Programación concurrente:

    • Permite especificar la ejecución concurrente de las acciones de un programa, así como las técnicas para resolver problemas inherentes a la ejecución concurrente → mecanismos de comunicación y sincronización
    • Es más compleja que la programación tradicional

  • David Baron puso esta nota en su oficina en Mozilla hace un tiempo:

thistall.jpg

Beneficios de la programación concurrente

  • Cuando los procesos se ejecutan concurrentemente puede haber procesos que colaboran entre sí mientras que otros pueden competir por los mismo recursos.

  • Entonces si añade estos problemas, ¿cuales son los beneficios de la programación concurrente?

    • Mejor aprovechamiento de la CPU
    • Velocidad de ejecución: cuando hay mas de 1 procesador podemos tener cada proceso en un procesador
      • Por ejemplo programas cálculo numérico, tratamiento de imágenes, la propia compilación de código con make, etc…

  • Solución de problemas inherentemente concurrentes:

    • Sistemas de control
    • Tecnologías web: servidores web, chat, servidores correo, navegadores.
    • Aplicaciones basadas en interfaces de usuario (e.g. juegos)
    • Simulación realista de objetos físicos: la simulación de objetos físicos no se puede hacer de manera secuencial porque no se correspondería con la vida real
    • SGBD: la programación concurrente permite aplicar políticas adecuadas para mantener la integridad de los datos.

Concurrencia y arquitecturas hardware

Cuando hablamos de hardware nos referimos al número de procesadores del sistema:

  • Sistemas monoprocesador: 1 solo procesador
  • Sistemas multiprocesador: más de un procesador

La programación concurrente presenta beneficios tanto en arquitecturas hardware monoprocesador (comunicación mediante variables compartidas) como en arquitecturas hardware multiprocesador

  • Arquitecturas hardware monoprocesador:

    • También es posible tener ejecución concurrente de procesos

    • No todos los procesos se ejecutan al mismo tiempo, sólo uno de ellos los estará haciendo, pero la sensación del usuario es de estar ejecutándose al mismo tiempo

    • El SO va alternando el tiempo de procesador entre los distintos procesos → Multiprogramación

    • Todos los procesos comparten la misma memoria. La forma de sincronizar y comunicar es mediante el uso de variables compartidas.

  • Arquitecturas hardware multiprocesador: permiten que exista el paralelismo real, aunque la realidad es que siempre haya más procesos que procesadores. Las clasificamos en:

    • Fuertemente acopladas: Se comunican mediante variables en memoria compartida, ya que los procesadores y otros dispositivos están conectados a un bus: Multiproceso

    • Débilmente acopladas: No existe memoria compartida por los procesadores, cada procesador tiene su memoria local. Se trata de un Procesamiento distribuido. El mecanismo de comunicación más común es el paso de mensajes.

  • El paso de mensajes también se puede aplicar en sistemas de multiproceso y de multiprogramación.

  • La unión del paso de mensajes y la programación concurrente ha llevado a la programación concurrente orientada a objetos. El caso más representativo es el de JAVA

Cuadro resumen

  • Programa Concurrente: Conjunto de acciones que pueden ser ejecutadas simultáneamente.

  • Programa Paralelo: Programa concurrente para sistema multiprocesador

  • Programa Distribuido: Programa paralelo para sistemas sin memoria compartida

    En la siguiente tabla tenemos en las filas el número de procesadores y en la columna correspondiente si se trata de memoria compartida o no.

NP./ MC. Sí No
1 Multiprogramación -
N Multiproceso Programación distribuida

Especificación de ejecución concurrente

  • ¿Qué se puede ejecutar concurrentemente?

    • No todas las partes de un programa se pueden ejecutar concurrentemente:
      No Sí
      x:=1; x:=1;
      y:=x+2; y:=2;
      z:=y+1; z:=3;

  • En la primera columna está claro que la primera sentencia que debe ejecutar antes que la segunda

  • En la segunda columna, el orden en que se ejecuten no tiene importancia

Condiciones de Bernstein:

Para poder determinar si dos conjuntos de instrucciones se pueden ejecutar concurrentemente, sea $S_k$ un conjunto de instrucciones a ejecutar, llamamos:

  • $L(S_k) = { a_1, a_2, …a_n }$ al conjunto de lectura, formado por todas las variables cuyos valores son referenciados (se leen) durante la ejecución de las instrucciones $S_k$

  • $E(S_k) = { b_1, b_2, …b_m }$ al conjunto de escritura, formado por todas las variables cuyos valores son actualizados durante la ejecución

Para que se puedan ejecutar concurrentemente dos conjuntos de instrucciones $S_i$ y $S_j$ se debe cumplir que ninguno escriba lo que el otro lee o escribe:

  1. $L(S_i) \cap E(S_j)= \varnothing$
  2. $E(S_i) \cap L(S_j)= \varnothing$
  3. $E(S_i) \cap E(S_j)= \varnothing$

  • Dadas las siguientes instrucciones, decidir cuáles se pueden ejecutar de forma concurrente.

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

  • Procedemos así:

    1. Calculamos los conjuntos de lectura y escritura

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

    2. Aplicamos las condiciones a cada par de sentencias:

        $S_1$ $S_2$ $S_3$ $S_4$
      $S_1$ - S N S
      $S_2$ - - N S
      $S_3$ - - - N
      $S_4$ - - - -

Ejercicio 1

Usando las condiciones de Bernstein, construye una tabla como la anterior para el siguiente código:

S1 cuad := x * x;
S2 m1 := a * cuad;
S3 m2 := b * x;
S4 z := m1 + m2;
S5 y := z + c;
  • La ejecución concurrente tiene dos características:
    • Orden parcial
    • Indeterminismo (causado por el orden parcial)
    • El indeterminismo está en la raíz de los problemas de la programación concurrente

Orden de ejecución de las instrucciones

  • Programas secuenciales: orden total, ante un conjunto de datos de entrada siempre se sabe el flujo del programa:

progsec.png

  • Programas concurrentes: orden parcial, ante el mismo conjunto de datos no se puede saber cual será el flujo de ejecución. En cada ejecución el flujo puede ir por un sitio distinto:

    progconc.png

    El orden parcial lleva a los programas a un comportamiento indeterminista: arrojar diferentes resultados cuando se ejecuta el programa repetidamente con los mismos datos de entrada.

Problemas inherentes a la programación concurrente

Exclusión mutua

  • Situación en la que un recurso sólo puede ser accedido por un proceso (recurso crítico)

    Ojo! Lo que realmente se ejecuta concurrentemente son las líneas de código generadas por el compilador. Cada línea es atómica o indivisible, p.e. la instrucción x := x + 1, genera el ensamblador:

    LOAD X R1;
ADD R1 1;
STORE R1 X

  • Este programa no podría lanzar dos procesos concurrentes salvo que la línea de código se defina como Sección Crítica

    exmutua.png

Condición de sincronización

  • Situaciones en las que un recurso compartido por varios procesos se encuentra en un estado en el que un proceso no puede hacer una determinada acción con él hasta que no cambie su estado

  • La programación concurrente debe permitirnos bloquear procesos a la espera de un evento y desbloquearlos cuando el evento haya ocurrido

  • Supongamos el siguiente sistema:

    • Lector: va almacenando en el buffer las imágenes capturadas por una camara

    • Gestor: recoge las imágenes del buffer, las trata y las deja en la cola de impresión

    • Impresor: va imprimiendo las imágenes de la cola de impresion

condsinc.png

  • Supongamos que las tres funciones se ejecutan de manera concurrente:

    def lector():                   
  # Captura una imagen y la almacena en el buffer
  while True:                   
    imagen = captura_imagen()
    buffer.add(imagen)

def gestor():
  # Coge una imagen del buffer, la trata y la almacena en cola de impresion
  while True:
    imagen = buffer.get()
    imagen = procesar(imagen)
    cola_impresion.add(imagen)

def impresor():
  # Coge una imagen de la cola de impresion y la imprime
  while True:
    imagen = cola_impresion.get()
    imprimir(imagen)

  • Esta solución está incompleta:

    • ¿Qué ocurre cuando el proceso lector o el proceso gestor tratan de poner una imagen y el buffer o la cola están llenos?
    • ¿Qué ocurre cuando el proceso gestor o el proceso impresor tratan de coger una imagen y el buffer o la cola están vacios?

  • Es por tanto necesario establecer condiciones de sincronización

Propiedades de los programas concurrentes

Además de las especificaciones funcionales, un programa concurrente debe cumplir:

  • Propiedades de seguridad: Son aquellas que aseguran que nada malo va a pasar durante la ejecución del programa

  • Propiedades de vivacidad: Son aquellas que aseguran que algo bueno pasará eventualmente durante la ejecución del programa

Ejemplo

  • En el juego del pañuelo hay dos equipos A y B, y un juez con un pañuelo. Cada jugador de un equipo tiene un número del 1 al 3.
  • No puede haber dos jugadores en el mismo equipo con el mismo número. El juez dice un número y entonces los dos rivales con el mismo número salen corriendo a coger el pañuelo.
  • El jugador que lo coja ha de volver corriendo a su sitio sin que su rival logre tocarle la espalda.

Propiedades de seguridad

  • Exclusión mutua: se debe garantizar que ciertos recursos críticos solo pueden ser usados por un proceso o hilo a la vez. Previene la inconsistencia en los datos. Mecanismos: locks, semáforos o monitores.

    Ejemplo: el pañuelo ha de adquirirse por un jugador o por otro, en exclusion mutua, ya que si lo adquieren los dos puede llegar a romperse → mal funcionamiento del sistema.

  • Condición de sincronización: se debe asgurar que la ejecución de un proceso ocurre en el orden correcto respecto a otros procesos. Esto ocurre porque hay situaciones en las que un proceso debe esperar a que se produzca un determinado evento para poder avanzar y esto no llega a ocurrir. Mecanismos: señales, variables de condición o semáforos.

    Ejemplo: el jugador debe esperar a que digan su número para poder salir en busca del pañuelo.

  • No Interbloqueo (deadlock): los interbloqueos son situaciones en las que dos o más procesos están esperando que ocurra un evento que nunca se producirá. También se le llama interbloqueo pasivo o deadlock. Se deben evitar estas situaciones.

    Ejemplo: Si uno de los jugadores coge el pañuelo y se lo lleva a su casa. El juez debería esperar a que le devuelva el pañuelo y los jugadores a que el juez diga su número, pero esto nunca va a pasar.

Propiedades de vivacidad

  • No Interbloqueo activo: El interbloqueo activo se produce cuando un sistema ejecuta una serie de instrucciones sin hacer ningún progreso (livelock). Esto se debe evitar.

    Ejemplo: Si los jugadores que salen a por el pañuelo hacen el amago de cogerlo pero nunca llegan a hacerlo.

  • No Inanición: La inanición se produce cuando existe un grupo de procesos que nunca progresan porque no se les otorga tiempo de procesador para avanzar. Esto también lo debemos evitar.

    Ejemplo: En nuestro ejemplo se produciría si el juez nunca dice el número de un jugador en concreto. Hay que garantizar cierta equidad en el trato a los procesos a no ser que las especificaciónes del sistema digan lo contrario.

Ejemplo

Supongamos que una variable se actualiza con dos funciones que se ejecutan concurrentemente, ¿qué valor tendría x al acabar el programa?

x = 0

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

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

Ejercicio 2

Plantea una traza que haga que x valiese 5 al final de la ejecución.

  • ¿Qué rango de valores crees que podría acabar teniendo x?
  • ¿De qué problemas de los nombrados en esta sesión adolece el programa?

Ejercicio 3

Contesta a las siguientes cuestiones:

  1. ¿Cuál es la ventaja de la concurrencia en los sistemas monoprocesador?
  2. ¿Cuáles son las diferencias entre programación concurrente, paralela y distribuida?
  3. ¿Cuáles son los dos problemas principales inherentes a la programación concurrente?
  4. ¿Qué es una sección crítica?
  5. ¿Cuáles son las características de un programa concurrente?
  6. ¿Qué se entiende por un programa concurrente correcto?

Aclaraciones

  • En ningún caso estas transparencias son la bibliografía de la asignatura, por lo tanto debes estudiar, aclarar y ampliar los conceptos que en ellas encuentres empleando los enlaces web y bibliografía recomendada que puedes consultar en la página web de la ficha de la asignatura y en la web propia de la asignatura.