Синхронизация без ожидания: различия между версиями

Подход «без препятствий» к созданию неблокирующих механизмов синхронизации предложили Херлихи и др. [ ], использовавшие его для разработки двухсторонней очереди на базе широко распространенной команды CAS (сравнение с обменом). Всем предыдущим неблокирующим двухсторонним очередям либо требовались экзотические команды синхронизации, такие как двойное сравнение с обменом (DCAS), либо приходилось мириться с тем, что операции с противоположных концов очереди всегда конфликтовали друг с другом.

Херлихи и др. [ ] предложили Dynamic STM (DSTM) – первый STM-алгоритм, являющийся динамическим в следующих смыслах: (1) новые объекты могут распределяться «на лету», и к ним могут впоследствии обращаться транзакции; (2) транзакциям нет необходимости заранее знать, к каким объектам они будут обращаться. Эти два свойства делают алгоритм DSTM намного более полезным, чем предыдущие версии STM для программирования динамических структур данных. В результате стали возможными неблокирующие реализации таких сложных структур совместно используемых данных, как сбалансированные деревья поиска, списки с пропусками, динамические хеш-таблицы и т. п.

Подход «без препятствий» сыграл ключевую роль в разработке обоих вышеупомянутых результатов: Херлихи и др. [ ] могли сконцентрироваться на функциональности и корректности DSTM, не заботясь о том, как обеспечить более сильные гарантии прогресса – такие как отсутствие блокировок.

Появление DSTM и подхода «без препятствий» привели к разработке множества улучшений и вариаций различными исследовательскими группами, большая часть которых также предпочитала подход «без препятствий». С другой стороны, Харрис и Фрейзер [ ] предложили динамическую версию STM под названием OSTM, обладавшую преимуществами DSTM, но при этом являвшуюся неблокирующей. Эксперименты, проведенные в Рочестерском университете [20], показали, что на некоторых рабочих нагрузках DSTM превосходит эффективностью OSTM на порядок величины, однако на других нагрузках OSTM вдвое превосходит DSTM. Эти различия, вероятно, связаны с разными проектными решениями, которые в большинстве случаев являются ортогональными к условию прогресса, поэтому не вполне понятно, какое заключение можно сделать в данном случае по поводу влияния выбранного условия прогресса на эффективность работы алгоритма.

Возможно, более непосредственное сравнение можно выполнить для другой пары алгоритмов, один из которых также является алгоритмом без препятствий от Херлихи и др. [ ], а второй – аналогичным алгоритмом, но без блокировок, который представили Харрис и Фрейзер [ ]. Эти алгоритмы, разработанные независимо друг от друга, реализуют инструкцию MCAS (CAS, обобщенную на случай обращения к M независимо выбранным областям памяти). Эти два алгоритма очень похожи; проведенное независимое сравнение обнаружило, что разница между ними связана лишь с желанием Харриса и Фрейзера разработать реализацию без блокировок. В результате их алгоритм стал несколько более сложным, к тому же ему требуется не менее 3M + 1 операций CAS, тогда как алгоритм Херлихи и др. [ ] требует только 2M + 1 операций. Непосредственного сравнения эффективности этих двух алгоритмов не производилось, однако можно предполагать, что алгоритм без препятствий будет эффективнее алгоритма без блокировок – особенно в отсутствие конфликтующих операций MCAS.