FIFO

 Nota: Se procura o sistema de escalonamento, veja FIFO (escalonamento).

Em engenharia 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. Tem uma estrutura diferente da estrutura de uma LIFO (que significa Last In, First Out, as pilhas).

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 idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

Como exemplo de aplicação para filas, pode-se citar a fila de processos de um sistema operacional. Nela, é estabelecido um tempo t a ser usado por cada um dos processos. Se durante a execução de um processo o tempo passa de 0 a t, este é posto na fila e o processo seguinte é executado. Se o processo seguinte não terminar de ser executado no tempo t, ele é posto na fila e o processo subsequente é executado, e assim por diante até todos os processo serem executados.

Em termos de controle de estoque, refere-se a um método de armazenamento onde os itens são consumidos por ordem de chegada.

Inserção e remoção

A inserção é o método que insere um elemento no fim de uma fila. Já a remoção é o método que remove um elemento do início de uma fila.

Em programação estruturada temos:

/** Protótipo Na Linguagem C 
 *  Para uma Fila de elementos inteiros 
 */
void inserir(int * Fila, int elemento) {
    if (amo < MAX) {
        Fila[amo] = elemento;
        amo++;
    }
}//end inserir
//------------------------------------------------
int remover(int * Fila) {
    int i;
    for (i = 0; i < amo - 2; i++) {
       Fila[i] = Fila[i+1];
    }
    amo--;
}
//end remover
//------------------------------------------------
Onde amo (amount), trata-se de uma variável global que armazena a quantidade de elementos existentes na lista.

Em programação orientada a objeto temos um objeto Fila, e:

/** Implementação do método na Linguagem Java
 *  Para uma Fila usando referência ( com nodos ( nós ) )
 */
public void insereNaFila(Nodo p) {
     if(this.isEmpty()){
        this.inicio = p;
        this.fim = p;
    }
    else{
        fim.setProximo(p);
        this.fim = p;
    }
}
 
public void removeDaFila(){
     if(this.inicio != null){
        this.inicio = inicio.getProximo();
     }
}
 
public boolean isEmpty() {
     return this.getInicio() == null;
}

Cabeça ou a cauda primeiro

Há controvérsias sobre os termos "cabeça" e "cauda" existente em referência às filas FIFO. Para muitas pessoas, os itens deverão entrar numa fila na cauda, permanecem nela até chegar á cabeça e deixam a fila de lá. Este ponto de vista se justifica, por analogia, com filas de pessoas esperando por algum tipo de serviço em paralelos a utilização de "front" e "back" no exemplo acima. Outras pessoas acreditam que os objetos entram numa fila na cabeça e deixam na cauda, na forma de alimentos passando por uma cobra. Filas escritas desta maneira aparecem em lugares que possam ser consideradas autoritárias, como o sistema operacional GNU / Linux.

Escalonamento de Disco

Os Controladores de disco usam também o FIFO como um algoritmo de escalonamento para determinar a ordem de serviço de solicitações de E/S .

Comunicações e redes

Pontes de comunicação, switches e roteadores usados em redes de computadores usam FIFO's para manter os pacotes de dados em rota para seu próximo destino. Normalmente, uma estrutura FIFO é utilizada por conexões de rede. Alguns dispositivos possuem vários destes algoritmos simultaneamente e independentemente de filas de diferentes tipos de informações.

Aplicações

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.

Exemplos de sinalizadores de status FIFO incluem: cheios, vazios, quase cheio, quase vazio, etc.

Outras estruturas algébricas usadas em Engenharia da Computação

• LIFO
• Autómato
• Árvore (estrutura de dados)
• Árvore B
• Grafo

Ver também

• Lista de termos referentes ao tema

Ligações externas

http://www.ime.usp.br/~pf/algoritmos/aulas/fila.html