17 / 24 · Теория
Пустая и полная FIFO и одновременные передачи
Отделяйте заполненность от указателей и задавайте добавление/извлечение на границах.
Уроки доступны бесплатно. Запишитесь, чтобы сохранять прогресс.
Очередь сохраняет порядок приёма
FIFO первой выдаёт самый старый принятый элемент. Указатель чтения определяет старейшую запись, указатель записи — следующее место хранения. Одно равенство указателей не различает пустоту и заполненность, поэтому этот вариант хранит счётчик заполненности. Для глубины четыре указателям нужны два бита, а count — три, чтобы представить от нуля до четырёх. Храните метки вместе с данными.
Наша регистровая FIFO не имеет сквозного прохода пустой очереди. Output-valid равен count>0, pop — output-valid AND output-ready. Input-ready равен count<depth OR pop, позволяя замену при одновременной выдаче головы полной очереди. Push равен input-valid AND input-ready. Следующий count равен count+push-pop. Два отдельных присваивания для увеличения и уменьшения count могут неправильно обработать одновременные передачи; используйте одно общее обновление или явные случаи.
| Старый count | Условия | push | pop | Новый count |
|---|---|---|---|---|
| 0 | Вход и готовый приёмник | 1 | 0 | 1 |
| 1 | Вход и готовый приёмник | 1 | 1 | 1 |
| 4 | Вход и остановленный приёмник | 0 | 0 | 4 |
| 4 | Вход и готовый приёмник | 1 | 1 | 4 |
Пустая очередь не может извлекать только потому, что приёмник готов. Её новый вход впервые передаётся на следующем фронте. Полная очередь [A,B,C,D], одновременно потребляющая A и принимающая E, становится [B,C,D,E], оставаясь полной. Проверяйте поведение базовой памяти при чтении и записи одной физической позиции.
FIFO на четыре элемента. Изначально пуст; указатели чтения и записи равны 0. pop принимается, если FIFO непуст. push принимается при наличии места или при принятом pop на том же фронте.
Глубины, равные степени двух, естественно циклически переходят по битам указателя. Глубина три требует явного перехода с позиции два на ноль. Проверяйте циклический переход, удаление последнего элемента и замену при заполненности отдельно.
Пустая очередь глубины четыре поглощает лишь четыре элемента при пяти тактах остановки приёмника. Пятый вход должен ждать. Источнику, который не может остановиться, нужна большая ёмкость или определённое правило потерь. Конечная FIFO не исправляет постоянно более медленное потребление. Проверяйте 0≤count≤depth, accepted-delivered=count и порядок меток; одни счётчики не выявят перестановку.
Попробуйте сами
Для глубины два и очереди [tag3,tag4] вход tag5 предлагается при out-ready=1. Найдите push, pop, следующий count и очередь. Был бы tag5 извлечён сразу, если бы очередь была пуста?
Прочитать объяснение
Pop=1 делает input-ready высоким несмотря на полную заполненность, поэтому push=1. Следующий count остаётся равным двум, очередь — [tag4,tag5]. Пустая очередь имеет out-valid=0, поэтому tag5 сохраняется и не может извлечься до более позднего фронта.