Дисциплина Моделирование элементов вс

Министерство Общего и Профессионального Образования РФ
Ульяновский Государственный Технический Университет
Кафедра Вычислительная Техника

Дисциплина Моделирование

Моделирование элементов ВС

Выполнили:

Новичков К.В.

Сидоров А.С.

Руководитель:

Куцоконь Н. С.

Ульяновск 2002

Моделирование

Модель – это физическая или абстрактная система, адекватно представляющая собой объект исследования.

Физические модели образуются из совокупности материальных объектов. Для их построения используются различные свойства, причем природа применяемых в модели материальных элементов не обязательно та же, что и в исследуемом объекте. Примером физической модели является макет.

Абстрактная модель – это описание объекта исследования на некотором языке. Абстрактность модели проявляется в том, что её компонентами являются понятия, а не физические элементы,(например: словесные описания, чертежи, схемы, графики, таблицы, программы, алгоритмы, математические описания).

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

Понятие адекватности - весьма широкое и основывается на строгих в математическом отношении понятиях изоморфизма и гомоморфизма.

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

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

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

Имитационная модель – это описание объекта на некотором языке. Составными частями имитационной модели являются описания: элементов, образующих систему, структуры системы, то есть совокупности связей между элементами, свойств среды в которой функционирует исследуемая система. Эта информация в целом имеет логико-математический характер и представляется в форме совокупности алгоритмов, описывающих функционирование исследуемой системы. Программа, построенная на основе этих алгоритмов, позволяет получить информацию о поведении исследуемой системы. Таким образом, в качестве имитационной модели выступает программа для ЭВМ, а имитационное моделирование сводится к проведению экспериментов с моделью путем прогонов программы на некотором множестве данных.

Имитационные модели, используемые при исследовании ВС, обычно имеют вероятностную природу. Моделирование вероятностных процессов основывается на методе статистических испытаний (методе Монте - Карло). По этой причине имитационное моделирование часто называют статистическим моделированием, хотя в большинстве имитационных моделей метод статистических испытаний сочетается с вычислениями по детерминированным зависимостям.

При имитационном моделировании описания объектов исследования имеют алгоритмический характер, а сами модели – суть программы для ЭВМ. Поэтому такое моделирование иногда называют алгоритмическим.

Главная особенность данного подхода к моделированию заключается в том, что используемые для построения модели алгоритмические языки – гораздо более гибкое и доступное средство описания сложных систем, нежели язык математических функциональных соотношений. Благодаря этому в имитационных моделях сложных систем находят отражение многие детали их структуры и функции, которые вынужденно опускаются или непроизвольно утрачиваются в математически строгих моделях. Свойственная имитационным моделям реалистичность основывается на использовании для их построения всех имеющихся представлений об объекте исследования как теоретического, так и эвристического характера. Позитивное свойство статистического моделирования – универсальность, гарантирующая принципиальную возможность анализа систем любой степени сложности с любой степенью детализации изучаемых процессов. Негативное свойство статистического моделирования – трудоёмкость процесса моделирования, то есть необходимость выполнения очень большого количества операций над числами, и частный характер результатов, не раскрывающий зависимости, а лишь определяющий её в отдельных априорно назначенных точках.

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

Так как моделирующий процесс носит абстрактный характер, нельзя описать какие-либо формальные правила или алгоритмы построения моделей. Для одного конкретного объекта можно построить несколько разных моделей, каждая из которых будет "правильной" в том смысле, что её внешнее поведение совпадает с поведением моделируемого объекта. В исследовании объекта или системы нас прежде всего интересует, каким образом она выполняет свои функции, то есть выполняет некоторую работу. Поэтому построение модели включает две задачи: описание условий работы системы и описание операций, выполняемых системой в заданных условиях. Первая задача неизмеримо сложнее, чем вторая.

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

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

Модели вычислительных процессов и оценка трудоемкости алгоритма.

Трудоемкость алгоритмов – количество вычислительной работы требуемой для реализации алгоритма.

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

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

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

В первом приближении трудоемкость алгоритма можно охарактеризовать следующей совокупностью параметров:

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

N₁,N₂,…,N_n - среднее количество обращений к файлам F₁,F₂,…,F_n соответственно за одну реализацию алгоритма;

Q₁,Q₂,…,Q_n – среднее количество информации (байтов) передаваемые за одно обращение к фалам F₁,F₂,…,F_n соответственно.

Значение В характеризует трудоемкость обработки информации (счета), а значения N₁,N₂,…,N_n, Q₁,Q₂,…,Q_n – трудоемкость процесса ввода-вывода информации. При решении задач анализа и синтеза вычислительных систем возникает необходимость в описании свойств вычислительных процессов, порождаемых алгоритмами решения задач. С наибольшей полнотой и точностью свойства вычислительных процессов представляются самими алгоритмами, определяющими вычислительные процессы до мельчайших подробностей. Однако при решении задач теории вычислительных систем интерес представляют не все без исключения детали вычислительных процессов, а только те, которые характеризуют порядок использования ресурсов системы в процессе решения задач.

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

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

Вычислительные процессы, порождаемые моделью, должны соответствовать реальным процессам с точностью до совпадения, по крайней мере, математических ожиданий их одноименных характеристик.

Первые два требования выделяют круг сведений о вычислительных процессах, наиболее существенно влияющих на порядок функционирования ВС. На данном уровне рассмотрения вопросов прочие сведения о вычислительных процессах не принимаются во внимание, т.е. алгоритмы и вычислительные процессы считаются различными постольку, поскольку они различаются по количеству и характеру запросов на обслуживание. Необходимость третьего требования продиктована результативностью вероятностного подхода к исследованию многообразных процессов, какими являются вычислительные процессы. Фактор случайности, вводимый в модель, позволяет порождать бесконечное число реализаций вычислительного процесса, что характерно для процессов выполнения алгоритма. Последнее требование определяет минимальную норму «точности» модели. Конечно, идеальная модель должна представлять реальные процессы с точностью до равенства распределений соответствующих случайных величин описывающих вычислительные процессы. Однако от построения идеальной модели приходится отказаться по следующим причинам:

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

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

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

Область программы имеет емкость, достаточную для размещения, подмножества загрузочных модулей, которые должны одновременно присутствовать в оперативной памяти в процессе решения задачи. Здесь мы рассмотрим наиболее частый и общий случай, когда программа не может быть целиком размещена в оперативной памяти из-за ограниченной емкости последней. В этом случае программа разделяется на так называемые загрузочные модули m₀,m₁,m₂…, которые хранятся во внешней памяти как записи m₀,m₁,m₂…, составляющие файл F1, называемый главным файлом.

Файл - упорядоченная совокупность данных, обрабатываемых одним общим для этих данных способом. Файл разделяется на записи.

Запись – совокупность единиц информации (байтов) обрабатываемых совместно как одно целое.

Данные, связанные с задачей, разделяются на файлы F₂,F₃,…, которые в свою очередь разделяются на записи a₁,a₂,…,b₁,b₂,…,c₁,c₂,…

В зависимости от способа использования данных в процессе решения задачи различают входные, выходные и входные - выходные файлы.

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

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

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

Задача начинает выполняться с момента загрузки в оперативную память корневого (ведущего) модуля m₀ и передачи ему управления. В некоторый момент времени модуль m₀ может вызвать в оперативную память модуль m_, который в свою очередь обратиться к модулю m_ и т.д. В результате этого в области программы могут одновременно размещаться несколько модулей m₀, m_,…, m_. После завершения работы модуль m_ передает управление вызвавшему его модулю и область памяти, занимаемая модулем m__, считается свободной и в нее может быть вызван очередной модуль. Т.о. в каждый момент времени в оперативной памяти, присутствует лишь часть модулей, входящих в состав программы.

В области данных выделяется подобласть Д в которой размещаются данные, в основном постоянно используемые в процессе решения задачи. Доступ к данным, размещенным в файлах F2,F3,F4 организуется путем, выделения областей оперативной памяти a_i,b_j,c_k называемых буферами ввода-вывода. Каждый из буферов обеспечивает размещение, по крайней мере, одной записи из соответствующего файла. Буфер a_i обслуживающий входной файл F2 используется для хранения записи a_i. Запись вызывается в буфер командами ввода-вывода, после чего данные, включенные в эту запись, становятся доступными для обработки. Аналогично, результаты, формируемые программой, заносятся в область буфера c_k и по мере формирования записей переносятся в выходной файл F4.

П
m₁
еред выполнением программы корневой модуль m₀ загружается в начало раздела, выделенного задаче. Программа инициируется путем передачи управления первой команде корневого модуля. Начиная с этого момента, выполнение программы может протекать в соответствии со следующей временной диаграммой:

Отрезки на осях времени t обозначает периоды активного состояния процессов обработки C и обращения к файлам F1,F2,F3,F4.

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

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

раздел Р оперативной памяти ОП;
пакет магнитных дисков НМД1 для хранения загрузочных модулей программы, т.е. файла F1;
устройство ввода с перфокарт ПК, с которого вводится входной файл F2;
пакет магнитных дисков НМД2 для хранения рабочего файла F3;
магнитную ленту НМЛ, на которую записывается выходной файл F4;
процессор Пр, выполняющий команды программы.

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

Будем рассматривать вычислительный процесс, как последовательность этапов счета и ввода-вывода информации при обращении к файлам F₁…F_H как это показано на приведенной ранее временной диаграмме. Состояние вычислительного процесса, соответствующее этапу счета, обозначим символом S₀, обращениям к файлам F₁…F_H – символами S₁…S_H. Окончание вычислительного процесса будем рассматривать как переход процесса в состояние S_H₊₁ поглощающее вычислительный процесс. В этих обозначения вычислительный процесс – это последовательность состояний S_t₀,S_t₁,…,S_tm, изменяющихся в моменты времени t_o,t₁,…,t_m, причем

и заключительное состояние процесса

следующая страница >>