Моделирование распределенного банка данных

Имеются следующие исходные данные для моделирования: распределенный банк данных организован на базе двух ЭВМ, соединенных дуплексным каналом связи. Поступающий запрос обрабатывается на первой ЭВМ и с вероятностью 50% необходимая информация обнаруживается в этой ЭВМ. В противном случае запрос направляется на вторую ЭВМ. Запросы поступают через 10±3 с. Выдача ответа с первой ЭВМ требует 18±2с, передача запроса по каналам на вторую ЭВМ занимает 3 с. Временные характеристики второй ЭВМ аналогичны.

Смоделировать прохождение 400 запросов. Определить необходимую емкость накопителей перед обеими ЭВМ, обеспечивающую безотказную работу системы.

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

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

Теоретическим обоснованием концептуальной, формализованной модели системы являются сведения, приведенные в учебных пособиях: Советов Б. Я., Яковлев С. А. «Моделирование систем», Советов Б. Я., Яковлев С. А. «Моделирование систем. Практикум». В данной литературе приведены все необходимые данные, примеры, основные принципы моделирования.

Для построения математической модели воспользуемся формулами и примерами расчетов, рассмотренными в учебнике Вентцель Е. С. «Исследование операций».

Принципы программирования на языке имитационного моделирования GPSS изложены в книге Шрайбер Т.Дж. «Краткое практическое руководство по GPSS». В руководстве представлены основные концепции моделирования на GPSS, примеры, списки операторов и блоков GPSS.

1. Описание моделируемой системы

Из условия следует, что распределенный банк данных функционирует следующим образом: запросы поступают на первую ЭВМ, и с вероятностью 50% необходимая информация находится здесь, следовательно на первой ЭВМ обрабатывается весь поток поступающих заявок, а на второй только половина. Временные характеристики ЭВМ аналогичны.

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

2. Структурная схема модели системы и ее описание

На основании задания построим структурную схему данной системы.

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

1. режим нормального обслуживания, когда обе ЭВМ обслуживают заявки;

2. режим простоя, когда одна или обе ЭВМ свободны;

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

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

3. Временная диаграмма и ее описание

имитационный моделирование оптимизация язык Более детально процесс функционирования распределенного банка данных можно представить на временной диаграмме (рисунок 2).

На диаграмме:

— ось 1 — моменты поступления запросов;

— ось 2 — пребывание запросов в накопителе 1;

— ось 3 — обработка запросов на ЭВМ 1;

— ось 4 — передача запроса по каналам на вторую ЭВМ;

— ось 5 — пребывание запросов в накопителе 2;

— ось 6 — обработка запросов на ЭВМ 2;

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

На этом завершается этап построения концептуальной модели системы.

4. Q-схема системы и ее описание

Данный этап является формализацией модели. Наилучший способ для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания это построение непрерывно-стохастической модели.

По своей сути описанные процессы являются процессами обслуживания потоков партий и комплектов деталей, поэтому для формализации задачи используем аппарат Q-схем. В соответствии с построенной концептуальной моделью структурную схему данной СМО (рисунок 1) можно представить в виде, показанном на рисунке 3, где И — источник, Н — накопитель, К — канал, ЭВМ1 и ЭВМ2 — первая и вторая ЭВМ соответственно.

Рисунок 3 — Структурная схема процесса функционирования распределенного банка данных в символике Q-схем.

При этом источник И имитирует поступление запросов. Изделия поступают в накопители Н1 и Н2 соответственно. Обслуживание происходит на ЭВМ1 и ЭВМ2, передача запроса с ЭВМ1 на ЭВМ2 осуществляется через канал.

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

5. Укрупненная схема моделирующего алгоритма

После этапа формализации задачи необходимо приступить к построению моделирующего алгоритма.

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

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

Обобщенная схема детерминированного моделирующего алгоритма данной задачи, т. е. алгоритма построенного по «принципу t», представлена на рисунке 4.

Разберем алгоритм работы модели.

С помощью блока 1 происходит пуск системы и начинается эмуляция работы объекта исследования.

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

Блок 3 определяет прошли все запросы или нет.

Блок 4 осуществляет поступление запроса на вход Q-схемы.

Блок 5 производит переход из первого накопителя на первую ЭВМ.

Блок 6 описывает обработку заявки на первой ЭВМ.

Блок 7 проверяет, получена ли требуемая информация.

В блоке 8 осуществляется передача запроса с ЭВМ1 по каналу на ЭВМ2.

Блок 9 производит переход из второго накопителя на вторую ЭВМ.

Блок 10 описывает обработку заявки на второй ЭВМ.

Блок 11 осуществляет переход к следующему интервалу? t.

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

Блок 13 прекращает эмуляцию.

6. Детальная схема моделирующего алгоритма и ее описание

На данном этапе произведем декомпозицию системы к виду блок-диаграммы, которая, сохраняя в основном структуру модели, использует графические аналоги соответствующих операторов GPSS, а затем переведем ее в программу на GPSS. Блок-диаграммой в пакете GPSS называется графическое представление операций, происходящих в моделируемой системе.

Блок-диаграмма модели процесса функционирования распределенного банка данных представлена на рисунке 5, где NEVM1, NEVM2 — накопители; SEK — участок заполнения секции; BLOK1, BLOK2 — участки комплектации деталей 1-го и 2-го типов. За единицу системного времени выбираем 1/100, так как согласно технической документации GPSS/РС при этом обеспечивается наилучшее качество псевдослучайных последовательностей.

7. Математическая модель и ее описание

Запишем переменные и уравнения имитационной модели процесса функционирования распределенного банка данных:

Т — общее время моделирования;

— время решения задачи най ЭВМ, =1,2;

N₀ — количество обслуженных запросов;

N₁ — количество запросов, получивших отказ;

Р_отк — вероятность отказа в обслуживании;

уравнения модели:

(7.1)

(7.2)

(7.3)

где — вероятность отказа в обслуживании;

и — коэффициенты загрузки ЭВМ1 и ЭВМ2;

и — суммарное время занятости ЭВМ1 и ЭВМ2;

Вероятность отказа в обслуживании Р_отк и коэффициенты загрузки ЭВМ1 и ЭВМ2 являются критериями эффективности работы распределенного банка данных.

8. Описание машинной программы решения задачи

Переведем построенную блок-диаграмму модели, в программу на языке GPSS/PC. Текст программы приведен в приложении 1, комментарии — в приложении 2.

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

SIMULATE (МОДЕЛИРОВАТЬ) начальная карта программы, если разработчик намерен выполнить прогон модели. Если эта карта отсутствует, то интерпретатор проверяет правильность записи модели на языке GPSS, но прогона модели не выполняет.

Блок STORAGE (МНОГОКАНАЛЬНОЕ УСТРОЙСТВО) используется для создания многоканальных устройств. Однако в программе он используется для создания накопителей.

Вход в многоканальное устройство и выход из него обеспечиваются использованием операторов ENTER (ВОЙТИ) и LEAVE (ВЫЙТИ) соответственно. В программе используется два накопителя.

GENERATE (ГЕНЕРИРОВАТЬ) — это блок, через который транзакты входят в модель. Не существует ограничений на число различных блоков GЕNЕRАТЕ в одной модели. Интервал времени между последовательными появлениями транзактов блока GENERAТЕ называют интервалом поступления.

Блоки QUEUE (СТАТЬ В ОЧЕРЕДЬ) и DЕРАRТ (ПОКИНУТЬ ОЧЕРЕДЬ) обеспечивают возможность автоматического сбора статистических данных, описывающих вынужденное ожидание, которое может происходить время от времени в различных точках модели

QUEUE OCH1 — оператор организации очереди, длина очереди OCH1 увеличивается на единицу. Для увеличения на заданное число в поле B оператора вводится необходимое число.

DEPART OCH1 — то же, но длина очереди уменьшается.

Блок GATE SF (ВПУСТИТЬ) проверяет занято ли в данный момент накопитель. Если да, то транзакты уничтожаются, что моделирует отказ.

С помощью блока TRANSFER (ПЕРЕДАТЬ) задается вероятность нахождения информации на первой ЭВМ, если она найдена транзакт уничтожается.

Вход транзакта в блок SEIZЕ (ЗАНЯТЬ) моделирует занятие прибора, вход того же транзакта в другой блок RELЕАSЕ (ОСВОБОДИТЬ) моделирует освобождение прибора. Назначением этого блока является изменение состояния ранее занятого прибора с «занято» в «незанято».

Блок АDVANCЕ (ЗАДЕРЖАТЬ) предназначен для реализации задержки продвижения транзакта в течение некоторого интервала времени. Обычно этот интервал задается случайной переменной. Опыт показывает, что время обслуживания обычно меняется от одного обслуживания к другому.

Транзакты удаляются из модели, попадая в 6 лок ТЕRМINАТЕ (ЗАВЕРШИТЬ). Блоки ТЕRМINАТЕ всегда позволяют выйти всем транзактам, которые пытаются это сделать. В модели может быть любое число блоков ТЕRМINАТЕ.

Когда симулятор GPSS доходит до оператора END, он автоматически заканчивает работу.

9. Результаты моделирования и их анализ

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

START_TIME END_TIME BLOCKS FACILITIES STORAGES FREE_MEMORY

0 4013 24 2 2 14 960

LINE LOC BLOCK_TYPE ENTRY_COUNT CURRENT_COUNT RETRY

40 1 GENERATE 406 0 0

50 2 QUEUE 406 0 0

55 3 GATE 406 0 0

57 4 TRANSFER 0 0 0

60 NAK1 ENTER 406 3 0

70 6 SEIZE 403 0 0

90 7 LEAVE 403 0 0

95 8 DEPART 403 0 0

110 9 TRANSFER 403 0 0

120 OTVET ADVANCE 205 1 0

130 11 RELEASE 204 0 0

140 12 TERMINATE 204 0 0

150 PER RELEASE 198 0 0

160 14 ADVANCE 198 0 0

170 15 QUEUE 198 0 0

175 16 GATE 198 0 0

179 17 TRANSFER 0 0 0

180 NAK2 ENTER 198 1 0

190 19 SEIZE 197 1 0

200 20 DEPART 196 0 0

210 21 LEAVE 196 0 0

230 22 ADVANCE 196 0 0

240 23 RELEASE 196 0 0

250 OTK TERMINATE 196 0 0

FACILITY ENTRIES UTIL. AVE._TIME AVAILABLE OWNER PEND INTER RETRY DELAY

EVM1 403 0.922 9.18 1 403 0 0 0 3

EVM2 197 0.881 17.96 1 401 0 0 0 1

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

OCH1 12 3 406 46 3.16 31.26 35.25 0

OCH2 10 2 198 17 2.67 54.20 59.29 0

STORAGE CAP. REMAIN. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

NEVM1 12 9 0 12 406 1 3.16 0.264 0 0

NEVM2 10 8 0 10 198 1 2.67 0.267 0 0

Проанализируем полученную статистику. В сумме за время моделирования через блоки ТЕRМINАТЕ прошло 400 транзактов, что соответствует модулированию 400 запросов.

Среднее содержимое очереди для первого накопителя — 3.16; для второго — 2.67, что соответствует коэффициенту загрузки 26% и 27%. Это низкие коэффициенты загрузки, но только при таких емкостях накопителей удовлетворяется главное требование к работе системы — безотказность. В тоже время коэффициенты загрузки для ЭВМ очень высоки — 92% и 88%, что свидетельствует об эффективности их работы.

Согласно формулам (7.1), (7.2), (7.3), исходным и полученным данным имеем:

Т = 4013 с;

= 9,2с; = 18с;

N₀ =400;

N₁ =0;

Р_отк — вероятность отказа в обслуживании;

и — коэффициенты загрузки ЭВМ1 и ЭВМ2;

= 0,917

= 0,884

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

10. Описание возможных улучшений в работе системы

Попытаемся каким-либо способом оптимизировать работу системы, при этом будем обращать внимание на такие характеристики системы, как коэффициенты загрузки ЭВМ и накопителей. Попробуем несколько повысить эффективность использования накопителей, но с начала определимся с показателями, которые можно изменять. Очевидно, что нельзя изменить время поступления запросов в систему, следовательно, будем изменять внутренние характеристики системы. Определимся с экономической целесообразностью таких изменений, вторая ЭВМ используется не так эффективно как первая, следовательно, можно попробовать увеличить скорость работы первой ЭВМ за счет второй. Опытным путем установили новое время обработки запросов для ЭВМ1 15±2с, для ЭВМ2 20±2 с.

START_TIME END_TIME BLOCKS FACILITIES STORAGES FREE_MEMORY

0 4091 24 2 2 15 200

LINE LOC BLOCK_TYPE ENTRY_COUNT CURRENT_COUNT RETRY

40 1 GENERATE 409 0 0

50 2 QUEUE 409 0 0

55 3 GATE 409 0 0

57 4 TRANSFER 0 0 0

60 NAK1 ENTER 409 1 0

70 6 SEIZE 408 0 0

90 7 LEAVE 408 0 0

95 8 DEPART 408 0 0

110 9 TRANSFER 408 0 0

120 OTVET ADVANCE 213 1 0

130 11 RELEASE 212 0 0

140 12 TERMINATE 212 0 0

150 PER RELEASE 195 0 0

160 14 ADVANCE 195 0 0

170 15 QUEUE 195 0 0

175 16 GATE 195 0 0

179 17 TRANSFER 0 0 0

180 NAK2 ENTER 195 6 0

190 19 SEIZE 189 1 0

200 20 DEPART 188 0 0

210 21 LEAVE 188 0 0

230 22 ADVANCE 188 0 0

240 23 RELEASE 188 0 0

250 OTK TERMINATE 188 0 0

FACILITY ENTRIES UTIL. AVE._TIME AVAILABLE OWNER PEND INTER RETRY DELAY

EVM1 408 0.786 7.88 1 408 0 0 0 1

EVM2 189 0.921 19.95 1 397 0 0 0 6

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

OCH1 7 1 409 122 1.25 12.55 17.89 0

OCH2 9 7 195 14 2.99 62.71 67.56 0

STORAGE CAP. REMAIN. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

NEVM1 7 6 0 7 409 1 1.25 0.179 0 0

NEVM2 9 2 0 9 195 1 2.99 0.332 0 0

В результате преобразования суммарная емкость накопителей уменьшилась на 6 единиц, но и коэффициент использования ЭВМ1 снизился на 15,4%, а коэффициент использования ЭВМ2 увеличился незначительно. Однако этот результат можно считать некоторым улучшением системы, так как он уменьшает материальные затраты.

Заключение

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

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

Советов Б.Я., Яковлев С. А. Моделирование систем. — М.: Высш. шк., 1995.

Советов Б.Я., Яковлев С. А. Моделирование систем. Практикум. — М.: Высш. шк., 1999.

Вентцель Е. С. Исследование операций. — М.: Радио и связь, 1972.

Шрайбер Т.Дж. Краткое практическое руководство по GPSS. — электронное учебное пособие