FIFO (výpočetní technika a elektronika) - FIFO (computing and electronics)

Zastoupení fronty FIFO

Ve výpočetní technice a v systémové teorii je FIFO ( zkratka pro první dovnitř, první ven ) metoda pro organizaci manipulace s datovou strukturou (často, konkrétně s datovou vyrovnávací pamětí ), kde je nejstarší (první) položka nebo „hlava“ fronta , je zpracován jako první.

Takové zpracování je analogické s obsluhou lidí v oblasti fronty na základě zásady „kdo dřív přijde, je dřív na řadě“ (FCFS), tj. Ve stejném pořadí, v jakém dorazí k ocasu fronty.

FCFS je také žargonový termín pro plánovací algoritmus operačního systému FIFO , který dává každému procesnímu procesoru (CPU) čas v pořadí, v jakém je požadován. Protikladem FIFO je LIFO , last-in-first-out, kde je nejprve zpracován nejmladší vstup nebo „vrchol zásobníku“. Prioritní fronta , ani FIFO nebo LIFO ale může přijmout podobné chování dočasně nebo ve výchozím nastavení. Teorie front zahrnuje tyto metody pro zpracování datových struktur , stejně jako interakce mezi frontami FIFO striktní.

Počítačová věda

Reprezentace fronty FIFO s operacemi zařazování a odkládání.

V závislosti na aplikaci může být FIFO implementován jako posuvný registr hardwaru nebo pomocí různých paměťových struktur, typicky kruhová vyrovnávací paměť nebo druh seznamu . Informace o abstraktní datové struktuře najdete v tématu Fronta (datová struktura) . Většina softwarových implementací fronty FIFO není bezpečná pro vlákna a vyžaduje blokovací mechanismus k ověření, že s řetězcem datové struktury manipuluje pouze jeden podproces.

Následující kód ukazuje propojený seznam implementace jazyka FIFO C ++ . V praxi existuje řada implementací seznamu, včetně populárních maker systému Unix C sys / queue.h nebo šablony standardní knihovny C ++ std :: list, takže není nutné implementovat datovou strukturu úplně od začátku. 

#include <memory>
#include <stdexcept>

using namespace std;

template <typename T>
class FIFO {
    struct Node {
        T value;
        shared_ptr<Node> next = nullptr;

        Node(T _value): value(_value) {}
    };

    shared_ptr<Node> front = nullptr;
    shared_ptr<Node> back  = nullptr;

public:
    void enqueue(T _value) {
        if (front == nullptr) {
            front = make_shared<Node>(_value);
            back = front;
        } else {
            back->next = make_shared<Node>(_value);
            back = back->next;
        }
    }

    T dequeue() {
        if (front == nullptr)
            throw underflow_error("Nothing to dequeue");

        T value = front->value;
        front = move(front->next);
        
        return value;
    }
};

Ve výpočetních prostředích, která podporují model potrubí a filtrů pro komunikaci mezi procesy , je FIFO jiný název pojmenovaného kanálu .

Řadiče disků mohou použít FIFO jako algoritmus plánování disku k určení pořadí, ve kterém mají být obsluhovány požadavky na vstupně-výstupní operace s diskem , kde je také známý stejným inicialismem FCFS jako u dříve zmíněného plánování CPU.

Mosty , přepínače a směrovače komunikační sítě používané v počítačových sítích používají FIFO k držení datových paketů na cestě k jejich dalšímu cíli. Typicky se na každé síťové připojení používá alespoň jedna struktura FIFO. Některá zařízení mají více FIFO pro současné a nezávislé řazení různých typů informací do fronty.

Elektronika

Plán FIFO

FIFO se běžně používají v elektronických obvodech pro vyrovnávací paměť a řízení toku mezi hardwarem a softwarem. Ve své hardwarové podobě FIFO primárně sestává ze souboru čtení a zápisu ukazatele , ukládání a řídicí logiky. Úložištěm může být statická paměť s náhodným přístupem (SRAM), klopné obvody , západky nebo jakákoli jiná vhodná forma úložiště. Pro FIFO jiné než triviální velikosti se obvykle používá SRAM se dvěma porty, kde jeden port je vyhrazen pro psaní a druhý pro čtení.

První známý FIFO implementovaný do elektroniky byl Peter Alfke v roce 1969 ve Fairchild Semiconductor . Alfke byl později ředitelem společnosti Xilinx .

Synchronicita

Synchronní FIFO je FIFO, kde se pro čtení i zápis používají stejné hodiny. Asynchronní FIFO používá pro čtení a zápis různé hodiny a mohou způsobit problémy s metastabilitou . Běžná implementace asynchronního FIFO používá Grayův kód (nebo jakýkoli kód vzdálenosti jednotky) pro ukazatele čtení a zápisu, aby se zajistilo spolehlivé generování příznaků. Jedna další poznámka týkající se generování příznaků je, že pro generování příznaků pro asynchronní implementace FIFO je nutné použít aritmetiku ukazatele. Naopak, k vygenerování příznaků v synchronních implementacích FIFO lze použít buď netěsný přístup kbelíku, nebo aritmetiku ukazatele.

Pro účely synchronizace se používá hardwarová FIFO. Často se implementuje jako kruhová fronta a má tedy dva ukazatele :

  • Číst ukazatel / číst registr adres
  • Registr ukazatele zápisu / zápisu adresy

Stavové příznaky

Mezi příklady stavových příznaků FIFO patří: plný, prázdný, téměř plný a téměř prázdný. FIFO je prázdný, když registr načtených adres dosáhne registru adres pro zápis. FIFO je plný, když se registr adresy zápisu dostane do registru adres čtení. Adresy pro čtení a zápis jsou zpočátku na prvním paměťovém místě a fronta FIFO je prázdná .

V obou případech jsou adresy pro čtení i zápis stejné. Chcete-li rozlišit mezi těmito dvěma situacemi, jednoduchým a robustním řešením je přidat jeden bit navíc pro každou adresu pro čtení a zápis, který je invertován pokaždé, když se adresa zalomí. S tímto nastavením jsou podmínky disambiguation:

Viz také

Reference

externí odkazy