Aunque cada paquete de hilos puede tener una implementación distinta, existen dos formas básicas de implementación de los hilos, y una forma mixta :
El paquete se implementa en el espacio de usuario, sin que el núcleo conozca su existencia. El núcleo sigue manejando procesos con un único hilo.
Los hilos se ejecutan en la parte superior de un sistema de tiempo de ejecución, que consiste en un conjunto de procedimientos que gestionan los distintos hilos. Cuando un hilo ejecuta una llamada al sistema, se bloquea (duerme), realiza una operación en un mútex, o realiza alguna acción que provoca su suspensión, en realidad llama a un procedimiento del sistema de tiempo de ejecución. Este procedimiento es el que verifica si se debe suspender el hilo. En ese caso, almacena los registros del hilo en una tabla, localiza un nuevo hilo no bloqueado para ejecutar, y restaura los registros del nuevo hilo a partir de los valores almacenados en la tabla. Se establecen también los valores del puntero de pila y de programa, y entonces el hilo vuelve a ejecutarse.
Si la máquina tiene una instrucción para almacenar los registros y otra para cargarlos, entonces todo el intercambio de hilos se puede realizar en una sola operación. Esta conmutación entre hilos es muy superior, en velocidad, a la conseguida si el intercambio se realizase a nivel del núcleo.
En un sistema operativo que soporta hilos a nivel de usuario, una aplicación puede ser 'multithreaded', esto es, múltiples hilos de ejecución pueden existir dentro de un proceso. Normalmente, una limitación de los hilos de usuario es que sólo un hilo, representando una porción de todo el programa, puede ejecutarse en un momento dado. Cuando un proceso formado por hilos es planificado, el contexto de un hilo de usuario se enlaza con el proceso, y el proceso ejecuta dicho hilo. Si un hilo se bloquea o finaliza, otro hilo del mismo proceso puede ser planificado en su lugar, con lo cual no se pierde el quantum de tiempo asignado.
Los hilos de usuario pueden ser creados por programadores de aplicaciones usando los APIs de hilos proporcionados por una biblioteca de hilos. Estos APIs permiten a los programadores crear, finalizar, y sincronizar los hilos de un proceso. La librería de hilos puede también contener un planificador para los hilos de usuario. Los hilos de usuario no son directamente visibles por el kernel, son visibles sólo en el espacio de usuario. Así pues, un hilo de usuario debe estar asociado con un entidad del kernel planificable (como un proceso) para tener acceso al procesador. En este modelo, los procesos, no los hilos, son las entidades planificables por el núcleo.
Una definición de los hilos de nivel usuario se puede encontrar en el dicho "muchos a uno". Esta definición se deriva de la naturaleza de la implementación, pues varios hilos pueden existir en un proceso, pero sólo uno se puede ejecutar en un momento dado.
Las principales ventajas de un paquete de hilos a nivel de usuario son :
En este tipo de paquetes el núcleo gestiona los hilos. No se necesita un sistema de tiempo de ejecución como en el caso de los hilos a nivel de usuario.
Para cada proceso el núcleo tiene una tabla con una entrada por cada uno de los hilos del proceso, con los registros, estado, prioridades y otra información sobre cada hilo. La información es la misma que en los hilos a nivel de usuario, sólo que ahora se encuentra en el espacio del núcleo y no en el espacio de usuario (dentro del sistema de tiempo de ejecución), por lo cual está limitado. Las llamadas que pueden bloquear un hilo se implementan como llamadas al sistema, lo que supone un mayor coste que en el caso de nivel de usuario, donde se realizaban llamadas a un procedimiento del sistema de tiempo de ejecución.
Si un hilo se bloquea, el kernel puede decidir entre ejecutar otro hilo del mismo proceso (si alguno está listo) o un hilo de otro proceso. En cambio en los hilos a nivel de usuario, el sistema de tiempo de ejecución mantiene en ejecución los hilos del propio proceso hasta que el kernel les quita la CPU, o bien no existan más hilos del proceso listos para la ejecución.
En un sistema operativo con soporte de hilos a nivel del kernel, los procesos no son entidades planificables, sino que son los hilos las entidades planificables y los procesos son sólo contenedores lógicos para los hilos. De esta forma, si una aplicación se está ejecutando, cada hilo de un proceso puede ejecutarse en un procesador diferente, ya que el núcleo es capaz de planificar los hilos individualmente.
Los hilos a nivel del núcleo son creados por la librería de hilos empleando llamadas al sistema de gestión de hilos del núcleo. Estas llamadas al sistema permiten a la biblioteca de hilos crear, finalizar y sincronizar los hilos del núcleo. Los hilos del núcleo son visibles tanto por el núcleo como por la librería de hilos. El núcleo planifica y gestiona estos hilos según sus propias necesidades y las necesidades de los servicios del núcleo.
Existen dos formas de hilos a nivel de núcleo en una implementación mixta :
- Un hilo del núcleo por cada hilo de usuario.
- Múltiples hilos de usuario multiplexados en un sólo hilo del núcleo.
- Cualquier número de combinaciones.
Este modelo soporta proceso paralelo, por ser un
modelo de hilos a nivel del núcleo.
Una de las principales ventajas de un sistema operativo que soporto hilos a nivel del núcleo es la posibilidad de ejecutar el código de una aplicación multihilo concurrentemente en varios procesadores.
Las estructuras manejadas por el paquete de hilos deben estar protegidas para no ser modificadas de forma inconsistente durante la gestión de eventos asíncronos o señales. Para ello, la implementación del paquete debe garantizar que la ejecución de las secciones críticas del código del paquete sólo pueden ser ejecutadas por un hilo al mismo tiempo. Existen dos técnicas básicas para implementar la exclusión mutua dentro de la biblioteca de hilos :
Normalmente existen dos flags o variables especiales en la biblioteca de hilos :
Para salir del modo protegido, simplemente se desactiva el kernel flag si el dispatcher flag no está activado. En otro caso, se invoca el dispatcher, que puede provocar un cambio de contexto a otro hilo, y permite gestionar señales recibidas mientras se está en modo protegido.
En la mayor parte de los paquetes, el envío de señales de nivel proceso a los hilos está fuertemente relacionado con el dispatcher. En particular, las señales recibidas mientras se está en modo protegido son gestionadas de forma diferente que las señales recibidas mientras se está en modo usuario, aunque comparten un gestor universal de señales a nivel proceso, que es establecido durante la inicialización del paquete de hilos para todas las señales enmascarables del sistema :
a) Gestión en modo usuario : Cuando una señal es capturada por el gestor universal y el kernel flag no está activado (se está en modo usuario), se entra en modo protegido activando el kernel flag, todas las señales son habilitadas, y se llama a una rutina que primero dirige la señal al hilo apropiado y después llama al dispatcher. El control puede que no regrese inmediatamente al hilo interrumpido si la señal hace que el hilo destinatario de mayor prioridad, sea seleccionado por el planificador para su ejecución.
b) Gestión en modo protegido : Cuando una señal es capturada por el gestor universal y el kernel flag está activado (se está en modo protegido), la señal recibida es anotada y su gestión es diferida hasta que se llama al dispatcher. El control es devuelto inmediatamente al punto del hilo interrumpido regresando del gestor universal, que previamente habilita nuevamente las señales a nivel de proceso.
Bajo circunstancias normales, una llamada al dispatcher seleccionará el siguiente hilo elegible para ejecución del conjunto de hilos listos de acuerdo con la política de planificación. Si el hilo seleccionado es distinto del hilo actual en ejecución se realiza un cambio de contexto, que implica las siguientes acciones :
Cuando se va a ejecutar un hilo que no fue interrumpido por una señal, el contexto es conmutado al estado local del nuevo hilo. Antes de que el control sea transferido al nuevo hilo, el kernel flag y el dispatcher flag son desactivados y se comprueba si se recibieron señales mientras se estaba en modo protegido. Si no se recibieron señales, el control es transferido al nuevo hilo ; en otro caso, las señales son gestionadas y se produce otro intento de ejecutar un hilo. Como la gestión de señales puede cambiar el hilo a ser ejecutado a continuación, el cambio de contexto debe ser reiniciado.
Cuando se va a ejecutar un hilo que fue interrumpido
por una señal, el gestor universal de señales permanecerá
pendiente en la cima de la pila del hilo. Por lo tanto, el gestor
deshabilita todas las señales antes de realizar el cambio
de contexto. Cuando el hilo retome el control retornará
del gestor universal, habilitará todas las señales
de nuevo y regresará al marco de interrupción del
sistema operativo que restaurará el estado global (registros,
palabra de estado, etc.). Es imprescindible deshabilitar las señales
antes de cambiar al contexto de un hilo interrumpido para evitar
un crecimiento ilimitado de la pila, ya que de otra forma, el
gestor universal podría ser interrumpido por una nueva
instancia de gestor universal antes de que el hilo pudiese regresar
de la primera instancia, y así sucesivamente.
Las señales de nivel proceso que fueron capturadas en modo protegido son diferidas hasta que es llamado el dispatcher, en otro caso son gestionadas inmediatamente. La gestión de la señal implica determinar el hilo receptor y la acción a realizar para la señal. El receptor es determinado de acuerdo con el modelo de envío de señales, que describe cuando un hilo recibe una señal y como se resuelven los conflictos entre múltiples hilos.
A continuación se presenta el modelo de resolución de conflictos empleado en el paquete Pthreads de Frank Mueller y también en el paquete Pthreads de Chris Provenzano :
En dichos paquetes, si un hilo es seleccionado como receptor de una señal, se elige una acción a realizar de la siguiente forma :
Los gestores de señales de hilo (gestores de usuario) instalados mediante una llamada a sigaction son invocados a través de un mecanismo de llamada falsa o fake call. Una llamada falsa introduce un entorno en la pila y establece el entorno para que actúe como si el hilo hubiese llamado explícitamente a una función.
La utilización de las llamadas falsas como mecanismo para invocar gestores de usuario está motivado por la restricción que obliga a que los gestores de usuario sean ejecutados con el nivel de prioridad del hilo correspondiente. Por lo tanto, en vez de realizar una llamada explícita al gestor de usuario cuando se recibe una señal de proceso, la ejecución del gestor de usuario es diferida hasta que el hilo receptor sea ejecutado.
Básicamente el mecanismo es el siguiente :
Los mútex deben ser implementados para proporcionar exclusión mutua de la forma más eficiente posible. Idealmente, una instrucción atómica del tipo Test-and-SeT (TST) debería ser suficiente para su implementación, pero desafortunadamente esto no es suficiente y produciría algunas deficiencias :
El protocolo de herencia de prioridad requiere que si un hilo de mayor prioridad se suspende en un mútex debido a la espera por un hilo de menor prioridad que posee el mútex, el hilo de menor prioridad hereda la mayor prioridad hasta que se desbloquea el mútex. De esta forma, la asociación de propiedad de un mútex permite que un hilo de mayor prioridad incremente la prioridad del hilo que posee el mútex. Existen varias formas de implementación para guardar el propietario de un mútex de forma atómica junto al bloqueo del mútex.
Se garantiza que una secuencia atómica reiniciable es atómica aumentando el gestor de señales. Si dicha secuencia fue interrumpida por el gestor de señales, la secuencia atómica es reiniciada en el gestor de señales ; en otro caso no se realiza ninguna acción. Para la implementación del bloqueo de un mútex, debe garantizarse que existe un propietario asociado con cada mútex bloqueado en todo momento.
Este esquema no es extensible a un sistema multiprocesador. En este caso, las instrucciones TST son imprescindibles ya que son la única forma de garantizar actualizaciones atómicas en la memoria. Pero todavía se pueden emplear las secuencias atómicas reiniciables para grabar la propiedad junto con las instrucciones TST, permaneciendo en el bucle de espera del hilo hasta que se haya pasado el intervalo limite entre el bloqueo del mútex y el establecimiento del propietario, para el hilo que adquiere el mútex.
Existen numerosos problemas a la hora de implementar un paquete de hilos. Algunos problemas son específicos de una implementación de nivel usuario, ya que se intenta que el sistema operativo esté involucrado lo menos posible. Otros problemas son inherentes a la implementación en sí, independientemente del nivel. Algunos problemas son más fáciles de resolver, otros no tanto y son resueltos de formas distintas según la implementación. Además, la adopción del estándar POSIX Thread no resuelve todos los problemas de implementación, ya que el estándar deja muchos detalles libres a la implementación concreta.
A pesar de su mejor rendimiento, los paquetes que implementan hilos a nivel de usuario presentan importantes problemas:
1) La implementación de las llamadas al sistema con bloqueo: Los sistemas operativos sin soporte de hilos no suelen proporcionar llamadas al sistema sin bloqueo, equivalentes a las llamadas con bloqueo empleadas habitualmente.
Si un hilo realiza una acción que produce un bloqueo, en una implementación a nivel de núcleo, el hilo realiza una llamada al kernel, y éste bloquea el hilo e inicia otro; en cambio, en la implementación a nivel de usuario, no se puede permitir que el hilo realice directamente la llamada al kernel ya que suspendería todo el proceso, es decir, todos los hilos del proceso. Se debe pues permitir que todos los hilos realicen llamadas con bloqueo, pero evitando que un hilo bloqueado afecte a los demás. Empleando llamadas al sistema con bloqueo no se podría conseguir este objetivo.
Una solución consiste en modificar las llamadas al sistema para que no utilicen el bloqueo, pero esto es complicado, pues se deben realizar cambios en el sistema operativo, y se perdería precisamente una importante ventaja de los hilos a nivel de usuario, como es su implementación en sistemas operativos ya existentes.
Existe otra solución cuando se puede conocer a priori si una llamada se bloqueará. En algunas versiones de UNIX existe una llamada select que realiza esta consulta. Se puede, entonces, reemplazar el procedimiento de biblioteca, por ejemplo, read por otro que primeramente realice la llamada al sistema select y después realice la llamada al sistema read sólo en caso de que se tenga garantía de no bloqueo. Si la llamada read se va a bloquear (lo cual se conoce mediante la llamada select) no se realiza y se ejecuta otro hilo del proceso. En la siguiente ocasión que el sistema de tiempo de ejecución obtiene el control, puede volver a intentar la llamada read (verificar si habrá o no bloqueo). Este método necesita que se reescriban parte de los procedimientos de biblioteca de las llamadas al sistema, es algo ineficiente y poco elegante, pero no existen muchas más soluciones al respecto. El código encargado de realizar la verificación de la llamada, que se coloca junto con la llamada al sistema, se suele llamar jacket.
Marsh and Scott [MAR91] han realizado algunas sugerencias para resolver algunos problemas asociados con los hilos de nivel usuario, definiendo un interfaz genérico entre el kernel del sistema operativo y el nivel de usuario, que proporciona una comunicación rápida entre las actividades de ambos niveles. Así por ejemplo, cuando se produce una solicitud de E/S sin bloqueo, el kernel asocia la solicitud con un dato (el hilo que realiza la llamada), de forma que el planificador de hilos de nivel usuario pueda ser notificado de que la operación de E/S se ha completado. Gracias a este dato se elimina la necesidad de demultiplexar la señal en el nivel de usuario con lo cual se incrementa la respuesta a eventos asíncronos de forma considerable sin complicar indebidamente el kernel del sistema operativo.
2) Ejecución paralela de hilos del mismo proceso: Otro problema con los paquetes de hilos a nivel usuario es que cuando un hilo comienza su ejecución, el resto de los hilos del proceso no puede ejecutarse, a menos que el primer hilo libere voluntariamente la CPU, mientras que en los paquetes de nivel kernel pueden ejecutar varios hilos del mismo proceso de forma paralela. En los paquetes a nivel de núcleo, el planificador se ejecuta periódicamente debido a las interrupciones de reloj, y se permite la planificación round-robin, a diferencia del paquete a nivel usuario, en el que en un único proceso no existen interrupciones del reloj, imposibilitando la planificación round-robin, y la única oportunidad que tiene el planificador de ejecutarse es que un hilo entre en el sistema de tiempo de ejecución por voluntad propia. Una posible solución sería que el sistema de tiempo de ejecución solicite una señal al reloj (interrupción) por cada segundo con el fin de obtener el control, pero esto resulta en una programación problemática, y además puede interferir con una interrupción empleada para un hilo.
3) Aplicaciones de bloqueo: Las aplicaciones en las que es más interesante el uso de hilos son aquellas donde los hilos se bloquean habitualmente, ya que realizan continuas llamadas al sistema. Si los hilos del proceso están bloqueados, como el único trabajo que realiza el sistema de tiempo de ejecución es conmutar entre hilos, pero todos los hilos del proceso se encuentran bloqueados, no hay razón para verificar la seguridad de las llamadas al sistema, sino que lo que interesaría sería devolver al control al kernel, para que planificase otro proceso, mientras tanto.
4) La inversión de prioridades es difícil de resolver. La combinación de prioridades y secciones críticas puede causar un fenómeno llamado inversión de prioridad, una situación en la cual un hilo de mayor prioridad no puede expulsar a otro de menor prioridad que ejecuta su sección crítica. La inversión de prioridad puede provocar retrasos largos e inaceptables en aplicaciones de usuario o microkernel multihilo. Además, no permite garantizar las restricciones de tiempo impuestas por los sistemas de tiempo real. Por otro lado, implementar la herencia de prioridades supone un gran esfuerzo en el caso de un mútex compartido entre hilos de procesos diferentes, ya que sería necesario establecer alguna forma de comunicación entre las bibliotecas de ambos procesos.
5) Primitivas de sincronización globales : La mayoría de las implementaciones de bibliotecas de hilos de nivel usuario carecen de mútex y variables de condición compartidos que puedan ser utilizados entre procesos, aunque el estándar POSIX Threads los define. Estos objetos pueden ser implementados de dos formas :
6) Aumento del rendimiento : En la mayoría de las implementaciones, la obtención del espacio para la pila y el contexto o bloque de control del hilo (Thread Control Block, TCB) lleva el 70% del tiempo empleado en su creación. Esta velocidad de creación puede aumentarse si el paquete posee una zona de memoria para TCBs y pila, que es empleada durante la creación de los hilos.
Existen problemas de implementación que afectan tanto a los hilos a nivel usuario como a los hilos a nivel núcleo, y que cada paquete concreto ha resuelto de forma particular. Los principales problemas son los siguientes :