17 / 24 · Concept

FIFO vide, pleine et transferts simultanés

Distinguez l’occupation des pointeurs et définissez les insertions/retraits aux limites.

Une file conserve l’ordre d’acceptation

Une FIFO livre d’abord l’élément accepté le plus ancien. Son pointeur de lecture identifie l’entrée la plus ancienne et son pointeur d’écriture le prochain emplacement de stockage. Des pointeurs égaux ne distinguent pas à eux seuls vide et plein : cette conception conserve donc un compteur d’occupation. Pour une profondeur quatre, les pointeurs nécessitent deux bits mais le compteur en nécessite trois pour représenter zéro à quatre. Stockez les étiquettes avec les données.

Notre FIFO enregistrée ne laisse pas passer directement les données d’une file vide. Output-valid vaut count>0 et pop vaut output-valid ET output-ready. Input-ready vaut count<depth OU pop, permettant le remplacement lorsqu’une file pleine livre simultanément sa tête. Push vaut input-valid ET input-ready. Le prochain count vaut count+push-pop. Deux affectations séparées incrémentant et décrémentant count peuvent mal gérer les transferts simultanés ; utilisez une mise à jour combinée ou des cas explicites.

Ancien count	Conditions	push	pop	Nouveau count
0	Entrée et récepteur prêt	1	0	1
1	Entrée et récepteur prêt	1	1	1
4	Entrée et récepteur bloqué	0	0	4
4	Entrée et récepteur prêt	1	1	4

Une file vide ne peut pas retirer un élément simplement parce que le récepteur est prêt. Sa nouvelle entrée est transférée au plus tôt au front suivant. Une file pleine [A, B, C, D] consommant A et acceptant E simultanément devient [B, C, D, E], toujours pleine. Vérifiez le comportement de la mémoire sous-jacente lors d’une lecture et d’une écriture à la même position physique.

Observer l’occupation, l’insertion et le retrait

FIFO à quatre cases. Initialement vide ; pointeurs de lecture et d'écriture à 0. Accepter pop si le FIFO n'est pas vide. Accepter push s'il reste une place ou si un pop est accepté sur le même front.

Les profondeurs en puissances de deux rebouclent naturellement avec les bits des pointeurs. Une profondeur trois exige une transition explicite de la position deux à zéro. Testez séparément le rebouclage, le retrait du dernier élément et le remplacement à pleine capacité.

Une file vide de profondeur quatre n’absorbe que quatre éléments pendant un blocage du récepteur de cinq cycles. La cinquième entrée doit attendre. Une source ne pouvant pas se bloquer nécessite davantage de capacité ou une politique de perte définie. Aucune FIFO finie ne corrige une consommation durablement plus lente. Vérifiez 0≤count≤depth, accepted-delivered=count et l’ordre des étiquettes ; les compteurs seuls ne révèlent pas un réordonnancement.

Essayez vous-même

Pour une profondeur deux et la file [tag3, tag4], l’entrée tag5 est proposée avec out-ready=1. Trouvez push, pop, le prochain count et la prochaine file. Tag5 serait-il retiré immédiatement si la file était vide ?

Lire l’explication

Pop=1 rend input-ready haut malgré l’occupation pleine : push=1. Le prochain count reste deux et la file devient [tag4, tag5]. Une file vide a out-valid=0 : tag5 est donc stocké et ne peut être retiré qu’à un front ultérieur.