PDF de programación - Tema 2 - Introducción a la concurrencia - Programación Avanzada

Asignatura 780014

Programación Avanzada

TEMA 2 – INTRODUCCIÓN A LA CONCURRENCIA

Introducción a la concurrencia

 Objetivo del tema:



Presentar el concepto de concurrencia, sus inicios y sus principales
características.

Introducción a la concurrencia

 Objetivo del tema:



Presentar el concepto de concurrencia, sus inicios y sus principales
características.

Índice


1.Definición

2.Historia
3.Beneficios / riesgos
4.HW y SO

5.Notación
6.Java

Definición





Definición de Concurrencia

“Notaciones y técnicas usadas para expresar en programas la

posibilidad potencial de ejecución simultánea de varios
algoritmos y resolver los problemas de sincronización y

comunicación derivados de realizar dicha implementación.”

Definición


Notaciones, forma de
Notaciones, forma de
representar los conceptos.
representar los conceptos.



Definición de Concurrencia

Técnicas, para descubrir la
concurrencia potencial de los
algoritmos

“Notaciones y técnicas usadas para expresar en programas la

Acciones que se ejecutan simultáneamente.

posibilidad potencial de ejecución simultánea de varios
algoritmos y resolver los problemas de sincronización y

comunicación entre procesos que cooperan.

comunicación derivados de realizar dicha implementación.”

sincronización de procesos

De forma segura

el resultado no debe ser función del número de procesadores o del tiempo.

Utilizando herramientas

que permitan diseñar la concurrencia y ejecutarla según el diseño.

Historia de la concurrencia (1º)

 Aparece en el diseño de Sistemas Operativos

 En fase temprana de su evolución

 Con los siguientes objetivos:

 Optimizar el uso de algunos recursos

 La CPU es mucho más rápida que las unidades de E/S

 Realizar un reparto más justo de recursos

 Un programa no tendrá que esperar a otros para comenzar

 Simplificar el desarrollo

 Un programa que se puede dividir en tareas que cooperan, es

más sencillo de codificar.

Historia de la concurrencia (2º)

 Requiere cambios en los lenguajes de programación

 Los primeros lenguajes no permitían crear prog. conc.

 Se crean librerías del SO para crear la concurrencia

 Esto dificulta la creación de programas la concurrencia no está

integrada en el lenguaje

 Se crean compiladores que convierten los programas en

concurrentes analizando lo que hacen
 Esta técnica desaprovecha posibilidades, los programas no estaban

pensados para ser concurrentes

 Finalmente aparecen lenguajes que contemplan la

concurrencia en su propio diseño

Historia de la concurrencia (3º)

 La concurrencia que ofrece el sistema operativo

permite programas secuenciales que son
concurrentes entre sí (llamados procesos)
 Los Procesos se comunican entre sí mediante mecanismos del

SO (Semáforos, sockets y otros)

 Esta concurrencia limita las opciones para crear programas
 En los años 80 aparecen sistemas operativos con :

 Múltiples procesos concurrentes

 Múltiples tareas dentro de cada proceso

 Son los hilos
 Comparten el mismo espacio de direcciones

Historia de la concurrencia (4º)

 Hilos (Threads) = “Procesos ligeros”

 Unidad básica de ejecución concurrente

 Ejecución simultánea y asíncrona

 Necesidad de coordinar su acceso a los datos que comparten

 Evitar corrupción de los datos (Seguridad)

 Necesidad de coordinar la disponibilidad de los recursos

 La CPU es crítica (Vitalidad)


 Es el modelo que usaremos

 Nos permite tomar el control

Beneficios

 Aprovechamiento de múltiples CPU

 Es más barato añadir otra CPU que aumentar velocidad

 Permite aprovechar varios procesadores para un programa (ejemplo:

videojuegos)

 Mejora el aprovechamiento de CPU en sistemas con una sola
 Simplificación del modelado de los programas

 Cada tarea (hilo) se:

 Programa independiente (menos complejo cada uno)
 Prueba independiente y se mantiene y repara

 Capacidad de atención de varias solicitudes

simultáneas
 Con un sólo programa activo (ejemplo RMI)

Beneficios

 Facilita la gestión de eventos asíncronos

 Gracias al propio diseño de los hilos y su comportamiento



 Facilita la creación de servidores (Web, BBDD, etc.)

 Un cliente no acapara un servidor, sólo un hilo del mismo


 Permite crear interfaces de usuario más amigables

 Se evita que el interface se pare si el programa está ocupado
 Siempre hay un hilo dispuesto a detectar las acciones del usuario

sobre los componentes (listener)

Riesgos

 Seguridad

 El acceso simultáneo a elementos compartidos puede

ocasionar inconsistencia por:
 “Condiciones de carrera” (Race condition)



 Un dato inconsistente puede invalidar todo un programa



 Se evita garantizando el acceso a variables en exclusión mutua

 En Java mediante métodos “Synchronized”
 Ejemplo en la última sección

Riesgos

 Interbloqueo

 Si tenemos varios recursos y varios hilos que los necesitan

 Si el uso de los recursos implica bloquearlo en exclusividad

 Si un hilo espera por un recurso hasta que queda libre

 Puede ocurrir que se cree un ciclo de necesidad de recursos y

bloqueos











 Puede ser difícil de detectar y bloquear todo un sistema

Riesgos

 Inanición

 Si tenemos varios hilos intentando utilizar CPU

 Si tenemos una mala planificación y alguno nunca la obtiene

 Tenemos Inanición (Starvation) que puede bloquear todo el

programa



 Escaso rendimiento

 La creación de hilos implica un coste de CPU y memoria

 El control de hilos implica un coste de CPU y memoria

 Un sistema mal diseñado puede tener mayor coste en

concurrencia que lo que ahorra su uso

HW y SO: Niveles de implementación

 Nivel de operación (CPU) (Hardware):

 Procesamiento a nivel de palabra.

 Nivel de instrucción (CPU) (Hardware):

 Ejecución simultánea de varias instrucciones ‘pipelining’


 Nivel de programa (cooperación) (software):

 Un mismo programa con varias tareas (hilos).

 Nivel de aplicaciones (competencia) (software):

 Varias aplicaciones en un mismo sistema.

HW

SW

HW y SO: Tipos de hardware concurrente

4 grupos de computadores “Taxonomía de Flyn” (Flyn, 1966)

 Basados en la estructura de los procesadores:

 Unidad de control (CU)
 Unidad aritmético lógica (ALU)


http://en.wikipedia.org/wiki/Flynn%27s_taxonomy


SISD (Single Instruction Single Data)
SIMD (Single Instruction Multiple Data)
MISD (Multiple Instruction Single Data)
MIMD (Multiple Instruction Multiple Data)

HW y SO: Tipos de hardware concurrente

SISD (Single Instruction Single Data):


Computador secuencial con procesador único capaz
de ejecutar una instrucción por vez y ésta aplicada
sobre un único dato.


Los antiguos equipos
de sobremesa se corresponden
con esta arquitectura y pequeños
ordenadores de uso específico

HW y SO: Tipos de hardware concurrente

SIMD (Single Instruction Multiple Data)


Primeros intentos de obtener rendimientos elevados
Podía ejecutar una instrucción sobre un gran número
de datos.

Ordenadores vectoriales.
Recientemente disponible en la mayoría
de los ordenadores

HW y SO: Tipos de hardware concurrente

MISD (Multiple Instruction Single Data):


Esta posibilidad no es muy común
Los sistemas tolerantes a fallos la utilizan

– Realizan diferentes cálculos con los mismos datos y los

resultados deben coincidir para ser aceptados

– Un ejemplo es la tecnología usada para las naves

espaciales

HW y SO: Tipos de hardware concurrente

MIMD (Multiple Instruction Multiple Data):
HW realmente concurrente. Hay varios procesadores
y por tanto varias unidades de control y varias
unidades de cálculo.


Multiprocesadores
Multicomputadores

Sistemas distribuidos

HW y SO: concurrencia en monoprocesador

 Concurrencia simulada que mejora el rendimiento del conjunto
 La aplicación concurrente puede o no ser ejecutada más eficientemente
 Razones:

 Optimizar utilización de los recursos.
 Servir a múltiples usuarios.
 Conseguir un diseño mas simple y comprensible.

HW y SO: concurrencia en multiprocesador

 Los procesadores comparten una memoria común
 Los procesos se ejecutan con concurrencia física.
 El programa concurrente se ejecuta más eficientemente


HW y SO: concurrencia en multicomputador

 Cada procesador tiene una memoria local
 Comparten controladores, discos, etc. (‘clusters’)
 Los procesos se ejecutan con concurrencia física
 No puede haber hilos de un mismo proceso en dos CPUs

– Lo contrario sería distribuida



HW y SO: concurrencia distribuida

 Cada computador es independiente del resto
 Se comunican a través de LAN o WAN
 Los procesos pueden intercambiar información a través de

la red

Computador 1

Computador 2

LAN/
WAN

Computador 3

Computador 4

HW y SO: estados de un proceso

 En ejecución: el proceso está ocupando un procesador que ejecuta sus

instrucciones.

 Preparado (espera): el proceso está listo para que se le asigne un

procesador para ejecutarse sobre él.

 Bloqueado: el proceso está a la espera de algún evento y no puede

pasar a ejecutarse.



Notación

 Muy importante la nomenclatura utilizada

 Procesador
 Multiprocesador
 Programa
 Proceso
 Subproceso
 Tarea
 Hilo (thread)
 Multiproceso
 Multitarea

 En esta asignatura usaremos indistintamente “proceso” e

“hilo” para referirnos a la unidad de ejecución.

Notación: representación de la concurrencia

 Diagrama de precedencia: grafo dirigido donde
los nodos representan secuencias de instrucciones y
las flechas el orden en que deben ejecutarse.

Cuantos
Primos

1-1000000

Calcula

1-

200000

Calcula
200001
400000

Calcula
400001
600000

Calcula
600001
800000

Calcula
800001
1000000

Suma 1..5

Notación: representación de la concurrencia

Eliminación de la r