Введение
В вычислительной технике и в теории систем, принцип "первый пришел – первый обслужен" (first in, first out, FIFO) – это метод организации обработки структуры данных (часто, в частности, буфера данных), при котором первым обрабатывается самый старый (первый) элемент, или "голова" очереди. Такая обработка аналогична обслуживанию людей в очереди по принципу "первый прибыл – первый обслужен" (first come, first served, FCFS), то есть в той же последовательности, в которой они присоединяются к концу очереди. FCFS также является общепринятым термином для алгоритма планирования задач операционной системы FIFO, который предоставляет каждому процессу время центрального процессора (CPU) в порядке поступления запросов. Противоположностью FIFO является LIFO (последний пришел – первый обслужен), при котором первым обрабатывается самый новый элемент, или "верх стека". Приоритетная очередь не является ни FIFO, ни LIFO, но может временно или по умолчанию использовать схожие принципы. Теория очередей охватывает эти методы обработки структур данных, а также взаимодействие между строгими FIFO-очередями.
In computing and in systems theory, first in, first out (the first in is the first out), acronymized as FIFO, is a method for organizing the manipulation of a data structure (often, specifically a data buffer) where the oldest (first) entry, or "head" of the queue, is processed first. Such processing is analogous to servicing people in a queue area on a first come, first served (FCFS) basis, i. e. in the same sequence in which they arrive at the queue's tail. FCFS is also the jargon term for the FIFO operating system scheduling algorithm, which gives every process central processing unit (CPU) time in the order in which it is demanded. FIFO's opposite is LIFO, last in first out, where the youngest entry or "top of the stack" is processed first. A priority queue is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default. Queueing theory encompasses these methods for processing data structures, as well as interactions between strict FIFO queues.
Электроника
FIFO широко используются в электронных схемах для буферизации и управления потоком данных между аппаратным и программным обеспечением. В аппаратной реализации FIFO в основном состоит из набора указателей чтения и записи, памяти и управляющей логики. Память может быть реализована на статической оперативной памяти (SRAM), триггерах, защелках или любой другой подходящей форме хранения. Для FIFO значительного размера обычно используется двухпортовая SRAM, где один порт предназначен для записи, а другой – для чтения. Первым известным FIFO, реализованным в электронике, был разработан Питером Альфке в 1969 году в Fairchild Semiconductor. Позже Альфке стал директором компании Xilinx.
Флаги состояния
Примеры флагов статуса FIFO включают: полный, пустой, почти полный и почти пустой. FIFO считается пустым, когда регистр адреса чтения достигает регистра адреса записи. FIFO считается полным, когда регистр адреса записи достигает регистра адреса чтения. Адреса чтения и записи изначально указывают на первое место в памяти, и очередь FIFO пуста. В обоих случаях адреса чтения и записи в итоге становятся равными. Чтобы различать эти две ситуации, простое и надёжное решение – добавить один дополнительный бит к каждому адресу чтения и записи, который инвертируется при каждом переполнении адреса. При такой конфигурации условия определения состояния следующие:
Когда регистр адреса чтения равен регистру адреса записи, FIFO пуст. Когда регистры адреса чтения и записи отличаются только в дополнительном старшем бите, а остальные биты совпадают, FIFO полон.
When the read address register equals the write address register, the FIFO is empty. When the read and write address registers differ only in the extra most significant bit and the rest are equal, the FIFO is full.