Развернутый комментарий про теоретико-параллельный доклад на JPoint 2014
На доклады на конференции JPoint 2014 в Москве было выделено по 45 минут. Что можно рассказать за 45 минут из теоретического курса параллельного программирования, который, по-хорошему, занимает целый семестр? Цель моего доклада заключалась в том, чтобы дать слушателям минимально необходимую теоретическую базу, которая позволит прочитать и понять 17-у главу спецификации языка Java (JLS), которая четко регламентирует допустимое поведение многопоточных программ на Java на любой архитектуре CPU. Это значит, что программисту на Java не обязательно разбираться в подробностях и деталях реализации кэшей, протоколов когерентности, параллелизма на уровне инструкций, специальных инструкций и барьеров, как и других особенностей различных архитектур. Это задача для тех, кто пишет JVM или хочет написать самый быстрый код. Программист на Java может писать корректные многопоточные программы, если он четко понимает, какие исполнения его многопоточного кода допустимы с точки зрения спецификации языка Java.
В качестве основной идеи доклада я выбрал тот неочевидный факт, что, в общем случае, поведение многопоточных программы нельзя изучать путем анализа различных перестановок выполняемых операций. Я отобрал основные определения и объяснил суть последовательной согласованности и линеаризуемости, чтобы подвести к этому факту. Из-за технических накладок с трансляцией организаторы попросили задержать начало доклада, из-за чего на доклад осталось около получаса, и его кульминационная концовка была несколько смазана. В этой записи я еще раз развернуто объясню основную идею и дам ссылки для домашнего чтения тем, кому хочется в этом подробней разобраться.
Слайды с доклада:
JPoint 2014 - Теоретический минимум для понимания Java Memory Model from Roman Elizarov
Итак, факт, на котором редко акцентируют внимание даже очень хорошие учебники по параллельному программированию, заключается в том, что исполнение системы, выполняющей операции над линеаризуемыми (атомарными) объектами, можно анализировать в модели чередования операций между потоками. А если объекты, на основании которых построен алгоритм не линеаризуемы (не атомарны), то делать выводы о возможном поведении программы, рассуждая какая операция из разных потоков выполнилась первой, а какая второй, категорически нельзя. Они, в общем случае, могут выполняться параллельно и могут демонстрировать совершенно не интуитивное поведение.
Я предпочитаю термин линеаризуемость. С точки зрения теории параллельного программирования, он является синонимом термина атомарность, но на практике термин атомарность часто используется нестрого, внося путаницу. Даже 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 часа в формате мастер-класса. Начав с такой же теоретической базы и объяснив, что же такое линеаризуемые объекты, я смогу объяснить слушателям основные способы построение этих самых линеаризуемых объектов, как с помощью взаимного исключения, так и без блокировок.