Чем занимается теория массового обслуживания

Свободная касса

Что такое теория массового обслуживания и где она применяется

Один из самых близких любому человеку разделов математики наряду с арифметикой — как ни странно, теория массового обслуживания. Это прикладной раздел теории вероятностей, задачи которого окружают нас везде: от очереди в магазине или на посадку в самолет до пробок на дорогах и сетей мобильной связи новейшего поколения. О перспективах развития этого направления и о его практических приложениях редакция N + 1 поговорила с заведующим кафедрой прикладной информатики и теории вероятностей РУДН, профессором Константином Евгеньевичем Самуйловым.

N + 1: Что такое теория массового обслуживания?

Константин Самуйлов: В основе этого большого раздела теории вероятностей лежит понятие цепи Маркова — последовательности случайных событий, для которых будущее состояние зависит только от настоящего состояния системы и не зависит от прошлого.

Теория Марковских цепей описывает работу большого числа процессов в реальном мире, например, работу автопилота и систем хранения, изменение численности популяций организмов в природе, лежит в основе алгоритма PageRank поисковой системы Google и, конечно, служит фундаментом для теории массового обслуживания. В зарубежной литературе она называется теорией очередей. В английском языке используется термин queueing theory.

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

Необходимость в новых моделях теории массового обслуживания возникает из практических задач, связанных с появлением технологий и системных новаций. Эти задачи можно взять из жизни — теория массового обслуживания востребована там, где возникают новые и сложные типы очередей.

И где именно она применяется?

Важнейшее практическое приложение теории массового обслуживания с самого ее возникновения — сфера коммуникаций: сначала телефония, позднее — телекоммуникации.

Как известно, мировая телекоммуникационная сеть — это самый большой технический объект из когда-либо созданных человеком. При этом сеть живет по случайным законам, поскольку запросы пользователей на предоставление телекоммуникационного ресурса возникают в случайные моменты, а объемы передаваемой информации также случайны.

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

Кроме того, мы еще смотрим в будущее и пытаемся понять, какие сети придут на смену нынешним. И соответственно, помогаем им родиться, проектируем их архитектуру.

Что можно сказать о современном состоянии телекоммуникаций с точки зрения теории массового обслуживания?

Телекоммуникации постоянно развиваются, и нет никаких признаков, что этот процесс замедлится. Нам надо думать о резервах для наращивания пропускной способности каналов связи.

Важный вызов — это дефицит пропускной способности. Доступная полоса частот исчерпана во всех диапазонах вплоть до десятков гигагерц, в лицензируемых диапазонах свободных частот уже просто нет.

Формула Шеннона устанавливает соответствие между шириной частотного диапазона (обычно измеряемого в мегагерцах) и максимальной полосой пропускания в битах в секунду, которую при этом можно получить. Так вот, нелицензированные диапазоны и частоты остались лишь в диапазонах выше десятков гигагерц.

В поисках решения проблемы Международный союз электросвязи приступил даже к изучению возможностей квантовой передачи информации. Это очень дорогие исследования, которые ранее не проводились на международном уровне.

Если ли альтернатива?

В принципе, есть. Например, мы сейчас начали заниматься исследованиями сетей шестого поколения. Это так называемая многоуровневая «летающая и всепроникающая» телекоммуникационная сеть.

На математическом языке она описывается как движущаяся сеть поверх наземной инфраструктуры. Например, на нижнем уровне точки доступа (базовые станции) сети расположены на беспилотных дронах, выше — на тяжелых подвесных платформах, привязные платформы в виде дирижаблей и аэростатов, еще выше — на низкоорбитальных спутниках и так далее.

Что-то похожее на сеть StarLink компании SpaceX?

Примерно так. Причем в исследованиях сетей типа 6G уже недостаточно использовать одну только теорию массового обслуживания. Для эффективного проектирования и последующей эксплуатации таких сетей мы применяем комбинацию методов и подходов.

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

А какая здесь математика?

Мы применяем математические инструменты, в том числе стохастическую геометрию. Нужно в каждый момент времени контролировать полет стаи дронов, контролировать местоположение каждого аппарата, выдерживать расстояниями между ними, которые, вообще говоря, случайны.

От расстояний зависит мощность передаваемого сигнала, интерференция сигналов от разных источников, отношение «сигнал-шум», а эти расстояния изменяются и случайны в каждый момент.

Например, в простейшем случае, необходимо решать задачи для треугольников со случайными сторонами или других геометрических фигур в терминах стохастической геометрии в трехмерном пространстве.

Вы говорите о чисто теоретических изысканиях или это часть практической разработки?

Конечно, часть практической разработки. Мы ведь не просто математики, мы работаем в тесной инженерной кооперации. Сейчас группа моих аспирантов и сотрудников находится в Технологическом университете города Брно в Чехии, это технический университет очень высокого уровня.

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

Более сложный путь — проведение имитационного моделирования. Это дольше и дороже, точность выше, но погрешность все равно остается высокой. Самую полную и точную картину позволят получить лишь физические измерения на действующих объектах.

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

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

Необходимо описать с помощью стохастической геометрии взаимное расположение летящих дронов. Также надо описать и смоделировать поведение абонента, описываемое той или иной моделью случайного блуждания random walk, — этим случайным перемещениям абонента также посвящен известный раздел теории вероятности.

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

Каков вклад именно вашей группы в этот проект?

Мы хорошо разбираемся в приложениях для высокочастотных сетей. Важная их часть — выделение пользователям емкости канала по их запросу, то, что по-английски называется capacity-on-demand.

Предоставление ресурса по запросу лежит в основе развития современной постиндустриальной экономики. Начало процессу положили в XVIII веке извозчики, предоставляющие услуги перевозки пассажиров конными экипажами.

Появление TCP/IP, протокола работы сети Интернет, позволило построить самую большую за всю историю сеть массового обслуживания, в которой пропуск трафика осуществляется оптимальными путями по свободным в данные конкретные моменты времени каналам.

В дальнейшем этот подход получил развитие при предоставлении массовых интернет-сервисов такими компаниями, как Yahoo, Google и Яндекс, и лег в основу шэринговой экономики.

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

Для моделирования можно применять вычислительные инструменты — такие, как пакеты программ компании Wolfram Research. С их помощью можно проводить весьма сложные вычисления в аналитическом виде, например, вычислять в символьном виде обратное преобразование Лапласа. Но в силу сложности задач не всегда удается их решить за требуемое для индустрии время, которая значительно опережает фундаментальные исследования.

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

Как можно описать эти результаты?

Недавно в журнале Probability in the Engineering and Informational Science у нас с соавторами вышла статья, в которой мы подробно описали решение для нового класса задач теории очередей для случая, когда пользователи могут не только забирать во временное пользование ограниченный ресурс системы, но также и добавлять свой ресурс в систему, расширяя ее возможности.

Ресурс, приносимый потребителем, описывается как отрицательный расход, при этом общий объем ресурсов, выделяемых потребителям, должен быть неотрицательным и не должен превышать предопределенные максимальные уровни (пороги).

Появление в модели отрицательного использования ресурса приводит к временному увеличению его объема в системе. Мы нашли необходимые и достаточные условия для определения стационарного распределения вероятностей марковского процесса, описывающего функционирование системы.

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

Для решения каких задач, за пределами телекоммуникаций, можно применить разработанный вами математический аппарат?

Например, для разного рода систем бронирования. Представьте себе систему бронирования билетов на транспорте или товаров в интернет-магазине.

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

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

А можно ли применить вашу методику, например, к области финтеха? Или к движению криптовалют?

В принципе, да, но надо понимать, что это особенные сферы, со своей информационной спецификой. Так, если взять задачи финансового рынка, то для него характерна закрытость информации. Соответственно, применять новые теории на этом рынке можно лишь очень ограниченно.

Математики, занимающиеся, например, финансами, актуарной математикой, расчетами рисков, используют ограниченный набор инструментов теории массового обслуживания. Временные ряды, описывающие биржевые котировки — совершенно другой математический аппарат.

Источник

Теория массового обслуживания

Содержание

История

Теорию потока однородных событий, которая легла в основу теории массового обслуживания, разработал советский математик А. Я. Хинчин. [2]

Первые задачи ТМО (Теории Массового Обслуживания) были рассмотрены сотрудником Копенгагенской телефонной компании, ученым Агнером Эрлангом, в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.

Имеется телефонный узел (обслуживающий прибор), на котором телефонистки время от времени соединяют отдельные номера телефонов друг с другом. Системы массового обслуживания (СМО) могут быть двух видов: с ожиданием и без ожидания (то есть с потерями). В первом случае вызов (требование, заявка), пришедший на станцию в момент, когда занята нужная линия, остается ждать момента соединения. Во втором случае он «покидает систему» и не требует забот СМО.

Поток

Однородный поток

Поток заявок однороден, если:

Поток без последействия

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

Стационарный поток

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

Простейший поток

Однородный стационарный поток без последействий является простейшим, потоком Пуассона.

Число событий такого потока, выпадающих на интервал , распределено по Закону Пуассона:

Пуассоновский поток заявок удобен при решении задач ТМО. Строго говоря простейшие потоки редки на практике, однако многие моделируемые потоки допустимо рассматривать как простейшие.

Мгновенная плотность

Мгновенная плотность (интенсивность) потока равна пределу отношения среднего числа событий, приходящихся на элементарный интервал времени (, ) к длине интервала (), когда последний стремится к нулю.

или, для простейшего потока,

где равно математическому ожиданию числа событий на интервале .

Формула Литтла

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

Литература

Библиография

См. также

Полезное

Смотреть что такое «Теория массового обслуживания» в других словарях:

теория массового обслуживания — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] теория массового обслуживания Раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других… … Справочник технического переводчика

Теория массового обслуживания — [theory of waiting lines, queueing theory] раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях как процессы обслуживания, т.е. удовлетворения каких… … Экономико-математический словарь

Теория массового обслуживания — [theory of waiting lines, queueing theory] раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях как процессы обслуживания, т.е. удовлетворения каких… … Экономико-математический словарь

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ — раздел прикладной математики, применяющийся в качестве метода в экономических исследованиях. Эта теория изучает статистические закономерности в массовых операциях, состоящих из большого числа однородных элементарных операций. К ним относятся,… … Большой экономический словарь

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ — раздел теории вероятностей, изучающей потоки требований на обслуживание, поступающие в системы обслуживания и выходящие из них, длительности ожидания и длины очередей и т. п. Целью исследований в Т. м. о. является рациональный выбор структуры… … Энциклопедический словарь по психологии и педагогике

Массового обслуживания теория — математическая дисциплина, изучающая системы, предназначенные для обслуживания массового потока требований случайного характера (случайными могут быть как моменты появления требований, так и затраты времени на их обслуживание). Типичным… … Большая советская энциклопедия

МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ — теория очередей, раздел теории вероятностей, изучающий математич. модели разного рода реальных массового обслуживания систем. Эти модели представляют собой случайные процессы специального вида, к рые наз. иногда процессами обслуживания. Чаще… … Математическая энциклопедия

МАССОВОГО ОБСЛУЖИВАНИЯ ТЕОРИЯ — раздел математики, изучающий системы, предназначенные для обслуживания массового потока требований случайного характера. Типичный пример такой системы автоматическая телефонная станция, где случайным образом поступают требования вызовы абонентов … Большой Энциклопедический словарь

массового обслуживания теория — раздел математики, изучающий системы, предназначенные для обслуживания массового потока требований случайного характера. Типичный пример такой системы автоматическая телефонная станция, где случайным образом поступают «требования» вызовы… … Энциклопедический словарь

Источник

Изучаем Latency: теория массового обслуживания

Тема latency со временем становится интересной в разных системах в Яндексе и не только. Происходит это по мере того, как в этих системах появляются какие-либо гарантии по обслуживанию. Очевидно, дело в том, что важно не только пообещать какую-то возможность пользователям, но и гарантировать её получение с разумным временем отклика. «Разумность» времени отклика, конечно, сильно различается для разных систем, но базовые принципы, по которым во всех системах проявляется латентность, — общие, и их вполне можно рассматривать в отрыве от конкретики.

Меня зовут Сергей Трифонов, я работаю в команде Real-Time Map Reduce в Яндексе. Мы разрабатываем платформу для обработки потока данных в реальном времени с секундным и субсекундным временем отклика. Платформа доступна для внутренних пользователей и позволяет им выполнять прикладной код над постоянно поступающими потоками данных. Я попытаюсь сделать краткий обзор основных концепций человечества на тему анализа latency за последние сто десять лет, и сейчас мы попробуем понять, что именно про latency можно узнать, применяя теорию массового обслуживания.

Феномен латентности начали систематически исследовать, насколько мне известно, в связи с появлением систем массового обслуживания — телефонных сетей связи. Теория массового обслуживания началась с работы А. К. Эрланга 1909 г., в которой он показал, что пуассоновское распределение применимо к случайному телефонному трафику. Эрланг разработал теорию, которая многие десятилетия использовалась для проектирования телефонных сетей. Теория позволяет определить вероятность отказа в обслуживании. Для телефонных сетей с коммутацией каналов отказ происходил, если все каналы заняты и звонок не может быть совершён. Вероятность этого события нужно было контролировать. Хотелось иметь гарантию, что, например, 95% всех звонков будут обслужены. Формулы Эрланга позволяют определить, сколько нужно серверов для выполнения этой гарантии, если известна длительность и число звонков. По сути, эта задача как раз про гарантии качества, и сегодня люди по-прежнему решают похожие задачи. Но системы стали гораздо сложнее. Основная проблема теории массового обслуживания в том, что в большинстве институтов её не преподают, и мало кто понимает вопрос за пределами обычной очереди M/M/1 (см. про нотацию ниже), зато хорошо известно, что жизнь намного сложнее этой системы. Поэтому я предлагаю, минуя M/M/1, перейти сразу к самому интересному.

Средние величины

, где — среднее по времени число запросов в рассматриваемой части системы [шт.], — среднее время, за которое запросы проходят через данную часть системы [с], — скорость поступления запросов в систему [шт./с]. Сила теоремы в том, что её можно применять к любой части системы: очередь, исполнитель, очередь + исполнитель или сеть целиком. Часто этой теоремой пользуются примерно так: «К нам льётся поток 1Gbit/s, а среднее время отклика мы измерили, и оно составляет 10 мс, следовательно в полёте у нас в среднем 1.25 MB». Так вот, это вычисление не верно. Точнее, верно, только если все запросы имеют одинаковый размер в байтах. Теорема Литтла считает запросы в штуках, а не в байтах.

Как пользоваться теоремой Литтла

В математике часто бывает нужно изучить доказательство, чтобы получить настоящий insight. Это как раз такой случай. Теорема Литтла настолько хороша, что я приведу здесь набросок доказательства. Входящий трафик описывается функцией — число запросов, которые вошли в систему к моменту времени . Аналогично — число запросов, которые вышли из системы к моменту времени . Моментом входа (выхода) запроса считается момент получения (передачи) последнего его байта. Границы системы определяются лишь этими моментами времени, поэтому теорема получается широко применимой. Если нарисовать графики этих функций в одних осях, то легко увидеть, что — это число запросов в системе в момент t, а — время отклика n-го запроса.

Теорема была формально доказана только в 1961 г., хотя само соотношение было известно задолго до этого.

На самом деле, если внутри системы запросы могут переупорядочиться, то всё немного сложнее, поэтому будем для простоты считать, что этого не происходит. Хотя теорема верна и в этом случае тоже. Теперь подсчитаем площадь между графиками. Это можно сделать двумя способами. Во-первых, по колонкам — как обычно считают интегралы. В этом случае получается, что подынтегральное выражение — это размер очереди в штуках. Во-вторых, построчно — просто сложив latency всех запросов. Понятно, что оба вычисления дают одну и ту же площадь, поэтому равны. Если обе части этого равенства поделить на время Δt, за которое мы считали площадь, то слева у нас будет средняя длина очереди (по определению среднего). Справа немного сложнее. Нужно в числитель и знаменатель вставить ещё число запросов N, тогда у нас получится

Если рассматривать достаточно большие Δt или один период занятости, то вопросы на краях снимаются и теорему можно считать доказанной.

Важно сказать, что в доказательстве мы не использовали никакие распределения никаких вероятностей. По сути, теорема Литтла — это детерминистический закон! Такие законы называются в теории массового обслуживания operational law. Их можно применять к любым частям системы и любым распределениям всевозможных случайных величин. Эти законы образуют конструктор, который можно успешно использовать для анализа средних значений в сетях. Недостаток в том, что все они применимы только к средним величинам и не дают никакого знания о распределениях.

Возвращаясь к вопросу, почему нельзя применять теорему Литтла к байтам, предположим, что и теперь измеряются не в штуках, а в байтах. Тогда, проводя аналогичное рассуждение, мы получим вместо странную вещь — площадь, деленную на общее число байт. Это по-прежнему секунды, но это что-то вроде средневзвешенного latency, где запросы большего размера получают больший вес. Можно эту величину назвать средней латентностью байта — что, в общем, логично, поскольку мы заменили штуки на байты — но никак не латентностью запроса.

Теорема Литтла говорит, что при определенном потоке запросов время отклика и число запросов в системе пропорциональны. Если все запросы выглядят одинаково, то среднее время отклика нельзя уменьшить, не наращивая мощности. Если же мы знаем размеры запросов заранее, можно пытаться переупорядочить их внутри, чтобы уменьшить площадь между и и, следовательно, среднее время отклика системы. Продолжая эту мысль, можно доказать, что алгоритмы Shortest Processing Time и Shortest Remaining Processing Time дают для одного сервера минимальное среднее время отклика без возможности вытеснения и с ней соответственно. Но есть побочный эффект — большие запросы могут не обрабатываться бесконечно долго. Феномен называется «голодание» (starvation) и тесно связан с понятием справедливости планирования, о котором можно узнать из предыдущего поста Scheduling: мифы и реальность.

Есть ещё одна распространённая ловушка, связанная с пониманием закона Литтла. Имеется однопоточный сервер, который обслуживает запросы пользователей. Допустим, мы как-то измерили L — среднее число запросов в очереди к этому серверу, и S — среднее время обслуживания одного запроса сервером. Теперь рассмотрим новый входящий запрос. В среднем он видит впереди себя L запросов. На обслуживание каждого из них уходит в среднем S секунд. Получается, что среднее время ожидания . Но по теореме получается, что . Если приравнять выражения, то увидим нонсенс: . Что не так в этом рассуждении?

Открытые и закрытые системы

Стоит отметить, что для закрытых систем «неверный» ход рассуждений, приводящий к выводу оказывается верным. Закрытые системы — это такие системы, в которые запросы не приходят извне и не уходят наружу, а циркулируют внутри. Или, иначе, системы с обратной связью: как только запрос покидает систему, новый запрос занимает его место. Эти системы важны ещё и потому, что любую открытую систему можно рассматривать как погружённую в закрытую систему. Например, можно рассматривать сайт как открытую систему, в которую постоянно сыпятся запросы, обрабатываются и уходят, а можно, наоборот, как закрытую систему вместе со всей аудиторией сайта. Тогда обычно говорят, что число пользователей фиксировано, и они либо ждут ответа на запрос, либо «думают»: получили свою страницу и пока не кликнули по ссылке. В том случае, если think time всегда нулевой, систему ещё называют батч-системой.

Закон Литтла для закрытых систем справедлив, если скорость внешних прибытий (их нет в закрытой системе) заменить на пропускную способность системы. Если завернуть однопоточный сервер, рассмотренный выше, в батч-систему, мы получим и утилизацию 100%. Часто такой взгляд на систему даёт неожиданные результаты. В 90-х годах именно такое рассмотрение интернета вместе с пользователями как единой системы дало толчок к изучению распределений, отличных от экспоненциальных. Распределения мы обсудим дальше, а здесь отметим, что в то время практически всё и везде рассматривалось как экспоненциальное, и этому даже находили какое-то обоснование, а не просто оправдание в духе «иначе слишком сложно». Однако оказалось, что не все практически важные распределения имеют одинаково длинные хвосты, и знание о хвостах распределения можно пытаться использовать. Но пока вернёмся к средним величинам.

Релятивистские эффекты

Предположим, у нас имеется открытая система: сложная сеть или простой однопоточный сервер — не важно. Что изменится, если ускорить вдвое поступление запросов и ускорить вдвое их обработку — например, увеличив мощность всех компонент системы в два раза? Как поменяются утилизация, пропускная способность, среднее число запросов в системе и среднее время ответа? Для однопоточного сервера можно попытаться взять формулы, применить их «в лоб» и получить результаты, но что делать с произвольной сетью? Интуитивное решение следующее. Предположим, что время ускорилось в два раза, тогда в нашей «ускоренной системе отсчёта» скорость серверов и поток запросов как будто не менялись; соответственно, все параметры в ускоренном времени имеют те же значения, что и раньше. Иными словами, ускорение всех «движущихся частей» любой системы эквивалентно ускорению часов. Теперь преобразуем значения в систему с нормальным временем. Безразмерные величины (утилизация и среднее число запросов) не поменяются. Величины, размерность которых включает временные множители первой степени, изменятся пропорционально. Пропускная способность [запросов / с] увеличится вдвое, а время отклика и ожидания [с] уменьшится вдвое.

Этот результат можно интерпретировать двумя способами:

Из этого следует, что если речь идёт про латентность, нельзя обойтись расчётами потоков, и даже утилизация устройств всего не решает. Нужно обязательно учитывать размеры запросов и не забывать про время распространения, которое часто игнорируют в теории массового обслуживания, хотя добавить его в расчёты совсем не сложно.

Распределения

В чем вообще причина образования очередей? Очевидно, в системе недостаточно мощностей, и избыток запросов накапливается? Не верно! Очереди возникают также в системах, где ресурсов достаточно. Если мощностей недостаточно, то система, как говорят теоретики, не стабильна. Есть две основные причины образования очередей: нерегулярность поступления запросов и вариативность размеров запросов. Мы уже рассматривали пример, в котором обе эти причины были устранены: система реального времени, где запросы одинакового размера приходят строго периодически. Очередь никогда не образуется. Среднее время ожидания в очереди равно нулю. Понятно, что добиться такого поведения очень сложно, если не невозможно, поэтому и образуются очереди. Теория массового обслуживания исходит из предположения, что обе причины носят случайный характер и описываются некоторыми случайными величинами.

Для описания разных систем используется нотация Кендалла A/S/k/K, где A — распределение времени между запросами, S — распределение размеров запросов, k — число серверов, K — ограничение на одновременное число запросов в системе (опускается, если ограничения нет). Например, широко известная M/M/1 расшифровывается так: первая M (Markovian или Memoryless) обозначает, что на вход в систему подаётся пуассоновский поток задач. Читай: сообщения приходят в случайные моменты времени с заданной средней скоростью запросов в секунду — прямо как при радиоактивном распаде — или, более формально: время между двумя соседними событиями имеет экспоненциальное распределение. Вторая M обозначает, что обслуживание этих сообщений тоже имеет экспоненциальное распределение и в среднем обрабатывается μ запросов в секунду. И наконец, единица в конце обозначает, что обслуживание выполняется одним сервером. Очередь не ограничена, так как 4-я часть нотации отсутствует. Буквы, которые используются в этой нотации, довольно странно выбраны: G — произвольное распределение (нет, не гауссово, как можно было бы подумать), D — deterministic. Cистема реального времени — D/D/1. Первая система теории массового обслуживания, которую решил Эрланг в 1909 г., — M/D/1. А вот нерешённая пока аналитически система — M/G/k для k>1, причём решение для M/G/1 нашли ещё в 1930-м.

Почему используют экспоненциальные распределения?

Основная причина в том, что они делают почти любую задачу про очереди решаемой, поскольку, как мы увидим дальше, появляется возможность применять цепи Маркова, про которые математики уже много всего знают. Экспоненциальные распределения имеют много хороших для теории свойств, потому что они не обладают памятью. Я не стану приводить здесь определение этого свойства, для разработчиков будет более полезным объяснение через failure rate. Предположим, у вас есть некое устройство, а из практики вы знаете распределение времени жизни таких устройств: они часто выходят из строя в начале жизни, затем ломаются относительно редко и после истечения гарантийного срока опять начинают часто ломаться. Формально эта информация как раз и содержится в failure rate function, которая довольно просто связана с распределением. По сути, это «выровненная» плотность вероятности с учётом того, что устройство дожило до некоторого момента. С практической точки зрения это именно то, что нам интересно: частота отказов устройств как функция времени, которое они уже находятся в эксплуатации. Например, если failure rate — константа, то есть частота отказа устройства не зависит от времени эксплуатации, а отказы просто происходят случайно с какой-то частотой, тогда распределение времени жизни устройства — экспоненциальное. В этом случае, чтобы предсказать, сколько устройство проработает, не надо знать, как долго оно находится в эксплуатации, какой у него износ и что бы то ни было другое. Это и есть «отсутствие памяти».

Короткие и длинные хвосты

Failure rate можно вычислить для любого распределения. В теории массового обслуживания — для распределения времени выполнения запроса. Failure rate говорит, как долго ещё запрос будет выполняться, исходя из того, сколько он уже выполняется. Если у нас возрастающий failure rate, то чем дольше запрос выполняется, тем больше вероятность, что он скоро закончится. Если у нас убывающий failure rate, то чем дольше запрос выполняется, тем больше вероятность, что он будет выполняться еще дольше. Как вам кажется, какой из этих двух вариантов наиболее типичен для вычислительных систем, баз данных и прочего, связанного с software и hardware? Для начала: почему это вообще важно? Пример из повседневной жизни. Вы стоите в очереди в кассу, поначалу очередь продвигается хорошо, но в какой-то момент перестаёт двигаться. Стоит ли перейти в другую очередь такой же длины? Если обслуживание имеет экспоненциальное распределение, то ответ — без разницы. В случае распределения с тяжёлым хвостом (убывающий failure rate) может быть выгодно мигрировать в другую очередь. Такого рода «анализ ситуации» можно применять для балансировки или миграции процессов.

Выясняется, что на производстве чаще встречаются распределения или экспоненциальные, или с возрастающим failure rate, а в компьютерных системах, наоборот, времена выполнения всяческих запросов или unix-процессов имеют распределения с тяжёлым хвостом. Это довольно неожиданная новость, и я решил её проверить.

RTMR выполняет много разного прикладного кода над данными, которые создаются из сессий пользователей поиска. Я вооружился LWTrace и оттрассировал с нашего продакшен-кластера все нужные данные. Меня интересовало только время работы пользовательского кода. Стриминговая обработка происходит довольно быстро, поэтому мне не составило труда собрать данные о примерно миллионе случайно выбранных запусков на случайных машинах в течение нескольких часов. Поскольку меня интересовал хвост распределения, я построил график распределения x\>$» data-tex=»inline»/> в двойных логарифмических осях. Чтобы понять, возрастающий или убывающий failure rate имеет это распределение, я сравнил его с двумя другими распределениями, которые имеют точно такое же среднее значение: экспоненциальным и распределением Парето.

Распределение Парето имеет степенную форму x\> = x^<-a>$» data-tex=»inline»/>, и поэтому затухает медленнее любой экспоненты — имеет тяжёлый хвост. Ещё оно знаменито тем, что часто встречается в «дикой природе», принцип 80/20: распределение богатства в обществе, размеров файлов в интернете и т. п. В двойных логарифмических осях оно превращается в прямую, что очень удобно для сравнения на глаз. Как видите, в RTMR мы имеем что-то, больше похожее на Парето, чем на экспоненту. Параметр , что соответствует принципу 80/20: всего 20% запросов создают 80% нагрузки.

Цепи Маркова

Эту большую тему невозможно объять парой абзацев, но я постараюсь. Цепи Маркова позволяют взглянуть на конечный автомат с вероятностной точки зрения. Для этого предполагают, что события, которые меняют состояние автомата, случайны и автомат просто переходит между состояниями с какими-то известными вероятностями. Для теории массового обслуживания используют автомат, состояния которого — это число запросов в системе. Событие «новый запрос» переводит автомат в следующее состояние, а событие «завершение обслуживания» — обратно. Спрашивается: что будет, если предоставить такому автомату достаточно времени? Допустим, много таких автоматов существует параллельно (ансамбль автоматов, если угодно), и они независимо и случайно плавают из одного состояния в другое. Теперь рассмотрим некоторое состояние, например состояние 0 на рисунке. Чтобы число автоматов в этом состоянии оставалось неизменным, надо, чтобы скорость их поступления была уравновешена скоростью переходов в другие состояния . Таким образом, мы получим уравнений столько же, сколько и неизвестных — по числу состояний. Дальше решим систему и найдём так называемое равновесное распределение. Для каждого отдельного автомата это распределение говорит, какую долю времени в каком состоянии он пребывает. Недолгое жонглирование символами приводит для M/M/1 к результату , где — это утилизация сервера. Конец истории. По ходу изложения я пропустил приличное количество предположений и сделал пару подмен понятий, но суть, надеюсь, не пострадала.

Важно понимать, что такой подход работает, только если текущее состояние автомата полностью определяет его дальнейшее поведение, а история о том, как он попал в это состояние, не важна. Для повседневного понимания конечного автомата это само собой разумеется — ведь на то оно и состояние. А вот для стохастического процесса из этого следует, что все распределения должны быть экспоненциальными, поскольку только они не обладают памятью — имеют константный failure rate.

Ещё важно сказать, что всю остальную информацию про систему легко получить, если мы знаем равновесное распределение. Среднее число запросов в системе — среднее значение этого распределения. Чтобы узнать среднее время отклика, применим теорему Литтла к числу запросов. Распределение времени отклика найти чуть сложнее, но тоже за несколько действий можно выяснить, что t\> = e^<-(\mu-\lambda)t>$» data-tex=»inline»/> и что среднее время отклика .

Неограниченное время отклика

По этому распределению можно найти любой перцентиль времени отклика, и оказывается, что сотый перцентиль равен бесконечности. Другими словами, худшее время отклика не ограничено сверху. Что, в общем-то, не удивительно, поскольку мы использовали пуассоновский поток. Но на практике такое поведение никогда не может встретиться. Очевидно, что входной поток запросов к серверу ограничен, хотя бы шириной сетевого канала к этому серверу, а длина очереди — памятью на этом сервере. Пуассоновский поток, напротив, с ненулевой вероятностью гарантирует возникновение сколь угодно больших бёрстов. Поэтому я бы не рекомендовал при проектировании системы исходить из предположения пуассоновского входного потока, если вас интересуют высокие перцентили, а загрузка системы очень высока. Лучше использовать другие модели трафика, про которые я расскажу в другой раз, когда буду говорить о сетевом исчислении.

Масштабирование и гарантии

Теперь, когда в нашем распоряжении есть достаточно мощный способ анализа систем, можно пытаться применять его к разным задачам и пожинать плоды. Примерно так развивалась теория массового обслуживания во второй половине ХХ века. Попробуем понять, чего удалось добиться. Для начала вернёмся к задачам, которые решал Эрланг. Это задачи M/M/k/k и M/M/k, в которых нам бы хотелось ограничивать вероятность отказа. Оказывается, для них несложно построить цепи Маркова. Отличие в том, что по мере прибавления задач вероятность обратного перехода увеличивается, так как задачи начинают обрабатываться параллельно, но когда число задач становится равно числу серверов, происходит насыщение. Дальше для M/M/k/k сеть заканчивается, автомат действительно оказывается конечным, и все запросы, которые приходят в последнее состояние, получают отказ. Вероятность этого события просто равна вероятности того, что мы находимся в последнем состоянии.

Для M/M/k дело обстоит сложнее, запросы встают в очередь, появляются новые состояния, но вероятность обратного перехода не увеличивается — уже все серверы работают. Сеть становится бесконечной, как для M/M/1. Кстати, если число запросов в системе ограничено, то цепь всегда будет иметь конечное число состояний и так или иначе будет решаться, чего не скажешь про бесконечные цепи. В закрытых системах цепи всегда конечны. Решая описанные цепи для M/M/k/k и M/M/k, мы придём к формуле B и формуле С Эрланга соответственно. Они довольно громоздкие, я не буду их приводить, но с их помощью можно получить интересный для развития интуиции результат, который называется square root staffing rule. Допустим, имеется система M/M/k с каким-то заданным входным потоком λ запросов в секунду. Предположим, что нагрузка должна завтра увеличиться в два раза. Спрашивается: как надо увеличить число серверов, чтобы время отклика осталось прежним? Число серверов надо удвоить, верно? Оказывается, вовсе нет. Вспомним, что мы уже видели: если ускорить время (серверы и вход) вдвое, то среднее время отклика уменьшается вдвое. Несколько медленных и один быстрый сервер — это не одно и то же, но тем не менее вычислительная мощность одинакова. В частности, для M/M/1 например, время отклика обратно пропорционально объёму «свободной ёмкости» и определяется только этим объёмом. При увеличении и потока, и вычислительной мощности вдвое, свободная ёмкость системы удваивается: . Может показаться, что для решения задачи нужно просто сохранить свободную ёмкость, но время отклика в M/M/k определяется уже по более сложной формуле Эрланга. Оказывается, что свободную ёмкость нужно поддерживать пропорционально квадратному корню из числа «занятых серверов», чтобы сохранить прежнее время отклика. Под числом «занятых серверов» подразумевается общее число серверов, умноженное на утилизацию: это минимально необходимое для стабильной работы число серверов.

Используя данное правило, иногда пытаются обосновать, как расширять кластер с серверами. Но не стоит питать иллюзий, что любой кластер — это M/M/k-система. Например, если у вас на входе используется балансер, который отправляет запросы в очереди на серверы, — это уже не M/M/k, так как M/M/k подразумевает общую очередь, из которой серверы забирают запросы, когда освобождаются. Зато эта модель подходит, например, для тредпулов с общей FIFO-очередью. Однако даже в этом случае стоит помнить, что это правило является аппроксимацией для случая, когда тредов много. По факту, если у вас больше 10 тредов, можно смело считать, что их много. Ну и не забываем про вездесущие экспоненциальные распределения: без предположения экспоненциальности всех распределений правило тоже не работает.

Время отклика в сети

В конечном счёте, интерес представляет сеть из M/M/k, соединённых хотя бы в цепочку, так как мы делаем распределённые системы. Для изучения сетей хотелось бы иметь конструктор: простые и понятные правила соединения известных элементов в блоки. В теории управления, например, есть передаточные функции, которые понятным образом комбинируются при последовательных или параллельных соединениях. Здесь же выходной поток из любого узла имеет очень сложное распределение, за исключением M/M/k, которая по известной теореме Бёрка выдаёт независимый пуассоновский поток. Это исключение, как можно догадаться, в основном и используется.

Соединение двух пуассоновских потоков — пуассоновский поток. Вероятностное разделение пуассоновского потока на два — опять даёт два пуассоновских потока. Всё это приводит к тому, что все очереди в системе как бы независимы, и можно получить, выражаясь формальным языком, так называемое product-form solution. То есть совместное распределение длин очередей является просто произведением распределений длин всех очередей, рассматриваемых по отдельности — именно так в теории вероятностей выражается независимость. Просто находим входные потоки во все узлы и используем формулы для каждого узла независимо. Есть ряд ограничений:

Пример сети Джексона.

Стоит отметить, что при наличии обратной связи НЕ получается пуассоновский поток, так как потоки оказываются взаимозависимыми. На выходе из узла с обратной связью тоже получается непуассоновский поток, и в итоге все потоки становятся непуассоновскими. Однако удивительным образом оказывается, что все эти непуассоновские потоки ведут себя ровно так же, как пуассоновские (ох уж эта теория вероятностей), если выполняются указанные выше ограничения. И тогда мы опять получаем product-form solution. Такие сети имеют название Jackson networks, в них возможны обратные связи и, следовательно, множественные посещения любого сервера. Есть и другие сети, в которых позволяется больше вольностей, но в результате все значимые аналитические достижения теории массового обслуживания по отношению к сетям предполагают пуассоновские потоки на входе и product-form solution, что стало предметом критики этой теории и привело в 90-х как к разработке других теорий, так и к изучению того, какие на самом деле распределения нужны и как с ними работать.

Важное применение всей этой теории сетей Джексона — моделирование пакетов в IP-сетях и ATM-сетях. Модель достаточно адекватна: размеры пакетов не сильно меняются и не зависят от самого пакета, только от ширины канала, так как время обслуживания соответствует времени передачи пакета в канал. Случайное время отправки, хоть и звучит дико, на самом деле обладает не очень большой вариативностью. Более того, оказывается, что в сети с детерминированным временем обслуживания латентность не может быть больше, чем в аналогичной сети Джексона, поэтому такие сети смело можно использовать для оценки времени отклика сверху.

Неэкспоненциальные распределения

Все результаты, о которых я рассказал, относились к экспоненциальным распределениям, но я также упомянул, что реальные распределения отличаются. Возникает ощущение, что вся эта теория достаточно бесполезна. Это не совсем так. Есть способ встроить в этот математический аппарат и другие распределения, более того, практически любые распределения, но это будет кое-чего нам стоить. За исключением нескольких интересных случаев, теряется возможность получить решение в явном виде, теряется product-form solution, а вместе с ним конструктор: каждую задачу нужно решать целиком с нуля, используя цепи Маркова. Для теории это большая проблема, но на практике это просто означает применение численных методов и даёт возможность решать куда более сложные и приближенные к реальности задачи.

Метод фаз

Идея проста. Цепи Маркова не позволяют нам иметь память внутри одного состояния, поэтому все переходы должны быть случайными с экспоненциальным распределением времени между двумя преходами. Но что если состояние разбить на несколько подсостояний? Переходы между подсостояниями по-прежнему должны иметь экспоненциальное распределение, если мы хотим, чтобы вся конструкция оставалась цепью Маркова, а мы этого очень хотим, поскольку знаем, как решать такие цепи. Подсостояния часто называют фазами, если они выстроены последовательно, а процесс разбиения — методом фаз.

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

А что если сделать много-много коротких одинаковых фаз? В пределе получим детерминированное распределение. То есть, выстраивая цепочку, можно уменьшать вариативность распределения.

Можно ли увеличить вариативность? Легко. Вместо цепочки фаз используем альтернативные категории, случайно выбирая одну из них. Пример. Почти все запросы выполняются быстро, но есть небольшая вероятность, что придёт огромный запрос, который выполняется долго. Такое распределение будет иметь убывающий failure rate. Чем дольше мы ждём, тем больше вероятность, что запрос попал во вторую категорию.

Продолжая развивать метод фаз, теоретики выяснили, что есть класс распределений, с помощью которых можно приблизиться с любой точностью к произвольному неотрицательному распределению! Coxian distibution строится методом фаз, только мы не обязаны проходить все фазы, после каждой фазы есть некоторая вероятность завершения.

Такого рода распределения можно использовать как для генерации непуассоновского входного потока, так и для создания неэкспоненциального времени обслуживания. Вот, например, цепь Маркова для системы M/E2/1 с распределением Эрланга для времени обслуживания. Состояние определяется парой чисел (n, s), где n — длина очереди, а s — номер стадии, в которой находится сервер: первая или вторая. Возможны все комбинации n и s. Входящие сообщения меняют только n, а по завершении фаз происходит их чередование и уменьшение длины очереди после завершения второй фазы.

У вас микробёрсты!

То есть время ожидания в очереди определяется двумя множителями. Первый — это эффект утилизации сервера, а второй — среднее время дообслуживания. Рассмотрим второй множитель. Запрос, приходящий в некоторый момент , видит, что на дообслуживание нужно время .

Среднее время определяется средним значением функции , то есть площадью треугольников, делённой на общее время. Понятно, что можно ограничиться одним «средним» треугольником, тогда . Это довольно неожиданно. Мы получили, что время дообслуживания определяется не только средним значением времени обслуживания, но и его вариативностью. Объяснение простое. Вероятность попасть в длинный интервал больше, она на самом деле пропорциональна длительности S этого интервала. Это объясняет знаменитый Waiting Time Paradox, или Inspection Paradox. Но вернёмся к M/G/1. Если скомбинировать всё, что мы получили, и переписать, используя вариативность , получим известную формулу Pollaczek-Khinchine:

Если доказательство вас утомило, надеюсь, порадует результат применения на практике. Мы уже изучали данные о времени обслуживания в RTMR. Длинный хвост как раз возникает при большой вариативности и в данном случае . Это, согласитесь, намного больше, чем для экспоненциального распределения. В среднем всё выполняется супер быстро: . Теперь предположим, что RTMR моделируется системой M/G/1, и пусть система будет не сильно загружена, утилизация . Подставляя в формулу, получим . Из-за микробёрстов даже такая быстрая и недоутилизированная система может превратиться в среднем в отвратительную. За 50 мс можно 6 раз сходить на жёсткий диск или, если повезёт, даже в дата-центр на другом континенте! Кстати, для G/G/1 существует аппроксимация, которая учитывает вариативность поступающего трафика: она выглядит точно так же, только вместо в ней сумма обоих вариативностей . Для случая с несколькими серверами дела обстоят лучше, но эффект нескольких серверов влияет только на первый множитель. Эффект вариативности остаётся: .

Как выглядят микробёрсты? Применительно к тредпулам это задачи, которые обслуживаются достаточно быстро, чтобы не быть заметными на графиках утилизации, и достаточно медленно, чтобы создать очередь за собой и влиять на время отклика пула. С точки зрения теории — это огромные запросы из хвостовой части распределения. Скажем, у вас пул из 10 тредов, и вы смотрите на график утилизации, построенный по метрикам времении работы и времени простоя, которые собираются раз в 15 секунд. Вы, во-первых, можете не заметить, что один тред вообще завис, или что все 10 тредов выполняли одновременно большие задачи целую секунду, а потом 14 секунд ничего не делали. Разрешающая способность в 15 секунд не позволяет увидеть скачок утилизации до 100% и обратно до 0%, а время отклика страдает. Например, так может выглядеть микробёрст, случающийся раз в 15 секунд в пуле из 6 потоков, если посмотреть на него через микроскоп.

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

Специально чтобы разбираться с подобными ситуациями, в RTMR используется механизм SelfPing, который строго периодически (каждые 10 мс), отправляет маленькую задачу в тредпул с единственной целью — замерить время ожидания в очереди. Предполагая худший случай, к этому замеру добавляется период 10 мс и берётся максимум на окне в 15 секунд. Таким образом, мы получаем оценку сверху на максимальное время ожидания на окне. Да, мы не видим реального положения дел, если время отклика меньше 10 мс, но в этом случае мы можем считать, что всё хорошо — нет ни единого микробёрста. Зато эта дополнительная self-ping-активность съедает строго ограниченное количество CPU. Механизм удобен тем, что он универсальный и неинвазивный: не нужно менять ни код тредпула, ни код задач, которые в нём выполняются. Подчеркну: измеряется именно худший случай, что очень удобно и интуитивно, по сравнению со всякими перцентилями. Также механизм обнаруживает и другую похожую ситуацию: одновременный приход большого количества вполне обычных запросов. Если их не настолько много, чтобы проблему было видно на 15-секундных графиках утилизации, — это тоже можно считать микробёрстом.

Хорошо, а как быть, если SelfPing показывает, что происходит нечто неадекватное? Как найти виновных? Для этого мы используем трассировку, уже упомянутый LWTrace. Идём на проблемную машину и через мониторинг запускаем трассировку, которая отслеживает в нужном тредпуле все задачи и сохраняет в памяти только медленные. Затем можно посмотреть топ-100 медленных трасс. После кратковременного исследования трассировку выключаем. Все другие способы поиска виновных не подходят: писать логи на все задачи тредпула невозможно; писать только медленные задачи — тоже не самое лучшее решение, так как всё равно придётся собирать трассу для всех задач, а это тоже накладно; профилирование с помощью perf не поможет, так как тяжёлые задачи случаются слишком редко, чтобы быть заметными в профиле.

Независимость от распределения времени обслуживания

У нас осталась ещё одна «степень свободы», которую мы до сих пор не использовали. Входящий поток и размеры запросов мы обсудили, разные количества серверов тоже, но ещё не говорили о планировщиках. Все примеры подразумевали FIFO-обработку. Как я уже упоминал, планирование действительно влияет на время отклика системы, и правильный планировщик может значительно улучшить latency (алгоритмы SPT и SRPT). Но планирование — это очень продвинутая тема для теории массового обслуживания. Возможно, эта теория даже не очень хорошо подходит для исследования планировщиков, но это единственная теория, которая может давать ответы про стохастические системы с планировщиками и позволяет вычислять средние значения. Есть другие теории, которые позволяют многое понять про планирование «в худшем случае», но про них мы поговорим в другой раз.

А сейчас рассмотрим несколько интересных исключений из общего правила, когда всё-таки удаётся получить product-form solution для сети и можно создать удобный конструктор. Начнём с одного узла M/Cox/1/PS. Пуассоновский поток на входе, практически произвольное распределение (Coxian distribution) времени обслуживания и справедливый планировщик (Processor Sharing), обслуживающий все запросы одновременно, но со скоростью, обратно пропорциональной их текущему числу. Где можно встретить такую систему? Например, именно так работают справедливые планировщики процессов в операционных системах. На первый взгляд может показаться, что это сложная система, но если построить (см. раздел метод фаз) и решить соответствующую цепь Маркова, то оказывается, что распределение длины очереди в точности повторяет систему M/M/1/FIFO, в которой время обслуживания имеет такое же среднее значение, но распределено экспоненциально.

Это невероятный результат! В противоположность тому, что мы видели в разделе про микробёрсты, здесь вариативность времени обслуживания никак не влияет на время отклика, ни в каком из перцентилей! Такое свойство редко встречается и называется insensitivity property. Обычно оно возникает в системах, где нет ожидания, и запрос сразу начинает так или иначе выполняться, когда не нужно дожидаться дообслуживания того, что уже выполняется. Другой пример системы с таким свойством — M/M/∞. В ней тоже нет ожидания, так как число серверов бесконечно. В таких системах выходной поток из узла имеет хорошее распределение, что позволяет получить product-form solution для сетей с такими серверами — сетей BCMP.

Для полноты картины рассмотрим простейший пример. Два сервера, работающие с разной средней скоростью (например, частота процессора отличается), произвольное распределение размеров поступающих задач, обслуживающий сервер выбирается случайно, бóльшая часть задач идёт на быстрый сервер. Нужно найти среднее время отклика. Решение. . Применим известную формулу для среднего времени отклика M/M/1/FCFS и получим .

Ну всё, теперь и планирование обсудили, можно закругляться. В следующей статье я расскажу, как в системах реального времени подходят к вопросу латентности и какие концепции используются там.

Источник