FIFO (informática e eletrônica)

Representação de uma fila FIFO

Na computação e na teoria de sistemas, FIFO é um acrônimo para primeiro a entrar, primeiro a sair (o primeiro a entrar é o primeiro a sair), um método para organizar a manipulação de uma estrutura de dados (geralmente, especificamente um buffer de dados) onde a entrada mais antiga (primeira), ou "cabeça" da fila, é processado primeiro.

Esse processamento é análogo ao atendimento de pessoas em uma área de fila por ordem de chegada (FCFS), ou seja, na mesma sequência em que elas chegam ao final 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) o tempo na ordem em que é exigido. O oposto de FIFO é LIFO, último a entrar, primeiro a sair, onde a entrada mais nova ou "topo da pilha" é processado primeiro. Uma fila de prioridade não é FIFO nem LIFO, mas pode adotar um comportamento semelhante temporariamente ou por padrão. A teoria das filas abrange esses métodos para processar estruturas de dados, bem como interações entre filas FIFO estritas.

Ciência da computação

Representação de uma fila FIFO com operações enqueue e dequeue.

Dependendo da aplicação, um FIFO pode ser implementado como um registrador de deslocamento de hardware ou usando diferentes estruturas de memória, normalmente um buffer circular ou uma espécie 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 um thread por vez.

O código a seguir mostra uma implementação de linguagem FIFO C++ de lista encadeada. Na prática, existem várias implementações de lista, incluindo macros populares C sys/queue.h de sistemas Unix ou a biblioteca padrão C++ std::list template, evitando a necessidade de implementar a estrutura de dados do zero.

#include # #include # usando namespace O quê?;modelo <Nome do tipo T>classe FIFO ( Estranho Node ( T valor; Share_ptr<Node> Próximo = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Nullptr; Node(T _valor): valor(_valor) Não. } Share_ptr<Node> frente = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Nullptr; Share_ptr<Node> Voltar = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Nullptr;público: vazio enquete(T _valor) ( se (frente - Sim. Nullptr) ( frente = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = make_shared<Node>(_valor); Voltar = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = frente; ? mais ( Voltar- Sim.Próximo = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = make_shared<Node>(_valor); Voltar = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Voltar- Sim.Próximo; ? ? T De que forma?() ( se (frente - Sim. Nullptr) jogar subflow_error("Nada de dequele"); T valor = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = frente- Sim.valor; frente = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Mexam-se!(frente- Sim.Próximo);  retorno valor; ?}

Em ambientes de computação que suportam o modelo de pipes e filtros para comunicação entre processos, um FIFO é outro nome para um pipe nomeado.

Os controladores de disco podem usar o FIFO como um algoritmo de escalonamento de disco para determinar a ordem na qual atender às solicitações de E/S de disco, onde também é conhecido pelo mesmo inicialismo FCFS do escalonamento de CPU mencionado anteriormente.

Pontes, switches e roteadores de rede de comunicação 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 FIFOs múltiplos para enfileirar diferentes tipos de informações simultânea e independentemente.

Eletrônicos

Um calendário FIFO

FIFOs são comumente usados em circuitos eletrônicos para buffering 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 estática de acesso aleatório (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, onde uma porta é dedicada à escrita e a outra à leitura.

O primeiro FIFO conhecido implementado em eletrônica foi por Peter Alfke em 1969 na Fairchild Semiconductor. Alfke foi mais tarde diretor da Xilinx.

Sincronicidade

Um FIFO síncrono é um FIFO onde o mesmo relógio é usado para leitura e escrita. Um FIFO assíncrono usa relógios diferentes para leitura e gravação e pode apresentar 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 sobre a geração de sinalizadores é que deve-se 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 com vazamento ou aritmética de ponteiro para gerar sinalizadores em implementações FIFO síncronas.

Um FIFO de hardware é usado para fins de sincronização. Geralmente é implementado como uma fila circular e, portanto, possui dois ponteiros:

• Ler ponteiro / ler registro de endereço
• Escrever ponteiro / escrever registro de endereço

Sinalizadores de status

Exemplos de sinalizadores de status FIFO incluem: cheio, vazio, quase cheio e quase vazio. Um FIFO está vazio quando o registrador de endereço de leitura alcança o registrador de endereço de escrita. Um FIFO está cheio quando o registrador de endereço de escrita alcança o registrador de endereço de leitura. Os endereços de leitura e gravação estão inicialmente no primeiro local de memória e a fila FIFO está vazia.

Em ambos os casos, os endereços de leitura e escrita 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 registro de endereço de leitura é igual ao registro de endereço de gravação, o FIFO está vazio.
• Quando os registros de endereços de leitura e gravação diferem apenas no bit extra mais significativo e o resto é igual, o FIFO está cheio.