Kezdőlap / Kidolgozott tételek / DEIK Mérnökinformatikus BSC 2017 / 11. tétel

11. Tétel — Folyamatközi kommunikáció eszközei és keresési-rendezési algoritmusok

Frissítve: 2026-09-09

Ez a tétel két nagyobb témakört fed le: a folyamatok közti kommunikáció (IPC) eszközeit, valamint a keresési és rendezési algoritmusokat a hozzájuk tartozó komplexitáselméleti alsó korlátokkal együtt.

Témák

I. Témakör: A folyamatok közti kommunikáció eszközei (IPC)

• A folyamatok közti kommunikáció eszközei (file, szignál, csővezeték, socket).

II. Témakör: Keresési és rendezési algoritmusok, komplexitáselméleti alsó korlátok

• Algoritmusok lépésszáma: beszúrásos rendezés, összefésüléses rendezés, keresések lineáris és logaritmikus lépésszámmal.
• Gyorsrendezés, az összehasonlítások minimális száma.
• Rendezés lineáris lépésszámmal: radix rendezés, vödör rendezés.

I. Témakör: A folyamatok közti kommunikáció eszközei (IPC)

1. Bevezetés: Miért van szükség folyamatközi kommunikációra?

A folyamatok közti kommunikáció (angolul Inter-Process Communication, röviden IPC) azon módszerek és mechanizmusok összessége, amelyek lehetővé teszik a számítógépen futó különböző folyamatok számára, hogy adatokat cseréljenek egymással, és szinkronizálják a tevékenységüket.

A modern operációs rendszerekben minden futó folyamat izolált memóriaterülettel rendelkezik. Ez a szigorú elválasztás a biztonságot és a stabilitást szolgálja: ha az egyik program meghibásodik vagy összeomlik, az nem rántja magával a többi futó alkalmazást.

Mivel azonban a folyamatok nem láthatják közvetlenül egymás memóriáját, szükség van az operációs rendszer (OS) által biztosított hivatalos csatornákra az információcseréhez.

2. File

A fájl alapú kommunikáció a legegyszerűbb IPC mechanizmus, ahol a folyamatok egy közösen elérhető fájlon keresztül cserélnek adatot. A kommunikáció lényege, hogy az egyik folyamat adatokat ír egy fájlba, míg a másik folyamat (vagy folyamatok) ugyanebből a fájlból olvassa ki azokat. A cél itt egy olyan közös, perzisztens adattároló létrehozása, amelyet a folyamatok megoszthatnak.

A kommunikációban részt vevő folyamatoknak ismerniük kell a közös fájl nevét és elérési útját. Az adatcseréhez mindkét folyamatnak rendelkeznie kell a megfelelő jogosultságokkal. Az egyik folyamat megnyitja a fájlt írásra, beleírja a küldendő adatokat, majd lezárja azt. A fogadó folyamat megnyitja a fájlt olvasásra, kiolvassa az adatokat, majd szintén lezárja. Az operációs rendszer garantálja, hogy a fájlba írt adatok a háttértárolóra kerüljenek.

3. Szignál

A szignál egy aszinkron szoftvermegszakítás, amelyet az operációs rendszer kernelje vagy egy másik folyamat küld egy adott folyamatnak egy esemény jelzésére. A kommunikáció csupán egyetlen, előre definiált egész szám elküldésére korlátozódik, amely egy adott eseménytípusnak felel meg.

Működése: Amikor egy folyamat szignált kap, a normál végrehajtása megszakad, és a kernel átadja neki a vezérlést a szignál kezelésére. A fogadó folyamat háromféleképpen reagálhat a beérkező szignálra:

• Alapértelmezett művelet végrehajtása: Minden szignálnak van egy előre definiált alapértelmezett viselkedése. Ez lehet a folyamat terminálása, a folyamat futásának felfüggesztése, vagy a szignál egyszerűen figyelmen kívül hagyása.
• Szignál figyelmen kívül hagyása: A folyamat explicit módon kérheti a kernelt, hogy bizonyos szignálokat hagyjon figyelmen kívül.
• Szignálkezelő rutin futtatása: A folyamat regisztrálhat egy saját, ún. szignálkezelő függvényt, amely a szignál beérkezésekor lefut. Ez a függvény végrehajthat tetszőleges műveletet, majd a vezérlést visszaadhatja a megszakított programpontra.

4. Csővezeték (Pipes)

A csővezeték egy egyirányú adatcsatorna, amelyet az operációs rendszer kernelje hoz létre és kezel a memóriában. Célja, hogy egy folyamat kimenetét egy másik folyamat bemenetére irányítsa át, lehetővé téve a folyamatos adatfolyamot közöttük. A csővezeték egy klasszikus "producer-consumer" modellt valósít meg: az egyik folyamat (producer) írja az adatfolyamot, a másik (consumer) pedig olvassa azt.

A csővezeték a kernelben egy fix méretű körkörös pufferként valósul meg. Amikor egy folyamat adatot ír a csővezetékbe, az adatok a pufferbe kerülnek. Amikor egy másik folyamat olvas a csővezetékből, az adatok a pufferből kerülnek kiolvasásra.

• Névtelen csővezeték (Anonymous Pipe / pipe):
  • Kifejezetten rokon folyamatok (pl. szülő és gyermek folyamat) közötti kommunikációra szolgál. A szülő létrehoz egy csövet a pipe() rendszerhívással, amely két fájl leírót (file descriptor) ad vissza: egyet az olvasáshoz, egyet az íráshoz. A fork() hívás után a gyermek örökli ezeket, így az egyik folyamat ír a csőbe, a másik pedig kiolvassa onnan.
  • Tulajdonság: Szigorúan egyirányú (half-duplex) adatfolyam.
• Nevesített csővezeték (Named Pipe / FIFO):
  • A fájlrendszerben egy speciális névvel rendelkezik, így teljesen független (nem rokon) folyamatok is képesek rajta keresztül kommunikálni úgy, mintha egy hagyományos fájlt olvasnának/írnának, de a háttérben a kernel memóriapuffere továbbítja az adatokat FIFO (First-In, First-Out) elven.

5. Socketek (Sockets)

A socket egy szoftveres végpont a folyamatok közötti kétirányú kommunikációs csatornában. A socket API (Application Programming Interface) egy absztrakciós réteget biztosít, amely elrejti a hálózati kommunikáció alacsony szintű részleteit, és egy, a fájlkezeléshez hasonló interfészt nyújt a programozók számára. A socketek elsődleges célja, hogy lehetővé tegyék a különböző számítógépeken futó folyamatok közötti kommunikációt a hálózaton keresztül, de hatékonyan használhatók egyazon gépen belüli kommunikációra is.

• Unix Domain Sockets (AF_UNIX): Helyi, egy gépen belüli kommunikációra szolgál. A socket a fájlrendszerben egy speciális fájlként jelenik meg, hasonlóan a nevesített csővezetékhez, de kétirányú és jóval rugalmasabb.
• Internet Sockets (AF_INET / AF_INET6): Hálózati kommunikációra szolgál IPv4, illetve IPv6 protokollok használatával. Ez teszi lehetővé a gépek közötti adatcserét.

II. Témakör: Keresési és rendezési algoritmusok, komplexitáselméleti alsó korlátok

1. Keresési algoritmusok és lépésszámuk

A keresés feladata annak eldöntése, hogy egy adott kulcsérték szerepel-e egy adatszerkezetben (pl. tömbben), és ha igen, hol található.

• Lineáris keresés (Linear Search):
  • Működése: A tömb elemeit szigorúan egymás után, sorban vizsgáljuk meg az elejétől a végéig, amíg meg nem találjuk a keresett elemet, vagy a tömb végére nem érünk.
  • Lépésszám (Időkomplexitás): Legrosszabb és átlagos esetben O(n), mivel a bemeneti elemek számával lineárisan arányos a műveletek száma. Előnye, hogy rendezetlen adatszerkezeten is alkalmazható.
• Bináris keresés (Binary Search):
  • Működése: Feltételezi, hogy az adatszerkezet szigorúan rendezett. A keresést a tartomány felezésével végzi: összehasonlítja a keresett értéket a középső elemmel. Ha a keresett érték kisebb, a bal oldali részhalmazon folytatja, ha nagyobb, a jobb oldali részhalmazon.
  • Lépésszám (Időkomplexitás): O(log n), mivel minden egyes lépésben felezedik a vizsgált tartomány mérete.

2. Egyszerű rendezések: Beszúrásos rendezés (Insertion Sort)

A rendezési algoritmusok célja egy adathalmaz elemeinek átrendezése egy adott reláció (pl. növekvő) szerint.

• Beszúrásos rendezés:
  • Működése: A kártyajátékok során alkalmazott módszerhez hasonlít. A tömböt két részre osztjuk: egy már rendezett és egy még rendezetlen részre. A rendezetlen részből folyamatosan veszi az elemeket, és a rendezett rész megfelelő pozíciójába illeszti be azokat, közben eltolva a nagyobb elemeket.
  • Lépésszám:
    • Legrosszabb és átlagos eset: O(n²), amikor a tömb fordított sorrendben van.
    • Legjobb eset: O(n), ha a tömb már eleve rendezett volt (mivel a belső ciklus le sem fut).
  • Tulajdonság: In-place (helyben rendező) és stabil (az azonos kulcsú elemek eredeti sorrendje megmarad).

3. "Oszt és uralkodj" alapú rendezések: Összefésüléses rendezés és Gyorsrendezés

Összefésüléses rendezés (Merge Sort)

• Működése: Klasszikus "oszt és uralkodj" algoritmus. A rekurzív folyamat során a feladatot kettéosztjuk:
  • Rekurzívan felekre bontjuk a tömböt egészen az egyelemű alaptömbökig.
  • Az alaptömböket rendezett módon összefésüljük egy nagyobb rendezett tömbbe.
• Lépésszám: Garantáltan O(n log n) időkomplexitás minden esetben (legrosszabb, átlagos és legjobb esetben is).
• Hátránya: Nem in-place algoritmus, a másolásokhoz és az összefésüléshez O(n) extra memóriaterületet igényel.

Gyorsrendezés (Quicksort)

• Működése: Szintén oszd meg és uralkodj elvű algoritmus.
  • Választunk egy elemet a tömbből, amelyet pivotnak (vezérlőelemnek) nevezünk.
  • Particionálás: A tömb elemeit úgy rendezzük át, hogy a pivotnál kisebb elemek balra, a nagyobbak pedig jobbra kerüljenek.
  • Rekurzívan meghívjuk a particionálást a bal és jobb oldali részre.
• Lépésszám:
  • Átlagos és legjobb eset: O(n log n).
  • Legrosszabb eset: O(n²) (például ha mindig a legnagyobb vagy legkisebb elemet választjuk pivotnak, és a részfák kiegyensúlyozatlanok lesznek).
• Tulajdonság: In-place rendezés, a gyakorlatban a leggyorsabb általános célú rendezés, de nem stabil.

4. Az összehasonlító rendezések alsó korlátja

• Kérdés: Lehetséges-e O(n log n)-nél gyorsabb rendezést készíteni kizárólag elemek közötti összehasonlítások alapján?
• Egy n elemű tömbnek n! (n faktoriális) lehetséges permutációja van. A rendezőalgoritmusnak mind a n! esetet meg kell tudnia különböztetni. Tehát a döntési fának legalább n! levele kell, hogy legyen.
• Egy h magasságú bináris fának legfeljebb 2ʰ levele lehet.
• Ebből következik: 2ʰ ≥ n!.
• Vegyük mindkét oldal 2-es alapú logaritmusát: h ≥ log₂(n!).
• A Stirling-formula alapján log(n!) aszimptotikusan Ω(n log n).

5. Rendezés lineáris lépésszámmal: Radix és Vödör rendezés

Ha az adatok speciális tulajdonságait kihasználjuk, megkerülhető az Ω(n log n) korlát, és lineáris O(n) idejű rendezések valósíthatók meg.

Radix rendezés (Radix Sort)

• Működése: A Radix rendezés nem elemeket, hanem az elemeket alkotó "számjegyeket" (vagy bájtokat, karaktereket) hasonlít össze. A leggyakoribb, ún. LSD (Least Significant Digit) Radix rendezés a legkisebb helyiértékű számjegytől halad a legnagyobbig:
  • Vegyük az n elemű, d számjegyű számokból álló sorozatot.
  • Rendezzük a sorozatot stabilan a legkisebb helyiértékű (LSD) számjegy szerint.
  • Ezután rendezzük stabilan a következő helyiértékű számjegy szerint.
  • Ezt ismételjük d alkalommal, amíg el nem érjük a legjelentősebb (MSD) számjegyet.

A "stabilan" szó itt kulcsfontosságú. Azt jelenti, hogy ha két elemnek az aktuális helyiértéken megegyezik a számjegye, az eredeti sorrendjük nem változhat meg. A Radix rendezés belső rendezőalgoritmusaként leggyakrabban a Leszámláló rendezést (Counting Sort) használják, amely stabil és lineáris idejű.

Vödör rendezés (Bucket Sort)

• Működése: Feltételezi, hogy a bemeneti adatok egy adott intervallumon egyenletesen oszlanak meg. Az adatok értéke alapján az elemeket előre meghatározott számú részre, úgynevezett vödrökbe (buckets) osztja szét. Ezt követően minden egyes vödröt külön-külön rendez egy másik algoritmussal (vagy rekurzívan vödör rendezéssel), majd a vödrök tartalmát sorban összefűzi.
• Lépésszám: Ha az elemek egyenletesen oszlanak meg a vödrök között, a vödör rendezés átlagos időkomplexitása O(n).