Barrapunto

Me resulta curioso que sorprenda una típica implementación de "test and set" :-)

Más que por la implementación de "mutexes" (multithread, intraproceso), la programación multithread me resulta especialmente compleja dado lo toscos que resultan los planificadores de threads/procesos de los sistemas operativos (incluso en el caso de RTOS, aunque en menor medida), sobretodo cuando hay muchos threads haciendo cálculo, donde un "quantum" de 10ms se vuelve eterno y con más de 20 threads de ese tipo, provocan que el planificador se torne ineficaz incluso a la hora de hacer E/S en otros threads (los threads de cálculo tienen prioridad sobre los de E/S, obviamente).

Cualquiera que haya trabajado con muchos threads de manera concurrente, sabe lo desastrosos que son los sistemas operativos al respecto de repartir tiempos, y que se le ha de "echar una mano" para que funcione con un reparto equitativo y predecible. Medidas útiles en el "mundo real" acerca de la programación multithread, resolución de colisiones, reparto de carga:


a) ["demasiado cálculo para el body"] Si hay muchos threads de cálculo ejecutándose de manera concurrente, tener en cuenta el "quantum" del sistema operativo (tiempo máximo para cálculo antes de que te interrumpa el "timer" mediante una IRQ hardware, depende del TICS_PER_SEC del S.O., normalmente de 100Hz a 3KHz). A mí me gusta que el equilibrio donde el número total de threads haciendo cálculo multiplicado por el "quantum", sea inferior a 0.5 segundos. Para devolver el "testimonio" de cálculo, se puede optar por:

- sched_yield() para POSIX (o SleepEx(0, TRUE) para Windows): devuelve el control si hay algún otro thread en estado "ready to run", si no, continúa con el thread en curso, hasta llegar al sobrepasar el "quantum" (no rearma el timer del quantum). Dependiendo del sistema operativo, el mero hecho de tener demasiados threads en estado "ready to run" puede poner en apuros al planificador (si hace un "round robin" estricto, hay pocos problemas, pero ojo con tocar la prioridad, pues puede desenvocar en un caso de "inversión de prioridades" que haga ir al sistema a trompicones). Haciendo una buena previsión para repartir el tiempo de ejecución, podemos tener bajo un kernel a 100Hz aplicaciones con cientos de threads que se comporten de manera muy suave, como si tuviesen un kernel a 10KHz (hace ligeramente más complejas las implementaciones, pues en lugar de concentrarte en el problema, tienes que tener en cuenta siempre al SO).

- sleep(0) para POSIX (o Sleep(0) para Windows): devuelve el control durante al menos un "quantum" (dependiendo del planificador, pasará a estar en alguno de los estados de "sleep"/"wait" o algún "pseudo ready to run").

b) ["muchos thread haciendo poco con un alto grado de concurrencia, con un alto grado de transacciones por segundo sostenidas"] Si los threads comparten datos, normalmente me he encontrado con dos grupos de casos:

- Productor / consumidor: hay threads que producen, dejan el resultado en una cola, y sólo se paran hasta llegar al límite del buffer. En este caso no hay problemas de exclusión mútua. Sería el caso análogo para threads que se usa entre procesos mediante "pipes", y los resultados son muy buenos, pero en el caso de datos independientes, claro (prácticamente no hay colisiones, sólo reparto de carga entre threads).

- Acceso a datos compartidos para transacciones diferentes: en este caso pueden existir zonas de sólo lectura, de lectura/escritura, susceptibles de ser cambiadas por cualquier thread. La solución obvia es añadir "mutexes" ("critical sections") para serializar el acceso... craso error: es MUY LENTO, dado que se acaba siendo código "mono thread", usando sólo una de las CPUs disponibles. Soluciones, dependiendo del problema en cuestión (no son válidas para todos los problemas):

- [Importando el orden] Planificador de trabajos: mediante fragmentación del espacio de soluciones, llegando incluso a usar BSPs [wikipedia.org] para bloquear sólo áreas concretas. La planificación funciona de manera similar a como operan los planificadores de los pipelines de las CPUs modernas con ejecución fuera de orden: los trabajos planificados, se empiezan ejecutar de manera concurrente, frenando sólo los que incurran en dependencias (similar al planificador de un SO sencillo).

- [Si no importa el orden] Proceso orientado por eventos: abstraer las tareas en mensajes con directrices, incluyendo dependencias, descripción de las operaciones a ejecutar, etc. En este caso queda una especie de "Tetris", al cual van llegando las piezas al pool de threads correspondiente.

El diseñar adecuadamente un sistema, a menudo reduce el problema de las colisiones. El diseño anárquico típico de "todos los threads acceden a todo de cualquier manera", es de lo más común, desafortunadamente (¡Ponle un procesador más gordo, Pepe!).

Me resulta curioso que sorprenda una típica implementación de "test and set" :-)

Como le he contestado al PH anterior lo que me ha gustado es que lo explicaba de un modo simple y con código, de arriba a abajo, apto para todos los públicos y con unas cuantas referencias...

Cualquiera que haya trabajado con muchos threads de manera concurrente, sabe lo desastrosos que son los sistemas operativos al respecto de repartir tiempos,[...] Medidas útiles en el "mundo real" acerca de la programación multithread, resolución de colisiones, reparto de carga:[...]

Interesante. De todos modos, cuando tienes demasiados threads lo que tienes es un problema, que a veces te has podido buscar tú mismo ;) Otras no, claro, y el problema te exige más. Por cierto que todo lo que hablas me suena al Parallel Programming Patterns [uiuc.edu] del que hablaba en la entrada anterior [barrapunto.com]... ;) (Quitando el tema de los timeslices o quanta)

Cualquiera que haya trabajado con muchos threads de manera concurrente, sabe lo desastrosos que son los sistemas operativos al respecto de repartir tiempos, y que se le ha de "echar una mano" para que funcione con un reparto equitativo y predecible.

No te voy a quitar razón, pero es asi inherentemente. Como todo hay un balance, este entre interactividad y tiempo de proceso. Tambien se perfila para una carga tipica, y cientos de hilos no lo son. Las ediciones de servidor casi lo soportan mejor, pero el diseñador del planificador no puede saber como se comportan tus hilos, asi que tienes que ser tu el que lo haga.

Aparte que toda esta mierda no son más que primitivas. Hay que estar loco, ser tonto o muy arrogante para intentar hacer algo serio con mutex y tal a pelo. Un framework al estilo de cilk condiciona pero hace lo inconmesurable en dificil.

El planificador de linux es realmente flexible, y con NOHZ se ha ganado, no viendote interrumpido para hacer nada.

Algun "guru" de windows puede informar si hay algo parecido a los distintos planificadores del nucleo que se pueden cambiar en caliente. Mi profesor de SO se partia el pecho cuando contaba que en windows para mantener la interactividad se establecio el quantum absurdamente pequeño. Algo asi como engañar pareciendo rapido al hacer click, siendo globalmente mas lento. Pero de eso hace años y supongo que los ultimos windows 200x server habra cambiado ¿no?