ФИФО (вычисления и электроника)
 | Эта статья нуждается в дополнительных цитатах для проверки . ( март 2015 г. ) |
В вычислительной технике и в теории систем « first in, first out » (первым пришел — первым вышел), сокращенно FIFO , — это метод организации манипуляций со структурой данных (часто, конкретно с буфером данных ), где самый старый (первый) ) запись, или «голова» очереди , обрабатывается первой.
Такая обработка аналогична обслуживанию людей в зоне очереди в порядке очереди (FCFS), т.е. в той же последовательности, в которой они достигают хвоста очереди.
FCFS — это также жаргонный FIFO термин, обозначающий алгоритм планирования операционной системы , который выделяет время центральному процессору (ЦП) каждому процессу в том порядке, в котором оно требуется. [1] Противоположностью FIFO является LIFO , «последним пришел — первым обслужен», где самая младшая запись или «верхушка стека» обрабатывается первой. [2] Очередь с приоритетами не является ни FIFO, ни LIFO, но может временно или по умолчанию действовать аналогично. Теория массового обслуживания охватывает эти методы обработки структур данных , а также взаимодействие между очередями строгого FIFO.
Информатика [ править ]
В зависимости от приложения FIFO может быть реализован в виде аппаратного сдвигового регистра или с использованием различных структур памяти, обычно кольцевого буфера или своего рода списка . Информацию об абстрактной структуре данных см. в разделе Очередь (структура данных) . Большинство программных реализаций очереди FIFO не являются потокобезопасными и требуют механизма блокировки для проверки того, что цепочкой структур данных управляет только один поток за раз.
В следующем коде показана реализация связанного списка FIFO на языке C++ . На практике существует ряд реализаций списков, включая популярные макросы C sys/queue.h систем Unix или шаблон стандартной библиотеки C++ std::list, что позволяет избежать необходимости реализации структуры данных с нуля.
#include <memory> #include <stdException> с использованием пространства имен std ; шаблон < имя типа T > класс FIFO { struct Node { T значение ; shared_ptr < узел > next = nullptr ; Узел ( T _value ) : значение ( _value ) {} }; shared_ptr < узел > front = nullptr ; shared_ptr < узел > назад = nullptr ; public : void enqueue ( T _value ) { if ( front == nullptr ) { front = make_shared <Node> _value ( ) ; сзади = спереди ; } Еще { назад -> следующий = make_shared < узел > ( _value ); назад = назад -> дальше ; } } T dequeue () { if ( front == nullptr ) throw underflow_error ( «Нечего удалять из очереди» ); Т Значение = передняя часть -> значение ; передний = двигаться ( вперед -> следующий ); возвращаемое значение ; } }; В вычислительных средах, которые поддерживают модель каналов и фильтров для межпроцессного взаимодействия , FIFO — это другое название именованного канала .
Контроллеры дисков могут использовать FIFO в качестве алгоритма планирования диска для определения порядка обслуживания дисковых запросов ввода-вывода , где это также известно тем же инициализмом FCFS, что и для планирования ЦП, упомянутого ранее. [1]
связи Мосты сетей , коммутаторы и маршрутизаторы, используемые в компьютерных сетях, используют FIFO для хранения пакетов данных на пути к следующему пункту назначения. Обычно для каждого сетевого соединения используется по крайней мере одна структура FIFO. Некоторые устройства имеют несколько FIFO для одновременной и независимой организации очереди различных типов информации. [3]
Электроника [ править ]
FIFO обычно используются в электронных схемах для буферизации и управления потоками между аппаратным и программным обеспечением. В своей аппаратной форме FIFO в основном состоит из набора указателей чтения и записи , логики хранения и управления. Хранилищем может быть статическая оперативная память (SRAM), триггеры , защелки или любая другая подходящая форма хранения. Для FIFO нетривиального размера обычно используется двухпортовая SRAM, где один порт предназначен для записи, а другой — для чтения.
Первый известный метод FIFO, реализованный в электронике, был предложен Питером Альфке в 1969 году в компании Fairchild Semiconductor . [4] Позже Альфке был директором Xilinx .
Синхронность [ править ]
Синхронный FIFO — это FIFO, в котором одни и те же часы используются как для чтения, так и для записи. Асинхронный FIFO использует разные такты для чтения и записи, и они могут создавать проблемы с метастабильностью . Общая реализация асинхронного FIFO использует код Грея (или любой код единичного расстояния) для указателей чтения и записи, чтобы гарантировать надежную генерацию флагов. Еще одно замечание относительно генерации флагов: необходимо обязательно использовать арифметику указателей для генерации флагов для асинхронных реализаций FIFO. можно использовать либо подход с дырявым ведерком И наоборот, для генерации флагов в синхронных реализациях FIFO , либо арифметику указателей.
Аппаратный FIFO используется для целей синхронизации. Она часто реализуется как циклическая очередь и, таким образом, имеет два указателя :
- Чтение указателя/чтение адресного регистра
- Указатель записи/регистр адреса записи
Флаги статуса [ править ]
Примеры флагов состояния FIFO: полный, пустой, почти полный и почти пустой. FIFO пуст, когда регистр адреса чтения достигает регистра адреса записи. FIFO заполняется, когда регистр адреса записи достигает регистра адреса чтения. Адреса чтения и записи изначально находятся в первой ячейке памяти, а очередь FIFO пуста .
В обоих случаях адреса чтения и записи оказываются равными. Чтобы различать эти две ситуации, простым и надежным решением является добавление одного дополнительного бита для каждого адреса чтения и записи, который инвертируется каждый раз при переносе адреса. При такой настройке условия устранения неоднозначности таковы:
- Когда регистр адреса чтения равен регистру адреса записи, FIFO пуст.
- Когда регистры адреса чтения и записи различаются только дополнительным старшим битом , а остальные равны, FIFO заполнен.
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б Эндрю С. Таненбаум; Герберт Бос (2015). Современные операционные системы . Пирсон. ISBN 978-0-13-359162-0 .
- ^ Крузе, Роберт Л. (1987) [1984]. Структуры данных и проектирование программ (второе издание) . Джоан Л. Стоун, Кенни Бек, Эд О'Догерти (работники производственного процесса) (второе (HC) издание учебника). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc., подразделение. Саймон и Шустер. п. 150. ИСБН 0-13-195884-4 .
- ^ Джеймс Ф. Куроуз; Кейт В. Росс (июль 2006 г.). Компьютерные сети: нисходящий подход . Аддисон-Уэсли. ISBN 978-0-321-41849-4 .
- ^ «Сообщение Питера Альфке на comp.arch.fpga от 19 июня 1998 г.» .
Внешние ссылки [ править ]
| Базы данных органов управления : Национальные |
|---|
| Одиночные узлы массового обслуживания | |
|---|---|
| Процессы прибытия | |
| Сети массового обслуживания | |
| Политика обслуживания | |
| Ключевые понятия | |
| Предельные теоремы | |
| Расширения | |
| Информационные системы | |
