Разработка модели системы массового обслуживания

1. Постановка задачи

2. Представление объекта моделирования в виде системы массового обслуживания

3. Разработка ГСЧ

3.1 ГСЧ 1

3.2 ГСЧ 2

4. Проверка качества разработанных ГСЧ

4.1 Оценка качества ГСЧ 1

4.2 Оценка качества ГСЧ 2

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

6. Работа программы

7. Исследование эффективности разработанной модели Приложение

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

Для разработки программной модели применялась среда программирования Visual Studio C++ 2009.

1. Постановка задачи

ЭВМ обслуживает три терминала по круговому циклическому алгоритму, предоставляя каждому терминалу 30 с. Если в течение этого времени задание обрабатывается, то обслуживание завершается; если нет, то остаток задачи ставится в специальную очередь, которая использует свободные циклы терминалов, т. е. задача обслуживается, если на каком-либо терминале нет заявок. Заявки на терминалы поступают примерно через 30 с. (экспоненциальный закон) и имеют в длину 300 ± 50 знаков (в соответствии с законом Гаусса). Скорость обработки заданий ЭВМ равна 10 знаков/сек.

Разработать:

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

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

3. Смоделировать 5 ч. работы ЭВМ, параметры очереди неоконченных заданий.

2. Представление объекта моделирования в виде системы массового обслуживания

Система состоит из трех терминалов, на которые из ГСЧ через определённые промежутки времени поступают задания, и ЭВМ. Терминалы функционируют параллельно. На вход терминалов поступают задания. В описании системы не ясно, как поступают заявки: от одного источника или от трех. Логичнее предположить, что источников три, так как один пользователь вряд ли будет работать с тремя терминалами одновременно. После обработки на терминале заявки попадают на ЭВМ. После обработки часть из них поступает в очередь, а остальные покидают систему. Из очереди задания поступают на ЭВМ для дообработки. Структурная схема модели изображена на рисунке 1Рисунок .

Рисунок 1

3. Разработка ГСЧ

Поскольку функционирование данной вычислительной системы подразумевает поступление сообщений в систему через случайные моменты времени, и продолжительность обработки данных на процессорах тоже не одинакова для всех сообщений, то для имитации этих процессов потребуется генератор случайных чисел. Из условия известно, что заявки на терминалы поступают через интервалы времени, распределённые по экспоненциальному закону, со средним значением 30 с. Генератор, служащий для получения последовательности псевдослучайных чисел, задающих интервалы времени, через которые поступают заявки, обозначим как ГСЧ 1. Также известно, что длины заявок (300 ± 50 знаков) распределены в соответствии с законом Гаусса (нормальным законом распределения). Генератор, имитирующий длины заявок обозначим как ГСЧ 2.

3.1 ГСЧ 1

массовый обслуживание генератор псевдослучайный

Получим алгоритм генерации случайной величины, распределенной по экспоненциальному закону методом обратной функции, который основан на использовании теоремы теории вероятностей: если случайная величина X имеет плотность распределения вероятности, то распределение случайной величины является равномерным в интервале (0,1). Чтобы получить случайную величину с плотностью распределения вероятностей необходимо решить уравнение

где — случайная величина, распределенная по равномерному закону и равная функции распределения вероятностей случайной величины .

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

Так как ГСЧ 1 имитирует время поступления заявок на ЭВМ, то примем математическое ожидание равным 30 с.

На основании этого напишем функцию, реализующую работу данного генератора:

double ExpGen (int sredn)

{

returnsredn*log ((static_cast (rand ()) / RAND_MAX) *1);

}

3.2 ГСЧ 2

Продолжительность обработки сообщений в процессоре будет определяться значениями, полученными ГСЧ 2 по нормальному распределению методом Бусленко. Представляем кривую плотности распределения в виде кусочно-постоянной функции, т. е. разбиваем интервал (a, b) на m интервалов с подинтервалами. На каждом подинтервале значение функции. Вероятность попадания в каждый из интервалов обозначим как, .

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

Так как ГСЧ 2 имитирует длины заявок, поступающих на ЭВМ, то длины заявок примем как [250+у; 350+у].

Функция, описывающая работу ГСЧ 2, выглядит так:

double GaussGen (double x, double y)

{

return (double)rand_Busl () / (RAND_MAX + x) * (y — x) + x;

}

4. Проверка качества разработанных ГСЧ

4.1 Оценка качества ГСЧ 1

Проверим качество генерируемой последовательности псевдослучайных величин для ГСЧ 1. Для этого построим гистограмму распределения и вычислим площадь отклонений ее значений от идеальной гистограммы распределения для равномерного закона.

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

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

где S_ид — площадь идеальной последовательности, S_i — площадь столбца для проверяемой последовательности. На основании площади отклонений вычислим погрешность распределения по формуле:

Как видно, погрешность работы на порядок меньше требуемой погрешности в 8%, следовательно генератор работает корректно, и последовательность значений, получаемая разработанным генератором, является достаточно качественной.

4.2 Оценка качества ГСЧ 2

Качества генерируемой последовательности для ГСЧ 2 будем проверять по критерию Пирсона. Для этого требуется вычислить значение ч²:

где M — число интервалов разбиения, N — количество генерируемых значений, — предполагаемая вероятность попадания в i-й интервал. Значение характеризует отношение количества чисел в i-том интервале к общему числу сгенерированных значений и вычисляется по формуле:

где n_i — количество чисел в i-м интервале.

Для генератора, работающего по нормальному закону распределения:

Значения ч² для 11 интервалов разбиения и 3000 генерируемых значений ниже табличного (ч² _табл = 14,6837 для P_дов = 0.9), что позволяет утверждать, что последовательности случайных чисел вычисляемых ГСЧ 2 качественные. Таблица значений, распределённых программой по интервалам:

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

На основании структурной схемы построим алгоритмическую модель вычислительной системы, она показана на рисунке 2Рисунок .

Рисунок 2

6. Работа программы

После запуска программы производится генерация массивов значений, которые будут использованы далее в программе. После заполнения массивов, пользователь может запустить процесс моделирования, по завершении которого будут выведены результаты, в том же окне программы. В ходе моделирования будут созданы два файла, для оценки ГСЧ 1 и ГСЧ 2. Программой будут сгенерированы файлы логов, по которым можно будет наблюдать процесс работы всей системы, а также результаты моделирования запишутся в файл «*.csv», по которому можно будет построить гистограмму или график.

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

.

Временная диаграмма работы системы показана на рисунке 3.

Рисунок 3

7. Исследование эффективности разработанной модели

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

.

Программа считает количество поступивших сообщений и количество сообщений, покинувших систему, поэтому:

Расчёт эффективности (загрузки ЭВМ) производится нахождением среднего значения коэффициента загрузки ЭВМ по выданным программой значениям:

К_з = ((299/304) + (293/310) + (298/305) + (291/312) + (285/318) + (295/308) + (290/313) + (296/307) + (284/300) + (280/303)) / 10 = (0.947 982 + 0.94 848 + 948 314 + 0.95 141 + 0.953 455 + 0.974 264 + 0.95 141 + 0.94 953 + 0.948 646 + 0.951 133) / 10 = 0,9 524 624

Заключение

В ходе выполнения данной курсовой работы была разработана система массового обслуживания, которая представляет собой два генератора псевдослучайных величин и ЭВМ, обрабатывающая поступающие заявки. Проверено качество их работы по гистограмме распределения и по критерию Пирсона. Оба генератора показали хорошие результаты. Погрешность распределения для первого генератора оказалась равной 0,553%, критерий Пирсона ч² для второго генератора равен 6,0245, при табличном значении (для выбранного числа интервалов разбиения) 14,6837.

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

Приложение

Исходный код программы.

// console. cpp: определяет точку входа для консольного приложения.

#include «stdafx.h»

#include «object.h»

#include

#include

#include

#include

#include

#include

using namespace std;

int mtime = 30;

int speed = 10;

int term_time = 30;

double nleft=250, nright=350;

int model_time=3600*5;

double ExpGen (int sredn)

{

returnsredn*log ((static_cast (rand ()) / RAND_MAX) *1);

}

double GaussGen (double x, double y)

{

return (double)rand () / (RAND_MAX + x) * (y — x) + x;

}

void gist (const char name[11], const char name₂[11], const double *mass, int num_elements, bool inf_show);

double main_buf=0;

EVM evm;

bool term1=true, term2=true, term3=true;

int _tmain (int argc, _TCHAR* argv[])

{

setlocale (LC_ALL, «rus»);

double sec_count=0;

srand (time (0));

double WorkTime=0;

double tbuf1=0, tbuf2=0, tbuf3=0;

double lbuf1=0, lbuf2=0, lbuf3=0;

do{

if (sec_count>=tbuf1)

{

tbuf1=floor (ExpGen (mtime));

lbuf1=floor (GaussGen (nleft, nright));

term1=false;

}

if (sec_count>=tbuf2)

{

tbuf2=floor (ExpGen (mtime));

lbuf2=GaussGen (nleft, nright);

term2=false;

}

if (sec_count>=tbuf3)

{

tbuf3=floor (ExpGen (mtime));

lbuf3=GaussGen (nleft, nright);

term3=false;

}

if (term1==false)

{

main_buf=evm.SetWtime (lbuf1, speed, term_time);

if (main_buf≠0)

{

evm.modifyline (main_buf);

}

sec_count=sec_count+term_time;

term1=true;

}

else

{

main_buf=evm.GetFromLine (speed);

if (main_buf≠0)

{

sec_count=sec_count+floor (main_buf);

}

}

if (term2==false)

{

main_buf=evm.SetWtime (lbuf2, speed, term_time);

if (main_buf≠0)

{

evm.modifyline (main_buf);

}

sec_count=sec_count+term_time;

term2=true;

}

else

{

main_buf=evm.GetFromLine (speed);

if (main_buf≠0)

{

sec_count=sec_count+floor (main_buf);

}

}

if (term3==false)

{

main_buf=evm.SetWtime (lbuf3, speed, term_time);

if (main_buf≠0)

{

evm.modifyline (main_buf);

}

sec_count=sec_count+term_time;

term3=true;

}

else

{

main_buf=evm.GetFromLine (speed);

if (main_buf≠0)

{

sec_count=sec_count+floor (main_buf);

}

}

}while (sec_count<=model_time);