FIFO (англ. firstin,firstout «первым пришёл — первым ушёл») — способ организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработкиочереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен» (ПППО). Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и так далее.

Этот принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда водители ожидают своей очереди на продолжение движения (в ПДД США нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание.

В более широком смысле, абстракцияLIFO (last-in,first-out «последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающийfirst-in-last-out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце.^[1]

В случае FIFO список называюточередью, в случаеLIFO —стек.

Вариантом очереди являетсяочередь с приоритетом, для которой нельзя использовать название FIFO, потому что в этом случае обработка структуры данных происходит по другому принципу.Теория массового обслуживания охватывает более общее понятие очереди, а также взаимодействие между очередями, обслуживание в которых осуществляется по принципу «строго-FIFO». Для обозначения этого принципа также используется аббревиатураFCFS (firstcome,firstserved «первым пришёл, первым обслужен»). Для производства возможен вариантFPFO (firstproduct,firstout).

Винформатике этот термин относится к способу запоминания данных, обрабатываемых вочереди. Каждый элемент очереди хранится в структуре данных очереди (без исключений). Первые данные, добавленные в очередь, будут первыми из неё удалены, то есть обработка производится последовательно в том же порядке, что и поступление.

Типичная структура данных выглядит следующим образом (пример на языкеC++):

structfifo_node{structfifo_node*next;value_typevalue;};classfifo{fifo_node*front;fifo_node*back;fifo_node*dequeue(void){fifo_node*tmp=front;front=front->next;returntmp;}queue(value){fifo_node*tempNode=newfifo_node;tempNode->value=value;back->next=tempNode;back=tempNode;}};

(Для информации об абстрактных структурах данных см.очереди. Подробнее о реализации см.кольцевой буфер.)

Популярные 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 в электронике была сделана Питером Алфке (1931—2011) в 1969 году в компанииFairchild Semiconductor^[2]. Также Питер Алфке был директоромXilinx.

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

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

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

Очередь FIFO пуста

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

Очередь FIFO полна

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

• RR
• SJN
• GIGO
• LIFO
• Стек

• Каммингс и др. Методы моделирования и синтеза для асинхронных конструкций FIFO с асинхронными указателями сравнения, SNUG Сан-Хосе, 2002 (англ.)

• Кибернетика
• Межпроцессное взаимодействие
• Принципы программирования

• Википедия:Cite web (не указан язык)
• Википедия:Страницы с шаблоном Другие значения с устаревшим параметром