FIFO je akronim za "prvi uđe, prvi izađe" (engl. first in, first out), a predstavlja metod za organizovanje i manipulisanja baferom podataka, pri čemu se najpre obrađuje najstariji (prvi) unos ili "glava" reda. Slično je obradi reda (eng. FCFS - "first-come, first-served"), gde prvi koji dođe, prvi bude uslužen i ljudi napuštaju red u redosledu u kom dolaze.

Prikaz FIFO metode, gde je operacija enqueue ubacivanje u red, a dequeue izbacivanje iz reda.

FCFS je takođe žargonski izraz za FIFO algoritam za raspoređivanje kod operativnog sistema, koji svaki proces daje centralnoj procesorskoj jedinici redom kako je zahtevano. Suprotnost za FIFO je LIFO (eng. last in, first out - "poslednji uđe, prvi izađe") gde se poslednji unos ili "vrh steka" prvi obrađuje.[1] Red sa prioritetom nije ni FIFO ni LIFO ali može prihvatiti slično ponašanje privremeno ili podrazumevano. Teorija čekanja obuhvata ove metode za obradu struktura podataka, kao i interakcije između striktnih FIFO redova.

Računarske nauke uredi

Struktura podataka uredi

U zavisnosti od primene, FIFO se može implementovati kao hardverski pomerački registar, ili kao različite strukture memorije, obično kao kružni bafer ili kao neka vrsta liste. Većina softverskih implementacija FIFO reda nije sigurna za niti i zahteva zaključavanje da bi se osiguralo da je lanac strukture podataka korišćen od strane samo jedne niti u nekom trenutku.

Kod uredi

Sledeći kod prikazuje implementaciju FIFO povezane liste u C++ programskom jeziku.

#include <iostream>
#include <stdexcept>
 
template <typename T>
class FIFO {
private:
    struct Node {
        T     value;
        Node *next;

        Node(T _value) : value(_value), next(NULL) {}
    };
    
    Node *front;
    Node *back;

public:
    FIFO() : front(NULL), back(NULL) {}

    ~FIFO() {
        while (front != NULL)
            dequeue();
    }

    void enqueue(T _value) {
        Node *newNode = new Node(_value);

        if (front == NULL)
            front = newNode;
        else
            back->next = newNode;

        back = newNode;
    }

    T dequeue() {
        if (front == NULL)
           throw std::underflow_error("Nothing to dequeue");

        Node *temp   = front;        
        T     result = front->value;

        front = front->next;
        delete temp;

        return result;
    }
};

Glava ili rep prvi uredi

Krajevi FIFO reda često se nazivaju glavom i repom. Nažalost, postoji kontroverza u vezi sa tim terminima:

  • Za mnoge ljude, stakve treba da se unose u red od repa dok ne stignu do glave i odatle napuštaju red. Ova tačka gledišta opravdana je analogno sa redovima ljudi koji čekaju neku vrstu usluživanja i prednji i zadnji dio reda paralelan je sa glavom i repom iz ovog primera.
  • Drugi ljudi veruju da stavke ulaze u red od glave i izlaze na rep, način na koji hrana prolazi kroz zmiju. Redovi napisani na ovaj način pojavljuju se na mestima koji se mogu smatrati autorativnim, kao što je operativni sistem Linuks.

Elektronika uredi

FIFO se često koristi u elektronskim kolima za baferovanje i kontrolu toka između hardvera i softvera. U svojoj hardverskoj formi, FIFO se prvenstveno sastoji od skupa pokazivača za čitanje i pisanje, logike skladištenja i kontrole. Skladište može biti statična memorija slučajnog pristupa (SRAM - Static Random Access Memory), flip-flopovi, lečevi ili bilo koji drugi pogodan oblik skladišta. Za FIFO netrivijalne veličine, najčešće se koristi statični RAM sa dva ulaza, gde je jedan ulaz namenjen za pisanje, a drugi za čitanje.

Sinhroni FIFO je FIFO kod kojeg se isti takt koristi za pisanje i čitanje. Asinhroni FIFO koristi različite taktove za čitanje i pisanje. Asinhroni FIFO uvodi probleme sa metastabilnošću. Uobičajena implementacija asinhronog FIFO-a koristi Grejev kod za polazivače čitanja i pisanja kako bi se osiguralo pouzdano stvaranje flegova i nužno se koristi aritmetika pokazivača.

Primeri FIFO statusnih flegova su: pun, prazan, skoro pun, skoro prazan, itd.

Prva poznata implementacija FIFO-a u elektronici bila je od strane Pitera Alfkija 1969. godine u Ferčajld poluprovodnicima. Piter Alfki je kasnije postao direktor Zajlinksa.

Reference uredi

Literatura uredi

Izvori uredi