Многоядерные процессоры являются обычным явлением.
Рано или поздно любому практикующему программисту придется войти в лабиринт многопоточного программирования и встретиться с населяющими его «монстрами».
Давайте поговорим о том, с чего начать на этом пути и какие инструменты и подходы помогут вам выйти победителем.
Этот отчет я передал будущим участникам круглогодичная стажировка Яндекс.
— Меня зовут Сева Миньков.
Я работаю в отделе облачной инфраструктуры отдела поиска.
Я работаю в основном над бэкэндом.
Я пишу на разных языках, но чаще всего это Java и языки, работающие на виртуальной машине Java (JVM).
Наша команда разрабатывает внутреннее облако, в котором запускаются практически все сервисы Яндекса — как общеизвестные, такие как Поиск, Почта и Алиса, так и всевозможные внутренние сервисы, виртуальные машины, а также недолговечные задачи MapReduce и машинные.
учебные задачи.
Наше облако не стоит на месте: компания растет, увеличивается количество сервисов и потребляемых ими ресурсов.
И наша команда очень часто сталкивается с проблемами масштабирования и повышения производительности.
Мы добиваемся этого, используя все доступные инструменты, включая вертикальное масштабирование — то есть ускорение отдельных компонентов системы, даже переписывая некоторые однопоточные алгоритмы, чтобы они работали быстрее.
Также мы занимаемся горизонтальным масштабированием: разбиваем систему на мелкие части для достижения большей производительности за счет добавления серверов, процессоров, ядер и т. д. И многопоточное программирование нам всем в этом очень помогает. Об этом мы сегодня и поговорим – откуда оно взялось, почему актуально; что такое модель памяти и как она обычно представлена в Java. Давайте коснемся некоторых практических аспектов того, как тестировать ваши приложения и проверять их корректность.
Для начала давайте взглянем на этот интересный график, показывающий тенденции в производительности микропроцессоров за последние 40 лет. Лет 10-15 назад, когда трава была зеленее, а процессоры были однопоточными, обычный программист мог однажды написать правильную однопоточную программу, а затем опираться на эмпирический закон Мура.
Он говорит, что процессоры становятся в два раза быстрее каждые два года.
Как видите, примерно в 2005 году по разным причинам производители микропроцессоров перешли на многоядерную архитектуру и начали увеличивать количество логических ядер.
И прирост производительности отдельного ядра перестал подчиняться закону Мура, и вычислительная мощность одного ядра стала расти медленнее.
Это произвело революцию, и обычным программистам пришлось использовать параллельное программирование, чтобы воспользоваться всем этим приростом производительности.
Поскольку мы практики, то попробуем написать простую многопоточную программу и своими глазами увидеть, как она работает. 
В качестве примера возьмем довольно простую задачу перекрестного чтения записей.
Пусть у нас есть две общие переменные X и Y, первоначально инициализированные значением по умолчанию (ноль), и два потока.
Каждый поток записывает в одну переменную и читает другую.
В этом случае Thread1 записывает один в X и читает Y. Второй поток делает то же самое, только в обратном направлении.
Простейшая реализация на Java может выглядеть примерно так.
Напишем класс ReadWriteTest, в нем будет две статические переменные X и Y. Прямо в основном методе мы сконструируем два потока Thread1 и Thread2, каждому из них дадим на вход некую лямбда-функцию, которая будет выполняться в момент выполнения потока.
выполняется.
Поместим туда код с предыдущего слайда и запустим два потока.
Порядок, в котором будут выполняться потоки, несколько непредсказуем.
Это зависит от того, как операционная система планирует потоки.
Соответственно, у нас могут быть разные варианты исполнения.
Похоже, чтобы понять, как все это работает, нам придется много раз запустить эту программу, затем агрегировать вывод и посмотреть, как часто в программе появляется тот или иной ответ. 
Ссылка со слайда
Чтобы не изобретать велосипед, можно воспользоваться готовым инструментом.Это так называемый jcstress — утилита стресс-тестирования Java Concurrency, входящая в состав проекта OpenJDK. Эта утилита предоставляет некоторую основу для написания стресс-тестов.
В этом случае код с предыдущего слайда можно довольно легко переписать.
Прежде всего, мы прикрепим к классу аннотацию jcstress Test, которая просто сделает наши тестовые сценарии видимыми для утилиты.
Мы также отмечаем его классом State, который говорит, что класс содержит данные, которые могут изменяться: как модифицироваться, так и считываться из разных потоков.
Давайте объявим два метода, thread1 и thread2, и отметим их аннотацией Actor. Аннотация Actor означает, что метод должен выполняться в отдельном потоке.
jcstress гарантирует, что каждый такой метод будет выполняться в отдельном потоке ровно в одном экземпляре класса State. Определенного порядка их запуска не существует. И запишем результат в некий объект II_Result, показанный на слайде.
Можно считать, что это кортеж из двух числовых значений, которые подаются с помощью метода Dependency Injection, о котором Кирилл рассказывал в предыдущем докладе.
Прежде чем запустить этот тест, давайте подумаем, какие выходные данные могут выдавать команды и какие значения мы можем добавить в r1 и r2. 
Для этого воспользуемся так называемой моделью чередования.
Так или иначе, каждая из операций: чтение или запись выполняется в каком-то порядке.
Достаточно просто комбинаторно перебрать все эти варианты и посмотреть, какие результаты мы получим.
Допустим, один из возможных сценариев заключается в том, что первый поток был полностью выполнен раньше второго.
Сначала мы добавили единицу к X и прочитали ноль из Y, так как там не было записей.
Затем мы написали один в Y и прочитали один из X, поскольку первый поток уже сделал это.
Первый ответ – ноль-один.
Второй сценарий прямо противоположен: второй поток выполняется раньше первого.
Соответственно, мы получаем зеркальный результат один-ноль.
Есть еще около четырех вариантов, которые дают тот же результат, когда наши нити полностью перепутаны.
Например, в одном потоке мы написали одно в X, во втором успели написать одно в Y, и вычисляем одно-единственное.
Затем в качестве домашнего упражнения вы сможете посмотреть, какие еще существуют варианты.
Кажется, мы перебрали все возможные варианты, больше ничего нет. Давайте запустим утилиту и посмотрим, какой результат она выдаст. 
Ссылка со слайда
Вывод выглядит как таблица.В первом столбце перечислены результаты, которые мы добавили к II_Result — утилита запускает этот код миллионы раз — и количество раз, когда конкретный результат вообще встречался.
Но этого отчета, вероятно, не было бы, если бы все было так просто.
Фактически, в этом выводе мы также можем видеть нулевой результат, который трудно объяснить с помощью модели альтернации.
Кажется, один из возможных вариантов — кто-то взял и переставил строки прямо в потоковом коде.
Давайте подумаем, почему это произошло и как нам с этим жить.
Еще прошу обратить внимание на то, что вариант one-one на моей машине встречался крайне редко.
Из 130 миллионов казней только 154 казни закончились результатом «один-один».
Напротив, ноль-ноль встречается очень часто, почти в 30% случаев.
Итак, подведем некоторые промежуточные итоги увиденного в целом.
Прежде всего, мы смогли понять, что взаимодействие потоков через память нетривиально.
Модель вращения, которую мы использовали, не работает. Мы стали свидетелями некоторых перестановок.
Это могло произойти по многим причинам.
Например, мы могли наблюдать некоторые «релятивистские эффекты» железа.
Вы можете представить это следующим образом: за один такт 3-ГГц процессора свет в вакууме успевает пройти около 10 см.
Протокол чтения и записи в память процессора сложен, и иногда для передачи значения от одного ядра к другому требуются многие сотни тактов.
Соответственно, одно ядро может как бы видеть прошлое.
Результат после записи произошел, но мы видим старое значение.
Кроме того, процессоры тоже не стоят на месте и могут менять инструкции.
Современные оптимизирующие компиляторы могут привести к такой же перестановке.
Для достижения максимальной однопоточной производительности они также могут менять местами инструкции, чтобы это не нарушало корректность однопоточной программы.
Но в многопоточных программах они могут привести к интересным эффектам, которые мы наблюдали.
И второй, наверное, главный вывод: мы увидели, что многопоточные программы принципиально недетерминированы.
Однопоточные программы обычно полагаются на некоторые инварианты ввода и вывода и являются детерминированными; учитывая, что генератор случайных чисел и пользовательский ввод являются входными параметрами.
Это очень все усложняет: сложно понять, что делает программа, и сложно ее протестировать.
По поводу сложности тестирования можно еще добавить, что один и тот же результат один в один произошел всего 154 раза из 130 миллионов вызовов.
Вероятность такого исхода составляет один на миллион.
В производстве это означает, что такая ошибка может быть воспроизведена неделями позже.
И это обязательно произойдет где-нибудь в воскресенье вечером, когда вы этого совсем не ждали.
Давайте подумаем, что нам следует делать и чего мы вообще хотим от языка, чтобы спокойно спать в воскресную ночь.
Во-первых, нам нужен инструмент, который позволит нам прогнозировать поведение программы и делать выводы о ее выполнении.
Во-вторых, нам нужны языковые средства, которые позволили бы нам влиять на перестановки и эффекты — они могут быть со стороны железа, компилятора и т. д. Нам бы хотелось меньше знать о том, как работает конкретный процессор, какие оптимизации может делать компилятор, и использовать аббревиатура, пришедшая из мира Java. Напишите один раз, запустите где угодно — напишите правильный многопоточный код один раз, чтобы он работал на всех платформах.
Эти вопросы и требования, которые мы перечислили, уже очень давно возникли в сознании разработчиков, как теоретиков, так и практиков.
Как любая сложная задача высокого уровня сложности, она решалась путем введения понятия некоторой абстрактной машины.
Все мы, разработчики языков программирования высокого уровня, пишем не для какого-то конкретного железа, не для такой-то модели процессора, а пишем какую-то абстрактную машину.
И спецификация языка предназначена для описания его поведения таким образом, чтобы примирить эти три мира.
С одной стороны, позволить разработчикам компиляторов и процессоров проводить собственные оптимизации и слегка взорвать мозги нам, программистам, уже пишущим на определенном языке.
Модель памяти занимает одно из центральных мест в этой абстрактной машине.
Оно должно ответить на один вопрос: если я прочитаю переменную X в каком-то потоке, результат какой из последних записей я вообще смогу там увидеть? Впервые на языке Java была предпринята попытка формализовать модель памяти; все остальные модели памяти появились позже.
Допустим, C++11 — это почти копия модели памяти Java с некоторыми изменениями.
В Java было несколько моделей памяти.
Изначально модель памяти была так называемой «thread-local»; его сочли неудачным, так как он затруднял работу обоих программистов, пишущих на Java, и запрещал компилятору производить некоторые вполне уместные оптимизации.
Соответственно, современная модель памяти была написана в рамках процесса сообщества JSR-133. Раз уж у нас есть священное писание в виде спецификации, попробуем разобраться в нем и понять, что на самом деле происходит внутри.
Здесь есть некоторая проблема.
Поднимите руки кто открыл спецификацию языка и прочитайте, что там происходит. Кто из вас читал в память модель параграфа 17.4? Вас ждет небольшой сюрприз.
Спецификация языка в принципе описана достаточно понятным языком.
Но модель памяти изобилует, скажем так, некоторым математическим хардкором.
Есть включения в греческом языке, много математических терминов из ряда транзитивное замыкание, объединение двух порядков и т.п.
К сожалению, другого пути нет. Единственное, на что можно положиться при написании многопоточных программ, — это спецификация.
Это надо будет прочитать и понять.
Я очень рекомендую это вам.
Более того, когда я впервые прочитал спецификацию, у меня сложились схожие впечатления.
Почему это так сложно? Я выбрал неверный путь и настоятельно советую вам поступить так же, как я.
Я взял и поискал в интернете, что такое модель памяти.
Я нашел книгу под названием JSR-133 «Поваренная книга для авторов компиляторов».
В нем описывается, как разработчик компилятора может простым способом реализовать эту модель памяти.
Проблема в том, что это одна конкретная реализация, и судить по ней обо всей модели памяти невозможно.
Давайте все же попробуем сделать небольшую попытку сделать основные выводы, которые можно понять из модели памяти Java. 
Ваша многопоточная программа может выполняться много раз.
Мы сами видели это на примере нашей программы ранее.
В нашем простейшем примере у нас уже было четыре результата от его выполнения.
И задача модели памяти Java — сказать, какие из этих исполнений правильные, а какие следует запретить.
И он постулирует три вещи.
Во-первых, в рамках одного потока ваша задача выполняется псевдопоследовательно.
Это означает, что компилятор может менять местами операции, процессор также может параллельно выполнять инструкции и менять их местами.
Но они должны делать это таким образом, чтобы видимые последствия выполнения вашей программы были такими же, как если бы она выполнялась непосредственно последовательно.
Во-вторых, в языке запрещены так называемые «из воздуха» значения, возникающие из ниоткуда.
К сожалению, у нас нет времени это показать, но бывают случаи, когда компилятор действительно может сделать такое преобразование, что в однопоточной программе все будет правильно, а в многопоточной у вас может возникнуть запись, что ты не сделал.
Соответственно, модель памяти говорит, что чтение любой переменной вернет либо значение по умолчанию, либо некоторые результаты записи, которая когда-то была произведена другой командой.
А остальные действия можно интерпретировать как последовательные, если они связаны отношением частичного порядка происходит-раньше.
И это теперь единственное место, где нам понадобится математика.
Частичное отношение возникает потому, что не все операции чтения и записи переменных связаны отношением.
Он обладает свойствами рефлексивности, транзитивности и антисимметрии.
Давайте поговорим еще немного о том, что происходит – до самого себя.
Первое правило заключается в том, что оно связывает все операции в одном потоке.
Если внутри одного потока написано X равно единице, Y равно единице; утверждается, что операции записи в X относятся к отношению происходит-до Y. То есть X происходит-до Y. И это также относится к некоторым специальным действиям, так называемым действиям синхронизации.
Более подробную информацию можно найти в характеристиках.
Например, это запись и чтение из энергозависимой переменной, блокировка/разблокировка на одном мониторе, вход в синхронизированный блок и выход из синхронизированного блока.
Очень важным моментом является то, что все действия синхронизации в вашей программе рассматриваются потоками в точно таком же порядке, как если бы они выполнялись одно за другим.
И бывает-раньше соединяет несколько пар этих действий.
Не имеет значения, в каком потоке происходят действия по синхронизации.
Важно, чтобы они передавали, например, одну изменчивую переменную.
В спецификации сказано, что, скажем, запись в изменчивую переменную происходит до любого другого последующего действия.
Здесь имеется в виду именно в том порядке, в котором у нас происходили действия по синхронизации.
И самое главное во всем этом то, что существует правило согласованности «происходит до», которое отвечает на самый важный вопрос о модели памяти.
Это можно интерпретировать следующим образом.
Если существует цепочка операций чтения/записи переменной и они связаны цепочкой отношений «происходит до», то чтение обязательно должно видеть последнюю запись в этой цепочке.
Если его там нет, извините, вы можете увидеть любое другое значение, любую другую запись или значение по умолчанию.
Теперь можно выдохнуть, с основными определениями мы закончили.
Попробуем проверить теорию на практике? Возьмем пример с перекрестным чтением записей и просто добавим к переменным X и Y модификатор volutity. Попробуем доказать гипотезу о том, что значения ноль-ноль мы больше не увидим.
Для этого мы просто воспользуемся правилами, которые я озвучил выше.
Мы организуем события-раньше в рамках одного потока.
Запись в X происходит перед чтением из Y и во втором потоке.
Запись в Y происходит до чтения из X. И тогда у нас есть четыре действия синхронизации: запись в X, запись в Y, чтение из X, чтение из Y. Они могут появляться в каком-то порядке, а пара может возникнуть в двух случаях.
Например, запись в X в первом потоке произошла раньше, чем чтение из X во втором потоке (происходит раньше).
Как вы можете видеть здесь, Y не связан отношениями.
Результат чтения из Y может просто вернуть нам либо значение по умолчанию, либо значение, которое записал второй поток.
А чтение из X всегда должно его видеть.
Соответственно, наши варианты могут быть ноль-один, один-один.
Второй случай — когда происходит соединение.
Это одно и то же — запись в Y происходит раньше, чем чтение из Y. Между X тоже нет связи.
Соответственно, результат тот же, только там будет один-ноль, ноль-единица.
Теоретически мы можем доказать поведение нашей новой программы.
Вы можете проверить это на практике.
Давайте добавим ключевое слово Volatible в наш тест. Запустите его и убедитесь, что действительно это значение больше никогда не будет воспроизведено.
«Так случилось-раньше» — очень хороший инструмент для доказательства правильности ваших программ.
Есть у него еще одно интересное и полезное свойство.
Допустим, у нас еще есть такой небольшой кусочек кода.
Одна изменчивая переменная X и переменная Z не являются изменчивыми, никакой разницы.
Есть один поток, который записывает только в переменные X и Z; и второй поток, который ждет, пока X примет значение единицы, и только затем печатает Z. Таким же образом мы можем построить связь «происходит до» внутри одного потока и между потоками.
Мы увидим, что запись в Z является транзитивной в первом потоке; его значение всегда будет достигать чтения во втором потоке.
На самом деле это довольно мощный механизм публикации данных между потоками.
Более того, представьте, что эти куски кода находятся в первом потоке — это некий метод объекта put value. Второй фрагмент кода — это некоторый метод получения значения того же объекта.
Доказав связь «происходит до» между этими методами, мы можем написать в документации, что «помещение значения происходит до получения значения».
Это помогает вам строить большие блоки вашей программы как кирпичики, для которых вы затем можете использовать свойство Does-Before так же, как и для Летучих, только с этими методами.
В стандартной библиотеке есть много мест, где это написано, например — put value происходит перед get. 
Итак, давайте сделаем некоторые выводы.
Во-первых, спецификация сложна.
К сожалению, это действительно единственное место, где вы найдете правду.
А сама модель памяти дает вам довольно мощный инструмент для доказательства правильности ваших программ.
Существуют инструменты, которые могут проверять многопоточную корректность, но у них есть большие ограничения.
Скажем так, это на самом деле не роскошь для уродов.
Вы можете либо доказать, что ваша программа работает на бумаге, либо она, вероятно, не работает, и у вас есть ошибка, которая будет воспроизведена как раз к вечеру воскресенья.
Во-вторых, не бойтесь проверить это на практике, используйте jcstress. Сама утилита хороша еще по одной причине: она используется для проверки того, насколько сама JVM соответствует модели памяти.
И есть список тестовых сценариев, которые как раз помогут вам его изучить.
В заключение я посоветую несколько книг, которые стоит прочитать.
Первая — «Искусство многопроцессорного программирования» Мориса Херлихи.
Там заложено множество теоретических основ о том, что происходит-раньше, последовательной согласованности, линеаризуемости и т. д. Вторая книга более практическая — «Java Concurrency на практике» Брайана Гетца.
Это коллекция шаблонов многопоточного проектирования, которые вы можете использовать в повседневной разработке.
В книге говорится о таких вещах, как безопасная публикация, безопасная инициализация и т. д. Я настоятельно рекомендую ее прочитать.
Вы можете посмотреть репортажи и прочитать блог Леша Шипилева , который был инженером по производительности в Oracle, а сейчас работает в Red Hat. Он много пишет о том, как Java-машина выглядит изнутри и как она работает. И он прочитал серию лекций о JMM. Вы можете прочитать блог Романа Елизарова .
Он преподавал, по-моему, многопоточное программирование в ИТМО.
Его блог немного запущен, но его можно прочитать, поискать его лекции и выступления на YouTube. В целом очень хорошо, рекомендую.
Спасибо всем.
Теги: #Виртуализация #Тестирование веб-сервисов #java #Параллельное программирование #многопоточное программирование #параллелизм на Java
-
Хостинг За Доллар
19 Oct, 24 -
3G Модем И Микротик
19 Oct, 24 -
Бизнес-План — Описание Рынка Ноутбуков
19 Oct, 24
