Itineracion de hebras

De Departamento de Informatica
Saltar a: navegación, buscar

Un hilo, hebra, threads o subproceso es la unidad de procesamiento más pequeña que puede ser planificada por el sistema operativo.

Un programa en ejecución es un proceso que implica uso de recursos para realizar la tarea: tiempo de CPU, memoria, archivos y dispositivos I/O.

La CPU solo puede ejecutar un proceso a la vez y es esta quien dice que tiempo necesita cada proceso.

La creación de un nuevo hilo es una característica que permite a una aplicación realizar varias tareas a la vez (concurrentemente). Los distintos hilos de ejecución comparten una serie de recursos tales como el espacio de memoria, los archivos abiertos, situación de autenticación, etc. Esta técnica permite simplificar el diseño de una aplicación que debe llevar a cabo distintas funciones simultáneamente.

Un hilo es básicamente una tarea que puede ser ejecutada en paralelo con otra tarea.

Los hilos de ejecución que comparten los mismos recursos, sumados a estos recursos, son en conjunto conocidos como un proceso. El hecho de que los hilos de ejecución de un mismo proceso compartan los recursos hace que cualquiera de estos hilos pueda modificar éstos. Cuando un hilo modifica un dato en la memoria, los otros hilos acceden a ese dato modificado inmediatamente.

Lo que es propio de cada hilo es el contador de programa, la pila de ejecución y el estado de la CPU (incluyendo el valor de los registros).


Contenido

Sincronización de Threads

Todos los hilos comparten el mismo espacio de direcciones y otros recursos como pueden ser archivos abiertos. Cualquier modificación de un recurso desde un hilo afecta al entorno del resto de los hilos del mismo proceso. Por lo tanto, es necesario sincronizar la actividad de los distintos hilos para que no interfieran unos con otros o corrompan estructuras de datos.

Una ventaja de la programación multihilo es que los programas operan con mayor velocidad en sistemas de computadores con múltiples CPUs (sistemas multiprocesador o a través de grupo de máquinas) ya que los hilos del programa se prestan verdaderamente para la ejecución concurrente. En tal caso el programador necesita ser cuidadoso para evitar condiciones de carrera (problema que sucede cuando diferentes hilos o procesos alteran datos que otros también están usando), y otros comportamientos no intuitivos. Los hilos generalmente requieren reunirse para procesar los datos en el orden correcto. Es posible que los hilos requieran de operaciones atómicas para impedir que los datos comunes sean cambiados o leídos mientras estén siendo modificados, para lo que usualmente se utilizan los semáforos. El descuido de esto puede generar interbloqueo.



Implementación de Threads

Existen 2 formas de implementacion:

Nivel usuario: los hilos se colocan en aplicaciones de usuarios, en consecuencia de esto el nucleo del sistema no sabe nada de su existencia. Cuando los threads se gestionan en el espacio del usuario, cada proceso necesita su propia tabla de threads privada para llevar el control de sus threads.

Nivel kernel: el nucleo mantiene una tabla de thread que sigue la pista de todos los thread del sistema. No es necesario ningún sistema en tiempo de ejecución dentro de cada proceso, igualmente no existe ninguna tabla de threads en cada proceso. En vez de eso, el núcleo mantiene una tabla de threads que sigue la pista de todos los threads en el sistema.


Prioridades

Cuando se lanzan varios threads para que se ejecuten simultáneamente, se les asigna una cuota de tiempo en función del valor que tengan en su propiedad Priority. La propiedad Priority es una propiedad pública de la clase Thread. Es una enumeración del tipo ThereadPriority, cuyos valores son:


AboveNormal: El thread tiene la prioridad por encima de la normal.

BelowNormal: El thread tiene la prioridad por debajo de la normal.

Highest: El thread tiene la prioridad mas alta.

Lowest: El thread tiene la prioridad mas baja.

Normal: El thread tiene la prioridad normal.


El thread puede cambiar su prioridad pero se debe tener en cuenta de que otros hilos en su programa (o el sistema operativo mismo) puede cambiar su prioridad, así que es necesario procurar depender en la prioridad.



Light weight process

Los LWP como "intermediarios" entre los Hilos de usuario y los Hilos de Kernel

Para manejar modelos M:M, M:1 o modelo de dos niveles, muchos sistemas consideran una estructura intermedia entre el thread de kernel y el thread de usuario. Esta estructura es llamada Light weight process o LWP ( proceso ligero ) y es un medio para lograr multitarea, se ejecuta en el espacio del usuario en la parte superior de un solo thread de kernel, es decir, por cada thread de kernel le corresponde un LWP y este es el que itinera los threads de usuario. Si una hebra de kernel se bloquea esperando, por ejemplo, E/S, se bloquea tambien el LWP, y por ultimo tambien la hebra de usuario asociada a ese LWP. Generalmente se necesita un LWP por llamada al sistema (concurrente) de tipo bloqueante.

Los LWP cumplen la funcion de procesadores virtuales por lo que si tenemos un conjunto de hebras asociadas a un proceso ligero (LWP), el programa puede planificar la ejecucion de estas hebras asociadas a un procesador virtual. Esto se conoce como activacion del planificador, y es una de las principales formas de planificar hebras relacionadas.

Los threads del kernel son manejados integramente por el kernel, no tienen que estar asociados a un proceso; el kernel puede crear threads de kernel cada vez que lo necesite para realizar una tarea en particular


Process-Contention Scope
System-Contention Scope

En este mismo contexto la planificación se realiza en dos sectores:


  • Entre hilos de usuario que compiten por un procesador virtual LWP, es decir la planificación se da dentro del proceso. Esto se llama Process-Contention Scope (PCS) (a la izquierda). Aqui se puede planificar a nivel de usuario con una biblioteca POSIX, por ejemplo, y el kernel no esta consciente de este proceso de planificacion. Generalmente se utiliza la prioridad, mencionada anteriormente, para seleccionar cual hebra ejecutar primero.


  • Entre hilos de kernel, que compiten por CPU, es decir la planificacion está a cargo del kernel, entre todos los hilos disponibles al sistema. Esto se llama System-Contention Scope (SCS) (a la derecha). Aqui entran en juego los algoritmos de planificacion de hebras propios del kernel de cada sistema operativo, el usuario no determina de que forma se itineran las hebras de kernel. Cabe destacar que sistemas Linux, Solaris 9 y Windows XP al poseer modelos de hilos 1:1 solo permiten SCS.

Estados de un Thread

Los principales estados de los hilos son: Ejecución, Listo y Bloqueado. No tiene sentido asociar estados de suspensión de hilos ya que es un concepto de proceso. En todo caso, si un proceso está expulsado de la memoria principal (RAM), todos sus hilos deberán estarlo ya que todos comparten el espacio de direcciones del proceso.

  • Creación: Cuando se crea un proceso se crea un hilo para ese proceso. Luego, este hilo puede crear otros hilos dentro del mismo proceso, proporcionando un puntero de instrucción y los argumentos del nuevo hilo. El hilo tendrá su propio contexto y su propio espacio de la columna, y pasará al final de los Listos.
  • Bloqueo: Cuando un hilo necesita esperar por un suceso, se bloquea (salvando sus registros de usuario, contador de programa y punteros de pila). Ahora el procesador podrá pasar a ejecutar otro hilo que esté en la final de los Listos mientras el anterior permanece bloqueado.
  • Desbloqueo: Cuando el suceso por el que el hilo se bloqueó se produce, el mismo pasa a la final de los Listos.
  • Terminación: Cuando un hilo finaliza se liberan tanto su contexto como sus columnas.

Planificación de thread

  • Planificación apropiativa: un hilo puede suspenderse en cualquier punto para dejar paso a otro hilo, incluso aunque el hilo pueda seguir en ejecución.
  • Planificación no apropiativa: un hilo se ejecuta hasta que él mismo realiza una invocación al sistema de gestión de hilos, siendo en ese momento cuando el sistema puede desalojarle para planificar otro hilo.

La ventaja de la planificación no apropiativa es que cualquier sección de código que no contenga una llamada al sistema de gestión de hilos es automáticamente una sección crítica. Así se pueden evitar cómodamente las condiciones de competencia. Por otro lado, los hilos planificados de forma no apropiativa no pueden aprovechar los sistemas multiprocesador, ya que se ejecutan de forma exclusiva. Es preciso tener cuidado con las secciones de código grandes que no contengan llamadas al sistema de gestión de hilos. El programador puede necesitar insertar invocaciones que permitan que otros hilos puedan planificarse y progresar en su trabajo. Los hilos planificados de forma no apropiativa no son aptos para su uso en aplicaciones en tiempo real, ya que en éstas los eventos llevan asociados tiempos absolutos en los que deben procesarse.

Ejemplos en código

Una breve descripcion de la API de POSIX

LA API pthread de POSIX, permite definir el ambito en el cual se itinerarán los threads al momento que son creados. Se provee de los siguientes valores para definir el ambito de contiendo (sea process-contention scope o system-contention scope):

  • PTHREAD_SCOPE_PROCESS: planifica las hebras usando la planificacion en PCS.
  • PTHREAD_SCOPE_SYSTEM: planifica las hebras usando la planificacion SCS, como dijimos anteriormente Linux y Mac OSX solo permiten este valor.

En los sistemas que implementan el modelo muchos-a-muchos, la politica PTHREAD_SCOPE_PROCESS planifica las hebras de nivel usuario sobre los procesos ligeros disponibles. La politica de planificacion PTHREAD_SCOPE_SYSTEM creara y asociará un proceso LWP a cada hebra de nivel de usuario en los sistemas muchos-a-muchos. En otras palabras asigna un thread de usuario a un thread de kernel, es decir, 1:1.

Las siguientes funciones se utilizan para definir y consultar, respectivamente, el ámbito de contienda seleccionado:

  • pthread_attr_setscope(pthread_attr_t *attr, int scope)
  • pthread_attr_getscope(pthread_attr_t *attr, int *scope)

parametros -> pthread_attr_setscope:

  1. Primer parametro : puntero al conjunto de atributos de la hebra.
  2. Segundo parametro: Se pasa el valor PTHREAD_SCOPE_SYSTEM o PTHREA_SCOPE_PROCESS segun el ambito de contienda que se desee.
  3. retorno != de cero si se produce error

parametros -> pthread_attr_getscope

  1. Primer parametro : puntero al conjunto de atributos de la hebra.
  2. Segundo parametro: contiene un puntero a un valor entero (int) al que se le pasa el valor actual de ambito de contienda.
  3. retorno != de cero si se produce error

Ejemplo en C, utilizando POSIX

Ejemplo tomando del libro "Fundamentos de sistemas operativos - Silberschatz", el mismo ejemplo se encuentra en las presentaciones del profesor aunque con comentarios en inglés y nombres de variables diferentes. Revisar los Comentarios para mayor información del funcionamiento paso a paso.

#include <pthread.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
	int i, scope;
	pthread_t tid[NUM_THREADS];
	pthread_attr_t attr;

	//Obtener los atributos predeterminados
	pthread_attr_init(&attr);

	//Primero consultar el ambito actual
	if(pthread_attr_getscope(&attr, &scope) !=0)
		fprintf(stderr, "Imposible obtener ambito de planificacion\n");
        else
	{
		if (scioe == PTHREAD_SCOPE_PROCESS)
			printf("PTHREAD_SCOPE_PROCESS");
		else if (scope == PTHREAD_SCOPE_SYSTEM)
			printf("PTHREAD_SCOPE_SYSTEM");
		else
			fprintf(stderr, "Valor de ambito ilegal .\n");
	}

	//Definir el algoritmo de planificacion de como PCS o SCS
	pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

	//Crear las hebras
	for (i = 0; i < NUM_THREADS; i++ )
		pthread_create(&tid[i], &attr, runner, NULL);

	//Ahora esperar a que termine cada hebra
	for (i = 0; i<NUM_THREADS; i++)
		pthread_join(tid[i], NULL);

//Cada hebra iniciara su ejecucion en esta funcion
void *runner(void *param)
{
	//realizar alguna tarea
	pthread.exit(0);
}

Ejemplo en Java, y su particular JVM

El planificador de Java tiene en cuenta dos características de los hilos a planificar.

  • La prioridad del hilo (la mas importante).
  • El indicador de demonio.

El planificador determina que hilos deberían ejecutarse comprobando la prioridad de todos los hilos. Los que tienen prioridad mas alta tendrán procesador mas rápido (con valores de prioridad de 1 a 10). Cuando se crea un hilo en Java, éste hereda la prioridad de su padre. A partir de aquí se le puede modificar su prioridad en cualquier momento utilizando el método setPriority . Las prioridades de un hilo varían en un rango de enteros comprendido entre MIN_PRIORITY y MAX_PRIORITY (definidas en la clase Thread). Se ejecutará primero el hilo de prioridad superior, el llamado “Ejecutables”, y sólo cuando éste para, abandona o se convierte en “No Ejecutable”, comienza la ejecución de en hilo de prioridad inferior. Si dos hilos tienen la misma prioridad, el programador elige uno de ellos en alguna forma de competición. El hilo seleccionado se ejecutará hasta que:

  • Un hilo con prioridad mayor pase a ser "ejecutable".
  • En sistemas con tiempo-compartido, termina su tiempo
  • Abandone, o termine su metodo run.

El planificador puede seguir dos patrones, preventivo y no preventido. Preventivo es, a muy resumidas cuentas, si en un momento dado un hilo que tiene una prioridad mayor a cualquier otro hilo que esta ejecutando pasa a ser "ejecutable", entonces el sistema elige a este nuevo hilo. Sin embargo dado que la maquina virtual de java opera sobre diversos sitemas operativos esto varia de sistema a sistema.

El ejemplo concreto

En el siguiente ejemplo, mostramos la ejecución de dos hilos con diferentes prioridades. Un hilo se ejecuta a prioridad más baja que el otro. Los hilos incrementarán sus contadores hasta que el hilo que tiene prioridad más alta alcance al contador que corresponde a la tarea con ejecución más lenta

import Java.awt.*;
import Java.applet.Applet;

// En este applet se crean dos hilos que incrementan un
//contador, se proporcionan distintas prioridades a cada uno y se para
//cuando los dos coinciden

public class SchThread extends Applet 
{
   Contar alto,bajo;
   public void init() 
   {
      // Creamos un thread en 200, ya adelantado
      bajo = new Contar( 200 );
      // El otro comienza desde cero
      alto = new Contar( 0 );
      // Al que comienza en 200 le asignamos prioridad mínima
      bajo.setPriority( Thread.MIN_PRIORITY );
      // Y al otro máxima
      alto.setPriority( Thread.MAX_PRIORITY );
      System.out.println( "Prioridad alta es"+alto.getPriority() );
      System.out.println( "Prioridad baja es"+bajo.getPriority() );
   }

   // Arrancamos los dos threads, y vamos repintando hasta que
   //el thread que tiene prioridad más alta alcanza o supera al
   //que tiene prioridad más baja, pero empezó a contar más
   //alto

   public void start() 
   {
      bajo.start();
      alto.start();
      while( alto.getContar() < bajo.getContar() )
      repaint();
      repaint();
      bajo.stop();
      alto.stop();
   }

   // Vamos pintando los incrementos que realizan ambos threads

   public void paint( Graphics g ) 
   {
      g.drawString( "bajo = "+bajo.getContar()+" alto = "+alto.getContar(),10,10 );
      System.out.println( "bajo = "+bajo.getContar()+" alto = "+alto.getContar() );
   }

   // Para parar la ejecución de los threads

   public void stop() 
   {
      bajo.stop();
      alto.stop();
   }
}

CUDA

Incluso en GPU la planificación de threads es muy importante, considerando la tremenda cantidad de threads que pueden estar funcionando de forma paralela en una GPU. Sin ahondar demasiado en el tema un warp es un grupo de 32 threads consecutivos de un bloque, y es la unidad de planificación en CUDA, el algoritmo de planificación es round-robin/aging y se usa para seleccionar el próximo warp a planificar de los disponibles en el pool de warps listos (operandos leídos).

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas