FIFO (računarstvo i elektronika)

S Wikipedije, slobodne enciklopedije
Jump to navigation Jump to search
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.
Wikitext.svg Ovom članku ili dijelu članka nedostaju interni linkovi.
Nakon dodavanja internih linkova uklonite ovaj šablon.
Spelling icon.svg Moguće je da ovaj članak ne poštuje standarde Wikipedije na bosanskom jeziku
kao što su upotreba afrikata, pravopis, pisanje riječi u skladu sa standardima, te način pisanja članaka.
Prikaz rada FIFO algoritma. Od 1. do 5. slike dolazak/redanje procesa, a od 6. do 10. obrada/odlazak procesa.

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[uredi | uredi izvor]

Strukture podataka[uredi | uredi izvor]

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

Kod[uredi | uredi izvor]

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 | uredi izvor]

FIFO raspored

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[uredi | uredi izvor]

  • LIFO (last in, first out)

Reference[uredi | uredi izvor]

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