Упрощение логической схемы алгоритма

Московский технический университет связи и информатики Контрольная работа по дисциплине Техника микропроцессорных систем в коммутации Москва 2015 г.

Задача 1.

По заданной в таблице 1 логической схеме алгоритма (ЛСА0 необходимо:

1) построить граф-схему алгоритма ГСА;

2) получить матричную схему алгоритма МСА;

3) получить схему формул переходов ФП и упростить ЛСА;

4) записать упрощенную ЛСА ;

5) доказать эквивалентность ЛСА и, вычислив значение ЛСА на всех наборах значений логических условий;

6) по заданному в таблице 1 распределению сдвигов упростить ЛСА и получить ЛСА ;

7) используя заданную в таблице 1 ЛСА, объединить частные ЛСА и в общую ЛСА, где .

Номер варианта определяется последней цифрой номера студенческого билета.

Таблица 1

Решение:

1. Построим граф-схему алгоритма ГСА по ЛСА:

2. Получим матричную схему алгоритма МСА:

Рис. 1

3. Получим систему формул переходов ФП и упростим ЛСА.

ц ₁

Все формулы переходов входящие в систему являются элементарными и поэтому не упрощаются. Невозможность упрощения ЛСА видна и по ГСА, так как алгоритм достаточно простой.

4. Используя заданную ЛСА, объединить частные ЛСА ₁ и в общую ЛСА, где

Матричная схема алгоритма у нас уже есть.

Получим матричную схему алгоритма .

По частным МСА составим объединенную .

Чтобы различить принадлежность определенного перехода, логическое выражение умножаем на определяющую функцию «r», а для на определяющую функцию ««.

ц ₀

Преобразуем общую ЛСА .

ц ₀

На рисунке 2 покажем наглядно полученную ЛСА с помощью ГСА.

Рис. 2

Задача 2

Дано:

Таблица 2 Отношение 1: R_Абонент 1

Таблица 3 Отношение 2: R_Абонент 2

Выполняемая операция: «Пересечение».

Требуется:

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

Решение:

Результат пересечения содержит только те кортежи первого отношения, которые есть во втором.

Таблица 4

Задача 3.

Разместить N страниц виртуальной памяти в оперативном запоминающем устройстве (ОЗУ) и во внешних запоминающих устройствах (ВЗУ) ЭУС при наличии:

S₀ свободных сегментов в ОЗУ,

S_Д свободных сегментов в накопителе на магнитных дисках (НМД),

S_Л свободных сегментов в накопителе на магнитных лентах (НМЛ).

А также составить таблицу страниц с указанием доступности страниц при заданной активности страниц.

Показать на рисунке принцип взаимосвязи страниц виртуальной памяти с сегментами ОЗУ и ВЗУ через таблицу страниц.

Дано:

Таблица 5

Для того чтобы сопоставить виртуальному адресу страницы физический адрес сегмента того или иного ЗУ на данный момент работы ЭУМ, в ОЗУ машины постоянно хранится так называемая таблица страниц.

Составим таблицу страниц с указанием доступности страниц при заданной активности.

Таблица 6

Покажем на рисунке 3 принцип взаимосвязи страниц виртуальной памяти с сегментами ОЗУ и ВЗУ через таблицу страниц.

Страницы с наибольшей активностью размещены в ОЗУ. Те страницы, которые не разместились в ОЗУ, размещены в ВЗУ. При этом в сегменты, находящиеся в НМД, размещены оставшиеся после размещения в ОЗУ страницы с большей активностью, так как НМД имеет большее быстродействие, чем НМЛ, и при наличии трехуровневой иерархии памяти ЭУМ информация из НМД поступает непосредственно в ОЗУ, а из НМЛ в ОЗУ поступает через НМД.

Рис. 3

Для простоты на рисунке указаны не страницы и сегменты, а группы страниц.

Задача 4.

Изобразить структурную схему централизованной неоднородной многопроцессорной ЭУМ Структурная схема централизованной неоднородной многопроцессорной ЭУМ показана рисунке 4,

Рис. 4

где УК — узел коммутации, ПУУ — периферийные управляющие устройства, ЦБУ — центральное управляющее устройство, ВВУ — вводно-выводные устройства, ВЗУ — внешние запоминающие устройства, УС-ПУУ — устройства связи с ПУУ,

УС-ВУ — устройства связи с внешними устройствами, УС-УК — устройства связи с другими УК, БОИ — блок обработки информации, ОЗУ — оперативное запоминающее устройство, Пр — процессор, ПУ — пульт управления, ПЗУ — постоянное запоминающее устройство.

матричный фазовый алгоритм память

Список используемой литературы Автоматическая коммутация. Учебник для вузов / Под ред. О. Н. Ивановой. — М.: Радио и связь, 1988, — 624 с.

Лазарев В.Г., Пийль Е. И., Турута Е. Н. Программное управление на узлах коммутации. — М.: Связь, 1978. — 264 с.

Тимин И. А. Методические указания и контрольные задания по курсу Техника микропроцессорных систем в коммутации. — М.: МТУСИ, 1999. — 32 с.