4551
правка
Синхронизация без ожидания: различия между версиями
Перейти к навигации
Перейти к поиску
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 82: | Строка 82: | ||
== Применение == | == Применение == | ||
Подход «без препятствий» к созданию неблокирующих механизмов синхронизации предложили Херлихи и др. [ ], использовавшие его для разработки двухсторонней очереди на базе широко распространенной команды 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. | |||
== Открытые вопросы == | |||