Télapó probléma

Télapó-problémaAz operációs rendszerek tervezésének fontos része az ütemezési, erőforrás- és szálkezelési feladatok problémamentes, holtpontmentes megoldása, szinkronizálása, amiről sok ismert szerző publikált már, néhányan közülük angol nyelven: W. Stallings, A. B. Downey, A. S. Tanenbaum, A. S. Woodhull., és magyarul is: Galambos Gábor, Knapp Gábor és Adamis Gusztáv. Ehhez a szakterülethez tartozik több népszerű probléma/esettanulmány, például a vacsorázó bölcsek problémája, illetve a Santa Claus Problem, vagyis a Télapó probléma.

A Télapó probléma specifikációját és megoldását a konkurens programozás eszközeire építve J. A. Trono készítette el (szemaforokkal), amire építve is – és kritizálva is azt – több Java implementáció is elkészült (például: P. Steiner), valamint több programozási nyelv szálkezelési lehetőségeinek összehasonlításáról is publikált J. Hurt és J. B. Pedersen és kliens-szerver elosztott környezetben is áttekintette a lehetőségeket D. Marchant és J. Kerridge. Ismert Haskell, Erlang, Polyphonic C# implementáció is.

A Télapó probléma meghatározása

A Télapó alszik az északi-sarki boltjában és csak akkor ébredhet fel, ha mind a 9 rénszarvas visszatér a dél-csendes-óceáni trópusi szigetén töltött rendes évi nyaralásukról, illetve ha akad néhány manó, akiknek nehézségei vannak az ajándékkészítés során. A 10 manó közül 1 manó problémája nem elég komoly ahhoz, hogy felébressze a Télapót (egyébként sosem aludna), így 3 manó megy egyszerre a Télapóhoz. Amikor a 3 manó problémáit közösen megoldották, akkor mind a 3 manónak vissza kell térnie a többi manóhoz, mielőtt egy újabb manólátogatás megtörténne. Ha a Télapó úgy ébred, hogy 3 manó várja őt a bolt ajtajánál és az utolsó rénszarvas is visszatért a trópusokról, akkor a Télapónak fontosabb, hogy olyan gyorsan elinduljon a szánnal, amilyen gyorsan csak lehetséges – így a manóknak várniuk kell karácsony utánig. Feltételezzük, hogy a rénszarvasok nem akarják elhagyni a trópusokat, ezért az utolsó pillanatig maradnak, amíg csak lehetséges. Lehet, hogy egyáltalán nem is jönnének vissza, ameddig a Télapó fizeti a számlát a paradicsomban… Ez is megmagyarázhatja az ajándékok kiszállításának gyorsaságát, hiszen a rénszarvasok alig várják, hogy visszatérhessenek oda, ahol meleg van. Az utolsóként érkező rénszarvas büntetést kap a Télapótól, mialatt a többi rénszarvas a meleg kunyhóban várja, hogy befogják őket a szán elé.

A Télapó probléma – egyik – megoldása

Találtam egy kb. 10 perces kiváló YouTube videót/animációt (The Santa Claus Problem – Thread Synchronization), amely lépésenként felépíti a feladatot, érzékelteti a közben felmerülő problémákat, és megoldást is mutat. Ezt ajánlom december 6-án minden érdeklődő figyelmébe:

A feladatot részletekbe menően és komplex módon gondolkodva kell megtervezni, és implementációi komoly nyelvi eszköztárat igényelnek. Érdemes P. Steiner Java megoldását részletesen átnézni, újragondolva – újabb nyelvi eszköztárral – implementálni.

A feladat a Java EE szoftverfejlesztő tanfolyam 1-4. óra: Elosztott alkalmazások, webszolgáltatások, illetve 5-8. óra: Szálkezelés, párhuzamosság alkalmaihoz kapcsolódik.

Szólj hozzá!