Исправленные упражнения: Очередь

Контенус

Исправленные упражнения: Очередь

Приведенные ниже исправленные упражнения касаются Цепи Маркова в непрерывном времени и, в частности, понятие очередь ожидания.

Упражнение 1

Система клиент-сервер получает в среднем 1000 запросов в секунду, поступающих в процесс Пуассона. Он имеет один сервер, который может обрабатывать в среднем 2000 клиентов в секунду. Предполагается, что время обслуживания заявки распределено по экспоненциальному закону. Рассчитайте вероятность того, что время обслуживания превысит 2 мс.

Каков процент отклоненных клиентов для системы без очереди.

Тот же вопрос по системе с очередью 1 место. Рассчитайте скорость приложения сервера.

Тот же вопрос для системы с очередью из 2-х мест.

Решение

Выбрав миллисекунду в качестве единицы времени, мы получаем рождаемость 1 и смертность 2. Время обслуживания T_С требования подчиняется экспоненциальному закону с параметром 2, поэтому вероятность того, что время обслуживания превысит две секунды, составляет 0,0183 благодаря следующей формуле:

Строка (a) представляет вместимость в очереди из 0 мест, а строка (b) представляет вместимость в очереди в 1 место. Для каждого нового места просто добавьте штат.

Для первой цепочки рассчитаем стационарное распределение:

Таким образом, у нас есть 1/3 клиентов, отклоненных (если мы находимся 1/3 времени в состоянии 1, то мы больше не можем принимать клиентов на 1/3 операции очереди). Заполняемость равна пи₀ = 2/3.

Для второй цепочки рассчитаем стационарное распределение:

А для емкости 2 в очереди получаем пи₃ = 1/15 и пи₀ = 8/15.

Упражнение 2

Система клиент-сервер получает в среднем 1000 запросов в секунду, поступающих в соответствии с пуассоновским процессом. В качестве эксперимента предполагается система без очереди, но состоящая из нескольких фронт-серверов. Когда все серверы заняты, запросы отклоняются.

Каков процент отклоненных клиентов для системы с 1 сервером, обрабатывающим 4000 запросов в секунду?

Тот же вопрос для системы с двумя серверами, каждый из которых обрабатывает 2000 запросов в секунду.

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

Решение

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

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

Для сервера: 1/5

Для двух серверов: 1/13

Для четырех серверов: 1/65

Упражнение 3

Грузовики прибывают на станцию техобслуживания для прохождения испытаний на безопасность по методу Пуассона со скоростью 6 раз в день. Продолжительность испытаний для каждого грузовика составляет экспоненциальный диапазон математического ожидания 1 час 30 минут. Предполагается, что процесс прибытия не останавливается и станция работает круглосуточно.

Допускает ли система стационарное распределение?

Если это так, рассчитайте его и укажите среднее количество пользователей в системе, среднее время, проведенное в системе, среднюю длину очереди и среднее время, проведенное в очереди (в устойчивом состоянии).

Решение

У нас лямбда=1/4 и мю=2/3 (в часах). Поскольку rho=3/8<1, система эргодический. По формулам расчета параметров систем М/М/1, Мы будем иметь :

Средняя длина очереди и время ожидания в очереди определяются по формуле:

Упражнение 4

Строительная компания имеет две одинаковые машины, каждая из которых может выходить из строя независимо от другой по пуассоновскому процессу с частотой 5 раз в месяц. Предполагается, что продолжительность ремонта равна va, которая подчиняется экспоненциальному закону с параметром mu (коэффициент обслуживания). При каком значении mu обе машины будут находиться в рабочем состоянии одновременно не менее половины времени?

Решение

Система моделируется процессом рождения и смерти с тремя состояниями (0, 1 или 2 машины отключены) со следующей диаграммой перехода:

У нас есть :

Отсюда

p0 — стационарная вероятность того, что две машины будут в рабочем состоянии, мы должны иметь:

Учитывая положительность мю, мы должны иметь

Поэтому будет необходимо иметь уровень обслуживания, по крайней мере, равный 13,660254 чтобы обе машины находились в рабочем состоянии хотя бы половину времени.

Упражнение 5

Прачечная имеет 3 одинаковые и независимые машины. Время работы каждой машины не зависит от прошлого и подчиняется экспоненциальному закону ожидания двух дней. Сломавшуюся машину чинит техник; время ремонта - однодневное ожидание. В прачечной работает только один техник.

Нарисуйте схему перехода.

Какова доля времени, когда все машины работают и когда все машины выключены?

Каково среднее количество работающих машин? Каково среднее количество обездвиженных машин?

Решение

Предположим, что состояние Ej обозначает состояние, в котором j машин обездвижены. Имеем следующую схему переходов:
Имеем в стационарном состоянии следующие уравнения: Отсюда
Таким образом, нужные дроби составляют 4/19 (для всех работающих машин) и 3/19 (для всех остановленных машин).
Среднее количество машин в рабочем состоянии: 4*(4/19)+2*(6/19)+1*(6/19)=30/19. А среднее количество обездвиженных машин 9/19+12/19+6/193.

Упражнение 6

Сервер базы данных получает в среднем 100 запросов в секунду, поступающих в соответствии с пуассоновским процессом. Время обработки запроса подчиняется экспоненциальному закону с параметром µ. Когда сервер занят, запросы сохраняются на большом диске для последующей обработки в порядке очереди. На рынке существует 4 различных типа серверов, которые могут соответственно обрабатывать 100, 150, 200 или 300 запросов в секунду при непрерывной работе.

Что будет, если мы планируем установить сервер, способный обрабатывать 100 запросов в секунду?

Мы хотим, чтобы клиент, отправивший запрос, получил ответ в среднем через 1/100 секунды. Какой тип сервера мне нужен?

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

Решение

Это очередь M/M/1, поэтому мы можем использовать законы Литтла. Есть стационарное распределение, если λ/µ<1, если взять сервер, который обрабатывает 100/секунду, то имеем λ/µ=1 цепочка не эргодическая (бесконечное накопление запросов)!

Если нам нужно время отклика 1/100 секунды, нам нужно решить уравнение 1/100=E(T)=1/( μ – λ), поэтому μ=200 запросов в секунду.

Запросы перенаправляются, если в системе уже есть 8 запросов. Так происходит перенаправление, когда система достигает 9 запросов в системе. Просто посчитайте π₉ узнать вероятность того, что запрос будет перенаправлен. По закону Литтл Пи₉ = (1 – ρ) ρ⁹ =1/1024.

Так как система получает 100 запросов в секунду, вспомогательный сервер получает 100/1024 запросов в секунду.

Упражнение 7

На автомобильном заводе изучалась задача определения оптимального количества работников, размещаемых за прилавками магазина, ответственными за снабжение рабочих необходимым инструментом. Исследование магазина началось с определения статистических характеристик приходов рабочих (1,6 приходов/минуту) и времени, затраченного работниками на предоставление запрошенных инструментов (0,9 услуг/минуту).

Рассчитайте среднее время ожидания в очереди (W_д) для S=2, S=3, S=4. Рассчитайте среднее количество клиентов за 8-часовой рабочий день и соответствующее среднее время обслуживания. Исходя из количества работников (S), рассчитайте количество часов простоя за 8-часовой рабочий день.

Подсчитайте время, ежедневно теряемое работниками из-за ожидания? Если почасовая себестоимость работника составляет 40,00 $, а рабочего — 80,00 $, какова общая стоимость потерянных часов?

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

Решение

Зная l и m, мы вычислили l/m = 1,6/0,9 = 1,77 > 1.

Поскольку l/m > 1, нас интересовали только значения S=2, S=3 и S=4.

Для расчета среднего времени ожидания в очереди мы сначала искали P₀, для каждого соответствующего значения S.

С=2, П₀ = 0,061 S=3, Р₀ = 0,152 S=4, Р₀ = 0.166

Которые дают

S=2, Вт_д = 4.00

С=3, Вт_д = 0.31

С=4, Вт_д = 0.06

Теперь посчитаем среднее количество клиентов за 8-часовой рабочий день.

лк 60 х 8 = 1,6 х 60 х 8 = 768

и для этого числа приходов потребуется (при времени обслуживания 1/м)

768/м = 768/0,9 = 853 минуты обслуживания в день.

= 14:21

Упражнение 8

Лаборатория содержит 2 одинаковых микрокомпьютера. Пользователи приходят по пуассоновскому процессу с параметром l = 3 пользователя в час. Продолжительность использования микрокомпьютера экспоненциальна, в среднем 0,6 часа (m = 1/0,6).

– Коэффициент использования лаборатории

– Количество пользователей в очереди

- Время ожидания в очереди

Босс считает, что люди тратят слишком много времени на ожидание, и решает добавить микрокомпьютеры. Он хочет, чтобы среднее время ожидания составляло менее 20 минут. Сколько он должен добавить? Каков новый коэффициент использования лаборатории?

Что произойдет с точки зрения времени ожидания пользователей, если мы разделим их на 3 группы, назначив каждой группе микрокомпьютер?

Какой вывод?

Решение

У нас очередь M/M/2.

г = 1/2м = 0,9

P0 = 1/19 P1 = л/м P0 = 1,8/19

Q = [r/1-r] (1 – P0 – P1) = 7,674

Wq = 2,56 ч

Система используется только на 90%, но каждому пользователю приходится ждать в среднем более 2,5 часов.

Мы можем попробовать с несколькими значениями S = s и вычислить Wq для каждого случая:

с=3

Q=0,532

Wq=0,177 ч. » 10,6 мин.

С 3 микрокомпьютерами ограничение выполняется, но коэффициент использования системы теперь равен r = 0,6.

Что произойдет, если мы разделим пользователей на 3 группы, назначив каждой группе микрокомпьютер?

Теперь у нас есть 3 очереди M/M/1, каждая из которых имеет скорость прибытия l = 3/3 = 1, скорость обслуживания m = 1/0,6 и коэффициент использования r = 0,6.

Мы получаем :

Wq = r²/[l(1-r)] = 0,9 часа

= 54 мин.

Поэтому предпочтительнее делиться ресурсами.

Тем самым,

S = 2 сотрудника будут иметь 2 x 8 – 14,21 = 1,79 часа бездействия в день.

S = 3 сотрудника будут иметь 3 x 8 - 14,21 = 9,79 часов бездействия в день.

S = 4 сотрудника будут иметь 4 x 8 - 14,21 = 17,79 часов бездействия в день.

Давайте теперь найдем время, ежедневно теряемое рабочими из-за ожидания:

S = 2768 х 4 = 3072 мин. = 51,2 часа

S = 3768 х 0,31 = 238 мин. = 3,96 часа

S = 4768 х 0,06 = 46 мин. = 0,76 часа

Общая стоимость потерянных часов составляет:

S = 2 $ 4 167,60 = 1,79 х 40 + 51,2 х 80

S = 3 $ 708,40 = 9,79 х 40 + 3,96 х 80 лучший!

S = 4 $ 772,40 = 17,79 х 40 + 0,76 х 80