Модель генератора последовательности случайных чисел : Курсовая работа (т) по Информационное обеспечение, программирование

Рубрикатор

Информационное обеспечение, программирование

Курсовые работы (т)

Модель генератора последовательности случайных чисел

Содержание

Введение2

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

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

.1ГСЧ 1А и ГСЧ1Б4

.2ГСЧ 2А и ГСЧ2Б6

.3Оценка качества ГСЧ9

. Разработка имитационной модели объекта15

.1Разработка структурной схемы15

.2Расчет статистических показателей15

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

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

. Анализ результатов моделирования20

Заключение24

Приложение25

Введение

вычислительное устройство информация мультиплексный

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

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

Программная модель создавалась с использованием среды программирования C++ Builder.

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

Система обработки информации содержит мультиплексный канал и ЭВМ. Сигналы от датчика поступают в канал через интервалы времени, распределённые по равномерному закону в диапазоне от 20 сек. до 40 сек. В канале они буферизуются и предварительно обрабатываются, ёмкость накопителя 10 величин сигналов. Обработка в ЭВМ осуществляется в течение интервала времени, распределенного по равномерному закону, в диапазоне от 15 до 45 сек.

Время безотказной работы и время восстановления ЭВМ распределены по закону Вейбулла-Гнеденко. Среднее значение времени безотказной работы 36 часов, параметр формы распределения = 0,95; среднее времени восстановления 20 мин, значение параметра формы распределения =0,85. Во время отказа ЭВМ обслуживание сигналов датчика прекращается; заявка, обслуживание которой было прервано, возвращается в начало очереди, время обслуживания обнуляется.

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

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

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

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

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

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

Из условия известно, что сигналы от датчиков поступают через интервалы времени, распределенные равномерно в диапазоне от 20 до 40 секунд. Генератор, служащий для имитации работы датчиков, назовем ГСЧ 1А. Обработка в ЭВМ осуществляется в течение интервала времени, распределенного по равномерному закону, в диапазоне от 15 до 45 сек. Генератор, применяемый для нахождения интервала времени, необходимого на обработку сигналов, назовем ГСЧ 1Б. Время безотказной работы ЭВМ, распределенное по закону Вейбулла-Гнеденко с параметром формы распределения ? = 0,95 и максимальным значением 36 часов, будет имитировать генератор с названием ГСЧ 2А. Время восстановления ЭВМ, распределенное по этому же закону, но с параметром ? = 0,85 и максимальным значением 20 минут, будет определяться генератором ГСЧ 2Б.

2.1 ГСЧ 1А и ГСЧ1Б

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

В итоге получим:

где xi - число из базовой последовательности от 0 до 1, a и b - минимальное и максимальное генерируемые значения соответственно. Подставив заданные значения a = 20, b = 40 получим выражение для ГСЧ 1А:

yi = 20 + 20xi,

а подставив значения a = 15, b = 45 получим выражение для ГСЧ 1Б:

yi = 15 + 30xi.

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

/* Функция генерирует числа от 20 до 40, распределенные по равномерному закону (сигналы от датчиков) */

double GenRand1a()

{20.0 + 20.0 * (static_cast<double>(rand()) / RAND_MAX);

}

/* Функция генерирует числа от 15 до 45, распределенные по

равномерному закону (обработка в ЭВМ) */

double GenRand1b()

{15.0 + 30.0 * (static_cast<double>(rand()) / RAND_MAX);

}

.2 ГСЧ 2А и ГСЧ2Б

Время безотказной работы ЭВМ и время восстановления будут определяться значениями, полученными ГСЧ 2А и ГСЧ 2Б соответственно. Для реализации этих ГСЧ применим метод Бусленко. Суть метода состоит в том, что площадь под кривой закона распределения на заданном участке делится на некоторое число одинаковых по площади прямоугольников. Распределение получается таким, что чем больше вероятность выпадения некоторого значения, тем большее скопление прямоугольников будет в этом месте. Для маловероятных чисел прямоугольников будет мало. Таким образом, если выбор номера прямоугольника осуществляется с равной вероятностью для каждого из прямоугольников, то чаще будем попадать на те прямоугольники, которые соответствуют более часто встречающимся числам для данного закона распределения. Для чисел, чья вероятность выпадения мала, наоборот прямоугольники будут попадаться редко, поскольку их мало (но они более широкие).

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

Если обозначить через ai левую границу i-го интервала, то ai+1 будет правой границей этого интервала. Значение из базовой последовательности от 0 до 1 обозначим через ri. Формула для генерации псевдослучайных чисел по методу Бусленко в этом случае будет выглядеть следующим образом:

xi = ai + (ai+1 - ai)ri.

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

void GenRand2::Init()

{pos = x1;sq = 0, sq1;

/* Вычислим площадь под графиком VeibulZakon() */

{+= VeibulZakon(pos) * step;+= step;

} while (pos < x2);

// Найдем единичную площадь, т. е. площадь одного прямоугольника

sq1 = sq / n;(granica != NULL)

{[] granica;= NULL;

}= new double[n + 1];[0] = x1; = x1;

int i;

/* Найдем границы интервалов, путем разделения всей имеющейся

площади по площадям отдельных прямоугольников */

for (i = 1; i < n; i++)

{= 0;

{+= VeibulZakon(pos) * step;+= step;

} while (sq < sq1);[i] = pos;

}[n] = x2;= true;

}

Непосредственная генерация значений производится функцией Generate(), реализованной следующим образом:

double GenRand2::Generate()

{(!IsInit)

Init();interval;

/* Определяем номер требуемого интервала - это

случайное число от 0 до n - 1 */

interval = rand() % n;left_val, right_val;

/* Найдем правую и левую границы интервалов */

left_val = granica[interval];_val = granica[interval + 1];

// Генерируем число на полученном интервалеvalue = (static_cast<double>(rand()) / RAND_MAX) *

(right_val - left_val) + left_val;

return value;

}

Следует заметить, что процедура инициализации генератора требует больших затрат машинного времени, но последующая генерация значений осуществляется очень быстро. Разработанный класс применяется как для ГСЧ 2А, так и для ГСЧ 2Б, достаточно объявить соответствующие переменные с разными параметрами:

Generator2a = new GenRand2(0.95, 36, 36, 42);b = new GenRand2(0.85, 20, 20, 27);

.3 Оценка качества ГСЧ

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

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

где x1, x2 - соответственно минимальное и максимальное генерируемые значения, а N - количество интервалов разбиения. Высота столбца будет рассчитываться по формуле:

где ni - количество значений, лежащих в i-том интервале, n - общее количество сгенерированных значений. Площадь столбца вычисляется по формуле

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

Площадь столбов идеальной гистограммы для закона Вейбулла-Гнеденко будет определяться по формуле:

где i - номер интервала, xi и xi + 1 - начало и конец i-го интервала.

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

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

где Sобщ - суммарная площадь всех столбцов, равная 1.

Описанный алгоритм вычисления погрешности распределения реализован в программе, также имеется возможность построения гистограммы распределения. На рисунке 1 показан расчет погрешности распределения для 10 интервалов разбиения и 3000 генерируемых значений для генератора ГСЧ 1А. На рисунке 2 показан аналогичный расчет для ГСЧ 1Б. Как видно из этих рисунков, полученные значения погрешности распределения не превышают рекомендуемого значения для равномерного закона распределения, равного 5%. Это позволяет сделать вывод, что последовательности значений, получаемые генераторами ГСЧ 1А и ГСЧ 1Б, являются достаточно качественными. На рисунках 3 и 4 изображены гистограммы распределения для ГСЧ 1А и ГСЧ 1Б соответственно, построенные по сгенерированным значениям.

Расчет погрешности распределения для ГСЧ 2А показан на рисунке 5, а на рисунке 6 приведена гистограмма распределения, построенная на основе сгенерированных значений. Аналогичные сведения для ГСЧ 2Б приведены на рисунках 7 и 8. Как видно по гистограммам, столбцы, построенные по реально сгенерированным значениям, мало отличаются от идеальных. Это позволяет говорить о высоком качестве спроектированных генераторов.

Рисунок 1

Рисунок 2

Рисунок 3

Рисунок 4

Рисунок 5

Рисунок 6

Рисунок 7

Рисунок 8

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

3.1 Разработка структурной схемы

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

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

Рисунок 9

3.2 Расчет статистических показателей

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

Коэффициент готовности ЭВМ будет определяться как отношение времени нахождения ЭВМ в активном состоянии (когда она не сломана) ко времени работы системы:

Коэффициент загрузки ЭВМ найдем как отношение времени обработки сигналов на ЭВМ ко времени нахождения ЭВМ в активном состоянии (когда ЭВМ способна этим заниматься):

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

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

На основании структурной схемы построим алгоритмическую модель вычислительной системы, она показана на рисунке 10. Особенностью подхода при проектировании алгоритмической модели является использование объектно-ориентированного программирования, т. е. датчик, мультиплексный канал и ЭВМ представлены в виде объектов, которые взаимодействуют между собой. Это позволяет существенно упростить понимание имитационной модели, поскольку достигается высокий уровень абстрагирования. А все особенности работы скрыты внутри реализации классов. Не погружаясь в техники программирования, можно понять работу этой модели.

Рисунок 10

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

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

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

Когда будут выбраны необходимые опции, можно запустить процесс моделирования, для этого нужно нажать на кнопку Запуск. После завершения процесса моделирования на экране появится информация о модели и рассчитанные статистические показатели. На рисунке 11 показан пример работы программы.

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

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

25: Поступил сигнал от датчика

: Сигнал добавлен в канал

: Сигнал прочитан из канала

: Сигнал запущен на обработку

: Обработка сигнала завершена

: Поступил сигнал от датчика

: Сигнал добавлен в канал

: Сигнал прочитан из канала

: Сигнал запущен на обработку

: Обработка сигнала завершена

: Поступил сигнал от датчика

: Сигнал добавлен в канал

: Сигнал прочитан из канала

: Сигнал запущен на обработку

: Поступил сигнал от датчика

: Сигнал добавлен в канал

: Обработка сигнала завершена

: Сигнал прочитан из канала

: Сигнал запущен на обработку

: Поступил сигнал от датчика

: Сигнал добавлен в канал

Рисунок 11

Рисунок 12

5. Анализ результатов моделирования

Запустим программу на моделирование и исследуем выданные результаты. В поле На момент завершения моделирования отображено состояние модели в последнюю секунду имитации. Рассмотрим эти сведения:

Прошло времени: 1296000

Количество сигналов, сгенерированных датчиками: 42473

Количество сигналов, поступивших в канал (от датчиков и от ЭВМ): 42482

Количество сигналов, удаленных из канала из-за переполнения: 1728

Количество сигналов, поступивших из канала в ЭВМ: 40750

Количество сигналов, направленных обратно в канал из-за поломки ЭВМ: 9

Количество сигналов, обработанных в ЭВМ: 40740

Количество сигналов, находящихся в канале: 4

ЭВМ вышла из строя, раз: 9

ЭВМ была восстановлена, раз: 9

Состояние ЭВМ: активна

ЭВМ обрабатывает сигнал: да

Время нахождения ЭВМ в активном состоянии: 1284663

Время нахождения ЭВМ в состоянии восстановления: 11337

Время фактической обработки сигналов на ЭВМ: 1243722

Время, когда ЭВМ была в активном состоянии, но не обрабатывала сигналы: 40941

Видно, что количество сигналов поступивших в канал, больше количества сгенерированных датчиками сигналов. Это свидетельствует о том, что при поломке ЭВМ обрабатываемый сигнал возвращался обратно в канал. Найдем разность между количеством сигналов, поступивших в канал и количеством сигналов сгенерированных датчиками 42482 - 42473 = 9. Теперь обратим внимание на строку

Количество сигналов, направленных обратно в канал из-за поломки ЭВМ: 9

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

Теперь обратим внимание на строку

Количество сигналов, удаленных из канала из-за переполнения: 1728

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

...

: Поступил сигнал от датчика

: Сигнал добавлен в канал

: Обработка сигнала завершена

: Сигнал прочитан из канала

: Сигнал запущен на обработку

: Поступил сигнал от датчика

: Сигнал добавлен в канал

: Поломка ЭВМ

: Обрабатываемый сигнал направлен обратно в канал

: Сигнал добавлен в канал

: Поступил сигнал от датчика

: Сигнал добавлен в канал