Multithreading
De Codepixel
Contenido |
[editar] Conceptos
- Computación en paralelo : conceptos sobre la programación en paralelo, las dependencias y las formas de sincronizar los datos.
- Thread : un hilo, desde el punto de vista del sistema operativo.
- Categoría de hilos : lista de temas sobre hilos, orientado al sistema operativo.
- Sincronización : Algoritmos para que varios hilos se ejecuten de forma coordinada.
- Mutex : objeto de exclusión mútua.
- Lock : tipos de bloqueos.
- Spin Lock : bloqueo usando un bucle y una operación atómica.
- Lock Convoy : problema de rendimiento cuando muchísimos bloqueos están activos, gastando cambios de contexto.
- Evento : objeto para señalizar operaciones.
- Semáforo : objeto para sincronizar hilos.
- Monitor : objetos que encapsulan a los semáforos, y permiten la operacion wait/signal.
- Barrera : objeto que fuerza a todos los procesos a esperar.
- Productor/Consumidor : problemas cuando un thread genera información, y otro la procesa.
- Concurrencia : lista de temas sobre la concurrencia en general.
- Control de Concurrencia : lista de temas sobre el control de la concurrencia.
- Algoritmos de control de Concurrencia : lista de los algorimos de control.
- Inter Process Communication : métodos del SO para comunicar procesos.
- Threaded Code : código generado por el compilador, como el usado en OpenMP
- Cola de mensajes : sistema para comunicar de forma asíncrona.
- Critical path : algoritmo para determinar el camino más importante en un conjunto de datos con dependencias.
- Fibras : fibras permiten ejecutar co-rutinas, que es un metodo ordenado de procesamiento multitarea (no pre-emptivo). Quiere decir que es el programa quién gestiona el cambio de contexto. Útil para implementar actores en un videojuego, por ejemplo.
[editar] Monitores
El patrón Monitor es uno de los más importantes en la programación concurrente. Permite diseñar accesos a recursos de forma coordinada.
- Monitors: an operating system structuring concept : uno de los papers más referenciados sobre sincronismo. Desarrolla el concepto de monitor para programación.
- xperience with Processes and Monitors in Mesa : una mejora con el método broadcast.
- A Fair Monitor (Condition Variables) Implementation for Win32 : una clase bien documentada sobre monitores en win32
- Implementing a Thread-Safe Queue using Condition Variables : un ejemplo para implementar una cola que espera resultados, usando las condiciones de la boost.
[editar] Referencias
- Symposium on Principles and Practice of Parallel Programming : referencia para publicaciones.
- Concurrent Programming Concepts : una explicación sobre conceptos que deben y no deben ser usados en programación concurrente.
- Strategies for Implementing POSIX Condition Variables on Win32 : patrones usados en la boost.threads.
- Dr Dobb's Go Parallel : lista de multitud de arículos sobre concurrencia.
- Herb Sutter : escribe sobre concurrencia, autor del libro "Effective Concurrency".
- artículos de Herb Sutter :lista de articulos de la DrDobb's. Imprescindibles.
- Game Engine - Multi-Threading Programming Resources. Compendio de enlaces sobre multi-threading.
[editar] Estructuras concurrentes
- Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms : para implementar tipos de datos sin bloqueos en un entorno multitarea.
- Strategies for Implementing POSIX Condition Variables on Win32 : cómo implementar condition variables, que dan problemas en win32 (en vista hay la primitiva Condition Variable)
- boost/condition : condition variables en la boost y una explicación de cómo funcionan.
[editar] Work Queue
- Effective Concurrency: Writing a Generalized Concurrent Queue : completa lista de artículos que hablan de cómo desarrollar código concurrente y óptimo.
- Thread Pool Pattern : patrón thread pool, con enlaces a más artículos.
- fiber class : implementación de un scheduler con fibras, para una mayor velocidad de intercambio de contexto.
[editar] Work Stealing
En máquinas con muchos procesadores, una cola tiene muchos problemas de localidad y de contención. Es probable que tareas que se han creado juntas, salten entre procesadores, creando mucha polución en la cache, y muchos cache miss innecesarios. Al tener una cola global para decenas o cientos de procesadores, se gastan muchos recursos en bloqueos y señales.
Otra forma de repartir trabajo es usar work stealing. Se basa en tener 1 cola por procesador. Cuando un trabajo hace spawn de varias tareas, todas las tareas van a su misma cola. Cuando un procesador se queda sin tareas, "roba" tareas de otras colas. Esta forma de trabajar es mucho más eficiente cuando tenemos sistemas que utilizan memoria compartida, como los procesadores modernos de intel/amd.
Este es el modo que actualmente prefieren empresas como microsoft o intel para su gestión de tareas, ya que es más efeciente cuando el número de procesadores crece. La librería de intel, threading builing blocks, usa una política similar.
La base principal de investigación es el Cilk, una extensión de C, desarrollada en el MIT, que lanza tareas en paralelo. Tiene una amplia documentación sobre cómo distribuir tareas.
- Scheduling Multithreaded Computations by Work Stealing : paper original.
- "How to Survive the Multicore Software Revolution (or at Least Survive the Hype)" : ebook sobre paralelismo de click.
- Microsoft Directions in Parallel Computing and Some Short Term Help : benchmarks que muestran la eficiencia de esta técnica.
- annotated bibliography : lista de referencias, con comentarios.
- General purpose task parallel threading approach : extenso y completo hilo de discusión comparando técnicas de paralelismo, orientado a videojuegos.
- Work stealing and implementation of runtime systems : comparativa de 5 implementaciones.
- Dynamic circular work-stealing deque : una implementación usando deques.
- Idempotent work stealing : una implementación con ciertas premisas, que la hacen más rápida.
[editar] Librerías
- tutorial de pthreads : con ejemplos de cómo se usa la librería de posix threads.
- Further Threads Programming:Synchronization : usando pthreads para bloqueos.
- tutorial de pthreads : más ejemplos y tutoriales.
- thread : en java.
- util.concurrent : documentación sobre unas clases en java que implementan cosas útiles para multitarea, como semáfos, barreras, sincronismos, thread pools, etc. Ideal para sacar ideas sobre una implementación completa.
- zthread : otra librería en c++, un poco más ligera que las demás.
[editar] Boost.Thread
La librería boost incluye una implementación para objetos que está bastante documentada y estudiada en muchos papers. Un objeto thread no contiene el thread, si no que es una forma de comunicarse con el hilo. Un objeto thread puede desligarse del hilo y morir, sin matar el hilo.
- boost.thread : manual de la versión 1.40.
- Introduction to Design : un resumen de las opciones que se tomaron al diseñar la librería.
- rationale : principios de diseño.
- scoped lock : explicación de este concepto en los objetos que bloquean.
- mutex : explicación sobre el concepto de mutex.
- interruption : qué es, y cómo usar la interrupción de hilos.
- Dr. Dobb's : sobre la libería boost.thread.
- a threading api : ideas para mejorar la boost.
