FIFO ( eng. f first i n, f first o ut "first in, first out") on tapa järjestää ja käsitellä dataa ajan ja prioriteettien suhteen. Tämä lauseke kuvaa jonon teknisen käsittelyn periaatetta tai ristiriitaisten vaatimusten ylläpitoa virtaviivaistamalla prosessia FFS-periaatteen mukaisesti. Ensiksi tullutta palvellaan ensin, seuraava odottaa, kunnes ensimmäisen palvelus on suoritettu, ja niin edelleen.
Tämä periaate on analoginen jonossa seisovien ihmisten käyttäytymiseen, kun ihmiset saavat palvelua siinä järjestyksessä, jossa he tulivat jonoon. Sama tapahtuu esimerkiksi sääntelemättömässä risteyksessä, kun kuljettajat odottavat vuoroaan jatkaakseen ajoa (USA:n liikennesäännöissä ei ole "häiriöt oikealle" -sääntöä, etuoikeus määräytyy FIFO-periaatteen mukaan). APP:ta käytetään myös lyhenteenä FIFO-käyttöjärjestelmän aikataulutusalgoritmista, joka varaa CPU-aikaa kullekin prosessille siinä järjestyksessä, jossa niitä huolletaan.
Laajemmassa merkityksessä LIFO - abstraktio ( l ast- i n, ensin " viimeinen sisään, ensimmäinen ulos") on FIFO-abstraktion vastakohta. Ero voi tulla selvemmäksi, jos otamme huomioon harvemmin käytetyn synonyymin FILO, joka tarkoittaa ensimmäinen sisään viimeinen ulos ("first in, last out"). Pohjimmiltaan molemmat abstraktiot ovat erityistapauksia yleisemmästä luettelon manipuloinnin käsitteestä. Ero ei ole luettelossa (tiedoissa), vaan sisällön käyttösäännössä. Ensimmäisessä tapauksessa lisääminen tehdään listan toiseen päähän ja vähennys toisesta, toisessa tapauksessa lisääminen ja vähentäminen tehdään toisessa päässä. [yksi]
FIFO:n tapauksessa listaa kutsutaan jonoksi , LIFO :n tapauksessa pinoksi .
Jonon muunnos on prioriteettijono , jolle ei voida käyttää nimeä FIFO, koska tällöin tietorakenteen käsittely tapahtuu eri tavalla. Jonoteoria kattaa yleisemmän jonon käsitteen sekä jonojen välisen vuorovaikutuksen, jossa palvelu suoritetaan "tiukan FIFO"-periaatteen mukaisesti. Tätä periaatetta käytetään myös lyhenteellä FCFS . _ _ _ _ _ Tuotannossa FPFO- vaihtoehto on mahdollinen ( ensimmäinen tuote , ensimmäinen tuote ) .
Tietojenkäsittelytieteessä termi viittaa tapaan, jolla jonossa käsiteltävät tiedot tallennetaan . Jokainen jonon elementti on tallennettu jonotietorakenteeseen ( ei poikkeuksia ). Ensimmäiset jonoon lisätyt tiedot poistetaan siitä ensimmäisenä, eli käsittely suoritetaan peräkkäin samassa järjestyksessä kuin saapuminen.
Tyypillinen tietorakenne näyttää tältä (esimerkki C++ :ssa ):
struct fifo_node { struct fifo_node * next ; arvo_tyyppi arvo ; }; luokan fifo { fifo_node * etuosa ; fifo_node * takaisin ; fifo_node * dequeue ( void ) { fifo_solmu * tmp = etuosa ; edessä = edessä -> seuraava ; paluu tmp ; } jono ( arvo ) { fifo_solmu * tempNode = uusi fifo_solmu ; tempNode -> arvo = arvo ; takaisin -> seuraava = tempNode ; takaisin = tempNode ; } };(Katso abstrakteja tietorakenteita, katso jonot . Katso toteutustiedot soittopuskurista .)
Suosittuja Unix-järjestelmiä ovat sys/queue.h-otsikkotiedosto C / C++ -ohjelmointikielillä , joka sisältää FIFO-jonosovelluksissa käytetyt makrot.
FIFO-jonojen yhteydessä on kiistaa termeistä "pää" ja "häntä". Useimmille ihmisille uuden elementin lisääminen jonoon tapahtuu sen pyrstössä, jolloin tämä elementti pysyy jonossa, kunnes se saavuttaa päänsä ja vastaavasti poistuu jonosta sieltä. Tämä näkemys on perusteltua analogisesti joidenkin palveluiden odottavien ihmisten jonojen kanssa, kun taas yllä olevassa esimerkissä yhtäläisyyksiä voidaan löytää käyttämällä termejä "etu" ja "taka". Jotkut ihmiset kuitenkin uskovat, että uusi esine tulee jonon päähän ja lähtee siitä hännän kautta, kuten ruoka kulkee käärmeen kehon läpi. Tällä tavalla kuvatut jonot näkyvät siellä, missä niitä voidaan pitää virallisina, kuten GNU/Linux - käyttöjärjestelmän kuvauksessa .
Laskentaympäristöissä, jotka tukevat liukuhihna- ja suodatinmalleja prosessien välistä viestintää varten , FIFO on vaihtoehtoinen nimi nimetylle putkelle .
Levyohjaimet voivat käyttää FIFO-menetelmää algoritmina levyn I/O-pyyntöjen ajoittamiseen.
Tietoliikennesillat , kytkimet ja reitittimet , joita käytetään tietokoneverkoissa, käyttävät FIFO-puskureita datapakettien tallentamiseen, kun ne matkustavat seuraavaan kohteeseen . Tyypillisesti jokaista verkkoyhteyttä kohden käytetään vähintään yhtä FIFO-rakennetta. Joissakin laitteissa on useita FIFO:ita erityyppisten tietojen samanaikaisille ja riippumattomille jonoille.
FIFO-periaatetta käytetään yleisesti elektronisissa piireissä puskuroimaan ja ohjaamaan kulkua laitteistosta ohjelmistoon. Laitteistomuodossa FIFO koostuu periaatteessa monista luku- ja kirjoitusosoittimista, muistista ja ohjauslogiikasta. Muistilaite voi olla SRAM , flip-flop, salpa tai mikä tahansa muu sopiva tyyppi. Suuremmat FIFOt käyttävät tyypillisesti kahta SRAM-porttia, joista toista käytetään kirjoittamiseen ja toista lukemiseen.
FIFO on synkroninen, jossa samaa kelloa käytetään sekä lukemiseen että kirjoittamiseen. Asynkroniset FIFOt käyttävät erilaisia kelloja lukemiseen ja kirjoittamiseen. Asynkronisia FIFO -tiedostoja käytettäessä on metastabiliteettiongelma . Useimmiten asynkronisia FIFO-osoittimia toteutettaessa käytetään harmaata koodia (tai mitä tahansa muuta koodia, jossa signaaliasteikon kaksi vierekkäistä arvoa eroavat vain yhdellä bitillä) lipun luotettavan generoinnin varmistamiseksi. Huomaa myös, että lippujen luomiseksi asynkronisissa FIFO-toteutuksissa on käytettävä aritmeettisia osoittimia. Sitä vastoin lippujen generoimiseksi synkronisissa FIFO-toteutuksissa voidaan käyttää joko leaky bucket -algoritmia tai samaa aritmeettista osoitinta.
Esimerkkejä FIFO-tilalipusta ovat: täynnä, tyhjä, melkein täynnä, melkein tyhjä jne.
Ensimmäinen tunnettu FIFO-toteutus elektroniikassa oli Peter Alfke (1931-2011) vuonna 1969 Fairchild Semiconductorissa [2] . Myös Peter Alfke oli Xilinxin johtaja .
Laitteissa synkronoinnissa käytetään FIFO-periaatetta. Se toteutetaan usein soittojonona ja siinä on kaksi osoitinta:
Aluksi luku- ja kirjoitusosoitteet ovat molemmat yhtä suuria kuin ensimmäinen muistipaikka, ja FIFO-jono on tyhjä.
FIFO-jono on tyhjä Kun lukuosoiterekisteri saavuttaa kirjoitusosoiterekisterin, FIFO-kiikku antaa tyhjän signaalin. FIFO-jono täynnä Kun kirjoitusosoiterekisteri saavuttaa lukuosoiterekisterin, FIFO-kiikku antaa Full-signaalin.