Министерство образования Республики Беларусь

Брестский государственный технический университет

Кафедра ИИТ

Пояснительная записка

к курсовой работе

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

Моделирование системы заданной конфигурации

Выполнил:

Студент 4 курса ФЭИС

группы АСОИ-552

Мелех Н.Н.

Брест 2009

СОДЕРЖАНИЕ

Введение

1.Построение концептуальной модели (км)

2. Разработка математической модели

3. Разработка gpss-ориентированной имитационноймодели

4. Разработка, реализация и исследование упрощенных моделей

5. Реализация и исследование имитационной модели

6. Исследование свойств системы

заключение

литература

ВВЕДЕНИЕ

Задан объект моделирования - некая система, назначение которой – выполнение некоторых действий над поступающими заданиями из одного модуля и передача обработанного результата в другой модуль. Структура эти двух модулей нас не интересует, и мы будем рассматривать их в дальнейшем как «черные» ящики, один из которых посылает в систему задания с интенсивностью l, т.е. является генератором, а другой - принимает обработанные задания, т.е. является приемником.

Цели исследования системы заключаются в следующем:

· выявить «узкие» места системы;

· для известной интенсивности поступления заданий в систему подобрать такие ее параметры, чтобы обеспечивалась оптимальная загрузка всех устройств;

· определить влияние производительности каждого элемента системы на ее общую производительность;

· спрогнозировать реакцию системы при изменении интенсивности поступления заданий на обслуживание.

Анализ этих характеристик позволяет выбрать оптимальные параметры системы (производительность всех устройств) и таким образом решить очень важную задачу: спроектировать систему с минимальными финансовыми затратами.

Для исследования системы всегда строится ее модель и производится моделирование. Модели можно разделить на несколько категорий:

- наглядные;

- символические;

- математические.

Наглядные и символические модели применяются на начальных стадиях моделирования, когда идет сбор информации об объекте моделирования. Математическая модель применяется, когда объект моделирования описывается с помощью математического аппарата.

1. ПОСТРОЕНИЕ КОНЦЕПТУАЛЬНОЙ МОДЕЛИ ( КМ )

Требуется разработать и исследовать модели системы. Тип модели - Q-схема. Модели транзактные. Способы расчета - имитационный (в среде GPSSWorld на языке GPSS) и аналитический.

Система состоит из устройств S1-S3, памяти S5 и S6.

Внешняя среда представлена источником запросов (узел S0), приемником обслуженных запросов (узел S4).

Число типов потоков запросов Q – 2 (50% заявок первого и 50% второго типа). Потоки различаются параметрами законов поступления и обслуживания. Законы поступления запросов 1 и 2 типов соответственно – Эрланга и равномерный. Законы обслуживания 1 и 2 типов соответственно – равномерные.

При появлении запроса ему выделяется место в памяти S5, при нехватке в памяти S6 и далее начинается обслуживание в S1. Иначе происходит отказ в обслуживании. Освобождается память по завершении обслуживания в системе. Потребность в памяти запросов 1 и 2 типа описывается разными дискретными равномерными законами (от 1 до x единиц).

Порядок движения запросов в процессе обслуживания представлен матрицей переходов P (где число – вероятность выбора маршрута) (таблица 1.1).

Таблица 1.1- Исходнаяматрицапереходов P

Параметры устройств и параметров потоков запросов (заявок) указаны в таблице 2.

Таблица 1.2- Параметры системы

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

Для этого анализируем матрицу Р. Полученные результаты наносим на схему (рисунок 1, 2).

Рисунок 1.1- Ресурсы системы.

Рисунок 1.2- Общая (исходная) схема Q-модели.

Основные обслуживающие ресурсы системы – устройства, памяти, накопители и т.д.

Для заданной системы .

Здесь ресурсы: - устройства S₁ , S₂ , S₃ , память S₅ ,S₆ .

Состав узлов:

S₀ - источник запросов (генератор);

S_{1 -} устройство с обслуживанием в одном из 4 -х каналов;

S_5-6,1 , - узел выделения памяти S₅ или S₆ (анализ наличия и выделение). Потребность в памяти запросов 1 и 2 типа описывается разными дискретными равномерными законами (от 1 до x единиц). S_{3 -} устройство с обслуживанием в одном из 2-х каналов;

S₂ , S_{3 -} устройство с обслуживанием в одном канале;

S_5-6,2 - узел (фаза) освобождения ранее занятой емкости памяти S₅ или S₆ ;

S₄ – приемник обслуженных запросов;

Параметры обслуживающих узлов представлены ниже в таблице 1.3.

Таблица 1.3.- Параметры обслуживающих узлов

В системе по условию обрабатывается два потока заявок с похожими маршрутами обработки, движения, но с разными законами, параметрами поступления и обслуживания. Обозначим потоки номерами – 1 и 2. Тогда множество потоков Q = {1; 2}. Мощность множества Q = 2.

Потоки отличаются вероятностным характером, стационарны. Соответственно для каждого потока надо определить, конкретизировать следующие законы (распределения):

1. Законы поступления транзактов 1и 2 типов соответственно – Эрланга и равномерный.

где:

λ– интенсивность поступления заданий для каждого из двух потоков.

λ^{(1 )} =0,004;

Равномерный:

Распределение задается двумя параметрами: a – левая граница, b – правая граница (b > a).

2. закон обслуживания транзактов 1и 2 типов равномерные;

0, t<a

S⁽¹⁾ (t)= , a ≤t≤b

1, t>b,

Уточняем схему модели

В моделируемой системе (см. рисунок 1.2):

- после узла S₀ нужен добавочный узел S₇ анализа наличия свободной емкости памяти S₅ для пришедшей заявки и выбора дальнейшего маршрута движения запроса – в память на узелS_{5,1 .}

- соответственно необходим узел S₈ анализа наличия свободной емкости памяти S₆ для пришедшей заявки и выбора дальнейшего маршрута движения запроса – в память на узелS_6,1 или в приемник отказанных заявок.

- соответственно необходим узелS₉ - приемник заявок, не вошедших в систему из-за нехватки памяти;

- после выхода из узлаS₂ дальнейший маршрут заявки определяется вероятностным выбором из двух альтернатив – необходим узел S₁₀ ,“разыгрывающий” для каждой пришедшей заявки выбор маршрута в соответствии с заданными вероятностями.

- после выхода из узлаS₃ необходим узел S₁₁ анализа дальнейший маршрут заявки определяется вероятностным выбором из двух альтернатив – необходим узел S₁₀ ,“разыгрывающий” для каждой пришедшей заявки выбор маршрута в соответствии с заданными вероятностями.

Уточненная схема модели безотносительно к потокам приведена на рисунке 1.3.

Рисунок 1.3- Уточненная схема Q-модели.

В соответствии с данными, полученными на предыдущем этапе, уточняем матрицу переходов.

Порядок движения запросов в процессе обслуживания представлен ниже матрицей переходов P.

Таблица 1.4- Уточненная матрица переходов P

Уточняем ранее полученные схемы Q-моделей (см. рисунок 1.3) с учетом наличия разных потоков заявок.

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

Отличие состоит в параметрах законов поступления (нужны два разных источника, т.е. узел S₀ заменяем на S_0,1 , S_0,2 , или здесь на S⁽¹⁾ ₀ и S⁽²⁾ ₀ ).

Соответственно нужны разные приемники обслуженных и отказанных заявок – новые узлы S⁽¹⁾ ₄ , S⁽²⁾ _{4 ,} S⁽¹⁾ ₉ , S⁽²⁾ _{9 .}

Отличие состоит также в параметрах законов обслуживания в устройствах и характере распределения ёмкости памяти.

Тогдановыйсоставузлов

S = {S⁽¹⁾ ₀ ,S⁽²⁾ ₀ , S₁ , S₂ , S₃ , S₄ , S_5,1 , S_5,2 , S_6,1 , S_6,2 , S₇ , S_{8 ,} S⁽¹⁾ ₉ , S⁽²⁾ _{9 ,} S₁₀ , S₁₁ }.

Уточненные схемы Q-модели по каждому потоку заявок представлены на рисунках 1.4 и 1.5.

Рисунок 1.4- Схема Q-модели 1-го потока

Рисунок 1.5- Схема Q-модели 2-го потока

В соответствии с данными, полученными на предыдущем этапе, уточняем матрицы переходов каждого из потоков.

Порядок движения запросов в процессе обслуживания представлен ниже матрицами переходов потоков P⁽¹⁾ иP⁽²⁾ .

Таблица 1.5- Матрица переходов P⁽¹⁾ для 1-го потока

Таблица 1.6- Матрица переходов P⁽²⁾ для 2-го потока

Для каждого потока параметры составляют:

- параметры законов поступления ;

- параметры обслуживания на ресурсах системы.

Последние включают:

- параметры обслуживания на устройстве S₁ ;

- параметры обслуживания на устройстве S₃ ;

- параметры обслуживания на устройстве S₄ ;

- параметры обслуживания в памяти S₂ .

- параметры обслуживания в памяти S₂ .

Параметры потоков приведены в таблице 1.7 и 1.8.

Таблица 1.7- Параметры 1-го потока

Таблица 1.8- Параметры 2-го потока

Параметры узлов Q-модели (см. рисунки 4, 4 – схемы Q-модели) приведены ниже в таблице 1.9.

Таблица 1.9- Параметры узлов Q-модели

Узловые характеристики системы, рассчитываемые на Q-модели, представлены в таблице 1.10.

Таблица 1.10- Узловые характеристики Q-модели

Системные характеристики системы, рассчитываемые на Q-модели, представлены таблице 1.11.

Таблица 1.11- Системные характеристики Q-модели

2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Результаты построения математической модели системы на базе ССМ представлены на рисунках 2.1, 2.2.

Рисунок 2.1- ССМ 1-го потока

Рисунок 2.2- ССМ 2-го потока

Использованные в рассматриваемой здесь модели ССМ-узлы кратко описаны в таблице 2.1

Таблица 2.1 - Описание узлов ССМ

3. РАЗРАБОТКА GPSS-ОРИЕНТИРОВАННОЙ ИМИТАЦИОННОЙ МОДЕЛИ

Реализуем имитационную модель на проблемно-ориентированном языке (GPSS).

Достоинство проблемно - ориентированного языка: полная автоматизация процесса моделирования. GPSS – GeneralPurposeSimulateSystem. Это язык макроопределений, связанных с описанием самой модели и режимов моделирования. Здесь нам нужно только лишь описать модель в терминах языка и запустить модель на счет.

Расчет модели будет производиться в системе GPSSWorld, следовательно модель надо описать на входном языке системы – на языке GPSS.

Приведем ее на рисунке 3.1.

Рисунок 3.1-ССМ , ориентированная на GPSS (1,2-ой поток)

В таблице 3.1 представлены параметры дополнительных узлов.

Таблица 3.1- Параметры GPSS-узлов

Измерение и вычисление узловых и системных характеристик иллюстрируется таблицами 3.2, 3.3. На схеме ССМ (рисунок 3.1) точки сбора статистики обозначены символом – x.

Таблица 3.2- Измерение узловых характеристик ССМ

Таблица 3.3- Измерение и вычисление системных характеристик ССМ

4. РАЗРАБОТКА, РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ УПРОЩЕННЫХ МОДЕЛЕЙ

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

Соответственно задача состоит в том, чтобы получить указанную сеть МО из исходной ССМ путем внесения в нее упрощений. Для этого:

1. Преобразуем исходную ССМ в сеть МО разомкнутого типа.

2. Заменим многоканальные узлы одноканальными.

3. Преобразуем сеть МО в однородную сеть.

4. Преобразуем сеть МО в экспоненциальную сеть.

5. Рассчитаем характеристики.

Построенная ранее ССМ (рисунки 2.1, 2.2) или GPSS-ССМ (рисунок 3.1) является разомкнутой, неоднородной (обслуживает два типа потоков заявок), не экспоненциальной и к тому же содержит такие неразрешенные в сетях МО ресурсы как память, узлы типа захвата и освобождения памяти, узел выбора маршрута в зависимости от состояния памяти.

Из исходной ССМ убираем:

- узел b₇ и связанные с ним альтернативные пути (маршруты) и соответствующие приемники b⁽¹⁾ ₉ и b⁽²⁾ ₉ , оставляя тем самым только основные маршруты с известными вероятностями их прохождения;

- убираем узел памяти b₅ и b₆ соответственно связанные с ним узлыb_5,1 , b_6,2 .

Полученный результат представлен на рисунке 4.1, только для одного из потоков, поскольку маршруты перемещения заявок оказываются одинаковыми для 1-го и 2-го потоков.

Рисунок 4.1- Сеть МО (для 1-го потока)

Для этого для каждого многоканального узла j с канальностью (Kj) и для каждого потока i (который обслуживается в этом узле) пересчитаем исходные трудоемкости запросов (средние значения длительности обслуживания в канале t^{( i )} _j ) и получим новые значения t*^{( i )} _j по формуле:

t *^{( i )} _{j =} t^{( i )} _j / Kj .

Здесь многоканальным является узел b₁ (c K₁ = 4) и b₃ (c K₃ = 2). Через этот узел проходят заявки 1-го и 2-го типов . Заменим его эквивалентным одноканальным узлом b*₁ (c K₁ = 1).

Тогда для первого потока

t *⁽¹⁾ _{1 =} t⁽¹⁾ ₁ / K₁ = 296 / 4 = 74

Для второго потока

t *⁽²⁾ _{1 =} t⁽²⁾ ₁ / K₁ = 296 / 4 = 74 .

Заменим все потоки заявок одним потоком с усредненными параметрами.

Для рассматриваемой модели:

j =1 или 2;

Q = {1, 2};

λ₀ ⁽¹⁾ = 0,004; t₀ ⁽²⁾ =240;

p⁽¹⁾ = 0,5; p⁽²⁾ =0,5;

t*⁽¹⁾ ₁ = 74;t*⁽²⁾ ₁ = 74;

t*⁽¹⁾ ₂ =36;t*⁽²⁾ ₂ = 36;

t ⁽¹⁾ ₃ =52;t ⁽²⁾ ₃ = 52

m*_t = 240.

При этом эквивалентное среднее значение длительности обслуживания для первого узла b*₁

t*_{1 =} p⁽¹⁾ *t*⁽¹⁾ _{1 +} p⁽²⁾ _* t*⁽²⁾ ₁ = 74.

Для узла b*₂

t*_{2 =} p⁽¹⁾ *t *⁽¹⁾ _{2 +} p⁽²⁾ _* t *⁽²⁾ ₂ = 36.

Для узла b₃

t_{3 =} p⁽¹⁾ *t⁽¹⁾ _{3 +} p⁽²⁾ _* t⁽²⁾ ₃ = 52.

Для рассматриваемой сети МО получим следующие значения параметров:

1. Для закона поступления заявок усредненного потока параметр экспоненциального распределения m_t = m*_t = 240 , скорость их поступления λ = 0,004.

2. Для закона распределения длительности обслуживания заявок в устройстве b₁ параметр экспоненциального распределения ₍ средняя длительность обслуживания в канале узла)m_t = t*₁ = 74.

3. Для закона распределения длительности обслуживания заявок в устройстве b₂ параметр экспоненциального распределения ₍ средняя длительность обслуживания в канале узла)m_t = t*₂ = 36.

4. Для закона распределения длительности обслуживания заявок в устройстве b₃ параметр экспоненциального распределения ₍ средняя длительность обслуживания в канале узла)m_t = t*₃ = 52.

В результате проведенных упрощений получена модель в виде разомкнутой, однородной, линейной, экспоненциальной сети МО с одноканальными устройствами.

Представим внешнюю среду одним узлом b₀ (вместо b₀ и b₄ ) и в качестве источника и в качестве приемника. Запросы приходят из внешней среды и возвращаются в нее.

Тогда сеть состоит из n = 5 узлов, где N = 3 устройств.

Состав узлов сети - b₀ , b₁ , b₂ , b_3, b₅ .

Опишем матрицу вероятностей переходов P, при этом будем учитывать все узлы, кроме маршрутных (таблица 4.1)

Таблица 4.1- Матрицу вероятностей переходов

Структура сети МО с указанием исходных параметров (интенсивностей потоков и параметров устройств) представлена на рисунке 4.2.

Рисунок 4.2- АМ (сеть МО)

В таблице 4.2 представлены параметры узлов сети МО.

Таблица 4.2- Параметры узлов сети МО

Параметры потока заявок приведены в таблице 4.3.

Таблица 4.3- Параметры потока заявок сети МО

Состав искомых характеристик представлен ниже. Это узловые характеристики:

- для узла b₁ - l₁ , m₁ , ρ₁ , ω₁ , u₁ ;

- для узла b₂ – l₂ , m₂ , ρ₂ , ω₂ , u₂ .

- для узла b₃ – l₃ , m₃ , ρ₃ , ω₃ , u₃ ;

Системные характеристики:

L = l₁ + l₂ + l₃ ;

M = m₁ + m₂ + m₃ ;

U = α_1* u₁ + α_2* u₂ + α_3* u_3;

W = α_1* ω₁ + α_2* ω₂ + α_3* ω₃ .

1. Опишем возможные состояния сети. Здесь это вектор , где M_i – число заявок в узле b_i .

Вектор , где M₁ – число заявок в узле b₁ (любое), M₂ – число заявок в узле b₂ (любое), M₃ – число заявок в узле b₃ (любое).

2. Вычислим неизвестные интенсивности потоков λ_i на входах в устройства. Для этого построим и решим систему из N линейных уравнений, используя свойство линейности, выражаемое для каждого из устройств i = 1, 2, …, N как

.

Здесь N = 3 и искомые величины: λ_1, λ₃ и λ_4. Система уравнений выглядит как

λ₁ =λ_{0 *} p_0,1 + λ_{1 *} p_1,1 + λ_{2 *} p_2,1 + λ_{3 *} p_3,1 ;

λ₂ =λ_{0 *} p_0,4 + λ_{1 *} p_1,4 + λ_{2 *} p_2,4 + λ_{3 *} p_3,4 .

λ₃ =λ_{0 *} p_0,3 + λ_{1 *} p_1,3 + λ_{2 *} p_2,3 + λ_{3 *} p_{3,3 ;}

А после подстановки значений p_{i , j} из матрицы P

λ₁ =λ_{0 *} 0+ λ_{1 *} 0+ λ_{2 *} 1+ λ_{3 *} 0;

λ₂ =λ_{0 *} 0+ λ_{1 *} 0+ λ_{2 *} 0.5+ λ_{3 *} 0.5 _;

λ₃ =λ_{0 *} 1+ λ_{1 *} 0+ λ_{2 *} 0+ λ_{3 *} 0.

Соответственно

λ₁ = 0,004;

λ₂ = 0,008;

λ₃ = 0,004.

3. Рассчитываем коэффициенты передач (среднее число посещений заявкой каждого устройства) α_k =λ_k / λ₀ .

α₁ =λ₁ / λ₀ = 1;

α₂ =λ₂ / λ₀ = 2;

α₃ =λ₃ / λ₀ = 1.

4. Рассчитываем коэффициенты загрузок устройств ρ_k =λ_{k *} t_k .

ρ₁ =λ_{1 *} t₁ = 0,296;

ρ₂ =λ_{2 *} t₂ = 0,288;

ρ₃ =λ_{3 *} t₃ = 0,208.

Так как коэффициенты загрузок меньше 1, то сеть работает в стационарном режиме и можно продолжать расчеты.

5. Рассчитываем узловые характеристики по формулам:

l_i = ρ_i ² / ( 1 -ρ_i ) ,

m_i = ρ_i / ( 1 -ρ_i ) ,

ω_{i =} l_i / λ_{i ,}

u_{i =} m_i / λ_{i .}

Для узла b₁ получаем

l₁ = 0,124; m₁ = 0,42; ω₁ = 31; u₁ = 105;

для узла b₂ получаем

l₂ = 0,116; m₂ = 0,404; ω₂ = 14,5; u₂ = 50,5;

для узла b₃ получаем

l₃ = 0,055; m₃ = 0,263; ω₃ = 13,75; u₃ = 65,75.

Полученные результаты сведем в таблицу 4.4.

Таблица 4.4- Значения характеристик сети МО

Реализуем имитационный метод расчета полученной АМ в системе GPSSWorld.

Рисунок 4.3- GPSS-модель сети МО

Построим GPSS-модель по соответствующей ССМ, ориентированной на язык GPSS.

Текст GPSS модели приведен ниже.

Листинг4.1- Текст GPSS модели

GENERATE (Exponential(1,0,240))

queue U_system

queue w_b_1

queue u_b_1

SEIZE b_1

depart w_b_1

ADVANCE (Exponential(2,0,74))

RELEASE b_1

depart u_b_1

queue u_sum_b_2

Label_1 queue w_b_2

queue u_b_2

SEIZE b_2

depart w_b_2

ADVANCE (Exponential(3,0,36))

RELEASE b_2

depart u_b_2

TRANSFER .5,,Label_1

depart u_sum_b_2

queue u_b_3

queue w_b_3

SEIZE b_3

depart w_b_3

ADVANCE (Exponential(4,0,52))

RELEASE b_3

depart u_b_3

depart U_system

TERMINATE 1

start 100000

Листинг 4.2- Статистический отчет выполнения GPSS-модели

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

B_1 100002 0.308 74.159 1 0 0 0 0 0

B_2 200116 0.300 36.068 1 100002 0 0 0 0

B_3 100001 0.217 52.102 1 100001 0 0 0 0

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

U_SYSTEM 11 2 100002 0 1.149 276.367 276.367 0

W_B_1 8 0 100002 69323 0.135 32.565 106.148 0

U_B_1 9 0 100002 0 0.444 106.723 106.723 0

U_SUM_B_2 9 1 100002 0 0.428 102.970 102.970 0

W_B_2 9 0 200116 140362 0.128 15.388 51.534 0

U_B_2 9 1 200116 0 0.428 51.456 51.456 0

U_B_3 8 1 100001 0 0.277 66.674 66.674 0

W_B_3 7 1 100001 78392 0.061 14.572 67.437 0

Ниже в таблице 4.5 представлены результаты аналитического и имитационного (с разной длительностью – 10000, 50000, 100000 заявок) моделирования и вычислена погрешность. При этом за эталон взяты характеристики АМ.

Таблица 4.5- Результаты аналитического и имитационного моделирования сети МО