17 / 24 · Concetto
FIFO vuota, piena e trasferimenti simultanei
Separa l'occupazione dai puntatori e specifica il comportamento di inserimento e rimozione ai limiti.
Le lezioni sono gratuite. Iscriviti per salvare i progressi.
Una coda conserva l'ordine di accettazione
Una FIFO consegna per primo l'elemento accettato più vecchio. Il puntatore di lettura identifica l'elemento più vecchio e quello di scrittura la successiva posizione di memorizzazione. La sola uguaglianza dei puntatori non distingue vuoto da pieno, quindi questo progetto mantiene un conteggio di occupazione. Con profondità quattro, i puntatori richiedono due bit, ma il conteggio ne richiede tre per rappresentare da zero a quattro. Memorizza i tag insieme ai dati.
La nostra FIFO registrata non ha passaggio diretto attraverso una coda vuota. Output-valid è count>0 e pop è output-valid AND output-ready. Input-ready è count<depth OR pop, consentendo la sostituzione quando una coda piena consegna contemporaneamente il proprio primo elemento. Push è input-valid AND input-ready. Il conteggio successivo è count+push-pop. Due assegnazioni separate che incrementano e decrementano count possono gestire male i trasferimenti simultanei; usa un aggiornamento combinato o casi espliciti.
| count precedente | Condizioni | push | pop | count nuovo |
|---|---|---|---|---|
| 0 | Ingresso e destinazione pronta | 1 | 0 | 1 |
| 1 | Ingresso e destinazione pronta | 1 | 1 | 1 |
| 4 | Ingresso e destinazione in stallo | 0 | 0 | 4 |
| 4 | Ingresso e destinazione pronta | 1 | 1 | 4 |
Una coda vuota non può rimuovere un elemento soltanto perché la destinazione è pronta. Il nuovo ingresso viene trasferito per la prima volta al fronte successivo. Una coda piena [A,B,C,D] che consuma A e accetta E contemporaneamente diventa [B,C,D,E], ancora piena. Verifica il comportamento della memoria sottostante quando leggi e scrivi la stessa posizione fisica.
FIFO a quattro elementi. Inizialmente vuota, con puntatori di lettura e scrittura a 0. Accetta pop se non è vuota. Accetta push se c’è spazio o se viene accettato un pop sullo stesso fronte.
Le profondità pari a una potenza di due riportano naturalmente i puntatori all'inizio tramite i loro bit. La profondità tre richiede una transizione esplicita dalla posizione due a zero. Prova separatamente il ritorno all'inizio, la rimozione dell'ultimo elemento e la sostituzione a coda piena.
Una coda vuota con profondità quattro assorbe soltanto quattro elementi durante uno stallo della destinazione di cinque cicli. Il quinto ingresso deve attendere. Una sorgente che non può fermarsi richiede più capacità oppure una politica di perdita definita. Nessuna FIFO finita risolve un consumo permanentemente più lento. Verifica 0≤count≤depth, accepted-delivered=count e l'ordine dei tag; i soli conteggi non rilevano il riordinamento.
Prova tu
Con profondità due e coda [tag3,tag4], viene offerto l'ingresso tag5 con out-ready=1. Trova push, pop, il conteggio successivo e la coda successiva. Tag5 verrebbe rimosso immediatamente se la coda fosse vuota?
Leggi la spiegazione
Pop=1 rende input-ready alto nonostante l'occupazione piena, quindi push=1. Il conteggio successivo rimane due e la coda è [tag4,tag5]. Una coda vuota ha out-valid=0, quindi tag5 viene memorizzato e non può essere rimosso prima di un fronte successivo.