FIFO

FIFO планировщик процессов

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

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

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

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

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

Информатика

Структуры данных

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

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

struct fifo_node 
{
  struct fifo_node *next;
  value_type value;
};

class fifo
{
  fifo_node *front;
  fifo_node *back;

  fifo_node *dequeue(void)
  {
    fifo_node *tmp = front;
    front = front->next;
    return tmp;
  }

  queue(value)
  {
    fifo_node *tempNode = new fifo_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. Также Питер Алфке был директором Xilinx.

Очередь FIFO полна/пуста

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

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

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

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

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

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

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

См. также

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

Ссылки

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