FIFO

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

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

Вариантом очереди является очередь с приоритетом, для которой нельзя использовать название 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 в электронике была сделана Питером Алфке (1931-2011) в 1969 году в компании Fairchild Semiconductor. Также Питер Алфке был директором Xilinx.

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

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

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

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

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

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

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

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

См. также

• RR
• SJN
• GIGO

Ссылки

• [www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO2.pdf Каммингс и др. Методы моделирования и синтеза для асинхронных конструкций FIFO с асинхронными указателями сравнения, SNUG Сан-Хосе, 2002] (англ.)

Отрывок, характеризующий FIFO

Соня кивнула головой.
Графиня обняла Соню и заплакала.
«Пути господни неисповедимы!» – думала она, чувствуя, что во всем, что делалось теперь, начинала выступать скрывавшаяся прежде от взгляда людей всемогущая рука.
– Ну, мама, все готово. О чем вы?.. – спросила с оживленным лицом Наташа, вбегая в комнату.
– Ни о чем, – сказала графиня. – Готово, так поедем. – И графиня нагнулась к своему ридикюлю, чтобы скрыть расстроенное лицо. Соня обняла Наташу и поцеловала ее.
Наташа вопросительно взглянула на нее.
– Что ты? Что такое случилось?
– Ничего… Нет…
– Очень дурное для меня?.. Что такое? – спрашивала чуткая Наташа.
Соня вздохнула и ничего не ответила. Граф, Петя, m me Schoss, Мавра Кузминишна, Васильич вошли в гостиную, и, затворив двери, все сели и молча, не глядя друг на друга, посидели несколько секунд.
Граф первый встал и, громко вздохнув, стал креститься на образ. Все сделали то же. Потом граф стал обнимать Мавру Кузминишну и Васильича, которые оставались в Москве, и, в то время как они ловили его руку и целовали его в плечо, слегка трепал их по спине, приговаривая что то неясное, ласково успокоительное. Графиня ушла в образную, и Соня нашла ее там на коленях перед разрозненно по стене остававшимися образами. (Самые дорогие по семейным преданиям образа везлись с собою.)
На крыльце и на дворе уезжавшие люди с кинжалами и саблями, которыми их вооружил Петя, с заправленными панталонами в сапоги и туго перепоясанные ремнями и кушаками, прощались с теми, которые оставались.
Как и всегда при отъездах, многое было забыто и не так уложено, и довольно долго два гайдука стояли с обеих сторон отворенной дверцы и ступенек кареты, готовясь подсадить графиню, в то время как бегали девушки с подушками, узелками из дому в кареты, и коляску, и бричку, и обратно.
– Век свой все перезабудут! – говорила графиня. – Ведь ты знаешь, что я не могу так сидеть. – И Дуняша, стиснув зубы и не отвечая, с выражением упрека на лице, бросилась в карету переделывать сиденье.
– Ах, народ этот! – говорил граф, покачивая головой.
Старый кучер Ефим, с которым одним только решалась ездить графиня, сидя высоко на своих козлах, даже не оглядывался на то, что делалось позади его. Он тридцатилетним опытом знал, что не скоро еще ему скажут «с богом!» и что когда скажут, то еще два раза остановят его и пошлют за забытыми вещами, и уже после этого еще раз остановят, и графиня сама высунется к нему в окно и попросит его Христом богом ехать осторожнее на спусках. Он знал это и потому терпеливее своих лошадей (в особенности левого рыжего – Сокола, который бил ногой и, пережевывая, перебирал удила) ожидал того, что будет. Наконец все уселись; ступеньки собрались и закинулись в карету, дверка захлопнулась, послали за шкатулкой, графиня высунулась и сказала, что должно. Тогда Ефим медленно снял шляпу с своей головы и стал креститься. Форейтор и все люди сделали то же.
– С богом! – сказал Ефим, надев шляпу. – Вытягивай! – Форейтор тронул. Правый дышловой влег в хомут, хрустнули высокие рессоры, и качнулся кузов. Лакей на ходу вскочил на козлы. Встряхнуло карету при выезде со двора на тряскую мостовую, так же встряхнуло другие экипажи, и поезд тронулся вверх по улице. В каретах, коляске и бричке все крестились на церковь, которая была напротив. Остававшиеся в Москве люди шли по обоим бокам экипажей, провожая их.
Наташа редко испытывала столь радостное чувство, как то, которое она испытывала теперь, сидя в карете подле графини и глядя на медленно подвигавшиеся мимо нее стены оставляемой, встревоженной Москвы. Она изредка высовывалась в окно кареты и глядела назад и вперед на длинный поезд раненых, предшествующий им. Почти впереди всех виднелся ей закрытый верх коляски князя Андрея. Она не знала, кто был в ней, и всякий раз, соображая область своего обоза, отыскивала глазами эту коляску. Она знала, что она была впереди всех.
В Кудрине, из Никитской, от Пресни, от Подновинского съехалось несколько таких же поездов, как был поезд Ростовых, и по Садовой уже в два ряда ехали экипажи и подводы.
Объезжая Сухареву башню, Наташа, любопытно и быстро осматривавшая народ, едущий и идущий, вдруг радостно и удивленно вскрикнула:
– Батюшки! Мама, Соня, посмотрите, это он!
– Кто? Кто?
– Смотрите, ей богу, Безухов! – говорила Наташа, высовываясь в окно кареты и глядя на высокого толстого человека в кучерском кафтане, очевидно, наряженного барина по походке и осанке, который рядом с желтым безбородым старичком в фризовой шинели подошел под арку Сухаревой башни.
– Ей богу, Безухов, в кафтане, с каким то старым мальчиком! Ей богу, – говорила Наташа, – смотрите, смотрите!
– Да нет, это не он. Можно ли, такие глупости.
– Мама, – кричала Наташа, – я вам голову дам на отсечение, что это он! Я вас уверяю. Постой, постой! – кричала она кучеру; но кучер не мог остановиться, потому что из Мещанской выехали еще подводы и экипажи, и на Ростовых кричали, чтоб они трогались и не задерживали других.
Действительно, хотя уже гораздо дальше, чем прежде, все Ростовы увидали Пьера или человека, необыкновенно похожего на Пьера, в кучерском кафтане, шедшего по улице с нагнутой головой и серьезным лицом, подле маленького безбородого старичка, имевшего вид лакея. Старичок этот заметил высунувшееся на него лицо из кареты и, почтительно дотронувшись до локтя Пьера, что то сказал ему, указывая на карету. Пьер долго не мог понять того, что он говорил; так он, видимо, погружен был в свои мысли. Наконец, когда он понял его, посмотрел по указанию и, узнав Наташу, в ту же секунду отдаваясь первому впечатлению, быстро направился к карете. Но, пройдя шагов десять, он, видимо, вспомнив что то, остановился.
Высунувшееся из кареты лицо Наташи сияло насмешливою ласкою.
– Петр Кирилыч, идите же! Ведь мы узнали! Это удивительно! – кричала она, протягивая ему руку. – Как это вы? Зачем вы так?
Пьер взял протянутую руку и на ходу (так как карета. продолжала двигаться) неловко поцеловал ее.
– Что с вами, граф? – спросила удивленным и соболезнующим голосом графиня.
– Что? Что? Зачем? Не спрашивайте у меня, – сказал Пьер и оглянулся на Наташу, сияющий, радостный взгляд которой (он чувствовал это, не глядя на нее) обдавал его своей прелестью.
– Что же вы, или в Москве остаетесь? – Пьер помолчал.
– В Москве? – сказал он вопросительно. – Да, в Москве. Прощайте.
– Ах, желала бы я быть мужчиной, я бы непременно осталась с вами. Ах, как это хорошо! – сказала Наташа. – Мама, позвольте, я останусь. – Пьер рассеянно посмотрел на Наташу и что то хотел сказать, но графиня перебила его:
– Вы были на сражении, мы слышали?
– Да, я был, – отвечал Пьер. – Завтра будет опять сражение… – начал было он, но Наташа перебила его:
– Да что же с вами, граф? Вы на себя не похожи…
– Ах, не спрашивайте, не спрашивайте меня, я ничего сам не знаю. Завтра… Да нет! Прощайте, прощайте, – проговорил он, – ужасное время! – И, отстав от кареты, он отошел на тротуар.
Наташа долго еще высовывалась из окна, сияя на него ласковой и немного насмешливой, радостной улыбкой.


Пьер, со времени исчезновения своего из дома, ужа второй день жил на пустой квартире покойного Баздеева. Вот как это случилось.
Проснувшись на другой день после своего возвращения в Москву и свидания с графом Растопчиным, Пьер долго не мог понять того, где он находился и чего от него хотели. Когда ему, между именами прочих лиц, дожидавшихся его в приемной, доложили, что его дожидается еще француз, привезший письмо от графини Елены Васильевны, на него нашло вдруг то чувство спутанности и безнадежности, которому он способен был поддаваться. Ему вдруг представилось, что все теперь кончено, все смешалось, все разрушилось, что нет ни правого, ни виноватого, что впереди ничего не будет и что выхода из этого положения нет никакого. Он, неестественно улыбаясь и что то бормоча, то садился на диван в беспомощной позе, то вставал, подходил к двери и заглядывал в щелку в приемную, то, махая руками, возвращался назад я брался за книгу. Дворецкий в другой раз пришел доложить Пьеру, что француз, привезший от графини письмо, очень желает видеть его хоть на минутку и что приходили от вдовы И. А. Баздеева просить принять книги, так как сама г жа Баздеева уехала в деревню.