FIFO (вычислительная техника и электроника)

редактировать
Представление FIFO (очереди) с операциями постановки в очередь и удаления из очереди.

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

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

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

Содержание

  • 1 Информатика
    • 1.1 Структура данных
    • 1.2 Код
    • 1.3 Начало или конец
    • 1.4 Конвейеры
    • 1.5 Планирование диска
    • 1.6 Связь и сеть
  • 2 Электроника
    • 2.1 FIFO полный-пустой
  • 3 См. Также
  • 4 Ссылки
    • 4.1 Цитаты
    • 4.2 Источники

Информатика

Структура данных

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

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

Код

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

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

Начало или конец очереди

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

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

Pipes

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

Планирование диска

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

Связь и сеть

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

Электроника

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

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

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

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

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

FIFO полный-пустой

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

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

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

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

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

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

См. также

Ссылки

Цитаты

Источники

Последняя правка сделана 2021-05-20 07:38:47
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте