El portero del comedor
A veces, un tradicional acertijo o un problema clásico se resuelve de forma ingeniosa.
Tenemos una mesa cuyo alrededor tiene sentado un determinado número de n filósofos. En el centro hay una gran bandeja con un montón de espaguetis:
Entre filósofo y filósofo hay un único tenedor, justo en el medio. Por lo tanto, tenemos un problema, dado que nadie (ni tan sólo un filósofo) puede comer espaguetis con sólo un tenedor. Existe una variante china pero con palillos y arroz; y el problema no es la cantidad de comida, sino garantizar que todos puedan comer en tiempo razonable para que ninguno muera de hambre.
¿Cómo podrían hacer los filósofos para comer sin tener que pasar hambre? Podríamos dar las siguientes instrucciones: simplemente utilizar dos tenedores cuando tengan hambre, comer, y dejarlos otra vez en su sitio cuando hayan terminado. Pero esa solución no es válida, puesto que uno de los tenedores (o ambos) puede ser cogido por más de uno de los filósofos vecinos al mismo tiempo. Además, puede darse el caso de que dos filósofos adyacentes intenten coger el mismo tenedor a la vez, pues puede que todos ellos tengan hambre al mismo tiempo.
Está prohibido utilizar tenedores que estén fuera del alcance de cada uno de los filósofos. En este contexto, comer puede ser considerado como parte crucial del problema, puesto que dos filósofos contiguos no pueden comer simultáneamente, pero los tenedores también son elementos básicos en la cuestión, puesto que no pueden ser utilizados por dos filósofos a la vez.
No creáis que es un problema académico. Este ejemplo está sacado de la vida real y es lo que ocurre, por ejemplo, con los sistemas operativos de los ordenadores, que obligan a muchos procesadores a compartir unos recursos limitados. La forma de interconexión de estos sistemas es bastante dispersa (no todos los procesadores tienen acceso a todos los recursos), sin contar con que la cantidad de recursos es muy pequeña para contentarlos a todos a la vez.
(Si quieres pensar cómo resolverlo sin leer una solución, para aquí. De lo contrario, continúa)
Para resolver el problema debemos introducir un nuevo jugador: 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. 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. En ese momento, hay dos por lo menos que no tienen a un vecino común al lado, por lo que es seguro que alguno de los filósofos podrá comer, pues tendrá a su disposición dos tenedores libres (os dejo el placer de verificar por vosotros mismos que al menos uno de los comensales podrá coger los dos tenedores simultáneamente).
Así que la solución es poner ese portero que hará que el último espere su turno en la puerta hasta que uno de los de dentro, pues que hay uno que come, termine. Cuando acabe saldrá y el portero dejará entrar al siguiente.
Una solución de lo más ingeniosa, ¿no os parece?.
Actualización: a petición de Juanjo, que tiene toda la razón del mundo, amplío el artículo diciendo que el problema ya estaba planteado en la wikipedia. Desastre de mí, no lo miré antes de publicarlo. Pero hay que destacar las soluciones que guimi ha puesto en un comentario. Os invito a que las miréis. Puede ser un problema clásico, pero no deja de tener su miga por ello.
Fuente:
“El curioso mundo de las matemáticas”, David Wells
El día 3 de julio de 2006 a las 09:40
no se los filosofos pero yo como los espaguetis con un solo tenedor .
XDXDXD
El día 3 de julio de 2006 a las 09:47
Has conseguido despistarme con el planteamiento. Por un momento pensé que el hecho de ser filósofos (en lugar de médicos, matemáticos o historiadores) tenía alguna relación con la solución dado que los filósofos tienen una tendencia innata a solucionar las cosas de una forma que a ningún mortal no-filósofo se le ocurriría (y no digo que eso sea malo o bueno, así que si hay algún filósofo leyendo que no se ofenda).
Respecto al problema, necesitaría conocer alguna premisa más para plantear nuevas soluciones. Por ejemplo, si el portero puede ordenar a los comensales el lugar en el que deben sentarse o, por el contrario, cada comensal tiene un lugar preasignado. En caso de que el portero pueda asignarlo, el rendimiento sería mejor permitiendo un máximo de n/2 sentados en la mesa y obligándolos a dejar un sitio libre en medio. De esta forma podrían comer simultáneamente n/2 comensales. Con n-1 comensales sentados sólo podría comer uno (uno de los dos adyacentes al lugar desocupado).
El día 3 de julio de 2006 a las 11:00
Si, yo me he quedado convencido de que ibas a decir que un filósofo diría que la mesa tendría que ser esférica para ser perfecta, otro discutiría sobre si los espaggetti son objetos esenciales, otro que dudaría de la talidad de los tenedores y, al final, todos se moririan de hambre menos el portero! ;D
El día 3 de julio de 2006 a las 11:22
Hola, con la referencia de los ordenadores he pensado en como resuelven los sistemas operativos el reparto de recursos y se me han ocurrido varias soluciones:
- Por turno cíclico:
Se empieza por un filósofo, que si quiere come o si no quiere no come y pasa su turno al de la derecha. Cada filósofo solo 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.
- Optimización:
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. En el dibujo de ejemplo (7 comensales) podemos poner 3 fichas en posiciones alternas (entre dos de ellas quedan dos filósofos). Se establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las fichas (y los turnos) a la derecha.
Esta era la aproximación antigua en los ordenadores, un procesador consultaba a los dispositivos sobre sus necesidades por turno (más o menos ;-).
La aproximación actual es por interrupciones y colas.
- 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.
(Esto crea el problema de que si todos quieren comer a la vez y todos empiezan tomando el tenedor de su izquierda se bloquea el sistema).
- Solución de conflictos (de la resolución de colisiones en protocolos de comunicación):
Cuando 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 ambos tenedores (si otro filósofo ya estaba en la cola de uno de los tenedores, él va después del otro).
(Es importante el detalle de tiempo aleatorio, con tiempo fijo se sigue bloqueando el sistema).
Saludos
Güimi
http://guimi.net
El día 3 de julio de 2006 a las 13:17
Güimi, me ha parecido muy interesante tu analogía. Soy programador, y aunque tenía una idea bastante clara de como se realizan las asignaciones de recursos, no sabía de la cuarta opción.
Pero si no me equivoco, con ese planteamiento, es posible el un filósofo nunca llegue a comer, dado que no se garantiza su permanencia en la cola. Llega a la cabeza de la cola, coge un tenedor, espera X tiempo, no obtiene el tenedor y se va al final. Si tiene mala suerte y siempre se repite ese proceso… se muere.
El día 3 de julio de 2006 a las 16:10
Con un solo tenedor se puede comer espaguetis. Por lo tanto cogeré el ejemplo chino, asumiendo que tenemos arroz y existe un solo palillo entre los platos. Con un solo palillo no se puede comer arroz? Bueno, seguro que ni que sea de uno en uno aplastandolo con la punta del palillo, se puede comer, se tarda, pero se puede comer. Podemos buscar 50.000 formas de compartir recursos para que, cada x tiempo, todos los filosofos puedan comer, pero seguro que tardan más de un dia en encontrarlo y los filosofos se impacientaran. A medida que vaya pasando el tiempo y los filosofos tengan hambre, y nadie suelte su palillo, por muy filosofos y buenas personas que sean, al final empezarà a actuar la ley de la junga: “O me das tu palillo o te clavo el mio”. Visto esto, el palillo deja de ser un utensilio para comer y pasa a ser un utensilio de defensa/ataque. Evidentemente los filosofos comeran con una mano mientras con la otra retendrán a los otros con su palillo. Poco a poco surgirà de entre ellos un filosofo dominante, el cual, despues de haver clavado su palillo a varios, se apoderará del plato de arroz, crearà una alianza con los 2-3 ex-filosofos de más confianza e impondrá una dictadura. A partir de aquí, tendremos un 2% de los filosofos bien alimentados y el resto distraidos creando una resistencia para derrocar la dictadura filosofil. La resistencia crearà una falsa sensación de rebelión, con la falsa esperanza de crear una arma mortifera con todos los palillos restantes y, el lider de esta, venderà todos los palillos al dictador filosofo a cambio de un buen porcentaje de arroz. La resistencia, enfurecida, se lanzará sobre el traidor y se lo comeran vivo, aportandoles una gran cantidad de proteinas que les hará pensar mejor que sus dictadores vegetarianos. Estos encontraran la forma de vencer a los dictadores, se los comeran, crearan una secta caníbal y adoraran al portero como un dios a quien le ofreceran el arroz. Cuando solo queden dos filosofos, empezarà la última gran batalla filosofa y se clavaran mutuamente todos los palillos, muriendo los dos. El portero explotarà por comerse todo el arroz. Moraleja: Si alguna vez te faltan palillos para comer, pideselos al camarero.
El día 3 de julio de 2006 a las 16:32
Muchas gracias a todos por las aportaciones. Me gusta que todos hayan tenido alguna idea. Eso es buena señal.
En particular la guimi ha dado una visión mucho más técnica que la que quería poner y me ha encantado ver las diferentes posibilidades.
Schink se lleva la palma: “Si alguna vez te faltan palillos para comer, pideselos al camarero.”
Gran lección
Salud!
El día 3 de julio de 2006 a las 22:54
yo he realizado este ejercicio en programación concurrente !
bueno…. yo y todo el mundo ! es el ejemplo más clásico !
El día 3 de julio de 2006 a las 23:30
Me alegra despiertar esos recuerdos tan añorados de estudiante (y los cates corespondientes), pero eso de todo el mundo … bueno, todo el mundo que lo haya estudiado
Salud!
El día 4 de julio de 2006 a las 00:10
Buenas! El problema de los filósofos tiene su apartado propio en la Wikipedia. Fue propuesto por Dijkstra (famoso por un algoritmo de caminos minimos con su nombre) y como ya se apuntó más arriba, es un problema clásico de computación y sincronización de procesos. Indica también que el bloqueo mutuo de 2 filósofos que intentan comer y no pueden se llama “deadlock”.
Por cierto, la opinión de Guimi podría complementar perfectamente al artículo. Animate a ampliarlo!
http://es.wikipedia.org/wiki/Problema_de_los_fil%C3%B3sofos_cenando
Salu2
El día 4 de julio de 2006 a las 00:47
Hay algún empedimento para que un filósofo pueda dar de comer a sus dos compañeros sentados a ambos lados, a la vez que come él?, es decir, da de comer al de su izquierda, luego al de su derecha y luego come él. De este modo dos filósofos alimentarían a cuatro compañeros (más ellos mismos) y finalmente quedaría uno sin “amigos” que se alimentaría por libre. Solo se emplearían seis cubiertos.
El día 4 de julio de 2006 a las 01:45
La demostración de que con n-1 comensales siempre hay uno con 2 tenedores se puede hacer utilizando el teorema de los nidos y los pichones. Si hay n pichones, n-1 nidos, y todos los pichones estan en un nido, ences hay un nido con dos pichones. No?
El día 4 de julio de 2006 a las 09:58
Hace poco publiqué una implementación en C de todos los algoritmos de concurrencia y sincronizacion clásicos que conocia, si te interesa puedes verlo aqui
El día 4 de julio de 2006 a las 10:05
Efectivamente, es un problema clásico en la literatura sobre programación concurrente.
Hace ya más de diez años que estudié estos temas, pero recuerdo que nos pasamos días y días (y páginas y páginas de manuales) estudiando las diversas soluciones, con los posibles problemas que surgían.
Pero bueno, a lo que iba, ya que parece que ha ocasionado cierta “gracia” el que los protagonistas sean filósofos: ¿por qué son filósofos? ¿qué tienen de especiales los filósfos y su forma de comer espaguetis?
Bueno, todo esto no deja de ser un símil de un sistema informático.
Los tenedores, mesa, etc.. son recursos compartidos y los filósofos son procesos (que se ejecutan varios de forma concurrente en el sistema).
La problemática de la situación surge de que los procesos están un tiempo (en principio, desconocido a la hora de establecer el algoritmo de gestión de los recursos compartidos) haciendo otras tareas, que no requieren ningún tipo de sincronización ni acceso a los recursos compartidos y, de vez en cuando, intentan acceder a dichos recursos.
Pues este tiempo haciendo otras tareas, en la formulación del problema tal y como yo la estudié, los filósofos están “filosofando” (o pensando, o como queramos decirlo): es decir, es una forma de decir, que estaban haciendo otras cosas no importantes para el problema.
y ¿por qué comen, en vez de acceder a otro recurso compartido: por ejemplo, acceso a una cama para dormir). Pues porque es la forma ideal para representar problemas tales como el “deadlock” en que todos mueren de hambre.
Y, ¿por qué comen espaguetis en vez de otros alimentos? Pues porque al requerir el uso de dos tenedores, cada uno haciendo el rol de tenedor derecho para un filósofo e izquierdo para otro, el problema se complica mucho, dando lugar a soluciones no tan triviales como en otros problemas y sirviendo para ejemplificar circunstancias tales como “deadlocks” y condiciones de carrera.
Un saludo.
El día 4 de julio de 2006 a las 10:56
Este problema se estudia en la asignatura Sistemas Operativos 2 de la UPV.La ultima solucion de guimi es la que mas me gusta.Saludos
El día 4 de julio de 2006 a las 11:19
Para Kent: “con ese planteamiento, es posible el un filósofo nunca llegue a comer, dado que no se garantiza su permanencia en la cola (…)”
No es así. Partimos de que cada filósofo está sentado en su silla y solo se pone a la cola de sus dos tenedores cercanos. Visto desde el otro lado, cada tenedor solo puede tener dos filósofos en cola, siempre los mismos.
En cuanto un filósofo A suelta un tenedor (porque ha comido o porque ha esperado demasiado tiempo con el tenedor en la mano) si el segundo filósofo B está ya en cola (tiene hambre) lo toma y sino vuelve a cogerlo A.
En mi tercer planteamiento el bloqueo solo se dá si todos los filósofos intentan a la vez comer y todos cogen a la vez el tenedor de su izquierda. En ese caso tan particular, si con tiempos aleatorios se van liberando tenedores, al no coincidir dos filósofos adyacentes, al menos uno podrá comer, desbloqueando el sistema. Con mucha mala suerte el desbloqueo puede ser lento, pero se garantiza que el sistema completo no se bloquea.
Se puede imaginar una configuración en que el sistema tienda a bloquearse (los filófos comen muy despacio, enseguida vuelven a tener hambre). En ese caso si se desea optimizar un poco más, se puede añadir límite de tiempo comiendo (Cuando un filósofo lleva 5 minutos comiendo, debe dejar los tenedores aunque aún tenga hambre).
Para gana, efectivamente estos periodos de tiempo son algoritmos RoundRobin con quantum que se dan en la UPV desde SO I. Casualmente, este verano doy clases de repaso de SO II en una academia
El día 4 de julio de 2006 a las 11:46
En la mili había dos colas: una para el pan (casi vacía) y otra para el embutido (a rebosar). Poco a poco descendía la cola del embutido y aumentaba la del pan.
Bastaba con hacer primero la cola del pan y luego ponerse en la del embutido.
Con los filósofos, mientras se preguntaban el porqué de la necesidad de comer, algunos esperan mientras otros comen.
Un saludo, Antonio
El día 4 de julio de 2006 a las 12:01
Hola,
he puesto en la wikipedia lo que aquí hemos comentado.
Saludos
Güimi
http://guimi.net
El día 4 de julio de 2006 a las 14:58
pues llevo toda mi vida comiendo espaguetis con un sólo tenedor y me parecería increíble que un filósofo fuera incapaz de hacerlo también.
El día 4 de julio de 2006 a las 18:13
Esto esta en el libro de tanenbaum “Sistemas Operativos Modernos” segunda edición pag 125
El día 8 de julio de 2006 a las 13:16
¿Cómo es eso que no se pueden comer espaguettis con un solo tenedor?
El problema es que no había CUCHARAS!!!
El día 9 de julio de 2006 a las 10:20
La próxima vez haré el post con fideos a la cazuela … pero dudo mucho quepodamos plantearlo
Salud!
El día 23 de julio de 2006 a las 18:37
Simplemente hay que ordenarle al portero como una instrucción de primer orden, de jerarquia superior a la de que haya n-1 comensales
A) Un tiempo prefijado máximo para comer
B) Qué el cambio de filósofo que espera turno sea secuencial en sentido horario o antihorario
C) (implicado x B) Qué no haya posibilidad de que un filósofo espere 2 turnos o filósofo que repita (nada de gemelos univitelinos ni “ahora no tengo apetito”)