ГУАП
КАФЕДРА №41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
М.Н. Шелест |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №5
МОДЕЛИРОВАНИЕ ЭЛЕМЕНТАРНОЙ СМО С КОНЕЧНЫМ БУФЕРОМ
по курсу: Имитационное моделирование
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Нахождение экспериментальных зависимостей ( , 0, 0) ( , 0, 0) для элементарной системы массового обслуживания с буфером объема N.
Индивидуальный вариант
Индивидуальный вариант номер 10 в соответствии с таблицей 1.
Таблица 1 – Индивидуальный вариант задания
№ |
Закон распределения |
Закон распределения времени |
|
Объем |
|
входного потока заявок |
0 |
буфера |
|||
варианта |
обслуживания заявок обслуж( ) |
||||
заявок( ) |
|
N |
|||
|
|
|
|||
10 |
Эрланговский 6 порядка |
равномерный |
5 |
3 |
Ход работы
1. Формулы и графики законов распределения вероятностей для интервалов между заявками и времени обслуживания заявок.
Формула эрланговского распределения вероятностей закона распределения входного потока заявок заявок( ) для интервалов между заявками:
|
|
|
|
|
|
|
−1 |
|
− |
|
|
|
|
( ; , ) = |
|
|
|
|
|||
|
|
|
|
|
|
|||||
|
|
|
|
( − 1)! |
||||||
эрл( , ) = − |
1 |
∑ |
ln , где Ri – случайное число в диапазоне [0,1] |
|||||||
|
||||||||||
|
|
=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
График эрланговского распределения вероятностей 6 порядка закона распределения |
входного потока заявок заявок( ) для интервалов между заявками в соответствии с рисунком 1.
Рисунок 1 – График закона распределения вероятностей для интервалов между заявками
2
Формула равномерного распределения вероятностей закона распределения времени обслуживания заявок обслуж( ) для времени обслуживания заявок:
|
1 |
, |
[ , ] |
|
|
|
|||
|
( ) = { |
− |
||
|
0, |
|
[ , ] |
|
равн |
= ( − ) + , где Ri – случайное число в диапазоне [0,1] |
|||
|
|
|
|
График равномерного распределения вероятностей закона распределения времени
обслуживания заявок обслуж( ) для времени обслуживания заявок в соответствии с рисунком 2.
Рисунок 2 – График закона распределения вероятностей для времени обслуживания заявок
3
2.Описание разработанной программы: список использованных переменных,
список использованных функций, блок-схема, листинг.
Полный код программы в соответствии с Приложением А.
Список использованных переменных функций моделирования работы ЭСМО с конечным буфером в соответствии с таблицей 2.
Таблица 2 – Список используемых переменных
Название |
Описание |
|
переменной |
||
|
||
shape |
Порядок эрлановского распределения заданный вариантом |
|
mu_0 |
Интенсивностью обслуживания заданная вариантом |
|
is_test |
Статус тестовый или экспериментальный запуск программы |
|
lambd |
Список значений интенсивности входного потока |
|
a |
Левая граница равномерного распределения |
|
b |
Правая граница равномерного распределения |
|
buffer_size |
Размер буфера для ЭСМО |
|
t_empirical |
Список рассчитанного эмпирически среднего времени обслуживания |
|
заявки |
||
|
||
l |
Итератор по значениям списка интенсивности входного потока lambd |
|
Nu |
Теоретически рассчитанный коэффициент вариации обработки |
|
Rho |
Теоретически рассчитанный коэффициент загрузки системы |
|
L |
Теоретически рассчитанное среднее число заявок в системе |
|
t_theor |
Теоретически рассчитанное среднее время обслуживания заявки |
|
get_t_request |
Лямбда функция получения следующего момента поступления запроса |
|
get_t_work |
Лямбда функция получения следующего момента ОУ |
|
n |
Количество заявок, поступивших к данному моменту в СМО |
|
k |
Количество заявок, обслуженных к данному моменту в СМО |
|
m |
Количество заявок в буфере к данному моменту в СМО |
|
is_busy |
Статус занятости ОУ |
|
t_system |
Системное время ЭСМО |
|
t_request |
Следующий момент поступления заявки |
|
t_work |
Следующий момент освобождения ОУ |
|
t_request_Data |
Список моментов поступления заявок |
|
t_work_Data |
Список моментов освобождения ОУ |
|
q_Old |
Старая оценка производительности системы |
|
q_Data |
Список оценок производительности системы |
|
loop_cnt |
Счетчик итераций цикла |
|
q_New |
Текущая оценка производительности системы |
|
t_me_New |
Текущая оценка среднего времени нахождения запроса в системе |
|
t_empirical |
Список среднего времени пребывания запроса |
|
q_empirical |
Список оценки производительности системы |
Код функций в соответствии с листингом 1.
Листинг 1 – Функция построения графиков для модели СМО
def model(shape, lambd, a, b, mu_0, buffer_size=1, is_test=False):
'''Функция моделироваиня СМО'''
#Лямбда ф-ция получения случайного значения распределения
#Эрланговского для закона распределения входного потока заявок
get_t_request = lambda : np.random.exponential(1/lambd) if is_test \ else st.erlang.rvs(a=shape,
4
scale=1/(lambd*shape))
# Равномерного для закона распределения времени обслуживания заявок get_t_work = lambda : np.random.exponential(1/mu_0) if is_test \
else np.random.uniform(a, b)
#Количество заявок, поступивших / обслуженных / в буфере к данному моменту в СМО
n, k, m = 0, 0, 0
#Статус занятости ОУ
is_busy = False
#Системное время t_system = 0
#Следующий момент поступления заявки t_request = get_t_request()
#Следующий момент освобождения ОУ
t_work = t_request
#Список времени моментов поступления заявок t_request_Data = np.array([])
#Список времени моментов освобождения ОУ
t_work_Data = np.array([])
q_Old = 2**32
q_Data = np.array([])
#Старая оценка среднего времени пребывания запроса t_me_Old = 2 ** 32
#Счетчик итераций цикла
loop_cnt = 0
# Моделируем СМО while True:
loop_cnt += 1 # Увеличиваем счетчик цикла
# Проверяем наступило ли время освобождения ОУ if t_request <= t_work:
#Записываем в системное время момент поступления заявки t_system = t_request
#Сохраняем в список момент поступления заявки
#t_request_Data = np.append(t_request_Data, t_request) if not is_busy or m < buffer_size:
t_request_Data = np.append(t_request_Data, t_request)
#Создаем новое значение
t_request_New = get_t_request()
# Сохранение для посдчета интенсивности входного потока q_Data = np.append(q_Data, t_request_New)
n += 1 # Увеличиваем |
счетчик поступивших заявок |
# Проверяем занято ли |
ОУ |
if not is_busy: |
|
is_busy = True # |
Устанавливаем статус ОУ в положение занято |
# Вычисляем следующий момент освобождения ОУ |
|
t_work = t_system |
+ get_t_work() |
#Добавлием заявку в буфер, только если в нем есть свободное место elif m < buffer_size:
m += 1
#else: print('ОТКАЗ', not is_busy or m < buffer_size)
#Вычисляем следующий момент поступления заявки, только если
заявка попала в буфер
5
t_request = t_system + t_request_New else:
#Записываем в системное время момент освобождения ОУ t_system = t_work
k += 1 # Увеличиваем счетчик обслуженных заявок
#Сохраняем в список момент освобождения ОУ
t_work_Data = np.append(t_work_Data, t_work)
# Проверяем есть ли заявки в буфере if m > 0:
m -= 1 # Берем заявку из буфера
# Вычисляем следующий момент освобождения ОУ t_work = t_system + get_t_work()
else:
#Устанавливаем статус ОУ в положение свободно is_busy = False
#Устанавливаем следующий момент освобождения ОУ t_work = t_request
#Проводим отценку каждые 1000 итераций цикла
if loop_cnt % 1000 == 0:
# Высчитываем среднее время обслуживания заявки
t_me_New = np.mean(t_work_Data - t_request_Data[:len(t_work_Data)])
#Расчет оценки производительности системы q_New = (k/n) / np.mean(q_Data)
#Проверка достаточности условия выхода
if np.abs((t_me_New - t_me_Old)/t_me_Old) < 0.01 \
or np.abs((q_New - q_Old)/q_Old) < 0.001: return t_me_New,
q_New
q_Old = q_New
t_me_Old = t_me_New # Перезаписываем среднее время обслуживания
заявки
def modeling_experimental_dependence(shape, mu_0, buffer_size = 10000, is_test = False):
'''Функция построения графиков для модели СМО'''
#Генерация списка значений интенсивности входного потока lambd = np.linspace(0.1,1,10) * mu_0
#Расчет границ для равномерного распределения
a= 1 / mu_0 - 0.05 * mu_0
b= a + 0.1 * mu_0
# Список среднего времени пребывания запроса t_empirical = np.array([])
#Список оценки производительности системы q_empirical = np.array([])
#Заполнение списка значений среднего времени пребывания запроса for l in lambd:
t_empirical_val, q_empirical_val = model(shape, l, a, b, mu_0,
buffer_size, is_test)
t_empirical = np.append(t_empirical, t_empirical_val) q_empirical = np.append(q_empirical, q_empirical_val)
# print('-----------------------------------------------------------
----') |
# |
TEST PRINT |
TEST |
|
|
|
print('t_empirical', |
t_empirical, |
'\nq_empirical', |
q_empirical, |
|||
end='\n\n') |
# TEST |
PRINT TEST |
|
|
if not is_test:
#Построение графика эрланговского распределения
#для закона распределения входного потока заявок
ploting_erlang_distribution(k=shape, lmbda=1/(np.mean(lambd)*shape),
6
N=10000)
#Построение графика равномерного распределения
#для закона распределения времени обслуживания заявок ploting_uniform_distribution(a=a, b=b)
#Создаем объекты графиков
fig, axis = plt.subplots(1, 2, figsize=(15, 7))
fig.suptitle('Статистика для ЭСМО c буффером размера
{}'.format(buffer_size), fontsize=16)
# Построение графика if is_test:
lambd = lambd[lambd != mu_0]
#Теор.знач. коэф загрузки системы
Rho = lambd / mu_0
# Расчет теор. значения среднего времени пребывания запроса в системе t_theor = [ 1/lambd[j] * sum( (i * (1-Rho[j]) * Rho[j]**i) / (1 - Rho[j]**(buffer_size+1)) for i in range(buffer_size+2) ) for j in
range(len(lambd))]
#Теор.знач. вероятности потери запроса
p_Fail = ((1-Rho) * Rho**buffer_size) / (1-Rho**(buffer_size+1))
#Теор.знач. производительности ситсемы q_theor = lambd * (1-p_Fail)
# Построение графика георитически расчитанного значения
axis[0].plot(lambd[:len(q_theor)], |
q_theor, |
label='Теоретическое |
||
значение', color='red') |
|
|
|
|
# Построение графика теоритически расчитанного значения |
||||
axis[1].plot(lambd[:len(t_theor)], |
t_theor, |
label='Теоретическое |
||
значение', color='red') |
|
|
|
|
# Построение графика экспериментально полученного значения |
||||
axis[0].plot(lambd[:9], |
q_empirical[:9], |
label='Экспериментальное |
||
значение', color='black') |
|
|
|
|
axis[0].set_title("График зависимости производительность системы\nот |
||||
интенсивности входного потока") |
|
|
|
|
axis[0].set_ylabel('Производительность системы') |
|
|
||
# Построение графика экспериментально полученного значения |
||||
axis[1].plot(lambd[:9], |
t_empirical[:9], |
label='Экспериментальное |
||
значение', color='black') |
|
|
|
|
axis[1].set_title("График зависимости среднего |
времени пребывания |
|||
запроса\nот интенсивности входного потока") |
|
|
|
|
axis[1].set_ylabel('Ср. t в системе') |
|
|
|
for ax in axis.flat:
ax.set_xlabel('Инт. входного потока') ax.grid()
ax.legend()
plt.show()
return t_empirical
7
3. Теоретический и экспериментальный графики зависимостей производительности СМО и среднего времени задержки запроса от интенсивности входного потока для тестового примера в соответствии с рисунками -.
Рисунок 3 – График зависимости λ от T для тестового Пуассоновского входного потока
8
4. Провели моделирование для получения требуемой экспериментальной зависимости при λ = 0.1µ0, 0.2µ0, …, 1µ0. Полученные данные внесли в таблицу 4.
Таблица 4 – Зависимость среднего времени пребывания запроса от интенсивности входного потока
λ |
0.1µ0 |
0.2µ0 |
0.3µ0 |
0.4µ0 |
0.5µ0 |
0.6µ0 |
0.7µ0 |
0.8µ0 |
0.9µ0 |
1µ0 |
|
|
|
|
|
|
|
|
|
|
|
T |
0,197 |
0,204 |
0,205 |
0,216 |
0,229 |
0,256 |
0,290 |
0,377 |
0,447 |
0,508 |
|
|
|
|
|
|
|
|
|
|
|
Q |
0,497 |
1,004 |
1,503 |
1,956 |
2,533 |
2,978 |
3,472 |
3,892 |
4,255 |
4,502 |
|
|
|
|
|
|
|
|
|
|
|
Экспериментальные графики зависимостей производительности СМО и среднего времени задержки запроса в СМО от интенсивности входного потока для своего варианта в соответствии с рисунками -.
Рисунок 4 – График зависимости λ от T для тестового Пуассоновского входного потока
9
Вывод
Входе данной лабораторной работы мы познакомились с элементарными системами массового обслуживания (ЭСМО) с конечным буфером, и смоделировали работу одной из таких систем.
Всмоделированной нами ЭСМО был реализован эрланговский закон распределения
6 порядка для входного потока заявок и равномерный закон распределения времени обслуживания заявок.
Разработанная программа моделировала случайное время появления заявок и время их обслуживания. В зависимости от параметров времени и заполненности буфера она принимала решения об обработках заявок, а мы фиксировали время поступления и обслуживания заявок, по которым потом определяли среднее время нахождения заявки в системе. Расчет средних значений позволил нам построить график зависимости среднего времени пребывания запроса от интенсивности входного потока. Расчеты были проведены при разных значениях интенсивности в диапазоне значений λ = 0.1µ0, 0.2µ0, …, 1µ0, поэтому на графике явно видно, что чем больше интенсивность тем больше среднее время обслуживания. Полученный результат согласуется с нашими представлениями об ЭСМО с постоянным входным потоком и временем обслуживания заявок.
10