9. Детерминированное параллельное программирование
Предыдущая серия:
Недетерминизм -- это большая проблема параллельного программирования. Выполнение программы будет недетерминированным, если в некоторой точке программы возникает неоднозначность, вариант, развилка -- что делать дальше (не путать с обычным условным ветвлением, которое выполняется детерминированно, так как логическое условие в момент его исполнения уже вычислено). Недетерминизм естественно присущ параллельности: когда две параллельные активности независимы, программная спецификация не может точно сказать, какая из них завершится первой. Если несколько нитей ожидают запуска, системе надо решать, какую нить стартовать следующей. Такой выбор реализуется разными механизмами -- например, с помощью планировщика, входящего в состав многих ОС, но, очевидно, за пределами самого языка программирования.
С недетерминизмом трудно справиться, если он для программиста наблюдаемый (явный) -- разработчику предлагается справляться с сопутствующими проблемами самостоятельно. В результате нередко возникает ситуация конкуренции (race condition), когда например две нити пытаются записать значение в одну и ту же общую переменную. Понимание и отладка таких программ обычно сильно затруднены.
Обход недетерминизма в языках с поддержкой параллельного программирования
Простой способ устранения race condition -- спроектировать язык так, что в нём просто не будет возникать ситуация недетерминизма. Но тогда вместе с водой выплеснется и ребёнок, так как полноценный параллелизм, очевидно, подразумевает недетерминизм. Но можно ли избежать хотя бы основных негативных эффектов недетерминизма, и сохранить параллелизм? Мы можем решить эту проблему, сформулировав чёткое различие между недетерминизмом внутри системы (которого нельзя избежать), и явным недетерминизмом, которого можно избежать.
Во-первых, ограничим наблюдаемый недетерминизм только теми частями программы, которые реально в нём нуждаются. В других частях программы наблюдаемого недетерминизма не будет.
Во-вторых, спроектируем язык, в котором будет возможно писать параллельные программы без наблюдаемого недетерминизма. Но возможно ли это? В языках наподобие Java и C# используется параллелизм с разделяемым состоянием, в Erlang -- параллелизм с обменом сообщениями, и для этих парадигм характерен явный недетерминизм. К счастью, этот "современный" пример ни о чём не говорит. Существуют как минимум четыре полезные парадигмы программирования, допускающие параллелизм без наблюдаемого недетерминизма (без race condition). Рассмотрим их более подробно.
1. Декларативный параллелизм (монотонное dataflow программирование). В этой парадигме на вход поступают детерминированные данные, и на их основе детерминировано вычисляются выходные данные, то есть мы существуем полностью в детерминированном мире. Если появляется множество входных потоков данных, все они должны быть детерминированными. Программа точно знает, как и какие входные значения она может взять, чтобы вычислить каждый результат (например, из каждого входного потока надо считать ровно один элемент). Эта парадигма легко делается ленивой: пока все входные данные не накопились, можно ничего не делать, или наоборот, вычислять что-то промежуточное на основании тех данных, что уже поступили.
2. Существует также парадигма немонотонного dataflow программирования, когда любое изменение входных данных вызывает немедленное их распространение по всей программе. Такие изменения представляются как токены потоков данных, путешествующие по системе. За счёт токенов по сути удаётся обойти недетерминизм входных данных, однако у этого подхода есть такой недостаток, что он иногда добавляет свой собственный недетерминизм, который не существует на входе (он называется глюк, glitch).
Например, имеется функция, вычисляющая x + x * y. Она была вызвана с аргументами x=3 и y=4 и вычислила результат 15. Если аргумент x изменится на 5, то результат функции перевычислится на 25. Однако наивная реализация с параллельным потоком будет некорректна. Возможен глюк, когда параметр x получит новое значение, которое запишется в слагаемое x в формуле в то время, когда ещё параллельно вычисляется умножение x*y с предыдущим значением x. В итоге будет получено не 25, а 17. Обходится это техническими ограничениями на схему управления нитями, однопоточной компиляцией некоторых функций, и т. п.
3. Функциональное реактивное программирование (непрерывное синхронное программирование) -- аналогично немонотонному dataflow, но без глюков. В этой парадигме программы функциональные, но аргументы функций могут изменяться, и такие изменения сразу распространяются до самых выходов. То есть допускается недетерминизм на входе, и никакого дополнительного недетерминизма самой программой не добавляется (при условии, что изменения распространяются корректно). На практике значения перевычисляются лениво -- только когда они реально становятся востребованными.
4. Дискретное синхронное программирование. В этой парадигме программа ожидает входные события, выполняет внутренние вычисления, и выдаёт выходные сообщения. Такая система называется реактивной. Реактивные системы должны быть детерминированными: одна и та же комбинация входов выдаст один и тот же выходной результат. Как и функциональное реактивное программирование, эта парадигма допускает недетерминированные входы и не добавляет недетерминизма.
Главное отличие, что время в этой парадигме дискретно: оно "измеряется" в шагах от одного входного события к следующему. Выходные сообщения выдаются "мгновенно" в то же логическое время, как поступили входные события. Все вычисления, выполненные для определения следующего выходного события, считаются частью одного и того же временного отрезка.
Концепция дискретного времени очень сильно упрощает программирование реактивных систем. Например, функции могут совсем просто компоноваться: выходные события одного вычислительного блока мгновенно становятся доступными в качестве входных событий других блоков.
= = =
Детерминированное параллельное программирование -- параллельная модель, которая за счёт предсказуемости всех процессов взаимодействия отличается высокой выразительностью, существенно упрощающей процесс программирования. Разрабатывать системы в этой парадигме намного проще, нежели в классических подходах "многопоточность с разделяемым состоянием" и "параллелизм через обмен сообщениями". Существенно легче становится разрабатывать и полноценные параллельные (parallel) программы, работающие на множестве ядер или процессоров. Но и цена за это будет такая, что работа кода должна быть полностью детерминирована.
Другими словами, уже простейшая массовая схема "один сервер + несколько (более одного) клиентов" будет недетерминирована, так как сервер не знает, от которого из клиентов поступит следующий запрос. В принципе, такой детерминизм на практике часто и не нужен, но сегодня все ведущие специалисты по параллельному программированию согласны с тем, что в параллельных системах надо прежде всего стремиться к увеличению степени детерминизма.
продолжение следует
Далее мы познакомимся с простейшей формой детерминированного параллелизма, и рассмотрим, как правильно её реализовывать на практике.
