FIFO (вычисления и электроника) - FIFO (computing and electronics)

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

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

Такая обработка аналогична обслуживанию людей в зона очереди на первым прибыл - первым обслужен Эквивалент в русском языке: поздний гость гложет и кость в той же последовательности, в которой они попали в хвост очереди.

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

Информатика

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

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

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

Код

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

#включают <memory>#включают <stdexcept>с помощью пространство имен стандартное;шаблон <typename Т>учебный класс ФИФО {    структура Узел {        Т ценить;        unique_ptr<Узел> следующий = nullptr;        Узел(Т _ценить): ценить(_ценить) {}    };    unique_ptr<Узел> передний = nullptr;    unique_ptr<Узел>* назад = &передний;общественный:    пустота ставить в очередь(Т _ценить) {        *назад = make_unique<Узел>(_ценить);        назад = &(**назад).следующий;    }    Т исключать из очереди() {        если (передний == nullptr)            бросать underflow_error("Нечего удалять из очереди");        Т ценить = передний->ценить;        передний = двигаться(передний->следующий);                возвращаться ценить;    }};

Сначала голова или хвост

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

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

Трубы

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

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

Контроллеры дисков могут использовать 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 используется для синхронизации. Часто реализуется как круговая очередь, и поэтому имеет два указателя:

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

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

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

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

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

Смотрите также

Рекомендации

Цитаты

  1. ^ Круз, Роберт Л. (1987) [1984]. Структуры данных и дизайн программы (второе издание). Джоан Л. Стоун, Кенни Бек, Эд О'Догерти (работники производственного процесса) (второе изд. Учебника). Энглвуд Клиффс, Нью-Джерси 07632: Prentice-Hall, Inc. div. Саймона и Шустера. стр.150. ISBN  0-13-195884-4. Определение конечной последовательности сразу же позволяет нам попытаться определить список: «список» терминов типа T - это просто конечная последовательность элементов множества T. ... Единственное различие между стеками и очереди и более общие списки - это операции с помощью которого могут быть сделаны изменения или доступ к списку.CS1 maint: location (связь)
  2. ^ Сообщение Питера Альфке на comp.arch.fpga от 19 июня 1998 г.

Источники