Кому нужна математика? Понятная книга о том, как устроен цифровой мир - Андрей Райгородский

Допустим, у нас 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) задается формулами: