FIFO (informatyka i elektronika)

Reprezentacja kolejki FIFO

W informatyce i teorii systemów FIFO to skrót od first in, first out (first in is first out), metoda organizowania manipulacji strukturą danych (często w szczególności buforem danych ) , w której najstarszy (pierwszy ) wpis lub „nagłówek” kolejki jest przetwarzany jako pierwszy.

Takie przetwarzanie jest analogiczne do obsługiwania ludzi w obszarze kolejki na zasadzie kto pierwszy, ten lepszy (FCFS), tj. w tej samej kolejności, w jakiej przybywają na koniec kolejki.

FCFS to także żargonowe określenie algorytmu planowania systemu operacyjnego FIFO , który przydziela czas każdej jednostce centralnej (CPU) procesu w kolejności, w jakiej jest on wymagany. Przeciwieństwem FIFO jest LIFO , last-in-first-out, gdzie najmłodszy wpis lub „wierzchołek stosu” jest przetwarzany jako pierwszy. Kolejka priorytetowa nie jest ani FIFO, ani LIFO, ale może zachowywać się podobnie tymczasowo lub domyślnie. Teoria kolejek obejmuje te metody przetwarzania struktur danych , a także interakcje między kolejkami ścisłego FIFO.

Informatyka

Reprezentacja kolejki FIFO z operacjami enqueue i dequeue.

W zależności od aplikacji, FIFO może być zaimplementowane jako sprzętowy rejestr przesuwny lub przy użyciu różnych struktur pamięci, zazwyczaj bufora cyklicznego lub rodzaju listy . Aby uzyskać informacje na temat abstrakcyjnej struktury danych, zobacz Kolejka (struktura danych) . Większość implementacji oprogramowania kolejki FIFO nie jest zabezpieczona wątkowo i wymaga mechanizmu blokującego w celu sprawdzenia, czy łańcuch struktury danych jest manipulowany tylko przez jeden wątek na raz.

Poniższy kod przedstawia połączoną listę implementacji języka FIFO C++ . W praktyce istnieje wiele implementacji list, w tym makra C sys/queue.h w popularnych systemach uniksowych lub biblioteki standardowej C++ std::list, co pozwala uniknąć konieczności implementowania struktury danych od zera. 

 
 

  

  
  
      
         
           

           
    

       
        


       
            
              
              
          
              
              
        
    

      
           
             

           
          
        
         
    
 #include  <pamięć>  #include  <stdexcept>  using  namespace  std  ;  szablon  <  nazwa typu  T  >  klasa  FIFO  {  struct  Node  {  wartość  T  ;  shared_ptr  <  Węzeł  >  następny  =  nullptr  ;  Węzeł  (  T  _wartość  )  :  wartość  (  _wartość  )  {}  };  shared_ptr  <  Węzeł  >  front  =  nullptr  ;  shared_ptr  <  Węzeł  >  wstecz  =  nullptr  ;  public  :  void  enqueue  (  T  _value  )  {  if  (  front  ==  nullptr  )  {  front  =  make_shared  <Node>  (  _value  )  ;  _  tył  =  przód  ;  }  else  {  wstecz  ->  następny  =  make_shared  <  węzeł  >  (  _wartość  );  wstecz  =  wstecz  ->  dalej  ;  }  }  T  dequeue  ()  {  if  (  front  ==  nullptr  )  throw  underflow_error  (  "Nic do usunięcia z kolejki"  );  wartość  T  =  przód  ->  wartość  ;  przód  =  ruch  (  przód  ->  następny  );  zwracana  wartość  ;  }  };

W środowiskach komputerowych obsługujących model potoków i filtrów do komunikacji międzyprocesowej FIFO to inna nazwa nazwanego potoku .

Kontrolery dysków mogą używać FIFO jako algorytmu planowania dysku w celu określenia kolejności obsługi żądań we/wy dysku , przy czym jest to również znane z tego samego inicjalizacji FCFS, jak w przypadku planowania procesora wspomnianego wcześniej.

Mosty sieci komunikacyjnych , przełączniki i routery używane w sieciach komputerowych wykorzystują FIFO do przechowywania pakietów danych w drodze do ich następnego miejsca docelowego. Zwykle na połączenie sieciowe jest używana co najmniej jedna struktura FIFO. Niektóre urządzenia są wyposażone w wiele FIFO do jednoczesnego i niezależnego kolejkowania różnych typów informacji.

Elektronika

Harmonogram FIFO

FIFO są powszechnie stosowane w obwodach elektronicznych do buforowania i sterowania przepływem między sprzętem a oprogramowaniem. W swojej formie sprzętowej FIFO składa się głównie z zestawu wskaźników do odczytu i zapisu , logiki przechowywania i sterowania. Przechowywanie może być statyczną pamięcią o dostępie swobodnym (SRAM), przerzutnikami , zatrzaskami lub dowolną inną odpowiednią formą przechowywania. W przypadku FIFO o nietrywialnym rozmiarze zwykle używana jest dwuportowa pamięć SRAM, w której jeden port jest przeznaczony do zapisu, a drugi do odczytu.

Pierwszy znany FIFO wdrożony w elektronice został przez Petera Alfke w 1969 roku w Fairchild Semiconductor . Alfke był później dyrektorem w firmie Xilinx .

Synchroniczność

Synchroniczne FIFO to FIFO, w którym ten sam zegar jest używany zarówno do odczytu, jak i zapisu. Asynchroniczne FIFO używa różnych zegarów do odczytu i zapisu, co może powodować z metastabilnością . Powszechna implementacja asynchronicznego FIFO wykorzystuje kod Graya (lub dowolny kod jednostki odległości) dla wskaźników odczytu i zapisu, aby zapewnić niezawodne generowanie flagi. Kolejna uwaga dotycząca generowania flag jest taka, że ​​do generowania flag dla asynchronicznych implementacji FIFO należy koniecznie użyć arytmetyki wskaźników. I odwrotnie, do generowania flag w synchronicznych implementacjach FIFO można użyć nieszczelnego wiadra lub arytmetyki wskaźników.

Do celów synchronizacji używany jest sprzętowy FIFO. Często jest implementowana jako cykliczna kolejka i dlatego ma dwa wskaźniki :

  • Odczyt wskaźnika/odczyt rejestru adresowego
  • Zapisz wskaźnik / zarejestruj adres zapisu

Flagi stanu

Przykłady flag stanu FIFO to: pełna, pusta, prawie pełna i prawie pusta. FIFO jest puste, gdy odczytany rejestr adresowy osiągnie rejestr adresowy zapisu. FIFO jest pełne, gdy rejestr adresu zapisu osiągnie rejestr adresu odczytu. Adresy odczytu i zapisu początkowo znajdują się w pierwszej lokacji pamięci, a kolejka FIFO jest pusta .

W obu przypadkach adresy odczytu i zapisu są równe. Aby rozróżnić te dwie sytuacje, prostym i niezawodnym rozwiązaniem jest dodanie jednego dodatkowego bitu dla każdego adresu odczytu i zapisu, który jest odwracany za każdym razem, gdy adres się zawija. Przy takim ustawieniu warunki ujednoznaczniające są następujące:

  • Gdy odczytany rejestr adresowy jest równy rejestrowi adresowemu zapisu, FIFO jest puste.
  • Gdy rejestry adresów odczytu i zapisu różnią się tylko dodatkowym najbardziej znaczącym bitem, a pozostałe są równe, FIFO jest pełne.

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=FIFO_(computing_and_electronics)&oldid=1104188471 ”