Все мы стояли в разных очередях. Утомительное стояние, сидение или даже лежание в очереди может навести на рассуждения о неустроенности нашего мира или о вреде бюрократии. Однако вынужденное безделье можно заполнить интересной и небесполезной математикой.
Продолжаем исследовать законы подлости вместе с теорией вероятностей и прочей другой математикой. В этой серии статей я привожу выдержки из своей книжки Вероятности и неприятности. Первая часть, посвящённая очередям, рассказывала об основном инструментарии теории очередей или теории массового обслуживания.
Есть в нашей жизни досадное явление — «обочечники». Это ушлые водители, объезжающие пробку по обочине и потом встревающие в поток. Есть настырные посетители поликлиник и касс, норовящие просочиться к заветному окошку или двери с формулой «Мне только спросить…». В любую отлаженную бюрократическую систему то и дело врываются неотложные дела, не терпящие промедления. Понятно, что порой без таких случаев не обойтись: в больницах бывают неотложные пациенты, в операционной системе компьютера есть задачи с очень высоким приоритетом; наконец, на дороге мы обязаны пропускать спецтранспорт, едущий по экстренному случаю. Но как внеочередники влияют на всю очередь? Подобные случаи моделируются очередями с приоритетом, и для них тоже есть развитая теория, поскольку в жизни они встречаются чуть ли не чаще простых очередей.
Пусть в нашей M/M/1-очереди (о том что значит это обозначение мы говорили в первой части), с вероятностью ε могут появляться особые клиенты, назовем их VIP (very impatient person — очень нетерпеливые персоны), которые встают не в конец очереди, а вклиниваются в ее начало, заставляя ждать всех стоящих позади. При этом они всё же дают оператору завершить работу с текущим клиентом, не прерывая его. Если внеочередников наберётся несколько, они могут образовать свою VIP-очередь. Вспомним, что пуассоновский поток можно представить как случайное «разбрасывание» по временному интервалу какого-то известного количества событий. Поскольку все клиенты приходят независимо, то, согласно нашему условию, мы получим поток нетерпеливых клиентов ελ и поток обычных клиентов (1 – ε) λ, при этом общий поток останется неизменным. Среднее время ожидания для VIP будет равно
как в простой M/M/1-очереди, поскольку они в своей VIP-очереди «не замечают» присутствия обычных клиентов. Для того, кто ждет на общих основаниях, время ожидания вырастет и составит уже:
Как показывает рисунок, пока VIP-ов немного, очереди они мешают не сильно. Но если доля внеочередников оказывается близкой к единице, то никакого преимущества они уже не имеют, зато немногочисленным скромным очередникам приходится ждать существенно дольше. При ε, стремящемся к единице, среднее время ожидания рядовых очередников стремится к μ/(μ – λ)² (больше двух часов в нашем случае!); и вообще, если μ лишь немного превышает λ, очередь остается устойчивой, однако время ожидания в ней вырастает катастрофически!
Но вот что любопытно. Можно найти среднее время ожидания для всей группы клиентов как взвешенную сумму
и она окажется равной 1/(μ – λ)², то есть такой же, как для обыкновенной M/M/1-очереди без всяких VIP-ов. Выходит, системе в целом внеочередники не мешают. На время занятости оператора они тоже не влияют, распределение времен ожидания остается экспоненциальным. Мы уже говорили в предыдущей главе, что для экспоненциального распределения кривая Лоренца и, соответственно, коэффициент Джини не зависят от параметра распределения, а значит, все M/M/1-очереди имеют одинаковую степень несправедливости — 0,5. Отсюда следует, что наш обобщенный критерий несправедливости для всех ожидающих в очереди также останется равным 0,5.
Стационарный бардак
А теперь немного изменим политику очередности. Пусть внеочередники будут сверхнаглыми, и если так случится, что один такой клиент придет вслед за другим, то вместо формирования нормальной очереди второй вклинится перед первым. Эта задача уже отличается от классического подхода к очередям с приоритетом.
Давайте сразу рассмотрим предельный случай, когда доля наглых клиентов равна единице. Тогда наша очередь превращается в то, что программисты называют стеком, — последовательность элементов, подчиняющуюся правилу «первым вошел, последним вышел» (FILO — first in, last out) — в противовес очереди, для которой выполняется правило «первым вошел, первым вышел» (FIFO — first in, first out).
Такая «очередь наоборот» выглядит неестественно, но если вместо людей мы рассмотрим пачку документов, то можем увидеть знакомую картину на рабочем столе, когда входящие документы не сортируются по времени, складываются в стопку по мере поступления, а потом обрабатываются начиная сверху. Удивительно, но в стационарном состоянии все средние значения основных параметров — и длины очереди, и времени ожидания, и времени занятости оператора — будут точно такими же, как и в FIFO-очереди. Что же поменяется? Посмотрим на пример работы такой очереди, он показан на рисунке.
Мы видим, что вместо целенаправленного движения к оператору клиенты могут то приближаться к нему, то отдаляться. Время ожидания для самого последнего клиента существенно удлиняется, однако, пока он ждет, через оператора проходит много вновь поступающих клиентов, которые обрабатываются почти мгновенно. В среднем же мы получаем примерно такое же время ожидания, как для «нормальной» очереди. Но мы уже много раз убеждались в том, что среднее значение не может характеризовать случайную величину в полной мере.
Глядя на динамику FILO-очереди, легко понять, что время ожидания клиента должно быть близким к времени занятости оператора. Действительно, время занятости определяется как период от момента прихода первого клиента до момента выхода последнего, но в стеке первый клиент и оказывается последним. Нужно еще учесть, что очередной клиент не прерывает оператора, поэтому ко времени его ожидания добавится время обслуживания клиента, с которым уже работает сотрудник. Если оно распределено экспоненциально, то, как уже обсуждалось в связи со временем ожидания автобуса, добавочное время будет распределено точно так же. В итоге время ожидания окажется распределено как сумма времени занятости оператора и периода работы с одним клиентом. На рисунке показаны распределения времени ожидания для M/M/1-очередей: обыкновенной, с политикой FIFO, придерживающейся правила FILO. В обоих случаях λ = 30 и μ = 34 человека в час.
Распределения сильно различаются, но средние значения у них практически одинаковые. Хотя распределение времени ожидания для FILO-очереди кажется сконцентрированным около моды (близкой к 1/μ, времени работы с одним клиентом), у него длинный тяжелый хвост, который сильно увеличивает дисперсию и повышает среднее значение. Медиана этого распределения равна 3 минутам. Это значит, что в половине случаев клиент будет ждать немного, но если уж застрянет, так застрянет: 5% клиентов потратят больше часа, а самые невезучие 2% вместо 2 минут вынуждены будут ждать своей очереди больше 2 часов! Для FIFO-очереди с такими же параметрами вероятность застрять на 2 часа составляет не более 0,04%.
При этом оператор, то есть бюрократ, обрабатывающий бумаги, не заметит разницы между очередью и стеком: распределение его времени занятости не изменится. Руководитель бюрократа тоже увидит, что из кабинета подчиненного бумаги выходят с нормальной интенсивностью в силу устойчивости очереди. И большинство документов даже окажутся обработаны очень оперативно. Но то и дело какая-то их часть внезапно «проваливается» на дно стопки и задерживается там очень надолго. Такие дела приходится «двигать вручную» тем, кто в них заинтересован.
Подобная картина наблюдается и в шкафу, куда мы складываем вещи с мыслью разобрать потом. Но мы задвигаем то, что уже лежит там, поглубже и добавляем новые вещи. Так что даже если мы и станем их постепенно разбирать, до «ископаемых» у самой стенки руки дойдут очень и очень нескоро.
Для демонстрации несправедливости распределения времени между различными делами в ведомстве бюрократа (или вещами в шкафу) изобразим кривые Лоренца для FIFO- и FILO-очередей, описываемых формулой M/M/1. Если для всех FIFO-очередей кривая Лоренца одинакова, несправедливость FILO-очередей зависит от соотношения λ и μ. Чем ближе их отношение к единице, тем ближе к ней и индекс Джини. На рисунке показаны кривые Лоренца для этих двух типов очередей с теми же параметрами, что и для предыдущего рисунка.
Хотели как лучше...
Закон сохранения клиентов, или равенство входного и выходного потоков, может сыграть еще одну злую шутку. Представьте себе контору, через которую проходит за рабочий день, скажем, 15 человек; при этом на каждого клиента в среднем уходит полчаса. В конторе два клерка, один трудится с интенсивностью 16 человек в день, а второй — 14. Вместе они могли бы обслужить человек тридцать, но, кажется, столько и не нужно. Люди в такой конторе почти не ждут своей очереди, среднее время ожидания составляет 18 минут, средняя длина очереди всего 1,2 человека. Очень часто бывает так, что, пока с клиентом работает кто-то из клерков, второй в это время отдыхает. На рисунке показан пример динамики очереди в конторе.
При этом надо иметь в виду, что этот незначительный поток распределён между двумя операторами: каждый из них наблюдает поток, еще в два раза менее интенсивный. Про такую работу говорят: «не бей лежачего».
Руководство, проведя все эти замеры и наблюдения, решает, что клерки живут уж больно вольготно, трудясь только половину рабочего времени, и в стремлении оптимизировать работу учреждения увольняет нерасторопного клерка. И вот все стало совсем иначе!
Система приблизилась к опасному состоянию, когда μ≈λ. При таких условиях очередь становится метастабильной: она может какое-то время вести себя «хорошо», а потом внезапно наступит коллапс:
При λ = 15 и μ = 16 средняя длина очереди будет как раз равна 15 клиентам, а среднее время занятости оператора составит 1 день. Руководство может быть довольно своей оптимизацией. Но мы-то знаем, что средние показатели не показывают толком почти ничего. Посмотрите, с какой вероятностью время занятости клерка превысит указанное количество дней
Таким образом, вроде бы разумное решение может иметь неожиданно неприятные последствия.
* * *
В этой главе мы разбирались с не самыми приятными сторонами нашей жизни — очередями и бюрократией. И хотя они часто вызывают у нас раздражение, всё же эти явления призваны помогать в организации по-настоящему сложных процессов, они поддаются исчислению и избавляют нас от гораздо более неприятного и даже опасного неуправляемого хаоса.