FIFO

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt

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 pielietojums ir rindas datu struktūrā.

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

Datorika[izmainīt šo sadaļu | labot pirmkodu]

Datu struktūra[izmainīt šo sadaļu | labot pirmkodu]

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[izmainīt š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.

Programmkanāli[izmainīt šo sadaļu | labot pirmkodu]

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.

Elektronika[izmainīt šo sadaļu | labot pirmkodu]

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

Skatīt arī[izmainīt šo sadaļu | labot pirmkodu]

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