Ustvarjen z NetLogo-om

Izvorna datoteka: filozofi_pri_vecerji.nlogo

KAJ JE TO?

Problem filozofov pri večerji je klasična študija primera sinhronizacije hkratnih procesov. Ta problem je znan študentom računalništva, uporaben pa je tudi za druge situacije, v katerih se mora več neodvisnih procesov uskladiti glede uporabe skupnega vira oz. pripomočka.

Problem je precej enostaven. Predpostavimo, da skupina filozofov sedi za okroglo mizo in je špagete. Ti filozofi so dolgočasni. Ne delajo drugega kot da mislijo, postanejo lačni in jedo. Med seboj ne komunicirajo.

Vilica leži na mizi med dvema filozofoma. Torej je na mizi natančno toliko vilic, kot je filozofov. Da lahko filozof je špagete, potrebuje dve vilici, vilico z leve in vilico z desne strani. Če želijo vsi filozofi dobiti kaj špagetov, si bodo morali vilice deliti.

Na več načinov gre lahko kaj narobe. Nek filozof lahko vzame obe vilici in nikoli ne neha s hranjenjem. To pomeni, da njegova neposredna soseda ne bosta mogla nikoli jesti. (Čeprav bo vsaj nekdo jedel.)

Kaj se zgodi, če vsak filozof takoj vzame vilico na svoji desni in čaka, da postane vilica na levi prosta? (Da to poskusiš, nastavi verjetnost_lakote na 1.0, sodelovanje? in menjavati_se? daj na OFF, nato klikni na nastavi in začni.) Ta situacija se imenuje »mrtva točka« in je poguba za oblikovalce konkurenčnih sistemov.

Cilj tega problema je, da najdemo strategijo, ki jo lahko filozofi uporabijo in ki zagotavlja, da:
1. Najmanj en lačen filozof lahko vedno je.
2. V povprečju vsi filozofi dobijo enako količino hrane.

Obstaja še ena značilnost sistema, ki pomaga pri iskanju rešitve: ko filozof drži vilico ima možnost, da jo označi ali pa, da odstrani oznako z vilice. Te oznake so vidne vsakemu filozofu, ki čaka na vilico. Ena naključna vilica bo vedno krenila na pot označena. Da pa se izognemo zmešnjavi, se označene vilice ne da vidno določiti, če ni vključeno sodelovanje. Če je sodelovanje vključeno, so označene vilice drugačne barve.

Ali lahko najdeš način, da nahraniš vse filozofe?

Ne pozabi, da filozofi v osnovi ne smejo komunicirati (razen z označevanjem vilic, čeprav to predstavlja komunikacijski kanal). To pomeni, da določanje globalnih značilnosti skupine (npr. sodo/liho število filozofov, prvi filozof) ni dovoljeno. Prebrisan bralec bo opazil, da začetno označevanje ene vilice krši to pravilo z dodeljevanjem globalno edinstveno značilnostjo enemu filozofu. Ali lahko najdeš način, da nahraniš vse filozofe, če odvzameš na začetku označeno vilico?

KAKO DELUJE?

Imamo dva tipa predstavnikov: filozofi in vilice. Filozofi vedo katera vilica je na njihovi levi in katera na njihovi desni. Vedo tudi v kakšni fazi so (razmišljujoči, lačni ali jedci) in koliko so v celoti pojedli. Vilice vedo, kdo jih trenutno drži (če jih sploh kdo) in če so označene.

Če hoče filozof vzeti vilico, mora najprej preveriti, da vilice ne drži kak od sosedov. Nato nastavi, da je on lastnik vilice. V tem modelu je mogoče, da ukradeš vilice drugemu filozofu. Zato je od vsakega filozofa odvisno, da to ne naredi.

Filozof spusti vilico, ko nastavi, da ni nihče njen lastnik.

Vsi filozofi na začetku razmišljajo (so modre barve). V vsakem koraku lahko misleči filozof postane lačen (rdeče barve) z verjetnostjo verjetnost_lakote. Lačen filozof bo poskušal pridobiti obe vilici. Dokler tega ne naredi bo ostal lačen. Lačen filozof, ki ima obe vilici, bo takoj začel jesti (bo zelene barve). Filozof, ki se prehranjuje, bo postal sit z verjetnostjo verjetnost_sitosti. V tem trenutku bo spustil obe vilici in bo spet razmišljal (modra barva).

Vrednost sodelovanje? določa katera strategija se uporablja za pridobivanje in spuščanje vilic. Če je sodelovanje izključeno (off), se uporablja naslednja enostavna strategija:
1. Če je na voljo leva vilica, jo vzemi.
2. Če je na voljo desna vilica, jo vzemi.
3. Če imaš obe vilici, začni s hranjenjem. Drugače poskusi še enkrat.
Ko je filozof sit, se vilice enostavno izpustijo. Označevanje se popolnoma ignorira.

Če je sodelovanje vključeno (on), se uporablja bolj prefinjena strategija z označevanjem. Za pridobivanje vilice:
1. Če je leva vilica na voljo, jo vzemi.
2. Če imaš levo vilico in je označena in še nimaš desne vilice, spusti levo vilico.
3. Če je desna vilica prosta, jo vzemi.
4. Če imaš desno vilico in je označena in še nimaš leve vilice, spusti desno vilico.
5. Če imaš obe vilici, začni s hranjenjem. Drugače poskusi še enkrat.
Ko končaš s hranjenjem, za spustitev vilic:
1. Če je ena od vilic označena, zbriši oznako in označi drugo vilico.
2. Spusti vilici.

KAKO UPORABLJATI?

Začetne nastavitve:
stavilo_filozofov: koliko filozof želiš nahraniti

Gumb nastavi bo nastavil začetne pogoje. Gumb začni bo zagnal simulacijo in gumb »naslednji korak« bo naredil naslednji korak simulacije in ti omogočil, da bolj natančno vidiš kaj se dogaja.

Druge nastavitve:
verjetnost_lakote: Verjetnost, da v nekem koraku nek misleči filozof postane lačen.
verjetnost_sitosti: Verjentost, da v nekem koraku filozof, ki se prehranjuje, postane sit.
sodelovanje?: Če je izključeno, bodo filozofi uporabljali bolj enostavno strategijo za pridobivanje vilic; če pa je vključeno, bodo filozofi uporabljali bolj prefinjeno strategijo. (Zgoraj si lahko pogledaš kako deluje.)
manjavati_se?: Če je vključeno, se bo lahko v enem trenutku premaknil samo en filozof (to vidiš z uporabo gumba naslednji korak); če je izključeno, ima vsak filozof možnost, da se premakne. Če je manjavati_se? vključeno, se bodo lahko nekateri filozofi premaknili dvakrat preden se bodo premaknili vsi filozofi. V povprečju se vsi filozofi premaknejo enakokrat.

Grafa:
Zaužiti špageti: grafično prikaže količino špagetov, ki jih je pojedel vsak filozof (glede na to koliko korakov je vsak filozof bil v fazi hranjenja)
Razporeditev stanj: grafično prikazuje število filozofov v vsaki fazi skozi čas

STVARI, KI JIH JE POTREBNO OPAZITI

Poigraj se z menjavati_se? za različne vrednosti za verjetnost_lakote ter verjetnost_sitosti in za različna števila filozofov. Opaziš lahko, da menjavati_se? vpliva več kot samo na hitrost simulacije, ker ni vsem filozofom zagotovljeno, da se bodo prvič premaknili preden se bo kdorkoli drug premaknil drugič. Ali misliš, da bo to dolgoročno vplivalo na rezultate simulacije? Zakaj da oz. zakaj ne? Pod katerimi pogoji se to zgodi?

Poigraj se z različnimi vrednostmi verjetnost_lakote in verjetnost_sitosti. Opazuj kako različne kombinacije na različne načine vplivajo na sistem. Opaziš lahko, da kljub temu, da sistem pod določenimi pogoji deluje dobro, lahko »težji« pogoji izpostavijo šibkosti. To dokazuje pomembnost »testiranja pod težjimi pogoji« za dosego dobrega sistema, posebno pri prosotnosti konkurence.

STVARI, KI JIH JE VREDNO POSKUSITI

Eksperimentiraj s sodelovanjem v kombinaciji z različnimi nastavitvami za verjetnost_lakote in verjetnost_sitosti. Poskušaj najti situacijo v kateri je očiten kontrast med obnašanjem filozofov, ki sodelujejo in filozofi, ke med seboj ne sodelujejo.

Poskušaj zagnati sistem za dalj časa z različnimi nastavitvami. Ali opaziš, da se kdaj na začetku sistem obnaša dobro, toda sčasoma začne »propadato« (in lahko pride celo do mrtve točke)? Kaj pa obratno? Kaj lahko iz tega sklepaš o vrednosti »dolgoživosti testiranja« pri doseganju stabilnosti in učinka konkurenčnega sistema?

RAZŠIRJANJE MODELA

Poskušaj najti drugačno strategijo za filozofe in jo implementiraj in preveri kako dobro deluje! Verjetno boš želel uporabiti označevanje, zato ne pozabi, da označevanje ni vidno, če je sodelovanje onemogočeno; lahko boš želel tudi to spremeniti. Ali lahko najdeš enostavnejšo strategijo kot je ta, ki smo jo pravkar predstavili?