tehnologia (1018792), страница 26
Текст из файла (страница 26)
5.9, а). На однопроцессорных компьютерах в мультипрограммных средах в этом случаеначинается попеременное выполнение соответствующих программ. Параллельные процессыбывают синхронные и асинхронные. Для синхронных процессов определяют точкисинхронизации - моменты времени, когда производится обмен информацией149между процессами. Асинхронные процессы обмениваются информацией только в моментактивизации параллельного процесса.Под вызовом сопрограммы понимают возможность поочередного выполнения двуходновременно запущенных программ, например, если одна программа подготовила пакетданных для вывода, то вторая может ее вывести, а затем перейти в состояние ожиданияследующего пакета. Причем в мультипрограммных системах основная программа, передавданные, продолжает работать, а не переходит в состояние ожидания, как изображено нарис.
5.9.150Если стрелка, изображающая вызов, касается блока, то обращение происходит к модулюцеликом, а если входит в блок, то - к элементу внутри модуля.При необходимости на структурной карте можно уточнить особые условия вызова (рис.5.10): циклический вызов, условный вызов и однократный вызов - при повторном вызовеосновного модуля однократно вызываемый модуль не активизируется.Связи по данным и управлению обозначают стрелками, параллельными дуге вызова,направление стрелки указывает направление связи (рис.
5.11).Структурные карты Константина позволяют наглядно представить результатдекомпозиции программы на модули и оценить ее качество, т. е. соответствиерекомендациям структурного программирования (сцепление и связность).Пример 5.2. Представим в виде структурной карты Константайна полную структурнуюсхему, полученную в предыдущем примере (см. рис. 5.6).Подпрограммы Очистка окна,Выводпрямоугольника,Выводстроки текста, Вывод отрезка прямой,Задание цвета рисования и Заданиецветафонаявляютсячастьюбиблиотеки графических примитивовпрактическивлюбойсредепрограммированияуниверсальногоязыка, поэтому их включать вструктурную карту не будем.Для остальных подпрограммпокажем особые условия вызова итипы связей (рис.
5.12).151Модули Расчет значений функции, Вывод таблицы и Построение графика связаны сосновной программой по образцу, так как параметры X и Y структурные (массивы),следовательно программа считается сцепленной по образцу.Анализ показывает, что количество сцеплений по образцу в программе можноуменьшить, если подпрограмму Расчет значений функции перенести на следующий уровень(рис.
5.13). Однако в этом случае при смене вида результата таблица значений будетрассчитываться заново.Аналогично можно перенести подпрограмму Разбор функции на более низкий уровень ивызывать ее, например, из подпрограммы Расчет значений функции, но поскольку великавероятность многократного вычисления значений одной функции на разных интервалах, врядли это целесообразно.152После внесения соответствующих изменений в алгоритм следует определить полнуюспецификацию модулей.
Спецификация должна включать: имя, краткое описание назначения,перечень входных и выходных параметров с указанием типа и области допустимых входных ивыходных значений. Затем можно приступать к реализации модулей.В соответствии с требованиями нисходящей разработки (комбинированный подход)можно предложить следующий порядок реализации модулей:• Основная программа,• Вывод окна с текстом,• Вывод заголовка и меню,153• Разбор функции,• Вычисление значений функции,• Вывод таблицы,• Расчет значений функции,• Построение графика.Структурные карты Джексона будут рассмотрены вместе с предложенной им методикойпроектирования программ, основанной на декомпозиции данных в § 5.5.5.4.
Проектирование структур данныхПод проектированием структур данных понимают разработку их представлений впамяти. Основными параметрами, которые необходимо учитывать при проектированииструктур данных, являются:• вид хранимой информации каждого элемента данных;• связи элементов данных и вложенных структур;• время хранения данных структуры («время жизни»);• совокупность операций над элементами данных, вложенными структурами иструктурами в целом.Вид хранимой информации определяет тип соответствующего поля памяти. В качествеэлементов данных в зависимости от используемого языка программирования могутрассматриваться:• целые и вещественные числа различных форматов;• символы;• булевские значения: true и false;а также некоторые структурные типы данных, например:• строки;• записи;• специально объявленные классы.При этом для числовых полей очень важно правильно определить диапазон возможныхзначений, а для строковых данных - максимально возможную длину строки.Связи элементов и вложенных структур, а также неустойчивость и совокупностьопераций над элементами и вложенными структурами определяют структуры памяти,используемые для представления данных.
Время жизни учитывают при размещении данных встатической или динамической памяти, а также во внешней памяти.Рассмотрим существующие варианты внутреннего представления данных, их элементови связей между ними более подробно.Представление данных в оперативной памяти. Различают две базовые структурыорганизации данных в оперативной памяти: векторную и списковую.154Векторная структура представляет собойпоследовательность байт памяти, которыеиспользуются для размещения полей данных(рис. 5.14). Последовательное размещениеорганизованных структур данных позволяетосуществлять прямой доступ к элементам: поиндексу (совокупности индексов) - в массивахили строках или по имени поля - в записях илиобъектах.Однако выполнение операций добавления и удаления элементов при использованиивекторных структур для размещения элементов массивов может потребовать осуществлениямногократных сдвигов элементов.Структуры данных в векторном представлении можно размещать как в статической, таки в динамической памяти.
Расположение векторных представлений в динамической памятииногда позволяет существенно увеличить эффективность использования оперативной памяти.Желательно размещать в динамической памяти временные структуры, хранящиепромежуточные результаты, и структуры, размер которых сильно зависит от вводимых исходных данных.Списковые структуры строят из специальных элементов, включающих помимоинформационной части еще и один или несколько указателей - адресов элементов иливложенных структур, связанных с данным элементом.
Размещая подобные элементы вдинамической памяти можно организовывать различные внутренние структуры (рис. 5.15).155Однако при использовании списковых структур следует помнить, что:• для хранения указателей необходима дополнительная память;• поиск информации в линейных списках осуществляется последовательно, а потомутребует больше времени;• построение списков и выполнение операций над элементами данных, хранящихся всписках, требует более высокой квалификации программистов, более трудоемко, асоответствующие подпрограммы содержат больше ошибок и, следовательно, требуют болеетщательного тестирования.Обычно векторное представление используют для хранения статических множеств,таблиц (одномерных и многомерных), например, матриц, строк, записей, а также графов,представленных матрицей смежности, матрицей инцидентности или аналитически [55].Списковое представление удобно для хранения динамических (изменяемых) структур иструктур со сложными связями.В наиболее ответственных случаях при выборе внутреннего представления целесообразноопределять вычислительную сложность [24, 55] выполнения наиболее часто встречающихсяопераций со структурой данных или ее элементами для различных вариантов.
А такжеоценивать их емкостную сложность.Пример 5.3. Разработать внутреннее представление неориентированного графа, надкоторым в основном выполняют операции определения смежности вершин, определениявершин, смежных данной, и удаления вершины.В [27, 55] предложены 10 вариантов внутреннего представления неориентированногографа, приведенного на рис.
5.16, а. Причем представление в виде матрицы смежности (рис.5.16, б) использует табличный способ описания связности вершин. Комбинации векторови односвязных списков (рис. 5.16, в-г) реализуют аналитическое задание графа, а вектор исписок n-связных списков напрямую отображают связи вершин. Интересно также, чтоструктуры, изображенные на рис. 5.16. б, в и д, могут быть размещены в статической памяти.Для выбора структуры необходимы исследования. В табл. 5.2 приведены результатырасчета временной сложности указанных операций на уровне машинных команд в тактахмикропроцессора для каждого представления и емкостной сложности этих представлений.(Оценка временной сложности выполнялась по методике, предложенной в [27, 55].)Анализ результатов показывает, что, если число вершин n < 100, то с точки зренияуменьшения времени выполнения наиболее эффективное представление - массив списков.Если же существенно экономное использование оперативной памяти, то наиболееэффективное представление - массив динамических векторов.Представление данных во внешней памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
