PDF de programación - Tema 1. Fundamentos de la concurrencia

TEMA 1. FUNDAMENTOS
TEMA 1. FUNDAMENTOS
DE LA CONCURRENCIA
DE LA CONCURRENCIA

Ingeniería en Informática

Contenidos
(cid:132) Introducción
(cid:132) Beneficios de la programación concurrente
(cid:132) Concurrencia y arquitecturas hardware
(cid:132) Especificación de ejecución concurrente
(cid:132) Características de los sistemas concurrentes
(cid:132) Problemas inherentes a la programación

concurrente

(cid:132) Verificación de programas concurrentes

© Alexis Quesada Arencibia

ProgramaciónConcurrente

2

Bibliografía
(cid:132) Programción Concurrente

(cid:132) J. Tomás, M. Garrido, F. Sánchez, A. Quesada, 2003
(cid:132) Capítulo 1 y 2

(cid:132) Principles of Concurrent and Distributed Programming

(cid:132) M. Ben-Ari. Prentice Hall, 1990
(cid:132) Capítulo 1 y 2

(cid:132) Concurrent Programming

(cid:132) A. Burns, G Davis. Addison-Wesley, 1993
(cid:132) Capítulo 1

Contenidos
(cid:132) Introducción
(cid:132) Beneficios de la programación concurrente
(cid:132) Concurrencia y arquitecturas hardware
(cid:132) Especificación de ejecución concurrente
(cid:132) Características de los sistemas concurrentes
(cid:132) Problemas inherentes a la programación

concurrente

(cid:132) Verificación de programas concurrentes

© Alexis Quesada Arencibia

ProgramaciónConcurrente

3

© Alexis Quesada Arencibia

ProgramaciónConcurrente

4

¿Qué es la concurrencia?
(cid:132) Definición Real Academia Española:
<<Acaecimiento o concurso de varios sucesos en un

mismo tiempo>>

(cid:132) Una forma de ver la concurrencia es

como un conjunto de actividades que se
desarrollan de forma simultánea

(cid:132) En informática, cada una de esas

actividades se suele llamar proceso

Concurrencia
(cid:132) En Informática, se habla de concurrencia

cuando hay una
existencia simultánea de varios procesos en
ejecución

(cid:132) Dos procesos serán concurrentes cuando la

primera instrucción de uno de ellos se ejecuta
después de la primera instrucción del otro y
antes de la última

© Alexis Quesada Arencibia

ProgramaciónConcurrente

5

© Alexis Quesada Arencibia

ProgramaciónConcurrente

6

1

Concurrencia
(cid:132) Ojo, existencia simultánea no implica ejecución

simultánea
(cid:132) Dependerá del hardware subyacente

(cid:132) El paralelismo es un caso particular de la

concurrencia

(cid:132) Se habla de paralelismocuando ocurre la ejecución

simultánea de instrucciones:
(cid:132) arquitecturas paralelas
(cid:132) procesamiento paralelo
(cid:132) algoritmos paralelos
(cid:132) programación paralela

¿Dónde se encuentra la
concurrencia?
(cid:132) En la Naturaleza (el problema que se modela)

(cid:132) ¿ejemplos?

(cid:132) En el hardware(la herramienta para

solucionar el problema):
(cid:132) ejecución paralela de instrucciones
(cid:132) funcionamiento paralelo de los periféricos
(cid:132) procesadores múltiples
(cid:132) sistemas distribuidos

© Alexis Quesada Arencibia

ProgramaciónConcurrente

7

© Alexis Quesada Arencibia

ProgramaciónConcurrente

8

Concurrencia inherente o
potencial
(cid:132) Sistemas inherentemente concurrentes:

(cid:132) el entorno con el que interactúan, o el entorno

que modelan tiene forzosamente actividades
simultáneas

(cid:132) p.ej. red de cajeros automáticos

(cid:132) Sistemas potencialmente concurrentes:

(cid:132) no es estrictamente necesario que haya

concurrencia, pero se puede sacar partido de ella

(cid:132) p.ej. para aumentar la velocidad de ejecución

Programa y Proceso
(cid:132) Definición extendida: un proceso es un programa

en ejecución

(cid:132) o mejor “una actividad asíncrona susceptible de

ser asignada a un procesador”

© Alexis Quesada Arencibia

ProgramaciónConcurrente

9

© Alexis Quesada Arencibia

ProgramaciónConcurrente

10

Procesos
(cid:132) Independientes

(cid:132) P.ej. dos procesos de dos usuarios diferentes

(cid:132) Cooperantes

(cid:132) P. ej. el navegador del esquema anterior

(cid:132) Estas tareas de colaboración y competencia

exigen mecanismos de comunicación y
sincronización entre procesos

Programación Concurrente

Disciplina que se encarga del estudio de las
notaciones que permiten especificar la ejecución
concurrente de las acciones de un programa, así
como las técnicas para resolver los problemas
inherentes a la ejecución concurrente (comunicación
y sincronización)

© Alexis Quesada Arencibia

ProgramaciónConcurrente

11

© Alexis Quesada Arencibia

ProgramaciónConcurrente

12

2

Programación Concurrente
(cid:132) Tradicionalmente estuvo asociada al mundo de los

Sistemas Operativos

(cid:132) Primeros programas concurrentes: SO

(cid:132) Evolución plataformas hardware
(cid:132) Diferentes partes del SO en ejecución sin un orden

predecible y compartiendo variables => nuevos problemas

(cid:132) Soluciones específicas

(cid:132) Tres hitos importantes marcan su evolución:

(cid:132) Hilo
(cid:132) Aparición de lenguajes de alto nivel que da soporte a la P.C.
(cid:132) La aparición de Internet

Programación concurrente
(cid:132) EL trabajar con procesos concurrentes

añade complejidad a la tarea de
programar

(cid:132) ¿cuáles son entonces los beneficios que

aporta la programación concurrente?

© Alexis Quesada Arencibia

ProgramaciónConcurrente

13

© Alexis Quesada Arencibia

ProgramaciónConcurrente

14

Contenidos
(cid:132) Introducción
(cid:132) Beneficios de la programación concurrente
(cid:132) Concurrencia y arquitecturas hardware
(cid:132) Especificación de ejecución concurrente
(cid:132) Características de los sistemas concurrentes
(cid:132) Problemas inherentes a la programación concurrente
(cid:132) Verificación de programas concurrentes

Beneficios de la programación
concurrente
(cid:132) Mejor aprovechamiento de la CPU
(cid:132) Velocidad de ejecución
(cid:132) Solución de problemas de naturaleza

concurrente
(cid:132) Sistemas de control
(cid:132) Tecnologías web
(cid:132) Aplicaciones basadas en interfaces de usuarios
(cid:132) Simulación
(cid:132) SGDB

© Alexis Quesada Arencibia

ProgramaciónConcurrente

15

© Alexis Quesada Arencibia

ProgramaciónConcurrente

16

Contenidos
(cid:132) Introducción
(cid:132) Beneficios de la programación concurrente
(cid:132) Concurrencia y arquitecturas hardware
(cid:132) Especificación de ejecución concurrente
(cid:132) Características de los sistemas concurrentes
(cid:132) Problemas inherentes a la programación

concurrente

(cid:132) Verificación de programas concurrentes

Concurrencia y arquitecturas
hardware

(cid:132) Arquitecturas que soportan la

programación concurrente
(cid:132) Sistemas con un solo procesador (sistemas

monoprocesador)

(cid:132) Sistemas con más de un procesador

(sistemas multiprocesador)

© Alexis Quesada Arencibia

ProgramaciónConcurrente

17

© Alexis Quesada Arencibia

ProgramaciónConcurrente

18

3

Sistemas monoprocesador

(cid:132) No hay paralelismo. Los
procesos se reparten el
procesador: entrelazado
(interleaving)

(cid:132) ¿Quién planifica los procesos?

(cid:132) el sistema operativo
(cid:132) el propio ejecutable (gracias

al compilador) -> runtime
scheduler (RTSS)

(cid:132) Todos los procesos comparten

la misma memoria

(cid:132) Forma “natural” de sincronizar

y comunicar procesos
(cid:132) Variables compartidas

Sistemas multiprocesador o
sistemas paralelos
(cid:132) Más de un procesador => permite que

exista un paralelismo real entre los
procesos

(cid:132) Clasificación sistemas multiprocesador

(cid:132) estrechamente acoplados (multiprocesadores)
(cid:132) débilmente acoplados (sistemas distribuidos)

© Alexis Quesada Arencibia

ProgramaciónConcurrente

19

© Alexis Quesada Arencibia

ProgramaciónConcurrente

20

Sistemas estrechamente
acoplados
(cid:132) Normalmente llamados multiprocesadores
(cid:132) Los procesadores comparten memoria y reloj

(cid:132) Puede ser más o menos difícil acceder a la

memoria de otro procesador

Sistemas estrechamente
acoplados

(cid:132) La sincronización y comunicación entre procesos

se suele hacer mediante variables compartidas

(cid:132) Ventaja:

coste

(cid:132) aumento de velocidad de procesamiento con bajo

(cid:132) Inconveniente:

procesadores

(cid:132) Escalable sólo hasta decenas o centenares de

© Alexis Quesada Arencibia

ProgramaciónConcurrente

21

© Alexis Quesada Arencibia

ProgramaciónConcurrente

22

Sistemas débilmente acoplados o
sistemas distribuidos
(cid:132) Múltiples procesadores conectados mediante

una red

(cid:132) Los procesadores no comparten memoria ni

reloj

(cid:132) Los sistemas conectados pueden ser de

cualquier tipo

(cid:132) Escalable hasta millones de procesadores (ej.

Internet)

Sistemas distribuidos: ventajas
(cid:132) compartición de recursos dispersos
(cid:132) ayuda al trabajo cooperativo de equipos

humanos

(cid:132) aumento de velocidad de ejecución
(cid:132) escalabilidad ilimitada
(cid:132) aumento de fiabilidad:

(cid:132) tolerancia a fallos (fault tolerance)
(cid:132) alta disponibilidad (availability)

© Alexis Quesada Arencibia

ProgramaciónConcurrente

23

© Alexis Quesada Arencibia

ProgramaciónConcurrente

24

4

Sistemas distribuidos
(cid:132) La forma natural de comunicar y

sincronizar procesos es mediante el uso de
paso de mensajes

Contenidos
(cid:132) Introducción
(cid:132) Beneficios de la programación concurrente
(cid:132) Concurrencia y arquitecturas hardware
(cid:132) Especificación de ejecución concurrente
(cid:132) Características de los sistemas concurrentes
(cid:132) Problemas inherentes a la programación

concurrente

(cid:132) Verificación de programas concurrentes

© Alexis Quesada Arencibia

ProgramaciónConcurrente

25

© Alexis Quesada Arencibia

ProgramaciónConcurrente

26

Especificación de ejecución
concurrente

Condiciones de Bernstein

(cid:132) ¿Qué se puede ejecutar concurrentemente?

(cid:132) Sea

(cid:132) Condiciones de Bernstein (1966)

(cid:132) ¿Cómo especificarlo?
(cid:132) Lenguaje concurrente

(cid:132) L(Sk)={a1,a2,...,an} el conjunto de lectur