Informática III - Inicio - Departamento de Sistemas e ... · thread por cada tarea puede implicar la creación de un gran número de threads La técnica es asignar threads por eventos,

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


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


Soporte de concurrencia en hardware

Multiprocesamiento: SMP, múltiples unidades de ejecución. Multiprogramación: multithreading simultáneo Grids


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


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


Concurrencia vs. paralelismo

Tareas Tareas

Plataformamonoprocesador

PlataformaSMP


Complejidad y concurrencia

Competencia por recursos Bloqueos y deadlocks Planificación Optimización de perfomance


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


Propiedades requeridas

Seguridad Vitalidad Reusabilidad Perfomance


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’


Vitalidad

Una actividad nunca deja de mostrar comportamiento La falta de esta propiedad hace que los objetos ‘no funcionen’


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


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


Aseguramiento de Sistemas Concurrentes

Exclusión

Inmutabilidad

Sincronización


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.


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


Exclusión

Inmutabilidad Sincronización Adaptadores Locks


Inmutabilidad

El objeto nunca cambia de estado (sólo lectura) Tipos abstractos de datos Representaciones de valores


Sincronización

Mutex Semáforos Latches


Mutex (exclusión mutua)

try{mutex.adquirir();try{

/* tareas...*/}finally{

mutex.liberar();}

} catch( InterruptedException e ){...

}


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


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’


Control de Estado

Fallas y excepciones Guarda Estados y confinamiento Control de concurrencia Transacciones


Fallas y Excepciones

Objeto

Mensaje(método + parámetros )

Respuesta

Precondiciones Invariantes + Poscondiciones

Excepciones


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


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


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.


Tratamiento de Fallas

Terminación abrupta (muerte súbita) Continuación Rollback Rollforward Reintento


Creación de Threads

Mensajes unidireccionales Servicios Descomposición paralela Objetos activos


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


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


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


Mensajes Unidireccionalescliente

Atributos y Conexiones

aceptarmensaje

Accion(){ actualizarEstado(); enviarMensajes();}

helper

objeto host


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


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


Worker Threads

cliente servidor

canal worker

helper

pedido

encolar

tomar


Colas de Eventosaplicación

generarEvento();... evento

eventoeventoevento

cola deeventos

for(;;){ tomarEvento(); despachar(); ...}

despacho


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.


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


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


Servicios

Callbacks Join Control de Servicios


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


Callbacks

Cliente

Servidor

Helper

t2: Notificación

t0: Pedido

t1: Pedido


Join

Cuando un thread A debe esperar la finalización de otro B, el método Thread.join() permite sincronizar ambos sucesos


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’


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:


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


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


BarrerasEtapa1 Etapa2 Etapa3

sinc

roni

zaci

ón

sinc

roni

zaci

ón


Bibliografia

Java Distributed Objects, Doug Lea, Addison-Wesley, segunda edición 1999 El Lenguaje de Programación Java, Arnold y Gosling, Addison-Wesley

Documents

Informática III - Inicio - Departamento de Sistemas e ... · thread por cada tarea puede implicar la creación de un gran número de threads La técnica es asignar threads por eventos,