Буферы типа «очередь» и «магазин»

Кроме адресуемых регистров общего назначения получили распространение вспомогательные запоминающие устройства, называемые буферами данных. По способу организации движения информации в них различают два типа: буфер FIFO (first in – first out) – первым вошедший первым выходит или «очередь» и буфер LIFO (last in – first out) – последним вошедший первым выходит. Отличительной особенностью этих буферов памяти является отсутствие входов адреса записи и чтения, т.е. в них невозможно обратиться к произвольному адресу хранения.

Буфер FIFO

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

Функциональная схема FIFO приведена на рис. 3.30.

Рис. 3.30 Структура буфера FIFO

data in – шина входных данных

– write enable – разрешение записи данных

– write address –запись адреса

RE – read enable - разрешение чтения

RA – read address – чтение адреса

шина выходных данных

Диаграмма использования адресов приведена на рис. 3.31.

Рис. 3.31. Распределение памяти в буфере FIFO

Адрес записи от 0000 до 1111 задается счетчиком хвоста очереди СТ. ХВ. Сигнал «Поставить в очередь», поступая на вход – разрешение записи, записывает поступившие по входной шине данные в тот регистр памяти, номер которого хранится в СТ. ХВ. По срезу сигнала «Поставить в очередь» выходной код счетчика хвоста увеличивается на 1, подготавливая адрес записи для очередного сигнала «Поставить в очередь».

При поступлении сигнала «Извлечь из очереди» на выходной шине появляется слово, хранящееся в том регистре памяти, номер которого задан кодом счетчика головы очереди СТ. ГОЛ. По срезу сигнала выходной код счетчика увеличивается на 1, подготовив для выдачи следующее слово, ставшее теперь первым в очереди.

Переполнение счетчика хвоста очереди осложнений не вызовет, поскольку после максимально возможного кода счетчика 1111 в нем автоматически появится код 0000. Очередь в своем кольце просто переползет хвостом через нулевую отметку счетчика. Так же со временем переползет и голова.

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

Первая – буфер полон, тогда в него нельзя больше записать и нужно приостановить передатчик или перейти к другому буферу.

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

Обе ситуации имеют общий признак – равенство показаний обоих счетчиков после исчезновения входного сигнала. Этот признак выделяет компаратор. Если коды счетчиков стали равны после очередного извлечения из очереди, то очередь иссякла, буфер пуст. Если они стали равны после очередной постановки в очередь, то буфер полон. Характер последнего обращения к буферу запоминается в RS триггере. Сигналы, информирующие устройство управления об особых состояниях буфера, получаются как конъюнкции того или иного состояния триггера и признака равенства показаний счетчиков головы и хвоста.

Буфер LIFO

Другое название стек – stack – хранилище, которое загружаясь сверху, разгружается также сверху в обратном порядке (стог сена, поленница дров и т.д.).

Стек нужен когда выполнение задания прерывается более срочным и все данные, связанные с прерванной работой засылаются на временное хранение в буфер типа «магазин». Выполнение срочного задания может быть в свою очередь прервано поступлением сверхсрочного и т.д. и в стеке по мере погружения туда (сверху) новых и новых данных формируется очередь слов, стековый порядок извлечения которых (тоже сверху) соответствует правильной по рангу срочности очередности их обработки.

Функциональная схема LIFO приведена на рис. 3.32.

Рис. 3.32. Структура буфера LIFO

data in – шина входа данных в стек

данные из стека

– write enable – разрешение записи данных

– write address –запись адреса

RE – read enable - разрешение чтения данных

RA – read address – чтение адреса

INC – инкрементор

Основу стека также как и в FIFO составляет регистровая память и реверсивный счетчик адреса в котором хранится текущий номер регистра вершины стека. Реверсивный счетчик прибавляет единицу к своему содержимому при наличии сигнала «заслать в стек» и уменьшает на единицу если поступит сигнал «извлечь из стека».

Диаграмма использования адресов LIFO приведена на рис. 3.33.

Рис. 3.33 Схема распределения памяти в буфере LIFO

Адрес, по которому производится засылка в стек должен быть на единицу больше адреса, по которому выполняется чтение из стека. Такой сдвиг на 1 выполняет инкрементор INC.

Стек также имеет два особых состояния:

1. Если буфер пуст, т.е. код вершины 0000, то после четырехвходового элемента ИЛИ-НЕ получим сигнал об этом событии:

2. Если буфер полон, то код вершины 1111 пройдя через четырехвходовый конъюнктор даст единицу сигнала:

1Λ1Λ1Λ1 = 1

ИНКРЕМЕНТОР (INC)

Устройство комбинационного типа, увеличивающее выходной код на единицу по отношению к входному (рис. 3.34).

Рис. 3.34. Одноразрядный инкрементор

В основе INC лежит полусумматор, у которого складывается не 2 числа, а одно число «а» с функцией переноса предыдущего разряда «cr».

Перенос полусумматора CR = cr · a

Сумма S = cr ⊕ a = cr · + · a

a	cr	CR	S
0			0
			1
1

Не используются так как cr = 0

Из таблицы следует, что:

1. если cr = 0, то S = a, т.е. В = А (выходное слово повторяет входное)

2. если cr = 1, то S = a + 1, т.е. В = А + 1 (выходное слово увеличивается на единицу)

На рис. 3.35–а приведено УГО 4-х разрядного инкрементора, а на рис. 3.35-в структура n-разрядного:

а в

Рис. 3.35. а – УГО INC, в – трехразрядный инкрементор

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

Инкременторы и декременторы используются при организации серий обращений к последовательным адресам памяти в составе схем микропроцессоров.