Es un
problema relacionado con los sistemas multitarea, donde a un proceso o un hilo
de ejecución se le deniega siempre el acceso a un recurso compartido. Sin este
recurso, la tarea a ejecutar no puede ser nunca finalizada.
Comparación con interbloqueo:
La
inanición es una situación similar al interbloqueo, pero las causas son
diferentes. En el interbloqueo, dos procesos o dos hilos de ejecución
llegan a un punto muerto cuando cada uno de ellos necesita un recurso que es
ocupado por el otro.
En cambio, en este caso, uno o más procesos están esperando recursos ocupados
por otros procesos que no se encuentran necesariamente en ningún punto muerto.
Un caso de inanición la ilustra
perfectamente la paradoja conocida como la cena de los filósofos de Edsger
Dijkstra cuando se da el caso de que todos los filósofos cogen el tenedor a la vez.
El cual dice lo siguiente:
Cinco
filósofos se sientan alrededor de
una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de
fideos y un tenedor a la izquierda de su plato. Para comer los fideos son
necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su
izquierda y derecha. Si cualquier filósofo toma un tenedor y el otro está
ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda tomar
el otro tenedor, para luego empezar a comer.
Si
dos filósofos adyacentes intentan
tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos
compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.
Si
todos los filósofos toman el
tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán
esperando eternamente, porque alguien debe liberar el tenedor que les falta.
Nadie lo hará porque todos se encuentran en la misma situación (esperando que
alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este
bloqueo mutuo se denomina interbloqueo o deadlock.
El
problema consiste en encontrar un
algoritmo que permita que los filósofos nunca se mueran de hambre.
Posibles soluciones para la solución de la paradoja.
- Varios turnos:
Se
establecen varios turnos. Para hacerlo más claro supongamos que cada filósofo
que puede comer (es su turno) tiene una ficha que después pasa a la derecha. Si
por ejemplo hay 7 comensales podemos poner 3 fichas en posiciones alternas
(entre dos de las fichas quedarían dos filósofos).
Se
establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las
fichas (y los turnos) a la derecha.
En
base al tiempo que suelen tardar los filósofos en comer y en volver a tener
hambre, el tiempo de turno establecido puede hacer que sea peor solución que la
anterior. Si el tiempo de turno se aproxima al tiempo medio que tarda un
filósofo en comer esta variante da muy buenos resultados. Si además el tiempo
medio de comer es similar al tiempo medio en volver a tener hambre la solución
se aproxima al óptimo.
-Por
turno cíclico:
Se
empieza por un filósofo, que si quiere puede comer y después pasa su turno al
de la derecha. Cada filósofo sólo puede comer en su turno. Problema: si el
número de filósofos es muy alto, uno puede morir
de hambre antes de su turno.
- Colas
de tenedores:
Cuando
un filósofo quiere comer se pone en la cola de los dos tenedores que necesita.
Cuando un tenedor está libre lo toma. Cuando toma los dos tenedores, come y
deja libre los tenedores.
Visto
desde el otro lado, cada tenedor sólo puede tener dos filósofos en cola,
siempre los mismos.
Esto
crea el problema comentado de que si todos quieren comer a la vez y todos
empiezan tomando el tenedor de su derecha se bloquea el sistema (deadlock).
- Resolución
de conflictos en colas de tenedores:
Cada
vez que un filósofo tiene un tenedor espera un tiempo aleatorio para
conseguir el segundo tenedor. Si en ese tiempo no queda libre el segundo
tenedor, suelta el que tiene y vuelve a ponerse en cola para sus dos
tenedores.
Si
un filósofo A suelta un tenedor (porque ha comido o porque ha esperado
demasiado tiempo con el tenedor en la mano) pero todavía desea comer, vuelve a
ponerse en cola para ese tenedor. Si el filósofo
adyacente B está ya en esa cola de tenedor (tiene hambre) lo toma y si no
vuelve a cogerlo A.
Es
importante que el tiempo de espera sea aleatorio o se mantendrá el bloqueo del
sistema.
- El
portero del comedor
Se
indica a los filósofos que abandonen la mesa cuando no tengan hambre y que no
regresen a ella hasta que vuelvan a estar hambrientos (cada filósofo siempre se
sienta en la misma silla). La misión del portero es controlar el número de
filósofos en la sala, limitando su número a n-1, pues si hay n-1 comensales
seguro que al menos uno puede comer con los dos tenedores.
No hay comentarios.:
Publicar un comentario