Informática III
Concurrencia
Informática III Ing. José L. Simón Pág. 1
Motivaciones
El uso de concurrencia en los programas es relevante para: Aprovechar los avances en hardware y
software: multiprocesamiento, soporte de threads a nivel S.O. y lenguaje, etc.
Mejorar perfomance superponiendo tareas Mejorar los tiempos de respuesta Simplificar la estructura de los programas
Informática III Ing. José L. Simón Pág. 1
Ejemplos
Un servidor Web atiende miles de requerimientos simultáneos Un central telefónica cursa múltiples comunicaciones Un control de vuelo supervisa todos los sistemas de un avión
Informática III Ing. José L. Simón Pág. 1
Soporte de concurrencia en hardware
Multiprocesamiento: SMP, múltiples unidades de ejecución. Multiprogramación: multithreading simultáneo Grids
Informática III Ing. José L. Simón Pág. 1
Soporte de concurrencia en software
Soporte del sistema operativo: multiprogramación (threading nativo), sincronización, IPC Soporte de threads a nivel de plataforma de desarrollo: POSIX pThreads, Windows dll’s, Java Threads Frameworks de objetos activos
Informática III Ing. José L. Simón Pág. 1
Definiciones
Concurrencia Procesamiento simultáneo “lógico” No implica múltiples procesadores “físicos”
Paralelismo Procesamiento simultáneo “físico” Múltiples elementos de procesamiento y/o
dispositivos de operación independiente
Informática III Ing. José L. Simón Pág. 1
Concurrencia vs. paralelismo
Tareas Tareas
Plataformamonoprocesador
PlataformaSMP
Informática III Ing. José L. Simón Pág. 1
Complejidad y concurrencia
Competencia por recursos Bloqueos y deadlocks Planificación Optimización de perfomance
Informática III Ing. José L. Simón Pág. 1
Objetos ActivosEjecutoresDeMetodos
Cola
insertar()remover()
RepresentacionDeRecursos
InterfaceCliente
manejadorM1()manejadorM2()manejadorM3()
<<Interface>> Planif icador
despachar()m1()m2()m3()
1
0..*
1
0..*
1
1
1
1
1
1
1
1
Informática III Ing. José L. Simón Pág. 1
Propiedades requeridas
Seguridad Vitalidad Reusabilidad Perfomance
Informática III Ing. José L. Simón Pág. 1
Seguridad
Ninguna operación debe dejar a un objeto en un estado incoherente que pueda generar comportamientos erróneos o inesperados. Las fallas de seguridad hacen que el objeto ‘funcione mal’
Informática III Ing. José L. Simón Pág. 1
Vitalidad
Una actividad nunca deja de mostrar comportamiento La falta de esta propiedad hace que los objetos ‘no funcionen’
Informática III Ing. José L. Simón Pág. 1
Reusabilidad
Los objetos son utilizables en múltiples contextos cuando se cumple que: Su comunicación externa está restringida Su estructura interna es determinística
Informática III Ing. José L. Simón Pág. 1
Perfomance
La medida en la cual las actividades se ejecutan a tiempo y rápidamente, y depende de: Potencia Latencia Capacidad Eficiencia Escalabilidad Degradación
Informática III Ing. José L. Simón Pág. 1
Aseguramiento de Sistemas Concurrentes
Exclusión
Inmutabilidad
Sincronización
Informática III Ing. José L. Simón Pág. 1
ExclusiónEn un sistema seguro, cada objeto debe autoprotegerse de las violaciones a su integridad.
Frecuentemente esto requiere la cooperación de otros objetos y sus métodos.
La acción simultánea de múltiples threads sobre un mismo objeto puede generar estados inconsistentes.
Informática III Ing. José L. Simón Pág. 1
Exclusión
Técnicas de exclusión: Los métodos no alteran el estado del objeto Asegurar dinámicamente que el estado del
objeto es accedido por los threads secuencialmente
Asegurar estructuralmente que el objeto es usado por un thread a la vez
Informática III Ing. José L. Simón Pág. 1
Exclusión
Inmutabilidad Sincronización Adaptadores Locks
Informática III Ing. José L. Simón Pág. 1
Inmutabilidad
El objeto nunca cambia de estado (sólo lectura) Tipos abstractos de datos Representaciones de valores
Informática III Ing. José L. Simón Pág. 1
Sincronización
Mutex Semáforos Latches
Informática III Ing. José L. Simón Pág. 1
Mutex (exclusión mutua)
try{mutex.adquirir();try{
/* tareas...*/}finally{
mutex.liberar();}
} catch( InterruptedException e ){...
}
Informática III Ing. José L. Simón Pág. 1
Semáforos
Son un tipo especial de mutexes con un contador de threads: cada vez que un thread adquiere el lock se decrementa en 1 Si un thread invoca adquirir() y el contador está en 0, se bloquea hasta que se libere un lock
Informática III Ing. José L. Simón Pág. 1
Latches
Son variables de condición que pueden cambiar de estado una única vez, señalando un paso irreversible Son empleadas usualmente para sincronizar el arranque de un sistema, por ejemplo ‘inicializado’ o ‘listo’
Informática III Ing. José L. Simón Pág. 1
Control de Estado
Fallas y excepciones Guarda Estados y confinamiento Control de concurrencia Transacciones
Informática III Ing. José L. Simón Pág. 1
Fallas y Excepciones
Objeto
Mensaje(método + parámetros )
Respuesta
Precondiciones Invariantes + Poscondiciones
Excepciones
Informática III Ing. José L. Simón Pág. 1
Enfoques para la Ejecución de Operaciones
Optimista: se intenta (try) ejecutar la operación. En caso de falla, se tratan las excepciones que aparecen Pesimista: se verifican las precondiciones antes de ejecutar la operación
Informática III Ing. José L. Simón Pág. 1
Excepciones y Guarda
A veces es muy costoso en términos de perfomance o recursos verificar las precondiciones de una operación. En este caso se intenta la operación (enfoque 'optimista') y si falla se trata la excepción
Informática III Ing. José L. Simón Pág. 1
Guarda
En contextos donde es posible, un método puede verificar las precondiciones utilizando construcciones de 'guarda' para evitar la ejecución de la operación si puede anticiparse que va a ocurrir una falla.
Informática III Ing. José L. Simón Pág. 1
Tratamiento de Fallas
Terminación abrupta (muerte súbita) Continuación Rollback Rollforward Reintento
Informática III Ing. José L. Simón Pág. 1
Creación de Threads
Mensajes unidireccionales Servicios Descomposición paralela Objetos activos
Informática III Ing. José L. Simón Pág. 1
Estrategias de creación
Por tarea: se crea un thread para ejecutar una tarea asíncronamente, por ejemplo en sistemas con e/s intensiva Por actor: el thread es creado para ‘disparar’ un objeto activo que ejecuta un proceso generalmente en respuesta a un evento externo, p. ej. en control o sistemas distribuidos
Informática III Ing. José L. Simón Pág. 1
Basado en ActoresLa forma general es:
for( ;; ) {aceptar_y_procesar_pedidos();
}
Este método crea un objeto activo(actor) que lleva a cabo una seriede tareas diversas
Informática III Ing. José L. Simón Pág. 1
Basado en Tareas
for(;;) {aceptar_pedido();crear_tarea();
}
Manejador de Tarea
Manejador de Tarea
Manejador de Tarea
Servicio
Este método crea un thread por requerimientoque lleva a cabo tareas individuales definidas
Informática III Ing. José L. Simón Pág. 1
Mensajes Unidireccionalescliente
Atributos y Conexiones
aceptarmensaje
Accion(){ actualizarEstado(); enviarMensajes();}
helper
objeto host
Informática III Ing. José L. Simón Pág. 1
Mensajes Unidireccionales
Eventos: clicks, teclas, etc. Notificaciones: alertas de cambio de estado Postings: mensajes de correo, etc. Activaciones: creacion de procesos Comandos: imprimir, etc. Relays: despacho y ruteo de mensajes
Informática III Ing. José L. Simón Pág. 1
Worker Threads
La idea central es usar cada WT para ejecutar múltiples tareas secuenciales no relacionadas entre si. Cada WT acepta comandos, almacenándolos en un canal (buffer, cola, pila, etc.) hasta que pueden ejecutarse en un modelo productor-consumidor
Informática III Ing. José L. Simón Pág. 1
Worker Threads
cliente servidor
canal worker
helper
pedido
encolar
tomar
Informática III Ing. José L. Simón Pág. 1
Colas de Eventosaplicación
generarEvento();... evento
eventoeventoevento
cola deeventos
for(;;){ tomarEvento(); despachar(); ...}
despacho
Informática III Ing. José L. Simón Pág. 1
Polling y E/S dirigida por eventos
‘Polling’ o encuesta periódica es una técnica basada en la revisión periódica de una condición o estado, señalando el cambio en forma sincrónica Ejemplos: espera de terminación de una operación de E/S, liberación de un lock o sección crítica, etc.
Informática III Ing. José L. Simón Pág. 1
Aplicaciones de Polling
Cuando el número de condiciones a sondear es limitado o el sistema no tiene gran carga, este enfoque es aceptable, brindando mejor perfomance que el esquema ‘thread por tarea’ Sin embargo al crecer número de condiciones a sondear puede comprometerse la perfomance. En estos casos se apela a técnicas de serialización y encolamiento
Informática III Ing. José L. Simón Pág. 1
E/S por Eventos
En tareas con e/s intensiva, asignar un thread por cada tarea puede implicar la creación de un gran número de threads La técnica es asignar threads por eventos, donde cada evento significa disponibilidad de e/s Las interfaces gráficas de usuario son ejemplo de aplicación de esta técnica
Informática III Ing. José L. Simón Pág. 1
Servicios
Callbacks Join Control de Servicios
Informática III Ing. José L. Simón Pág. 1
Callbacks
Notificación enviada por el servidor al cliente, indicando la finalización de una tarea Profusamente utilizada, en especial en sistemas donde la finalización de una tarea en el servidor dispara acciones independientes en el cliente Usualmente el cliente provee el mecanismo por el cual es notificado
Informática III Ing. José L. Simón Pág. 1
Callbacks
Cliente
Servidor
Helper
t2: Notificación
t0: Pedido
t1: Pedido
Informática III Ing. José L. Simón Pág. 1
Join
Cuando un thread A debe esperar la finalización de otro B, el método Thread.join() permite sincronizar ambos sucesos
Informática III Ing. José L. Simón Pág. 1
Control de Servicios
En numerosas aplicaciones un servicio dado puede optimizarse ‘ordenando’ los requerimientos de los clientes a fin de optimizar perfomance, por ejemplo, en la interface de r/w de discos, aplicando encolamiento y ‘thread´pools’
Informática III Ing. José L. Simón Pág. 1
Descomposición Paralela
Fork/Join Barreras
Son técnicas que permiten aprovechar la existencia de múltiples CPU's para la resolución de problemas decomputación intensiva, apuntando a mejorar la potenciay perfomance de la aplicación:
Informática III Ing. José L. Simón Pág. 1
Fork-Join
Aplica el principio de división de tareas y paralelismo Es utilizable cuando el algoritmo aplicable es 'descomponible' Plantea nuevos problemas asociados a la descomposición
Informática III Ing. José L. Simón Pág. 1
Barreras
En la descomposición paralela suelen darse situaciones donde para pasar a otra etapa de procesamiento es imprescindible esperar la terminación de un grupo de threads
Informática III Ing. José L. Simón Pág. 1
BarrerasEtapa1 Etapa2 Etapa3
sinc
roni
zaci
ón
sinc
roni
zaci
ón
Informática III Ing. José L. Simón Pág. 1
Bibliografia
Java Distributed Objects, Doug Lea, Addison-Wesley, segunda edición 1999 El Lenguaje de Programación Java, Arnold y Gosling, Addison-Wesley