FIFO - акроним для первым пришел, первым ушел - в вычислениях и в теории систем - это метод организации манипуляции со структурой данных - часто, в частности, - где самая старая (первая) запись или «заголовок» очереди обрабатывается первой.
Такая обработка аналогична обслуживанию людей в зоне очереди по принципу в порядке очереди в той же последовательности, в которой они пришли к хвост очереди.
FCFS также является жаргонным термином для алгоритма планирования операционной системы FIFO , который дает каждому процессу центральному процессору (ЦП) время в порядок, в котором это требуется. Противоположность FIFO - это LIFO, «последним пришел - первым вышел», когда в первую очередь обрабатывается самая младшая запись или «вершина стека». Очередь с приоритетом не является ни FIFO, ни LIFO, но может принимать аналогичное поведение временно или по умолчанию. Теория очередей охватывает эти методы для обработки структур данных, а также взаимодействия между очередями строгого FIFO.
В зависимости от приложения, FIFO может быть реализован как аппаратный сдвиговый регистр или с использованием различных структур памяти, обычно кольцевого буфера или типа список. Для получения информации об абстрактной структуре данных см. Очередь (структура данных). Большинство программных реализаций очереди FIFO не являются потокобезопасными и требуют механизма блокировки для проверки того, что цепочка структур данных управляется только одним потоком за раз.
Следующий код показывает реализацию связанного списка FIFO C ++ на языке. На практике существует ряд реализаций списков, включая популярные макросы C sys / queue.h для Unix-систем или шаблон стандартной библиотеки C ++ std :: list, что позволяет избежать необходимости реализации структуры данных с нуля.
#include#include с использованием пространства имен std; шаблон class FIFO {struct Node {T value; unique_ptr следующий = nullptr; Узел (T _value): значение (_value) {}}; unique_ptr front = nullptr; unique_ptr * задняя = передняя; public: void enqueue (T _value) {* back = make_unique (_value); назад = (** назад).next; } T dequeue () {if (front == nullptr) throw underflow_error («Ничего не удалять из очереди»); Значение T = перед->значение; передний = двигаться (передний->следующий); возвращаемое значение; }};
Концы очереди 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 пусто.
В обоих случаях адреса чтения и записи совпадают. Чтобы различать эти две ситуации, простое и надежное решение - добавить один дополнительный бит для каждого адреса чтения и записи, который инвертируется каждый раз, когда адрес переносится. При такой настройке условия устранения неоднозначности следующие: