PDF de programación - Tópicos de programación Concurrente y Paralela

Tópicos de programación

Concurrente y Paralela



Facultad de Informática UNLP

UNLu

Clase 1 - Conceptos básicos

Material y contenidos

• El material y contenidos del curso es una adaptación de las clases
de la cátedra de Programación Concurrente de la Facultad de
Informática de la Universidad Nacional de La Plata, a cargo del
Profesor Dr. Marcelo Naiouf



• El contenido que abarcaremos contará con dos etapas:

– Etapa I: Contenidos teóricos y conceptuales

– Etapa II: Análisis de un problema a resolver, resolución y evolución de las

soluciones: secuencial, memoria compartida, pasaje de mensajes e híbrida

Metodología

Comunicación

 Esp. Lic. Fabiana Leibovich: [email protected]



Bibliografia



 Foundations of Multithreaded, Parallel, and Distributed

Programming. G. Andrews. Addison Wesley
www.cs.arizona.edu/people/greg/mpdbook


 An Introduction to Parallel Computing. Grama, Gupta, Karypis, Kumar.

Objetivos

 Plantear

los

fundamentos de

la programación concurrente,
estudiando sintaxis y semántica, así como herramientas y lenguajes
p/ la resolución de programas concurrentes.


 Analizar el concepto de sistemas concurrentes que integran la
arquitectura de hardware, el SO y los algoritmos para la resolución
de problemas concurrentes.


 Estudiar

los conceptos

fundamentales de comunicación y
sincronización e/ procesos, por Memoria compartida (MC) y Pasaje
de mensajes (PM).


 Vincular

la concurrencia en software con
procesamiento distribuido y paralelo, para
multiprocesador con algoritmos concurrentes.

los conceptos de
lograr soluciones

¿Qué es la concurrencia?

RAE: “Coincidencia, concurso simultáneo de varias circunstancias”



Concurrencia es la capacidad de ejecutar múltiples actividades en
paralelo o simultáneamente



Permite a distintos objetos actuar al mismo tiempo

Concepto clave dentro de la Ciencia de la Computación, relevante
para el diseño de hardware, SO, multiprocesadores, computación
distribuida, programación y diseño.



La necesidad de sistemas de cómputo cada vez más poderosos y
flexibles atenta contra
la simplificación de asunciones de
secuencialidad



¿Dónde encontramos concurrencia?

“Concurrency is everywhere”


 Está presente en la naturaleza, la vida diaria, los

sistemas de cómputo, etc

 Cualquier sistema más o menos “inteligente” exhibe

concurrencia…
 Desde un teléfono hasta un automóvil
 Navegador Web accediendo información mientras atiende al usuario
 Acceso de varias aplicaciones a disco
 Varios usuarios conectados al mismo sistema (ej, haciendo una

reserva)
 Juegos
 Otros??

Concurrencia “natural”

Problema: Desplegar cada 3 segundos un mensaje
Qué ocurre si se quiere mostrar, además, otro cartel pero cada cada
5 segundos ??



El programa (secuencial) es más complejo…

Una solución más
natural es ejecutar dos
algoritmos simples
concurrentemente…


Por qué es necesaria la Programación

Concurrente?

 No hay más ciclos de reloj…
 Aplicaciones con estructura más natural.

 El mundo no es secuencial
 Más

apropiado

programar

múltiples

actividades

independientes y concurrentes

 Reacción a entradas asincrónicas (ej: sensores)

 Mejora en la respuesta

 No bloquear la aplicación completa por E/S

 Performance a partir de hardware multiprocesador / multicore

 Ejecución paralela

 Sistemas distribuidos

 Una aplicación en varias máquinas
 Sistemas C/S o P2P



Objetivos de los sistemas concurrentes

 Ajustar el modelo de arquitectura de hardware y software al

problema del mundo real a resolver.



 El mundo real ES CONCURRENTE



 Incrementar la performance, mejorando los tiempos de respuesta
de los sistemas de procesamiento de datos, a través de un enfoque
diferente de la arquitectura física y lógica de las soluciones.


 Algunas ventajas: la velocidad de ejecución que se puede alcanzar,
mejor utilización de la CPU de cada procesador, y explotación de la
concurrencia inherente a la mayoría de los problemas reales.



Conexiones

¿Qué es un proceso?

 Programa secuencial:

 un solo flujo de control que ejecuta una instrucción y cuando esta finaliza

ejecuta la siguiente


 PROCESO: programa secuencial

 Un único thread o flujo de control


 Múltiples threads o flujos de control



 programa concurrente
 procesos paralelos

programación secuencial, monoprocesador

Los procesos cooperan y compiten...


Posibles comportamientos de los procesos

 Procesos independientes

 Relativamente raros
 Poco interesantes



Posibles comportamientos de los procesos

 Competencia

 Típico en SO y redes, debido a recursos compartidos



Posibles comportamientos

de los procesos

 Cooperación

 Los procesos se combinan para resolver una tarea común
 Sincronización



Procesamiento secuencial, concurrente y

paralelo

 Analicemos la solución secuencial y monoprocesador
(UNA máquina) para fabricar un objeto compuesto por
N partes o módulos.

La solución secuencial nos fuerza a establecer un estricto
orden temporal.

Al disponer de sólo una máquina el ensamblado final del
objeto sólo se podrá
luego de N pasos de
procesamiento o fabricación.

realizar

Procesamiento secuencial, concurrente y

paralelo

 Si disponemos de N máquinas para fabricar el objeto, y
no hay dependencias (x ej de la materia prima), cada
una puede trabajar al mismo tiempo en una parte

Consecuencias 

 Menor tiempo para completar el trabajo
 Menor esfuerzo individual
 Paralelismo del hardware

Dificultades 

 Distribución de la carga de trabajo
 Necesidad de compartir recursos evitando conflictos
 Necesidad de esperarse en puntos clave
 Necesidad de comunicarse
 Tratamiento de las fallas
 Asignación de una de las máquinas para el ensamblado (Cual??)

Procesamiento secuencial, concurrente y

paralelo

 Vimos las soluciones secuencial y paralela (multiplicando el hard)
en el problema de fabricar un objeto (sistema) de múltiples partes
 Otro enfoque: UNA máquina dedica parte del tiempo a cada
componente del objeto  Concurrencia sin paralelismo de
hard

Dificultades 

 Distribución de carga de trabajo
 Necesidad de compartir recursos evitando conflictos
 Necesidad de esperarse en puntos clave
 Necesidad de comunicarse
 Necesidad de recuperar el “estado” de cada proceso al retomarlo.

CONCURRENCIA  Concepto de software no restringido a una

arquitectura particular de hardware ni a un número

determinado de procesadores

Programa Concurrente

 Un programa concurrente especifica dos o más programas
secuenciales que pueden ejecutarse concurrentemente en el
tiempo como tareas o procesos.

 Un proceso o tarea es un elemento concurrente abstracto que
puede ejecutarse simultáneamente con otros procesos o tareas
(en paralelo), si el hardware lo permite

 Un programa concurrente puede tener N procesos habilitados
para ejecutarse concurrentemente y un sistema concurrente
puede disponer de M procesadores cada uno de los cuales
puede ejecutar uno o más procesos.

Características importantes:



- Interacción
- No determinismo  dificultad para la interpretación y debug
- Ejecución “infinita”

Soporte de ejecución de un programa

concurrente

 Los procesos concurrentes se ejecutan con la ayuda de un núcleo de

ejecución (run-time support system)

 Planificador (scheduler) del sistema operativo


 Se encarga de la creación, terminación y multiplexado de los procesos

 Opciones del núcleo:

 Desarrollado como parte de la aplicación (Modula-2)
 Incluido en el entorno de ejecución del lenguaje (Ada, Java)
 Parte de un sistema operativo de tiempo real (POSIX)
 Microprogramado en el procesador (occam2)


El método de planificación utilizado afecta al comportamiento temporal del sistema



Concurrencia vs. Paralelismo

 La concurrencia no es (sólo) paralelismo

Concurrencia “interleaved” 

 Procesamiento simultáneo lógicamente
 Ejecución

intercalada en un único

procesador

 “Seudo-paralelismo”



Concurrencia simultánea 

 Procesamiento simultáneo físicamente
 Requiere un sistema multiprocesador o

multicore

 Paralelismo “full”


Procesamiento secuencial, concurrente y

paralelo

 Cambios de estado de los procesos (recordar de S.O.)

Procesamiento secuencial, concurrente y

paralelo

Multiprogramación en un procesador
 El tiempo de CPU es compartido entre varios procesos x ej por time

slicing

 El SO controla y planifica procesos: si el slice expiró o el proceso se

bloquea el SO hace context (process) switch



Process switch: suspender el proceso actual y restaurar

otro



1. Salvar el estado actual en memoria. Agregar el
proceso al final de la cola de ready o una cola de wait

2. Sacar un proceso de la cabeza de la cola ready.
Restaurar su estado y ponerlo a correr

Reanudar un proceso bloqueado: mover un proceso
de la cola de wait a la de ready

Procesos e hilos

 Todos los sistemas operativos soportan procesos

 Cada proceso se ejecuta en una máquina virtual distinta


 Algunos sistemas operativos soportan procesos ligeros (hilos o

threads)

 Todos los hilos de un proceso comparten la misma máquina virtual
 Tienen acceso al mismo espacio de memoria
 El programador o el lenguaje deben proporcionar mecanismos

para evitar interferencias


 La concurrencia puede estar soportada por

 El lenguaje: Java, Ada, occam2
 El sistema