FIFO (информатика)
FIFO — акроним First In, First Out («первым пришёл — первым ушёл», англ. ), абстрактное понятие в способах организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен» (ПППО). Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и т.д.
Этот принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда водители ожидают своей очереди на продолжение движения (в американских ПДД нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание. В более широком смысле, абстракция LIFO или Last-In-First-Out («последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающий First-In-Last-Out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце. [1]
Вариантом очереди является очередь с приоритетом, для которой нельзя использовать название FIFO, потому что в этом случае обработка структуры данных происходит по другому принципу. Теория массового обслуживания охватывает более общее понятие очереди, а также взаимодействие между очередями, обслуживание в которых осуществляется по принципу «строго-FIFO».
Содержание
Информатика
Структуры данных
В информатике этот термин относится к способу запоминания данных, обрабатываемых в очереди. Каждый элемент очереди хранится в структуре данных очереди (без исключений). Первые данные, добавленные в очередь, будут первыми из неё удалены, т. е. обработка производится последовательно в том же порядке, что и поступление. Это типичное поведение для очереди, хотя и не единственно возможное (см. также алгоритмы LIFO (информатика) и стек).
Типичная структура данных выглядит следующим образом (На примере языка C/C++):
(Для информации об абстрактных структурах данных см. очереди. Подробнее о реализации см. кольцевой буфер.)
Популярные Unix-системы включают в языки программирования C/C++ файл заголовка sys/queue.h, который содержит макросы, используемые в приложениях по созданию FIFO очередей.
Споры о голове и хвосте очереди
Споры по поводу терминов «голова» и «хвост» существует в связи с очередями FIFO. Для большинства людей добавление нового элемента в очередь делается в её хвост, потом этот элемент остаётся в очереди до достижения её головы и, соответственно, оттуда покидает очередь. Эта точка зрения оправдана по аналогии с очередями людей, которые ждут каких-то услуг, при этом в приведенном выше примере можно найти параллели с использованием терминов «фронт» и «тыл». Однако, некоторые люди считают, что новые объекты входят в голову очереди и покидает её через хвост, подобно пище, проходящей через змея. Очереди, описанные таким образом, появляются в тех случаях, когда они могут рассматриваться как официальные, например, в описании операционной системы GNU/Linux.
Конвейеры
В вычислительных средах, которые поддерживают модели конвейеров и фильтров для межпроцессного взаимодействия, FIFO является альтернативным названием для именованного канала.
Планирование работы диска
Контроллеры дисков могут использовать метод FIFO в качестве алгоритма планирования работы диска по обслуживанию запросов ввода-вывода данных.
Коммуникация и сети
Коммуникационные мосты, коммутаторы и маршрутизаторы, используемые в компьютерных сетях, используют буферы FIFO для хранения пакетов данных при их передаче к следующему месту назначения. Обычно используется по крайней мере одна структура FIFO при каждом соединении сети. Некоторые устройства обладают несколькими буферами FIFO для одновременных и независимых очередей различных типов информации.
Электроника
Принцип FIFO обычно используется в электронных схемах для буферизации и управления потоком, передаваемом от аппаратного обеспечения к программному. В аппаратной форме FIFO в основном состоит из множества указателей чтения и записи, памяти и логики управления. Устройство памяти может быть SRAM, триггер, защёлка или любого другого подходящего типа. Для FIFO больших размеров используется, как правило, двойной порт SRAM, в котором один порт используется для записи, а другой для чтения.
Синхронным является такой FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронные FIFO используют для чтения и записи различные часы. При использовании асинхронных FIFO возникает проблема метастабильности. Чаще всего при реализации асинхронных указателей FIFO используется код Грея (или любой другой код, в котором два соседних значения шкалы сигнала отличаются только в одном разряде) для обеспечения надежной генерации флага. Заметим ещё, что для генерации флагов в асинхронных реализациях FIFO нужно обязательно использовать арифметические указатели. И наоборот, для генерации флагов в синхронных реализациях FIFO можно использовать либо алгоритм «дырявое ведро», либо тот же арифметический указатель.
Примерами флага статуса FIFO являются: полон, пуст, почти полон, почти пуст, и т.д.
Первая известная реализация FIFO в электронике была сделана Питером Алфке в 1969 году в компании Fairchild Semiconductors. Сейчас Питер Алфке является директором Xilinx.
Очередь FIFO полна/пуста
В аппаратуратных устройствах принцип FIFO используется для синхронизации. Он часто реализуется в виде кольцевой очереди и имеет два указателя:
- Указатель чтения/Регистр адреса чтения
- Указатель записи/Регистр адреса записи
Первоначально адреса чтения и записи оба равны первой позиции памяти, при этом очередь FIFO пуста.
Очередь FIFO пуста Когда регистр адреса чтения догоняет регистр адреса записи, триггер FIFO выдаёт сигнал «Пуст». Очередь FIFO полна Когда регистр адреса записи догоняет регистр адреса чтения, триггер FIFO выдаёт сигнал «Полон».
FIFO для самых маленьких (вместе с вопросами на интервью)
«Напишите на доске код на верилоге для FIFO» — это популярный вопрос во время интервью в компании типа Apple и AMD, причем у него есть вариации для всех уровней инженеров, так как существуют десятки типа реализаций FIFO: на D-триггерах, встроенной SRAM памяти или на массиве D-защелок; с одном или двумя тактовыми сигналами; с одним, двумя или N вталкиваниями / выталкиваниями в одном такте; с разделяемой несколькими FIFO общей памятью; с парой указателей для записи/чтения и с хранением элементов в виде связанного списка; FIFO позволяющее undo; FIFO позволяющие потери данных; всякая экзотика типа FIFO шириной ноль итд.
Если человек не в теме или не понял вопроса, он может начать «запускаем GUI от Xilinx, вносим параметры и инстанциируем сгенерированный код». Это вызывает реакцию, как если бы школьная учительница геометрии спросила «найдите гипотенузу» и школьник бы ткнул пальцем в гипотенузу и с улыбкой ответил «вот она!»
Если у человека в резюме есть десять лет опыта, он спросит «какое именно FIFO» ему показать из списка выше. Но если человек только что пришел с вводного курса, то он должен как минимум знать то что написано ниже. То есть уметь написать самое простое FIFO на D-триггерах и с одним тактовым сигналом, уметь его использовать с окружающей логикой и разпознать случаи, в которых его нужно применять.
Без этого умения вы не знаете Verilog и не умеете проектировать на уровне регистровых передач. К сожалению, FIFO нет в книге Харрис & Харрис («Цифровая схемотехника и архитектура компьютера: RISC-V»), и это ее недостаток. В реальной жизни любой компании которая проектирует CPU, GPU, сетевые чипы и нейроускорители, во многих блоках есть десятки FIFO.
[Тут может быть возражение, что в любой крупной компании, в которой вы будете работаеть, уже будет внутрення библиотека всех видов FIFO и вам в 90% случаев не нужно будет его писать. Но я не буду на это возражение отвечать.]
Небольшое отступление
Эту заметку я написал прежде всего для участников Сколковской Школы Синтеза Цифровых Схем, в качестве приквела к занятию «Стандартные блоки и приемы проектирования для ASIC и FPGA: очереди FIFO и кредитные счетчики». Это занятие проведет в субботу 22 января 2022 инженер-разработчик ПЛИС Дмитрий Смехов.
Дмитрий уже писал про FIFO на Хабре. Его заметка наглядно описывает, как работает пара из указателей для чтения и записи. Поэтому я очень рекомендую ее прочитать перед началом занятий, особенно часть начиная со слов «Определение пустого и полного FIFO» и до слов «Это означает, что FIFO полное и записывать дальше нельзя, что бы не испортить уже записанные данные».
При этом заметка Дмитрия посвящена FIFO с двумя тактовыми сигналами и памятью, причем глубиной степени двойки. Про FIFO с двумя тактовыми сигналами на школе будет отдельное занятие, по мотивам статей Клифа Каммингса (1, 2). Также при проектировании ASIC помимо FIFO c хранением данных в памяти часто используются FIFO на основе регистрового файла из D-триггеров, код для которых я написал в примере ниже.
Кроме этого статья Дмитрия недостаточно артикулирует зачем FIFO нужно вообще. Я попробую дать на пальцах некое первоначальное понимание для тех, кто видит FIFO впервые. А также дам три задачки, которые было бы хорошо решить участникам перед занятием, так как Дмитрий будет на нем говорить больше о кредитных счетчиках, чем о FIFO.
Что такое FIFO?
Итак: в базовом виде очередь FIFO — это блок для временного хранение информации, в который можно запихивать данные слева и получать их справа:
Альтернативные имена для сигналов:
Сигнал D в некоторых реализациях называют write_data, Q — read_data.
Сигналы Push/Pop иногда называют put/get и иногда write/read. Но тут нужно быть внимательным. Есть FIFO, которые Xilinx называет «стандартными», в которых данные приходят после запроса read. Но при проектировании ASIC чаще используются FIFO, в которых следующие данные уже присутствуют на шине, когда Empty=0, и установка сигнала Pop/Read в единицу вызовет удаление текущего значения с головы FIFO. После чего там окажется следующее значение и FIFO станет пустым.
Сигналы Empty/Full иногда называют Can_read/can_write.
Функционально FIFO — это просто массив с двумя указателями, которые также называют адресами и иногда индексами. write/put_pointer и read/get_pointer. Работает это так (gif отсюда):
А чем FIFO отличается от сдвигового регистра (shift register), спросите вы? Два отличия:
В сдвиговом регистре глубины D данное/трансфер проходит от начала до конца ровно за D сдвигов, то есть минимум за D тактов. В FIFO же этот путь зависит от количества элементов в FIFO. То есть если FIFO пустое, то записанный трансфер будет доступен для чтения уже в следущем такте (для FIFO на D-триггерах или SRAM-based с байпасом). Но если FIFO глубиной D почти полное (наполненность равна D-1), то путь займет минимуму D тактов.
В сдвиговом регистре мы перемещаем данные, а в FIFO — указатели. Это экономит динамическое энергопотребление чипа, которое зависит от движения данных по D-триггерам. Чем меньше движения, особенно для широких шин, тем лучше.
Ниже мы рассмотрим примеры базового FIFO, RTL код для которого вместе с моделью и тестовым окружением я выложил на GitHub. Обратите внимание, что я намеренно выложил код незаконченным — участники школы в порядке упражнения должны сами заполнить места, которые обозначены TODO.
Зачем нужно FIFO?
FIFO позволяет расцепить отправлятеля и получателя данных по времени. Например представим, что у нас есть два процессора, которые работают совершенно параллельно и даже могут иметь разные адресные пространства. Представим, что им нужно передать данные так, чтобы данные не размножились и не потерялись, а также чтобы один процессор не ждал другого а просто занимался своей активностью и читал или писал когда ему удобно.
Для этого можно сделать, чтобы при записи в ячейку с определенным адресом одним процессором происходила запись в FIFO, а при чтении с определеного адреса другим процессором происходило чтение из FIFO:
А что будет, спросите вы, если CPU2 будет пробовать читать из пустого FIFO, или CPU1 будет пробовать писать в заполненное FIFO? Вот тогда процессор CPU1 будет останавливаться на инструкции store и ждать, а процессор CPU2 будет останавливаться на инструкции LOAD и ждать. Такая опция называется gated storage, она реализована в некоторых встроенных процессорах, например MIPS interAptiv.
Другое применение: выравнивание результатов параллельных блоков по времени. Допустим вы хотите получить от двух блоков два потока чисел и сложить их попарно. При этом блоки посылают числа в разное время, а блок, получающий результаты, может не готов принять сумму. Нет проблем, строим вот такую конструкцию, которая складывает числа попарно, даже если они шлются в разное время. Код для этой конструкции тоже на гитхабе и тоже намеренно незаконченный:
Еще применение. Если вы носите некие данные вместе (например координаты точек и их цвета) и хотите отправить поток этих данных на обработку, но обрабатывать собираетесь только часть данных (например пересчитывать координаты, но не трогать цвета), то вы можете отправить необрабатываемые данные в находящееся сбоку FIFO, где они будут лежать и ждать соотвествующие им обрабатываемые данные:
FIFO также широко используют, чтобы принять результаты вычисление после конвейера, в комбинации с кредитными счетчиками. Эта схема мало описана в учебниках, но применяется сплошь и рядом в промышленности, описана в статьях и патентах. Альтернатива такой схеме — это вводить сложные остановки конвейера, что чревато багами и проблемами с таймингом. Комбинация «конвейер + FIFO + кредитный счетчик» гораздо лучше, о ней расскажет Дмитрий Смехов на Школе Синтеза:
Пример 1
Перейдем к примерам. p020_generic_flip_flop_fifo.v содержит намеренно незаконченную реализацию простого FIFO на D-триггерах, с регистровым файлом data, парой из указателей wr_ptr/rd_ptr и использованием счетчика для генерации флагов empty и full.
Результат работы синтезируемого модуля generic_flip_flop_fifo_rtl сравнивается с результатом несинтезируемой модели fifo_model , которая написана с использованием очереди (SystemVerilog queue).
Тонкий момент: так как в RTL-реализации имеется комбинационная логика после D-триггеров на выходе (это вполне допустимо), то при моделировании в тестовом окружении приходится идти на специальные ухищрения:
Вопрос на понимание 1: Каковы преимущества и каковы недостатки оставлять такой хвост из комбинационной логики после D-триггеров в данном примере
Вопрос на понимание 2: Перепишите пример, чтобы все выходы стали registered, то бишь шли от D-триггеров.
Для запуска примера можно использовать Icarus Verilog и GTKWaves. Как их установить, я описал в посте «Ни дня без строчки верилога — учим язык решением большого количества простых задач». Если вы поправите пример правильно, то вы увидите вот такие временные диаграммы:
и вот такой лог:
Вопрос на понимание 3: Позволяет ли данная реализация писать в полное FIFO?
Пример 2
Упражнение p021_gen_dff_fifo_pow2_depth.v делает то же самое, что и предыдущее упражнение, но отличает состояние empty от full без использования счетчика. Это возможно за счет введения ограничения — FIFO второго примера может иметь только глубину степени двойки (1, 2, 4, 8, . ). Это достигается с помощью введения дополнительного бита в указатели:
Замечу что FIFO первого примера может иметь глубину 3, 113 и вообще любую — в ASIC-х любят экономить D-триггеры. Точное вычисление размера требуемого FIFO (позволяет максимальную пропускную способность по требованиям, но ни элементом больше) — признак профессионализма. Впрочем даже для самых суровых профессионалов электронные компании часто оставляют небольшой запас, даже при защите с помощью кредитных счетчиков, так как стоимость ошибки в уже произведенном ASIC-е может быть астрономической.
Пример 3
Упражнение p022_three_fifos_around_adder.v — это та самая конструкция из трех FIFO и сумматора, которую мы уже обсудили выше.
В ней не хватает следующего кода, который нужно дописать для понимания:
Если вы сделаете все правильно, то пример выдаст следующий лог:
На временных диаграммах вы тоже можете увидеть, что в тестовой последовательности, cначала пары идут вместе и подряд (back-to-back). Потом получатель перестает принимать результаты (это называется backpressure). Еще до этого иссякает источник чисел B:
Через некоторое время прием восстанавливается и потом заталкивание и получение происходит случайно:
Вопрос на понимание 4: Будет ли схема работать, если удалить выходное FIFO? А одно из входных?
Вопрос на понимание 5: Зачем может понадобиться на выходе FIFO глубины 2 (подсказка: skid buffer).
На этом мы введение (первые 5% материала) в FIFO заканчиваем и ждем вас на Сколковской Школе Синтеза Цифровых Схем. Школу поддерживает Ядро Микропроцессор / Syntacore — они готовят прорыв в российских RISC-V суперскалярных микропроцессорах, и Cadence Design Systems — их софтвером, согласно Джону Кули, пользуются в Apple для проектирования айфонов. Плату Omdazz, которую держит в руках девушка Наташа, вам подарят бесплатно, если вы будете делать упражнения:
24. Очереди fifo
Логическая структура очереди Очередью FIFO (First — In — First- Out — «первым пришел — первым исключается»). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение — с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO. Основные операции над очередью — те же, что и над стеком — включение, исключение, определение размера, очистка, неразрушающее чтение.
Машинное представление очереди FIFO и реализация операций При представлении очереди вектором в статической памяти в дополнение к обычным для дескриптора вектора параметрам в нем должны находиться два указателя: на начало очереди (на первый элемент в очереди) и на ее конец (первый свободный элемент в очереди). При включении элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель увеличивается на единицу. При исключении элемента из очереди выбирается элемент, адресуемый указателем на начало, после чего этот указатель уменьшается на единицу.
В исходном состоянии указатели на начало и на конец указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца «догонит» указатель начала. Это ситуация заполненной очереди, но если в этой ситуации указатели сравняются, эта ситуация будет неотличима от ситуации пустой очереди. Для различения этих двух ситуаций к кольцевой очереди предъявляется требование, чтобы между указателем конца и указателем начала оставался «зазор» из свободных элементов. Когда этот «зазор» сокращается до одного элемента, очередь считается заполненной и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (не обязательно начального) значения в оба указателя. Определение размера состоит в вычислении разности указателей с учетом кольцевой природы очереди. Программный пример 4.3 иллюстрирует организацию очереди и операции на ней.
Function QWrite(a: data) : boolean;
Function QRead(var a: data) : boolean;
Function Qsize : integer;
var QueueA : array[1..SIZE] of data;
top, bottom : integer;
begin top:=1; bottom:=1; end;
begin top:=bottom; end;
Function QWrite(a : data) : boolean;
if bottom mod SIZE+1=top then < очередьполна >QWrite:=false
Queue[bottom]:=a; bottom:=bottom mod SIZE+1; QWrite:=true;
Function QRead(var a: data) : boolean;
if top=bottom then QRead:=false else
begin a:=Queue[top]; top:=top mod SIZE + 1; QRead:=true;
Function QSize : integer;
if top <= bottom then QSize:=bottom-top
Очереди с приоритетами
В реальных задачах иногда возникает необходимость в формировании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов. Так, и FIFO, и LIFO-очереди могут трактоваться как приоритетные очереди, в которых приоритет элемента зависит от времени его включения в очередь. При выборке элемента всякий раз выбирается элемент с наибольшим приоритетом.
Очереди с приоритетами могут быть реализованы на линейных списковых структурах — в смежном или связном представлении. Возможны очереди с приоритетным включением — в которых последовательность элементов очереди все время поддерживается упорядоченной, т.е. каждый новый элемент включается на то место в последовательности, которое определяется его приоритетом, а при исключении всегда выбирается элемент из начала. Возможны и очереди с приоритетным исключением — новый элемент включается всегда в конец очереди, а при исключении в очереди ищется (этот поиск может быть только линейным) элемент с максимальным приоритетом и после выборки удаляется из последовательности. И в том, и в другом варианте требуется поиск, а если очередь размещается в статической памяти — еще и перемещение элементов.
Очереди в вычислительных системах Идеальным примером кольцевой очереди в вычислительной системы является буфер клавиатуры в Базовой Системе Ввода-Вывода ПЭВМ IBM PC. Буфер клавиатуры занимает последовательность байтов памяти по адресам от 40:1E до 40:2D включительно. Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT, Unix, OS/2, ЕС и др.). Ресурсы вычислительной системы (процессор, оперативная память, внешние устройства и т.п.( используются всеми задачами, одновременно выполняемыми в среде такой операционной системы. Поскольку многие виды ресурсов не допускают реально одновременного использования разными задачами, такие ресурсы предоставляются задачам поочередно. Таким образом, задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Эти очереди обычно приоритетные, однако, довольно часто применяются и FIFO-очереди, так как это единственная логическая организация очереди, которая гарантированно не допускает постоянного вытеснения задачи более приоритетными. LIFO-очереди обычно используются операционными системами для учета свободных ресурсов. Также в современных операционных системах одним из средств взаимодействия между параллельно выполняемыми задачами являются очереди сообщений, называемые также почтовыми ящиками. Каждая задача имеет свою очередь — почтовый ящик, и все сообщения, отправляемые ей от других задач, попадают в эту очередь. Задача-владелец очереди выбирает из нее сообщения, причем может управлять порядком выборки — FIFO, LIFO или по приоритету.
FIFO (вычислительная техника и электроника) — FIFO (computing and electronics)
Представление FIFO (очереди) с операциями постановки в очередь и удаления из очереди.
FIFO — акроним для первым пришел, первым ушел — в вычислениях и в теории систем — это метод организации манипуляции со структурой данных — часто, в частности, — где самая старая (первая) запись или «заголовок» очереди обрабатывается первой.
Такая обработка аналогична обслуживанию людей в зоне очереди по принципу в порядке очереди в той же последовательности, в которой они пришли к хвост очереди.
FCFS также является жаргонным термином для алгоритма планирования операционной системы FIFO , который дает каждому процессу центральному процессору (ЦП) время в порядок, в котором это требуется. Противоположность FIFO — это LIFO, «последним пришел — первым вышел», когда в первую очередь обрабатывается самая младшая запись или «вершина стека». Очередь с приоритетом не является ни FIFO, ни LIFO, но может принимать аналогичное поведение временно или по умолчанию. Теория очередей охватывает эти методы для обработки структур данных, а также взаимодействия между очередями строгого FIFO.
Содержание
- 1 Информатика
- 1.1 Структура данных
- 1.2 Код
- 1.3 Начало или конец
- 1.4 Конвейеры
- 1.5 Планирование диска
- 1.6 Связь и сеть
- 2.1 FIFO полный-пустой
- 4.1 Цитаты
- 4.2 Источники
Информатика
Структура данных
Представление Очередь FIFO (first in, first out)
В зависимости от приложения, FIFO может быть реализован как аппаратный сдвиговый регистр или с использованием различных структур памяти, обычно кольцевого буфера или типа список. Для получения информации об абстрактной структуре данных см. Очередь (структура данных). Большинство программных реализаций очереди FIFO не являются потокобезопасными и требуют механизма блокировки для проверки того, что цепочка структур данных управляется только одним потоком за раз.
Следующий код показывает реализацию связанного списка FIFO C ++ на языке. На практике существует ряд реализаций списков, включая популярные макросы C sys / queue.h для Unix-систем или шаблон стандартной библиотеки C ++ std :: list, что позволяет избежать необходимости реализации структуры данных с нуля.
Начало или конец очереди
Концы очереди FIFO часто называют началом и хвостом. К сожалению, существуют разногласия относительно этих терминов:
- Для многих людей элементы должны помещаться в очередь в хвосте и оставаться в очереди, пока они не достигнут заголовка и не покинут очередь оттуда. Эта точка зрения оправдана по аналогии с очередями людей, ожидающих какого-либо обслуживания, и параллельна использованию передней и задней части в приведенном выше примере.
- Другие люди считают, что предметы входят в очередь в начале и покидают в хвосте, как еда, проходящая через змею. Очереди, записанные таким образом, появляются в местах, которые можно считать авторитетными, например, в операционной системеLinux.
Pipes
В вычислительных средах, поддерживающих каналы и фильтры модель для межпроцессного взаимодействия, FIFO — это другое имя для именованного канала.
Планирование диска
Контроллеры дисков могут использовать FIFO в качестве алгоритма планирования диска для определить порядок обслуживания запросов дискового ввода-вывода.
Связь и сеть
Связь сетевые мосты, коммутаторы и маршрутизаторы, используемые в компьютерных сетях используйте FIFO для хранения пакетов данных на пути к следующему пункту назначения. Обычно для каждого сетевого подключения используется по крайней мере одна структура FIFO. Некоторые устройства имеют несколько FIFO для одновременной и независимой постановки в очередь различных типов информации.
Электроника
Расписание FIFO.FIFO обычно используются в электронных схемах для буферизации и управления потоком между аппаратным и программным обеспечением. В своей аппаратной форме FIFO в основном состоит из набора указателей чтения и записи, хранения и логики управления. Хранение может быть статической памятью с произвольным доступом (SRAM), триггерами, защелками или любой другой подходящей формой хранения. Для FIFO нетривиального размера обычно используется двухпортовая SRAM, где один порт предназначен для записи, а другой — для чтения.
Синхронный FIFO — это FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронный FIFO использует разные часы для чтения и записи. Асинхронные FIFO создают проблемы с метастабильностью. Обычная реализация асинхронного FIFO использует код Грея (или любой код единичного расстояния) для указателей чтения и записи, чтобы гарантировать надежную генерацию флагов. Еще одно замечание относительно генерации флагов: необходимо обязательно использовать арифметику указателей для генерации флагов для реализаций асинхронного FIFO. И наоборот, можно использовать либо подход дырявого ведра, либо арифметику указателя для генерации флагов в реализациях синхронного FIFO.
Примеры флагов состояния FIFO включают: полный, пустой, почти полный, почти пустой и т. Д.
Первый известный FIFO, реализованный в электронике, был разработан Питером Альфке в 1969 году в Fairchild Semiconductors. Питер Альфке позже был директором в Xilinx.
FIFO полный-пустой
Аппаратный FIFO используется для целей синхронизации. Он часто реализуется как кольцевая очередь и поэтому имеет два указателя:
- Указатель чтения / регистр адреса чтения
- Указатель записи / регистр адреса записи
Адреса чтения и записи изначально и в первой ячейке памяти, и в очереди FIFO пусто.
FIFO пустой Когда чтение адресного регистра достигает регистра адреса записи, FIFO запускает пустой сигнал. FIFO full Когда регистр адреса записи достигает регистра адреса чтения, FIFO запускает полный сигнал.
В обоих случаях адреса чтения и записи совпадают. Чтобы различать эти две ситуации, простое и надежное решение — добавить один дополнительный бит для каждого адреса чтения и записи, который инвертируется каждый раз, когда адрес переносится. При такой настройке условия устранения неоднозначности следующие: