ФИФО (вычисления и электроника)

Представление очереди FIFO

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

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

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

Информатика

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

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

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

#include <memory>
#include <stdexcept>

using namespace std;

template <typename T>
class FIFO {
    struct Node {
        T value;
        shared_ptr<Node> next = nullptr;

        Node(T _value): value(_value) {}
    };

    shared_ptr<Node> front = nullptr;
    shared_ptr<Node> back  = nullptr;

public:
    void enqueue(T _value) {
        if (front == nullptr) {
            front = make_shared<Node>(_value);
            back = front;
        } else {
            back->next = make_shared<Node>(_value);
            back = back->next;
        }
    }

    T dequeue() {
        if (front == nullptr)
            throw underflow_error("Nothing to dequeue");

        T value = front->value;
        front = move(front->next);
        
        return value;
    }
};

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

Контроллеры дисков могут использовать FIFO в качестве алгоритма планирования диска для определения порядка обслуживания дисковых запросов ввода-вывода , где это также известно тем же инициализмом FCFS, что и для планирования ЦП, упомянутого ранее.

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

Электроника

График ФИФО

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

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

Синхронность

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

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

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

Флаги статуса

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

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

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

См. также

• Учет ФИФО и ЛИФО
• ДО
• Теория массового обслуживания
• SCHED_FIFO

Внешние ссылки

• Каммингс и др., Методы моделирования и синтеза для асинхронного проектирования FIFO с асинхронным сравнением указателей, SNUG, Сан-Хосе, 2002 г.