Fifo что это такое в программировании
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 выдаёт сигнал «Полон».
Национальная библиотека им. Н. Э. Баумана
Bauman National Library
Персональные инструменты
FIFO (First In First Out)
FIFO (англ. First In First Out ) является аббревиатурой для «первый пришел, первый ушел», способа организации и управления буфером данных, где сначала обрабатывается самая старая (первая) запись, или ‘голова’ очереди. Она аналогична обработке очереди (первым пришел, первым обслужен (ПППО)): где люди покидают очередь в том порядке, в котором они прибывают.
Противоположностью FIFO является LIFO (Last In First Out), «последним пришел, первым ушел», где самая молодая запись или «вершина стека» обрабатывается в первую очередь. [1]
Очередь с приоритетами не является ни FIFO, ни LIFO, но может принять подобное поведение временно или по умолчанию.
Теория массового обслуживания охватывает эти методы для обработки структур данных, а также взаимодействия между строгими FIFO очередями.
Содержание
Информатика
Структура данных
В зависимости от прикладной программы, буфер FIFO может быть реализован в виде аппаратного регистра сдвига, или с использованием различных структур памяти, обычно циклическим буфером или одним из видов списков.
Реализация
Следующий код показывает реализацию связанного списка FIFO на языке C++. На практике, существует целый ряд реализаций списка, в том числе популярных макросов Unix-систем C sys/queue.h или шаблона стандартной библиотеки C++ std :: list, устраняя необходимость в реализации структуры данных с нуля.
Первоочередность головы или хвоста очереди
Концы очереди FIFO часто называют головой и хвостом. К сожалению, существует спор относительно этих терминов:
Программирование работы диска
Дисковые контроллеры могут использовать очередь FIFO в качестве алгоритма планирования работы диска для определения порядка обслуживания запросов ввода/вывода.
Коммуникации и сети
Сетевые мосты, коммутаторы и маршрутизаторы, используемые в компьютерных сетях используют FIFO для хранения пакетов данных на пути к их следующему месту назначения. Как правило, по меньшей мере, одна структура FIFO используется за сетевое соединение. Некоторые устройства имеют несколько FIFO для одновременного и независимого массового обслуживания различных типов информации.
Электроника
FIFO широко используются в электронных схемах для буферизации и управления потоком между аппаратным и программным обеспечением. В своей аппаратной форме, в первую очередь FIFO состоит из набора операций чтения и записи указателей, систем хранения данных и логики управления. Хранение может быть статическим оперативным запоминающим устройством (ОЗУ), триггерами или любой другой подходящей формой хранения. Для FIFO нетривиального размера обычно используется двухпортовый SRAM, где один порт предназначен для записи, а другой для чтения.
Синхронный FIFO это такой FIFO, где один и тот же тактовый сигнал используется как для чтения, так и для записи. Асинхронный FIFO использует различные тактовые сигналы для чтения и записи. Асинхронные FIFO вводят проблемы метастабильности. Общая реализация асинхронного FIFO использует код Грея (или любой блок кода расстояния) для чтения и записи указателей для обеспечения надежной генерации флага. Еще одно примечание, касающееся генерации флага, в том, что надо обязательно использовать арифметические операции над указателями, чтобы создать флаги для реализации асинхронного FIFO. С другой стороны, можно использовать либо подход, который называется «дырявое ведро», или арифметические операции над указателями для создания флагов в реализациях синхронных FIFO.
Примеры флагов состояния FIFO включают в себя: полный, пустой, почти полный, почти пустой, и т.д.
Очередь FIFO полна/пуста
Аппаратный FIFO используется для целей синхронизации. Он часто реализуется в виде круговой очереди, и, таким образом, имеет два указателя:
Операции чтения и записи адреса изначально находятся на первой позиции памяти и очередь FIFO пуста.
Очередь FIFO пуста
Когда регистр адреса чтения достигает регистра адреса записи, FIFO вызывает сигнал «Пуст».
Очередь FIFO полна
Когда регистр адреса записи достигает регистра адреса чтения, то FIFO запускает сигнал «Полон».
Как работает FIFO
FIFO это один из ключевых элементов цифровой техники. Это память типа «первым вошёл-первым ушёл» (first input – first output). Меня как разработчика ПЛИС FIFO окружают повсюду. Собственно я только и делаю что беру данные из одного FIFO и перекладываю в другое. Но как оно работает? В современных САПР конечно уже есть готовые элементы, у Altera есть замечательные мегафункции. У Xilinx есть Core Generator. Но что делать если что-то не устраивает в стандартных решениях? Ответ один – разобраться и написать самому.
В интернете существует большое количество статей про FIFO, и когда то мне попалась очень хорошая и толковая статья. К сожалению, сейчас я её не нашёл. Далее – мой личный опыт по созданию и применению компонента FIFO. Готовый элемент находится на Github в проекте fpga_components. Свой компонент потребовался по нескольким причинам:
Одно из главных применений FIFO это перевод данных с одной тактовой частоты на другую. Этим определяется такая схема. При одной тактовой частоте на запись и чтение автоматы можно упростить.
Давайте рассмотрим внешние порты компонента FIFO:
Флаги FIFO передаются типом bl_fifo_flag; Определение типа:
Обратите внимание, используется отрицательная логика. Узнали? Да, я ещё из тех динозавров кто работал с TTL на сериях 155, 533, 1533 и отдельными микросхемами FIFO. Так что эти флаги мне привычны, они были сделаны много лет назад и до сих пор используются.
Флаг ef – сигнализирует что FIFO пустое. Если ef=1, то из FIFO можно прочитать одно слово.
Флаг pae – сигнализирует, что FIFO почти пустое. На сколько почти определяет параметр FIFO_PAE. Если pae=1, то из FIFO можно прочитать не более чем FIFO_PAE слов.
Флаг hf – сигнализирует что FIFO заполнено наполовину.
Флаг paf – сигнализирует, что FIFO почти полное. На сколько почти определяет параметр FIFO_PAF. Если paf=1, то в FIFO можно записать не более чем FIFO_PAF слов
Флаг ff – FIFO полное. Если ff=0, то в FIFO записывать нельзя.
Флаг ovr – переполнение. Если ovr=1, то это значит что произошла запись в полное FIFO
Флаг und – underflow. Если und=1, то это значит что произошло чтение из пустого FIFO.
Вполне очевидно, что при записи в FIFO мы должны записать слово в двухпортовую память и увеличить счётчик записи. Или сначала увеличить, а потом записать. А при операции чтения надо зафиксировать данные на выходе и увеличить счётчик чтения. А вот дальше требуется решить следующие вопросы:
Надо ясно понимать, что узел перетактирования (в проекте это компонент ctrl_retack_counter_m12) передаёт данные с задержкой на несколько тактов. Поэтому состояния FIFO также изменяются с задержкой. Например, если FIFO пустое и него записано одно слово, то флаг ef=1 появится с некоторой задержкой. Это же относится к выходам количества слов в FIFO. Например, если в пустое FIFO будет записано 16 слов, то в процессе записи выход cnt_wr будет принимать значения 0,1,2,3, … 16 (это если не производится чтение из FIFO), а вот выход cnt_rd будет принимать значения например такие: 0, 5, 8, 12, 16. Точный порядок будет зависеть от соотношения частот и не может быть предсказан. Это принципиальное свойство FIFO которое работает на разных частотах. Хотя в зависимости от схемы синхронизации могут быть различные нюансы.
Определение пустого и полного FIFO производится на анализе счётчиков адресов. Причём у меня есть два адреса для записи (текущий и следующий) и два адреса для чтения, также текущий и следующий. В компоненте cl_fifo_control_m12 это сигналы w_adr, w_next_adr и r_adr, r_next_adr; Соотношение адресов в различных состояниях представлено на рисунках ниже.
В исходном состоянии w_adr=0, r_adr=0, w_next_adr=1, r_next_adr=1. Если w_adr=r_adr, то FIFO пустое.
При записи слово данных записывается по адресу w_adr и адрес записи увеличивается.
Через несколько таков значение w_adr будет передано в w_adr_to_rd (перейдёт в тактовый домен clk_rd) и по факту не совпадения r_adr и w_adr_to_rd будет установлен флаг ef=1, т.е. из FIFO можно будет считать слово данных. Однако одно слово это мало, для получения высокой скорости передачи надо работать с блоком данных. И здесь требуется использовать флаг PAE. Когда в FIFO будет записано FIFO_PAE слов, будет установлен флаг pae=1 и можно будет прочитать сразу блок данных. Это основной режим работы с DMA каналом.
Если скорость записи больше чем скорость чтения, то адрес записи догонит адрес чтения:
В этом случае w_next_adr будет равен r_adr, а точнее r_adr_to_wr (мы можем сравнивать только значения на своём тактовом домене). Это означает, что FIFO полное и записывать дальше нельзя, что бы не испортить уже записанные данные. Надо отметить, что для подключения АЦП это обычная ситуация. У нас такой режим называется однократный сбор через FIFO. В этом режиме АЦП записывает данные на большой скорости в FIFO, а медленный процессор эти данные считывает. При этом мы знаем, что действительными будет только блок данных который соответствует размеру FIFO. Обычно на этот размер как раз и программируется канал DMA. После чтения данных FIFO сбрасывается и всё повторяется снова. Вот в этом режиме принципиально важно, что бы запись в полное FIFO не портила предыдущие данные.
Если требуется записывать данные блоками, то надо использовать флаг PAF. Если paf=1, то в FIFO можно записать FIFO_PAF слов.
Значения флагов PAE и PAF надо выбирать из требований DMA контроллера к которому подключено FIFO. Например, для PCI Express у нас используется блок данных размером 4 кБ. Это 256 слов по 128 разрядов. Размер флага PAE я устанавливаю в 272. Т.е. чуть больше чем 256. Это я делаю намеренно, что бы не допускать опустошения FIFO. Ну не доверяю я схемам формирования флагов.
А как производится определение количества слов в FIFO? Всё достаточно просто – из адреса записи надо вычесть адрес чтения. Адрес кратен степени 2, поэтому вычитание будет идти по модулю 2^N; Поскольку у нас есть две пары адресов, то у нас получится и два значения количества слов в одном FIFO (может это как то связано с квантовой механикой?).
Значения флагов PAE и HF (по чтению) формируются из r_cnt. Значения PAF и HF(по записи) формируются из w_cnt.
Основной причиной, по которой пришлось разрабатывать свой компонент FIFO, является потребность в реализации циклического режима для работы на ЦАП. В этом режиме производится запись блока данных, он может быть любого размера, разумеется не превышая размера FIFO. А затем начинается чтение, причём после выдачи последнего записанного слова сразу происходит переход на первое слово. Это позволяет подключить медленный процессор к быстрому ЦАП. Компонент FIFO имеет два входа для циклического режима. rt_mode=1 означает, что после выдачи последнего записанного слова надо перейти на нулевой адрес.
А вот вход rt нужен немного для другого. Наличие rt=1 позволяет перевести FIFO на нулевой адрес в произвольный момент времени. Иногда это у нас тоже используется.
В проекте fpga_components представлены два FIFO:
Это конструкция будет синтезирована в двухпортовую память. Идея красивая и в результате доработки cl_fifo_x64_v7 получилось FIFO cl_fifo_m12.
Недостаточно написать FIFO, надо ещё проверить его работу. Для проверки используется подход принятый при разработке PROTEQ, о котором можно прочитать в моей предыдущей статье.
Существует компонент tb_00 который имеет настраиваемые параметры.
Он позволяет проверить прохождение потока данных через FIFO при различных соотношениях тактовых частот и уровнях срабатывания флагов PAE и PAF. Также существуют компоненты тестовых случаев:
Конечно, для каждого теста сохраняется и свой отчёт.
При необходимости тесты будут дополняться. Хочу обратить внимание, что для вывода текста в консоль я использую пакет PCK_FIO. Он резко упрощает вывод текста.
Например, вывод результатов выглядит так:
В итоге я считаю что получился элегантный компонент, достаточно удобный для практической работы.
Очереди сообщений в бэкенд-архитектуре: как построить надежную систему
Очереди сообщений — устоявшаяся технология, которую разработчики применяют уже много лет. Разберемся, как она работает.
Почему понадобились очереди сообщений
Серверные сообщения обычно устроены просто и однотипно: сервер получает запрос, обрабатывает его и сразу же возвращает клиенту. Схема хорошо работает до тех пор, пока обработка запроса занимает немного времени, например доли секунды.
Но бывает, что вернуть ответ клиентскому приложению сразу невозможно. Например, когда сервер обрабатывает видео — это может занять минуты и даже часы. На время обработки большого объема данных вычислительные ресурсы сервера загружены и его способность обрабатывать входящие запросы падает.
Что такое обмен серверными сообщениями и как он устроен
Допустим, серверное приложение получило тяжелый запрос. Оно передает его другим приложениям дальше по цепочке, а само продолжает общение с клиентом.
Для передачи сообщения другим приложениям используют специальный инструмент — очереди сообщений. Эта технология решает любые инфраструктурные вопросы:
Когда в вашем бэкенд-приложении задействованы очереди, обработка видео выглядит так:
Схема асинхронного обмена сообщениями между приложениями. Источник
FIFO и LIFO (ФИФО и ЛИФО) — что это такое
Сервисы обмена сообщениями между серверами делятся на два типа:
Сервисы для организации очередей сообщений
Популярные сервисы для организации очередей сообщений — RabbitMQ, Apache Kafka и Redis. Давайте посмотрим, чем они различаются.
RabbitMQ
Сервер организации очередей сообщений, написанный на языке программирования Erlang. Это распределенный и горизонтально масштабируемый брокер сообщений. Он позволяет разным программам взаимодействовать с помощью протокола AMQP, а через дополнительные модули — и с помощью некоторых других протоколов: MQTT, HTTP и так далее.
RabbitMQ — это инструмент, который силен в маршрутизации сообщений. Система поддерживает несколько видов распределения сообщений в сети, их комбинация позволяет создавать очень хитрые правила доставки сообщений.
Apache Kafka
Apache Kafka — продукт, который реализует систему распределенного журнала событий. Kafka славится своей скоростью работы и масштабируемостью. Из-за способности передавать терабайты данных эту систему очередей сообщений любят разработчики, работающие с Big Data. Например, ее используют в Airbnb, Adidas, Cisco и PayPal.
Redis
Redis создавалась как система хранения данных в оперативной памяти. Изначальное предназначение — ускорение доступа к востребованной информации и построение систем кеширования.
Но разработчики добавили в код возможность построения простых очередей и стеков. В итоге Redis применяют в качестве сервера очередей сообщений в проектах, где нужно быстро и дешево проверить инженерные гипотезы по работе с очередями.
Fifo что это такое в программировании
FIFO (англ. first in, first out — «первым пришёл — первым ушёл») — способ организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен» (ПППО). Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и так далее.
Этот принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда водители ожидают своей очереди на продолжение движения (в ПДД США нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание.
В более широком смысле, абстракция LIFO или last-in-first-out («последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающий first-in-last-out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце. [1]
Вариантом очереди является очередь с приоритетом, для которой нельзя использовать название FIFO, потому что в этом случае обработка структуры данных происходит по другому принципу. Теория массового обслуживания охватывает более общее понятие очереди, а также взаимодействие между очередями, обслуживание в которых осуществляется по принципу «строго-FIFO». Для обозначения этого принципа также используется аббревиатура FCFS ( first come, first served — «первым пришёл, первым обслужен»).