FIFO

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa
Mergefrom 2.svg
O artigo ou secção FIFO (escalonamento) deverá ser fundido aqui. (desde fevereiro de 2019)
Se discorda, discuta esta fusão aqui.
Disambig grey.svg Nota: Se procura o sistema de escalonamento, veja FIFO (escalonamento).
Exemplo de execução de um código FIFO com as operações enqueue (enfileirar) e dequeue (desenfileirar).

Em Ciência da Computação, FIFO (acrônimo para First In, First Out, que em português significa primeiro a entrar, primeiro a sair) refere-se a estruturas de dados do tipo fila.

FCFS (First-Come, First-Served), que significa "o primeiro a entrar é o primeiro a ser servido" é também um jargão para o algoritmo FIFO de agendamento de tarefas do sistema operacional, que dá a cada processo tempo de CPU na ordem em que as demandas são feitas. O oposto de FIFO é LIFO (Last-In, First-Out), que significa "o último a entrar é o primeiro a sair", aonde a entrada mais recente, ou o topo da pilha de processos, é processado primeiro.[1] Já uma fila prioritária não é nem FIFO, nem LIFO, mas pode adotar comportamento similar temporariamente, ou mesmo por padrão.

As listas são amplamente utilizadas em programação para implementar filas de espera. Em uma fila de tipo FIFO os elementos vão sendo colocados na fila e retirados (ou processados) por ordem de chegada. A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

Aplicações[editar | editar código-fonte]

Os algoritmos FIFO's são comumente usados em circuitos eletrônicos de buffer e controle de fluxo, que vai desde o hardware até o software. Na forma de um hardware o FIFO consiste basicamente de um conjunto de ler e escrever ponteiros, armazenamento e lógica de controle. Armazenamento pode ser SRAM, flip-flops, fechos ou qualquer outra forma adequada de armazenamento. Para o FIFO, de tamanho não-trivial, uma SRAM de porta dupla geralmente é utilizada quando uma porta é usada para a escrita e a outra para leitura.

O FIFO síncrono aonde o mesmo clock é usado para leitura e escrita. Um FIFO assíncrono utiliza diferentes relógios para leitura e escrita.Uma aplicação comum de um FIFO assíncrono utiliza um código de Gray (código binário refletido),ou qualquer unidade de código a distância, para a ler e escrever os ponteiros para garantir a geração de bandeira confiável.Uma nota mais preocupante é que se deve necessariamente usar a aritmética de ponteiro para gerar bandeiras para implementações assíncronas FIFO. Por outro lado, pode-se usar a abordagem de um balde "de fuga" ou a aritmética de ponteiro para gerar bandeiras nas implementações síncronas FIFO.

Outras estruturas algébricas usadas em Engenharia da Computação[editar | editar código-fonte]

Ver também[editar | editar código-fonte]

Referências

  1. Kruse, Robert L. (1987) [1984]. Data Structures & Program Design (second edition) second (hc) textbook ed. Englewood Cliffs, New Jersey 07632: Prentice-Hall, Inc. div. of Simon & Schuster. 150 páginas. ISBN 0-13-195884-4. The definition of a finite sequence immediately makes it possible for us to attempt a definition of a list: A 'list' of terms of type T is simply a finite sequence of elements of the set T. ... The only difference among stacks and queues and more general lists is the operations by which changes or accesses can be made to the list. 

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.