Multithreading

De Codepixel

Contenido

[editar] Libros

[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.

[editar] Referencias

  • Herb Sutter : escribe sobre concurrencia, autor del libro "Effective Concurrency".

[editar] Estructuras concurrentes

  • boost/condition : condition variables en la boost y una explicación de cómo funcionan.

[editar] Work Queue

  • fiber class : implementación de un scheduler con fibras, para una mayor velocidad de intercambio de contexto.

[editar] Concurrent I/O

[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.

[editar] Librerías

  • 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.
  • concurrency kit : lista de algoritmos "lockless" para multithreads, con una buena documentación y referencia a los papers usados.

[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.

  • 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.
Herramientas personales