Az I. 637. feladat (2024. október)

I. 637. A számítógépes hálózatok fejlesztésének hőskorában különféle eljárásokat találtak ki a gépek közötti kommunikáció megvalósítására. Az egyik ilyen technológia logikailag kör alakban egymáshoz kapcsolt számítógépek közötti adatátvitelt valósít meg. A kört gyűrűnek is hívják, a technológia neve Token Ring, elterjesztője az 1980-as évektől az IBM volt.

Tekintsük úgy, hogy a számítógépek kör alakban vannak elrendezve és egy közös adatátviteli vonalra csatlakoznak. Ezen a vonalon halad egy irányba körbe egy speciális jel, a token, illetve mögötte az adatok. Ha nincs a vonalon adat, tehát egyik gép sem küld a másiknak, akkor csak a token utazik körbe. Ha van adat, akkor az a token mögött van és tartalmazza az adatot küldő és fogadó számítógép címét is.

A számítógépek a vonalat figyelik, és ha elér egy géphez a token, akkor a következők egyike történik:

• Ha a token 0 értékű és nincs mögötte adat, akkor a vonalon éppen nem történik adatküldés. Ha a gép küldeni akar adatot, akkor megteheti: a tokent 1-re állítja, és elhelyezi mögötte a vonalon az adatot a küldő és fogadó gép címével együtt. Ha nem akar küldeni, akkor csak továbbküldi a 0 értékű tokent a körben következő gépnek.
• Ha a token 1 értékű és van mögötte adat, akkor a gép megvizsgálja, hogy ki az adat címzettje. Ha ő a címzett, akkor kiolvassa az adatot, majd továbbküldi a tokent 0 értékkel és magát az adatot is. Ha nem ő a címzett, akkor továbbküldi a kapott tokent 1-es értékkel és az adatot is.
• Ha a token 0 értékű és van mögötte adat, akkor a gép megvizsgálja, hogy ő volt-e az adat feladója. Amennyiben ő volt, akkor törli az adatot és továbbküldi a tokent 0 értékkel. Ha nem ő volt a feladó, akkor továbbküldi az adatot és a tokent 0 értékkel.

A gépek ilyen szabályok szerinti működése biztosítja, hogy a hálózaton mindig csak egy adat legyen, és ne történhessen meg, hogy két gép egyszerre küld adatot, mert ekkor a vonalon lévő elektromos jelek értelmezhetetlenné válnának. Ezt a jelenséget ütközésnek nevezik, amelyet a Token Ring technológiával így el lehet kerülni. A ma legelterjedtebb Ethernet technológia másként oldja meg az ütközés problémáját.

A Token Ring működésének hatékonysága függ attól, hogy hány számítógép van a körben, illetve ezek a gépek mekkora valószínűséggel kívánnak adatokat küldeni. Készítsünk számítógépes programot és modellezzük a hálózat működését: vizsgáljuk meg, hogy átlagosan mennyi időbe telik egy adatcsomag átvitele két gép között. A modellezés során feltételezzük, hogy a token és az adat egyik géptől a mellette lévő másik gépig egy időegység alatt ér át. A számítógépek a modellben elhanyagolható idő alatt végzik a tevékenységüket, tehát a \(\displaystyle t\)-edik időegységben fogadott tokent és adatot a \(\displaystyle (t+1)\)-edik időegységben küldik tovább.

A szimuláció során minden gép, amely éppen nem kíván adatot küldeni egy véletlenszámtól függően eldönti, hogy a következő időegységtől kezdve küld-e adatot, vagy sem. Az adatküldésre való hajlandóságot egy \(\displaystyle H\) véletlenszámmal adjuk meg. Ha egy gép egyszer úgy döntött, hogy küldeni szeretne, akkor egészen addig ebben az állapotában marad, amíg az adat elküldése és annak nyugtázása meg nem történik. Ez a Token Ring esetében akkor következik be, amikor egy 0 értékű token mögött olyan adatot olvas a gép a vonalról, amelynek ő a feladója.

Példaként egy 10 gépből álló hálózatban az egyik gép adatot akar küldeni egy tőle 4 egységre lévő másik géphez. Az adatküldés igényétől kezdve példaként még várnia kell 15 időegységet, hogy elérjen hozzá a 0 értékű token adatok nélkül. Ekkor feladja az adatot és 1-re állítja a tokent, amely 4 időegység múlva megérkezik a fogadóhoz. A fogadó beolvassa a számára küldött adatot, majd 0 tokennel továbbítja azt. A token és az adat 6 időegység után visszaérkezik a feladó géphez, amely nyugtázza a sikeres adatküldést, ami így \(\displaystyle 15+4+6\) időegységig tartott.

A program standard bemenetének egyetlen sorában a gépek \(\displaystyle N\) száma (\(\displaystyle {2\leq N\leq 255}\)), a gépek adatküldését jellemző H valószínűség (\(\displaystyle 0\leq H< 1\)), valamint a szimuláció teljes idejét időegységben megadó \(\displaystyle T\) érték (\(\displaystyle 1000\leq T <100\,000\)) található egy-egy szóközzel elválasztva.

A program a standard kimenetre egy egész és egy valós számot írjon szóközzel elválasztva: mennyi adatot sikerült a szimuláció során átjuttatni a hálózaton, illetve átlagosan mennyi idő telt el egy-egy adat esetén a küldési hajlandóságtól az adatküldés nyugtázásáig.

Példák:

Beküldendő egy tömörített i637.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2024. november 15-én LEJÁRT.

Statisztika:

Az I. 637. feladat értékelése még nem fejeződött be.

A KöMaL 2024. októberi informatika feladatai