INTRODUCCIÓN AL CONCEPTO DE HILO.

Las aplicaciones informáticas pueden ser de muchos tipos, desde procesadores de texto hasta procesadores de transacciones (bases de datos), simuladores de cálculo intensivo, etc.

Las aplicaciones están formadas de uno o más programas. Los programas constan de código para la computadora donde se ejecutarán. El código es generalmente ejecutado de forma secuencial. Normalmente, un "programa hilado" (threaded program, programa construido mediante hilos) tiene el potencial de incrementar el rendimiento total de la aplicación en cuanto a productividad y tiempo de respuesta mediante ejecución de código asíncrono y paralelo.

La ejecución de código paralelo se realiza mediante la ejecución de dos o más partes de un programa en dos o más procesadores en un instante dado. La ejecución asíncrona se puede realizar conmutando la ejecución del segmento de código actual que se bloquea por alguna razón, a otro segmento. Los hilos permiten al programador emplear estas características y muchas otras.

Otros beneficios de los hilos están relacionados con los recursos compartidos y el escaso tiempo empleado en su creación, terminación y cambio de contexto. Todo esto contribuye a incrementar el rendimiento de la aplicación así como conservar los recursos del sistema.

Cuando un programa se activa en el sistema, es decir está en ejecución o es candidato para la ejecución, se le conoce como un proceso. Cuando un proceso se encuentra activo, se le asignan una serie de recursos del sistema operativo para gestionarle, entre ellos una entrada en la tabla de procesos, un área de usuario, un contexto de registros único, memoria virtual, etc. La mayoría de los sistemas operativos sólo soportan procesos. Los procesos pueden ser vistos como una entidad "hilo simple", es decir, ejecutan sólo un flujo de instrucciones de una forma secuencial.

Los procesos son planificados para ejecución una y otra vez hasta que finalizan, es decir, el programa termina su tarea. Cuando es planificado, un proceso se ejecutará en un procesador durante un intervalo de tiempo llamado quantum de tiempo. Un quantum es simplemente la cantidad de tiempo que el proceso tiene permitido para su ejecución antes de que el sistema operativo compruebe si existe un proceso de mayor prioridad listo para la ejecución. Un nuevo proceso es planificado para ejecución en lugar del proceso actual cuando :

  1. El quantum de tiempo del proceso actual finaliza.
  2. El proceso actual se bloquea, duerme, finaliza, o es desalojado.

Siendo un hilo simple, una aplicación puede ejecutarse sólo en un procesador en un instante dado y sólo puede ejecutarse de forma secuencial. Una forma de incrementar la velocidad de ejecución de un programa secuencial sería dividir el trabajo entre múltiples procesadores. Es aquí donde los hilos resultan útiles.

En los sistemas operativos tradicionales, cada proceso tiene un espacio de direcciones y un único hilo de control (contador de programa). Es lo que normalmente se entiende por proceso. Sin embargo, existen ocasiones en las que sería conveniente que dos procesos trabajasen de forma concurrente pero con una serie de datos comunes. Este problema es difícil de resolver normalmente, ya que los procesos son independientes y la comunicación de los datos debe realizarse mediante algún mecanismo de comunicación entre procesos (IPC), como pueden ser: semáforos, memoria compartida, paso de mensajes, etc. Pero parece claro que se introduce una cierta complejidad en la resolución de este tipo de problemas.

Una solución que parece razonable consistiría en que los "procesos" compartiesen el espacio de direcciones (la memoria), de esta forma no sería necesario su intercomunicación, ya que todos tendrían acceso a la misma zona de memoria. Se plantean sin embargo otros problemas, como es el acceso concurrente a una misma posición de memoria, evitando los problemas de inconsistencia de datos.

El significado exacto del término thread no está acordado. Uno de los usos más habituales denota a procesos ligeros (con flujo de control secuencial) que comparten un espacio de direcciones y algunos otros recursos, y para los cuales el tiempo empleado en el cambio de contexto es mucho menor que el empleado en los procesos pesados (procesos soportados por el kernel del sistema operativo).

Los hilos son flujos de control independientes dentro de un mismo proceso que comparten datos globales (variables globales, ficheros, etc.), pero poseen una pila, variables locales y contador de programa, propios. Se les suele llamar "procesos de peso ligero" porque su contexto es menor que el contexto de un proceso. Por lo tanto, los cambios de contexto entre hilos son menos costosos que los cambios de contexto entre procesos. Además, los hilos son un modelo adecuado para explotar el paralelismo en un entorno multiprocesador de memoria compartida.

La gestión de procesos es uno de los aspectos claves en el diseño de un sistema operativo. De la optimización de su funcionamiento depende en gran medida la buena utilización del sistema y sus recursos.

La historia de los hilos.

La noción de hilo, como flujo de control secuencial, se remonta al menos, al año 1965 [OSU96], con el sistema de tiempo compartido de Berkeley. Sólo que en aquel tiempo no fueron llamados hilos, sino procesos. Los procesos interactuaban a través de variables compartidas, semáforos, o mecanismos similares. Max Smith realizó un prototipo de implementación de hilos en Multics alrededor de 1970; usaba pilas múltiples en un proceso pesado simple para soportar compilaciones en background.

Sin embargo, el progenitor más importante de los hilos fue el lenguaje de programación PL/I, hacia el año 1965. El lenguaje, según fue definido por IBM, proporcionaba una instrucción del tipo CALL XXX (A, B) TASK; construcción que bifurcaba generando un hilo para XXX. No se sabe si algún compilador de IBM implementó esta característica, pero fue estudiado exhaustivamente mientras se estaba diseñando Multics; se comprobó que la llamada TASK como estaba definida no mapeaba en procesos, ya que no existía protección entre los hilos de control. Entonces Multics tomó una dirección diferente, y la característica TASK fue eliminada de PL/I por IBM.

Después vino UNIX, a principios de 1970. La noción UNIX de 'proceso' consistía en un hilo de control secuencial más un espacio de direcciones virtuales (esta noción derivó directamente del proceso de diseño de Multics). Así pues 'procesos', en el sentido de UNIX, son "máquinas pesadas". Ya que no pueden compartir memoria (cada proceso tiene su propio espacio de direcciones), interactuan a través de tuberías, señales, etc. La memoria compartida fue añadida a UNIX mucho más tarde.

Después de algún tiempo, los usuarios de UNIX comenzaron a echar en falta los viejos procesos que podían compartir memoria. Esto dio lugar a la "invención" de los hilos: procesos al "viejo estilo" que compartían el espacio de direcciones de un simple proceso UNIX. Se les llamó, entonces, procesos ligeros en contraste con los procesos pesados UNIX. Esta distinción se remonta a finales de los 70's y principios de los 80's, cuando comenzaron los desarrollos de los primeros microkernels: Thoth (precursor del V-Kernel y QNX), Amoeba, Chorus, la familia RIG-Accent-Mach, etc.

En relación con los paquetes de hilos, C Threads fue una de las implementaciones iniciales de hilos, nacida como una extensión del lenguaje C basada en corrutinas. Una implementación sencilla fue empleada por Cooper [COO88] como herramienta de enseñanza. Esta implementación original no gestionaba señales por hilo, y sólo soportaba planificación no preemptiva.

El primer sistema operativo comercial que implementó hilos fue Mach. Cooper construyó una implementación de C Threads basada en los hilos Mach que soportaba planificación preemptiva.

También existe una implementación anterior, realizada en Brown University [DOE87], de una biblioteca de hilos con planificación preemptiva, soporte de diversas arquitecturas (incluso multiprocesadores) y gestión de señales asíncronas.

Posteriormente, algunos sistemas operativos comerciales, como LynxOS o SunOS, implementaron alguno de los diversos borradores del estándar POSIX Threads, empleando un método mixto a dos niveles, basado en una biblioteca de nivel usuario y soporte >


Transfer interrupted!

tivos, como Chorus implementaron la mayor parte de la funcionalidad en el kernel, debido a sus requisitos de diseño.

Características de las implementaciones.

Se pueden distinguir dos tipos de implementaciones de los hilos : hilos a nivel de usuario y los hilos a nivel de kernel.

Un hilo a nivel de usuario mantiene todo su estado en el espacio de usuario. Como consecuencia de ello, el hilo no utiliza recursos del kernel para su gestión, y se puede conmutar entre hilos sin cambiar el espacio de direcciones. Como desventaja, los hilos a nivel de usuario no se pueden ejecutar mientras el kernel está ocupado, por ejemplo, con paginación o E/S, ya que esto necesitaría algún conocimiento y participación por parte del kernel.

Es posible combinar ambos métodos, como se hace en SunOS 5.x (Solaris 2.x). Aquí, uno o más procesos ligeros (light weight processes - LWPs) se ejecutan en multitarea mediante uno o más hilos de nivel usuario, que son implementados usando librerías en el espacio de usuario.

Algunas razones que caracterizan las implementaciones de hilos, y que determinan el uso que puede tener un paquete de hilos, son:

Algunos nuevos sistemas (QNX y Plan 9, por ejemplo) consideran que los hilos "resuelven el síntoma, pero no el problema". En estos sistemas se considera que en vez de usar hilos, ya que el tiempo de cambio de contexto del SO es demasiado lento, una mejor aproximación, es mejorar el SO en sí.

Parece irónico, que ahora que los SO para ordenadores de sobremesa incluyen multitarea en modo protegido, el modelo de programación de moda consiste en múltiples hilos ejecutándose en un espacio de direcciones común, haciendo el proceso de depuración más difícil, e incluso haciendo más difícil la generación de código fiable.

Con la ventaja de tener un rápido cambio de contexto, y existiendo servicios del SO, como la reserva explícita de memoria compartida entre un equipo de procesos cooperando, se puede crear un entorno de hilos, sin tener los problemas que se establecerían en un espacio de memoria totalmente compartida.

3.3. APLICACIONES DE LOS HILOS.

Algunos programas presentan una estructura que puede hacerles especialmente adecuados para entornos multihilo. Normalmente estos casos involucran operaciones que pueden ser solapadas. La utilización de múltiples hilos, puede conseguir un grado de paralelismo que incremente el rendimiento de un programa, e incluso hacer más fácil la escritura de su código. Algunos ejemplos son :

Algunas de estas técnicas pueden ser implementadas usando múltiples procesos. Los hilos son sin embargo más interesantes como solución porque :

Los hilos se crearon para permitir combinar el paralelismo con la ejecución secuencial y el bloqueo de llamadas al sistema. Las llamadas al sistema con bloqueo facilitan la programación, y el paralelismo obtenido mejora el rendimiento.

Ejemplo de servidor de archivos.

Consideremos el siguiente ejemplo de un servidor de archivos, en distintas implementaciones :

1) Servidor con varios hilos:

- El hilo servidor, lee las peticiones de trabajo del buzón del sistema.

- Examina la solicitud, y selecciona un hilo trabajador inactivo (bloqueado), al cual envía la solicitud mediante algún tipo de mensaje. Después el hilo servidor despierta al hilo trabajador dormido (por ejemplo, mediante un SIGNAL en el semáforo donde duerme).

- Cuando el hilo trabajador despierta, consulta la cache del bloque de memoria compartida entre todos los hilos, para verificar que puede dar servicio a la solicitud. Si no, envía una solicitud al disco para obtener el bloque de disco correspondiente (si se trata de una operación de lectura), y se duerme a la espera. Se llama al planificador, y se inicializa otro hilo, que podría ser el servidor para pedir más trabajo, o bien otro trabajador listo para realizar un trabajo. Pero veamos como se implementaría el servidor de archivos sin hilos.

2) Servidor con un único proceso (único hilo), en el cual el proceso servidor realiza todo el tratamiento cíclicamente:

- obtener una solicitud

- examinar el tipo de solicitud

- servir la solicitud, y volver al principio.

Mientras el proceso espera al disco, está inactivo y no procesa otras solicitudes. Si el servidor de archivos se ejecuta en una máquina dedicada, como suele ser habitual, la CPU estará inactiva, mientras se espera al disco, produciendo un menor número de solicitudes/sg. servidas. Así pues, los hilos aumentan el rendimiento de una forma importante, y sin embargo cada uno de ellos también se ejecuta de forma secuencial.

3) Servidor como máquina de estados finitos:

- obtener una solicitud

- examinar el tipo de solicitud

- Si se encuentra en la caché, perfecto, sino se envía un mensaje al disco, y en vez de bloquearse, se registra el estado de la solicitud actual en una tabla

- Después se consulta la tabla y se obtiene el siguiente mensaje, que puede ser una solicitud de un nuevo trabajo, o una respuesta del disco con respecto a una operación pendiente anterior.

- Si es un nuevo trabajo, se comienza su resolución. Y si es una respuesta del disco, se localiza la información necesaria en la tabla y se procesa la respuesta.

Como no se puede enviar un mensaje y bloquearse a la espera, no se puede utilizar RPC, así pues las primitivas deben ser del tipo send y receive sin bloqueo.

Sin embargo, en este diseño se pierde el modelo "de proceso secuencial" que teníamos en los casos anteriores. Necesitamos guardar el estado y restaurarlo en la tabla para cada mensaje enviado o recibido. En el fondo lo que estamos realizando es una simulación de varios hilos y sus pilas de una manera complicada. El funcionamiento es el de una máquina de estados finitos que obtiene un evento y reacciona según el estado en el que se encuentre.

Los hilos, por tanto, mantienen la idea de procesos secuenciales que realizan llamadas al sistema con bloqueo (por ejemplo, RPC), y sin embargo permiten el paralelismo. Las llamadas al sistema con bloqueo facilitan la programación, y el paralelismo mejora el rendimiento del sistema. En el 2º caso, el servidor de un único hilo emplea llamadas con bloqueo, pero tiene un bajo rendimiento al no conseguir el paralelismo. El 3º caso, logra un mejor rendimiento mediante el paralelismo conseguido por la máquina de estados finitos, pero emplea llamadas sin bloqueo que dificultan la programación.

Otras aplicaciones de los hilos.

Los hilos también pueden ser muy útiles en la implementación no sólo de procesos servidores, sino de procesos clientes. Por ejemplo, si un cliente quiere copiar un archivo en varios servidores, puede hacer que un hilo se comunique con cada servidor.

También se pueden emplear los hilos en el manejo de señales, como por ejemplo las interrupciones del teclado: se puede dedicar un hilo a la espera de señales, en vez de que éstas interrumpan el proceso. Normalmente, el hilo se bloquea a la espera de señales, y cuando se produce una señal, despierta y la procesa. Esto puede eliminar la necesidad de interrupciones a nivel de usuario.

Otra razón de peso que justifica la utilización de hilos, y que no tiene relación con las RPCs o la comunicación, se basa en que muchas tareas son más fáciles de programar mediante procesos paralelos, ya que tienen una naturaleza inherentemente paralela. Como ejemplo encontramos el problema del productor-consumidor. Este problema es de naturaleza paralela, ya que de esta forma es más fácil su diseño, al margen de que en la realidad el productor y el consumidor se ejecuten o no de forma paralela. Además, dada la necesidad de compartir un buffer común, este problema se adapta perfectamente al caso de los hilos.

Como última justificación, en un sistema multiprocesador, es posible que los hilos de un mismo proceso se ejecuten realmente en paralelo, en varias CPU. Un programa bien diseñado y que emplee hilos funcionará tanto en una CPU con hilos compartidos, como en un verdadero multiprocesador, lo que hace al diseño independiente de la implementación.

El empleo de los hilos en el desarrollo de aplicaciones puede tener la recompensa de incrementar el rendimiento de la aplicación. Un incremento en el rendimiento de la aplicación puede significar una ventaja competitiva, sin embargo la robustez de la aplicación y la portabilidad de la misma, han de tenerse también en consideración. Desarrollar aplicaciones robustas basadas en hilos es posible con un correcto entrenamiento y con herramientas que ayuden al mantenimiento del programa. Desarrollar aplicaciones portables será posible cuando la industria se ciña al nuevo estándar POSIX 1003.1c.

3.4. ORGANIZACIÓN DE LOS HILOS DE UN PROCESO.

Otra forma de estudiar las posibilidades de emplear los hilos es pensar en términos de modelos de programación. La programación multihilo es especialmente útil en algunos modelos de programación.

Los hilos se pueden organizar de distintas formas para que cooperen entre sí en la resolución de un problema. Existen una serie de modelos típicos de organización de los hilos de un proceso. Veamos cada modelo aplicado al ejemplo del servidor de archivos:

Figura 3-4 Modelo servidor/trabajador.

Figura 3-5 Modelo de cola de trabajo.

Figura 3-6 Modelo de equipo.

Figura 3-7 Modelo de tubería.

DISEÑO DE UN PAQUETE DE HILOS.

Es posible implementar una biblioteca de hilos que soporte planificación preemptiva, rápidos cambios de contexto entre hilos, secciones críticas pequeñas, evite el crecimiento ilimitado de la pila, emplee pocas llamadas al sistema, y proporcione un interfaz independiente del lenguaje.

Un paquete de hilos consiste de un conjunto de primitivas relacionadas con la gestión de los hilos, y disponibles para que el programador realice aplicaciones multihilo. El paquete de hilos también se encargará de gestionar, controlar, crear y destruir los hilos que la aplicación multihilo requiere para su ejecución. Los paquetes de hilos suelen tener también llamadas para especificar el tipo de algoritmo de planificación deseado para los hilos: round-robin, prioridades, etc., así como establecer las prioridades en su caso.

Para maximizar el rendimiento de la biblioteca de hilos, las llamadas al kernel del sistema operativo deben ser minimizadas. La sobrecarga asociada cuando se entra y se sale del kernel del sistema hace que las llamadas al sistema sean operaciones muy costosas. La mayoría de las llamadas que debe realizar el paquete estarán relacionadas con la inicialización de la biblioteca y otra serie de etapas que no sean críticas en tiempo.

Existen dos formas de gestionar los hilos:

a) Diseño de Hilos Estáticos : El numero de hilos se fija al escribir el programa o durante la compilación. Cada hilo tiene asociada un pila fija. Es una alternativa simple pero inflexible.

b) Diseño de Hilos Dinámicos : Se permite la creación y destrucción de hilos durante la ejecución. En este modelo un proceso se inicia con un sólo hilo (de manera implícita), pero puede crear más hilos posteriormente. Este suele ser el diseño habitual empleado en los paquetes de hilos actuales.

Existe una llamada para la creación de hilos que determina el programa principal del hilo, para ello se pasa a la llamado un puntero al procedimiento principal, un tamaño para la pila del hilo, y otra serie de parámetros, como puede ser la prioridad de planificación. La llamada devuelve un identificador del hilo. La sintaxis abstracta de la llamada de creación de hilos es id_Hilo CreateThread(puntero_procedimiento, tamaño_pila, Parametros...)

Un hilo puede finalizar su ejecución por dos razones (al igual que un proceso) : la terminación natural de su trabajo o su eliminación desde el exterior.

Estructura básica.

El estándar POSIX Threads especifica un modelo de hilos dirigido por prioridades con políticas de planificación preemptivas, gestión de señales, y primitivas para proporcionar exclusión mutua así como espera sincronizada. El diseño de un paquete de hilos suele estar influenciado por las restricciones impuestas por el estándar POSIX Threads (si se desea seguir dicho estándar, caso habitual) y el tipo de plataforma sobre la que se va a implementar. Normalmente el diseño del paquete intenta reducir al mínimo la cantidad de código dependiente de la plataforma, y se suele aislar en módulos concretos, de forma que la biblioteca sea adaptable a nuevas plataformas.

En la mayoría de las implementaciones, el interfaz consiste en una biblioteca C con puntos de entrada enlazables, de forma que pueda ser compilada para generar un interfaz de lenguaje independiente. Este es el caso de la implementación Pthreads realizada por Frank Mueller como base del proyecto PART (Portable Ada Run-Time), en el que se implementa un sistema de tiempo de ejecución para la gestión de tareas Ada apoyado en la biblioteca de hilos.

Figura 3-8 Niveles en un paquete de hilos.

Un interfaz permite que los programas empleen los servicios de la biblioteca independientemente del lenguaje que empleemos. En el caso del lenguaje C, las rutinas de la biblioteca son utilizables directamente, mientras que en otros lenguajes es necesario crear un interfaz entre el lenguaje y la biblioteca de hilos.

En algunos diseños de paquetes de hilos, el código de las rutinas de la biblioteca se ejecuta normalmente en modo usuario, aunque las secciones críticas se ejecutan en un modo protegido o kernel de la biblioteca (no confundir con el modo kernel del sistema), que es un modo especial que garantiza la exclusión mutua entre hilos. Estas implementaciones suelen emplear rutinas de la biblioteca estándar del sistema y algunas llamadas al kernel del sistema.

Los objetivos de diseño que deben prevalecer son :

Sincronización.

Como los hilos comparten el espacio de direcciones, comparten las variables globales. El acceso a dichas variables se realiza generalmente mediante regiones críticas, para evitar que varios hilos tengan acceso a los mismos datos al mismo tiempo. Por ello es necesario sincronizar el acceso a los recursos compartidos por los hilos de un proceso. La implementación de las regiones críticas es más sencilla utilizando semáforos, monitores u otras construcciones similares.

El estándar POSIX Threads especifica un mútex como estructura de datos para garantizar el acceso exclusivo a datos compartidos, y variables de condición para realizar la sincronización entre hilos. Otros métodos de sincronización tales como semáforos contadores pueden implementarse empleando estas primitivas. Normalmente los paquetes de hilos implementan las siguientes técnicas :

Mútex.

Un mútex consiste en una especie de semáforo binario con dos estados, cerrado y no cerrado. Un mútex es un objeto que permite a los hilos asegurar la integridad de un recurso compartido al que tienen acceso. Tiene dos estados : bloqueado y desbloqueado. Sobre un mútex se pueden realizar las siguientes operaciones:

Antes de acceder a un recurso compartido un hilo debe bloquear un mútex. Si el mútex no ha sido bloqueado antes por otro hilo, el bloqueo es realizado. Si el mútex ha sido bloqueado antes, el hilo es puesto a la espera. Tan pronto como el mútex es liberado, uno de los hilos en espera a causa de un bloqueo en el mútex es seleccionado para que continúe su ejecución, adquiriendo el bloqueo.

Un ejemplo de utilización de un mútex  es aquél en el que un hilo A y otro hilo B están compartiendo un recurso típico, como puede ser una variable global. El hilo A bloquea el mútex, con lo que obtiene el acceso a la variable. Cuando el hilo B intenta bloquear el mútex, el hilo B es puesto a la espera puesto que el mútex ya ha sido bloqueado antes. Cuando el hilo A finaliza el acceso a la variable global, desbloquea el mútex. Cuando esto suceda, el hilo B continuará la ejecución adquiriendo el bloqueo, pudiendo entonces acceder a la variable.

Hilo A : Hilo B :


lock(mutex)            lock(mutex)
acceso al recurso      acceso al recurso
unlock(mutex)          unlock(mutex)




Un hilo puede adquirir un mútex no bloqueado. De esta forma, la exclusión mutua entre hilos del mismo proceso está garantizada, hasta que el mútex es desbloqueado permitiendo que otros hilos protejan secciones críticas con el mismo mútex. Si un hilo intenta bloquear un mútex que ya está bloqueado, el hilo se suspende. Si un hilo desbloquea un mútex y otros hilos están esperando por el mútex, el hilo en espera con mayor prioridad obtendrá el mútex. Para simplificar las implementaciones, normalmente un hilo no puede ser cancelado cuando tiene cancelación activada y controlada, y se suspende debido a la espera del mútex, con el fin de garantizar un estado determinista del mútex en los gestores de limpieza.

Un mútex debe ser bloqueado durante el menor tiempo posible para minimizar la espera. Por ejemplo, se debe proteger el acceso a estructuras de datos compartidas entre hilos mediante mútex. Pero no se debe bloquear un mútex, realizar una acción que puede provocar la suspensión del hilo, y después desbloquear el mútex, porque se puede producir la espera durante un largo periodo mientras se posee el mútex.

Variables de condición.

Una variable de condición es un objeto que permite que los hilos se ejecuten en un secuencia ordenada. Los hilos pueden esperar a que se cumpla una cierta condición, o pueden indicar a otros hilos que se ha producido una cierta condición, liberando uno o más hilos de la condición de espera. Existe un mútex y un predicado asociados con una variable de condición. El predicado es una variable específica de la aplicación comprobada por los hilos, indicando que algún tipo de condición está lista o no. El predicado es necesario porque la variable de condición misma es opaca, siendo usado en las operaciones wait y signal. El mútex de la variable de condición asegura que un hilo como máximo está accediendo al predicado y entrando en un estado de espera o enviando una señal basada en su valor.

Típicamente, una variable de condición es empleada para indicar cuando un hilo debe comenzar a trabajar en una tarea. Esto puede ser útil para implementar el modelo de hilos de trabajo en equipo, haciendo que los hilos trabajadores esperen por una variable de condición usada como un flag para indicar el instante de comienzo. En el modelo de tubería se puede emplear una variable de condición para indicar que la etapa anterior de una tarea ha sido completada por algún hilo.

Un ejemplo de utilización de una variable de condición es aquel en el que un hilo A bloquea un mútex asociado con una variable de condición. Eventualmente el hilo A adquiere el bloqueo de este mútex, procediendo entonces a acceder al predicado. Si el predicado indica un estado deseado, el hilo A procederá a desarrollar la tarea X y desbloqueará el mútex. Si no, el hilo A entrará en un estado de espera, pero la operación wait realizará automáticamente el desbloqueo del mútex. El hilo B bloquea el mútex asociado con la variable de condición después de haber completado la tarea Y. Eventualmente, el hilo B adquirirá el bloqueo de este mútex, procediendo entonces a acceder al predicado. El hilo B pondrá el predicado en el estado ready, indicando con signal que el predicado está listo y desbloqueando el mútex. Si el hilo A estaba esperando en la variable de condición, la indicación signal emitida por el hilo B provocará que el hilo A continúe su ejecución. Supongamos la secuencia en la que el hilo A sólo realiza la tarea X después de que el hilo B haya realizado la tarea Y. El hilo B indica que ha realizado la tarea Y empleando una variable de condición accedida por ambos hilos A y B.

Hilo A : Hilo B :


lock(mutex)                             Realizar Tarea Y
while (!predicado)                      lock(mutex)
       wait(var_condic, mutex)          predicado = TRUE
Realizar Tarea X                        signal(var_condic)
unlock(mutex)                           unlock(mutex)




Para permitir la sincronización entre hilos y la suspensión durante un largo intervalo de tiempo, se emplean las variables de condición. Una variable de condición está asociada con un mútex y un predicado basado en datos compartidos. Cuando un hilo necesita sincronizarse con otro, bloquea el mútex, comprueba el predicado y, si el predicado se evalúa a falso, se suspende en la variable de condición. Cuan el hilo es reactivado, vuelve a evaluar el predicado y así hasta que el predicado se hace cierto. La evaluación nuevamente del predicado es esencial ya que las reactivaciones en un multiprocesador y las reactivaciones debidas a eventos asíncronos pueden causar que el hilo continúe su ejecución mientras el predicado permanece a falso, debido a que las operaciones no son atómicas.

Cuando un hilo entra en una espera condicional con el mútex asociado bloqueado, el mútex es desbloqueado y el hilo suspendido en una sola operación atómica. De forma similar, el mútex es bloqueado nuevamente cuando el hilo continua su ejecución, de forma atómica. Así pues, el mútex asociado está siempre en un estado conocido, incluso cuando las señales interrumpen una espera condicional, ya que el mútex es readquirido antes de que se inicie la ejecución de cualquier gestor de interrupciones.

Una variable de condición es "señalada" por un hilo después de que el hilo cambie el estado de algún dato compartido permitiendo que el predicado asociado se haga cierto. Cuando una variable de condición es señalada, al menos uno de los hilos bloqueados en ella pasa al estado preparado. Si más de un hilo está bloqueado en la variable de condición, el hilo con mayor prioridad pasará al estado preparado. En particular, en un sistema multiprocesador, puede ser más eficiente desbloquear más de un hilo a la espera de la condición.

Una variable de condición es una variable similar a la variable de condición empleada en la implementación de los monitores como técnica de sincronización. Se suele asociar un mútex a una variable de condición cuando ésta se emplea. Cuando se espera por una variable de condición, se indica el mútex bloqueado asociado a la sección crítica a la que se desea acceder cuando se cumpla la condición. De esta forma la variable de condición y el mútex cooperan en la protección de una región crítica condicional.

- El mútex se emplea para realizar un cierre a corto plazo, normalmente para proteger el acceso a las regiones críticas.

- La variable de condición se utiliza para una espera a largo plazo, en espera de algún recurso no disponible. Por ello cuando se espera por una condición, se libera el mútex de acceso a la región critica, pero se vuelve a bloquear dicho mútex cuando se despierta la variable de condición.

Variables globales.

El problema de compartir las variables globales por varios hilos puede provocar que generemos valores incorrectos en sus valores, debido a la indeterminación del hilo que se ejecutará en cada momento. Existen diversas soluciones a este problema:

1) Prohibir las variables globales: Es algo ideal, pero genera conflictos con el software existente.

2) Asignar variables globales particulares a cada hilo: Cada hilo tiene su propia copia de la variable global, lo que evita los conflictos. Se crea pues un nivel más de visibilidad correspondiente a las variables visibles por todos los procedimientos de un hilo. El problema es que no todos los lenguajes tienen formas de expresar este tipo de variables. Una solución es asignar un bloque de memoria a las variables globales y transferirla a cada procedimiento del hilo como un parámetro adicional. No es una solución elegante, pero funciona.

3) Crear nuevos procedimientos de biblioteca, para crear, asignar y leer los valores de estas variables globales en un hilo. Esta es la forma que suelen adoptar la mayoría de los paquetes de hilos. Las llamadas, de forma abstracta, podrían ser:

- create_global("puntero_variable") = Asigna un espacio de almacenamiento para un puntero de una variable en un área especial reservada para el hilo que hizo la llamada. El hilo que hizo la llamada es el único que puede acceder a la variable. Si otro hilo crea una variable global con el mismo nombre obtiene un espacio de almacenamiento distinto, lo que evita conflictos con el ya existente.

- set_global("puntero_variable", &valor) = Almacena el valor de un puntero en el espacio de almacenamiento reservado anteriormente.

- puntero_variable = read_global("puntero_variable") = Devuelve la dirección almacenada en la variable global, para tener acceso al valor del dato.

IMPLEMENTACIÓN DE UN PAQUETE DE HILOS.

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 :

  1. Implementación a nivel usuario, en forma de paquete o biblioteca de hilos, donde toda la funcionalidad es parte del programa de usuario. Esta implementación puede ser más eficiente, ya que no se necesita entrar al kernel en cada llamada, pero complica la gestión de señales y otras operaciones con los hilos. Además se necesitan dos planificadores, un planificador de procesos (a nivel kernel) y un planificador de hilos (en el paquete de hilos, a nivel usuario). Existen sin ningún soporte del kernel y mantienen todo su estado en el espacio de usuario. El kernel no conoce su existencia por lo que no pueden ser planificados para ejecutarse en múltiples procesadores en paralelo.
  2. Implementación a nivel kernel, donde toda la funcionalidad es parte del kernel del sistema operativo. Esta implementación simplifica el control sobre las operaciones de los hilos y la gestión de señales, pero añade gran sobrecarga al ser necesario entrar y salir del kernel en cada llamada. Este tipo de sistemas son conocidos como sistemas puros o sistemas de un solo nivel, ya que el kernel es el responsable de planificar todos los hilos.
  3. Implementación mixta, que consiste en implementar una biblioteca de hilos, pero apoyado en un modelo de hilos de nivel kernel, que permite la ejecución de los hilos de usuario. Estos sistemas son conocidos como sistemas híbridos o sistemas a dos niveles. El kernel coopera con el paquete de hilos de nivel usuario en la planificación. Normalmente el kernel planifica procesos ligeros, llamados abreviadamente LWPs, y la biblioteca de hilos planifica hilos de usuario sobre LWPs.

Paquete de hilos de nivel usuario.

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.

Figura 3-9 Paquete de hilos a nivel de usuario.

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 :

Paquete de hilos de nivel kernel.

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.

Figura 3-10 Paquete de hilos a nivel de núcleo.

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.

Estructura básica.

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.

Envío de señales.

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.

El dispatcher.

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.

Figura 3-11 Diagrama de flujo del Dispatcher.

Gestión de señales.

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 :

  1. si la señal es dirigida específicamente a un hilo, dicho hilo es el receptor, sino
  2. si la señal es enviada de forma síncrona, se dirige al hilo que la provocó, sino
  3. si la señal fue causada por la finalización de un reloj, se dirige al hilo que inició el reloj, sino
  4. si la señal fue causada por la finalización de una E/S, se dirige al hilo que realizó la petición, sino
  5. la señal permanece pendiente a nivel proceso hasta que se pueda seleccionar un hilo que la reciba. La elección de un hilo arbitrario es suficiente para cumplir con el estándar POSIX Threads. En este caso, se realiza una búsqueda secuencial en la lista de todos los hilos hasta que se llega al final o se encuentra un hilo que tiene habilitada la señal.

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 :

  1. si el hilo deshabilitó la señal, la señal permanece pendiente para el hilo, sino
  2. si la señal es una señal de alarma y fue provocada por la finalización de un reloj, el hilo seleccionado pasa al estado preparado si fue suspendido, o, es colocado al final de la lista de preparados si la finalización del tiempo fue provocada por el consumo del quantum de tiempo asignado al hilo, sino
  3. si el hilo fue suspendido en una llamada sigwait, el hilo pasa al estado preparado y las señales especificadas en la llamada sigwait son deshabilitadas para el hilo, sino
  4. si existe un gestor registrado para la señal, se instala una llamada falsa o fake call para el hilo seleccionado, las señales son deshabilitadas según la máscara especificada en sigaction, y el hilo pasa al estado preparado, sino
  5. si la señal es la señal de cancelación, se instala una llamada falsa a pthread_exit en la pila, y el hilo pasa al estado preparado, sino
  6. si la acción definida para la señal es ignorar la señal, no se realiza ninguna acción y se descarta la señal, sino
  7. si la acción definida para la señal es la acción por defecto, se realiza la acción por defecto definida para el proceso.

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.

Figura 3-12 Llamada falsa en un mismo hilo.

Básicamente el mecanismo es el siguiente :

    1. Si el gestor de usuario interrumpió una espera condicional, el mútex asociado es readquirido y la espera condicional finalizada.
    2. La variable errno del hilo es salvada.
    3. El gestor de usuario es llamado.
    4. La variable errno del hilo es restaurada.
    5. La máscara de señales de hilo solicitada es restaurada, y las señales pendientes para el hilo y para el proceso son gestionadas si están habilitadas.
    6. El control es devuelto al punto de la interrupción o a una instrucción cuya dirección puede ser opcionalmente especificada por el gestor de usuario. La posibilidad de redirigir el control a una dirección especificada es una característica no requerida por el estándar POSIX Threads pero deja dicha posibilidad abierta, y en algunas ocasiones es imprescindible, como ocurre con la implementación Pthreads de Frank Mueller para soportar el sistema de tiempo de ejecución de Ada.

Implementación de mútex.

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.

Problemas de implementación.

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.

Paquetes de nivel usuario.

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.

Problemas generales.

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 :

  1. Procedimientos de biblioteca no reentrantes : Un obstáculo más problemático en la utilización de los hilos es hacer reentrantes las bibliotecas de C. Muchas llamadas de biblioteca emplean información de estado global, algunos interfaces no son reentrantes, las macros tienen que ser modificadas, y la interrupción debida a señales debe ser considerada sin sacrificar el rendimiento. Como ejemplo, podemos poner un buffer en el que un hilo prepara un mensaje para enviar a la red, pero antes de hacerlo se produce un cambio de hilo, y el nuevo hilo reescribe sobe el buffer del anterior. Este aspecto es tratado por Jones [JON91].
  2. Otros procedimientos cruciales, como malloc en UNIX, emplean tablas cruciales del sistema, sin emplear regiones críticas protegidas, ya que fueron escritos para sistemas de un único hilo, donde esto no era necesario. Para solucionar esto habría que reescribir toda la biblioteca del sistema. Otra solución consiste en proporcionar a cada procedimiento que lo necesite un jacket que cierre un mútex global al iniciar el procedimiento. Con ello se consigue que esté activo un único hilo de la biblioteca en cada instante. De esta forma, la biblioteca se convierte en un gran monitor.
  3. La gestión de las señales también resulta problemática. La sobrecarga debida a la gestión de señales independiente para cada hilo complica el diseño y la implementación del paquete de hilos de forma considerable. Puede ocurrir que varios hilos traten de capturar la misma señal para realizar acciones diferentes, lo cual es incompatible. Esta situación puede surgir si uno o más hilos emplean procedimientos estándar de biblioteca, y otros en cambio utilizan procedimientos propios escritos por el usuario. Normalmente es difícil gestionar las señales en un ambiente con un único hilo, pero el paso a un ambiente de múltiples hilos no facilita su manejo, y más si tenemos en cuenta que las señales son un concepto típico de proceso, sobre todo si el núcleo no conoce la existencia de los hilos como ocurre en los paquetes a nivel usuario. En la mayoría de las implementaciones de hilos, cada hilo tiene su propia máscara de señales, lo que le permite bloquear o desbloquear señales, pero cada hilo no puede tener su propio gestor de señales. Normalmente la solución es implementar un hilo que se encargue sólo de la gestión de señales, y deshabilitar las señales en el resto de hilos, para que no sean capturadas por ellos. Además se debe tener cuidado con la máscara de señales, a la hora de enviar señales a otros hilos del proceso, ya que la señal será captura por el primer hilo que se ejecute y tenga habilitada dicha señal.
  4. La cancelación de un hilo por parte de otro, cuando ya no es necesario que siga realizando más trabajo es problemática, ya que el hilo cancelado puede encontrarse en una región crítica y al ser cancelado no libera un recurso que puede necesitar otro hilo que espera por él. Una solución suele ser emplear la cancelación diferida, es decir colocar una serie de puntos de cancelación en los cuales se comprueba si el hilo ha sido cancelado, en cuyo caso se procede a su destrucción. Pero si el hilo no se encuentra en un punto de cancelación, no puede ser cancelado hasta que no llegue a uno de esos puntos, aunque la cancelación haya sido solicitada con anterioridad.

VENTAJAS DE LOS HILOS.

La principal ventaja de los hilos es el rendimiento. Normalmente el rendimiento es una cantidad percibida y no dada. Unas aplicaciones se beneficiarán de los hilos mientras que otras no. Como se suele decir "el número de kilómetros puede variar".

Existen un gran número de ventajas para emplear los hilos de usuario así como los hilos del núcleo :

  1. Ejecución paralela : Los hilos de nivel kernel se pueden ejecutar realmente en paralelo en máquinas SMP (Symmetric Multiprocessors). Además el mismo código binario es válido tanto para una máquina de un procesador como una máquina multiprocesador.
  2. Ejecución de código asíncrono : Ya que existen múltiples hilos de ejecución en un programa construido con hilos, es posible que otro hilo del mismo proceso sea planificado para ejecutar en el caso de que el hilo de ejecución actual se bloquee. Esto incrementa la probabilidad de que la aplicación asociada se ejecute mucho más rápido. Normalmente existen algunas cosas a tener en cuenta :
    1. En el modelo de hilos de usuario, algunos bloqueos bloquearán todo el proceso y se planificará un proceso diferente.
    2. En el modelo de hilos de núcleo, es posible que un hilo de otro proceso sea planificado cuando sucede un bloqueo del hilo actual.
    3. En ambos modelos, un hilo puede bloquearse y pueden no existir otros hilos listos para ejecutarse en el proceso, por cualquier tipo de razones.

Así pues, el incremento del rendimiento no siempre está garantizado, aunque al menos, el uso de los hilos puede incrementar la probabilidad de un mejor rendimiento.

  1. Recursos compartidos : Los hilos comparten la mayoría de los recursos en un proceso. Comparten el acceso a los ficheros, memoria compartida, y el espacio de direcciones virtual. El empleo de los hilos permite a los programadores conservar los recursos del sistema. El rendimiento puede beneficiarse también porque los recursos compartidos entre hilos necesitan menos gestión que los recursos compartidos entre procesos.
  2. Velocidad de las operaciones con hilos : Los hilos tienen un menor contexto que los procesos, así pues, las operaciones con hilos son generalmente más rápidas que las operaciones similares con procesos. En especial, la creación, finalización y cambio de contexto de un hilo, son operaciones más rápidas con los hilos que con los procesos. Como ejemplo, en los procesadores de propósito general (SPARC, MIPS, ALPHA, HP-PA, x86) el cambio de contexto entre hilos de un mismo proceso lleva del orden de 50us. mientras que el cambio de contexto entre hilos de distintos procesos lleva del orden de 100us. Estos tiempos son muy inferiores al tiempo de cambio de contexto completo entre procesos. Así en Solaris la creación de un proceso es unas 30 veces más lento que la creación de un hilo, las variables de sincronización son unas 10 veces más lentas y el cambio de contexto unas 5 veces más lento.
  3. Tiempo de respuesta : Si es posible separar operaciones en un programa, los hilos se pueden emplear para mejorar los tiempos de respuesta de la aplicación. Por ejemplo, supongamos que estamos usando una utilidad de correo electrónico. En una versión de un solo hilo, mientras almacenamos un mensaje podemos apreciar algún retraso antes de que la interfaz de usuario sea refrescada. Esto es porque el programa está primero haciendo una operación de E/S para almacenar el mensaje y después refresca la pantalla. Estas operaciones las realiza de forma secuencial. Normalmente, si esta aplicación fuese una versión programada con varios hilos, un hilo podría gestionar la E/S mientras otro hilo gestiona la interfaz de usuario. Estas operaciones pueden funcionar en paralelo, con la consiguiente ganancia en el tiempo de respuesta.
  4. Programación natural : Esta ventaja no está relacionada con el rendimiento, pero es importante. En algunas aplicaciones, el diseñador puede necesitar instrucciones del tipo 'goto' y otros métodos para superar las limitaciones de la programación secuencial tradicional. Sin embargo, con los hilos, el programador no está limitado a emplear un modelo de ejecución secuencial. Así, las limitaciones de la programación secuencial pueden solucionarse de forma más intuitiva, menos compleja y más natural, incluso empleando otros modelos de programación, como la programación concurrente. Además muchos problemas son más fáciles de plantear y programar con un modelo de hilos debido a su estructura concurrente.
  5. Existe un estándar (POSIX 1003.1c) lo que permite hacer a las aplicaciones portables entre distintas plataformas. El mismo código fuente es válido para distintas plataformas.
  6. Objetos distribuidos : Con la aparición del estándar de objetos distribuidos CORBA, los hilos toman un papel especial e importante. Los objetos distribuidos tienen una estructura multihilo inherentemente. Cada vez que se pide que un objeto realice una acción, el objeto ejecuta la acción mediante un hilo independiente, de forma que el objeto puede haber más de un hilo al mismo tiempo. Además los servidores de objetos se pueden construir con hilos de forma más efectiva y con un mayor rendimiento.

PROBLEMAS POTENCIALES DE LOS HILOS.

 

Algunos autores, como John Ousterhout [OUS94], consideran que los hilos sólo deben emplearse cuando se desea y es posible una concurrencia verdadera, y no en entornos uniprocesador. Consideran que son demasiado complicados de usar para la mayoría de los programadores, incluso para los expertos, y plantean la programación con eventos como alternativa para la mayoría de los casos. Las problemas se deben a las siguientes causas :

  1. Complejidad : Aunque es cierto que la programación con hilos puede proporcionar una forma más natural de resolver los problemas, existen otras cosas que se deben tener en cuenta. La programación con hilos es más difícil que la clásica programación secuencial. Por ejemplo, cuando se mantiene, depura u optimiza una aplicación con hilos, se deben tener en cuenta la existencia de múltiples hilos de código en ejecución. Por ello generalmente es más fácil depurar y optimizar un programa de hilo simple.
  2. Sincronización : Se debe coordinar el acceso a los datos compartidos mediante bloqueos. Olvidar un bloqueo puede producir la corrupción de los datos.
  3. Posibilidad de deadlock : Las dependencias circulares en los bloqueos pueden originar deadlock.
  4. Depuración difícil, debido a las dependencias entre los datos y las dependencias de tiempo. Depurar en un sistema multiprocesador es más complicado, más costoso, y los errores no siempre son reproducibles. Una biblioteca de hilos puede ser útil para detectar y analizar errores en un entorno uniprocesador antes de ser probada en un sistema multiprocesador. Existen dos tipos de errores, los errores serie que pueden ocurrir en un entorno uniprocesador, y los errores paralelos que son inherentes a una ejecución paralela, y son difíciles de detectar.
  5. Rompen la abstracción, lo que impide diseñar módulos independientes.
  6. Obtener un buen rendimiento es difícil. Los bloqueos demasiado simples (grano grueso) disminuyen el nivel de concurrencia, mientras que los bloqueos de grano fino son demasiado complicados. Además la velocidad de cambio de contexto del sistema operativo influye notablemente en el rendimiento.
  7. Soporte escaso : El código es difícil de transportar a otras arquitecturas que no soportan hilos. Las librerías estándar no suelen ser hilo-seguras. Las llamadas al kernel o al sistema de gestión de ventanas pueden no estar preparadas para soportar múltiples hilos.
  8. Disponibilidad de herramientas : Para favorecer el desarrollo de aplicaciones multihilo, la industria necesitará crear herramientas de depuración y optimización más refinadas. Sin embargo, la tecnología de los depuradores y optimizadores es relativamente joven lo que a corto plazo supone un problema para los programadores. Un entorno de programación multihilo debe proporcionar depuradores con soporte multihilo [CAS90]. La información debe ser extraída del TCB (bloque de control del hilo) y hacerla disponible al usuario. Los cambios de contexto deberían ser visibles para el usuario. Por ejemplo, cuando se va a producir un cambio de contexto, el usuario podría elegir si continua depurando después del punto de suspensión o si cambia al contexto de otro hilo. Además se podrían presentar ventanas de depuración separadas para cada hilo dentro de un proceso.
  9. Utilización de código no seguro : Se debe tener mucho cuidado a la hora de mezclar código multihilo con código no hilo-seguro, es decir, código no preparado para ejecución en un entorno multihilo.

Consideraciones de programación.

Obviamente, la utilización de los hilos no es sencilla de cara al programador. Un entorno multihilo brinda ventajas, pero puede también incrementar la complejidad de la programación. Algunos problemas típicos encontrados por los programadores cuando trabajan con hilos son :

TÉCNICAS DE PROGRAMACIÓN.

Aunque los paquetes de hilos sólo suelen implementar mútex y variables de condición como estructuras básicas para sincronización de hilos, se pueden implementar otras estructuras más complicadas en nuestros programas.

En este apartado vamos a mostrar como implementar distintas técnicas de programación para algunas situaciones habituales en la programación con hilos. Se emplean las primitivas de gestión de mútex y variables de condición que define el estándar POSIX 1003.1c, y que se pueden consultar en un capítulo posterior, como base para definir otras primitivas más potentes.

Implementación de semáforos.

En este caso vamos a mostrar como implementar semáforos contadores empleando un mútex y una variable de condición. Vamos a implementar la estructura de un semáforo, con las operaciones P (WAIT) y V (SIGNAL) definidas por Dijkstra, junto con las operaciones de inicialización y destrucción del semáforo. El semáforo tendrá siempre un valor >=0, de forma que si es 0, cualquier operación V sobre el semáforo suspenderá el hilo que realiza la operación, hasta que el semáforo adquiera un valor superior.

Definimos la estructura de datos de un semáforo sem_t compuesta por :


/* Estructura de datos del semáforo */
typedef struct {
    pthread_mutex_t lock;  /* Acceso exclusivo a la estructura */
    pthread_cond_t  no_cero;        /* Condición de semáforo no cero */
    unsigned int    contador; /* Valor del semáforo */
    unsigned int    en_espera;/* No. de hilos en espera */
} sem_t;

/* Inicializa la estructura del semáforo con el valor indicado */
int sem_init(sem_t *s, unsigned int valor) {
    /* Inicializa el mútex y la variable de condición asociadas */
    pthread_mutex_init(&s->lock, NULL);
    pthread_cond_init (&s->no_cero, NULL);
    s->contador = valor;
    s->en_espera = 0;
    return (0);
}

/* Destruye un semáforo que ya no es necesario */
int sem_destroy(sem_t *s) {
    pthread_mutex_destroy(&s->lock);        /* Destruye el mútex */
    pthread_cond_destroy(&s->no_cero);     /* Destruye la var.cond.*/
    return (0);
}

/* Operación P o WAIT de Dijkstra sobre el semáforo */
int sem_wait(sem_t *s) {
    pthread_mutex_lock(&s->lock);  /* Acceso exclusivo a datos sem.*/
    while (s->contador == 0) {    /* Esperar hasta que semáforo>0 */
        s->en_espera++;                        /* contar al hilo en espera */
        pthread_cond_wait(&s->no_cero, &s->lock); /* Espera condic. */
        s->en_espera --;               /* Descontar al hilo en espera */
    }
    s->contador--;         /* Decrementa el valor del semáforo */
    pthread_mutex_unlock(&s->lock);        /* Libera el mútex */
    return (0);
}

/* Operación V o SIGNAL de Dijkstra sobre el semáforo */
int sem_signal(sem_t *s) {
    pthread_mutex_lock(&s->lock);  /* Acceso exclusivo a datos sem.*/
    if (s->en_espera)                      /* Si existen hilos en espera */
        pthread_cond_signal(&s->no_cero);      /* Se despierta un hilo */
    s->contador++;                 /* Se incrementa el semáforo */
    pthread_mutex_unlock(&s->lock);        /* Libera el mútex */
    return (0);
}

Implementación de bloqueos de lectores/escritores.

El problema de los lectores/escritores es un problema clásico de la programación concurrente. Se debe permitir el acceso simultáneo de múltiples lectores a una estructura de datos crítica, pero sólo se debe permitir el acceso a un escritor al mismo tiempo, y de forma exclusiva.

En algunos paquetes de hilos, como UI Threads se incorporan primitivas para la gestión de este problema. A continuación vamos a definir primitivas similares. Vamos a definir una estructura de datos que podemos asociar con un bloque de datos al que deseamos acceder para lectura y en ocasiones para escritura. Definimos la estructura de datos bloqueo de lectores/escritores rwlock_t compuesta por :


/* Estructura de datos del bloqueo de lectores/escritores */
typedef struct {
        pthread_mutex_t lock;      /* Acceso estructura de datos      */
        pthread_cond_t  lectura;   /* Condición lectura permitida     */
        pthread_cond_t  escritura; /* Condición escritura permitida   */
        int             estado;    /* -1:escritor,0:libre,>0:lectores */
        int             en_espera; /* No. de escritores en espera     */
} rwlock_t;

/* Inicializa una estructura de bloqueo de lectores/escritores */
int rwlock_init(rwlock_t *rw) {
        / * Inicializa el mútex y variables de condición asociados */
        pthread_mutex_init(&rw->lock, NULL);
        pthread_cond_init(&rw->lectura, NULL);
        pthread_cond_init(&rw->escritura, NULL);
        rw->estado    = 0;
        rw->en_espera = 0;
        return (0);
}


/* Destruye la estructura de bloqueo de lectores/escritores */
int rwlock_destroy(rwlock_t *rw) {
        pthread_mutex_destroy(&rw->lock );       /* Destruye el mútex y */
        pthread_cond_destroy(&rw->lectura ); /* var. de condición */
        pthread_cond_destroy(&rw->escritura);/* asociados */
        return (0);
}


/* Adquiere un bloqueo de lector */
int rw_rdlock(rwlock_t *rw) {
        pthread_mutex_lock(&rw->lock);  /* Acceso exclusivo */
        /* Mientras se esté escribiendo o haya escritores en espera,
           se suspende hasta que haya permiso de lectura */
        while ( (rw->estado < 0) && rw->en_espera )
                pthread_cond_wait(&rw->lectura, &rw->lock);
        rw->estado++;
        pthread_mutex_unlock(&rw->lock);        /* Libera el mútex */
        return (0);
}


/* Adquiere un bloqueo de escritor */
int rw_wrlock(rwlock_t *rw) {
        pthread_mutex_lock(&rw->lock);  /* Acceso exclusivo */
        rw->en_espera++;       /* Incrementa el no. de lectores en espera */
        /* Mientras se está leyendo o escribiendo, 
           se suspende a la espera del permiso de escritura */
        while (rw->estado)
                pthread_cond_wait(&rw->escritura, &rw->lock);
        rw->estado = -1; /* Establece el estado de escritura */
        rw->en_espera--; /* Decrementa el no. de escritores en espera */
        pthread_mutex_unlock(&rw->lock);        /* Libera el mútex */
        return (0);
}


/* Libera un bloqueo de lectores/escritores */
int rw_unlock(rwlock_t *rw) {
        pthread_mutex_lock(&rw->lock);  /* Acceso exclusivo */
        if (rw->estado == -1 ) { /* Si era un bloqueo de escritura */
           rw->estado = 0;  /* libera el bloqueo */
           if (rw->en_espera) /* Si existen escritores en espera */
                pthread_cond_signal(&rw->escritura); /* despierta uno*/
           else /* Sino despierta a todos los lectores */
                pthread_cond_broadcast(&rw->lectura);/* */
        } else {      /* Si era un bloqueo de lectura */
           rw->estado--;   /* libera el bloqueo de lectura */
           /* Si no hay más lectores, despierta un escritor */
           if (rw->estado == 0)
                  pthread_cond_signal(&rw->escritura);
        }
        pthread_mutex_unlock(&rw->lock);        /* Libera el mútex */
        return (0);
}

Antes de emplear este tipo de bloqueo debemos garantizar que hemos inicializado la estructura. Además al finalizar su utilización se debe destruir. Cada vez que intentemos una operación sobre los datos bloqueamos primero la variable asociada de lectores/escritores empleando el bloqueo apropiado (lectura o escritura), realizamos la operación, y después liberamos la variable asociada. La forma normal de emplear las primitivas es recubrir cada tipo de acceso (lectura o escritura) con el bloqueo correspondiente y el desbloqueo final :


LECTOR :                                        ESCRITOR :
rw_rdlock(&rw);                         rw_wrlock(&rw);
 Acceso para lectura                     Acceso para escritura
rw_unlock(&rw)                          rw_unlock(&rw);


Implementación de barreras.

Una barrera es un punto de sincronización entre varios hilos. Esta técnica permite que varios hilos se sincronicen en un determinado punto de su ejecución, de forma que ninguno de ellos puede avanzar en su ejecución hasta que todos hayan alcanzado el punto establecido por la barrera. Con esta técnica se pueden implementar algoritmos SIMD en sistemas MIMD de una forma sencilla.

Figura 3-13 Funcionamiento de una barrera.

En la implementación que se realiza, empleamos el tipo semáforo sem_t definido con anterioridad. Definimos la estructura de datos de una barrera barrier_t compuesta por :

Cada nodo de la lista de hilos en espera del tipo waitlist_t consta de :


/* Estructura de la lista de hilos en espera */
typedef struct _list {
        sem_t           sem;      /* Semáforo de espera asociado */
        struct _list    *next;     /* Siguiente hilo de la lista */
} waitlist_t;

/* Estructura que define el tipo Barrera */
typedef struct _barrier {
        pthread_mutex_t lock;           /* Acceso exclusivo             */
        unsigned int    maxcont;   /* No. de hilos a sincronizar   */
        unsigned int    en_ejecución; /* No. de hilos en ejecución    */
        waitlist_t      *head;       /* Cabeza de lista de hilos en espera */
} barrier_t;

/* Inicializa una variable barrera */
int barrier_init(barrier_t *b, int num_hilos) {
        if ( contador < 1 )     /* Si el no. de hilos a sincronizar */
                return (-1);    /* no es válido devuelve error */
        b->maxcont      = num_hilos;
        b->en_ejecucion = num_hilos;
        b->head         = NULL;
        pthread_mutex_init(&b->lock, NULL);
        return( 0 );
}

/* Se bloquea en una barrera hasta que lleguen todos los hilos, para después continuar la ejecución */
int barrier_wait(barrier_t *b ) {
        pthread_mutex_lock(&b->lock);           /* Acceso exclusivo */
        /* Si es el último hilo en alcanzar la barrera */
        if (b->en_ejecucion == 1) {
                if (b->maxcont != 1) { /* Si no es el único hilo */
                   waitlist_t *h;
                   /* Despierta todos los hilos a la espera
                      de la sincronización con la barrera */
                   for (h = b->head; h != NULL; h = h->next)
                        sem_signal(&h->sem );
                        /* Limpia la barrera, para otra sincronización */
                   b->head         = NULL;
                   b->en_ejecucion = b->maxcont;
                }
                pthread_mutex_unlock(&b->lock); /* Libera el mútex */
        } else { /* Si no es el último hilo en alcanzar la barrera */
                waitlist_t wl;
                sem_init(&wl.sem, 0);   /* Inicializa semáforo temporal */
                b->en_ejecución--;      /* Un hilo menos en ejecución   */
                wl.next = b->head;      /* Inserta en la cabeza de la   */
                b->head = &wl;          /* lista de hilos en espera     */
                pthread_mutex_unlock(&b->lock);/* Libera el mutex */
                sem_wait(&wl.sem );     /* Espera la sincronización     */
                sem_destroy(&wl.sem);   /* Destruye el semáforo temporal*/
        }
        return (0);
}

/* Destruye una variable barrera */
int barrier_destroy(barrier_t *b) {
        b->maxcont      = 0;
        b->en_ejecucion = 0;
        return( pthread_mutex_destroy( &b->lock) );
}

Antes de emplear este tipo de técnica debemos garantizar que hemos inicializado la variable de la barrera. Además al finalizar su utilización se debe destruir. Cada vez que necesitemos un punto de sincronización conjunta, empleamos la primitiva de espera por la barrera en el lugar adecuado en cada uno de los hilos que deseamos sincronizar. La forma normal en la que aparece la primitiva en relación con la ejecución de los distintos hilos a sincronizar es :


t  Hilo1                         Hilo2                           Hilo3
1  .......                       .......                 .......
2  .......                       barrier_wait(&b);       .......
3  barrier_wait(&b);             (suspendido)            .......
4  (suspendido)                                          barrier_wait(&b);
5  Continua                      Continua                Despierta al resto
6  .......                       .......                 .......


Implementación de monitores.

Los monitores son una técnica muy útil en programación concurrente. Consiste en agrupar un conjunto de procedimientos o funciones junto con una serie de datos críticos compartidos que son manipulados por dichos procedimientos, de forma que en un momento dado sólo puede estar ejecutándose un único procedimiento del monitor. Esto garantiza el acceso exclusivo.

A la hora de crear un monitor debemos tener en cuenta los siguientes aspectos :


/* Estructura de los datos compartidos del monitor */
typedef struct _monitor_t {
        pthread_mutex_t         lock;    /* Acceso exclusivo al monitor */
        datos_t                 datos; /* El resto de datos del usuario */
} monitor_t

void monitor_init(monitor_t *m, ... ) {
        pthread_mutex_init(&m->lock, NULL);
        ... Inicialización de los datos de usuario : m->datos ...
}

void monitor_destroy(monitor_t *m, ... ) {
        pthread_mutex_destroy(&m->lock);
        ... Destrucción de los datos de usuario : m->datos ...
}

void monitor_func(monitor_t *m) {
        pthread_mutex_lock(&m->lock);
        ... Código de la función concreta del monitor ...
        pthread_mutex_unlock(&m->lock);
}

3.11. RENDIMIENTO DE LOS HILOS.

El estándar POSIX Threads sugiere un conjunto de métricas de rendimiento basadas en un conjunto de rutinas definidas en la interfaz. A continuación se muestran algunas medidas que intentarn mostrar el rendimiento de los hilos, extraídas de [MUE93]. Estas medidas fueron tomadas en una Sun SPARC 1+ y en una Sun SPARC IPX bajo el sistema operativo SunOS 4.1 empleando análisis de tiempo doble. El paquete de hilos para el que fueron tomadas las medidas es el paquete Pthreads de Frank Mueller, que es una implementación de nivel usuario. Algunas medidas son comparadas con las obtenidas para el sistema SunOS con una arquitectura Multihilo, mientras que otras son comparadas con una versión previa del sistema LynxOS baja una Sun SPARC IPX.

  Tiempo [microsegundos]
Métrica de rendimiento SPARC 1+ SPARC IPX
  SunOS PThreads de Frank Mueller LynxOS
Entrar y Salir del modo protegido.     0.4 7.5
Entrar y Salir del kernel del sistema.     18  
Bloquear/Liberar mútex, sin espera.     1 5
Bloquear/Liberar mútex, con espera.     51  
Sincronización de semáforo. 158 101 55 75
Creación de hilos, sin cambio de contexto. 56 25 12  
Par setjmp/longjmp 59 49 29  
cambio de contexto sugerido.     37 38
Cambio de contexto de proceso.     123 41
gestor de señales del hilo (internas).     52  
gestor de señales del hilo (externas).     250  
gestor de señales del sistema.     154  

Figura 3-14 Ejemplo de rendimiento de un paquete de hilos.

Como se puede observar los beneficios de la biblioteca de hilos de nivel usuario se deben al hecho de que entrar y salir del modo protegido de la biblioteca es mucho más rápido que entrar y salir del modo kernel del sistema. Además el cambio de contexto de hilos es más rápido que el cambio de contexto de procesos.

Las métricas incluyen una pareja de bloqueo/desbloqueo de mútex, primero bajo la suposición de que el mútex es solicitado cuando está desbloqueado, y después suponiendo el intervalo entre un desbloqueo de un hilo A y el retorno de la operación de bloqueo del hilo B (que fue suspendido mientras el hilo A poseía el mútex). La sincronización de semáforos se refiere a una operación P o WAIT más una operación V o SIGNAL, implementadas sobre mútex y variables de condición.

También se tomaron medidas durante la creación de un nuevo hilo (excluyendo el tiempo empleado en el cambio de contexto).

4.1. PRINCIPIOS DEL MULTITHREADING.

Otra visión del concepto de hilo desde una perspectiva hardware es el multithreading [HWA93]. El concepto de multithreading o multihilado es una extensión de los conceptos de multitarea y multiproceso. El propósito es explotar el paralelismo de grano fino en modernos multiprocesadores construidos mediante procesadores de múltiples contextos o procesadores superescalares que generan múltiples instrucciones. Cada hilo emplea un contador de programa distinto. El mayor problema de la arquitectura es la resolución de los conflictos entre recursos. Los niveles de sofisticación, en asegurar la coherencia de los datos y preservar el orden de los eventos, se van incrementando progresivamente desde el modelo de programación simple, pasando por la multitarea, la multiprogramación, el multiproceso, hasta llegar al multihilado. Se necesitan desarrollar mecanismos especiales para gestión de memoria y protección con el fin de garantizar la corrección e integridad de los datos en las operaciones paralelas de los hilos. El multithreading o multihilado necesita que el procesador de la máquina esté diseñado para manejar múltiples contextos simultáneamente mediante un cambio de contexto base.

El entorno de la arquitectura.

Un sistema masivamente paralelo multihilado (multithreaded MPP) se modela mediante una red de nodos de procesadores (P) y memorias (M). La memoria distribuida forma un espacio de direcciones global.

Para analizar el rendimiento de dicha red se emplea los siguientes parámetros:

1) Latencia L: Es la latencia de comunicación en un acceso a memoria remoto. Este valor incluye los retrasos de la red, las penalizaciones por fallos en la cache, y los retrasos causados por contenciones en divisiones de transacciones.

2) Número de hilos N: Es el número de hilos que pueden ser entremezclados en cada procesador. Un hilo está representado por un contexto que consta de un contador de programa, un conjunto de registros, y un vector de estado del contexto.

3) Sobrecarga del cambio de contexto C: Son los ciclos de máquina perdidos en la realización del cambio de contexto en un procesador. Este tiempo depende del mecanismo de intercambio y la cantidad de estados del procesador dedicados al mantenimiento de los hilos activos.

4) Intervalo entre intercambios R: Se refiere al número de ciclos entre intercambios disparados por referencia remota. El inverso p=1/R es el ratio de peticiones de accesos remotos. Refleja una combinación del comportamiento del programa y el diseño del sistema de memoria.

Una forma de incrementar la eficiencia es reducir el ratio de peticiones empleando memorias cache coherentes distribuidas. Otra forma es eliminar la espera del procesador mediante el multihilado.

Computación multihilo.

El modelo de computaciones paralelas multihilo fue descrito por Bell(1992), y se presenta en la siguiente figura :

Figura 4-1 Modelo de computación multihilo.

La computación comienza con un hilo secuencial (1), seguido por una planificación (2) donde los procesadores inician los hilos de la computación (3), a través de mensajes entre computadoras que actualizan las variables entre los nodos donde existe memoria distribuida (4), y finalmente mediante sincronización (5) antes del comienzo de la siguiente unidad de trabajo paralelo.

El periodo de sobrecarga de comunicación (3) inherente en las estructuras de memoria distribuida está normalmente distribuido en toda la computación y está solapado completamente. La sobrecarga del paso de mensajes debido a las llamadas receive y send en los multicomputadores puede reducirse mediante hardware especializado operando en paralelo con la computación.

El ancho de banda de la comunicación limita la granularidad, ya que se debe transferir cierta cantidad de datos a otros nodos para completar un grano de la computación. Las llamadas de paso de mensajes (4) y sincronización (5) son no productivas. Son necesarios mecanismos rápidos para reducir u ocultar estos retrasos. El mutithreading no es capaz de incrementar la velocidad en la ejecución de hilos simples, mientras que los modelos de consistencia débiles son capaces de hacerlo.

Problemas de asincronía.

Los procesadores masivamente paralelos (MPP) operan de forma asíncrona en un entorno de red. La asincronía produce dos problemas de latencia fundamentales, las cargas remotas y la sincronización de las cargas :

1) Carga remota: Supongamos el siguiente ejemplo.

Figura 4-2 Ejemplo del problema de la carga remota.


        vA = rload pA
        vB = rload pB
        C = vA - vB

Las variables A y B se encuentran localizadas en los nodos N2 y N3 respectivamente. Se necesitan en el nodo N1 para calcular la diferencia A-B en la variable C. El cálculo básico necesita la ejecución de dos cargas remotas (rload) y después la resta. Supongamos que pA y pB son punteros a A y B respectivamente. Las dos cargas remotas pueden realizarse en el mismo hilo o en dos hilos distintos. El contexto de la computación en N1 se representa en la variable CTXT, y puede tener un puntero de pila, un identificador de proceso, etc.

2) Sincronización de las cargas: La desocupación debida a la sincronización se presenta a continuación:

Figura 4-3 Ejemplo del problema de la sincronización de la carga.


- Nodo N1 calcula C=A-B
- A y B son calculadas concurrentemente
- El hilo en N1 debe ser notificado cuando A y B están listas.

Las variables A y B son calculadas mediante procesos concurrentes, y no se sabe cuando estarán listas para ser leídas por el nodo N1. Las señales ready1 y ready2 pueden llegar al nodo N1 de forma asíncrona. Esta situación es típica en el problema del productor consumidor. Puede resultar en una espera ocupada.

La clave es cómo evitar la desocupación en el nodo N1durante las operaciones de carga. La latencia debida a las cargas remotas es una propiedad de la arquitectura. La latencia debida a la sincronización de las cargas también depende de la planificación y del tiempo de cálculo de A y B que puede ser mucho mayor que la latencia de paso. Normalmente la latencia de sincronización es imprevisible, mientras que la latencia de carga remota sí los es.

Soluciones del multihilado.

La solución a los problemas de asincronía consiste en multiplexar varios hilos: cuando un hilo realiza una petición de carga remota, el procesador comienza a trabajar en otro hilo. Para ello, el coste de cambio de contexto de hilo debe ser mucho menor que la latencia de la carga remota, de lo contrario es preferible que el procesador espere la respuesta de la carga remota.

Cuanto mayor es la latencia entre nodos más hilos son necesarios para ocultarla eficientemente. Otro aspecto a tener en cuenta es que los mensajes deben llegar en orden. Así por ejemplo, supongamos que el hilo T1 realiza un carga remota; mientras llega el resultado podemos conmutar al hilo T2, que realiza otra carga remota. Entonces puede ocurrir que las respuestas no lleguen en el mismo orden, debido a que las peticiones pueden ser a nodos de distintas distancias, con distintos grados de congestión, nodos cuyas cargas se diferencian enormemente.

Figura 4-4 La solución del multihilado.

Una forma de abordar este problema es asociar a cada carga remota y cada respuesta un identificador del hilo apropiado, de tal forma que pueda ser reestablecido a la llegada de la respuesta. A estos identificadores se les llama continuaciones sobre mensajes. Se necesita un gran espacio de nombres de continuación para poder manejar un número adecuado de hilos a la espera de respuestas remotas.

El tamaño de este espacio de nombres de continuación soportado por el hardware difiere enormemente en los diseños existentes: desde 1 en la computadora Standford Dash, 4 en la MIT Alewife, 64 en la HEP, 1024 en la Tera, hasta todo el espacio de direcciones de memoria local en la Monsoon, la Hybrid Dataflow/VonNeumann, la MDP y la *T. Naturalmente si el soporte hardware para este espacio es pequeño, se puede virtualizar multiplexándolo por software, pero esto tiene una sobrecarga asociada.

Solución de Cache distribuida.

Cada localización de memoria pertenece a un nodo. Los directorios son empleados para mantener listas de importación/exportación y estado cuando los datos son compartidos (en las lecturas, algunas caches pueden contener copias) o exclusivos (en las escrituras, una cache mantiene el valor actual).

Figura 4-5 Cache distribuida.

Los directorios se multiplexan entre un pequeño número de contextos para cubrir los efectos de la carga de la cache. La MIT Alewife, la KSR-1, y la Stanford Dash implementan protocolos de coherencia basados en directorios.

La cache distribuida ofrece una solución al problema de las cargas remotas pero no al problema de la sincronización de cargas, en cambio el multihilo ofrece una solución para las cargas remotas y posiblemente para la sincronización de cargas. Normalmente, las dos aproximaciones se pueden combinar para resolver ambos tipos de problemas de acceso remoto.

5.6. OTROS SISTEMAS OPERATIVOS.

 

Lo cierto es, que la mayoría de los sistemas operativos comerciales y no comerciales de mayor difusión que existen están subiéndose al tren de los hilos. Esto se debe a que cada vez es necesario que las computadores trabajen más rápido, y no forma de hacerlo es aprovecharse de las arquitecturas multiprocesador, cada vez más comunes. Pero para ello es necesario que el sistema operativo esté implicado en las tareas de planificación de procesos. Pero además si en vez de procesos son entidades más veloces, como los hilos, la ganancia es mucho mayor. Por ello casi todos los sistemas operativos incorporan o incorporarán hilos, adoptando como API de programación el estándar POSIX 1003.1c en la mayoría de los casos (al menos en sistemas UNIX).

A continuación se presenta un cuadro que resume los distintos sistemas operativos actuales, indicando el tipo de hilos que implementan, la versión de hilos POSIX que soportan, el nivel de implementación (kernel o no) y el modelo de planificación de los hilos : 2 niveles, indica que varios hilos de usuario se enlazan con uno o más hilos de nivel kernel ; o bien, 1 a 1, indica que cada hilo de nivel usuario se enlaza con un hilo exclusivo de nivel kernel (sistemas puros).

Sistema Operativo Hilos preferidos Versión POSIX Soporte Kernel Modelo de planificación
SunOS 4.x LWP No No  
Solaris 2.3 UI-Threads No 2 niveles
Solaris 2.4 UI-Threads Draft 8 2 niveles
Solaris 2.5 UI-Threads 1003.1.c-1995 2 niveles
SVR4.2MP/UW 2.0 UI-Threads No    
IRIX 6.1. sproc() No  
IRIX 6.2 sproc() 1003.1c-1995  
Digital UNIX 3.2 cma Draft 4 1 a 1
Digital UNIX 4.0 1003.1c-1995 1003.1c-1995 2 niveles
DGUX 5.4 ? Draft 6  
NeXTStep C-Threads No    
AIX 3.5.x DCE Threads DCE Threads No  
AIX 4.1 y 4.2 Draft 7 Draft 7 1 a 1
Plan 9 rfork() No    
OpenVMS 6.2 cma Draft 4 No  
OpenVMS Alpha 7.0 1003.1c-1995 1003.1c-1995 2 niveles
OpenVMS VAX 7.0 1003.1c-1995 1003.1c-1995 No  
HP-UX 10.10 Draft 4 Draft 4 No  
WinNT Win32 Threads No  
OS/2 DosCreateThread Draft 4  
Win32 Win32 Threads No 1 a 1
Linux 1.2.13 - 2.0 Draft 4 1003.1c-1995 No  
Linux 2.x clone() No  

Figura 5-15 Sistemas operativos con gestión de hilos.

También existen otros sistemas operativos que en sus últimas implementaciones han incorporado hilos a nivel kernel, como es el caso de HP-UX 10.20, Chorus, etc. En general la tendencia es que en breve plazo todos los sistemas operativos soportarán hilos a nivel kernel, con el objetivo de exprimir las ventajas de las arquitecturas multiprocesador, que cada vez son más habituales.

LINUX.

Linux soporta hilos a nivel kernel a partir de la versión 1.3.56, pero es en las versiones 2.x del kernel donde el soporte es más robusto. Sin embargo, existen bibliotecas que implementan hilos a nivel usuario desde la versión 1.0.9. Actualmente se está trabajando en hacer el kernel más seguro y reentrante. Con la introducción de las versiones 2.1.x, el espacio de memoria ha sido revisado, gracias a lo cual se puede acceder de forma más rápida a la memoria de usuario.

La implementación de los hilos a nivel kernel que realiza Linux es muy particular, en concepto, a la presentada habitualmente por el resto de sistemas operativos que implementan hilos en su núcleo. Normalmente se define un hilo de forma independiente respecto de un proceso, en el sentido de que son entidades distintas. En Linux se ha definido un hilo como un contexto de ejecución (COE), lo que significa que solo se necesita una tabla de procesos/hilos y un solo planificador.

Normalmente un hilo posee el estado de la CPU (y alguna otra información mínima de estado) mientras que el proceso contenía el resto de información (datos, E/S, señales) compartida por los hilos del proceso. Con esto se consigue una rápida conmutación entre hilos, pero ocasiona algunos problemas, como qué hacer cuando un hilo realiza llamadas del tipo fork() o execve(). Se puede ver a los hilos de Linux como un superconjunto de esta funcionalidad, ya que todavía pueden conmutar de forma rápida y compartir partes del proceso, pero se puede especificar qué partes se desean compartir, y además no tienen problemas con llamadas del tipo exec() o fork(). Existen cuatro "flags" para indicar la forma de compartir información entre hilos que se pueden especificar en la nueva llamada al sistema clone() que implementa Linux :

La llamada clone(), que es una llamada de bajo nivel, es una extensión de la clásica llamada fork(). De hecho, clone(0) es equivalente a fork(). Sin embargo, clone() combinada con los flags proporciona una mayor funcionalidad. Esta llamada es implementada en las últimas versiones de la librería glibc de la siguiente forma :


int clone( int (*fn)(), void **stack, int flags, int argc, ...
/* args */ );

Cada PID es de 32 bits. Si el flag CLONE_PID no es empleado, cada hilo obtiene su propio PID como cualquier otro proceso. Pero si el PID va a ser compartido, el kernel emplea los 16 bits superiores para asignar el identificador del hilo TID. Además, cada proceso tiene al menos un hilo. A cada nuevo hilo del proceso se le asignará un TID comenzando con 1, pues el 0 está reservado para referirse a todos los hilos del proceso.

Los hilos kernel de Linux son en realidad procesos, con lo cual la planificación es idéntica a la que se hace con el resto de procesos, y además la cancelación o suspensión de los hilos se hace mediante señales.

Por otro lado, el soporte de hilos a nivel kernel de Linux todavía sigue en desarrollo. Aún existe una parte de código del kernel que no es reentrante, sobre todo en el caso de los gestores de dispositivo, y se sigue trabajando en el desarrollo de una librería libc segura y reentrante.

Existen extensiones de Linux para tiempo real en las versiones 2.x del kernel, que permiten establecer políticas de planificación mediante la llamada sched_setscheduler().


Click to see more great pages on Campus Life.