Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Представление FIFO (очереди) с операциями постановки в очередь и удаления из очереди .

FIFO - аббревиатура от first in, first out - в вычислениях и в теории систем , представляет собой метод организации манипулирования структурой данных - часто, в частности, буфером данных - где самая старая (первая) запись или `` голова '' очереди , обрабатываются в первую очередь.

Такая обработка аналогична обслуживанию людей в зоне очереди по принципу « первым пришел - первым обслужен» в той же последовательности, в которой они прибыли в хвост очереди.

FCFS - это также жаргонный термин для алгоритма планирования операционной системы FIFO , который дает каждому центральному процессору (ЦП) время в том порядке, в котором это требуется. Противоположность FIFO - это LIFO , «последним вошел - первым ушел», когда в первую очередь обрабатывается самая младшая запись или «вершина стека». [1] очереди приоритетов не является ни FIFO или LIFO , но может принять подобное поведение временно или по умолчанию. Теория массового обслуживания охватывает эти методы обработки структур данных , а также взаимодействия между очередями строгого FIFO.

Информатика [ править ]

Структура данных [ править ]

Представление очереди FIFO (first in, first out)

В зависимости от приложения FIFO может быть реализован как аппаратный сдвиговый регистр или с использованием различных структур памяти, обычно кольцевого буфера или типа списка . Для получения информации об абстрактной структуре данных см. Очередь (структура данных) . Большинство программных реализаций очереди FIFO не являются потокобезопасными и требуют механизма блокировки для проверки того, что цепочка структуры данных управляется только одним потоком за раз.

Код [ править ]

В следующем коде показана реализация связанного списка FIFO на языке C ++ . На практике существует ряд реализаций списков, включая популярные макросы C sys / queue.h систем Unix или шаблон стандартной библиотеки C ++ std :: list, что позволяет избежать необходимости реализации структуры данных с нуля.

#include  <память>#include  <stdexcept>используя  пространство имен  std ;template  < typename  T > class  FIFO  {  struct  Node  {  T  value ;  unique_ptr < узел >  next  =  nullptr ; Узел ( T  _value ) :  значение ( _value )  {}  }; unique_ptr < узел >  front  =  nullptr ;  unique_ptr < Узел > *  back  =  & front ;public :  void  enqueue ( T  _value )  {  * back  =  make_unique < Node > ( _value );  назад  =  & ( ** назад ). следующий ;  } T  dequeue ()  {  if  ( front  ==  nullptr )  throw  underflow_error ( «Ничего не удалять из очереди» );  Значение  T =  перед -> значение ;  front  =  двигаться ( вперед -> дальше );  возвращаемое  значение ;  } };

Сначала голова или хвост [ править ]

Конец очереди FIFO часто называют головным и хвостовым . К сожалению, по поводу этих терминов существуют разногласия:

  • Для многих людей элементы должны помещаться в очередь в хвосте и оставаться в очереди, пока они не достигнут начала и не покинут очередь оттуда. Эта точка зрения оправдана по аналогии с очередями людей, ожидающих какой-либо услуги, и параллельна использованию передней и задней части в приведенном выше примере.
  • Другие люди полагают, что предметы входят в очередь в голове и уходят в хвост, как еда, проходящая через змею. Очереди, написанные таким образом, появляются в местах, которые можно считать авторитетными, например, в операционной системе Linux .

Трубы [ править ]

В вычислительных средах, которые поддерживают модель каналов и фильтров для межпроцессного взаимодействия , FIFO - это другое имя именованного канала .

Планирование диска [ править ]

Контроллеры дисков могут использовать FIFO в качестве алгоритма планирования диска для определения порядка обслуживания запросов ввода-вывода диска.

Связь и сети [ править ]

Коммуникационные сетевые мосты , коммутаторы и маршрутизаторы, используемые в компьютерных сетях, используют FIFO для удержания пакетов данных на пути к их следующему пункту назначения. Обычно для каждого сетевого подключения используется по крайней мере одна структура FIFO. Некоторые устройства имеют несколько FIFO для одновременной и независимой постановки в очередь различных типов информации.

Электроника [ править ]

Расписание FIFO.

FIFO обычно используются в электронных схемах для буферизации и управления потоком между аппаратным и программным обеспечением. В своей аппаратной форме FIFO в основном состоит из набора указателей чтения и записи, хранения и логики управления. Хранение может быть статической памятью с произвольным доступом (SRAM), триггерами, защелками или любой другой подходящей формой хранения. Для FIFO нетривиального размера обычно используется двухпортовая SRAM, где один порт предназначен для записи, а другой - для чтения.

Синхронный FIFO - это FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронный FIFO использует разные часы для чтения и записи. Асинхронные FIFO создают проблемы с метастабильностью . Обычная реализация асинхронного FIFO использует код Грея (или любой код единичного расстояния) для указателей чтения и записи, чтобы гарантировать надежную генерацию флагов. Еще одно замечание относительно генерации флагов: необходимо обязательно использовать арифметику указателей для генерации флагов для реализаций асинхронного FIFO. И наоборот, можно использовать либо метод дырявого ведра, либо арифметику указателей для генерации флагов в реализациях синхронного FIFO.

Примеры флагов состояния FIFO включают: полный, пустой, почти полный, почти пустой и т. Д.

Первый известный FIFO, реализованный в электронике, был разработан Питером Альфке в 1969 году в Fairchild Semiconductors. [2] Питер Альфке позже стал директором Xilinx .

FIFO полный-пустой [ править ]

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

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

Адреса чтения и записи изначально находятся в первой ячейке памяти, и очередь FIFO пуста .

FIFO пуст
Когда регистр адреса чтения достигает регистра адреса записи, FIFO запускает пустой сигнал.
FIFO заполнен
Когда регистр адреса записи достигает регистра адреса чтения, FIFO запускает полный сигнал.

В обоих случаях адреса чтения и записи совпадают. Чтобы различать эти две ситуации, простое и надежное решение - добавить один дополнительный бит для каждого адреса чтения и записи, который инвертируется каждый раз, когда адрес переносится. При такой настройке условия устранения неоднозначности следующие:

  1. Когда регистр адреса чтения равен регистру адреса записи, FIFO пуст.
  2. Когда младшие биты адреса чтения равны младшим битам адреса записи, а дополнительные старшие биты различны, FIFO заполнен.

См. Также [ править ]

  • FINO (первый пришел , никогда не ушел)
  • Мусор на входе, мусор на выходе

Ссылки [ править ]

Цитаты [ править ]

  1. ^ Круз, Роберт Л. (1987) [1984]. Структуры данных и дизайн программ (второе издание) . Джоан Л. Стоун, Кенни Бек, Эд О'Догерти (работники производственного процесса) (второе изд. Учебника). Энглвуд Клиффс, Нью-Джерси 07632: Prentice-Hall, Inc. div. Саймона и Шустера. С.  150 . ISBN 0-13-195884-4. Определение конечной последовательности сразу же позволяет нам попытаться определить список: «список» терминов типа T - это просто конечная последовательность элементов множества T. ... Единственное различие между стеками и очереди и более общие списки - это операции, с помощью которых могут быть внесены изменения или доступ к списку.CS1 maint: location ( ссылка )
  2. ^ После Питера Alfke по адресу comp.arch.fpga на 19 июня 1998

Источники [ править ]

  • Cummings et al., Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparsions, SNUG San Jose 2002.