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.

Mintamegoldásként a Budapesti Városmajori Gimnázium FágLógia, Inc. (Bodányi Zsigmond Balázs, Bárczy Huba István, Virágh Bálint) csapatának Python nyelvű megoldását (i637.py), a Budapesti Szent István Gimnázium Felhő (Kezdődy Gréta, Lipcsei Emma Andrea) csapatának C# nyelvű munkáját (i637.cs), és Gyönki Dominik az Egri Neumann János Gimnázium versenyzőjének C++ nyelvű programját (i637.cpp) adjuk közre.

Statisztika:

22 dolgozat érkezett.
10 pontot kapott:	Borsos Benedek, Fajszi Karsa, Gyönki Dominik, Halmosi Dávid, Illés Gergely Levente, Nagy 292 Korina, Palik Csenge, Rajtik Sándor Barnabás, Szabó Imre Bence, Tóth Marcell Domonkos.
9 pontot kapott:	Magyar Levente Árpád.
8 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	2 dolgozat.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2024. októberi informatika feladatai