Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

Значительная часть образовательных программ высшего и среднего профессионального образования включает дисциплины, связанные с функциональной организацией вычислительных устройств и архитектурой вычислительных машин. При этом в ряде программ схемотехническая подготовка обучающихся не предусматривается, что делает затруднительным, а в некоторых случаях и нецелесообразным использование в учебном процессе популярных программных средств автоматизированного проектирования, предполагающих такую подготовку. В то же время разработка и экспериментальное исследование обучающимися функциональных моделей изучаемых устройств, не требующая схемотехнической подготовки, облегчает более глубокое изучение устройств на функциональном уровне. В связи с этим представляет интерес использование в качестве средства функционального моделирования широко известного табличного процессора Microsoft Excel, позволяющего ограничиться «крупноблочным» представлением моделируемых устройств, отвлекаясь от схемотехнических особенностей их реализации.

Цель работы: анализ возможностей построения и экспериментального исследования учебных функциональных моделей запоминающих устройств типа очередь с помощью табличного процессора Microsoft Excel.

Очередь можно определить как структуру данных, представляющую собой список элементов, организованных по принципу «первым пришел – первым вышел» (First In – First Out, FIFO). При реализации очереди могут быть использованы различные масштабы аппаратной поддержки. В частности, при программной реализации такая поддержка ограничивается выделением области оперативной памяти вычислительной машины для накопителя очереди [1-3]. Полностью аппаратная очередь обычно строится на основе адресного блока памяти и регистров-счетчиков для хранения и отслеживания положения головы и хвоста очереди. Возможно также и совместное использование программной и аппаратной реализации очередей [4]. Как правило, при организации работы очереди предусматривается слежение за ее состоянием. Выявляются два состояния: отсутствие данных (в этом случае блокируется чтение) и полное заполнение очереди (блокируется запись). Существуют различные алгоритмы управления переполнением очередей [5; 6]. Выделяют два вида очереди: линейная и кольцевая. Распространенной формой очереди является кольцевой или циклический буфер. В кольцевой очереди, в отличие от линейной, после записи данных в последнюю ячейку следующей ячейкой для записи становится первая ячейка очереди. Аналогично за чтением данных из последней ячейки следует чтение из первой ячейки очереди. Такая организация очереди, в отличие от обычного линейного буфера, позволяет использовать ячейки в начале очереди, освободившиеся после чтения данных, для продолжения процесса записи после занесения данных в последнюю ячейку очереди. Однако в этом случае при формировании условий для состояний отсутствия данных и полного заполнения очереди приходится уменьшать на единицу число используемых ячеек очереди.

В зависимости от того, какую ячейку памяти (ЯП) в режиме хранения выделяют счетчик записи (СЗ) (первую свободную или последнюю занятую) и счетчик чтения (СЧ) (первую занятую или последнюю свободную), возможны четыре варианта организации кольцевой очереди на основе блока памяти. Эти варианты представлены в таблице 1, где N – число ЯП в очереди, «%» – символ операции вычисления остатка от деления, Аmin – минимальное, Аmax – максимальное значение СЗ и СЧ.

Следует заметить, что число доступных для записи ЯП (ND) в кольцевой очереди на единицу меньше фактического числа: ND=N-1. Эту особенность можно пояснить на примере первого варианта очереди (табл. 1, строка 1). Условие полностью заполненной очереди, приостанавливающее процесс записи, выполняется, когда после очередной записи содержимое СЗ становится на единицу меньше (с учетом определения остатка от деления) содержимого СЧ: (СЗ+1)%N=СЧ. Таким образом, между последней записанной и первой считываемой ЯП всегда будет находится временно недоступная свободная ЯП.

Таблица 1

Варианты организации кольцевой очереди на основе блока памяти

Структура и режимы работы моделируемой очереди

Разработка и экспериментальное исследование функциональных моделей запоминающих устройств типа очередь рассматривается на примере кольцевой очереди на основе блока памяти, имеющей организацию в соответствии с вариантом 2 (табл. 1, строка 2). Очередь, так же как и стек, относится к безадресным запоминающим устройствам и по структуре, режимам и алгоритмам работы имеет много общего со стеком. В то же время у моделируемой кольцевой очереди есть существенные отличия от стека, в том числе: представляет собой кольцевой буфер; вместо одного регистра-счетчика адреса, который работает как суммирующий и вычитающий, содержатся два суммирующих; используется другой алгоритм чтения; иначе формируются признаки положительного и отрицательного переполнения. Предполагая совместное рассмотрение стека и очереди при изучении безадресных запоминающих устройств, с целью облегчения работы с моделями этих устройств далее, по возможности, используются обозначения и форма изложения (структура описания, названия таблиц, представляющих работу модели, и подрисуночных подписей для схем и экранных изображений), принятые в работе [7].

Структура моделируемой очереди приведена на рисунке 1а, где СЗ – счетчик записи, выполняющий функции регистра указателя (маркера) записи; БП – блок памяти, выполняющий функции накопителя очереди; СЧ – счетчик чтения, выполняющий функции регистра указателя (маркера) чтения; МП – мультиплексор адреса, позволяющий подавать на адресные входы БП при записи адрес из СЗ, а при чтении – из СЧ; РЗД – регистр записи данных; РЧД – регистр чтения данных. Аналогичный БП, а также РЗД и РЧД могут использоваться в стеке.

Рис. 1. Очередь на основе блока памяти: структура (а), алгоритм записи (б), алгоритм чтения (в), пример записи и чтения (г)

В очереди предусмотрена установка СЗ в нулевое состояние при подаче сигнала «Установка “0…0”», а СЧ – в состояние 11…1 при подаче сигнала «Установка “1…1”». Кроме того, содержимое любого из этих счетчиков можно увеличить на единицу с помощью соответствующего сигнала «+1». Счет в СЗ и СЧ выполняется по модулю максимального числа (в примере по модулю 7 – «111»), после достижения которого идет нулевое значение и счет продолжается. В очереди также формируются два признака: З (очередь полностью заполнена) и П (очередь пуста). При З=1 приостанавливается запись, а при П=1 – чтение.

Очередь работает в трех основных режимах: запись, чтение и хранение. Очередь находится в режиме хранения при отсутствии сигналов ЗП (запись) и ЧТ (чтение). Алгоритмы записи и чтения приведены на рисунках 1б и 1г, где М[СЗ] – содержимое ячейки БП с адресом, указанным в СЗ, а М[СЧ] – в СЧ.

Работа очереди на примере записи последовательности данных a, b, c и чтения данного c показана на рисунке 1в, где ЯП 0, ЯП2 1, ЯП 2, ЯП 3 – ячейки БП; символ «@» – маркер записи, отмечающий ячейку, адрес которой находится в СЗ; символ «#» – маркер чтения, отмечающий ячейку, адрес которой находится в СЧ. В примере перед записью данного а очередь пуста (П=1), а после записи данного с – полностью заполнена (З=1).

Разработка функциональной модели очереди

Разрабатывается функциональная модель учебного варианта очереди, накопителем которой является БП, содержащий восемь 8-разрядных ячеек памяти. Для удобства проведения экспериментальных исследований в функциональную модель очереди внесены дополнения и изменения, аналогичные тем, что использовались в функциональной модели стека [7]:

- включены поля для задания управляющих сигналов ЗП, ЧТ, НУ (начальная установка), ВД (ввод данных) и 8-разрядное поле Д (данные);

- РЗД заменен на регистр счетчик данных (РСД), в который можно не только заносить данные из поля ввода данных Д, но и (в режиме записи) автоматически увеличивать содержимое РСД на единицу (при ВД=1);

- добавлен блок управления (БУ) с управляющим выходом Т, состояние которого при каждом нажатии клавиши F9 (при НУ=0) меняется на противоположное, моделируя подачу четных (T=0) и нечетных (T=1) тактовых сигналов в узлы и блоки очереди, прекращающуюся при установке очереди в начальное состояние (НУ=1).

Изменения состояний регистров, ячеек памяти и признаков очереди в зависимости от поступающих управляющих и тактовых сигналов приведены в таблице 2. При этом работа РСД, РЧД и ячеек блока памяти описывается так же, как и в функциональной модели стека, где они имеют аналогичное назначение [7].

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

Таблица 2

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

Рис. 2. Экранная форма для экспериментального исследования очереди: начальная установка и приостановка чтения (а), запись и приостановка записи (б), чтение (в)

Таблица 3

Функциональное моделирование узлов и блоков очереди с помощью формул MS Excel

При разработке модели очереди каждому регистру, ЯП и признаку выделяется ячейка MS Excel, в которую помещается формула, описывающая его функционирование. В таблице 3 приведены сокращенные обозначения узлов и блоков очереди с указанными в квадратных скобках ссылками на ячейки MS Excel, содержащие соответствующие формулы, а также сами формулы. В модели очереди для моделирования отдельных узлов и блоков используются те же самые ячейки MS Excel, что и для аналогичных по назначению узлов и блоков стека. Благодаря этому формулы, описывающие работу БУ[C3], РСД[G4] и ячеек блока памяти полностью, а РЧД[G15] – частично совпадают с формулами, используемыми при моделировании стека [7].

Сохранение состояний ячеек MS Excel в процессе моделирования обеспечивается использованием формул с циклическими ссылками.

Экспериментальные исследования

Экспериментальные исследования требуют изменений параметров MS Excel, связанных с вычислением формул (вычисления в книге «вручную» и итеративные вычисления с предельным числом итераций, равным единице), которые обеспечивают моделирование выполнения такта в модели очереди, благодаря тому что при каждом нажатии клавиши F9 вызывают пересчет формул. Работа очереди исследуется в следующих трех режимах: записи, чтения и параллельного выполнения записи и чтения.

Рис. 3. Экранные формы при экспериментальном исследовании очереди: параллельное выполнение записи в ЯП4 и чтения из ЯП2 (а), записи в ЯП5 и чтения из ЯП3 (б)

Если после записи формируется признак З[I7]=1 (очередь полностью заполнена), то процесс записи приостанавливается, работа очереди может быть возобновлена при переходе в режим чтения. Записываемые данные вводятся в РСД[G4] либо с клавиатуры с помощью поля Д[G2], либо путем автоматического добавления единицы к содержимому РСД[G4] (при ВД[I4]=1). Если после чтения формируется признак П[I12]=1 (очередь пуста), то процесс чтения приостанавливается. В этом случае работа очереди может быть возобновлена при переходе в режим записи.

Режим параллельного выполнения записи и чтения является дополнительным. В первом такте содержимое РСД[G4] записывается в ЯП по адресу из СЗ[D6], и содержимое СЧ[D13] увеличивается на единицу. Во втором такте содержимое СЗ[D6] увеличивается на единицу, и в РЧД[I5] считывается содержимое ЯП, адрес которой находится в СЧ[D13]. Экранные формы для примеров параллельного выполнения записи и чтения приведены на рисунке 3.

При параллельной записи и чтении, если запись в ЯП производится в первом такте, а чтение из этой же ЯП – во втором, то признак П[I12]=1 не формируется.

Заключение

В ходе анализа возможностей функционального моделирования и экспериментального исследования запоминающих устройств типа очередь с помощью MS Excel выделено четыре основных варианта построения кольцевой очереди, определяемые тем, в какой последовательности выполняются действия в режиме записи (запись в ЯП и увеличение содержимого СЗ) и в режиме чтения (чтение из ЯП и увеличение содержимого СЧ).

Разработка функциональной модели и экспериментальное исследование очереди рассмотрены на примере кольцевой очереди, в которой в режиме записи в начале выполняется запись в ЯП, а в режиме чтения – увеличение содержимого СЧ. Создание модели включает: определение структуры, режимов и алгоритмов работы моделируемой очереди; разработку экранной формы для проведения экспериментальных исследований; описание изменения состояний регистров, счетчиков, ячеек памяти и триггеров признаков в зависимости от управляющих и тактовых сигналов; представление работы всех узлов и блоков очереди стандартными функциями MS Excel.

Экспериментальное исследование кольцевой очереди позволяет наблюдать «перемещение» недоступной для записи ЯП по множеству ячеек блока памяти. Особенностью моделируемой очереди является наличие дополнительного режима параллельной записи и чтения, который дает возможность в одном обращении к блоку памяти в первом такте выполнять запись, а во втором – чтение. Для проведения экспериментальных исследований рассмотренного варианта очереди достаточно нарисовать на листе MS Excel изображенную на рисунке 2 экранную форму и ввести в используемые ячейки формулы в соответствии с таблицей 3. Простота и наглядность экранной формы, автоматическое формирование очередного записываемого данного упрощают отладку и исследование модели устройства. Количество вариантов организации учебных очередей для моделирования может быть удвоено путем добавления очередей, растущих от старших к младшим адресам.