4551
правка
Синхронизация без ожидания: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
== Основные результаты == | == Основные результаты == | ||
Далее будут вкратце рассмотрены наиболее важные результаты, относящиеся к неблокирующим механизмам синхронизации, и в частности, синхронизация без препятствий. | |||
Несмотря на то, что в практическом плане был достигнут прогресс как в части неблокирующих реализаций совместно используемых объектов, так и в отношении неблокирующих STM-систем, этот прогресс был достаточно медленным из-за сложностей, связанных с одновременным обеспечением корректности и отсутствия блокировок. До введения понятия алгоритмов без препятствий STM-системы без блокировок отличались серьезными недостатками, такими как необходимость в заблаговременном объявлении и инициализации всей памяти, к которой впоследствии могли бы обращаться транзакции, необходимость заблаговременного знания транзакциями, к каким областям памяти они будут обращаться, неприемлемые ограничения на топологию этой памяти и т. п. | |||
Помимо работы над такими инструментами, как STM-системы для построения неблокирующих структур данных, немалые усилия прилагались к работе над их непосредственной реализацией. Эта работа не привела к появлению практичных алгоритмов без ожидания, однако было получено несколько практичных реализаций без блокировки для простых структур данных, таких как очереди и стеки [21, 24]. В литературе было описано несколько более смелых реализаций, которые едва ли можно было назвать практичными, поскольку их алгоритмы были сложными и неочевидными, многие были неверными, и почти все не имели формальных доказательств. Находить доказательства для таких алгоритмов непросто, а после небольших модификаций их корректность приходится доказывать заново. | |||
Далее будут рассмотрены некоторые результаты, полученные в результате применения подхода «без препятствий». | |||
Важный практический довод за использование алгоритмов без препятствий заключается в том, каким образом выполняется управление конкуренцией при ее возникновении. Представляя принцип вычисления без препятствий, Херлихи и др. [15] пояснили, что контроль конкуренции необходим для ускорения прогресса в свете ее наличия, поскольку в этом случае алгоритмы без препятствий не могут прямо гарантировать прогресс. Однако они не пояснили более конкретно, как использовать механизмы контроля конкуренции на практике. | |||
Впоследствии Херлихи др. [ ] представили динамическую STM-систему (см. следующий раздел), которая предоставляет интерфейс для модульного инструмента управления конкуренцией (менеджера конкуренции), позволяющий экспериментировать с альтернативными менеджерами. Шерер и Скотт [ ] экспериментировали с несколькими такими альтернативными менеджерами и обнаружили, что выбор лучшего менеджера конкуренции зависит от рабочей нагрузки. Геррауи и др. [9] описали подход к реализации, поддерживающий изменение менеджеров конкуренции «на лету» в ответ на изменение условий рабочей нагрузки. | |||
Все менеджеры конкуренции, описанные в вышеупомянутых работах, являются ситуативными и работают на базе интуиции; не приводится каких-либо попыток анализа того, какие гарантии обеспечиваются менеджерами конкуренции и есть ли такие гарантии вообще. Геррауи и др. [10] сделали первый шаг по направлению к формальному анализу менеджеров конкуренции, показав, что их жадный менеджер конкуренции гарантирует, что каждая транзакция в конечном итоге завершается. Однако использование жадного менеджера конкуренции приводит к тому, что алгоритм становится блокирующим, так что при доказательстве обязательно приходится предполагать, что потоки не потерпят неудачу при выполнении транзакций. | |||
Фич и др. [7] показали, что любой алгоритм без препятствий может быть преобразован в алгоритм, который в любой реальной системе окажется практичным алгоритмом без ожидания. «Практичность» здесь используется по той причине, что гарантия прогресса в случае алгоритма без ожидания зависит от частичной синхронности, существующей в любой реальной системе, однако преобразованный алгоритм технически не является алгоритмом без ожидания, так как этот термин определен в контексте полностью асинхронной системы. Тем не менее, алгоритм, полученный в результате преобразования Фич и др. К алгоритму без препятствий, гарантирует прогресс для удачных транзакций, даже если другие транзакции не достигли успеха. | |||
Работа по встраиванию техник управления конкуренцией в алгоритмы без препятствий выполнялась главным образом в контексте STM-систем, так что менеджер конкуренции может быть вызван непосредственно из реализации STM. Таким образом, программисту, использующему реализацию STM, не приходится беспокоиться о том, как в систему интегрировано управление конкуренцией; однако это не относится к случаю интеграции механизма управления конкуренцией в непосредственные реализации структур данных без препятствий. | |||
Одним из вариантов является встраивание программистом вызовов менеджера конкуренции вручную, однако этот подход довольно утомителен и приводит к появлению ошибок. Геррауи и др. [ ] предложили версию подхода, в которой менеджер конкуренции рассматривается как детектор ошибок. Авторы также исследовали вопрос о том, какие гарантии прогресса и какими детекторами ошибок могут быть обеспечены. | |||
