FIFO

У этого термина существуют и другие значения, см. FIFO и LIFO.

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

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

Этот принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда водители ожидают своей очереди на продолжение движения (в американских ПДД нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание. В более широком смысле, абстракция LIFO или Last-In-First-Out («последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающий First-In-Last-Out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце.^[1]

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

Информатика

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

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

Типичная структура данных выглядит следующим образом (пример на языке 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 в электронике была сделана Питером Алфке в 1969 году в компании Fairchild Semiconductors. Сейчас Питер Алфке является директором Xilinx.

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

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

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

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

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

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

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

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

См. также

• GIGO

Примечания

1. ↑ Роберт Круз. Структуры данных и проектирование программ. — Бином. Лаборатория знаний, 2008. — С. 768.

Ссылки

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