?

Log in

No account? Create an account

elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Развернутый комментарий про теоретико-параллельный доклад на JPoint 2014
elizarov

На доклады на конференции JPoint 2014 в Москве было выделено по 45 минут. Что можно рассказать за 45 минут из теоретического курса параллельного программирования, который, по-хорошему, занимает целый семестр? Цель моего доклада заключалась в том, чтобы дать слушателям минимально необходимую теоретическую базу, которая позволит прочитать и понять 17-у главу спецификации языка Java (JLS), которая четко регламентирует допустимое поведение многопоточных программ на Java на любой архитектуре CPU. Это значит, что программисту на Java не обязательно разбираться в подробностях и деталях реализации кэшей, протоколов когерентности, параллелизма на уровне инструкций, специальных инструкций и барьеров, как и других особенностей различных архитектур. Это задача для тех, кто пишет JVM или хочет написать самый быстрый код. Программист на Java может писать корректные многопоточные программы, если он четко понимает, какие исполнения его многопоточного кода допустимы с точки зрения спецификации языка Java.

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

Слайды с доклада:

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

Я предпочитаю термин линеаризуемость. С точки зрения теории параллельного программирования, он является синонимом термина атомарность, но на практике термин атомарность часто используется нестрого, внося путаницу. Даже 17-ая глава JLS (JMM) допускает вольность в этом вопросе. Раздел 17.7 назван "Non-atomic Treatment of double and long" и содержит утверждение что "Writes to and reads of references are always atomic" в том смысле, что даже если ссылка занимает 64 бита, её чтение и запись не может происходить двумя операциями над её 32-битными частями. Там не имеется в виду линеаризуемость операций над ссылками.

Термин линеаризуемость вообще не используется в JMM, однако легко видеть, что JMM обещает линейную-упорядоченность всем операциям синхронизации (17.4.4), которыми являются, в том числе, операции чтения и записи volatile переменных (17.4.2). Из этого напрямую следует, что операции над volatile переменными в Java линеаризуемы просто по определению этого термина. В теории, такие переменные называют атомарными регистрами. В тоже время, возможным исполнениям над обычными разделяемыми переменными (не помеченными как volatile) JMM дает большую свободу. Время доклада было слишком ограничено, чтобы рассказать, что обычные разделяемые переменные в Java соответствуют тому, что в теории называют регулярными регистрами, за исключением long и double, про которые можно разве что сказать, что они являются безопасными регистрами.

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

V. Garg. Concurrent and Distributed Computing in Java. 2004. Этот учебник содержит основные элементы как параллельного так и распределенного программированию. Он не большой, поэтому собственно многопоточному (параллельному) программированию там посвящено не очень много. Однако он и не сложен в понимании и дает материал в понятной и логичной последовательности. Дело в том, что параллельное и распределенное программирование использует практически одинаковый формализм и несмотря на то, что в первом случае процессы общаются через разделяемы объекты, а во втором случае, через передачу сообщений, некоторые результаты и алгоритмы имеют прямые параллели для того и другого случая. Многие практически интересные вещи, такие как, например, Data Race Detector (DRD), разрабатываемый в нашей компании, можно осознать и создать только понимая концепции и алгоритмы из обеих областей одновременно.

M. Herlihy. The Art of Multiprocessor Programming. 2012. Это фундаментальный труд, название которого не случайно перекликается с классическим трудом Дональда Кнута. Там действительно освещены все фундаментальные теоретические достижения именно многопоточного программированиям. Автор не отвлекается на теорию распределенного программирования, а дает очень хороший обзор современных алгоритмов работающих с общей памятью.

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

L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. 1978. Несмотря на то, что в этой работе речь идет о распределенной системе, именно в ней впервые введено понятие произошло до.

L. Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. 1979. В этой работе впервые вводится понятие поледовательной согласованности именно для того, чтобы специфицировать среду исполнения многопоточных программ. Удивительно, но по прошествии более чем 30 лет, оно до сих пор именно так и используется.

L. Lamport. The Mutual Exclusion Problem. Part I: A Theory of Interprocess Communication. 1980. В этой работе рассматривается проблема взаимного исключения, которую я не затрагивал в своем докладе, однако именно в этой работе есть апелляция к СТО, как обоснование необходимости действительно параллельного формализма параллельных вычислений, в котором бывают фундаментально параллельные (не упорядоченные отношением произошло до) операции.

L. Lamport. On Interprocess Communication. 1985. В ней заложены основы теории параллельного программирования. Именно в этой работе вводится понятие атомарного регистра, как и других, более слабых регулярного и безопасного. Показано как более сильные регистры можно построить из более слабых.

M. Herlihy, J. Wing. Linearizability: A Correctness Condition for Concurrent Objects. 1990. В этой работе дается определение линеаризуемости, которое фактически обобщает понятие атомарности на произвольный класс общих объектов.

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


  • 1

Re: 99% это много, но вообще ни разу не 100%

Я циничен до неприличия... поэтому сомневаюсь что оракл сможет вбухать столько ресурсов в не х86 архитектуры сколько он вбухал в x86... тупо не будет спроса. сама платформа развивается и так очень и очень небыстро :( так что можно забыть про армы в плане concurrent программирования на яве (исключение для "матросовых")

скажу им отдельное большое спасибо если они запилят huma как обещали. скажу ОЧЕНЬ большое спасибо если сделают (блин сколько можно этого ждать!) stack allocated structs (value types) с контролируемым layout. + еще спасибо за убийство jni и прикручивание чего-то намного менее винтажного... вот вроде немного пожелал а понимаю что если сбудется лет за 10 это будет мега круто :((... если не дай бог запилят type inference (val/var вместо "запли тут свой любимый тип с кучей треугольных скобочек")... но это вообще лет на 15 или "вышку" тянет :))

и кстати я не призываю "забить" на jmm а призываю подходить со здоровым прагматизмом - это не святая скрижаль :) и иногда приходится выходить за рамки...

Re: 99% это много, но вообще ни разу не 100%

Насчет ARM я не специалист. Комментировать не буду. Да и не нужен ARM чтобы удивляться и ценить JMM. Оптимизации в HotSpot имеют все шансы научить ценить JMM и на x86 (тут должен раздаваться злобный смех). Я, например, был глубоко шокирован, что прогресс уже дошел до того, что на x86 можно реально огрести, если инициализировать singleton через DCL без volatile, как это наглядно продемонстрировал Алексей: http://habrahabr.ru/post/143390/

Собственно безопасная публикация, про которую Алексей написал, это самая типичная идиома, про которую программист "понимающий" x86 "уверен", что ему на x86 всё простят :))) Я уже не говорю о том, что x86 активно обрастает разными специальными слабо-упорядоченными инструкциями в SSE, а разные компиляторы и рантаймы потихоньку учатся ими пользоваться налево и направо. Это очень весело. И никакой ARM не нужен.

Насчет jni и всего остального, вроде как есть движение в нужную сторону идет:
http://openjdk.java.net/jeps/169
http://openjdk.java.net/jeps/191

Отсутвие val/var меня, если честно, теперь (since Java 8, когда есть нормальный inference) уже не напрягает.


Edited at 2014-04-25 11:35 am (UTC)

Re: 99% это много, но вообще ни разу не 100%

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

sse/avx можно сказать что в jvm не используется. к примеру хотспот в лицо знает 5 (или около того) методов из рантайма которые он компилит с использованием avх и все!!! из-за этого на простом коде ява может слить c++ в разы. поэтому хочется чтоб запилили huma и не было бы как с aparapi :(

value types тоже к сожалению пытаются нагрузить immutable семантикой непонятно на кой. изменяемость вещь полезная, а идиоты и так найдут 39 способов выстрелить себе в ногу. кроме того не увидел ни слова про встраиваемые массивы (fixed array csharp) а без этого - печалька.

про замену jni читал, но и там не все гладко... нигде нет упоминания про ускорение callbacks в java код, а это мешает :(

Re: 99% это много, но вообще ни разу не 100%

Да ну ладно, нет спроса на Java/ARM: начиная от гиков, которые на ARMv6 (Raspberry Pi) водружают целые аппсервера, кончая вполне серьёзными чуваками, которые содержат зоопарк промышленных миниатюрных девайсов с датчегами, под которые писать переносимый код упаришься (тот самый Internet of Things растёт отсюда).

Я ведь тоже про прагматизм в JMM, и выше, вроде, пояснял, что даже те, кто выходит за рамки JMM, хорошо её изучают, дабы знать, где же они вышли в "серую зону" и нужно начинать быть сверхосторожными. Так что в каком-то смысле для них JMM всё ещё святая скрижаль, которая под сенью своей гарантирует функциональное блаженство :)

  • 1