Анализ метода выбора из двух

Допустим, у нас n серверов. Заявки (или задания) поступают с интенсивностью ?_n в единицу времени, и каждый сервер в среднем обрабатывает одно задание в единицу времени, то есть загрузка системы равна ? < 1 (если ? ?1, то система перегружена, очередь будет расти до бесконечности). Рассмотрим случай, когда n очень велико и стремится к бесконечности.

Обозначим через f_k долю серверов, у которых ровно k заявок (заявка, которая находится на обслуживании в данный момент, тоже учитывается). Обозначим через u_k долю серверов, у которых заявок k или больше. Значения u_k можно легко получить через f_k и наоборот:

Понятно, что u₀ = 1.

Представим, что система находится в равновесии. Тогда у нас в среднем

серверов, на которых ровно k заданий. Все эти серверы обрабатывают задания со скоростью одно задание в единицу времени. Другими словами, количество серверов с k заявками или больше уменьшается на n(u_k ? u_k+1) в единицу времени.

Теперь давайте посмотрим, на сколько количество серверов с k заявками или больше увеличивается в единицу времени. Чтобы увеличить число таких серверов, заявки должны поступать на серверы, у которых в данный момент k ? 1 заявка. При методе выбора из двух вероятность того, что новое задание попадет на сервер с k или больше заявками, равна

потому что в этом случае оба случайно и независимо выбранных сервера должны иметь k или больше заявок, и для каждого из двух серверов эта вероятность и_k[26]. Значит, вероятность того, что новая заявка поступит на сервер, у которого ровно k ? 1 заявка, равна

Поскольку заявок в единицу времени поступает ?п, то получается, что число серверов с k или больше заявками в единицу времени в среднем увеличивается на

Так как система находится в равновесии, число серверов с k или больше заявками должно оставаться неизменным, то есть (П.9) равняется (П.11). Отсюда получаем уравнение баланса:

Результат, приведенный в работе{34}, говорит, что при определенных общепринятых предположениях о законе поступления заданий и времени их выполнения, в пределе для бесконечного количества серверов, уравнение (П.12) действительно описывает равновесное состояние системы. Это достаточно сложный технический результат. Нетрудно проверить или даже догадаться, что решение уравнения (П.12) задается формулами:

Это так называемый двойной экспоненциальный закон. Двойка в формуле, та самая двойка – вторая степень – из выражения (П.10). Точно так же мы могли бы выбирать не из двух, а из r серверов и получили бы

Интересно заметить, что при тех же предположениях, но случайном выборе одного сервера, изменятся выражения (П.10) и, соответственно, (П.11). Действительно, на этот раз заявка выбирает только один сервер и вероятность попасть на сервер с k или больше заявками равна просто и_k. Тогда вместо (П.12) получаем классическое уравнение баланса:

решение которого задается известной формулой Эрланга:

Очевидно, что и_k в формуле (П.13) убывает гораздо быстрее.

Именно эти формулы мы использовали в табл. 5.1. В нашем случае ? = 0,9, и в таблице мы привели значения f_k. В первой колонке – значения k, во второй – значения f_k, подсчитанные по формуле (П.14), в третьей – значения f_k, подсчитанные по формуле (П.13).

Назад к Главе 5