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.