Párhuzamos rendszerek modellezése OPM segítségével
Posted by Nucc
Számítógépes hálózatról konyhanyelven
Posted by Nucc
A következő kis szösszenetet még 2006-ban írtam egyetemi éveim alatt, eddig a blogter oldalán pihent. Gondoltam megkeresem, és felveszem a már hivatalos blog oldalamra. Tehát íme egy szösszenet 2006-ból…
Gondoltam megpróbálom szemléltetni a számítógépes hálózatok működését, mert úgy vettem észre egyetemen sokan csak dobálóznak a szavakkal, de hogy mi micsoda, az néha megválaszolatlanul marad.[OFF] Mikor elkezdtem ezt a blogot, nem gondoltam volna, hogy lesz valaki aki olvassa. Meglepetés erejével hatott az a 30 látogató is, még ha nem is olvasták végig, erőt adtak hogy folytassam. Nehéz gondolatokról írni, de megpróbálkozom vele… [/OFF]
Egyetemünkön mindig nagy para van hálózatok évfolyamzh előtt. Újra előkerülnek a kedves kis algoritmusok, Dijkstra, Bellmann-Ford, megint ellepik az 53-as portot a dig lekeresek, es sorolhatnam. A problémát ott látom, hogy senki sem tudja mit miért csinál, copy paste, ide ezt kell írni, oda meg azt. Talán mondhatjuk, hogy a tömegképzés hátránya? A következő pár sorban csak egy kis képet szeretnék mutatni az anyagról, nem oktató jelleg, csak hogy legyen egy kis képünk a dologról.
Próbálok szemléltetést adni az egész tárgyhoz, kicsit az ELTE-s oktatás oldaláról. Sajnos nálunk 1 félévig oktatják, ebben is teli lényegtelen dolgokkal, de mit tehet az ember. Ez van. Megjegyezném, ez nem doksi, ez csak csupán pár gondolat összefűzése.
Az, hogy hogy alakult ki a hálózat, nem mennék bele. De minthogy az informatika az élet digitalizálása, 0-1-re alakítása, így a minta, amire épül nem újkeletű.
Képzeljük el a következőt. Levelet szeretnénk küldeni egyik nagyon jó ismerősünknek. Fogunk egy papirt, ceruzát, megírjuk levelünket, borítékba helyezzük, elszaladunk a postára, majd a posta eljuttatja barátunknak. Ha válaszol rá, akkor pár nap múlva ott lesz a ládánkban a levele. A számítógépes hálózat olyan mint egy postai rendszer. Posta meg már mióta létezik. Na szedjük össze, mi mi is egész pontosan.
Először is, meg kell írnunk a levelet. Vegyünk egy txt filet. Miután megírtuk, fogunk egy borítékot. Ez a boríték felelős azért, hogy más ne tudja elolvasni, és hogy ellássuk olyan információkkal, hogy kinek is küldjük. Ezért lesznek felelősök a csomagolások (amikor fejlécezzük őket).
Na igen. Hogy kinek is küldjük. Az életben mindenkinek van egy postai címe, név, utca, házszám, város, irányítószám. A címe mindenkinek egyedi (az irányítószámot most még ne keverjük bele), elég érdekes lenne, ha egy másik ember kapná meg levelünket, úgyhogy az adatok teljes mértékben rá illenek. Ezért felelős a MAC Address. A MAC Address nem más, mint a hálózati eszköz beleégetett kódja (na jó, ha ügyes az ember megváltoztathaja). Ez alapján mindenki egyedi. A Mac address-el viszont van egy kis probléma. Honnan tudjuk, merre is van az a szerencsétlen célpont. Ez körülbelül olyan, mintha nevet írnék, meg utcát. Talán egyszer megérkezne levelünk, de nem garantálnám biztosra. Kell egy mód, ami alapján levelünk a leggyorsabban ér célba.
Mikor a borítékra felírjuk az irányítószámot, kihangsúlyoznám, irányító!!, azt mondjuk meg a postának, hogy merre fele küldje. Minden posta rendelkezik egy számmal, és a posták közötti forgalom ezekkel a számokkal történik.
Most a példa megkönnyítéséért mindenkinek legyen egy postafiókja, ezzel egyszerűbb lesz követni.
Vegyünk hálózatokat. Hálózatok ugye gépek összekapcsolása. Tehát definiálunk egy közös tulajdonságot, melyre ha illeszkedik egy gép, akkor egy hálózatban vannak. A mi esetünkben egy hálózatban legyenek azok a postafiókok, melyek egy irányítószám alá esnek. Remélem idáig egyértelmű. Az IP cimünk nem más, mint az irányítószám és a postafiókunk egyfajta kotyvaléka. De mi is az az IP cím?
Az IP-nek (Internet Protokol) jelenleg két verziója él. A 4-es és a 6-os. Amiről most szó lesz, az a 4-es verzió, a 6-os még csak az előszobában jár, a mobil-távközlés fogja a nappalinkba terelni. Az IP cím 4 darab 8-bites számból áll, ezeket ponttal választjuk el. 8 bit => 0..255. A 0-nak és a 255-nek kitüntetett szerepe van, ilyen címet nem kaphat gép. Ez alapján tudunk elérni egy gépet. Elrugaszkodva a postától, ez olyan mint egy telefonszám. Amikor azt mondom, hogy 192.168.1.1, akkor ez egy 4-es verziójú IP cím. Egy hálózati eszköz több ilyen címmel is rendelkezhet (több postafókunk is lehet), de egy IP egy géphez tartozik (1 postafiók csak egy 1 személyé lehet). Valahogy definiálnunk kéne azt a közös tulajdonságot, mely alapján 2 gép egy hálózatba kerül. Erre való a netmask. Ez a netmask olyan mint egy maszk. Innen is ered a neve. Most képzeletben vegyünk két ugyanolyan hosszú bináris számsorozatot. Legyen mondjuk a 100110 és a 101001. Az első legyen a cím, a második a mask. Most helyezzük rá a maskot a címre, ahol egyes van, ott legyen az eredeti szám, ahol nulla, oda ne írjunk semmit. Mi a következőt kaptuk: 1_0__0. Ahol _ jel van, oda írhatunk 0-t vagy 1-et, ahol szám, az változatlan. Amely cimek ezek után erre illeszkedik, az a hálózat tagja lesz. Tehát 110110, 100100 egy hálózatba kerülnek, mert a séma mindkettőre illeszkedik. Most még egy gyors példa. Szeretnénk egy olyan hálózatot, mely 2 gépet számol. 192.168.1.1, legyen az egyik cim, 192.168.1.3 legyen a másik cím. Ekkor a gépek az utolsó előtti bitben térnek el, tehát a netmask 255.255.255.253 (mert a 2^1-n változik, és az 255-2=253), az IP amire pedig illesztek, az a 192.168.1.1. Amúgy ha azt írnám, hogy 192.168.1.0/24, az azt jelenti, hogy az IP cím első 24 bitjének változatlannak kell maradnia, de az utolsó 8 bitre, a mi esetünkben a 0 helyére, bármit írhatunk, azok a gépek egy hálózatban lesznek. Létezik továbbá olyan, hogy broadcast, ez egy kitüntetett IP cím, ez felelős azért, hogy egy csomagot minden gép megkapjon. Például azt szeretnénk elküldeni minden gépnek, hogy kapcsoljon ki. Ilyenkor a broadcast cimre küldünk egy kikapcs üzenetet és ilyenkor ezt az összes, a hálózatban lévő gép meg fogja kapni.
Tehát ez alapján már tudunk gépeket csoportosítani. Most nézzük hogy jut el egy boríték egyik helyről a másikra.
A postára érkezik egy levél, amin van egy irányítószám. Mi is történik ezután. Fogja a hölgy a levelet, megnézi hogy a szám ugyanaz-e, mint az ő ir.számuk. Ha igen, akkor berakja a kiküldésre váró levelek közé. Ha nem, megy a központba, majd ott eldöntik mi legyen vele. A központba megérkeznek a levelek, van rengeteg zsák, az egyik zsák az 1-essel keződőek, a másik a 2-essel, és így tovább. Majd amikor megtelik egy zsák, megnézik a számot, és ha 6-ossal kezdődik akkor megy az Alföldre, és így tovább. Majd az Alföldi központban nézik a második számot, megint zsákba, és így tovább (csak Kecskemét száma ugrott most be…).
Gondolom találkoztunk már azzal a szóval hogy Router. Ha otthon több gépünk van, akkor biztos fent van egy a falon, de léteznek ezekből az eszközökből hatalmas példányok is. A router nem más, mint az a hölgy, vagy úr, aki a leveleket zsákokba rakja. A router olyan, mint egy polip. A lábain hálózatok vannak, és van egy kitüntetett lába, ez lesz a GateWay. Jön egy levél, ami egy IP címmel rendelkezik, mégpedig a címzettel. A router megnézi a címet, majd megnézi létezik e olyan hálózat valamelyik lábán, amire ez a cím illeszkedik. Ha nem, akkor a kitüntetett lábra kerül, vagyis a GateWay-re, majd talán ott eldöntik mi legyen vele. Vagyis amikor a postán a kisasszony megnézte, hogy az irányítószám ugyanaz-e, mint az ő számuk, akkor ha igen, akkor ment az egyik lábon a fiókba, ha nem, akkor gateway-re rakta, majd a feljebblévők eldöntik mi is legyen vele. Megjegyezném, hogy minden gépnek van routing táblája, és minden gép ezáltal egy router. Ha ezt most olvasod, akkor egyben egy router előtt is ülsz, aminek a gateway ága ott lóg hátul…
Ha jobban megnézzük, a levelek egy gráfon (pontok, melyek vonalakkal vannak összekötve) vándorolnak, ahol a csúcsok a posták, élek pedig a postások útja, vagy a vonaté ami szállítja, stbstb. Mondjuk Debrecenbe nem úgy szeretnénk eljuttatni levelünket, hogy elküldjük Győrbe, majd Pécsre, majd Szegedre, és onnan végül Debrecenbe. Kicsit sokba kerülne a postának. Dijkstra (azt hisszem Holland matematikus volt, de most hirtelen ??? ) villamosvezetékek elrendezésére kitalált egy algoritmust, amivel legkevesebb vezetékből lehet elektromos hálózatot építeni. Ez lényegében egy gráfon megkeresi a legkisebb súlyú feszítőfát (egyik pontból a másikba a legrövidebb utat, mégpedig minden pontra működik). Vagyis ha összekötjük a postákat, és utána súlyozzuk az éleket a posták közti utazási idővel, akkor egy gráfot kapunk, melyre ha Dijkstra algoritmusát alkalmazzuk megkapjuk a legrövidebb utat két posta között. A routereket ezek alapján konfigurálják, ezzel érik el, hogy minél kevesebb csomagütközés legyen, és lehetőleg a leggyorsabban jusson el csomagunk a partnerhez. Gondolom nem örülnél neki, ha a 2mbites adsl kapcsolattal csak 3 kbyte/sec-el tudnál tölteni, mert körbeutazza a csomag a világot, pedig csak a szomszédnak küldesz egy mp3-at.
Ha már mp3, vagyis zene. Biztos volt már úgy, hogy walkmant hallgattatok és szerettetek volna megmutatni egy számot a haverotoknak. Viszont a szám sztereóban élvezhető, és … na yolvan, a lényeg hogy szükség volt egy jack osztóra. Hálózatoknál is előfordul, hogy hirtelen bekerül egy gép a lakásba, viszont a routeren már nincs több férőhely. Ilyenkor az ember vesz egy switchet, amivel toldhat. Régebben voltak hubok, mostanában már nem kapni, a switch egy intelligens hub. A switch tudja, hogy milyen gép van a lábánál, a hub nem. A hub minden gépnek elküldi az üzenetet ami ő rá van kötve, a switch csak bizonyos lábán. Röviden ennyi a különbség. A probléma akkor áll fenn, ha nagyobb hálózatunk van, tele switchekkel, meg hálózatokkal, és mondjuk az egyik hálózatnak van csak internet kapcsolata. Előfordulhat ugyanis, hogy kör alakul ki, és ekkor egy csomag el kezd cirkulálni a hálózaton, majd bizonyos idő után persze inaktívvál válik és meghal, de addig is lassítja az adatforgalmat.
Erre használjuk Bellmann-Ford algoritmust, ami szintén egy feszítőfát állít elő, ezzel a switchek kimenő ágait tudjuk korlátozni, ezzel küszöböljük ki a köröket.
Erlang
Posted by Nucc
A napokban újra előkapartam Joe Armstrong, Programming Erlang című könyvét, mert kicsit szerettem volna kizökkeni az imperatív nyelvek világából. Az Erlang, egy funkcionális nyelv, erről a fura fajról szeretnék pár sorban írni.
Az Erlanggal tavaly találkoztam, mikor is az OPM (Object Process Methodology) modellnek megfelelő felépítésű nyelvet kerestem. Az OPM egy egységes szerkezet-folyamat leírásra helyezi a hangsúlyt, az UML-ben leggyakrabban használatos szerkezeti diagrammal ellentétben. A szerkezet-folyamat alatt azt értem, hogy egy terven jelennek meg mind az állapotátmenetek, mind pedig az objektumok, melyek az átmenetekben részt vesznek. A folyamatok szemléltetésének van egy hatalmas előnye, mégpedig hogy vizuálisan is elkülönülnek egymástól a független állapotátmenetek, ezáltal a rendszert már az elejétől fogva párhuzamos folyamatokként tekinthetjük, ahol a szinkronázációs pontok (pl. shared object) azon objektumok lesznek, melyek több folyamatban is részt vesznek.
Az Erlang egy funkcionális nyelv, bár rálátásom szerint inkább gyengén funkcionálisnak nevezném. Az imperatív nyelvekben egy függvény értékét mindig az állapottér aktuális állapota határozza meg, így egy tetszőleges függvényt ugyanazokkal a paraméterekkel meghívva teljesen más eredményeket kaphatunk, ellenben a funkcionális nyelvekben szigorúan mindig ugyanazt. Ezen nyelveket inkább kutatásokra alkalmazzák, de egynéhány megjelent az iparban is, ilyen például az Erlang.
Az Erlangot mint írtam félig funkcionálisnak nevezném, ugyanis szekvenciális lefutás esetén (egy process egy szálon) funkcionális. Azonban az Erlang a párhuzamosságot célozta meg fő erényének, azon kívül, hogy gyönyörűen skálázható és igen hibatűrő. Mivel a párhuzamos programok - egész pontosan szálak - szinkronizáció során cserélnek információkat, ezért egy függvény eredményét befolyásolhatja egy másik folyamattal történő szinkronizáció eredménye. Az, hogy párhuzamos teljesen funkcionális nyelv létezhet-e, ezt inkább egy fórumbeszélgetésben boncolgatnám, de érzésem szerint nem.
A szálak futtatását a virtuális gép kezeli, így a szálak kezelése hatékonyabbá válhat, aminek megmagyarázáshoz kell írnom pár sort magáról a nyelvről.
Először is a többi nyelvben megszokott változó itt nem létezik, szerepüket konstansok váltják. Az elv a matemetikából ered, ahol ha azt állítom egy egyenletrendszer megoldásában, hogy x értéke 10, akkor bármely egyenletet tekintve az x értéke 10 lesz. Imperatív nyelveknél már nincs így, például ha veszünk egy számlálót, ami x értékét folyamatosan növeli, akkor ha a folyamatot tekintem, az x=x+1 már ellentmondásba kerülne, hisz nem tudunk olyan x-et mondani, mely kielégítené az egyenletet. Az Erlang egyenletekkel dolgozik, nem pedig értékadásokkal. Merül fel a kérdés, hogy ha nincs változó, akkor mi van helyette? A válasz erre a függvény. Az előző példában szóbahozott számláló nem más, mint egy parciálisan rekurzív függvény. Például az 1-től n-ig számláló függény az az n hosszú f(f(f(…f(0)))) függvénykompozíció, ami x > 0 intervallumon f(x+1) = f(x)+1, x = 0 esetén pedig f(0) = 0. Ekkor f(k) lesz az 1-től k-ig számláló függvényünk.
Amennyiben ennek részeredményeivel szeretnénk dolgozni, tegyük fel kiírni a képernyőre, úgy meg kell mondanunk, hogy miután megnövelte egyel az értéket, mit is tegyen az részeredménnyel. Erre szolgál a funkcionális nyelvekben használatos lambda kalkulus, ami segítségével egy függvényt paraméterként is átadhatunk, és kiértékelése majd egy általunk meghatározott ponton fog megtörténni a függvényben. Ha g(x) a kiirást végző függvény, akkor definiáljuk az f(x+1) = g(f(x)+1) egyenletet, ahol g az az identikus leképezés, mely továbbítja a függvényértéket a videókártya irányába (mondjuk elindítva egy másik folyamatot). Az új függvényünket úgy is írhatjuk, mint f(x+1, g ) := g(f(x,g) +1) ha x > 0, és f(0) = 0.
Milyen előnyökkel járhat, ha a konstansokkal dolgozunk? Párhuzamos környezetben a legnagyobb problémát az osztott változók, úgynevezett erőforrások okozzák. Biztosítanunk kell, hogy állapota mindig konzisztens maradjon, azaz például egyszerre csak egy folyamat módosítsa. Ez konstansok esetén nem okoz problémát, hiszen mindenki csak olvasni fogja. Azonban az erőforrások feladata, a szinkronizáció így nem valósulhatna meg, hisz nincs felület az információcserére.
Erlangban folyamatok létrehozása egy olcsó műveletnek számít, ezt a virtuális gép folyamatkezelőjével éri el (20000 folyamat/16ms). A folyamatok üzenetekkel kommunikálnak egymással. A folyamatokban ellenőrzőpontokat helyezünk el, melyhez egy várakozási sor, és őrfeltételek társulnak. A folyamat akkor haladhat tovább, ha a várakozási sorban lévő üzenetek valamelyikére érvényesül egy őrfeltétel. Amíg a blokkoltság fennáll, a folyamat állapota változatlan. Így ha a számlálós példát nézzük, a g függvény blokkolódjon mindaddig amíg nem kap egy üzenetet, és üzenet esetén pedig hívja meg rekurzívan önmagát úgy, hogy a számláló aktuális értékét reprezentáló konstanst növelje meg egyel. Mivel g is bárkinek üzenhet, így akár x aktuális értékét elküldheti üzenet formájában másoknak. Tehát mint látható, Erlangban az osztott változókat függvények veszik át, melyek folyamata bármikor megszakítható, és folytatható. A kommunikáció asszinkron, vagyis az üzenet elküldésével a küldő tovább fut, amíg nem terminál, vagy pedig blokkolódik.
Ez a fajta elgondolás előnye, hogy minden folyamat izoláltan fut, nem kell senkivel semmit megosztania. Ekkor viszont nem számít, hogy melyik processoron fut, továbbá az sem szükséges, hogy ugyanazon a gépen fusson ahol a többi szál. Ekkor igaz számításba kell venni a hálózati közeg sebességét (a programban szabályozhatjuk az elhelyezést), de a virtuális gépeket fürtbe szedve a folyamatokat bárhol elindíthatjuk a hálózaton, az üzenetküldést pedig a virtuális gép irányítja.
További előny, hogy imperatív nyelven megírt programoknál egy folyamat létrehozása költséges, és az operációs rendszer irányítja. Webszervereknél alkalmazzák például, hogy elindítanak 5-6 szálat, és minden, a kliens felől érkező kérést egy úgynevezett balancer valamelyik szálra tereli. Azonban problémát okozhat, ha a szerver hirtelen kap nagy terhelést. Ekkor új szálakat kéne létrehozni, ami költséges, ugyanakkor állandóan többet fenntartani pedig memóriaigényes. Erlang esetén mivel egy szál létrehozása olcsó, minden kérést külön szálra tehetünk, és akár kényelmesen újabb gépeket helyezhetünk szolgálatba bárminemű kódváltoztatás és külső eszköz (mások által megírt ütemező) nélkül.
Amennyiben érdekelnek a nyelv rejtelmei, látogass vissza később!
http://nucc.bteam.hu
OPM: http://www.slideshare.net/guest77b0cd12/object-process-methodology-presentation
Sztaki gyorsgomb
Posted by Nucc
Zolival összedobtunk egy patch-et a sztaki-szótár firefox extensionjéhez, ugyanis rohadtul zavart, hogy amennyiben egy angol szó jelentésére vagyok kíváncsi, akkor a kijelölés, jobb-gomb, listából kikeres, kattintás szekvenciális sorozatot végig kell játszanom. Erre jött az ötlet, hogy duplaklikk a szóra, és egy billentyű lenyomására már ugorjon is az ablak. Ez a billentyű a “d” lett, továbbá bevezettünk egy “f”-et is, ami levágja a többesszámot és az ing suffixot, ezzel megspórólva a hasonló szavakon való bolyongást. Amennyiben van még ötlet, írjatok!