FIFO

Приказ FIFO методе, где је операција enqueue убацивање у ред, а dequeue избацивање из реда.

FIFO је акроним за "први уђе, први изађе" (енгл. first in, first out), а представља метод за организовање и манипулисања бафером података, при чему се најпре обрађује најстарији (први) унос или "глава" реда. Слично је обради реда (енг. FCFS - "first-come, first-served"), где први који дође, први буде услужен и људи напуштају ред у редоследу у ком долазе.

FCFS је такође жаргонски израз за FIFO алгоритам за распоређивање код оперативног система, који сваки процес даје централној процесорској јединици редом како је захтевано. Супротност за FIFO je LIFO (енг. last in, first out - "последњи уђе, први изађе") где се последњи унос или "врх стека" први обрађује. Ред са приоритетом није ни FIFO ни LIFO али може прихватити слично понашање привремено или подразумевано. Теорија чекања обухвата ове методе за обраду структура података, као и интеракције између стриктних FIFO редова.

Рачунарске науке

Структура података

У зависности од примене, FIFO се може имплементовати као хардверски померачки регистар, или као различите структуре меморије, обично као кружни бафер или као нека врста листе. Већина софтверских имплементација FIFO реда није сигурна за нити и захтева закључавање да би се осигурало да је ланац структуре података коришћен од стране само једне нити у неком тренутку.

Код

Следећи код приказује имплементацију FIFO повезане листе у C++ програмском језику.

#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;
    }
};

Глава или реп први

Крајеви FIFO реда често се називају главом и репом. Нажалост, постоји контроверза у вези са тим терминима:

• За многе људе, стакве треба да се уносе у ред од репа док не стигну до главе и одатле напуштају ред. Ова тачка гледишта оправдана је аналогно са редовима људи који чекају неку врсту услуживања и предњи и задњи дио реда паралелан је са главом и репом из овог примера.
• Други људи верују да ставке улазе у ред од главе и излазе на реп, начин на који храна пролази кроз змију. Редови написани на овај начин појављују се на местима који се могу сматрати ауторативним, као што је оперативни систем Линукс.

Електроника

FIFO се често користи у електронским колима за баферовање и контролу тока између хардвера и софтвера. У својој хардверској форми, FIFO се првенствено састоји од скупа показивача за читање и писање, логике складиштења и контроле. Складиште може бити статична меморија случајног приступа (SRAM - Static Random Access Memory), флип-флопови, лечеви или било који други погодан облик складишта. За FIFO нетривијалне величине, најчешће се користи статични РАМ са два улаза, где је један улаз намењен за писање, а други за читање.

Синхрони FIFO је FIFO код којег се исти такт користи за писање и читање. Асинхрони FIFO користи различите тактове за читање и писање. Асинхрони FIFO уводи проблеме са метастабилношћу. Уобичајена имплементација асинхроног FIFO-a користи Грејев код за полазиваче читања и писања како би се осигурало поуздано стварање флегова и нужно се користи аритметика показивача.

Примери FIFO статусних флегова су: пун, празан, скоро пун, скоро празан, итд.

Прва позната имплементација FIFO-а у електроници била је од стране Питера Алфкија 1969. године у Ферчајлд полупроводницима. Питер Алфки је касније постао директор Зајлинкса.

Литература

• Kruse, Robert L. (1987). Data structures and program design (2. изд.). Englewood Cliffs, N.J.: Prentice-Hall. ISBN 978-0-13-195884-5. OCLC 13823328. 

Извори

• Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparisons