FIFOjärjestys

FIFOjärjestys, tai First-In-First-Out, on periaate, jonka mukaan ensimmäiseksi syötetty yksikkö poistetaan tai käsitellään ensimmäisenä. Sitä käytetään erityisesti jonojen tai puskureiden yhteydessä, joissa tulo- ja lähtöjärjestyksen on oltava säilytettyä.

FIFOjärjestyksen toteuttamiseen käytetään usein jonon rakenteita. Jono tukee tyypillisiä operaatioita kuten enqueue (lisää alkio lopulle), dequeue (poistaa ja palauttaa ensimmäisen alkion) sekä katsoa ensimmäistä alkiota ilman poistamista (peek tai front). Kun järjestys säilyy, aikaisemmin tulleet yksiköt käsitellään ennen myöhemmin tulleita, mikä tekee FIFO:stä luotettavan ja ennakoitavan.

Tietokoneissa FIFO voidaan toteuttaa esimerkiksi linkitettynä listana tai kiertokantajana taulukkoon. Tällöin enqueue ja dequeue tapahtuvat yleensä O(1) ajassa, kun pään ja hännän osoittimet ovat kunnossa. Säiliön koko voi olla rajoitettu tai rajoittamaton; kiertokanta mahdollistaa tehokkaan tilankäytön, kun tilaa on rajallinen.

Sovelluksia ovat muun muassa tulostusjonot, käyttöjärjestelmän prosessien ja tehtävien aikataulutus, verkon pakettien puskurointi sekä viestijonot järjestelmissä. FIFO tarjoaa yksinkertaisen ja oikeudenmukaisen menetelmän kohtalon varmistamiseen, jos prioriteetteja ei käytetä.

Rajoituksina FIFO ei huomioi erilaisten tehtävien tärkeyttä; pitkät jonot voivat johtaa konvoili-ihmikuvaan (convoy effect) ja vasteaikojen nousuun. FIFO-järjestyksiä voidaan laajentaa tai muokata käyttämällä kiertokantoja, rajattuja kokoonpanijoita tai priory-jonoja, kun tarvitaan priorisointia tai parempaa vasteaikaa.