17 / 24 · Konzept
FIFO: leer, voll und gleichzeitige Übertragungen
Trennen Sie Belegung und Zeiger und spezifizieren Sie Einfügen und Entnehmen an den Grenzen.
Lektionen sind frei lesbar. Schreibe dich ein, um deinen Fortschritt zu speichern.
Eine Warteschlange erhält die Übernahmereihenfolge
Ein FIFO gibt das älteste übernommene Element zuerst aus. Sein Lesezeiger kennzeichnet den ältesten Eintrag und sein Schreibzeiger den nächsten Speicherplatz. Gleiche Zeiger allein unterscheiden leer nicht von voll, deshalb führt dieser Entwurf einen Belegungszähler. Bei Tiefe vier benötigen Zeiger zwei Bits, der Zähler aber drei, um Null bis vier darzustellen. Speichern Sie Tags gemeinsam mit Daten.
Unser registrierter FIFO hat keinen Durchgriff bei leerer Warteschlange. Output-valid ist count>0 und pop ist output-valid AND output-ready. Input-ready ist count<depth OR pop und erlaubt Ersatz, wenn eine volle Warteschlange gleichzeitig ihr vorderstes Element ausgibt. Push ist input-valid AND input-ready. Der nächste count ist count+push-pop. Zwei getrennte Zuweisungen zum Erhöhen und Verringern von count können gleichzeitige Übertragungen falsch behandeln; verwenden Sie eine kombinierte Aktualisierung oder ausdrückliche Fälle.
| Alter count | Bedingungen | push | pop | Neuer count |
|---|---|---|---|---|
| 0 | Eingabe und bereiter Empfänger | 1 | 0 | 1 |
| 1 | Eingabe und bereiter Empfänger | 1 | 1 | 1 |
| 4 | Eingabe und wartender Empfänger | 0 | 0 | 4 |
| 4 | Eingabe und bereiter Empfänger | 1 | 1 | 4 |
Eine leere Warteschlange kann nicht allein wegen eines bereiten Empfängers entnehmen. Ihre neue Eingabe wird frühestens an der nächsten Flanke übertragen. Eine volle Warteschlange [A,B,C,D], die gleichzeitig A ausgibt und E übernimmt, wird [B,C,D,E] und bleibt voll. Prüfen Sie das Verhalten des zugrunde liegenden Speichers beim Lesen und Schreiben derselben physischen Position.
FIFO mit vier Einträgen. Anfangs leer, Lese- und Schreibzeiger stehen auf 0. pop wird angenommen, wenn sie nicht leer ist. push wird angenommen, wenn Platz frei ist oder an derselben Flanke ein pop angenommen wird.
Bei Tiefen als Zweierpotenz laufen die Zeigerbits natürlich um. Tiefe drei benötigt einen ausdrücklichen Übergang von Position zwei auf Null. Testen Sie Umlauf, Entfernen des letzten Elements und Ersatz bei voller Belegung getrennt.
Eine leere Warteschlange mit Tiefe vier nimmt während eines fünf Takte langen Empfängerhalts nur vier Elemente auf. Die fünfte Eingabe muss warten. Ein Sender, der nicht anhalten kann, benötigt mehr Kapazität oder eine definierte Verlustregel. Kein endlicher FIFO löst dauerhaft langsameren Verbrauch. Prüfen Sie 0≤count≤depth, accepted-delivered=count und Tag-Reihenfolge; Zähler allein erkennen keine Umordnung.
Selbst ausprobieren
Bei Tiefe zwei und Warteschlange [tag3,tag4] wird input tag5 mit out-ready=1 angeboten. Bestimmen Sie push, pop, nächsten count und nächste Warteschlange. Würde tag5 bei leerer Warteschlange sofort entnommen?
Erklärung lesen
Pop=1 setzt input-ready trotz voller Belegung auf hoch, also push=1. Der nächste count bleibt zwei und die Warteschlange ist [tag4,tag5]. Eine leere Warteschlange hat out-valid=0; tag5 wird daher gespeichert und kann erst an einer späteren Flanke entnommen werden.