FIFO (computação e eletrônica) - FIFO (computing and electronics)
Na computação e na teoria dos sistemas , FIFO (um acrônimo para first in, first out ) é um método para organizar a manipulação de uma estrutura de dados (muitas vezes, especificamente um buffer de dados ), onde a entrada mais antiga (primeira), ou "cabeça" de a fila é processada primeiro.
Esse processamento é análogo a atender pessoas em uma área de fila por ordem de chegada (FCFS), ou seja, na mesma sequência em que chegam na cauda da fila.
FCFS também é o jargão para o algoritmo de escalonamento do sistema operacional FIFO , que dá a cada unidade de processamento central (CPU) de processo o tempo na ordem em que é solicitado. O oposto do FIFO é LIFO , last-in-first-out, onde a entrada mais jovem ou "topo da pilha" é processada primeiro. Uma fila de prioridade não é FIFO ou LIFO, mas pode adotar um comportamento semelhante temporariamente ou por padrão. A teoria das filas engloba esses métodos de processamento de estruturas de dados , bem como as interações entre filas FIFO estritas.
Ciência da Computação
Dependendo do aplicativo, um FIFO pode ser implementado como um registrador de deslocamento de hardware ou usando diferentes estruturas de memória, normalmente um buffer circular ou um tipo de lista . Para obter informações sobre a estrutura de dados abstrata, consulte Fila (estrutura de dados) . A maioria das implementações de software de uma fila FIFO não são thread-safe e requerem um mecanismo de bloqueio para verificar se a cadeia de estrutura de dados está sendo manipulada por apenas uma thread por vez.
O código a seguir mostra uma implementação de linguagem FIFO C ++ de lista vinculada . Na prática, existem várias implementações de lista, incluindo macros C sys / queue.h de sistemas Unix populares ou o modelo std :: list da biblioteca padrão C ++ , evitando a necessidade de implementar a estrutura de dados do zero.
#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;
}
};
Em ambientes de computação que suportam o modelo de canais e filtros para comunicação entre processos , um FIFO é outro nome para um canal nomeado .
Os controladores de disco podem usar o FIFO como um algoritmo de escalonamento de disco para determinar a ordem em que atender às solicitações de E / S de disco , onde também é conhecido pelo mesmo inicialismo FCFS do escalonamento de CPU mencionado antes.
Pontes de rede de comunicação , switches e roteadores usados em redes de computadores usam FIFOs para manter pacotes de dados em rota para seu próximo destino. Normalmente, pelo menos uma estrutura FIFO é usada por conexão de rede. Alguns dispositivos apresentam vários FIFOs para enfileirar diferentes tipos de informações de forma simultânea e independente.
Eletrônicos
FIFOs são comumente usados em circuitos eletrônicos para buffer e controle de fluxo entre hardware e software. Em sua forma de hardware, um FIFO consiste principalmente em um conjunto de ponteiros de leitura e gravação , armazenamento e lógica de controle. O armazenamento pode ser memória de acesso aleatório estática (SRAM), flip-flops , travas ou qualquer outra forma adequada de armazenamento. Para FIFOs de tamanho não trivial, geralmente é usada uma SRAM de porta dupla, em que uma porta é dedicada à gravação e a outra à leitura.
O primeiro FIFO conhecido implementado em eletrônica foi por Peter Alfke em 1969 na Fairchild Semiconductor . Alfke mais tarde foi diretor da Xilinx .
Sincronicidade
Um FIFO síncrono é um FIFO em que o mesmo relógio é usado para leitura e gravação. Um FIFO assíncrono usa relógios diferentes para leitura e gravação e podem introduzir problemas de metaestabilidade . Uma implementação comum de um FIFO assíncrono usa um código Gray (ou qualquer código de distância de unidade) para os ponteiros de leitura e gravação para garantir a geração confiável de sinalizadores. Uma observação adicional a respeito da geração de sinalizadores é que se deve necessariamente usar aritmética de ponteiro para gerar sinalizadores para implementações FIFO assíncronas. Por outro lado, pode-se usar uma abordagem de balde furado ou aritmética de ponteiro para gerar sinalizadores em implementações FIFO síncronas.
Um hardware FIFO é usado para fins de sincronização. Muitas vezes, é implementado como uma fila circular e, portanto, tem dois indicadores :
- Ponteiro de leitura / registro de endereço de leitura
- Ponteiro de gravação / registro de endereço de gravação
Sinalizadores de status
Exemplos de sinalizadores de status FIFO incluem: cheio, vazio, quase cheio e quase vazio. Um FIFO está vazio quando o registro de endereço de leitura atinge o registro de endereço de gravação. Um FIFO está cheio quando o registrador de endereço de gravação atinge o registrador de endereço de leitura. Os endereços de leitura e gravação estão inicialmente no primeiro local da memória e a fila FIFO está vazia .
Em ambos os casos, os endereços de leitura e gravação acabam sendo iguais. Para distinguir entre as duas situações, uma solução simples e robusta é adicionar um bit extra para cada endereço de leitura e gravação que é invertido cada vez que o endereço é quebrado. Com esta configuração, as condições de desambiguação são:
- Quando o registrador de endereço de leitura é igual ao registrador de endereço de gravação, o FIFO está vazio.
- Quando o bit menos significativo (LSB) do endereço de leitura é igual aos LSBs do endereço de gravação e o bit mais significativo extra é diferente, o FIFO está cheio.