Какая структура данных описывается как fifo

FIFO (вычисления и электроника)

FIFO — аббревиатура от first in, first out — в вычислениях и в теории систем , представляет собой метод организации манипулирования структурой данных — часто, в частности, буфером данных — где самая старая (первая) запись или « голова » очереди , обрабатываются в первую очередь.

Такая обработка аналогична обслуживанию людей в зоне очереди по принципу « первым пришел — первым обслужен» в той же последовательности, в которой они прибыли в хвост очереди.

FCFS — это также жаргонный термин для алгоритма планирования операционной системы FIFO , который дает каждому центральному процессору (ЦП) время в том порядке, в котором это требуется. Противоположность FIFO — это LIFO , «последним вошел — первым ушел», когда в первую очередь обрабатывается самая младшая запись или «вершина стека». [1] очереди приоритетов не является ни FIFO или LIFO , но может принять подобное поведение временно или по умолчанию. Теория массового обслуживания охватывает эти методы обработки структур данных , а также взаимодействия между очередями строгого FIFO.

Содержание

Информатика [ править ]

Структура данных [ править ]

В зависимости от приложения FIFO может быть реализован как аппаратный сдвиговый регистр или с использованием различных структур памяти, обычно кольцевого буфера или типа списка . Для получения информации об абстрактной структуре данных см. Очередь (структура данных) . Большинство программных реализаций очереди FIFO не являются потокобезопасными и требуют механизма блокировки для проверки того, что цепочка структуры данных управляется только одним потоком за раз.

Код [ править ]

В следующем коде показана реализация связанного списка FIFO на языке C ++ . На практике существует ряд реализаций списков, включая популярные макросы C sys / queue.h систем Unix или шаблон стандартной библиотеки C ++ std :: list, что позволяет избежать необходимости реализации структуры данных с нуля.

Сначала голова или хвост [ править ]

Конец очереди FIFO часто называют головным и хвостовым . К сожалению, по поводу этих терминов существуют разногласия:

• Для многих людей элементы должны помещаться в очередь в хвосте и оставаться в очереди, пока они не достигнут начала и не покинут очередь оттуда. Эта точка зрения оправдана по аналогии с очередями людей, ожидающих какой-либо услуги, и параллельна использованию передней и задней части в приведенном выше примере.
• Другие люди полагают, что предметы входят в очередь в голове и уходят в хвост, как еда, проходящая через змею. Очереди, написанные таким образом, появляются в местах, которые можно считать авторитетными, например, в операционной системеLinux .

Трубы [ править ]

В вычислительных средах, которые поддерживают модель каналов и фильтров для межпроцессного взаимодействия , FIFO — это другое имя именованного канала .

Планирование диска [ править ]

Контроллеры дисков могут использовать FIFO в качестве алгоритма планирования диска для определения порядка обслуживания запросов ввода-вывода диска.

Связь и сети [ править ]

Коммуникационные сетевые мосты , коммутаторы и маршрутизаторы, используемые в компьютерных сетях, используют FIFO для удержания пакетов данных на пути к их следующему пункту назначения. Обычно для каждого сетевого подключения используется по крайней мере одна структура FIFO. Некоторые устройства имеют несколько FIFO для одновременной и независимой постановки в очередь различных типов информации.

Электроника [ править ]

FIFO обычно используются в электронных схемах для буферизации и управления потоком между аппаратным и программным обеспечением. В своей аппаратной форме FIFO в основном состоит из набора указателей чтения и записи, хранения и логики управления. Хранение может быть статической памятью с произвольным доступом (SRAM), триггерами, защелками или любой другой подходящей формой хранения. Для FIFO нетривиального размера обычно используется двухпортовая SRAM, где один порт предназначен для записи, а другой — для чтения.

Синхронный FIFO — это FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронный FIFO использует разные часы для чтения и записи. Асинхронные FIFO создают проблемы с метастабильностью . Обычная реализация асинхронного FIFO использует код Грея (или любой код единичного расстояния) для указателей чтения и записи, чтобы гарантировать надежную генерацию флагов. Еще одно замечание относительно генерации флагов: необходимо обязательно использовать арифметику указателей для генерации флагов для реализаций асинхронного FIFO. И наоборот, можно использовать либо метод дырявого ведра, либо арифметику указателей для генерации флагов в реализациях синхронного FIFO.

Примеры флагов состояния FIFO включают: полный, пустой, почти полный, почти пустой и т. Д.

Первый известный FIFO, реализованный в электронике, был разработан Питером Альфке в 1969 году в Fairchild Semiconductors. [2] Питер Альфке позже стал директором Xilinx .

FIFO полный-пустой [ править ]

Аппаратный FIFO используется для синхронизации. Он часто реализуется как круговая очередь и поэтому имеет два указателя:

1. Чтение указателя / чтение регистра адреса
2. Указатель записи / регистр адреса записи

Адреса чтения и записи изначально находятся в первой ячейке памяти, и очередь FIFO пуста .

FIFO пуст Когда регистр адреса чтения достигает регистра адреса записи, FIFO запускает пустой сигнал. FIFO заполнен Когда регистр адреса записи достигает регистра адреса чтения, FIFO запускает полный сигнал.

В обоих случаях адреса чтения и записи совпадают. Чтобы различать эти две ситуации, простое и надежное решение — добавить один дополнительный бит для каждого адреса чтения и записи, который инвертируется каждый раз, когда адрес переносится. При такой настройке условия устранения неоднозначности следующие:

Базовые принципы построения FIFO.

Очередь FIFO (First In, First Out) представляет собой циклический буфер, где будут храниться помещаемые в очередь данные. Есть два указателя: указатель на «голову» очереди ( head ) и указатель на «хвост» очереди ( tail ).

Новый записываемый элемент помещается в ячейку, на которую указывает head , затем этот указатель перемещается на следующую ячейку памяти буфера.

Выбираются элементы из очереди по указателю tail , после того, как элемент выбран из очереди, указатель tail так же передвигается вперед к следующей ячейке.

Обычно глубина FIFO и разрядность указателей являются числами степени двойки. Например, если разрядность указателей head и tail – это 8, то глубина FIFO будет 256 элементов.

Цикличность буфера обеспечивается автоматически. При последовательном увеличении значения указателя однажды возникнает перенос, а сам указатель при этом обнуляется (после указателя 255 его следующее значение будет 0).

Теперь, когда мы знаем, что есть два указателя, легко определить всякие информационные сигналы:

1. FIFO пусто, если значения указателей «голова» и «хвост» равны.
2. Число элементов хранимых в FIFO можно вычислить отняв от значения «головы» значение указателя «хвоста». Если получится отрицательное число, то нужно еще прибавить глубину FIFO.
3. FIFO полное, если число хранимых элементов на единицу меньше, чем глубина FIFO.

Возможно, последнее утверждение нуждается в пояснении. Например, глубина FIFO 256 элементов. Мы запишем в него 255 элементов, но читать из FIFO пока не будем. Тогда «голова»=255, а «хвост»=0. Сейчас FIFO полное. Если в него записать еще один элемент, то значение «головы» станет 0 (возникает перенос) и получится, что и «голова» и «хвост» становятся одинаковыми и равными нулю. Все, FIFO опять стало пустым? Конечно, это ошибка логики.

Нельзя допускать запись в полное FIFO и чтение/выборку элемента из пустого FIFO.

Все вышеописанное прекрасно, но что делать, если запись и чтение происходят с использованием разных тактовых частот, если FIFO асинхронное? Мы не можем на прямую сравнивать или делать какие-то арифметические операции с указателями «голова» и «хвост», так как в этом случае они храняться в разных клоковых доменах (clock domains).

Просто пересинхронизировать группу (8-ми битные счетчики указателей голова и хвост) сигналов в другой домен не есть хороший вариант, как было уже ранее показано в другой статье. Главная проблема здесь – не все биты шины могут перейти в другой клоковый домен одновременно, а значит двоичное число на шине может быть искажено.

С другой стороны, понятно, что и «хвост» и «голова» могут изменяться только на единицу за один раз. То есть они считают последовательно. Этот факт как раз и делает возможным использование специальных счетчиков — счетчиков Грея.

Код Грея — специальная система счисления, в которой два соседних значения различаются только в одном разряде.

Вот пример трехбитных кодов Грея. Слева в таблице значения обычного двоичного счетчика, а справа значения из счетчика Грея.

Методика использования кодов Грея может быть следующая. Значение счетчика указателя, например, головы FIFO перекодируется в код Грея и пересекает клоковый домен с помощью группы синхронизаторов (каждый – это два последовательных триггера). При этом, как мы знаем, не все биты могут быть зафиксированы верно: в новом клоковом домене в некоторых битах зафиксируются новые значения числа на шине, а в некоторых – старые значения. Однако, для кода Грея изменения в соседних числах счетчика происходят только в одном бите, значит только в одном бите и может произойти коллизия. Только один изменяющийся сейчас бит может быть принят не верно. В этом случае принимающий домен просто считает предыдущее число на шине, а верное, следующее число он считает на следующем такте своей частоты. Такая ошибка даже и ошибкой не считается, ведь она не приводит к аварии FIFO.

Принятый код Грея может быть перекодирован обратно в обычную двоичную систему счисления и тут уже мы имеем верное значение обоих указателей в одном клоковом домене. Теперь можно их сравнивать, вычислять число элементов в FIFO и так далее.

В принципе, FIFO может изначально держать указатели «головы» и «хвоста» в кодах Грея.

Вообще использование кодов Грея в асинхронных 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 используется для синхронизации. Он часто реализуется в виде кольцевой очереди и имеет два указателя:

1. Указатель чтения/Регистр адреса чтения
2. Указатель записи/Регистр адреса записи

Первоначально адреса чтения и записи оба равны первой позиции памяти, при этом очередь FIFO пуста.

Очередь FIFO пуста Когда регистр адреса чтения догоняет регистр адреса записи, триггер FIFO выдаёт сигнал «Пуст». Очередь FIFO полна Когда регистр адреса записи догоняет регистр адреса чтения, триггер FIFO выдаёт сигнал «Полон».