Эта статья требует дополнительных ссылок для проверки . ( март 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
FIFO - аббревиатура от first in, first out - в вычислениях и в теории систем , представляет собой метод организации манипулирования структурой данных - часто, в частности, буфером данных - где самая старая (первая) запись или `` голова '' очереди , обрабатываются в первую очередь.
Такая обработка аналогична обслуживанию людей в зоне очереди по принципу « первым пришел - первым обслужен» в той же последовательности, в которой они прибыли в хвост очереди.
FCFS - это также жаргонный термин для алгоритма планирования операционной системы FIFO , который дает каждому центральному процессору (ЦП) время в том порядке, в котором это требуется. Противоположность FIFO - это LIFO , «последним вошел - первым ушел», когда в первую очередь обрабатывается самая младшая запись или «вершина стека». [1] очереди приоритетов не является ни FIFO или LIFO , но может принять подобное поведение временно или по умолчанию. Теория массового обслуживания охватывает эти методы обработки структур данных , а также взаимодействия между очередями строгого FIFO.
Информатика [ править ]
Структура данных [ править ]
В зависимости от приложения 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 в основном состоит из набора указателей чтения и записи, хранения и логики управления. Хранение может быть статической памятью с произвольным доступом (SRAM), триггерами, защелками или любой другой подходящей формой хранения. Для FIFO нетривиального размера обычно используется двухпортовая SRAM, где один порт предназначен для записи, а другой - для чтения.
Синхронный FIFO - это FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронный FIFO использует разные часы для чтения и записи. Асинхронные FIFO создают проблемы с метастабильностью . Обычная реализация асинхронного FIFO использует код Грея (или любой код единичного расстояния) для указателей чтения и записи, чтобы гарантировать надежную генерацию флагов. Еще одно замечание относительно генерации флагов: необходимо обязательно использовать арифметику указателей для генерации флагов для реализаций асинхронного FIFO. И наоборот, можно использовать либо метод дырявого ведра, либо арифметику указателей для генерации флагов в реализациях синхронного FIFO.
Примеры флагов состояния FIFO включают: полный, пустой, почти полный, почти пустой и т. Д.
Первый известный FIFO, реализованный в электронике, был разработан Питером Альфке в 1969 году в Fairchild Semiconductors. [2] Питер Альфке позже стал директором Xilinx .
FIFO полный-пустой [ править ]
Аппаратный FIFO используется для синхронизации. Он часто реализуется как круговая очередь и поэтому имеет два указателя:
- Чтение указателя / чтение регистра адреса
- Указатель записи / регистр адреса записи
Адреса чтения и записи изначально находятся в первой ячейке памяти, и очередь FIFO пуста .
- FIFO пуст
- Когда регистр адреса чтения достигает регистра адреса записи, FIFO запускает пустой сигнал.
- FIFO заполнен
- Когда регистр адреса записи достигает регистра адреса чтения, FIFO запускает полный сигнал.
В обоих случаях адреса чтения и записи совпадают. Чтобы различать эти две ситуации, простое и надежное решение - добавить один дополнительный бит для каждого адреса чтения и записи, который инвертируется каждый раз, когда адрес переносится. При такой настройке условия устранения неоднозначности следующие:
- Когда регистр адреса чтения равен регистру адреса записи, FIFO пуст.
- Когда младшие биты адреса чтения равны младшим битам адреса записи, а дополнительные старшие биты различны, FIFO заполнен.
См. Также [ править ]
- FINO (первый пришел , никогда не ушел)
- Мусор на входе, мусор на выходе
Ссылки [ править ]
Цитаты [ править ]
- ^ Круз, Роберт Л. (1987) [1984]. Структуры данных и дизайн программ (второе издание) . Джоан Л. Стоун, Кенни Бек, Эд О'Догерти (работники производственного процесса) (второе изд. Учебника). Энглвуд Клиффс, Нью-Джерси 07632: Prentice-Hall, Inc. div. Саймона и Шустера. С. 150 . ISBN 0-13-195884-4.
Определение конечной последовательности сразу же позволяет нам попытаться определить список: «список» терминов типа T - это просто конечная последовательность элементов множества T. ... Единственное различие между стеками и очереди и более общие списки - это операции, с помощью которых могут быть внесены изменения или доступ к списку.
CS1 maint: location ( ссылка ) - ^ После Питера 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.