A Linux Programozása nevű tárgyra adtam be egy helyi hálózatra tervezett elosztott kommunikációt megvalósító rendszert, és példaalklamazásként elosztott quicksort algoritmust. A rendszer tökéletesen elosztott, ami annyit tesz, hogy a helyi hálózatra csatolt gépek mindegyikén fut egy szolgáltatás, ami UDP üzenetek segítségével tartja a kapcsolatot a többi számítógéppel, és felületet nyújt a kommunikációhoz a felhasználói programoknak.
Letöltés
Linux architektúrán legegyszerűbben a következő parancsok végrehajtásával tölthetjük le a forráskódot, és fordíthatjuk le a rendszert:
wget http://users.hszk.bme.hu/~gb606/disco/Makefile
make all
Dokumentáció
Disco Architektúra
A létrehozott rendszer feladata egy helyi hálózatra csatlakoztatott számítógépek kommunikációjának támogatása, anélkül, hogy ehhez szükség lenne központi kiszolgáló segítségére. A központi kiszolgáló feladatait (felhasználók követése, üzenetek továbbítása) szét kell osztani a résztvevő számítógépek között. A legegyszerűbb megoldás az, ha az összes számítógép ismeri a résztvevőket, és kommunikációra UDP üzeneteket, szükség esetén UDP üzenetszórást alkalmazunk.
Minden résztvevő számítógépen fut egy DisCo kiszolgáló, amely a többi számítógéppel tartja a kapcsolatot, és felületet biztosít a felhasználói programok (továbbiakban szolgáltatások, Service-ek) számára Unix Domain Socket-en keresztül.
Lényeges kikötés, hogy egy gépen egyféle szolgáltatásból csak egy futhat egy időben és az egyes szolgáltatások a többi résztvevő gépen csak azonos szolgáltatással kommunikálhat (ez nem jelent korlátozást, hiszen az egyes szolgáltatások maguk is biztosíthatnak felületet a helyi gépen más szolgáltatások számára).
Disco protokoll
Közös csatorna
A résztvevő számítógépek között meg kell oldani azt, hogy az elosztott résztvevők mindegyike egységes képet kapjon a hálózatban szereplő gépekről, és a rajtuk futó szolgáltatásokról. Ezen felül továbbítani kell a szolgáltatások irányított vagy szórt (single-/broadcast) üzeneteit.
A közös csatornán használt üzenetek a következők. A kommunikáció UDP/IP felett történik, minden üzenetet sorvégjel (‘\n’) zár.
| Üzenetformátum | Paraméterek | Jelentés |
|---|---|---|
| (%s | Számítógép szöveges azonosítója | A küldő fél bejelentkezik a hálózatba |
| =%d %s | A rendelkezésre álló szolgáltatások kódolva; szöveges azonosító | Bejelentkezésre válasz: a küldő gép szolgáltatásai, és azonosítója |
| ) | – | Kijelentkezés |
| +%d | Szolgáltatás azonosító | A küldő számítógépen új szolgáltatás indult |
| -%d | Szolgáltatás azonosító | A küldő számítógépen egy szolgáltatás leállt. |
| !%d %s | Szolgáltatás azonosító, üzenet | Irányított üzenet szolgáltatások között |
| .%d %s | Szolgáltatás azonosító, üzenet | Szórt üzenet szolgáltatások között |
Helyi kommunikáció
Kiszolgáló -> Szolgáltatás
| Üzenetformátum | Paraméterek | Jelentés |
|---|---|---|
| (%s | Helyi gép szöveges azonosítója | A kiszolgáló elküldi a helyi gép azonosítóját |
| +%d %s | Távoli gép szám azonosítója, távoli gép szöveges azonosítója | Egy távoli gépen elindult az adottal kompatibilis szolgáltatás |
| -%d | Távoli gép azonosítója | A távoli gépen leállították az adott szolgáltatást |
| !%d %s | Távoli gép azonosítója, üzenet | Irányított üzenet érkezett |
| .%d %s | Távoli gép azonosítója, üzenet | Szórt üzenet érkezett |
Szolgáltatás -> Kiszolgáló
| Üzenetformátum | Paraméterek | Jelentés |
|---|---|---|
| %d | Szolgáltatástípus azonosítója | Szolgáltatás azonosítása a helyi kiszolgáló számára |
| !%d %s | Címzett azonosítója, üzenet | Üzenet küldése a megjelölt számítógépen lévő azonos szolgáltatás számára |
| . %s | Üzenet | Üzenet küldése az összes azonos szolgáltatásnak a hálózatban |
Protokoll folyamatok
Bejelentkezés
Amikor egy új számítógépen elindul a DisCo kiszolgáló, egy bejelentkezés (‘(%s’) üzenetet küld minden számítógépnek a hálózatban. Nyilvánvaló, hogy kezdetben semmilyen szolgáltatás nem fut az újonnan indult kiszolgáló mellett. A bejelentkezés hatására minden számítógép visszaküldi a saját azonosítóját és a rajta futó szolgáltatások azonosítóit kódolva.
Szolgáltatás indítása, leállítása
Minden távoli szolgáltatás indulásakor vagy leállításakor az eseményt jelezni kell az esetleges azonos típusú helyi szolgáltatásnak. Illetve a helyi szolgáltatásokban történt változást szórt üzenetként továbbítani kell a többi számítógépnek.
Egy példa alkalmazás: quicksort
A bemutatott példában a 2-es azonosítóhoz rendeljük a sort szolgáltatást, amely gyorsrendezést valósít meg az elosztott rendszerben. A hálózat bármelyik gépén beadott rendezési feladatot a rendszer autonóm módon szétosztja a feladatot, majd a végeredmény ott lép ki, ahol a feladatot beadtuk.
Pontosítva az algoritmust, (a továbbiakban node-nak hívjuk a sort szolgáltatással rendelkező számítógépeket) ha egy node kap egy rendezési feladatot (egy másik node-tól, vagy a rendszeren kívüli felhasználótól) azt két részre osztja, majd kiválaszt véletlenszerűen két node-ot, akiknek elküldi a két részfeladatot. Minden node oda küldi vissza az eredményt, ahonnan kapta. Ha a végeredményről van szó, akkor azt a részeredmények összerakása után a helyi fájlrendszerben output.txt fájlba rakja.
Protokoll
A quicksort szolgáltatás a DisCo kiszolgáló felületét használva, a fent leírt protokollra épít, az üzeneteit tehát DisCo protokoll szerint felcímezve küldi. Alant csak a DisCo protokoll üzenetrészében szereplő tartalmat fejtem ki, bár az is fontos információt tartalmaz, hogy ki az üzenet címzettje.
| Üzenetformátum | Paraméterek | Jelentés |
|---|---|---|
| ?%d%c%d,%d,… | Feladatazonosító (aminek szerepelnie kell a válaszban); részjelölő karakter: ‘< ' vagy '>‘ attól függően, hogy a feladat a teljes feladat alsó, vagy felső részfeladata; majd a rendezési feladatot leíró vesszővel elválasztott számsorozat (első eleme az adatok száma, majd jönnek a számok) | A küldő node feladatot ad a címzettnek. |
| !%d%c%d,%d,… | A feladatkiírásban szereplő azonosító; a részjelölő karakter; és a rendezett számsorozat hasonlóan a feladatkiíráshoz | A küldő node befejezte a feladatot, és küldi az eredményt. |
Rendezés menete
A felhasználó bármelyik a rendszerbe csatlakozott számítógépen létrehoz egy feladatfájlt, benne a rendezésre váró számokkal, sorvégjellel elválasztva. E fájl nevét beírva a sort programba bekerül a feladat a rendszerbe. Ha minden jól megy, pár pillanat múlva a megoldás bekerül az output.txt -be.
Telepítés és futtatás
A DisCo kiszolgálót és a quicksort szolgáltatást a következő parancsok beírásával lehet a leggyorsabban telepíteni (minden előzetes letöltés nélkül):
wget http://users.hszk.bme.hu/~gb606/disco/Makefile
make all
A fent letöltött Makefile letölti az összes szükséges forrásfájlt, és előállítja a szükséges bináris állományokat, és generál egy azonnal használható input.txt -t. A kiszolgálót futtatni a
./disco _név_
-el lehet, ahol a _név_ egy szabadon választott szöveges azonosítója a számítógépnek. A rendezési feladat generálására alkalmas eszköz az
./inputgen _kimenetszám_
, ami stdout-ra a megadott számú véletlenszámot írja ki. Végül a sort szolgáltatást a ./sort paranccsal indíthatjuk el.