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

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

я конечно не люблю как г-н Шипилев художественно опускать людей прочитавших jmm и считающих что они познали истину в конечной инстанции но все же замечу:

jmm это больше декларация о намериниях которая ОТСТАЕТ от фактичечкой реализации. Другими словами утверждение о том что программа не соответствующая JMM работает неправильно НЕВЕРНО

в силу ряда обстоятельств субъективного характера из корректности программы по JMM НЕ СЛЕДУЕТ корректность работы программы.

получили грабли в обе стороы. т.е. не можем установить ни отношения следствия ни равносильности.

что будем делать с операциями которые не нашли отражения в JMM (поскольку появились ПОСЛЕ нее?) Atomic*.lazySet() не использовать? (а как же hb/ha ??)

в общем не плоди фанатиков :) а то фраза "я знаю jmm ща я вам объясню как оно должно быть" воспринимается мной как "я прочитал евангелие от луки!" хочется ответить "их еще 12 - иди читай дальше"


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

И ещё про это забывать нельзя: "Любая формальная система неполна".

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

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

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

Вроде я нигде и не утверждал что "программа не соответствующая JMM работает неправильно". Если у кого-то по результатам моего доклада возникло такое ощущение, то заранее извиняюсь. Однако, это никак не связано с "ОТСТАВАНИЕМ" от фактический реализацию. Скажу больше, для любой конкрентной реализации (JVM + платформа) всегда можно написать программу для которой нет гарантии корректной работы по спецификации, но которая корретно работает на данной реализации. Так будет всегда по определению. Сила и суть JMM в том, что она дает некий минимальный набор гаранткий, которая позволяет писать такие программы, которые корректно работают на любой реализации.

"в силу ряда обстоятельств субъективного характера из корректности программы по JMM НЕ СЛЕДУЕТ корректность работы программы." Приведу, пожалуйста, примеры. Хотелось бы увидеть программу, которая корректна по JMM, но не корректно работает.

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

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


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

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

Подписываюсь под Роминым комментом вон там:
http://elizarov.livejournal.com/33610.html?view=394314#t394314

Я вообще думаю, что широкий переход на не-x86 архитектуры (типа ARM) всем покажет, насколько больно закрывать глаза на JMM и надеяться, что всё будет работать, потому что всегда работало на всепрощающем x86. А учитывая, что экосистема ARM вообще куда богаче чем x86, уследить за всеми железячными загонами будет под силу только группе хорошо подготовленных людей, которые пишут под них языковые рантаймы и компиляторы.

С другой стороны, я знаю когорту людей, которая хорошо знает JMM (и оттуда знает минимальный набор гарантий, которые всегда будут), и приемлемо хорошо знают целевой хардвар, чтобы выходить за рамки JMM ради перформанса. Однако даже эти рисковые ребята изучают JMM для того, чтобы представлять границу между безопасным хаком и небезопасным хаком, и поэтому могут свои рискованные телодвижения контролировать. Всякие Atomic*.lazySet, Unsafe.*fence и прочие приблуды попадают в эту категорию.

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

Edited at 2014-04-24 05:00 pm (UTC)

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 всё ещё святая скрижаль, которая под сенью своей гарантирует функциональное блаженство :)

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

ВАша риторика догоняет и перегоняет Путинскую, поэтому доверия нет ни вам, ни вашим собеседникам.

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

ЛОЛШТО. Вы сейчас с кем разговаривали?

5 0 CWɨ GVA-@+l)/l$enPQ?ϗct^)X8Q^UbKjyd

Вот это и есть смешно. Раз память разделяемая,это общие жёны в комунне. Тут уж не до золотого века. Для параллельных алгоритмов характерно многократное чтение, не так ли? Или будем память наращивать, тогда замедление пропорционально ln(n).

Edited at 2014-05-09 06:59 pm (UTC)

Re: золотой век многопоточного программирования в разд

Я вас не понимаю. Обобществление жён какое-то. При чём тут многократное чтение? Откуда взялось про наращивание памяти? И отдельно, откуда взялось про ln(n)? Потрудитесь изложить свою мысль полнее.

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

не могу найти тебя в программе БитБайта.

Жми сверху в программе на "мастер классы"

  • 1
?

Log in

No account? Create an account