Упрощение логической схемы алгоритма
Московский технический университет
связи и информатики
Контрольная работа
по дисциплине Техника
микропроцессорных систем в коммутации
Москва 2015 г.
Задача 1.
По заданной в таблице 1 логической схеме алгоритма (ЛСА0 необходимо:
1) построить граф-схему алгоритма ГСА;
2) получить матричную схему алгоритма МСА;
) получить схему формул переходов ФП и упростить ЛСА;
4) записать
упрощенную ЛСА ;
) доказать
эквивалентность ЛСА и ,
вычислив значение ЛСА на всех наборах значений логических условий;
) по
заданному в таблице 1 распределению сдвигов упростить ЛСА и
получить ЛСА ;
) используя
заданную в таблице 1 ЛСА ,
объединить частные ЛСА и в общую
ЛСА , где .
Номер варианта определяется последней цифрой номера студенческого билета.
Таблица 1
|
Распределение сдвигов
|
|
|
, ,
|
|
Решение:
1. Построим граф-схему алгоритма ГСА по ЛСА:
2. Получим матричную схему алгоритма МСА:
Рис.
1
3. Получим систему формул переходов ФП и упростим ЛСА.
φ 1
Все
формулы переходов входящие в систему являются элементарными и поэтому не
упрощаются. Невозможность упрощения ЛСА видна и по ГСА, так как алгоритм
достаточно простой.
.
Используя заданную ЛСА , объединить частные ЛСА 1 и в общую ЛСА , где
Матричная
схема алгоритма у нас уже есть.
Получим
матричную схему алгоритма .
По
частным МСА составим объединенную .
Чтобы
различить принадлежность определенного перехода, логическое выражение умножаем на определяющую функцию “r”, а
для на определяющую функцию “”.
φ 0
Преобразуем
общую ЛСА .
φ 0
На
рисунке 2 покажем наглядно полученную ЛСА с помощью ГСА.
Рис.
2
Задача
2
Дано:
Таблица 2 Отношение 1: R_Абонент
1
Код
|
Тип абонента
|
Абонентский номер
|
Тип комплекта для набора
номера
|
1
|
Оператор
|
2400011
|
PBR
|
2
|
Оператор
|
2400012
|
PBR
|
Аналоговый абонент
|
2403769
|
PBR (многочастотный)
|
4
|
Аналоговый абонент
|
2403771
|
PBR
|
5
|
Цифровой абонент
|
2402750
|
Комплект набора
|
Таблица 3 Отношение 2: R_Абонент
2
Код
|
Тип абонента
|
Абонентский номер
|
Тип комплекта для набора
номера
|
1
|
Оператор
|
2400011
|
PBR
|
2
|
Оператор
|
2400012
|
PBR
|
6
|
Оператор
|
2400013
|
PBR
|
7
|
Оператор
|
2400014
|
PBR
|
8
|
Оператор
|
2400015
|
PBR
|
Выполняемая операция: “Пересечение”.
Требуется:
Выполнить заданную операцию над заданными отношениями базы данных.
Результат выполнения представить в виде соответствующего отношения.
Решение:
Результат пересечения содержит только те кортежи первого отношения,
которые есть во втором.
Таблица 4
Код
|
Тип абонента
|
Абонентский номер
|
Тип комплекта для набора
номера
|
1
|
Оператор
|
2400011
|
PBR
|
2
|
Оператор
|
2400012
|
PBR
|
Задача 3.
Разместить N страниц
виртуальной памяти в оперативном запоминающем устройстве (ОЗУ) и во внешних
запоминающих устройствах (ВЗУ) ЭУС при наличии:
S0 свободных сегментов в ОЗУ,
SД свободных сегментов в накопителе на магнитных дисках
(НМД),
SЛ свободных сегментов в накопителе на магнитных лентах
(НМЛ).
А
также составить таблицу страниц с указанием доступности страниц при заданной
активности страниц.
Показать
на рисунке принцип взаимосвязи страниц виртуальной памяти с сегментами ОЗУ и
ВЗУ через таблицу страниц.
Дано:
Таблица 5
Число страниц N
|
Число свободных сегментов в
ОЗУ, S0
|
Число свободных сегментов
НМД, Sд
|
Число свободных сегментов в
НМЛ, Sл
|
Значение параметра
активности (αi)
группы из ni страниц
|
7000 1500 2500 8000
Для того чтобы сопоставить виртуальному адресу страницы физический адрес
сегмента того или иного ЗУ на данный момент работы ЭУМ, в ОЗУ машины постоянно
хранится так называемая таблица страниц.
Составим таблицу страниц с указанием доступности страниц при заданной активности.
Таблица 6
Номер страницы
|
Номер сегмента
|
Доступность страницы
|
Параметр активности страницы
|
0149901499125
|
|
|
|
1500249915002499018
|
|
|
|
2500399925003999012
|
|
|
|
4000549940005499010
|
|
|
|
55006999550069990< 5
|
|
|
|
Покажем на рисунке 3 принцип взаимосвязи страниц виртуальной памяти с
сегментами ОЗУ и ВЗУ через таблицу страниц.
Страницы с наибольшей активностью размещены в ОЗУ. Те страницы, которые
не разместились в ОЗУ, размещены в ВЗУ. При этом в сегменты, находящиеся в НМД,
размещены оставшиеся после размещения в ОЗУ страницы с большей активностью, так
как НМД имеет большее быстродействие, чем НМЛ, и при наличии трехуровневой
иерархии памяти ЭУМ информация из НМД поступает непосредственно в ОЗУ, а из НМЛ
в ОЗУ поступает через НМД.
Рис. 3
Для простоты на рисунке указаны не страницы и сегменты, а группы страниц.
Задача 4.
Изобразить структурную схему централизованной неоднородной
многопроцессорной ЭУМ
Структурная схема централизованной неоднородной многопроцессорной ЭУМ
показана рисунке 4,
Рис. 4
где УК - узел коммутации,
ПУУ - периферийные управляющие устройства,
ЦБУ - центральное управляющее устройство,
ВВУ - вводно-выводные устройства,
ВЗУ - внешние запоминающие устройства,
УС-ПУУ - устройства связи с ПУУ,
УС-ВУ - устройства связи с внешними устройствами,
УС-УК - устройства связи с другими УК,
БОИ - блок обработки информации,
ОЗУ - оперативное запоминающее устройство,
Пр - процессор,
ПУ - пульт управления,
ПЗУ - постоянное запоминающее устройство.
матричный фазовый алгоритм память
Список используемой литературы
1.
Автоматическая
коммутация. Учебник для вузов / Под ред. О. Н. Ивановой. - М.: Радио и связь,
1988, - 624 с.
2.
Лазарев В.Г.,
Пийль Е.И., Турута Е.Н. Программное управление на узлах коммутации. - М.:
Связь, 1978. - 264 с.
3.
Тимин И.А.
Методические указания и контрольные задания по курсу Техника микропроцессорных
систем в коммутации. - М.: МТУСИ, 1999. - 32 с.