17 / 24 · Conceito

FIFO vazia, cheia e transferências simultâneas

Separe a ocupação dos ponteiros e especifique o comportamento de push/pop nos limites.

Uma fila preserva a ordem de aceitação

Uma FIFO entrega primeiro o item aceito há mais tempo. Seu ponteiro de leitura identifica a entrada mais antiga e seu ponteiro de escrita, a próxima posição de armazenamento. Ponteiros iguais, por si só, não distinguem vazio de cheio, portanto este projeto mantém uma contagem de ocupação. Para profundidade quatro, os ponteiros precisam de dois bits, mas a contagem precisa de três para representar de zero a quatro. Armazene as etiquetas junto com os dados.

Nossa FIFO registrada não permite passagem direta através da fila vazia. Output-valid é count>0 e pop é output-valid AND output-ready. Input-ready é count<depth OR pop, permitindo substituição quando uma fila cheia entrega simultaneamente seu primeiro item. Push é input-valid AND input-ready. O próximo count é count+push-pop. Duas atribuições separadas que incrementam e decrementam count podem tratar incorretamente transferências simultâneas; use uma atualização combinada ou casos explícitos.

count anterior	Condições	push	pop	count novo
0	Entrada e destino pronto	1	0	1
1	Entrada e destino pronto	1	1	1
4	Entrada e destino em pausa	0	0	4
4	Entrada e destino pronto	1	1	4

Uma fila vazia não pode fazer pop apenas porque o destino está pronto. Sua nova entrada é transferida pela primeira vez na borda seguinte. Uma fila cheia [A,B,C,D] que consome A e aceita E simultaneamente torna-se [B,C,D,E], ainda cheia. Verifique o comportamento da memória subjacente ao ler e escrever na mesma posição física.

Observe a ocupação, a inserção e a remoção da fila

FIFO de quatro posições, inicialmente vazia e com os ponteiros de leitura e escrita em 0. Aceita pop se não estiver vazia. Aceita push se houver espaço ou se um pop for aceito na mesma borda.

Profundidades de potência de dois retornam naturalmente ao início pelos bits dos ponteiros. Profundidade três exige uma transição explícita da posição dois para zero. Teste separadamente o retorno ao início, a remoção do último item e a substituição com a fila cheia.

Uma fila vazia de profundidade quatro absorve apenas quatro itens durante uma pausa de cinco ciclos do destino. A quinta entrada deve esperar. Uma fonte que não pode pausar precisa de mais capacidade ou de uma política definida de perda. Nenhuma FIFO finita resolve um consumo permanentemente mais lento. Verifique 0≤count≤depth, accepted-delivered=count e a ordem das etiquetas; contagens sozinhas não revelam reordenação.

Experimente

Para profundidade dois e fila [tag3,tag4], a entrada tag5 é oferecida com out-ready=1. Encontre push, pop, o próximo count e a próxima fila. Tag5 faria pop imediatamente se a fila estivesse vazia?

Ler a explicação

Pop=1 torna input-ready alto apesar da ocupação cheia, portanto push=1. O próximo count permanece dois e a fila é [tag4,tag5]. Uma fila vazia tem out-valid=0, portanto tag5 é armazenada e não pode fazer pop até uma borda posterior.