Вероятности и неприятности. Математика повседневной жизни

Пусть в нашей M/M/1-очереди с вероятностью ε могут появляться особые клиенты, назовем их VIP (very impatient person — очень нетерпеливые персоны), которые встают не в конец очереди, а вклиниваются в ее начало, заставляя ждать всех стоящих позади. При этом они всё же дают оператору завершить работу с текущим клиентом, не прерывая его. Если внеочередников наберется несколько, они могут образовать свою VIP-очередь. Вспомним, что пуассоновский поток можно представить как случайное «разбрасывание» по временному интервалу какого-то известного количества событий. Поскольку все клиенты приходят независимо, то, согласно нашему условию, мы получим поток нетерпеливых клиентов ελ и поток обычных клиентов (1–ε)λ, при этом общий поток останется неизменным. Среднее время ожидания для VIP будет равно  как в простой M/M/1-очереди, поскольку они в своей VIP-очереди «не замечают» присутствия обычных клиентов. Для того, кто ждет на общих основаниях, время ожидания вырастет и составит уже:

Как показывает рисунок 7.9, пока VIP-ов немного, очереди они мешают не сильно. Но если доля внеочередников оказывается близкой к единице, то никакого преимущества они уже не имеют, зато немногочисленным скромным очередникам приходится ждать существенно дольше. При ε, стремящемся к единице, среднее время ожидания рядовых очередников стремится к μ/(μ — λ)² (больше двух часов в нашем случае!); и вообще, если μ лишь немного превышает λ, очередь остается устойчивой, однако время ожидания в ней вырастает катастрофически!

Рис. 7.9. Соотношение средних времен ожидания для очереди с нетерпеливыми VIP-клиентами

Но вот что любопытно. Можно найти среднее время ожидания для всей группы клиентов как взвешенную сумму εW_VIP + (1 — ε)W₀, и она окажется равной 1/(μ — λ)², то есть такой же, как для обыкновенной M/M/1-очереди без всяких VIP-ов. Выходит, системе в целом внеочередники не мешают. На время занятости оператора они тоже не влияют, распределение времен ожидания остается экспоненциальным. Мы уже говорили в предыдущей главе, что для экспоненциального распределения кривая Лоренца и, соответственно, коэффициент Джини не зависят от параметра распределения, а значит, все M/M/1-очереди имеют одинаковую степень несправедливости — 0,5. Отсюда следует, что наш обобщенный критерий несправедливости для всех ожидающих в очереди также останется равным 0,5.

Стационарный бардак

А теперь немного изменим политику очередности. Пусть внеочередники будут сверхнаглыми, и если так случится, что один такой клиент придет вслед за другим, то вместо формирования нормальной очереди второй вклинится перед первым. Эта задача уже отличается от классического подхода к очередям с приоритетом. Давайте сразу рассмотрим предельный случай, когда доля наглых клиентов равна единице. Тогда наша очередь (рис. 7.10) превращается в то, что программисты называют стеком, — последовательность элементов, подчиняющуюся правилу «первым вошел, последним вышел» (FILO — first in, last out) — в противовес очереди, для которой выполняется правило «первым вошел, первым вышел» (FIFO — first in, first out).

Рис. 7.10. Очередь как стек

Такая «очередь наоборот» выглядит неестественно, но если вместо людей мы рассмотрим пачку документов, то можем увидеть знакомую картину на рабочем столе, когда входящие документы не сортируются по времени, складываются в стопку по мере поступления, а потом обрабатываются начиная сверху. Удивительно, но в стационарном состоянии все средние значения основных параметров — и длины очереди, и времени ожидания, и времени занятости оператора — будут точно такими же, как и в FIFO-очереди. Что же поменяется? Посмотрим на пример работы такой очереди, он показан на рис. 7.11. Мы видим, что вместо целенаправленного движения к оператору клиенты могут то приближаться к нему, то отдаляться. Время ожидания для самого последнего клиента существенно удлиняется, однако, пока он ждет, через оператора проходит много вновь поступающих клиентов, которые обрабатываются почти мгновенно. В среднем же мы получаем примерно такое же время ожидания, как для «нормальной» очереди. Но мы уже много раз убеждались в том, что среднее значение не может характеризовать случайную величину в полной мере.

Рис. 7.11. Динамика FILO-очереди или стопки документов, которые при поступлении кладутся наверх и обрабатываются начиная сверху. Как и прежде, темные точки соответствуют каждому седьмому клиенту