Pāriet uz saturu

FIFO

Vikipēdijas lapa

FIFO (akronīms no first in, first out — 'pirmais iekšā, pirmais ārā') datorikā un rindu teorijā apzīmē datu organizācijas un manipulācijas metodi, kurā pirmais ievietotais ieraksts tiek apstrādāts kā pirmais. Metodes galvenais lietojums ir rindas datu struktūrā.

FIFO pretēja pieeja ir LIFO, kur pēdējais pievienotais elements tiek apstrādāts kā pirmais.

Tipiska FIFO datu struktūra C++ sintaksē:

struct fifo_node 
{
  struct fifo_node *next;
  value_type value;
};
 
class fifo
{
  fifo_node *front;
  fifo_node *back;
 
  fifo_node *dequeue(void)
  {
    fifo_node *tmp = front;
    if ( front != NULL )
      front = front->next;
    else
      back = NULL;
    return tmp;
  }
 
  queue(value)
  {
    fifo_node *tempNode = new fifo_node;
    tempNode->value = value;
    if ( front == NULL )
    {
      front = tempNode;
      back = tempNode;
    }
    else
    {
      back->next = tempNode;
      back = tempNode;
    }
  }
};

Bieži FIFO rinda tiek implementēta arī bez rādītājiemriņķveida buferis.

Vairumā Unix sistēmu ir pieejama definīcijas datne sys/queue.h, kas nodrošina standartizētu FIFO rindu izveidi.

Sākumu vai beigas vispirms

[labot šo sadaļu | labot pirmkodu]

Strīdīga ir jēdzienu sākums un beigas lietošana saistībā ar FIFO rindām. Liela daļa lietotāju saskata analoģiju ar cilvēku rindu, piem., veikalā, kur jauni cilvēki pievienojas rindas beigās, bet apkalpots tiek tas, kurš atrodas rindas sākumā. Citi uzskata, ka rinda ir līdzīga čūskai, kur jauni elementi tiek apēsti sākumā un apstrādāti beigās. Vairumā GNU/Linux operētājsistēmās rindas ir implementētas pēc čūskas analoģijas.

Datorsistēmās, kas atbalsta programmkanālus (angļu: pipes) komunikācijām starp procesiem, FIFO tiek lietots arī kā sinonīms nosauktajam programmkanālam.

Disku kontrolieri ienākošos lasīšanas/rakstīšanas pieprasījumus apstrādā pēc FIFO metodes. Tīklošanas ierīces (maršrutētājs, tīkla komutators, utt.) buferē un pārsūta ienākošās datu paketes pēc FIFO metodes. Metode tiek arī izmantota lai buferētu un regulētu datu plūsmu saskarnē starp elektroniskajām ierīcēm un programmnodrošinājumu. Aparatūras līmenī FIFO tiek implementēts kā lasīšanas/rakstīšanas rādītāji, datu glabāšanas atmiņa un loģikas kontrole. Elektronikā izšķir sinhrono un asinhrono FIFO implementāciju. Sinhronajā implementācijā gan lasīšanas, gan rakstīšanas operācijām tiek izmantots viens takts devējs. Asinhronā implementācijā tiek izmantoti dažādi takts devēji, un ir jāņem vērā no tā sekojošā sistēmas nestabilitāte (angļu: metastability).

  • LIFO last in, first out (pēdējais iekšā, pirmais ārā)
  • GIGO garbage in, garbage out (mēsli iekšā, mēsli ārā)