В вычислительной технике и теории систем принцип «первым пришел — первым обслужен» (FIFO), сокращенно обозначаемый как FIFO , представляет собой метод организации обработки структуры данных (часто, в частности, буфера данных ), при котором самая старая (первая) запись, или «голова» очереди , обрабатывается первой.
Такая обработка аналогична обслуживанию людей в очереди по принципу «первым пришел — первым обслужен » (FCFS), т.е. в той же последовательности, в которой они попадают в конец очереди.
FCFS также является жаргонным термином для алгоритма планирования операционной системы FIFO , который предоставляет каждому процессу время центрального процессора (ЦП) в том порядке, в котором оно требуется. [1] Противоположностью FIFO является LIFO , last-in-first-out, где самая молодая запись или «вершина стека» обрабатывается первой. [2] Приоритетная очередь не является ни FIFO, ни LIFO, но может временно или по умолчанию принимать похожее поведение. Теория очередей охватывает эти методы обработки структур данных , а также взаимодействия между очередями strict-FIFO.
В зависимости от приложения FIFO может быть реализован как аппаратный сдвиговый регистр или с использованием различных структур памяти, обычно кольцевого буфера или разновидности списка . Для получения информации об абстрактной структуре данных см. Очередь (структура данных) . Большинство программных реализаций очереди FIFO не являются потокобезопасными и требуют механизма блокировки для проверки того, что цепочка структур данных обрабатывается только одним потоком за раз.
Следующий код показывает реализацию связанного списка FIFO на языке C++ . На практике существует ряд реализаций списков, включая популярные макросы Unix-систем C sys/queue.h или шаблон стандартной библиотеки C++ std::list, что позволяет избежать необходимости реализовывать структуру данных с нуля.
#include <память> #include <stdexcept> с использованием пространства имен std ; template < имя_типа T > class FIFO { struct Node { T value ; shared_ptr < Узел > next = nullptr ; Узел ( T _value ) : значение ( _value ) {} }; shared_ptr < Узел > front = nullptr ; shared_ptr < Узел > back = nullptr ; public : void enqueue ( T _value ) { if ( front == nullptr ) { front = make_shared < Node > ( _value ); back = front ; } else { back -> next = make_shared < Node > ( _value ); back = back -> next ; } } T dequeue () { if ( front == nullptr ) throw underflow_error ( "Нечего выводить из очереди" ); T значение = front -> value ; front = move ( front -> next ); return value ; } }; В вычислительных средах, поддерживающих модель каналов и фильтров для межпроцессного взаимодействия , FIFO — это еще одно название именованного канала .
Контроллеры дисков могут использовать FIFO в качестве алгоритма планирования диска для определения порядка обслуживания запросов ввода-вывода диска , где он также известен по той же инициализации FCFS, что и для планирования ЦП, упомянутого ранее. [1]
Коммуникационные сетевые мосты , коммутаторы и маршрутизаторы, используемые в компьютерных сетях, используют FIFO для хранения пакетов данных на пути к следующему месту назначения. Обычно для каждого сетевого соединения используется по крайней мере одна структура FIFO. Некоторые устройства имеют несколько FIFO для одновременной и независимой организации очередей различных типов информации. [3]
FIFO обычно используются в электронных схемах для буферизации и управления потоком между оборудованием и программным обеспечением. В своей аппаратной форме FIFO в основном состоит из набора указателей чтения и записи , логики хранения и управления. Хранилищем может быть статическая память с произвольным доступом (SRAM), триггеры , защелки или любая другая подходящая форма хранения. Для FIFO нетривиального размера обычно используется двухпортовая SRAM, где один порт выделен для записи, а другой для чтения.
Первая известная схема FIFO была реализована в электронике Питером Альфке в 1969 году в компании Fairchild Semiconductor . [4] Позднее Альфке был директором компании Xilinx .
Синхронный FIFO — это FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронный FIFO использует разные часы для чтения и записи, и они могут вызывать проблемы метастабильности . Распространенная реализация асинхронного FIFO использует код Грея (или любой код единичного расстояния) для указателей чтения и записи, чтобы гарантировать надежную генерацию флагов. Еще одно замечание относительно генерации флагов заключается в том, что для генерации флагов для асинхронных реализаций FIFO обязательно нужно использовать арифметику указателей. И наоборот, для генерации флагов в синхронных реализациях FIFO можно использовать либо подход с дырявым ведром , либо арифметику указателей.
Аппаратный FIFO используется для синхронизации. Он часто реализуется как кольцевая очередь и, таким образом, имеет два указателя :
Примеры флагов состояния FIFO включают: полный, пустой, почти полный и почти пустой. FIFO пуст, когда регистр адреса чтения достигает регистра адреса записи. FIFO заполнен, когда регистр адреса записи достигает регистра адреса чтения. Адреса чтения и записи изначально оба находятся в первой ячейке памяти, а очередь FIFO пуста .
В обоих случаях адреса чтения и записи оказываются равными. Чтобы различать эти две ситуации, простым и надежным решением будет добавить один дополнительный бит для каждого адреса чтения и записи, который инвертируется каждый раз, когда адрес переходит на следующий уровень. При такой настройке условия устранения неоднозначности следующие: