A FIFO ( eng. f first i n, f first o ut "first in, first out") az adatok idő és prioritások szerinti rendezésének és kezelésének módja. Ez a kifejezés leírja a várólista technikai feldolgozásának elvét vagy az egymásnak ellentmondó követelmények fenntartását a folyamat egyszerűsítésével az érkezési sorrendben való kiszolgálás elve (FFS) szerint. Aki előbb érkezik, azt szolgálják ki először, a következő megvárja, amíg az első szolgálata befejeződik, és így tovább.
Ez az elv analóg a sorban állók viselkedésével, amikor az emberek abban a sorrendben kapják meg a szolgáltatást, ahogyan beálltak a sorba. Ugyanez történik például egy szabályozatlan kereszteződésben, amikor a sofőrök a sorukra várva folytatják a vezetést (az Egyesült Államok közlekedési szabályaiban nincs „jobboldali beavatkozás” szabály, az elsőbbség meghatározása a FIFO-elv szerint történik). Az APP a FIFO operációs rendszer ütemezési algoritmusának rövidítéseként is használatos, amely az egyes folyamatokhoz a CPU-időt a kiszolgálás sorrendjében rendeli hozzá.
Tágabb értelemben a LIFO absztrakció ( l ast- i n, f first- o ut "utolsó be, első ki") a FIFO absztrakció ellentéte. A különbség egyértelműbbé válhat, ha figyelembe vesszük a ritkábban használt FILO szinonimát, ami azt jelenti, hogy „ first in-last-out ” („first in, last out”). Lényegében mindkét absztrakció sajátos esete a listamanipuláció általánosabb fogalmának. A különbség nem a listában (adatokban), hanem a tartalomelérési szabályban van. Az első esetben az összeadás a lista egyik végéhez, a másikból a kivonás, a második esetben az összeadás és a kivonás az egyik végén történik. [egy]
FIFO esetén a listát queue -nak, LIFO esetén veremnek nevezzük .
A sor egy változata a prioritási sor , amelyre a FIFO név nem használható, mert ebben az esetben az adatstruktúra feldolgozása más módon történik. A sorban állás elmélete kiterjed a sor általánosabb fogalmára, valamint a sorok közötti interakcióra, amelyben a szolgáltatás a "szigorú FIFO" elv szerint történik. Ennek az elvnek a jelölésére az FCFS rövidítést is használják . _ Gyártáshoz az FPFO opció lehetséges ( f first p roduct , f first o ut ).
A számítástechnikában a kifejezés a sorban feldolgozott adatok tárolási módjára utal . A sor minden eleme egy sor adatstruktúrában van tárolva ( nincs kivétel ). A sorba elsőként hozzáadott adat kerül ki belőle elsőként, vagyis a feldolgozás szekvenciálisan, az érkezéssel megegyező sorrendben történik.
Egy tipikus adatstruktúra így néz ki (példa a C++ nyelven ):
struct fifo_node { struct fifo_node * next ; érték_típus érték ; }; osztályú fifo { fifo_node * front ; fifo_node * vissza ; fifo_node * dequeue ( érvénytelen ) { fifo_node * tmp = front ; front = front -> next ; return tmp ; } sor ( érték ) { fifo_node * tempNode = new fifo_node ; tempNode -> érték = érték ; vissza -> next = tempNode ; back = tempNode ; } };(Az absztrakt adatstruktúrákért lásd: várólisták . A megvalósítás részleteit lásd a gyűrűs pufferben .)
A népszerű Unix rendszerek közé tartozik a sys/queue.h fejlécfájl a C / C++ programozási nyelvekben , amely a FIFO soralkalmazásokban használt makrókat tartalmazza.
A "fej" és a "farok" kifejezésekkel kapcsolatban vita van a FIFO-sorokkal kapcsolatban. A legtöbb ember számára egy új elem hozzáadása a sorhoz a végén történik, majd ez az elem addig marad a sorban, amíg el nem éri, és ennek megfelelően onnan hagyja el a sort. Ezt a nézőpontot az egyes szolgáltatásokra várakozók soraival való analógia indokolja, míg a fenti példában az „elöl” és a „hátul” kifejezések használatával találhatunk párhuzamot. Egyesek azonban úgy vélik, hogy az új tárgy a sor élére kerül, és a farkán keresztül távozik, mint a kígyó testén áthaladó táplálék. Az így leírt sorok ott jelennek meg, ahol hivatalosnak tekinthetők, például a GNU/Linux operációs rendszer leírásában .
Azokban a számítási környezetekben, amelyek támogatják a folyamatok közötti kommunikációhoz használt folyamat- és szűrőmodelleket , a FIFO a névvel ellátott cső alternatív neve .
A lemezvezérlők használhatják a FIFO metódust algoritmusként a lemez I/O kérések ütemezéséhez.
A számítógépes hálózatokban használt kommunikációs hidak , kapcsolók és útválasztók FIFO puffereket használnak az adatcsomagok tárolására, amint azok a következő úticéljukra utaznak. Általában minden hálózati kapcsolathoz legalább egy FIFO struktúrát használnak. Egyes eszközök több FIFO-val rendelkeznek a különböző típusú információk egyidejű és független soraihoz.
A FIFO elvet általában az elektronikus áramkörökben használják a hardvertől a szoftverig terjedő áramlás pufferelésére és szabályozására. Hardveres formában a FIFO alapvetően sok olvasási és írási mutatóból, memóriából és vezérlőlogikából áll. A memóriaeszköz lehet SRAM , flip-flop, reteszelő vagy bármilyen más megfelelő típusú. A nagyobb FIFO-k általában kettős SRAM portot használnak, az egyik portot írásra, a másikat olvasásra használják.
A FIFO szinkron, amelyben ugyanazt az órát használják mind az olvasáshoz, mind az íráshoz. Az aszinkron FIFO-k különböző órákat használnak az olvasáshoz és az íráshoz. Az aszinkron FIFO-k használatakor metastabilitási probléma lép fel . Leggyakrabban az aszinkron FIFO-mutatók implementálásakor Gray kódot (vagy bármely más kódot, amelyben a jelskála két szomszédos értéke csak egy bittel különbözik) használnak a zászló megbízható generálásának biztosítására. Azt is megjegyezzük, hogy az aszinkron FIFO-megvalósításokban jelzők generálásához aritmetikai mutatók használata szükséges. Ezzel szemben a szinkron FIFO-megvalósításokban jelzők létrehozásához vagy a szivárgó vödör algoritmusa vagy ugyanaz az aritmetikai mutató használható.
Példák a FIFO állapotjelzőre: tele, üres, majdnem tele, majdnem üres stb.
A FIFO első ismert implementációja az elektronikában Peter Alfke (1931-2011) volt 1969-ben a Fairchild Semiconductornál [2] . Peter Alfke is a Xilinx igazgatója volt .
Hardver eszközökben a FIFO elvet használják a szinkronizáláshoz. Gyakran csengetési sorként valósítják meg, és két mutatója van:
Kezdetben az olvasási és írási címek megegyeznek az első memóriapozícióval, és a FIFO-sor üres.
A FIFO-sor üres Amikor az olvasási címregiszter utoléri az írási címregisztert, a FIFO flip-flop üres jelet ad ki. A FIFO-sor megtelt Amikor az írási címregiszter utoléri az olvasási címregisztert, a FIFO flip-flop Full jelet ad ki.