Problema de la cena de los filósofos

Problema de la cena de los filósofos
Ilustración del problema de los filósofos cenando.

El problema de los filósofos cenando es un problema clásico de las ciencias de la computación propuesto por Edsger Dijkstra en 1965 para representar el problema de la sincronización de procesos en un sistema operativo. Cabe aclarar que la interpretación está basada en pensadores chinos, quienes comían con dos palillos, donde es más lógico que se necesite el del comensal que se siente al lado para poder comer.


Contenido

Enunciado del problema

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 coge un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger 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 cogen 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.

Algunas posibles soluciones

  • 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.

  • 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.

  • 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.

  • Turno Por Velocidad

Los dos filósofos

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Inanición (informática) — En informática, inanición ( starvation en inglés) 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… …   Wikipedia Español

  • Materialismo — El materialismo es una corriente filosófica que en oposición al idealismo, resuelve el problema cardinal o fundamental de la filosofía acerca de la relación entre el pensar y el ser, entre el espíritu y la naturaleza, postulando que, la materia… …   Wikipedia Español

  • Jesús de Nazaret — «Jesús» redirige aquí. Para otras acepciones, véase Jesús (desambiguación). Para otros usos de este término, véase Jesús de Nazaret (desambiguación). Este artículo trata sobre Jesús de Nazaret como personaje histórico. Para más información sobre… …   Wikipedia Español

  • Asambleas de Dios — Saltar a navegación, búsqueda Asambleas de Dios. Las Asambleas de Dios es una organización cristiana de fe pentecostal que agrupa a diferentes iglesias evangélicas de todo el mundo en Concilios o Convenciones nacionales. Estos Concilios, a su vez …   Wikipedia Español

  • Reino Unido — Para otros usos de este término, véase Reino Unido (desambiguación). «RU» redirige aquí. Para otras acepciones, véase RU (desambiguación). «UK» redirige aquí. Para otras acepciones, véase UK (desambiguación) …   Wikipedia Español

  • Sociedad de la Dinastía Song — Una fiesta elegante, pintura que retrata un pequeño banquete en la Dinastía Song (960 1279). Aunque se pintó en el período Song, se cree que es una reproducción del original y que data de la Dinastía Tang (618 907). La pintura se ha atribuido al… …   Wikipedia Español

  • Leonardo da Vinci — «Leonardo» redirige aquí. Para otras acepciones, véase Leonardo (desambiguación). Para otros usos de este término, véase Da Vinci (desambiguación). Leonardo da Vinci …   Wikipedia Español

  • Cristianismo — El Cristianismo (del Griego antiguo Χριστός, Christós, Cristo , literalmente el Ungido ) es una religión abrahámica monoteísta basada en la vida y enseñanzas de Jesús de Nazaret, presentadas en el canon bíblico y otras escrituras del Nuevo… …   Wikipedia Español

  • Unión Cívica Radical — «UCR» redirige aquí. Para otras acepciones, véase UCR (desambiguación). Unión Cívica Radical Escudo de la UCR Presidente …   Wikipedia Español

  • Investigación reprimida en la Unión Soviética — La investigación científica oficialmente reprimida en la Unión Soviética se refiere a aquellas disciplinas de la ciencia que estaban sujeto a un serio e importante control ideológico en la URSS, en particular durante los tiempos de Iósif Stalin… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”