T1-1 Int - Apuntes 1 PDF

Preview

Summary

Presentaciones de clase...

Description

Programación Concurrente

Tema 1 Introducción I

Grado en Informática [email protected]

Programación Concurrente - Presentación

Bibliografía específica



Programación Concurrente J. Palma et al. Thomson, 2003, 



Capítulos 1 y 2

Principles of Concurrent and Distributed Programming M. Ben-Ari. Prentice Hall, 1990 



Capítulos 1 y 2

Concurrent Programming A. Burns, G Davis. Addison-Wesley, 1993 



Capítulo 1

Presentación basada en textos de sidelab URJC. (Creative Commons)

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

2

1

Contenido 1.1 Introducción 1.2 Programas y Procesos. 1.3 Arquitecturas físicas 1.4 Hilos y más hilos 1.5 Lenguajes Concurrentes

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

3

1.1 Introducción





El paradigma de la programación concurrente se ocupa de desarrollar métodos de representación de procesos concurrentes y herramientas para especificar y verificar programas concurrentes

La disciplina surge en los años 60 cuando los sistemas operativos, gracias a mejoras hardware, comienzan a aprovechar el procesador ejecutando varios procesos de forma concurrente, para: Ofrecer un entorno interactivo a múltiples usuarios Aprovechar el procesador cuando un proceso espera por una operación de entrada/salida

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

4

2

1.1 Introducción





Inicialmente la concurrencia sólo podía utilizarse con herramientas de bajo nivel y por el sistema operativo Los lenguajes de programación y sus librerías han evolucionado para proporcionar herramientas de programación concurrente: PascalFC, C/C++, Scala, OCAM, ADA, Haskell, Erlang, C#... Java, Python, Ruby

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

5

1.1 introducción









Una forma de ver la concurrencia es como un conjunto de actividades que se desarrollan de forma simultánea. En informática, cada una de esas actividades se suele llamar proceso. Por tanto: en Informática, se habla de concurrencia cuando hay una existencia simultánea de varios procesos en ejecución. Ojo, existencia simultánea no implica ejecución simultánea.

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

6

3

Contenido 1.1 Introducción

1.2 Programas y Procesos. 1.3 Arquitecturas físicas 1.4 Hilos y más hilos 1.5 Lenguajes Concurrentes

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

7

1.2 Programas y Procesos 

Programa Secuencial Conjunto de declaraciones de datos e instrucciones (o acciones) ejecutables, escrito en un lenguaje de programación Estas instrucciones deben ejecutarse una a continuación de otra, siguiendo una secuencia determinada por un algoritmo, para resolver un cierto problema



Procesos Definición extendida: Un proceso es un programa en ejecución Pueden existir varios procesos de un mismo programa simultáneamente en un sistema concurrente.



Cuando compilamos y ejecutamos un programa se crea un proceso que es la ejecución dinámica en la CPU de las instrucciones compiladas

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

8

4

1.2 Programas y procesos Concurrencia a dos niveles: Nivel del Sistema Operativo (procesos pesados)  

Programa: Fichero ejecutable Proceso: Proceso que aparece en el sistema cuando se ejecuta un Programa Un proceso utiliza unos recursos para ejecutarse: (Contador de programa, espacio de memoria, pila,…)

Nivel de un Programa Internamente (procesos ligeros o Hilos) 



Cada proceso puede contener internamente varios subprocesos o hilos Estos hilos comparten memoria principal para las variables globales, pero también tienen su propio CP, Pila y Registros…

Nosotros nos centraremos en la concurrencia a nivel de programa, procesos ligeros/Hilos PROGRAMACIÓN CONCURRENTE – TEMA 1 Introducción

10

1.2 Programas y procesos Ejemplo de procesos en un SO 

Nivel del Sistema Operativo

Programa Secuencial

Proceso (Proceso Pesado) PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

11

5

1.2 Programas y procesos Ejemplo de hilos en un programa 

Ejecución Programa: Juego Ping-Pong

Proceso Pesado

Hilo 1

Ping-Pong Runnig

Hilo 2 Hilo 3

Hilo 1: Jugador 1 Hilos (Procesos ligeros)

Hilo 2: Jugador 2 Hilo 3: Pelota

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

12

1.2 Programas y procesos Threads (Hilos) 





Un thread (hilo) es una secuencia de ejecución independiente dentro de un proceso (pesado), con un contador de programa, una pila y un conjunto de registros,… Los procesos (pesados) tradicionales – programas no concurrentestienen un sólo thread de control.. Un programa Multi-Hilo tienen varios hilos de ejecución no sólo el principal.

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

13

6

Contenido 1.1 Introducción 1.2 Programas y Procesos.

1.3 Arquitecturas físicas 1.4 Hilos y más hilos 1.5 Lenguajes Concurrentes

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

14

1.3 Arquitecturas físicas Soportan concurrencia:

Monoprocesadores  Sistemas con un solo procesador. Multiprocesadores  Computadores con más de un procesador. Sistemas distribuidos  Computadores (uni o multiprocesador) conectados entre sí por una red

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

15

7

1.5 Arquitecturas físicas Monoprocesador 



No hay paralelismo. Los procesos se reparten el procesador mediante interleaving, controlado por el planificador (scheduler) del S.O. Los procesos comparten la misma memoria, comunicación y sincronización mediante variables compartidas shared variable

reads

writes

Process 1

P1 in CPU

Shared memory

Process 2

Process 3

P2 in CPU Operating System

P3 in CPU

TIEMPO

scheduler

CPU

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

16

1.3 Arquitecturas físicas Multiprocesador: 

Multiprocesador Hay paralelismo real, peo el interleaving sigue siendo necesario (normalmente el número de procesadores es menor que el de procesos) shared variable

P1 in Core1 P2 in Core2

reads

writes

P3 in Core3

TIEMPO

L3 shared memory

Process 1

Process 2

Process 3

Operating System 



Varios Cores en un procesador pueden compartir la misma memoria. Los procesadores actuales tienen varios niveles de memoria, no toda compartida

PROGRAMACIÓN CONCURRENTE – TEMA 1

scheduler

Core 1

Core 2

Introducción

17

8

1.5 Arquitecturas físicas Sistemas distribuidos     

Múltiples procesadores conectados mediante una red Los procesadores no comparten memoria ni reloj Los sistemas conectados pueden ser de cualquier tipo Escalable hasta millones de procesadores (ej. Internet) Comunicación mediante de mensajes

CPU 1 memory

CPU 1

CPU X X CPU X CPU memory memory memory

CPU CPU CPU X X X

CPU N memory

CPU N

NETWORK

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

19

1.3 Arquitecturas Físicas 

Modelos de Concurrencia Memoria compartida  

Los procesos pueden acceder a una memoria común Existen variables compartidas que varios procesos pueden leer y escribir

Paso de mensajes  

Los procesos se intercambian mensajes entre sí Un proceso envía mensaje y otro proceso lo recibe

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

20

9

Contenido 1.1 Introducción 1.2 Programas y Procesos. 1.3 Arquitecturas físicas

1.4 Hilos y más hilos 1.5 Lenguajes Concurrentes

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

21

1.4 Hilos y más hilos.. Multithreading Models 



Los SS.OO. Deben optimizar sus algoritmos de scheduling para intentar conseguir el mejor uso de los cores disponibles Hay dos niveles de hilos en un sistema actual: Hilos de Usuario e Hilos de kernel

Hilos de usuario: Están soportados por encima del kernel y sin el soporte de éste. Son los hilos que creamos en los programas multi-hilo. Hilos de Kernel: Están soportador por el propio Kernel del SO, permitiéndole realizar múltiples tareas simultáneamente. 

Thread Libraries: proporcionan un API para crear y manejar hilos. Las tres principales son

1. POSIX Pthreads ( disponible Solaris Linux, MacOSX, Windows,..) 2. Win32 threads ( Librería a nivel de kernel en windows) 3. Java threads. (hilos de Usuario en Programas Java) PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

22

10

1.4 Hilos y más hilos Multithreading Models 

El mapeado/conversión de user-threads en kernel-threads puede seguir diversas estrategias dependiendo del sistema. (many to one, one to one, many to many , two levels).

www.cs.uic.edu 

Java threads: Todos los programas en Java usan threads aunque sea un solo thread principal. La JVM corre encima del SO, y no especifica qué modelo utiliza para mapear Java threads a kernel threads, esta decisión depende de la implementación de la JVM según el SO sobre el que se ejecute. (Puede ser one to one, many to many o many to one)

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

23

1.3 Hilos y más hilos Multithreading Models 

Ejemplo: Modelo de mapeo de dos niveles (Two Levels) en Solaris OS:

Level 1 Level 2

https://www.cs.cf.ac.uk

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

24

11

Contenido 1.1 Introducción 1.2 Programas y Procesos. 1.3 Arquitecturas físicas

1.4 Lenguajes Concurrentes

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

25

1.4 Lenguajes concurrentes







Incorporan características que permiten expresar la concurrencia directamente, sin recurrir a servicios del S.O., bibliotecas, etc. Normalmente incluyen mecanismos de sincronización y comunicación entre procesos. Ejemplos: Clásicos: Ada, SR, Occam, PARLOG... Actuales:Java, Python, Ruby



Otros lenguajes (Por Ej. C) pueden recurrir a interfaces del SO para crear concurrencia como las librerías del estándar POSIX (Portable Operating System Interface) Basado en UNIX

PROGRAMACIÓN CONCURRENTE – TEMA 1

Introducción

26

12...