ФИФО (вычисления и электроника)
 | Эта статья нуждается в дополнительных ссылок для проверки . ( март 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 заполнен.
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б Эндрю С. Таненбаум; Герберт Бос (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 г.» .
Внешние ссылки [ править ]
| Базы данных органов управления : Национальные |
|---|
| Одиночные узлы массового обслуживания | |
|---|---|
| Процессы прибытия | |
| Сети массового обслуживания | |
| Политика обслуживания | |
| Ключевые идеи | |
| Предельные теоремы | |
| Расширения | |
| Информационные системы | |
