Продажная многопоточность
Данный цикл статей рассматривает сложнейший мир многопоточного программирования через достаточно щекотливую тему, читатель должен быть готов к тому, что некоторые образы и примеры могут негативно повлиять на его психологическое состояние, некоторые — вызвать отвращение. Следует учитывать, что все описанные ситуации являются вымышленными и совпадения с реальностью случайны.
Повествование будет разбито на две части, от простого к сложному.
В первой части будут рассмотрены базовые понятия, стандартные подходы и проблемы. Будут приведены примеры использования нескольких, довольно известных примитивов синхронизации.
Во второй части, мы углубимся в более сложные концепты и так же, на простых и понятных примерах, разберем нетривиальные концепции, которые существуют в современных языках программирования.
О чудный дивный мир
Теплый летний вечер, закат. Приятный, едва прохладный, морской бриз ласкает волосы коренастого мужичка, который стоит на теплом песке, закрыв глаза. В своей памяти он пытается воспроизвести и хотя бы на секунду задержать тот самый момент, когда последние лучи солнца, уходящего за горизонт, поджигают небо ярко оранжевым пламенем. Несколько секунд и небо почти мгновенно окрашивается в фиолетово-черную пустоту. Еще пару мгновений и темнота скроет всю природную красоту этого места и прекрасный город Вхоревосток начнет медленно утопать в цветах оранжевых фонарей и люминесцентных ламп. Он совершенно забыл, как выглядит этот момент. Между ним и солнцем, которое уже почти скрылось за горизонт, пришвартован огромный контейнеровоз.
Слышен громкий звон, мат работяг, а позади него, метрах в двадцати, толпа голодных вонючих мужиков, с того самого судна, что отделяет нашего героя от последних лучей солнца, ломится в дверь небольшого припортового борделя, где он работает администратором.
И вот он докуривает папироску, бросает её в песок, смачно харкает в другую сторону и со словами: “Ну, началось, б***ь!” идет открывать дверь этим похотливым мужикам. Встает за стойку регистрации, прокашливается, пока они, по привычке, выстраиваются в очередь и тихим, низким, прокуренным голосом подзывает первого посетителя к себе. Отличное начало еще одной тяжелой трудовой ночи.
Добро пожаловать. Основные принципы
Работу в борделе будем рассматривать на трех ролях: администраторе, посетителе и проститутке. Для тех, кто по счастливой случайности, никогда в жизни не был в подобном месте, расскажу как это выглядит: приходит посетитель, администратор проверяет у него документы, проводит экспресс-тест на различные заболевания, выслушивает пожелания, рассчитывает (только наличные), выдает специальную карточку и отправляет к девушкам не самых высоких моральных принципов. Посетитель выбирает одну или несколько понравившихся, уединяется в отдельной комнате с достаточно вульгарными декорациями, и все его желания воплощаются в жизнь.
Здесь следует отвлечься и прояснить некоторые детали:
Процесс может сильно различаться в разных заведениях. Просто имейте это в виду и не используйте эту статью как инструкцию к действию.
Бордель, если говорить про тип заведения, мы, программисты называем просто — program, а конкретно наш, припортовый, зовем process.
Когда мы рассматриваем администратора, проститутку или любого другого сотрудника как живого человека, который может выполнять простые действия, то мы подразумеваем, что это thread.
А вот процесс выполнения этих, логически связанных друг с другом действий, например возвратно-поступательные движения, именуемые сексом, называем algorithm.
// algorithm
Runnable life = () -> {
while (isAlive()) {
work(Duration.ofHours(19));
sleep(Duration.ofHours(5));
}
};
// thread
var human = new Thread(life);
human.start();Успешность борделя будем оценивать при помощи следующих метрик: сколько клиентов за ночь можем обслужить (throughput или пропускная способность) и сколько времени пройдет с момента, когда придет очередной клиент, открыв старую скрипучую деревянную дверь, и уйдет со счастливой улыбкой на лице, закрыв её за собой (latency или задержка). Деньги в кассе не трогаем, пусть этим займутся другие люди.
Если throughput будет маленьким (передержали в холодном море), а latency очень большим, особенно когда очередной контейнеровоз прибыл в порт и его команда решила этой ночью расслабится в нашем заведении, то будь уверен: треть из них будет громко материться, треть — набухается до поросячьего визга, а еще треть просто уйдет выломав дверь. И никто не будет доволен; у многих людей по всему району, с огромной вероятностью, еще и лица будут разбиты (такая ситуация называется bottleneck).
Поэтому пытаемся всеми силами повышать трупут и снижать латенси. Можно делать свою работу очень быстро, оптимизировать каждое движение, обучить проституток различным техникам, но все мы знаем, что это не всегда помогает.
Ситуацию можно решить построив рядом еще один бордель, с другими администраторами, проститутками и декорациями в комнатах. Этим мы увеличим пропускную способность, как и затраты на содержание, что уже выглядит не так привлекательно. Потребуется человек, который будет направлять посетителей в один из этих борделей (это же обязанность reverse proxy).
Решение отличное, но о нём как-нибудь в следующий раз. Сейчас будем рассматривать только то, что происходит в отдельно взятом борделе, даже если их целая сеть по стране.
И да, везде будем использовать очереди (структура данных, знакомая всем с детства, работающая по принципу “первый вошел, первый вышел”, может иметь ограничение по количеству находящихся в ней человек), иначе посетители будут толпиться в самых неудобных для этого местах, затрудняя работу сотрудникам.
Перспективы роста, дружная молодая команда и на кухне печеньки есть
Итак, мы имеем относительно ровный поток посетителей и редко возникающую пиковую нагрузку. Поэтому администраторов, проституток и других сотрудников должно быть несколько на одну позицию, с возможностью быстро привлечь к работе еще большее их количество. Как будем решать? Способов несколько.
Первый. Как только потребуется еще один администратор, размещаем вакансию, общаемся с кандидатами, принимаем на работу, обучаем, выдаем бейджик и пускаем за стойку (это создание нового thread-а). Способ, сразу скажу, может быть очень долгим. Да и сколько людей хотим нанять? Для максимальной пропускной способности и минимальной задержки, должно быть столько же сотрудников, сколько и посетителей (этот подход называется thread per client). Но в наше время хороший сотрудник на вес золота, непозволительная роскошь.
Хотя на должность администратора можно взять несколько бомжей; они третий год живут на соседней заброшке в коробках из-под холодильников. А когда наплыв посетителей спадет, очередной сухогруз отправится в свое дальнее плавание, попросту их уволим. В будущем как-нибудь разберемся. Дай бог они не сопьются или их не растащат на органы врачи из ближайшей городской больницы (примерно так я вижу себе ручное создание тредов посреди кода). С проститутками такой способ не прокатит: думаю мало кто захочет, чтобы их ублажал бомж.
Следующий способ, с точки зрения ресурсов, более затратный, но имеет огромное преимущество. Заранее нанимаем какое-то количество сотрудников, обучаем, сажаем в специальную комнату, вешаем табличку thread pool. Пока бордель пуст, они сидят в ней, попивают чай, болтают, смотрят новости по телевизору. Как только приходят посетители, надевают на себя пиджаки с различными бейджиками, выходят из комнаты и начинают обслуживать посетителей (такой подход называется worker thread).
Кстати о том, как устроены эти комнаты. В каких-то случаях такой комнатой может выступать небольшая каморка со шваброй, чистящими средствами и запасами гандонов на 20 лет вперед. Туда вряд ли поместится больше одного сотрудника (это будет single thread pool).
log.info("так создается тред пул из одного треда (single thread pool)");
var singleThreadPool = Executors.newSingleThreadExecutor();
log.debug("а так мы можем начать выполнение кода в этом тред пуле");
singleThreadPool.execute(() -> {
log.debug("этот код будет исполнятся в отдельном треде");
doProstitute();
log.debug("закончили с этим...");
});
log.debug("вот этот код будет выполнен, когда предыдущая задача будет выполнена");
singleThreadPool.execute(() -> {
log.debug("этот код так же будет выполнятся в другом треде");
meetClients();
});
log.debug("При этом мы не заблокируем выполнение этого треда");В других же это будет огромный зал, который может вместить в себя десятки, а может быть и сотню сотрудников разного сорта. И если количество сотрудников неизменно, это fixed thread pool. Если оно может меняться, то это будет scalable thread pool. Как пример, посадим в неё смотрителя, который будет следить за наполнением этой комнаты. Мало работы — половину увольняет, не хватает рук — бежит на заброшку за бомжами или звонит в ближайшее hr-агентство.
log.info("а теперь посмотрим на fixed thread pool");
var fixedThreadPool = Executors.newFixedThreadPool(2);
log.debug("запускаем выполенение кода в отдельном треде");
fixedThreadPool.execute(() -> {
log.debug("этот код будет исполнятся в отдельном треде");
doProstitute();
log.debug("закончили с этим...");
});
log.debug("и одновременно запускаем еще одну задачу ");
fixedThreadPool.execute(() -> {
log.debug("этот код будет исполнятся в отдельном треде, одновременно");
meetClients();
log.debug("с этим тоже закончили...");
});
log.debug("а вот эта задача подождет, пока в тред пуле появится свободнй тред");
fixedThreadPool.execute(() -> {
log.debug("но так же будет выполнена в отдельном треде");
testVenerealDiseases();
});
log.debug("а этот тред пойдет дальше");log.info("и последний - scalable thread pool");
var scalableThreadPool = Executors.newCachedThreadPool();
log.debug("запускаем выполенение кода в отдельном треде, несколько раз");
for (int i = 0; i < 5; i++) {
scalableThreadPool.execute(() -> {
log.debug("этот код будет исполнятся в отдельном треде");
doProstitute();
log.debug("закончили с этим...");
});
}
log.debug("накидаем еще немного задач");
for (int i = 0; i < 3; i++) {
scalableThreadPool.execute(() -> {
log.debug("этот код будет исполнятся в отдельном треде, одновременно");
meetClients();
log.debug("с этим тоже закончили...");
});
}
log.debug("и еще одну, последнюю");
scalableThreadPool.execute(() -> {
log.debug("проверим всех на венерические");
testVenerealDiseases();
});
var tp = (ThreadPoolExecutor) scalableThreadPool;
log.debug("а тут мы посмотрим, сколько у нас тредов было создано: {}", tp.getPoolSize());
// у меня в консоле получилось 9
// пять проституток, три администратора и один лаборантПравилом хорошего тона считается иметь разные комнаты для разных сотрудников, проституток и администраторов. И причина тут не в том, что они оргию устроят, когда клиентов нет. Тяжело понять на глаз, кто закончился, а кого в избытке, да и может сложиться ситуация, когда проститутка пойдет за стойку регистрации, схватив пиджак с чужим бейджиком, а администратора утащат в комнату отдыха пара огромных волосатых мужиков, которые не хотят ждать. Им все равно, а мы потеряем ценного сотрудника.
Поэтому кадровый план следующий: если посетители долго стоят в очереди при входе — нужно больше администраторов. Если они в ярости ломают друг другу лица, часами ожидая когда освободится единственная, уже до смерти усталая проститутка — увеличиваем штат проституток. Каждому типу сотрудников по своей комнате отдыха (в реальной жизни не самая лучшая стратегия, но, для примера, подходит идеально).
Ого, он такой… асинхронный?!
Что по процессам? Есть процесс регистрации посетителя и процесс его соития с проституткой, есть еще один... но то, что происходит в туалете, остается в туалете. Все они независимы друг от друга и других процессов, происходящих в борделе в этот момент (с точки зрения многопоточности эти процессы будут называться parallel).
Огромный плюс регистрации в том, что этот процесс можно разделить на части, которыми одновременно будут заниматься разные сотрудники. Для получения финального результата нужно собрать воедино всё промежуточные результаты. Не пытайтесь повторить такое с сексом, так не работает.
Попробуем разделить регистрацию. Для этого заводим службу безопасности и берем на работу пару студентов из меда, сажаем всех их в две каморки за ресепшеном и вешаем таблички на дверь, чтобы не перепутать. Служба безопасности будет проверять документы посетителей, а студенты — наличие различных заболеваний. Это разгрузит администратора, уменьшит задержки и увеличит пропускную способность.
При регистрации администратор берет паспорт посетителя и относит его в службу безопасности, а самого клиента отправляет сдавать анализы. Процесс забора биоматериала происходит достаточно быстро, поэтому клиент практически сразу же выходит из лаборатории, а вот результатов обеих процедур надо немного подождать, в это время администратор продолжает процесс регистрации (это называется асинхронным взаимодействием).
Точкой синхронизации этих трех параллельных процессов будет момент оплаты, когда администратор берет деньги с клиента, он должен быть на сто процентов уверен, что этот персонаж полностью безопасен. Обычно звонки из службы безопасности и лаборатории с результатами случаются раньше, чем наступает этот момент, поэтому проблем не возникает. В случае, если администратор не получил хотя бы один звонок, то он сидит в неловкой тишине и смотрит в потолок (примерно так и работают futures). Получив все недостающие ответы, администратор принимает решение по следующему шагу: либо он рассчитывает клиента и пропускает его дальше, либо вежливо предлагает покинуть заведение.
Что делать, если посетитель пошел в лабораторию, но не вернулся до того момента, когда администратор уже сбегал в службу безопасности? Ничего, ждать возвращения посетителя, без него продолжать регистрацию невозможно (wait-notify механизм).
Если бы всё было так просто, это знали бы все
Настало время метрик. Сейчас у каждого из администраторов есть свой личный блокнот к которому имеет доступ только он, и после регистрации каждого посетителя администратор записывает в блокнот статистику по клиентам (такие вещи называются thread local storage). В конце рабочего дня каждый администратор вырывает страницу из блокнота и отдает её охраннику, который всё это время молча сидел рядом со входом на своем протертом до поролона кресле, читая газету и, иногда, что-то комментируя себе под нос. Кстати, про него еще ходят слухи, что он побил того самого Али, когда тот был в своей лучшей форме.
Работа охранника — не только охранять бордель от буйных клиентов, но еще и собирать со всех администраторов листочки со статистикой и записывать информацию по посетителям в толстенный журнал. Данный метод работает плохо: часть листочков теряется, калькулятора у охранника нет, он уже стар и косячит с цифрами. Статистику можно получить только за предыдущие сутки. Поэтому владелец борделя решил, что каждый администратор после того, как зарегистрировал посетителя, должен выйти в лобби и на доске перед входом прикрепить лист А4, на котором будет текущее количество посетителей (да, это самый обычный счетчик посетителей). Лист обязательно убрать в файл, и каждому посетителю будет видно, что наш бордель место популярное (это называется shared resource, а значит сейчас начнется самое интересное — concurrency).
Ровно в полдень и ни секундой позже тот самый охранник должен сорвать листок и приклеить новый, на котором красуется цифра 0. Старое значение он, конечно же, записывает в свой журнал.
Стоит сказать, что увеличение счетчика — сложный процесс, состоящий из трех этапов: вначале надо узнать текущее значение, дальше следует взять калькулятор или посчитать в уме новое значение, и в самом конце — записать новое значение туда, где каждый его увидит... на лист бумаги, прямо перед входом. Кстати, если бы существовали компьютеры, мало что бы изменилось, ведь этот процесс, внутри еще не изобретенных машин для просмотра котиков на ютубе, происходил бы абсолютно так же, только во много раз быстрее.
Каждому администратору была дана четкая инструкция, как работать с этим счетчиком (она выше), но люди существа ленивые, поэтому они стали запоминать последние значения счетчика: зачем лишний раз ходить? Когда посетитель радостно поднимается наверх, чтобы воплотить свои самые сокровенные и грязные желания в жизнь, то администратор просто вспоминает текущее значение, прибавляет единицу, и радостно несет клеить бумажку на стену. Есть еще более ленивые персонажи, курильщики — они ходят обновлять счетчик не каждый раз, а только когда идут на перекур, по возвращению смотрят на число, записанное на бумажке, и запоминают его (вот как-то так и работает кэш процессора).
Когда администратор работает один, проблем тут никаких нет: в конце дня всё сходится, если только он не убежал домой, забыв повесить на стене последнее запомненное значение. Но если администраторов несколько, все работают в спешке, подобная привычка сделает этот счетчик бессмысленным.
Представим двух администраторов: один уже полчаса общается с довольно похотливым, но очень медленным старикашкой. Тот переспрашивает всё по три раза, по второму кругу рассказывает, чем он будет заниматься наверху, а потом долго отсчитывает сумму самыми мелкими монетами. Второму, можно сказать, повезло и вот уже третий посетитель молча выкладывает на стол нужную сумму денег и довольно быстро поднимается наверх.
После очередного молчуна наш “везунчик” (если его можно так назвать), закрывает глаза и вспоминает, что же он последний раз записывал. 23? Да, 23! Прибавляет к этому числу три — 26; при этом он этом хлопает себя по нагрудному карману — сигареты еще есть, отлично, пора перекурить. Записывает это число и радостно идет к доске вешать свой лист, после чего выходит на улицу любоваться рассветом. Он курит медленно, долгий, тяжелый вдох, задержать дыхание, быстрый выдох. Он делает это для того, чтобы растянуть удовольствие, чтобы никотин ударил в мозг и мир немного пошатнулся, да и кашель бьет по легким не так больно. Он знает, что до конца года не доживет, пагубная привычка добила его окончательно.
В это время первый наконец-то заканчивает общаться с дедушкой и вспоминает, что в последний раз, когда он ходил немного отлить, видел на стене число 23, поэтому он записывает 24 и идет вешать его на доску, ему плевать какое значение висит там. Второй, вернувшись с одного из своих последних перекуров, смотрит на доску. Там 24. Ему все равно что он там записал, главное запомнить — 24, 24, 24… и уходит обслуживать следующего клиента.
static int count = 0;
private static void incrementCounter() {
count++;
}
private static int getCounter() {
return count;
}
public static void main(String[] args) {
var administrators = Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++) {
administrators.execute(() -> {
log.debug("администратор начал работу");
for (int n = 0; n < 100; n++) {
doSomeAdminStuff();
incrementCounter();
}
log.debug("администратор закончил работу");
});
}
awaitMorning();
log.debug("а сколько у нас посетителей было (должна быть тысяча): {}", getCounter());
// [main ] - а сколько у нас посетителей было (должна быть тысяча): 762
}Математика не сходится, анализируем происходящее. Добавляем в инструкцию администраторов пункт на полный запрет что-либо там запоминать (это же volatile). По логике, это должно помочь решить проблему. Но уже несколько раз все те же два администратора попадали в следующую ситуацию: они почти одновременно заканчивают регистрировать посетителей, оба идут к доске, видят 11. Каждый возвращается за стойку, прибавляет единицу, оба записывают новое число на листок, у каждого получилось 12. Оба идут клеить свой листок на доску. (такая ситуация зовется race condition, к сожалению, она никуда не делась)
static volatile int count = 0;
private static void incrementCounter() {
count++;
}
private static int getCounter() {
return count;
}
public static void main(String[] args) {
var administrators = Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++) {
administrators.execute(() -> {
log.debug("администратор начал работу");
for (int n = 0; n < 100; n++) {
doSomeAdminStuff();
incrementCounter();
}
log.debug("администратор закончил работу");
});
}
awaitMorning();
log.debug("а сколько у нас посетителей было (должна быть тысяча): {}", getCounter());
// [main ] - а сколько у нас посетителей было (должна быть тысяча): 988
}Пора запретить этот бардак
Нельзя терять посетителей, пусть даже на бумаге. Решение приходит само собой: надо запретить администраторам одновременно обновлять этот счетчик (привет lock, mutex и критические секции). Хозяин борделя пишет новую инструкцию: когда администратор подходит к доске, и видит число, то первым делом он должен прикрепить лист со своим именем (это lock acquire или вход в критическую секцию), а уже потом делать все сложные вычисления и обновлять это значение. Если видит свое имя, то первый пункт можно пропустить. Если чужое, то он обязан стоять и ждать до тех пор, пока сотрудник, чье имя написано на листе, не вернется и не снимет лист со своим именем с доски (эта операция называется снятием блокировки — lock release или выходом из критической секции).
При этом в инструкции не указано как именно сотрудники, которые столпились у доски, должны решать кто будет первым вешать свое имя на доску когда увидит число (это называется unfair lock). Кто быстрее — того и доска. В конечном счете они коллективно решили, что гораздо честнее будет выстраиваться в очередь перед доской (это уже fair lock).
final static Lock lock = new ReentrantLock();
static int count = 0;
private static void incrementCounter() {
try {
lock.lock();
count++;
} catch (Exception ignore) {
} finally {
lock.unlock();
}
}
private static int getCounter() {
try {
lock.lock();
return count;
} catch (Exception e) {
throw new RuntimeException(e);
} finally {
lock.unlock();
}
}
// или можно использовать ключевое слово synchronized
// private static synchronized void incrementCounter() {
// count++;
// }
// private static synchronized int getCounter() {
// return count;
// }
public static void main(String[] args) {
var administrators = Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++) {
administrators.execute(() -> {
log.debug("администратор начал работу");
for (int n = 0; n < 100; n++) {
doSomeAdminStuff();
incrementCounter();
}
log.debug("администратор закончил работу");
});
}
awaitMorning();
log.debug("а сколько у нас посетителей было (должна быть тысяча): {}", getCounter());
// [main ] - а сколько у нас посетителей было (должна быть тысяча): 1000
}Сработало, цифры сходятся. Метрики считаются корректно, владелец наконец-то счастлив, разве что иногда высказывает свое недовольство, когда видит, что его сотрудники могут по 15-20 минут торчать у доски, ожидая своей очереди, а самого значения счетчика не видно. Но подход отлично работает, поэтому он был использован во всех возможных и невозможных местах.
Как я уже говорил в самом начале, после общения с администратором посетитель получает одну или несколько карточек со случайным номером (анонимность в данном деле превыше всего). Их количество зависит от толщины кошелька и фантазий, которые даже своему психологу не рассказывают. А дальше он сам решает как будет проводить время: хоть с каждой по отдельности, хоть со всеми сразу. Надо вручить проститутке карточку, сказать в какую комнату идти, дальше либо последовать за ней, либо проделать ту же самую операцию еще раз.
Когда-нибудь это должно было случиться. В бордель заходят два моряка, один — старый колоритный морской волк, всё повидал, всех в этом борделе по многу раз пере-это-самое, и сегодня он решил, что надо взять сразу двух проституток: новенькую, молодую неопытную Алису, и вторую, прожжённую курву, жизнь повидавшую, пускай её имя будет Боб. Старику уже давно хотелось всё бросить и иметь нормальную семью. Второй моряк — молодой парень, для него наступила пора проб и ошибок и по совету администратора он обратил свое внимание на Боба и Алису. Как говориться, если и пробовать, то всё сразу.
Волчара первым делом отдал свою карточку Алисе, перекинулся парой фраз, отправил её в комнату, и пошел искать Боба. В этот самый момент второй моряк отдал свою карточку Бобу, так же отправил в комнату и пошел искать… Алису. Ходили они долго, искали тщательно, но каждый пришел сюда за своей целью, от которой отказываться никак не хотел. Паренек даже к администратору подходил несколько раз, спрашивал про Алису, но тот выдавал стандартную фразу: она занята, надо немного подождать, скоро освободится. Наступило утро, мелкий паренек весь на нервах, уже в шестой раз в туалете сбрасывает напряжение, а старый морской волк как присел на диван в холле, тихо посапывая, так и помер, не вставая с места (это пример типичного deadlock-а). Они так и не смогли за ночь найти, каждый свою вторую проститутку.
Ситуация не из приятных, скорая помощь, слезы, разбитые лица и прочая утренняя рутина. Деньги пришлось вернуть, услуга не была оказана и появился первый негативный отзыв в путеводителе. Одни потери, как финансовые, так и репутационные.
var alice = new Prostitute("Alice");
var bob = new Prostitute("Bob");
var oldSailor = new Thread(() -> {
log.debug("пойти искать Алису");
findProstitute();
synchronized (alice) {
log.debug("выбрать Алису");
log.debug("пойти искать Боба");
findProstitute();
synchronized (bob) {
log.debug("выбрать Боба");
log.debug("Умотать в комнаду с двумя проститутками");
}
}
});
var yongSailor = new Thread(() -> {
log.debug("пойти искать Боба");
findProstitute();
synchronized (bob) {
log.debug("выбрать Боба");
log.debug("пойти искать Алису");
findProstitute();
synchronized (alice) {
log.debug("выбрать Алису");
log.debug("Умотать в комнаду с двумя проститутками");
}
}
});
oldSailor.setName("Old Sailor");
oldSailor.start();
yongSailor.setName("Young Sailor");
yongSailor.start();
// [Young Sailor ] - пойти искать Боба
// [Old Sailor ] - пойти искать Алису
// [Young Sailor ] - выбрать Боба
// [Old Sailor ] - выбрать Алису
// [Young Sailor ] - пойти искать Алису
// [Old Sailor ] - пойти искать БобаПовторения данного инцидента не хотелось и были приняты следующие решения: всех сотрудниц записали в журнал по имени-фамилии, году рождения, отсортировали в алфавитном порядке и теперь посетитель, если он хочет утех сразу с несколькими проститутками, должен отдавать им карточки и отправлять в комнату только в этом, алфавитном порядке, и никак иначе (circular wait condition). Это первое. И второе: если проститутка уходит в комнату, а посетитель не приходит в течение 10 минут, она должна выйти из комнаты, мало ли что произошло. Номерок она обязана вернуть посетителю, чтобы он мог попробовать всю процедуру провести еще раз, с самого начала. Комментарий от владельца заведения был следующий: нечего других задерживать, если в данный момент все твои желания не могут быть исполнены.
Если бы первое условие было выполнено, то дедушка умер бы раньше, но гораздо более счастливым.
А другие способы существуют?
После ситуации с дедушкой экспериментировать на посетителях никто больше не решался. Администраторы — другое дело: им изменили правила подсчета, запоминать теперь не просто можно, а нужно. Больше никаких листов с именем. Теперь каждый администратор обязан запомнить последнее увиденное число на доске, сделать все необходимые вычисления за стойкой, а когда он возвращается обратно, то должен сравнить число, которое он запомнил с фактическим, на доске, которое, в свою очередь, к этому времени могло и поменяться. Только если эти два числа совпадали, только тогда он мог повесить на стену листок с уже увеличенным значением (это compare and swap, либо compare and set). Если число, которое он запомнил не совпало с фактическим, он обязан, обязан начать все заново, вдруг ему повезет в следующий раз (именно так и работают lock-free алгоритмы).
var administrators = Executors.newFixedThreadPool(10);
var counter = new AtomicInteger();
for (int i = 0; i < 10; i++) {
administrators.execute(() -> {
log.debug("администратор начал работу");
for (int n = 0; n < 100; n++) {
doSomeAdminStuff();
// неблокирующее обновление счетчика
counter.incrementAndGet();
}
log.debug("администратор закончил работу");
});
}Эксперимент удался. В любой момент можно посмотреть текущее значение счетчика, спонтанные очереди рядом с доской ушли в прошлое. Но появилась проблема. Возьмем пару администраторов и выделим среди них одного, который по два-три раза перепроверяет свои вычисления, всё у него четко, но парень медленный, да и отвлекаться любит часто. Подходит он к доске, чтобы повесить 32, но не может, там висит 33, запоминает его и уходит за стойку, достает калькулятор, считает два раза и еще один раз в уме, всегда получается 33, значит именно это он и должен записать на листочке. Записывает, идет к доске, а там уже 35. Да что такое?! Ладно, нужно второй раз сходить, запомнил 35, садится считать… но тут захотелось ему поссать, сбегал поссал, возвращается к доске с 36, а там висит 37
После двадцатой итерации ему это надоедает: он уже три часа бегает от стойки к доске и обратно. Жрать хочет адски, в желудке дыра, бросить работу не может, счетчик обновить надо, а сколько он так будет бегать туда-сюда не представляет. прошлый раз до утра пробегал, пока все клиенты не ушли. Так и с голоду помереть можно (это типичный пример starvation).
var administrators = Executors.newFixedThreadPool(10);
var counter = new AtomicInteger();
for (int i = 0; i < 9; i++) {
administrators.execute(() -> {
log.debug("администратор начал работу");
for (int n = 0; n < 100; n++) {
doSomeAdminStuff();
while (true) {
var current = counter.get();
doItSlowly();
var success = counter.compareAndSet(current, current + 1);
if (success)
break;
}
}
log.debug("администратор закончил работу");
});
}
administrators.execute(() -> {
int iHateMyJob = 0;
log.debug("медленный администратор начал работу");
for (int n = 0; n < 100; n++) {
doSomeAdminStuff();
int uhhh = 0;
while (true) {
var current = counter.get();
doItExtremelySlowly();
var success = counter.compareAndSet(current, current + 1);
if (success)
break;
uhhh++;
}
iHateMyJob = Math.max(iHateMyJob, uhhh);
}
log.debug("медленный администратор закончил работу, уровень ненависти: {}", iHateMyJob);
});
// У меня на первом запуске получилось так:
// [pool-2-thread-10 ] - медленный администратор закончил работу, уровень ненависти: 467
// 467 попыток обновить значение, неплохо
И ладно, если бы это были проблемы только одного медленного администратора, бегает, тратит силы, плевать на него. Для работы борделя это не просто пустая трата времени, а увеличение задержек и снижение пропускной способности. Мы же стараемся сделать наоборот. Ради этого переоборудовали входную группу так, что к каждому администратору своя небольшая очередь, как в продуктовом магазине к кассам. Люди существа не слишком умные и, стоя в самом начале очереди, они начинают иногда тупить и задерживать всех остальных, очень долго выбирая к какому администратору пойти. Поэтому им приходится выбирать очередь в самом начале, в которой придется стоять до момента регистрации. Один из администраторов, вместо того, чтобы начать обслуживать следующего посетителя бегает туда-сюда с горящей жопой, остальные своих уже обслужили и начинают зазывать людей к себе, с конца очереди (такой подход называется work stealing). Но все равно нерасторопный сотрудник к утру часто получает негативный отзыв нецензурной бранью и хорошим таким хуком в красивое личико.
С таким подходом подсчета очень важно понимать, что в какой-то момент следует прекратить эту бессмысленную беготню (которая используется по умолчанию во всех неблокирующих алгоритмах и называется fast path) и перейти к решительным действиям. В нашем случае, после третьего неудачного раза, начинаем использовать старую добрую бумажку с именем (обратная сторона неблокирующих алгоритмов: вначале пробуем несколько раз пройтись по fast path, если не получается, переходим к slow path, который сложнее и дольше, но точно сработает с первого раза. В случае, если мы точно можем посчитать количество шагов за которое алгоритм синхронизации будет выполнен, он будет уже wait-free).
А ведь раньше я на железной дороге работала, Semapwhores
Наконец-то закончили с этими скучными администраторами, пусть они себе и дальше спокойно бегают, циферки складывают, переходим к самому интересному — к проституткам.
В нашем борделе есть четкое правило: не больше четырех посетителей на одну стандартную комнату с огромной кроватью, при этом не уточняется кто с кем будет совокуплятся и будут ли вообще проститутки. А если берете огромный президентский люкс и штук пять проституток, то в нём уже можно будет устроить групповой заплыв всей команды небольшого рыболовного баркаса.
Для реализации этого плана, рядом с каждой комнатой, в которой будет происходить непотребство, стоит охранник. Он контролирует количество входящих и выходящих людей, его кодовое имя — semapwhore (именно таким образом работает примитив синхронизации semaphore, в основе которого лежит счетчик с permit).
Как только матрос входит в комнату, охранник в своей голове проводит сложные математические вычисления по уменьшению данного счетчика. Если матрос худой, значит минус один, если огромный жирный потный мужик, значит считаем за двух (операция acquire(count), которая уменьшает количество пермитов). Когда кого-то во время пьяного угара выкинут в окно и он захочет вернуться в комнату через дверь, никакие уговоры не помогут, бедолагу посчитают еще раз. Выходить можно строго через дверь (тогда сработает обратная операция release(count), которая увеличит количество пермитов).
Также, матросу придется подождать, если в голове у охранника нулевое количество пермитов или их попросту недостаточно, матрос уж слишком жирный для прохода, а пермитов хватит только на худого. Уговаривать охранника можно только если цель — убить время, ожидая пока кто-нибудь выйдет из этой комнаты через дверь.
var semaphore = new Semaphore(4);
var sailors = Executors.newFixedThreadPool(10);
var counter = new AtomicInteger();
for (int i = 0; i < 10; i++) {
sailors.execute(() -> {
try {
log.debug("Морячок пытается войти в комнату");
semaphore.acquire();
counter.incrementAndGet();
log.debug("Морячок вошел в комнату, а там еще {} морячка", counter.get());
SleepUtils.sleepQuietlyAround(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
finally {
counter.decrementAndGet();
semaphore.release();
log.debug("Морячок вышел из комнаты, а там осталось {}", counter.get());
}
});
}
// [pool-2-thread-1 ] - Морячок пытается войти в комнату
// [pool-2-thread-3 ] - Морячок пытается войти в комнату
// [pool-2-thread-5 ] - Морячок пытается войти в комнату
// [pool-2-thread-6 ] - Морячок пытается войти в комнату
// [pool-2-thread-10 ] - Морячок пытается войти в комнату
// [pool-2-thread-7 ] - Морячок пытается войти в комнату
// [pool-2-thread-9 ] - Морячок пытается войти в комнату
// [pool-2-thread-4 ] - Морячок пытается войти в комнату
// [pool-2-thread-2 ] - Морячок пытается войти в комнату
// [pool-2-thread-8 ] - Морячок пытается войти в комнату
// [pool-2-thread-6 ] - Морячок вошел в комнату, а там еще 3 морячка
// [pool-2-thread-5 ] - Морячок вошел в комнату, а там еще 2 морячка
// [pool-2-thread-10 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-3 ] - Морячок вошел в комнату, а там еще 2 морячка
// [pool-2-thread-8 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-6 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-5 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-7 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-2 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-10 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-3 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-9 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-7 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-4 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-1 ] - Морячок вошел в комнату, а там еще 4 морячка
// [pool-2-thread-8 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-2 ] - Морячок вышел из комнаты, а там осталось 3
// [pool-2-thread-9 ] - Морячок вышел из комнаты, а там осталось 2
// [pool-2-thread-4 ] - Морячок вышел из комнаты, а там осталось 1
// [pool-2-thread-1 ] - Морячок вышел из комнаты, а там осталось 0Представим ситуацию, в бордель забежала команда по гребле, только с международных соревнований, которые по стечению обстоятельств проходили в нашем городе. Работать синхронно и слаженно у них в крови — по другому победы не достичь никогда. Набрали проституток, каждому по одной, без всяких проблем зашли в люкс и начали заниматься сексом, каждый со своей.
Данный процесс для них, как для команды, невероятно сложен: каждая пара находит место поудобнее, в этих царских хоромах этот процесс занимает время. Три пары оказались на кровати, одна на полу в прихожей, парочка на кресле уже разделась и готова к старту. Все ждут последнюю пару (await), которая пытается поудобнее устроиться на кухне. Как только все будут готовы, словно по выстрелу сигнального пистолета, они начинают заниматься сексом (так работает примитив синхронизации barrier, который создается со счетчиком, последний тред вызвавший метод await продолжает выполнение в каждом потоке).
Их движения синхронны, охи и вздохи слышны в такт, но организм у каждого разный, поэтому длительность процесса варьируется, кто закончил — отдыхает, ждет всех остальных, мило беседуя со своей партнершей (обычно мы имеем дело с cyclicbarrier, который позволяет несколько раз использовать этот примитив синхронизации). Как только последний закончит, все начинают менять локацию, ждут окончания процесса. Вторую попытку начинают все также синхронно, после того как последняя парочка устроиться поудобнее.
var rowers = Executors.newFixedThreadPool(4);
var barrier = new CyclicBarrier(4);
for (int i = 0; i < 4; i++) {
rowers.execute(() -> {
try {
log.debug("Пловец выбирает место");
findPlace();
log.debug("Пловец нашел место");
barrier.await();
log.debug("Пловец начинает заниматься сексом");
doSex();
log.debug("Пловец кончил, ждет остальных");
barrier.await();
log.debug("Решают, что надо еще раз, меняют позиции");
findPlace();
log.debug("Пловец нашел новое место");
barrier.await();
log.debug("Пловец начинает заниматься во второй раз");
doSex();
log.debug("Пловец кончил, ждет остальных");
barrier.await();
log.debug("Выходит из комнаты счастливым");
} catch (Exception e) {
e.printStackTrace();
}
});
}
// [pool-2-thread-4 ] - Пловец выбирает место
// [pool-2-thread-3 ] - Пловец выбирает место
// [pool-2-thread-2 ] - Пловец выбирает место
// [pool-2-thread-1 ] - Пловец выбирает место
// [pool-2-thread-1 ] - Пловец нашел место
// [pool-2-thread-3 ] - Пловец нашел место
// [pool-2-thread-2 ] - Пловец нашел место
// [pool-2-thread-4 ] - Пловец нашел место
// [pool-2-thread-4 ] - Пловец начинает заниматься сексом
// [pool-2-thread-1 ] - Пловец начинает заниматься сексом
// [pool-2-thread-3 ] - Пловец начинает заниматься сексом
// [pool-2-thread-2 ] - Пловец начинает заниматься сексом
// [pool-2-thread-3 ] - Пловец кончил, ждет остальных
// [pool-2-thread-4 ] - Пловец кончил, ждет остальных
// [pool-2-thread-2 ] - Пловец кончил, ждет остальных
// [pool-2-thread-1 ] - Пловец кончил, ждет остальных
// [pool-2-thread-1 ] - Решают, что надо еще раз, меняют позиции
// [pool-2-thread-3 ] - Решают, что надо еще раз, меняют позиции
// [pool-2-thread-4 ] - Решают, что надо еще раз, меняют позиции
// [pool-2-thread-2 ] - Решают, что надо еще раз, меняют позиции
// [pool-2-thread-4 ] - Пловец нашел новое место
// [pool-2-thread-2 ] - Пловец нашел новое место
// [pool-2-thread-3 ] - Пловец нашел новое место
// [pool-2-thread-1 ] - Пловец нашел новое место
// [pool-2-thread-1 ] - Пловец начинает заниматься во второй раз
// [pool-2-thread-4 ] - Пловец начинает заниматься во второй раз
// [pool-2-thread-2 ] - Пловец начинает заниматься во второй раз
// [pool-2-thread-3 ] - Пловец начинает заниматься во второй раз
// [pool-2-thread-3 ] - Пловец кончил, ждет остальных
// [pool-2-thread-4 ] - Пловец кончил, ждет остальных
// [pool-2-thread-2 ] - Пловец кончил, ждет остальных
// [pool-2-thread-1 ] - Пловец кончил, ждет остальных
// [pool-2-thread-1 ] - Выходит из комнаты счастливым
// [pool-2-thread-3 ] - Выходит из комнаты счастливым
// [pool-2-thread-4 ] - Выходит из комнаты счастливым
// [pool-2-thread-2 ] - Выходит из комнаты счастливымПредставим еще более дикую ситуацию (в которой будет участвовать примитив синхронизации countdownlatch, он также создается со счетчиком): день рожденья у одного из участников квартета, который исполняет в жанре А-капелла. Они сняли пять проституток и заготовили огромный торт, вручили самой страшной проститутке на этой части планеты, с четкой инструкцией: стоять за дверью и слушать (висеть на методе await, дожидаясь пока счётчик не станет равен нулю), как только четвертый раз прозвучит нота ля первой октавы, это фишка данного коллектива, издавать именно этот звук при достижении оргазма (в этот момент будет вызван метод countdown и значение счетчика уменьшится на единицу), войти в комнату с тортом и поздравить именинника.
План был хорош! После четвертой протяжной ноты ля, она врывается в комнату и видит как именинник, в окружении трех обессиленных коллег, в поте лица совершает возвратно-поступательные движения, чтобы издать этот магический звук. Полный провал. Объяснение простое — кто-то успел кончить два раза.
Следует всегда быть осторожным с countdownlatch, условие, по которому поток, висящий на методе await продолжит выполнение — внутренний счетчик, значение которого стало равным нулю, кто и сколько раз вызовет метод countdown, не имеет значения.
var singers = Executors.newFixedThreadPool(4);
var prostitute = Executors.newFixedThreadPool(1);
var latch = new CountDownLatch(4);
for (int i = 0; i < 3; i++) {
singers.execute(() -> {
log.debug("Певец начинает заниматься сексом");
doSex();
log.debug("Певец закончил");
latch.countDown();
log.debug("Певец решает еще разок");
doSex();
log.debug("Певец закончил еще раз");
latch.countDown();
});
}
singers.execute(() -> {
log.debug("Именнинник начинает заниматься сексом");
doSexSlowly();
log.debug("Именнинник закончил");
latch.countDown();
});
prostitute.execute(() -> {
try {
log.debug("Проститутка ждет задверью пока все закончат...");
latch.await();
log.debug("Простутутка входит в комнату с тортом");
} catch (Exception e) {
}
});
// [pool-2-thread-1 ] - Певец начинает заниматься сексом
// [pool-2-thread-3 ] - Певец начинает заниматься сексом
// [pool-2-thread-2 ] - Певец начинает заниматься сексом
// [pool-2-thread-4 ] - Именнинник начинает заниматься сексом
// [pool-3-thread-1 ] - Проститутка ждет задверью пока все закончат...
// [pool-2-thread-3 ] - Певец закончил
// [pool-2-thread-3 ] - Певец решает еще разок
// [pool-2-thread-1 ] - Певец закончил
// [pool-2-thread-1 ] - Певец решает еще разок
// [pool-2-thread-2 ] - Певец закончил
// [pool-2-thread-2 ] - Певец решает еще разок
// [pool-2-thread-3 ] - Певец закончил еще раз
// [pool-3-thread-1 ] - Простутутка входит в комнату с тортом
// [pool-2-thread-1 ] - Певец закончил еще раз
// [pool-2-thread-4 ] - Именнинник закончил
// [pool-2-thread-2 ] - Певец закончил еще раз По этическим соображениям, в данной статье будет опущено описание такого потока синхронизации как rendezvous (и нет, это не магазин с туфельками), хотя на практике, в нашем борделе, это один из самых часто используемых примитивов. На техническом языке он работает следующим образом: первый поток, приходя в точку рандеву, вызывает метод exchange(object) и ожидает, пока второй поток не сделает тоже самое. Дальше они оба продолжают работу.
Как с этим жить дальше
На сегодня всё, рабочий день подходит к концу, администраторы устало зевают, проститутки, не спеша, собираются домой, а охранник, который всё это время тихо сидел в углу и читал газету, встает со своего потертого кресла и идет обнулять счетчик посетителей.
Мы же, за эту долгую ночь, узнали о базовых понятиях, которые используется в многопоточном программировании, на примерах увидели как можно использовать примитивы синхронизации, разобрали какие проблемы могут возникнуть. И получили интересную тему для обсуждения с нашим психологом.
В следующий раз поговорим о более сложных вещах, таких как паттерны и парадигмы, которые в современном мире очень сильно снижают сложность написания и поддержки многопоточных систем.