Мультитрединг - как победить дракона

[yigal_s]

1. Semaphores
2. Monitors (conditional variables).
3. Messages, рандеву, remote calls, actors (пока не разобрался, одно ли это и то же концептуально, или есть разница. Вообще, в принципе, больше "слышал звон", чем "в теме". Потихоньку разберусь)
4. transactional memory - несколько дней назад где-то ссылку на это дело подобрал.

Интересно, есть еще что-то неупомянутое?

-----
Upd: собственно, в списке представлена некоторая линия эволюции (хотя линейной эволюции в реальности, видимо, не было в точности) способов "синхронизации", вернее, написания мультитредного кода.

Comments

то ли еще будет...

[yms.livejournal.com]

deadlock
для гуи в .NET - Invoke()
для COM - apartments
ну и всякие стандартные приемчики типа как организовать синглтон в условиях мультитрединга

Re: то ли еще будет...

[yigal_s]

нет, это всё не концеепции решения мультитрединоговых задач, а очень частные вещи.

[cmm.livejournal.com]

> Интересно, есть еще что-то неупомянутое?

единственный по-настоящему надёжный вариант — не приставать к дракону вообще.

на крайняк использовать shared memory между процессами, для чётко определённых вещей.

короче: отказаться от модели, в которой shared memory является выбором по умолчанию.

[yigal_s]

> на крайняк использовать shared memory между процессами, для чётко определённых вещей

Типа передачи сообщений :-) (см. пункт 3)

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

[cmm.livejournal.com]

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

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

[yigal_s]

дык кто мешает построить те или иные формальные модели в памяти, удобные для параллельного доступа? Речь же не о том, как нам атомарно увеличить ячейку, на которую указывает другая изменяемая ячейка. Речь о том, как правильно (и быстро тоже) решать нужные нам задачи, алгоритмы писать (конечно, если GUI или embedded soft можно назвать "алгоритмом".

[cmm.livejournal.com]

я утверждаю примерно следующее, на самом деле: все возможные модели безопасного и постижимого для человеческого ума параллельного доступа к памяти так или иначе сводятся к двум вещам:

* объявлению параллельного доступа к константным данным простой оптимизацией (то есть с точки зрения семантики клиентского кода, абсолютно параллельно где эти данные сидят: все в одном месте или в виде кучи копий).

* созданию у изменяющего данные кода иллюзии параллельного доступа и чёткой синхронизации (то бишь убиранию параллельности) этого дела "под капотом".

[yigal_s]

> иллюзии параллельного доступа и чёткой синхронизации

Да ради бога. Беда, что вот как убирать произвольные вещи под капот, чтобы они оттуда на очередном повороте не вывалились - не понятно. Не понятно вот это самое - как писать четкую синхронизацию.

[yigal_s]

то есть, по сути, я увидел тут только замкнутый круг - мол, написать постижимый и безопасный код можно только запрятав вещи под капот. Вот только вопрос - как безопасно и постижимо запрятать. Ну и, наверно, чтоб performance серьезно не деградировала - всегда ведь хочется выжать максимум из дуалкорного гипертрединга на жалкие 3GHz.

[cmm.livejournal.com]

ну собственно transactional memory с аппаратной поддержкой — это именно вот оно.
гениальная фишка, на самом деле.

[yigal_s]

Хочется надеяться, что это оно самое.

Хотя жаль, что в этом случае устареют искуссные и оригинальные способы бега по граблям.

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

Вы, кстати, не знакомы вот с этой работой? http://portal.acm.org/citation.cfm?id=808062

[cmm.livejournal.com]

> проблемы написания блокирующего (а не транзакционного) мультитрединга было бы правильно загнать в какую-то математическую теорию.

загнать-то можно (типа CPU + память = такая большая машина состояний, далее везде), толку только с таких теорий.  практикующие теоретики (хихи) предпочитают атаковать проблему формализации со стороны упрощения моделей, а не совершенствования теорий — видимо, у них есть на это хорошие причины. :)

> Вы, кстати, не знакомы вот с этой работой?

ой, нет.  я на самом деле в математике очень слаб...

[yigal_s]

увы, я тоже дальше абстракта пока заглядывать смысла не увидел. Но "тема доклада" интригует.

А как Вам следующее утверждение? Вроде бы, авторы утверждают, что святой грааль мультитрединга уже обнаружен:

Another great thing about [...] channels is that it has a formal
mathematical foundation, namely CSP, CCS, LOTOS and others. These theories provide design rules or guidelines for writing reliable concurrent software. Semaphores and monitors have no formal foundation, they simply work. From CSP there are several programming languages derived

см. далее http://groups.google.com/group/comp.realtime/msg/be9177cdd85c52a6

[yigal_s]

> единственный по-настоящему надёжный вариант — не приставать к дракону вообще

И, кстати, это вообще не доказано :-)

Прогресс-то понимания проблем мультитрединга и изобретения новых парадигм пока налицо. Как знать, может быть когда-нибудь мультитрединг будет просто таким разделом дискретной математики.

[cmm.livejournal.com]

существование чёткой каузальной зависимости между привычкой наступать на грабли и черепно-мозговым травматизмом тоже не доказано.  в силу хотя бы неоднозначного направления каузации.

и тем не менее. :)

[yigal_s]

И тем не менее прогресс налицо (иначе бы мы тут в ЖЖ не писали одновременно).

[cmm.livejournal.com]

в том-то и дело: для реляционных баз данных проблема решена: давно, строго и формально (если я ничего не путаю, да).

[yigal_s]

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

[cmm.livejournal.com]

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

[yigal_s]

да, пожалуй, разница всё ж есть принципиальная между программированием на ассемблере и программированием "синхронизаций".

[cmm.livejournal.com]

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

[yigal_s]

А еще прогресс вот в этих четырёх циферках сверху (хотя насколько успешен в реальности номер 4 я пока не выяснял).

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

Факт, что с помощью трёх циферок сверху можно писать и читать всё более и более сложные вещи, а не просто топтаться на месте.

[dumalkin.livejournal.com]

Transactional memory не решает проблемы паралельной работы.
Это хорошая штука, но сама по себе к параллельности отношения не имеет, и зачастую полезна в однопотоковом приложении.
Хотите многопоковость без дедлоков ?:) Это есть у нас - наш апп. сервер как раз это и дает.
В кратце идея - автоматическое превращение вызовов в асинхронные, и автоматическое перенаправление чтений данных с неизменяемых автоматически создаваемых копий. В С++ (первая версия) это было дубль- буферизация, сейчас в .Нет - мусорщик собирает неиспользуемые копии :)
Кстати, транзакции на уровне обьектов (не строчек в ДБ) у нас тоже есть :)