EL porter del menjador

De vegades, una tradicional endevinalla o un problema clàssic es resol de manera enginyosa.

[@more@]

Tenim una taula al voltant de la qual hi ha asseguts un determinat nombre de n filòsofs. Al centre hi ha una gran safata amb una pila d’espaguetis:

Entre filòsof i filòsof hi ha un única forquilla, just al mig. Per tant, tenim un problema, doncs ningú (ni tan sols un filòsof) pot menjar espaguetis amb només una forquilla. Existeix una variant xinesa però amb palets i arròs; i el problema no és la quantitat de menjar, sinó garantir que tots puguin menjar en temps raonable perquè cap no mori de gana.

Còm podrien fer els filòsofs per menjar sense haver de passar gana? Podríem donar les següents instruccions: simplement utilitzar dues forquilles quan tinguin gana, menjar i deixar-les una altra vegada al seu lloc quan hagin acabat. Però aquesta solució no és vàlida, ja que un de les forquilles (o totes dues) poden ser agafades per més d’un dels filòsofs veïns alhora. A més, pot donar-se el cas que dos filòsofs adjacents intentin agafar la mateixa forquilla a la vegada, doncs pot ser que tots ells tinguin gana al mateix temps.

Està prohibit utilitzar forquilles que estiguin fora de l’abast de cadascun dels filòsofs. En aquest context, menjar pot ser considerat com a part crucial del problema, ja que dos filòsofs contigus no poden menjar simultàniament, però les forquilles també són elements bàsics en la qüestió, ja que no poden ser utilitzades per dos filòsofs a la vegada.

No creieu que és un problema acadèmic. Aquest exemple està tret de la vida real i és el que passa, per exemple, amb els sistemes operatius dels ordinadors, que obliguen a molts processadors a compartir uns recursos limitats. La forma d’interconnexió d’aquests sistemes és bastant dispersa (no tots els processadors tenen accés a tots els recursos), sense comptar que la quantitat de recursos és molt petita per acontentar-los a tots a la vegada.

(Si vols pensar com resoldre-ho sense llegir una solució, para aquí. Si vols llegir la solució, continua)

Per resoldre el problema hem d’introduir un nou jugador: el porter del menjador. S’indica als filòsofs que deixin la taula quan no tinguin gana i que no tornin a ella fins que tornin a estar famolencs. La missió del porter és controlar el nombre de filòsofs a la sala, limitant el seu número a n-1, doncs si hi ha n-1 comensals, assegurem que, almenys, un pot menjar amb les dues forquilles. En aquest cas hi ha dos que no tenen un veí comú al costat, pel que és segur que un dels filòsofs podrà menjar ja que tindrà a la seva disposició dues forquilles lliures (us deixo el plaer de verificar per vosaltres mateixos que almenys un dels comensals podrà agafar les dues forquilles simultàniament).

Així que la solució és posar aquest porter que farà que l’últim esperi el seu torn a la porta fins que un dels de dins (almenys hi ha un que menja) acabi. En acabar sortirà i el porter deixarà entrar al següent.

Una solució d’allò més enginyosa, no us sembla?.

Font:
http://historias-de-la-ciencia.bloc.cat/post/1052/83776

Quant a omalaled

Me llamo Fernando y soy un apasionado de la ciencia y admirador de los científicos y ténicos de todas las épocas. Espero disfrutéis sabiendo un poquito más de ellos.
Aquesta entrada ha esta publicada en General. Afegeix a les adreces d'interès l'enllaç permanent.

3 comentaris a l'entrada: EL porter del menjador

  1. omalaled diu:

    Jo amb forquilla i cullera 😉

    Salut!

  2. Trena diu:

    Hòstia!

    Quan has dit això dels ordinadors i els processadors i els recursos he intentat pensar amb una solució tipus FIFO o FILO… però no ho he acabat de veure clar… m’ha semblat que els filòsofs es llencarien de cap als espaguetis i al final seria més aviat una salvatjada 😛

    La solució és bona, però em sembla que no hi hagués caigut mai de la vida…

    Jo també me’ls menjo amb cullera i forquilla, però crec que si només tingués una forquilla també seria capaç de menjar-me’ls 😉

  3. omalaled diu:

    La veritat és que d’entrada no se li acudiria quasi bé a ningú.

    Jo no sóc informàtic i em van dir que és un clàsic problema de “programació concurrent”. Després, un del wiki ca actualitzar la wikipedia aquí.

    Salut!

Els comentaris estan tancats.