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  |