FIFO (računarstvo i elektronika)

Ovo je stabilna verzija, pregledana dana 17 decembar 2024. 2 izmjene čekaju pregled.

FIFO (first in first out) red (ili samo red) je kolekcija koja se temelji na prvi ušao, prvi izašao politici. Ova politika često se 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 razumijevanje 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, a upravo time se bavi FIFO disciplina. Redovi su prirodni modeli za mnoge svakodnevne pojave, pa oni igraju središnju ulogu u brojnim aplikacijama.

Prikaz rada FIFO algoritma. Od 1. do 5. slike dolazak/redanje procesa, a od 6. do 10. obrada/odlazak procesa.

Kompjuterske nauke

uredi

Strukture podataka

uredi
 
Prezentacija FIFO (prvi ušao,prvi izašao) reda.

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). 

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

uredi
 
FIFO raspored

FIFO se najčešće koristi u elektronskim 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 uradio je Peter Alfke 1969. koji 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 najnoviji ulazak ili "vrh gomile".

Također pogledajte

uredi
  • LIFO (last in, first out)

Reference

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