Механики
 Скачать 4.29 Mb.
|
|
1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ САНКТ - ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ , МЕХАНИКИ И ОПТИКИ Т . И . Алиев ОСНОВЫ МОДЕЛИРОВАНИЯ ДИСКРЕТНЫХ СИСТЕМ Учебное пособие Санкт - Петербург 2009 2 Алиев Т.И. Основы моделирования дискретных систем. – СПб: СПбГУ ИТМО, 2009. – 363 с. В пособии излагаются математические модели и результаты анализа дискретных систем различных классов с использованием аналитических, численных и имитационных методов исследования. В качестве моделей таких систем рассматриваются модели, построенные на основе систем и сетей массового обслуживания. Аналитические методы исследования базируются на аппарате теории массового обслуживания, численные – на аппарате теории марковских случайных процессов, статистические – на методах имитационного моделирования, которое реализуется в среде GPSS World. Материал пособия сопровождается многочисленными примерами, направленными на развитие навыков и умения применять простейшие модели и методы для исследования реальных систем. Особое внимание уделяется анализу и изучению свойств систем, представляемых моделями массового обслуживания. Пособие предназначено для студентов, обучающихся в области информационных технологий, а также для выпускников (бакалавров, магистрантов и специалистов) по направлению 230100 – «Информатика и вычислительная техника», подготавливающих выпускные квалификационные работы, в которых требуется выполнить моделирование и исследование системы с дискретным характером функционирования. Пособие может быть полезным для аспирантов и специалистов, выполняющих исследования реальных систем с использованием аналитических и имитационных методов моделирования. Рекомендовано к печати Советом факультета компьютерных технологий и управления 10 марта 2009 г., протокол № 8 ISBN 978-5-7577-0336-7 СПбГУ ИТМО стал победителем конкурса инновационных образовательных программ вузов России на 2007-2008 годы и успешно реализовал инновационную образовательную программу «Инновационная система подготовки специалистов нового поколения в области информационных и оптических технологий», что позволило выйти на качественно новый уровень подготовки выпускников и удовлетворять возрастающий спрос на специалистов в информационной, оптической и других высокотехнологичных отраслях науки. Реализация этой программы создала основу формирования программы дальнейшего развития вуза до 2015 года, включая внедрение современной модели образования. Санкт-Петербургский государственный университет информационных технологий, механики и оптики, 2009 Алиев Т.И., 2009 3 Введение «Даже если ваше объяснение настолько ясно, что исключает всякое ложное толко- вание, все равно найдется человек, который поймет вас неправильно» (Законы Мэрфи) Математическое моделирование является мощным и эффективным инструментом исследования разнообразных объектов, систем и процессов в различных областях человеческой деятельности. Многообразие процессов, протекающих в исследуемых системах и объектах, обусловливает и многообразие математических методов и средств, используемых в теории моделирования. Моделирование – сложнейший многоэтапный процесс исследования систем, направленный на выявление свойств и закономерностей, присущих исследуемым системам, с целью их создания или модернизации. В процессе моделирования решается множество взаимосвязанных задач, основными среди которых являются разработка модели, анализ свойств и выработка рекомендаций по модернизации существующей или проектированию новой системы. Большинство технических систем, в том числе вычислительные системы и сети, описываются в терминах дискретных случайных процессов с использованием вероятностных методов [1, 3, 9, 11]. При этом широкое применение находят математические модели, отражающие структурно-функциональную организацию исследуемых систем, построенные на основе моделей теории массового обслуживания, анализ которых может проводиться аналитическими, численными и статистическими методами. В качестве аналитических методов используются вероятностные методы теории массового обслуживания, в качестве численных – методы теории марковских случайных процессов, в качестве статистических – методы имитационного моделирования. При изложении аналитических методов расчёта автор, помня знаменитое высказывание, что «всякое уравнение длиной более двух дюймов, скорее всего, неверно», сознательно стремился использовать сравнительно простые математические зависимости, позволяющие рассчитывать, в первую очередь, основные характеристики функционирования систем, такие как нагрузку, загрузку и средние значения вероятностно-временных характеристик исследуемой системы. По той же причине в пособии отсутствуют громоздкие выводы и сложные доказательства представленных математических зависимостей, которые позволяют, с одной стороны, достаточно просто выполнить оценочные расчёты, не прибегая к сложным вычислениям, с другой стороны, получить вполне адекватное представление о свойствах соответствующих реальных систем за счёт детального их анализа. Наиболее важные и необходимые при решении многих задач формулы заключены в рамку. 4 Теоретический материал пособия сопровождается многочисленными примерами и задачами, которые направлены на развитие умения и навыков применять простейшие модели и методы для расчёта нагрузки и загрузки отдельных элементов и системы целом, для проведения анализа характеристик функционирования реальных систем, представляемых моделями массового обслуживания или моделями марковских случайных процессов. При решении задач следует иметь в виду, что при отсутствии каких- либо необходимых исходных данных могут и должны вводиться предположения и допущения, позволяющие решить (пусть и упрощённо) поставленную задачу. В пособии для более эффективного усвоения материала фрагменты, представляющие наибольший интерес, выделяются разными шрифтами, что позволяет акцентировать внимание читателя на тех или иных аспектах, которые, по мнению автора, являются важными для понимания описанных моделей и методов. Полужирный курсив выделяет наиболее важные и часто используемые термины и понятия, для которых дается чёткое определение или подробное описание. Полужирным шрифтом выделяются прочие общепринятые термины и понятия, часто встречающиеся в литературе и не имеющие чёткого определения, а также вспомогательные заголовки, названия и т.д. Курсив выделяет в тексте ключевые слова и фразы, на которые следует обратить внимание и которые раскрывают смысл излагаемого материала, а также выделяет термины и понятия, которые определены в других разделах. Какова цель данного пособия? Для кого оно предназначено, на какой круг читателей ориентировано? Ответы на эти вопросы определяют содержание и стиль изложения материала. Данное учебное пособие преследует две основные цели. 1. Дать неподготовленному читателю начальное представление о принципах моделирования сложных систем на примере широко используемых на практике моделей массового обслуживания и методов их расчёта с использованием трех основных подходов: аналитического, численного и имитационного. При этом излагаемый материал не должен содержать громоздкие математические выкладки и доказательства. Используемые математические выражения и формулы должны быть понятны любому техническому специалисту, имеющему базовую математическую подготовку в рамках среднего и высшего образования и самые общие представления о теории вероятностей, служащей математической основой излагаемого материала. 2. Предоставить читателю минимальный набор моделей, методов и средств для исследования несложных реальных систем в различных прикладных областях. Для достижения этой цели в пособии рассматривается большое количество примеров математических моделей, с 5 помощью которых иллюстрируется применение излагаемых аналитичес- ких, численных и имитационных методов расчёта. Для достижения сформулированных целей в пособии: • вводится четкая однозначная терминология, используемая в процессе изложения материала; • формируется представление о моделях массового обслужива-ния, их многообразии, а также о величинах, описывающих эти модели; • формулируются задачи моделирования как универсального инструмента исследования сложных систем, в том числе технических систем, таких как вычислительные машины, комплексы, системы и сети; • рассматриваются методы расчёта характеристик математи-ческих моделей, представляемых в виде систем и сетей массового обслуживания; • выполняется анализ свойств, и выявляются закономерности, присущие процессам, протекающим в моделях различных классов, а также анализируется влияние параметров модели на характеристики её функционирования. Структура учебного пособия. Пособие содержит 6 основных разделов, Заключительный раздел, Приложения, Список литературы и Алфавитный указатель. Материал каждого раздела разбит на параграфы, которые имеют двойную нумерацию. Некоторые параграфы разбиты на пункты с тройной нумерацией. Первый раздел содержит основные понятия и определения, касающиеся общих принципов моделирования, перечень параметров и характеристик дискретных систем, классификацию систем и моделей, краткую характеристику методов моделирования. Во втором разделе приводятся необходимые сведения из теории вероятностей и рассматриваются законы распределений случайных величин, наиболее часто используемые в теории массового обслуживания. В этот же раздел включён материал, связанный с аппроксимацией реальных распределений случайных величин, распределениями, представляющими собой комбинацию экспоненциальных распределений. В третьем разделе даются основные определения и понятия теории массового обслуживания, приводится классификация базовых моделей в виде систем массового обслуживания (СМО) и сетевых моделей в виде сетей массового обслуживания (СеМО), рассматриваются их параметры и характеристики. В четвёртом разделе излагаются аналитические методы расчёта простейших одноканальных и многоканальных СМО с однородным и неоднородным потоком заявок, а также линейных разомкнутых и замкнутых однородных экспоненциальных СеМО. В этом же разделе большое внимание уделяется анализу свойств исследуемых моделей, результаты которого позволяют выявить и сформулировать ряд важных особенностей и закономерностей, присущих процессам, протекающим в 6 системах. Выявленные свойства могут лечь в основу рекомендаций для проектирования подобных систем. Пятый раздел посвящен численным методам анализа моделей массового обслуживания с использованием аппарата теории марковских случайных процессов. Подробно рассматриваются примеры применения марковских случайных процессов для анализа СМО и СеМО с накопителями ограниченной ёмкости. Методам имитационного моделирования посвящен шестой раздел, в котором излагаются принципы имитационного моделирования и основы моделирования в среде GPSS World. Описание системы имитационного моделирования GPSS World содержит минимум информации, необходимой для построения простейших моделей массового обслуживания. В частности, из 53 операторов блока в этом разделе представлены менее половины, которые используются в рассматриваемых примерах имитационных моделей СМО и СеМО. Более полное и подробное описание системы имитационного моделирования GPSS World можно найти в специальной литературе по GPSS World [4], которая в последние годы представлена в достаточном объёме, и на сайте www.gpss.ru. Каждый раздел заканчивается тремя параграфами с одинаковыми названиями. 1. Резюме. Содержит краткое изложение представленного в разделе материала. 2. Практикум. Содержит обсуждение актуальных и наиболее часто задаваемых вопросов по изложенному материалу, а также подробные решения в качестве примеров наиболее интересных задач. 3. Самоконтроль. Содержит перечень тестовых вопросов и задач, позволяющих читателю самостоятельно выполнить проверку степени усвоения изложенного материала и закрепить полученные знания в процессе решения предлагаемых задач. Заключительный раздел является итоговым, в котором излагаются основные принципы моделирования как систематизированная последова- тельность этапов, методови средств по организации процесса моделирования. Некоторые разделы, параграфы и пункты пособия предваряются цитатами из законов Мэрфи, что, по мнению автора, возможно, позволит акцентировать внимание читателя и подтолкнуть его к критическому осмыслению излагаемого материала. В Приложениях представлены аббревиатуры, основные обозначения, используемые в пособии, а также приведён перечень вопросов, обсуж- даемых в основных разделах пособия. В конце пособия имеется Предметный указатель со ссылками на страницы, содержащие определения основных терминов и понятий, используемых в учебном пособии. Представленный Список литературы не претендует на полноту и содержит ограниченный перечень литературных источников, которые в 7 той или иной мере использовались при написании пособия. Этот перечень включает только учебные пособия и монографии, которые условно можно разбить на три группы, содержащие материал: • по теоретическим вопросам моделирования и математическим методам исследования систем и сетей массового обслуживания [2, 5, 6, 8, 12, 13, 17]; • по применению моделей и методов теории массового обслуживания для исследования вычислительных систем и сетей [1, 3, 9- 11, 14-16]; • по имитационному моделированию систем и сетей массового обслуживания и описанию системы имитационного моделирования GPSS World [4, 7, 18]. Пособие предназначено, прежде всего, для студентов, обучающихся по направлению «Информатика и вычислительная техника», изучающих дисциплину «Моделирование» и связанные с ней дисциплины, а также для выпускников (бакалавров, магистрантов и специалистов), подготавливаю- щих выпускные квалификационные работы, в которых требуется выполнить моделирование и исследование некоторой системы, например, компьютерной сети или её фрагмента – вычислительной системы (сервера), узла или канала передачи данных. Пособие может быть полезным в качестве введения в проблематику моделирования дискретных систем со стохастическим характером функционирования для магистрантов, аспирантов и специалистов, выполняющих исследования реальных систем с использованием аналитических и имитационных методов математического моделирования. Автор, понимает, что, как и «в любой хорошо отлаженной программе всегда есть хотя бы одна ошибка», так и в любой многократно вычитанной книге она также наверняка присутствует. Посему автор будет благодарен за все присланные по адресу aliev@d1.ifmo. ru обнаруженные ошибки и опечатки, а также критические замечания. 8 Раздел 1. Общие вопросы моделирования Раздел 1. ОБЩИЕ ВОПРОСЫ МОДЕЛИРОВАНИЯ «Все, что хорошо начинается, кончается плохо. Все что начинается плохо, кончается еще хуже» (Закон Паддера) Моделирование – замещение одного исходного объекта другим объектом, называемым моделью (рис.1.1), и проведение экспериментов с моделью с целью получения информации о системе путем исследования свойств модели. Объектами моделирования в технике являются системы и протекаю- щиев них процессы. В частности, в вычислительной технике объектами моделирования являются вычислительные машины, комплексы, системы и сети. При этом, наибольший интерес представляют конструктивные модели, допускающие не только фиксацию свойств (как в произведениях искусств), но и исследование свойств систем (процессов), а также решение задач проектирования систем с заданными свойствами. Моделирование предоставляет возможность исследования таких объектов, прямой эксперимент с которыми: • трудно выполним; • экономически невыгоден; • вообще невозможен. Моделирование – важнейшая сфера применения вычислительных систем и сетей в различных областях науки и техники: в математике и физике, в авиа- и автомобилестроении, в приборо- и машиностроении, в оптике, в электронике и т.д. Все более широкое распространение модели- рование находит в таких областях как экономика, социология, искусство, биология, медицина и т.п. В то же время, вычислительные системы и сети сами являются объектами моделирования на этапах проектирования новых и модернизации существующих систем, анализа эффективности использо- вания систем в различных условиях (например, в экстремальных ситуаци- ях, в условиях повышенных требований к надежности и живучести). При- менение моделирования на этапе проектирования позволяет выполнить анализ различных вариантов предлагаемых проектных решений, опреде- лить работоспособность и оценить надежность системы, выявить узкие места и мало загруженные ресурсы, а также сформулировать рекоменда- Рис.1.1. К понятию «моделирование» ИСХОДНЫЙ ОБЪЕКТ (система, процесс) МОДЕЛЬ Раздел 1. Общие вопросы моделирования 9 ции по рациональному изменению состава и структуры или способа функциональной организации системы. 1.1. Система 1.1.1. Понятия системы и комплекса «Усложнять - просто, упрощать – сложно» (Закон Мейера) Система (от греч. systema – целое, составленное из частей; соедине- ние) – совокупность взаимосвязанных элементов, объединенных в одно це- лое для достижения некоторой цели, определяемой назначением системы. |