Queueing theory for fun and practice #2: нагрузка и время отклика

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

"Массовое окормление паствы: пособие для начинающих" (редакция 3-я, неизданная)

(Часть 2, начало: ТМО, square root staffing, Little)

Как зависит время отклика от нагрузки на систему (утилизации)? Для многих систем измерения дадут что-то вроде такой картинки:

Такую кривую зависимости среднего времени отклика от нагрузки за характерную форму часто называют J-curve. Конечно, не обязательно кривая в конкретной системе будет выглядеть точно так – например, могут присутствовать ступеньки, соответствующие разным механизмам, которые ответственны за время отклика – но в среднем такая кривая свойственна многим системам, и приводит к ней как раз наличие внутренних очередей/буферов.

Queueing theory for fun and practice (#1): square root staffing, Little's law

На 28-ом этаже центра разработки крупного инвестиционного банка есть 8 туалетных кабинок для людей, идентифицирующих себя с мужским гендером. Работающий в центре высокофункциональный аутист Иннокентий подсчитал, что когда он заходит в туалет, в среднем 5 из 8 кабинок уже заняты.

Сколько человеко-часов в день сотрудники офиса спускают в унитаз?

"Теория массового обслуживания для сантехников" (неизданное)

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

Материалы, которые мне попадались по теории массового обслуживания, распадаются на две категории: ТМО как раздел математики (теории вероятности), и ТМО как раздел бизнес-управления, менеджмента производства/обслуживания (operations research).

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

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

Design of everyday things

Недавно прочитал "Дизайн привычных вещей" Дональда Нормана. Норман – computer scientist, и когнитивный психолог, известный и авторитетный специалист по эргономике. Он популяризовал сам термин "user experience", и был, вероятно, первым User Experience Architect – в Apple, что совершенно не удивляет.

На его книгу я наткнулся совершенно случайно, и залип с первых страниц. Книга написана в 1986 году, и Норман в предисловии пишет, что сознательно не переписывал разделы про кнопочные телефоны и видеомагнитофоны – технику того времени, давно уже канувшую в лету. Я немного опасался, что читать про проблемы интерфейса вещей, которые уже 20 лет никем не используются, будет скучно – но нет, наоборот. Вещи из 80-х проще, и ошибки дизайна на их примере понятнее – и но совершенно очевидно, что современные дизайнеры, проектируя гораздо более сложные вещи, продолжают делать ровно такие же ошибки.

Charlie Gracie: Current state of JVM Escape Analysis and downstream optimizations

Я уже какое-то время отошел от темы скаляризации и escape-анализа, но тут случайно наткнулся на любопытное видео с JFokus: Чарли Грасье из Микрософта рассказывает, как они для своих целей сделали прототип stack allocation для java 11. И даже не для Graal (где нынче чаще всего делают что-то новое), а для старого-доброго C2. Чарли начинает с краткого обзора escape-анализа и скаляризации в целом, потом кратко рассказывает, как они модифицировали JVM C2, чтобы сделать аллокацию на стеке.

Что это дает: они заинтересованы прежде всего в scala, и для scala-бенчмарков аллокация на стеке дает 5-15% увеличения производительности. Чарли спекулирует, что это прежде всего из-за увеличения кэш-локальности, поскольку объекты, аллоцированные на стеке, всегда будут горячими в кэше, а объекты, аллоцированные в куче, не всегда. Звучит немного странно, потому что стандартная аллокация в джаве (bump the pointer) тоже должна давать довольно хорошо предсказуемый и дружественный для кэширования паттерн доступа — но результаты говорят за себя.

Еще они обещают привести код в порядок, и инициировать принятие их изменений в mainline. Если получится (если!), будет очень интересно: я уже и не ждал ничего подобного в JVM.

Waiting time paradox #4: aftermath

(продолжение серии про парадокс времени ожидания)

…Мне кажется, это поразительный эффект: добавка sleep(5) в цикл обработки задач может уменьшать среднее время обработки. Даже после того, как я уже разобрался с этим эффектом на примере автобусной остановки, я все еще не мог поверить, что такой же эффект будет и в системе с очередью. И, несмотря на все формулы, разобранные примеры и симуляции, на интуитивном уровне я все еще ощущаю это как какой-то трюк. Это и поразительно: хотя логически я все понимаю, могу объяснить, и симуляцию написать, и картинку нарисовать – но моя интуиция все равно отказывается воспринимать это как очевидное.

И ведь происходит все в очень обыденной системе, с которой мы регулярно сталкиваемся в жизни. В математике есть множество выносящих мозг результатов, но многие из них выносят мозг просто потому, что относятся к системам, для которых в повседневной жизни нет аналогов. Парадокс Банаха-Тарского гораздо круче парадокса времен ожидания – но кто из нас в жизни сталкивается с разрезанием сферы на не-измеримые куски? Сама постановка задачи уже далеко выходит за рамки повседневного опыта и бытовой интуиции – не удивительно, что результат получается не интуитивный. Но очередь в Сбербанк, и кассир, который делает между клиентами минутную паузу, а иногда выбегает перекурить на 5 минут, а иногда попить чай на 15 – это обыденная ситуация. И оказывается, что в этой обыденной ситуации скрыто такое нетривиальное поведение!