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.

Fát építünk

Fát építünkAz adatok strukturális és könnyen értelmezhető formában való megjelenítése egy szoftver felhasználói felületén átgondolt tervezést igényel. Az adatokhoz hozzá kell jutni, ki kell választani a megfelelő grafikus komponenst, a mögötte lévő adatmodellt, össze kell ezeket kötni. Gyakran előforduló feladat, hogy táblázatosan is ábrázolható adatokból – felhasználva az adatok közötti összefüggéseket és kapcsolatokat – csoportosítva jelenítsünk meg hierarchikusan, fa struktúrában, kinyitható-becsukható formában, ahogyan ezt a felhasználók jól ismerik a fájl- és menürendszereket használva.

Fát építünk kétféleképpen

Adatbázisból, az Oracle HR sémából lekérdezünk két összetartozó nevet: részleg és alkalmazott. A lekérdezés során figyelünk a megfelelő sorrendre, ami a későbbi feldolgozást megkönnyíti. Adatainkat részlegnév szerint növekvő, azon belül alkalmazott neve szerint is növekvő – ábécé szerinti – sorrendbe rendezzük. A vezérlő rétegben két függvényt írunk, amely a modell rétegtől jut hozzá az adatokat tartalmazó generikus listához – átvett paraméterként –, és a visszaadott érték a nézet réteghez kerül.

A csoportváltás algoritmust használjuk, amely 5 blokkból épül fel. A külső ciklus előtti 1. blokk és utáni 5. blokk egyszer hajtódik végre, az előkészítő és lezáró tevékenységek tartoznak ide. A külső ciklus elején és végén található 2. és 4. blokk a belső cikluson kívül fut le, csoportonként, kategóriánként, részlegenként egyszer (most összesen 11-szer mindkettő). A 3. blokk a belső cikluson belül található, és alkalmazottanként egyszer hajtódik végre (most összesen 106-szor).

Háromszintű fát építünk: a gyökérbe (0. szint) fix, beégetett szövegként kerül a cég neve és a teljes létszám. Az 1. szinten jelennek meg a részlegek nevei és a hozzájuk tartozó létszámok. A 2. szint az alkalmazottak neveiből áll.

1. megoldás

A megoldás faKeszit1() függvénye szöveges adatot eredményez. Ez jól használható teszteléshez: megvan-e az összes adat, megfelelő-e a részlegek sorrendje azon belül az alkalmazottak sorrendje, működik-e a csoportosítás, rendben van-e a megszámolás?

A faKeszit1() függvény egy sok lépésben összefűzött (konkatenált) szöveget ad vissza. Az 1. blokkban előkészítjük a fa gyökerét, ami StringBuilder típusú, hiszen sokszor manipuláljuk és inicializáljuk a lista indexelésére használt i ciklusváltozót. A 2. blokkban megjegyezzük az aktuális részleget és előkészítjük az ehhez tartozó alkalmazottak nevét tároló generikus listát ( faReszlegAlkalmazott). Az aktReszleg-hez tartozó alkalmazottak neveit összegyűjtjük a 3. blokkban. Egy részleg feldolgozását a 4. blokkban fejezzük be a fa aktuális 1. és 2. szinten lévő elemeinek szövegbe való beszúrásával. A belső ciklushoz kötődően megszámolást nem kell alkalmaznunk, hiszen az adott részlegben dolgozó alkalmazottak száma a generikus listától elkérhető ( size()). Építünk arra, hogy a külső ciklusból nézve az egymás után végrehajtódó 2. és 4. blokkban az aktReszleg nem változik meg. A 2. blokkban még nem tudjuk a fa aktuális 1. szintjét hozzáfűzni a szöveghez, hiszen a létszám csak a belső ciklusban felépülő kollekciótól kérhető el utólag. Szükséges némi késleltetés, hiszen a szöveg összefűzése és lényegesen egyszerűbb (mint utólag manipulálni megfelelő helyeken). Az 5. blokkban a csoportváltás algoritmushoz kötődő tevékenységünk nincs.

Az 1. megoldás eredménye

2. megoldás

A faKeszit2() függvénynél alkalmazkodunk ahhoz, hogy a JTree vizuális komponenshez DefaultTreeModel observable típusú modell szükséges, így ezzel térünk vissza ( faModell). A fa csomópontjai DefaultMutableTreeNode osztályú objektumok lesznek, amelyeknek a userObject tulajdonsága szükség esetén manipulálható. Az 1 blokkban beszúrjuk a fa gyökerét ( faGyoker), amihez a későbbiekben csatlakozik a fa többi eleme. A 2. blokkban megjegyezzük az aktuális részleget és előkészítjük – megjelenítendő szöveg nélkül – a faReszleg csomópontot. A 3. blokkban fabeli csomópontként a fa 1. szintjén megjelenő részleghez névtelenül hozzáadjuk a fa 2. szintjére kerülő – aktuális részleghez tartozó – alkalmazottak nevét. A 4. blokkban utólag módosítjuk a faReszleg csomópont megjelenítendő szövegét. Az aktuális részleg létszámát itt sem kell külön megszámolni, mert a faReszleg-től elkérhető ( getChildCount()). Az 5. blokkban itt sincs különösebb teendőnk. 

A 2. megoldás eredménye

Fát építünk, képernyőkép

A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

Attól függően, hogyan jutunk hozzá a megjelenítéshez szükséges adatokhoz, több tanfolyamunkhoz is kapcsolódik a feladat és a modell rétegben mindig másképpen tervezünk és implementálunk:

  • A Java SE szoftverfejlesztő tanfolyam 45-48. óra: Adatbázis-kezelés JDBC alapon, 1. rész alkalmán hagyományos SQL lekérdező utasítást készítünk JDBC környezetben.
  • A Java EE szoftverfejlesztő tanfolyam 25-32. óra: Adatbázis-kezelés JPA alapon alkalommal a perzisztencia szolgáltatásait vetjük be.
  • A Java adatbázis-kezelő tanfolyam 13-16. óra: Konzolos kliensalkalmazás fejlesztése JDBC alapon, 1. rész, 33-36. óra: Grafikus kliensalkalmazás fejlesztése JDBC alapon, 2. rész alkalmain hierarchikus lekérdezéseket használunk.

Ismerkedjünk Lambda-kifejezésekkel!

Lambda-kifejezésA Java 8-tól használhatunk Lambda-kifejezéseket, amivel hatékonyabban, rövidebben és könnyebben valósíthatunk meg tipikus műveleteket.

Korábban általában az eseménykezelést globálisan (interfészek implementálásával), vagy lokálisan (névtelen interfész implementálásával) oldottuk meg, illetve besegítettek adapterek is. Sok- és többféle eseménynél ez a forráskódunk elaprózódásához vezetett, ami nehézkes olvashatóságot és karbantarthatóságot eredményezett.

A lambda-kifejezés egy olyan kódrészlet, amelyben valamihez hozzárendelünk valamit, például egy metódus paraméteréhez a végrehajtandó forráskódot ( x -> y). Ehhez építünk a funkcionális interfészekre és a metódus referenciákra (szintén Java 8-tól), illetve a típus kikövetkeztetés képességére is (Java 7-től).

A kiválogatás programozási tételt valósítjuk meg többféle implementációval, felhasználva a Java nyelv újdonságait, és a fentieken kívül még a Stream API-t is.

Adatforrás

Először is kellenek adatok, hiszen azokat dolgozzuk fel. Egy Termek osztályú egyszerű POJO-val dolgozunk, nev és ar tulajdonságokkal, generált konstruktorral, getter metódusokkal és toString()-gel. Az adatforrást biztosító absztrakt Lista ősosztályban a POJO-kból felépítünk egy termekLista nevű generikus listát (például CSV vagy XML fájlból beolvasva az összetartozó adatokat) – listaFeltolt() eljárás – és implementálunk egy univerzálisan használható listaKiir(String uzenet, List termekLista) eljárást is.

Örökítünk három utódosztályt a Lista osztályból, amelyek különbözőképpen dolgozzák fel a termekLista-t, bemutatva a fejlődés útját, illetve a rendelkezésre álló lehetőségeket.

Válogassunk a termékek közül négyféleképpen és adjuk vissza azon termékeket, amelyek:

  • limit alatti áron kaphatók,
  • ára limit1 és limit2 közé esik (zárt intervallumban),
  • neve adott szöveggel kezdődik (kis- és nagybetű különbözik),
  • neve adott szöveget tartalmaz (kis- és nagybetű nem különbözik)!

1. változat

Hagyományos megközelítéssel a fentiek megvalósításához külön egy-egy függvény tartozik, ahogyan az alábbiakban látható:

A termekListaLimitAr1() függvényben látható ötféle lehetőség a kiválogatásra a termekLista-ból:

  • //1: hagyományos, index alapú változat,
  • //2: iterátorra közvetlenül építő változat,
  • //3: bejáró ciklus, iterátorra közvetve építő változat,
  • //4: Stream API-ra építő változat, kiválogatás lambda-kifejezéssel ( filter), a megmaradó termékekre végrehajtandó forEach művelet lambda kifejezéssel,
  • //5: Stream API-ra építő változat, kiválogatás lambda-kifejezéssel ( filter), a megmaradó termékeket összegyűjtő/leképező collect művelettel.

Jól megfigyelhető, hogy négy függvény vázszerkezete megegyezik, és csupán a filter-ben található lambda-kifejezések különböznek. Ez a megoldás meglehetősen redundáns, nem általánosítható, valamint további műveletek megvalósítása további függvények implementálását igényli.

2. változat

Őrizzük meg a négyféle funkciót, sőt tegyük lehetővé, hogy ez tetszőlegesen bővíthető legyen. Használjunk saját generikus, funkcionális Feltetel interfészt saját döntés megvalósítását biztosítani tudó implementálandó teszt() függvénnyel, az alábbiak szerint:

A termekListaFeltetel() függvény paramétere a saját Feltetel interfészünket implementáló névtelen osztály példánya, amely felhasználható:

  • //6: ciklusban egyszerű feltételként,
  • //7: Stream API filter műveletében megadott lambda-kifejezésben,
  • //8: a listaKiir() metódusban paraméterként átadva névtelen osztály példányaként,
  • //9-től: a listaKiir() metódusban paraméterként átadva lambda-kifejezésként.

Látszik, hogy többféle kiválogató művelethez egyetlen implementált függvény szükséges. Ez a megoldás már jóval általánosabb.

3. változat

A saját interfész helyett használjuk fel a beépített Predicate generikus, funkcionális interfészt, építve annak test() függvényére az alábbiak szerint:

Belépési pont

Végül következzen a közös belépési pont, amelyben tetszőlegesen aktiválható és tesztelhető mindhárom változat működése:

Mit ír ki a program a konzolra?

A bejegyzéshez tartozó teljes forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

A feladat a Java SE szoftverfejlesztő tanfolyam szakmai moduljának 21-24. óra: Objektumorientált programozás 2. rész, 25-28. óra: Objektumorientált programozás 3. rész, valamint a Java EE szoftverfejlesztő tanfolyam szakmai moduljának 9-12. óra: XML feldolgozás alkalmaihoz kötődik.

Kockadobás kliens-szerver alkalmazás

Fejlesszünk elosztott, hálózatos, datagram alapú üzenetküldéssel megvalósított Java alkalmazást!

A kockadobás kliens egyszerre két szabályos dobókockával dob, amit ezerszer megismétel és a dobott számok összegét datagram típusú üzenetküldéssel folyamatosan elküldi a szervernek. A szerver localhost-on fut és egy megadott porton keresztül várja a klienstől. A szerver és a kliens egyaránt szálkezelést alkalmazó konzolos alkalmazás.

A projektben van egy swing GUI-s alkalmazás, amely JFreeChart oszlopdiagramon – folyamatosan frissítve – megjeleníti az összesített adatokat, mindez a szerver üzenetküldésével irányítva (amint beérkezik egy dobott (2-12-ig) összeg).

A kommunikációnak – a lehetőségekhez képes – biztonságosnak és – a hálózati adatforgalmat tekintve – takarékosnak kell lennie! Ennek részeként szükséges egy azonosító és egy egyszerű szabály (protokoll).

Tekintsük át mondatszerűen a szálkezelést használó kliens és szerver kommunikációhoz kötődő feladatait:

Ezek működését összefogja egy központi vezérlőosztály és a programok az alábbiak szerint működnek együtt:

A bejegyzéshez tartozó forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

A feladat a Java EE szoftverfejlesztő tanfolyam 1-8. óra: Elosztott alkalmazások, webszolgáltatások, szálkezelés, párhuzamosság alkalmához kapcsolódik.

A képernyőről a videó a FlashBack Express programmal, a videóból az animált gif az aconvert.com weboldalon készült.

Denevérek a barlangban

DenevérekÉvekkel ezelőtt hálózatos Java EE esettanulmányt akartunk készíteni Lengyel Borisz kollégával. Ötleteltünk: milyen technológiával és hogyan kommunikáljon egymással a szerver és a kliens(ek). A távoli metódushívás (Remote Method Invocation) mellett döntöttünk és elkészült a denevérek a barlangban projekt, amely evolúciós projektként azóta több változatot is megélt. A felhasználói felület (barlang) betölt néhány képet (denevér kliensek), amelyek a szerver segítségével mozognak.

Ismertetjük a tervezés folyamatát, a kliens és szerver funkcióit részletesen, végül ötleteket adunk a továbbfejlesztésre.

A főbb feladatokat így határoztuk meg:

  • az RMI kommunikációs módszer megismertetése,
  • az RMI szolgáltatás reprezentálása látványos grafikus/swinges klienssel,
  • alternatíva nyújtása a TCP protokoll közvetlenül csatlakozó socket-jére.

Elkészítettük az alábbi osztálydiagramot (persze ez nem az első változat):

Denevérek a barlangban - Osztálydiagram

A szerver és kliens funkcióit megvalósító osztályok/interfészek feladatait így határoztuk meg:

BarlangDenevérInterfész interfész:

  • véletlen 5 és 10 közötti a denevérek száma,
  • méretek a GUI-hoz.

Denevér osztály:

  • megvalósítja az RMI kliens funkciót,
  • JLabel leszármazott, külső képfájlt tölt be ( bat.jpg),
  • egyedi azonosítója van,
  • eldönti mozgásának irányát (4) és léptékét (3), mintha ultrahangot adna,
  • a szerver megadja neki, hogy az új helyre elmozdulhat-e,
  • saját magát képes mozgatni.

Pozíció interfész:

  • öröklődik a java.rmi.Remote interfészből,
  • két távolról hívható metódus fejét tartalmazza.

BarlangSzerver osztály:

  • megvalósítja az RMI szerver funkciót,
  • implementálja a Pozíció interfészt,
  • JFrame leszármazott,
  • figyel arra, hogy a denevérek ne mozogjanak ki a barlangból.

BarlangFelület osztály:

  • JFrame leszármazott,
  • GUI az RMI kliensek megjelenítéséhez.

BarlangSzerverTérkép osztály:

  • JPanel leszármazott,
  • GUI a szerveren a kliensek mozgásának követésére.

Ha futtatjuk az elkészült szerver és kliens programot, akkor ezt láthatjuk:

Denevérek a barlangban - animáció

A fejlesztés és tesztelés közben sok-sok továbbfejlesztési ötletet/javaslatot fogalmaztunk meg:

  • háttérkép a barlangról,
  • a háttérkép megvalósíthat labirintust, koordináta-rendszert,
  • átlátszó illetve egyedi képfájlok a denevéreknek,
  • a denevérek mozgásának tetszőleges iránya (360),
  • a denevérek mozgásának egyedi léptéke,
  • a denevérek figyeljenek egymásra (ne ütközzenek össze),
  • a denevérek figyeljenek a környezetükre (ne ütközzenek bele sziklákba, cseppkövekbe),
  • a szerver követheti a denevérek útvonalát,
  • a szerver archiválhat, szerializálhat, készíthet statisztikát.

A bejegyzéshez tartozó – több lépésben továbbfejlesztett – forráskódot ILIAS e-learning tananyagban tesszük elérhetővé tanfolyamaink résztvevői számára.

A feladat a Java EE szoftverfejlesztő tanfolyam 21-24. óra: RMI alapú kommunikáció alkalmához kapcsolódik.

A képernyőről a videó a FlashBack Express programmal, a videóból az animált gif az aconvert.com weboldalon készült.