Hilos de ejecución o thread
Un hilo de ejecución o thread , en sistemas operativos, es una característica que permite a una aplicación realizar varias tareas 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.
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 e ese dato modificado inmediatamente a en la siguiente figura podemos observar un ejemplo de un hilo de ejecución.
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).
El proceso sigue en ejecución mientras al menos uno de sus hilos de ejecución siga activo. Cuando el proceso es terminado, todos sus hilos de ejecución también lo son. Asimismo en el momento en el que todos los hilos de ejecución finalizan, el proceso no existe más y todos sus recursos son liberados.
Algunos lenguajes de programación tienen características de diseño expresamente creadas para permitir a los programadores lidiar con hilos de ejecución (como Java). Otros (la mayoría) desconocen la existencia de hilos de ejecución y éstos deben ser creados mediante llamadas de biblioteca especiales que dependen del sistema operativo en el que estos lenguajes están siendo utilizados (como es el caso del C y del C++).
Un ejemplo de la utilización de hilos es tener un hilo atento a la interfaz gráfica (iconos, botones, ventanas), mientras otro hilo hace una larga operación internamente. De esta manera el programa responde de manera más ágil a la interacción con el usuario. También pueden ser utilizados por una aplicación servidora para dar servicio a múltiples clientes de procesos.
Diferencias entre hilos y procesos
Los hilos se distinguen de los tradicionales procesos en que los procesos son generalmente independientes, llevan bastante información de estados, e interactúan sólo a través de mecanismos de comunicación dados por el sistema. Por otra parte, muchos hilos generalmente comparten otros recursos directamente. En muchos de los sistemas operativos que proveen facilidades para los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro. Este fenómeno se debe a que los hilos comparten datos y espacios de direcciones, mientras que los procesos al ser independientes no lo hacen. Al cambiar de un proceso a otro el sistema operativo (mediante el dispatcher) genera lo que se conoce como overhead, que es tiempo desperdiciado por el procesador para realizar un cambio de modo (mode switch), en este caso pasar del estado de Running al estado de Waiting o Bloqueado y colocar el nuevo proceso en Running. En los hilos como pertenecen a un mismo proceso al realizar un cambio de hilo este overhead es casi despreciable.
Sistemas operativos como Windows NT, OS/2 y Linux (2.5 o superiores) han dicho tener hilos 'baratos', y procesos 'costosos' mientras que en otros sistemas no hay una gran diferencia.
Funcionalidad de los hilos
Al igual que los procesos, los hilos poseen un estado de ejecución y pueden sincronizarse entre ellos para evitar problemas de compartimiento de recursos. Generalmente, cada hilo tiene una tarea especifica y determinada, como forma de aumentar la eficiencia del uso del procesador.
Estados de un hilo
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.
Cambio de estados
- 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. El hilo tendrá su propio contexto y su propio espacio de pila, y pasara a la cola de listas.
- Bloqueo: Cuando un hilo necesita esperar por un suceso, se bloquea (salvando sus registros). Ahora el procesador podrá pasar a ejecutar otro hilo que esté en la cola de Listos mientras el anterior permanece bloqueado.
- Desbloqueo: Cuando el suceso por el que el hilo se bloqueó se produce, el mismo pasa a la cola de Listos.
- Terminación: Cuando un hilo finaliza se liberan tanto su contexto como sus pilas.
Ventajas de los hilos contra procesos
Si bien los hilos son generados a partir de la creación de un proceso, podemos decir que un proceso es un hilo de ejecución, conocido como Monohilo. Pero las ventajas de los hilos se dan cuando hablamos de Multihilos, que es cuando un proceso tiene múltiples hilos de ejecución los cuales realizan actividades distintas, que pueden o no ser cooperativas entre sí. Los beneficios de los hilos se derivan de las implicaciones de rendimiento.
- Se tarda mucho menos tiempo en crear un hilo nuevo en un proceso existente que en crear un proceso. Algunas investigaciones llevan al resultado que esto es así en un factor de 10.
- Se tarda mucho menos en terminar un hilo que un proceso, ya que cuando se elimina un proceso se debe eliminar el BCP del mismo, mientras que un hilo se elimina su contexto y pila.
- Se tarda mucho menos tiempo en cambiar entre dos hilos de un mismo proceso
- Los hilos aumentan la eficiencia de la comunicación entre programas en ejecución. En la mayoría de los sistemas en la comunicación entre procesos debe intervenir el núcleo para ofrecer protección de los recursos y realizar la comunicación misma. En cambio, entre hilos pueden comunicarse entre sí sin la invocación al núcleo. Por lo tanto, si hay una aplicación que debe implementarse como un conjunto de unidades de ejecución relacionadas, es más eficiente hacerlo con una colección de hilos que con una colección de procesos separados.
Sincronización de hilos
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.
Formas de multihilos
Los sistemas operativos generalmente implementan hilos de dos maneras:
- Multihilo apropiativo: permite al sistema operativo determinar cuándo debe haber un cambio de contexto. La desventaja de esto es que el sistema puede hacer un cambio de contexto en un momento inadecuado, causando un fenómeno conocido como inversión de prioridades y otros problemas.
- Multihilo cooperativo: depende del mismo hilo abandonar el control cuando llega a un punto de detención, lo cual puede traer problemas cuando el hilo espera la disponibilidad de un recurso.
El soporte de hardware para multihilo desde hace poco se encuentra disponible. Esta característica fue introducida por Intel en el Pentium 4, bajo el nombre de HyperThreading.
Usos más comunes
Trabajo interactivo y en segundo plano
Por ejemplo, en un programa de hoja de cálculo un hilo puede estar visualizando los menús y leer la entrada del usuario mientras que otro hilo ejecuta las órdenes y actualiza la hoja de cálculo. Esta medida suele aumentar la velocidad que se percibe en la aplicación, permitiendo que el programa pida la orden siguiente antes de terminar la anterior.
Procesamiento asíncrono
Los elementos asíncronos de un programa se pueden implementar como hilos. Un ejemplo es como los softwares de procesamiento de texto guardan archivos temporales cuando se está trabajando en dicho programa. Se crea un hilo que tiene como función guardar una copia de respaldo mientras se continúa con la operación de escritura por el usuario sin interferir en la misma.
Aceleración de la ejecución
Se pueden ejecutar, por ejemplo, un lote mientras otro hilo lee el lote siguiente de un dispositivo.
Estructuración modular de los programas
Puede ser un mecanismo eficiente para un programa que ejecuta una gran variedad de actividades, teniendo las mismas bien separadas mediante a hilos que realizan cada una de ellas.
Implementaciones
Hay dos grandes categorías en la implementación de hilos:
- Hilos a nivel de usuario
- Hilos a nivel de Kernel
También conocidos como ULT (User Level Thread) y KLT (Kernel Level Thread)
Hilos a nivel de usuario (ULT)
En una aplicación ULT pura, todo el trabajo de gestión de hilos lo realiza la aplicación y el núcleo o kernel no es consciente de la existencia de hilos. Es posible programar una aplicación como multihilo mediante una biblioteca de hilos. La misma contiene el código para crear y destruir hilos, intercambiar mensajes y datos entre hilos, para planificar la ejecución de hilos y para salvar y restaurar el contexto de los hilos.
Todas las operaciones descritas se llevan a cabo en el espacio de usuario de un mismo proceso. El kernel continua planificando el proceso como una unidad y asignándole un único estado (Listo, bloqueado, etc.).
Ventajas de los ULT
- El intercambio de los hilos no necesita los privilegios del modo kernel, por que todas las estructuras de datos están en el espacio de direcciones de usuario de un mismo proceso. Por lo tanto, el proceso no debe cambiar a modo kernel para gestionar hilos. Se evita la sobrecarga de cambio de modo y con esto el sobrecoste o overhead.
- Se puede realizar una planificación específica. Dependiendo de que aplicación sea, se puede decidir por una u otra planificación según sus ventajas.
- Los ULT pueden ejecutar en cualquier sistema operativo. La biblioteca de hilos es un conjunto compartido.
Desventajas de los ULT
- En la mayoría de los sistemas operativos las llamadas al sistema (System calls) son bloqueantes. Cuando un hilo realiza una llamada al sistema, se bloquea el mismo y también el resto de los hilos del proceso.
- En una estrategia ULT pura, una aplicación multihilo no puede aprovechar las ventajas de los multiprocesadores. El núcleo asigna un solo proceso a un solo procesador, ya que como el núcleo no interviene, ve al conjunto de hilos como un solo proceso.
Una solución al bloqueo mediante a llamadas al sistema es usando la técnica de jacketing, que es convertir una llamada bloqueante en no bloqueante.
Hilos a nivel de núcleo (KLT)
En una aplicación KLT pura, todo el trabajo de gestión de hilos lo realiza el kernel. En el área de la aplicación no hay código de gestión de hilos, únicamente un API (interfaz de programas de aplicación) para la gestión de hilos en el núcleo. Windows 2000, Linux y OS/2 utilizan este método. Linux utiliza un método muy particular en que no hace diferencia entre procesos e hilos, para linux si varios procesos creados con la llamada al sistema "clone" comparten el mismo espacio de direcciones virtuales el sistema operativo los trata como hilos y lógicamente son manejados por el kernel.
Ventajas de los KLT
- El kernel puede planificar simultáneamente múltiples hilos del mismo proceso en múltiples procesadores.
- Si se bloquea un hilo, puede planificar otro del mismo proceso.
- Las propias funciones del kernel pueden ser multihilo
Desventajas de los KLT
- El paso de control de un hilo a otro precisa de un cambio de modo.
Combinaciones ULT y KLT
Algunos sistemas operativos ofrecen la combinación de ULT y KLT, como Solaris.
La creación de hilos, así como la mayor parte de la planificación y sincronización de los hilos de una aplicación se realiza por completo en el espacio de usuario. Los múltiples ULT de una sola aplicación se asocian con varios KLT. El programador puede ajustar el número de KLT para cada aplicación y máquina para obtener el mejor resultado global.
Sincronización y Comunicación entre procesos
La comunicación entre procesos: necesaria si se desea que varios procesos puedan colaborar para realizar una misma tarea. Sincronización === funcionamiento coordinado en la resolución de una tarea encomendada.
El SO ofrece mecanismos básicos de comunicación, que permiten transferir cadenas de bytes. Deben ser los procesos que se comunican quienes interpreten el significado de las cadenas transferidas para su labor coordinada.
Los mecanismos de comunicación y sincronización son dinámicos. Es decir, cuando se necesita un mecanismo de este estilo, se crea, usa y destruye, de forma que no se establezca de forma definitiva ningún mecanismo de comunicación, ya que ellos podrían producir efectos indeseados. Es decir, la comunicación es algo puntual.
Los servicios básicos de comunicación son:
- crear: el proceso solicita la creación del mecanismo
- enviar o escribir: el proceso emisor envía información al proceso receptor
- recibir o leer: el proceso receptor recibe información
- destruir: el proceso solicita la destrucción del mecanismo de comunicación
La comunicación puede ser sincrona y asíncrona:
- síncrona: los dos procesos han de ejecutar servicios de forma simultánea. El emisor ha de ejecutar el servicio enviar mientras el receptor ejecuta recibir.
- asíncrona: el emisor hace el envío y prosigue su ejecución. El SO ofrece un almacenamiento intermedio para guardar la información enviada, hasta que el receptor la solicite.
Esquema de Sincronización Sincrona
En un sistema operativo multiprogramado los procesos compiten por el acceso a los recursos compartidos o cooperan dentro de una misma aplicación para comunicar información. Ambas situaciones son tratadas por el sistema operativo mediante mecanismos de sincronización que permiten el acceso exclusivo de forma coordinada a los recursos y a los elementos de comunicación compartidos. Según el modelo de sistema operativo descrito anteriormente, basado en colas de procesos y transiciones de estados, los procesos abandonan la CPU para pasar a estado bloqueado cuando requieren el acceso a algún dispositivo, generalmente en una operación de E/S, pasando a estado preparado cuando la operación ha concluido y eventualmente volver a ejecución. La gestión de estos cambios de estado, es decir, los cambios de contexto, es un ejemplo de sección crítica de código dentro del sistema operativo que debe ser ejecutada por éste en exclusión mutua. Otros ejemplos de código que debe protegerse como sección crítica incluyen la programación de los dispositivos de E/S y el acceso a estructuras de datos y buffers compartidos.
Dentro del dentro del núcleo del sistema operativo, el espacio de direcciones es único, por lo que la comunicación se resuelve mediante el uso de variables de memoria compartida. Como contrapartida a la agilidad de este esquema, es necesario utilizar mecanismos explícitos de sincronización para garantizar acceso exclusivo a las variables compartidas. Si se definen buffers o colas compartidas a las que se proporciona acceso exclusivo, se pueden utilizar esquemas de comunicación más elaborados, como es el caso del productor-consumidor. El esquema cliente–servidor es un caso particular del productor-consumidor donde los clientes producen peticiones que son consumidas por el servidor de un determinado recurso. Un sistema operativo con estructura cliente-servidor resulta atractivo por la claridad de su diseño. Cuando los procesos que se comunican mediante estos esquemas no comparten el espacio de direcciones, lo que sucede en particular en sistemas basados en micro núcleo, se requieren primitivas de comunicación por paso de mensajes, que, al gestionar implícitamente la sincronización, simplifican la programación de la comunicación.
En los apartados siguientes vamos a tratar el problema de la sección crítica y sus soluciones. La sección crítica no es el único problema a resolver en un sistema operativo. Aunque se utilicen esquemas de comunicación elaborados, las interacciones en el uso de los recursos pueden conducir a interbloqueos, problema que se tratará más adelante.
Sección crítica
En programación concurrente, se define como a la porción de código de un programa de computador el cual accede a un recurso compartido (estructura de datos ó dispositivo) que no debe de ser accedido por mas de un hilo en ejecución (thread). La sección crítica por lo general termina en un tiempo determinado y el hilo, proceso ó tarea solo tendrá que esperar un período determinado de tiempo para entrar. Se necesita de un mecanismo de sincronización en la entrada y salida de la sección crítica para asegurar la utilización exclusiva del recurso, por ejemplo un semáforo.
El acceso concurrente se controla teniendo cuidado de las variables que se modifican dentro y fuera de la sección crítica. La sección crítica se utiliza por lo general cuando un programa multihilo actualiza múltiples variables sin un hilo de ejecución separado que lleve los cambios conflictivos a esos datos. Una situación similar, la sección crítica puede ser utilizada para asegurarse de que un recurso compartido, por ejemplo, una impresora, puede ser accedida por un solo proceso a la vez.
La manera en como se implementan las secciones puede variar dependiendo de los diversos sistemas operativos.
Sólo un proceso puede estar en una sección crítica a la vez.
Modelo de sección crítica
El modelo de sección crítica que vamos a utilizar sigue el siguiente protocolo genérico:
Entrar_SC(esta_SC) /* Solicitud de ejecutar esta_SC */
/* código de esta_SC */
Dejar_SC(esta_SC) /* Otro proceso puede ejecutar esta_SC */
Es decir, cuando un proceso quiere entrar a la sección crítica:
(1) ejecuta Entrar_SC(), y si la sección crítica está ocupada el proceso espera;
(2) ejecuta la sección crítica;
(3) ejecuta Dejar_SC(), permitiendo que entre uno de los procesos en espera.
La decisión de qué proceso es el seleccionado para entrar en el paso (3) puede tener consecuencias importantes, como se comentará más adelante. En general, puede asumirse disciplina FIFO.
Un aspecto fundamental es cómo se realiza la espera en Entrar_SC(), lo que determina el tipo de mecanismo de sincronización que se debe utilizar. Esto dependerá del tiempo que el proceso deba esperar para entrar a la sección crítica. La Figura C muestra un ejemplo de utilización de una sección crítica para implementar sincronización productor-consumidor. Hay que advertir que este ejemplo sólo es válido para un productor y un consumidor. Con n productores y m consumidores se producirían condiciones de carrera. Se propone como ejercicio la modificación de este código para el caso general.
Figura C. Una implementación del productor-consumidor (sólo válido para un productor y un consumidor).
Si se va a esperar durante un tiempo que compense el coste de los cambios de contexto asociados a bloquear y desbloquear el proceso, la exclusión mutua se implementa como de largo plazo. La espera por bloqueado resulta entonces más eficiente que la espera activa o mucho menos restrictiva que la inhibición de interrupciones. Un ejemplo de exclusión mutua de largo plazo es el acceso a un driver de un dispositivo, como el de disco.
Vamos a abordar a continuación los mecanismos de sincronización en los sistemas operativos, tanto los de corto plazo, que se basan en la espera por ocupado (incluyendo inhibición de interrupciones y cerrojos de espera activa), como los de espera por bloqueado (primitivas de dormir/despertar y semáforos), además de un mecanismo de comunicación de alto nivel semántico como es el paso de mensajes. Existen otros mecanismos, como regiones críticas y monitores, que no vamos a desarrollar en la siguiente investigación.
Antes de ello es preciso revisar las propiedades que deben cumplir estos mecanismos.
Propiedades del acceso exclusivo a secciones críticas:
Como criterios de validez de un mecanismo de sincronización nos referiremos al cumplimiento de las siguientes condiciones enunciadas por Dijkstra para el acceso exclusivo a una sección crítica.
SC.
- Exclusión mutua. No puede haber más de un proceso simultáneamente en la
- No interbloqueo. Ningún proceso fuera de la SC puede impedir que otro entre a la SC.
- No inanición. Un proceso no puede esperar por tiempo indefinido para entrar a la SC.
- Independencia del hardware. No se pueden hacer suposiciones acerca del número de procesadores o de la velocidad relativa de los procesos.
Suposición inicial adicional: las instrucciones del Lenguaje Máquina son atómicas y se ejecutan secuencialmente.
Además, existen otros criterios que determinan la calidad del mecanismo y que fundamentalmente se refieren a su rendimiento, como son la productividad (número de operaciones de sincronización por unidad de tiempo que el mecanismo es capaz de soportar) y el tratamiento equitativo entre los procesos (por ejemplo, siguiendo una política FIFO para entrar a la sección crítica).
Espera por ocupado
La espera por ocupado engloba una serie de mecanismos de sincronización que proporcionan acceso a secciones críticas de corto plazo. El más sencillo y más utilizado en los sistemas operativos clásicos es la inhibición de interrupciones. En multiprocesadores es necesario utilizar cerrojos de espera activa.
Inhibición de interrupciones
Las secciones críticas protegidas por interrupciones se especifican de la siguiente forma:
s= inhibir() /* Inhibe interrupciones */
/* Sección crítica */
desinhibir(s) /* Restaura estado anterior de interrupciones */
Este mecanismo lleva asociadas importantes restricciones. No cumple la condición de independencia del hardware, ya que en un multiprocesador sólo se inhiben las interrupciones en el procesador que ejecuta la inhibición, restringiéndose por tanto a las implementaciones monoprocesador. Por otra parte, en monoprocesadores, un proceso que utilizase la inhibición de interrupciones como forma de acceso exclusivo a secciones críticas de duración arbitrariamente larga impediría a los demás procesos ejecutar código alguno, aún ajeno a la sección crítica. En los sistemas UNIX clásicos todo el código de las llamadas al sistema se ejecuta como sección crítica, lo que hace a estos sistemas poco adecuados para aplicaciones de tiempo real, ya que es difícil acotar los tiempos de respuesta.
Cerrojos de espera activa
Un mecanismo más general que la inhibición de interrupciones es la utilización de una variable cerrojo para proteger la sección crítica. El proceso que quiere entrar a la sección crítica consulta el cerrojo. Si está libre (cerrojo==0), el proceso lo echa (cerrojo=1) y entra a la sección crítica. Si está echado, ejecuta una espera activa consultando su valor hasta que esté libre. Cuando un proceso deja la sección crítica, libera el cerrojo (cerrojo=0). Este esquema tan sencillo presenta importantes problemas de implementación. Como se puede comprobar, la operación de consulta y modificación del cerrojo constituye a su vez una sección crítica que hay que resolver previamente; si no dos procesos podrían leer simultáneamente un valor cero y ambos entrar a la sección crítica, violando la condición exclusión mutua. Existen algoritmos bastante sofisticados que permiten una implementación software (Decker y Lamport, véase el siguiente ejemplo), pero los procesadores actuales integran mecanismos a nivel de lenguaje máquina que permiten implementar consulta y modificación atómica sobre variables en memoria.
Algoritmo de Dekker (1965)
Para 2 procesos {Pi, Pj}.
int pet[2]; /* inicialmente pet[i]=0 para todo i */
int turno;
Entrar_SC (para un proceso Pi):
pet[i]= 1;
while (pet[j])
if (turno==j) {
pet[i]= 0;
while (turno==j) NOP; /* espera activa */
pet[i]= 1;
}
Dejar_SC (para un proceso Pi):
turno= j;
pet[i]= 0;
- Proporciona exclusión mutua: Pi sólo entra si pet[i]. Si también pet[j], entonces uno de los dos procesos espera por turno.
- No interbloqueo y no inanición: Sólo un proceso quedará esperando por turno, y en este caso el otro estará en la SC, por lo que el primero entrará cuando el segundo cambie el turno al salir.
- No garantiza un orden FIFO.
Algoritmo de la panadería de Lamport (1974)
Para n procesos {P0, P1, …, Pn-1}.
int num[n]; /* inicialmente num[i]=0 para todo i */
int mirando[n]; /* inicialmente mirando[i]=0 para todo i */
Entrar_SC (para un proceso Pi):
mirando[i]= 1;
num[i]= maximo(num) + 1; /* coger numero */
mirando[i]= 0;
for (j=0; j<n; j++) {
while (mirando[j]) NOP; /* esperar */
while (num[j] && esta_antes(j, i)) NOP; /* esperar */
}
Dejar_SC (para un proceso Pi):
num[i]= 0;
- Proporciona exclusión mútua: Si Pi está esperando para entrar y existe algún Pk que
- ha mirado el número, entonces esta_antes(i, k).
- No interbloqueo y no inanición: Se sigue una disciplina FIFO.
- Dos procesos pueden haber cogido el mismo número. Entonces esta_antes() debe resolver. Por ejemplo, si num[i]==num[j], si i<j entonces esta_antes(i, j). Nótese que i y j no pueden ser iguales.
Las instrucciones máquina de consulta y modificación atómica (read-modify-write) proporcionan acceso exclusivo a memoria en una operación atómica de consulta y modificación que bloquea el acceso al bus. El ejemplo más simple es la instrucción máquina Test&Set, que ejecuta atómicamente la secuencia:
R <- cerrojo
cerrojo <- 1
Dejando en el registro R el valor previo de cerrojo. Representaremos esta instrucción como una función que devuelve el valor de cerrojo:
BOOL test_and_set(cerrojo)
El acceso a una sección crítica se implementa haciendo una espera activa (spin-lock) sobre el cerrojo, mediante primitivas de echar el cerrojo (lock) y liberar el cerrojo
(unlock):
lock (tipo_cerrojo cerrojo)
{
while (test_and_set(cerrojo)) NOP;4
}
unlock (tipo_cerrojo cerrojo)
{
cerrojo= 0;
}
Una sección crítica se protege de la siguiente forma:
lock(cerrojo);
/* Sección crítica */
unlock(cerrojo);
Los procesadores modernos cuentan con instrucciones máquina análogas a Test&Set que permiten implementar la espera activa más eficientemente, reduciendo la contención en el acceso al bus de memoria.
Algunos sistemas operativos utilizan cerrojos condicionales, proporcionando una primitiva de echar el cerrojo condicionalmente (cond_lock()) que, en vez de dejar al proceso esperando, devuelve un código de estado si el cerrojo está ocupado, lo que es útil para tratar de evitar interbloqueos, como se verá más adelante.
La espera activa es un mecanismo adecuado para multiprocesadores. En monopocesadores, sin embargo, una espera activa por entrar a la sección crítica podría impedir, dependiendo de la política de planificación, que el proceso que ocupa la sección crítica acceda al procesador para liberarla, y en el mejor de los casos retardaría su entrada6. En cualquier caso, aún en multiprocesadores, es adecuado combinar el mecanismo de espera activa con una planificación que incremente la prioridad del proceso que ejecuta la sección crítica.
Espera por bloqueado
La espera por bloqueado se utiliza para implementar exclusión mutua de largo plazo y se proporciona, en su forma más simple, mediante primitivas que producen un cambio de estado en el sistema operativo, dormir o sleep para bloquear al proceso que la ejecuta, y despertar o wake-up para desbloquear a un conjunto de procesos. Estas primitivas permiten manejar eventos que sirven para gestionar el acceso a recursos compartidos.
Primitivas de dormir y despertar
Un evento se implementa mediante una variable booleana o flag y la cola asociada de procesos bloqueados en él. Los procesos que ejecutan dormir sobre un flag activado pasan a estado bloqueado, provocando un cambio de contexto. Cuando otro proceso o el propio sistema operativo ejecuta despertar sobre ese flag, desbloquea a todos los procesos dormidos en ese flag.
Con dormir y despertar pueden construirse primitivas de exclusión mutua de largo plazo, lock_lp y unlock_lp. Una implementación de lock_lp y unlock_lp es la siguiente:
lock_lp (tipo_flag flag)
{
lock(mutex);
while (flag)
dormir(flag);
flag= 1;
unlock(mutex);
}
unlock_lp (tipo_flag flag)
{
lock(mutex);
flag= 0;
despertar(flag);
unlock(mutex);
}
El código es de acceso exclusivo y, como se observa, se protege con una sección crítica de corto plazo mediante un cerrojo ("mutex"; hemos utilizado un cerrojo de exclusión mutua único común, que llamamos mutex (de mutual exclusión) el cual explicaremos mas adelante). Pero un proceso no puede quedarse dormido dentro de la sección crítica de corto plazo en lock_lp, ya que no permitiría la ejecución de despertar por otro proceso. Sin embargo, como ocurre en la práctica en los sistemas operativos, dormir() puede encargarse de liberar los cerrojos de los procesos, y despertar() de restaurarlos. En otras palabras, los procesos en estado bloqueado se consideran fuera de toda sección crítica. Un problema del esquema dormir/despertar es que despertar desbloquea a todos los procesos dormidos en el flag y sólo uno de ellos accederá a la sección crítica. Esto es especialmente preocupante en multiprocesadores, ya que producirían contención en el acceso al cerrojo. Sin embargo, la limitación fundamental del manejo de eventos con este mecanismo deriva de que la primitiva de despertar no almacena el evento; lo que introduce la posibilidad de condiciones de carrera en una secuencia de dormir y despertar sobre un flag (importa el orden en que se ejecutan).
Modelo de Sincronización Mutex (Mutual EXCLUSIÓN Object) Exclusión Mutua
Los algoritmos de exclusión mutua (comúnmente abreviada como mutex por mutual exclusion) se usan en programación concurrente para evitar que fragmentos de código conocidos como secciones críticas accedan al mismo tiempo a recursos que no deben ser compartidos.
a mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos.
La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.
En un sistema multiprocesador de memoria compartida, se usa la operación indivisible test-and-set sobre una bandera, para esperar hasta que el otro procesador la despeje. La operación test-and-set realiza ambas operaciones sin liberar el bus de memoria a otro procesador. Así, cuando el código deja la sección crítica, se despeja la bandera. Esto se conoce como spin lock o espera activa.
Algunos sistemas tienen instrucciones multioperación indivisibles similares a las anteriormente descritas para manipular las listas enlazadas que se utilizan para las colas de eventos y otras estructuras de datos que los sistemas operativos usan comúnmente.
La mayoría de los métodos de exclusión mutua clásicos intentan reducir la latencia y espera activa mediante las colas y cambios de contexto. Algunos investigadores afirman que las pruebas indican que estos algoritmos especiales pierden más tiempo del que ahorran.
A pesar de todo lo dicho, muchas técnicas de exclusión mutua tienen efectos colaterales. Por ejemplo, los semáforos permiten interbloqueos (deadlocks) en los que un proceso obtiene un semáforo, otro proceso obtiene el semáforo y ambos se quedan a la espera de que el otro proceso libere el semáforo. Otros efectos comunes incluyen la inanición, en el cual un proceso esencial no se ejecuta durante el tiempo deseado, y la inversión de prioridades, en el que una tarea de prioridad elevada espera por otra tarea de menor prioridad, así como la latencia alta en la que la respuesta a las interrupciones no es inmediata.
La mayor parte de la investigación actual en este campo, pretende eliminar los efectos anteriormente descritos. Si bien no hay un esquema perfecto conocido, hay un interesante esquema no clásico de envío de mensajes entre fragmentos de código que, aunque permite inversiones de prioridad y produce una mayor latencia, impide los interbloqueos.
Algunos ejemplos de algoritmos clásicos de exclusión mutua son:
- El algoritmo de Dekker.
El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra.
Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.
/* Definición de variables compartidas */
shared int bandera[2] = {0,0};
shared int turno = 0;
while (cierto)
{
bandera[proc_id] = cierto;
while (bandera[1-proc_id] == cierto)
{
if (turno == 1-proc_id)
{
bandera[proc_id] = 0;
while (turno == (1-proc_id)) /* espera a que sea su turno de intentar */;
bandera[proc_id] = 1;
}
/* Sección crítica */
turno = 1-proc_id; /* es el turno del otro proceso */
bandera[proc_id] = 0;
/* Sección no crítica */
}
}
- El algoritmo de Peterson.
El algoritmo de Peterson es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo memoria compartida para la comunicación.
Algoritmo
bandera[0] = 0
bandera[1] = 0
turno = 0
p0: bandera[0] = 1 p1: bandera[1] = 1
turno = 1 turno = 0
while( bandera[1] && turno == 1 ); while( bandera[0] && turno == 0 );
//no hace nada. espera. //no hace nada. espera.
// sección crítica // sección crítica
… …
// fin de la sección crítica // fin de la sección crítica
bandera[0] = 0 bandera[1] = 0
- Algoritmo de la panadería de Lamport
Es un algoritmo de computación creado por el científico en computación Dr Leslie Lamport, para implementar la exclusión mutua de N procesos o hilos de ejecución.
Algoritmo
El algoritmo de la panadería toma su nombre de la costumbre de las panaderías y tiendas en general, donde las personas al entrar al local obtienen un número de turno (único) y lo utilizan para el dependiente les vaya atendiendo en orden de llegada. El cliente obtiene su número de turno usando una cinta de papel que ofrece boletos con números consecutivos.
El dependiente sólo puede atender a una persona al mismo tiempo, lo que concuerda con el uso de un recurso de forma exclusiva: el recurso es el dependiente y la sección crítica de un cliente es lo que realiza mientras es atendido.
El sistema mantiene un número (variable global) que refleja el número de turno del cliente que se está atendiendo en el instante actual. Los clientes deben esperar en una cola hasta que llega su turno. Una vez que se acaba con un cliente, la variable global se incrementa en uno y el cliente que tenga un boleto con ese número pasa a ser atendido. Cuando termina una compra, el cliente se desprende de su boleto y se dedica a realizar cualquier otra actividad libremente (guardar el dinero en la billetera, retirarse, etc.), ya que no se encuentra más en su sección crítica. Si más tarde quiere volver a comprar, tendrá que obtener un nuevo número.
El modelo algorítmico que se propone, cada cliente es un hilo, identificado con un número único i. Los hilos se deben coordinar para decidir en cada momento qué hilo tiene derecho a ejecutar su código de sección crítica.
En la vida real, el sistema de los boletos funciona perfectamente, pero en un sistema informático la obtención del boleto es problemática: varios hilos pueden obtener el mismo número de turno. En el algoritmo de Lamport se permite que varios hilos obtengan el mismo número. En este caso, se aplica un algoritmo de desempate, que garantiza que sólo un hilo entra en sección crítica. El desempate se realiza así: si dos o más hilos tienen el mismo número de turno, tiene más prioridad el hilo que tenga el identificador con un número más bajo. Como no puede haber dos hilos con el mismo identificador, nunca se da el caso de que dos hilos evalúen al mismo tiempo que tienen derecho a ejecutar su sección crítica.
Entrada en sección crítica
Cuando un hilo quiere entrar en su sección crítica, primero obtiene su número de turno, que calcula como el máximo de los turnos de los otros hilos, más uno. (Si varios hilos realizan el cálculo al mismo tiempo, puede ocurrir que dos o más hilos obtengan el mismo turno).
Antes de entrar en sección crítica, el hilo debe asegurarse de que tiene el número de turno más bajo. En caso de empate, decidirá el identificador de hilo más bajo.
Cuando el hilo abandona la sección crítica, pone su número de turno a un valor especial que indique su no intención de entrar en sección crítica (en este algoritmo, se usa el valor cero).
Implementación
Este es el pseudocódigo del algoritmo de la panadería.
 Página anterior | Volver al principio del trabajo | Página siguiente  |