Tema 1

Principios Generales de la ConcurrenciaTema 1 - Programación Concurrente y de Tiempo Real

Antonio J. Tomeu1 Manuel Francisco2

1Departamento de Ingeniería InformáticaUniversidad de Cádiz

2Alumno colaborador de la asignaturaUniversidad de Cádiz

PCTR, 2015

Contenido

1. Concepto de Concurrencia.2. Por Qué Utilizar la Concurrencia.3. Exclusión Mutua y Sincronización.4. Consideraciones Sobre el Hardware.5. Sistemas Distribuidos.6. Sistemas de Tiempo Real.

¿Por Qué Utilizar Concurrencia?

I El hardware es cada vez más paraleloI Procesadores multinúcleo.I Uso de GPU para cálculos masivosI Uso de Clusters de procesadores

Figura: Intel i7 QuadCore (Nehalem) y Gráfica nVidia GPU (CUDA)

Antonio J. Tomeu, Manuel Francisco Principios Generales de la Concurrencia 3 / 51

¿Cuándo Utilizar Concurrencia?


Definición de Concurrencia

Definición de la RAECoincidencia, concurso simultáneo de varias circunstancias.

I En informática, se da cuando dos o más procesos existensimultáneamente.

I Distinguir entre existencia y ejecución simultánea.


Concepto de Proceso

DefiniciónUn proceso es un programa en ejecución.

I Está formado por:I El código que ejecuta el procesador.I El estado (valores registros CPU).I La pila de llamadas.I La memoria de trabajo.I Información de la planificación.


Concepto de Hilo

DefiniciónUn hilo es una secuencia de instrucciones dentro de un proceso, queejecuta sus instrucciones de forma independiente.

I Un proceso puede tener varios hilos.I Los hilos de un proceso no comparten

I La pila (cada una posee la suya).I El contador de programa (ídem).

I Los hilos de un proceso compartenI Memoria de proceso (datos).I Recursos de sistema.


Hilo vs. Procesos: Idealización Gráfica


Concurrencia vs. Paralelismo

I La concurrencia es más general que el paralelismo.I Las soluciones que la P. Concurrente da para la sincronización

y comunicación son válidas para programas paralelos conmemoria común.

I Se tiene paralelismo cuando se produce la ejecución simultáneade dos procesos concurrentes.

I Algoritmos paralelos.I Métodos de programación paralela.I Procesamiento paralelo.I Arquitectura paralela (procesador multinúcleo).


Concurrencia vs. Paralelismo: Gráficamente

Figura: Discrimine entre concurrencia y paralelismo


Presencia de Concurrencia

I En el dominio de los problemas: casos reales que se pretendenmodelar mediante programas.

I En el hardware:I Ejecución paralela.I Funcionamiento paralelo de periféricos.I Multiprocesadores y procesadores multinúcleo.I Sistemas distribuidos.

I En los sistemas operativos y el software:I Ejecución simultánea de procesos.I Ejecución simultánea de threads dentro de un proceso.


Concepto de Sistema Concurrente

DefiniciónSistema informático donde la concurrencia desempeña un papelimportante.

I Ejemplos:I Sistemas operativos.I Sistemas de gestión de bases de datos.I Sistemas en tiempo real.I Sistemas distribuidos.I Y prácticamente casi cualquier aplicación moderna con GUI

decente.I Distinguir entre:

I Sistemas inherentemente concurrentes.I Sistemas potencialmente concurrentes.


Concepto de Programación Concurrente

DefiniciónConjunto de notaciones y técnicas utilizadas para describir medianteprogramas el paralelismo potencial de los problemas, resolviendo losproblemas de sincronización y comunicación que pueden plantearse.

I Se ocupa: del análisis, diseño, implementación y depuración deprogramas concurrentes.

I No se ocupa: del hardware sobre el cual dichos programasconcurrentes se ejecutan, ni del lenguaje concreto con el queimplementar la concurrencia.


Características de la Programación Concurrente I

I Mejora del rendimientoI Indeterminación

I Un programa secuencial es determinista: los mismos datos deentrada generan siempre la misma salida (orden total).

I Un programa concurrente no es determinista: la misma entradapuede dar lugar a diferentes salidas (orden parcial).

I Esto no significa que el programa sea incorrecto.

I No atomicidad.


Características de la Programación Concurrente II

I Velocidad de ejecución de procesos desconocida.I Incertidumbre sobre el resultado.I Entrelazado

I Un programa concurrente puede tener varias secuencias deejecución diferentes.

I Puede haber entrelazados patológicos que lleven ainterbloqueo.

I Mayor dificultad de verificación de programas.I ¿Cuál es la definición de corrección de un programa?


Mejora de Rendimiento I

Ejemplo

Problema: encontrar el número de primos en un rango dado denúmeros naturales. Por ejemplo, en el rango 2-10 hay cuatroprimos: 2, 3, 5 y 7.Rango de interés: 10000000.

I Descargar: primosSecuencial.java, tareaPrimos.java yprimosParalelos.java


Mejora de Rendimiento II

I Solución secuencial: 664579 primos en 52 segundos.I Solución Concurrente/Paralela: 664579 primos en 33 segundos

(con Intel Pentium Core2 Duo).I Solución Concurrente/Paralela 2: 664579 primos en 13

segundos (con Intel Core i3 QuadCore).I Mejora del rendimiento: 37% y 75% respectivamente.


Figura: Mejora del rendimiento: secuencial vs. paralelo


Speedup

DefiniciónEn paralelismo, podemos definir el concepto de speedup como elcoeficiente entre el tiempo necesario para completar una tareasecuencialmente y el tiempo necesario para hacerlo en paralelo.

S =tiempo en secuencialtiempo en paralelo


Cálculo de Speedup

Convolución de una imagen

Tamaño de imagen: 1000x1000 pxI Tiempos en un Intel i5 @1,9GHz (2 núcleos con HT)

I Secuencial: 70 milisegundos.I Paralelo: 36 milisegundos.

I Speedup: 7036 = 1, 94

Convolución de una imagen

Tamaño de imagen: 1500x1500 pxI Tiempos en un Intel i5 @1,9GHz (2 núcleos con HT)


I Speedup: 7036 = 1, 89


Clasificación de Speedup

1. Si S < 1, la paralelización ha hecho que la solución empeore.En este caso, mejor no paralelizar.

2. Si 1 < S ≤ número de núcleos, hemos conseguido mejorar lasolución en un rango normal. En tareas puramente de cómputo(coeficiente de bloqueo muy cercano a 0), S debe estar muypróximo al citado número de núcleos.

3. Si S > número de núcleos, la mejora obtenida ha sidohiperlineal. Son casos muy poco comunes y solo se dan paradeterminados problemas ejecutándose en determinadasarquitecturas de memoria caché.


Ejemplo de Speedup Hiperlineal

Números primos

Primos en el rango 0-10000000I Tiempos en un Intel i5 @1,9GHz (2 núcleos con HT)


I Speedup: 186708968 = 2, 08


Indeterminación

I Diferentes ejecuciones, diferentes outputs.I Descargar incConcurrente.javaI Ejecutar varias veces.I ¿Qué está pasando?I ¿Tiene solución?


Entrelazado

I Dada una línea de tiempo de la CPU, analizando el flujo deinstrucciones que hay en ella:

I Tiene diferentes grupos de instrucciones de distintos procesos.I Diferentes ejecuciones, diferentes flujos.I Descargar ejEntrelazado.javaI ¿Qué está pasando?


El Porqué de Todo lo Anterior

Ejemplo de Entrelazado: Efectos Laterales Indeseables

PROC. INST. N REG1 REG2Inicial 0P1 Load(x) 0 0P2 Load(x) 0 0 0P1 Add(x, 1) 0 1 0P2 Add(x, 1) 0 1 1P1 Store(x) 1 1 1P2 Store(x) 1 1 1


Condiciones de Bernstein (Prevención de Efectos Laterales)

Permiten determinar si dos conjuntos de instrucciones se puedenejecutar de forma concurrente.

Condiciones de Bernstein

I L(Sk) = {a1, a2, ..., an} es el conjunto de lectura del conjuntode instrucciones Sk .

I E (Sk) = {b1, b2, ..., bn} es el conjunto de escritura delconjunto de instrucciones Sk .

I Dos conjuntos de instrucciones Si y Sj se pueden ejecutarconcurrentemente si:

I L(Si ) ∩ E (Sj) = ∅I E (Si ) ∩ L(Sj) = ∅I E (Si ) ∩ E (Sj) = ∅


Condiciones de Bernstein (Ejemplo de Aplicación)

Ejemplo

Dadas las siguientes instrucciones, ¿admiten ejecución concurrente?

S1 : a = x + y

S2 : b = z − 1S3 : c = a− b

S4 : w = c + 1


Interbloqueo

DefiniciónSituación en que todos los procesos quedan a la espera de unacondición que nunca se dará.

I Normalmente asociados a condiciones de espera circular porrecursos comunes.

I Descargar Deadlock.javaI ¿Qué está ocurriendo?


Conclusiones

I Trabajar a nivel de instrucciones atómicas o de grupos deinstrucciones cuya ejecución atómica es forzada por elprogramador.

I Hacer la Hipótesis del Progreso Finito.I Razonar sobre la corrección a nivel de grupos de instrucciones.I Considerar la incertidumbre sobre el resultado final.I Considerar la corrección bajo todas las secuencias de

entrelazado posible.I Desarrollar un modelo abstracto de sistema concurrente.


Problemas de la Concurrencia I: Condiciones de Concurso

I Aparecen cuando varias entidades concurrentes compartenrecursos comunes accediendo a ellos simultáneamente.

I Pueden dar lugar a problemas graves como sobreescritura dedatos, interbloqueos, etc.

I Son propias de los sistemas concurrentes.I Se caracterizan, a nivel de programación, por zonas de código

de las entidades concurrentes desde las que se accede arecursos comunes. Se las llama secciones críticas.

I Dado el indeterminismo de los programas concurrentes, laúnica forma de evitar una condición de concurso será forzar laejecución aislada de cada sección crítica.


Exclusión Mutua

Concepto

Consiste en evitar la condición de concurso sobre un recursocompartido forzando la ejecución atómica de las secciones críticasde las entidades concurrentes que lo usan. Elimina el entrelazado.

I Esto implica detener la ejecución de una entidad concurrentehasta que se produzcan determinadas circunstancias:sincronización.

I También implica el poder comunicar a otras entidades elestado de una dada: comunicación.

I Los lenguajes concurrentes deben permitir ambas.


Beneficios del Uso de Exclusión Mutua

I Dentro de las secciones críticas no hay entrelazado.I Se incrementa el determinismo, ya que se garantiza la

ejecución secuencial (“atómica”) de las secciones críticas.I Permite comunicar a los procesos a través de las secciones

críticas.I Acota a nivel de código (sintácticamente) las secciones críticas

mediante el uso de protocolos de entrada y salida de lasmismas.

I Pueden generar sobrecargas de ejecución.


Utilizando la Exclusión Mutua

I Descargar incConcurrenteSeguro.java.I ¿Qué diferencias sintácticas tiene con incConcurrente.java?I ¿Hay diferencias en la ejecución?I ¿Qué cree que ha pasado?


Modelo de Entidad Concurrente

Figura: Modelo de entidad concurrente

Problemas de la Concurrencia II: Sincronización

Ejemplo clásico: Problema del Productor-Consumidor

Figura: Problema del productor-consumidor


Corrección de Sistemas Concurrentes

I Propiedades de CorrecciónI Seguridad.I Vivacidad.I Inanición.I Equidad.

I Especificación Formal de Sistemas ConcurrentesI Lógica temporal.I CSP (Hoare).I Redes de Petri.

I Metodología gráfica de representación.I Admite modelado dinámico de sistemas concurrentes.I Permite una verificación matemáticamente sencilla de las

propiedades de corrección de un sistema concurrente.


Lenguajes Concurrentes

DefiniciónSe consideran lenguajes de programación concurrentes a aquellosque permiten expresar la concurrencia directamente, no siendonecesario el recurso al sistema operativo o a bibliotecas específicas.

I Incluyen herramientas para sincronizar y comunicar a entidadesconcurrentes.

I C no es un lenguaje concurrente.I C++ incorpora (¡por fin!) concurrencia nativa desde la revisión

C++11 (Agosto de 2012).I Ada, Java, Occam son lenguajes concurrentes.I Puede incluir OO como Java/C++, o no incluirla.


Técnicas de Creación de Entidades Concurrentes

I ManualesI Accediendo directamente al hardware.I Usando bibliotecas software (pthread en C, herencia de la

clase Thread o implementación de la interfaz Runnable enJava.

I AutomáticasI Bajo la responsabilidad del Sistema Operativo

(multiprogramación).I Detección del compilador de la concurrencia implícita en un

programa secuencial y generación automática de los procesosconcurrentes que correspondan.


Modelos de Creación de Entidades Concurrentes

I Modelo de Creación Estático.I Número de procesos concurrentes fijado en tiempo de

compilación.I No es un método flexible.I Es un método seguro, eficaz y limitado

I Modelo de Creación Dinámico (estándar actual).I Procesos creados y destruidos en tiempo de ejecución.I Es un método flexible.I Es menos seguro que los métodos estáticos.I Es utilizado por el sistema operativo Unix o el lenguaje Java.I Es menos estructurado y más difícil de interpretar.


Consideraciones Sobre el Hardware

I Sistemas monoprocesadorI Modelo de concurrencia simulado (procesadores virtuales).I Existe interfoliación de instrucciones.I Arquitectura de memoria común.I Existe planificación en el acceso al procesador.

I Sistemas multiprocesadorI Acoplamiento fuerte (Multiprocesadores y núcleos multicore)

I Arquitectura de memoria común (UMA).I Soluciones propuestas para monoprocesadores admisibles.I Existe planificación en el acceso a los núcleos.

I Acoplamiento débil (Sistemas distribuidos).I Arquitectura de comunicaciones.I Arquitectura de memoria no común (NUMA).I Necesidad de soluciones ad-hoc.


Consideraciones Sobre el Hardware

Figura: Taxonomía de Flynn


Taxonomía de Flynn: SISD

I SI: una instrucción por cada ciclo de reloj.I SD: un segmento de datos por cada ciclo de reloj.I Ejecución determinista.I Antiguo modelo de computación


Taxonomía de Flynn: SIMD

I SI: todas las unidades de ejecución ejecutan la misma.I SD: cada unidad la aplica sobre datos distintos.I Ejecución determinista y síncrona (con cerrojo).I Muy útil en nubes de datos reticuladas.


Taxonomía de Flynn: MIMD

I MI: cada procesador ejecuta distintas instruccionesI MD: sobre datos diferentesI Ejecución determinista/no determinista y síncrona/asíncrona.I Multiprocesadores, clusters, multicores...


Consideraciones Sobre el Hardware (Memoria)


Implementación de Programas Distribuidos

I Modelo de paso de mensajes.I Primitivas de comunicación send/receive.I Carácter de las primitivas.I Protocolo de solicitud/respuesta de pocas capas.

I Modelo RPC/RMII Permite al programador invocar procedimientos remotos de

forma (idealmente) transparente.I Requiere procedimientos de resguardo (stubs).

I Modelo de Objetos DistribuidosI DCOM (Microsoft).I CORBA (OMG).I EJB (Sun).


Sistemas de Tiempo Real

DefinicionSon sistemas concurrentes caracterizados por la existencia de unaligadura temporal para completar una tarea.

I Control robótico, teledirección, telemedicina, multimedia...

I El programador tiene acceso al reloj y planificador.I Pueden ser:

I Críticos: las tareas deben, necesariamente, satisfacer lasrestricciones impuestas por la ligadura temporal.

I No criticos: las tareas intentan satisfacer tales restricciones,pero el diseño no garantiza la consecución de las mismas contotal garantía.

I Linux RT y JRTS.


Sistemas de Tiempo Real: Características

I Predectibilidad.I Determinismo.I Certidumbre.I Control.


En el Próximo Tema...

I Programación en Lenguaje Java.I Elementos básicos.I Clases y objetos.I E/S básica.I Modelo de herencia.


Bibliografía

Ben-Ari, M.Concurrent and Distributed ProgrammingPrentice Hall, 2006[Capítulos 1 y 2]

Bollela, G. y Bruno, E.Real Time Java Programming with Java RTSSunMicrosystems, 2009.[Capítulo 1, págs. 3-13]

Palma, J.Programación concurrente2a edición, [Capítulos 1 y 2]

Date post:	23-Feb-2017
Category:	Engineering
Upload:	atomeu
View:	28 times
Download:	0 times

Tema 1

Engineering