FIFO (računarstvo i elektronika)

FIFO (first in first out) red (ili samo red) je kolekcija koja se temelji na prvi ušao, prvi izašao politici. Ova politika se često susreće u svakodnevnom životu: od ljudi koji čekaju u redu u pozorištu, automobila koji čekaju u redu na naplatnoj rampi, zadataka koji čekaju da se ispune do aplikacija na računaru. Jedan temelj ove politike usluga je percepcija pravičnosti. Prva ideja koja dolazi na pamet kada većina ljudi misli o pravednosti je da onaj ko čeka najduže treba prvo biti uslužen. To je upravo FIFO disciplina. Redovi su prirodni modeli za mnoge svakodnevne pojave pa oni igraju centralnu ulogu u brojnim aplikacijama.

Kompjuterske nauke

Strukture podataka

Ovisno o aplikaciji, FIFO se može implementirati kao hardverska smjena registra, ili koristeći različite memorijske strukture, obično kružnog buffer-a ili neke vrste liste. Operativni sistem može koristiti FIFO kao algoritam za određivanje reda I / O (ulazno/izlaznih) zahtjeva. Također FIFO se koristi i u mrežnim vezama (network connection).

Kod

Sljedeći kod je implementacija FIFO algoritma u 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;
    }
};

Elektronika

FIFO se najčešće koristi u elektroničkim sklopovima za buffering i kontrolu protoka između hardvera i softvera. U svom hardverskom obliku, FIFO se prvenstveno sastoji od niza za čitanje i pisanje pokazivača, skladištenja i kontrole logike. Skladištenja može biti statična memorija sa slučajnim pristupom (SRAM), flip-flops ili bilo koji drugi oblik pogodan za skladištenje. Za FIFO ne-trivijalne veličine, obično se koristi dual-port SRAM , gdje jedan port služi za pisanje a drugi za čitanje. Sinhroni FIFO je FIFO gdje se koristi isti takt i za čitanje i pisanje. Asinhroni FIFO koristi različite taktove za čitanje i pisanje. Prvu poznatu FIFO implementaciju u elektronici je uradio Peter Alfke 1969. godine. Peter Alfke je kasnije bio jedan od direktora u Xilinxu.

Suprotno od FIFO je LIFO, ( Last In, First Out ) što znači posljednji ušao, prvi izašao, gdje se prvo obrađuje najmlađi ulazak ili "vrh gomile".

Također pogledajte

LIFO (last in, first out)

Reference

N.Husović, E.Brka, S.Ribić: Operativni sistemi, Sarajevo, februar 2015. godine
Robert Sedgewick i Kevin Wayne: Algorithms, Princeton University
Stacks and its Applications