Distributed Connector

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

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.

DisCo architektúra

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.

Leave a Reply