4446
правок
Синхронизация без ожидания: различия между версиями
Перейти к навигации
Перейти к поиску
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 97: | Строка 97: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Поскольку исследования транзакционной памяти выросли из исследований неблокирующих структур данных, поддержка разработки таких структур данных долгое время считалась обязательной для реализаций STM. Однако недавно некоторые исследователи заметили, что по меньшей мере некоторые преимущества транзакционной памяти, связанные с разработкой ПО, могут быть получены и при помощи блокирующих STM. До сих пор продолжаются дискуссии о том, должны ли STM быть неблокирующими и какова цена за достижение этого состояния. | |||
Конструирование блокирующих STM значительно проще, но, хотя во многих случаях они оказываются достаточными, это не всегда верно. Рассмотрим, например, обработчик прерываний, использующий данные совместно с прерванным потоком. Прерванный поток не запустится заново до того момента, как обработчик прерываний закончит работы, поэтому очень важно, чтобы прерванный поток не блокировал обработчика прерываний. Таким образом, если планируется использование STM для упрощения кода доступа к этим совместно используемым данным, то STM должна быть неблокирующей. Это стимулирует авторов к продолжению исследований, направленных на улучшение неблокирующих STM и на понимание фундаментального разрыва, если таковой существует, между блокирующими и неблокирующими STM. | |||
Эффективность неблокирующих STM в общем случае планомерно растет [ ], и нет причины полагать, что неблокирующие STM не могут успешно конкурировать с блокирующими в общем случае, т.е. до тех пор, пока система не решит, что одна транзакция не должна ждать другую, которая была задержана (такая функция недоступна у блокирующих STM). | |||
Исследователи пришли к выводу, что наличие разрыва между блокирующими и неблокирующими STM можно доказать согласно некоторой метрике, однако в общем случае он не повлечет значительной разницы в эффективности. И в самом деле, Аттийя и др. [ ] продемонстрировали разницу между алгоритмами без препятствий и блокирующими алгоритмами согласно метрике, учитывающей количеством различных базовых объектов, к которым обращается реализация, плюс количество «остановок памяти», которые измеряют, сколько раз реализация может столкнуться с конкуренцией за переменную из другого потока. Этот результат интересен сам по себе, однако неясно, окажется ли он полезным для решения вопроса о том, следует ли использовать блокирующие объекты или объекты без препятствий, сама по себе метрика не учитывает время, потраченное на ожидание при блокирующих реализациях, и потому ошибается в их пользу. На данный момент сохраняется оптимистичная надежда на то, что STM можно сделать неблокирующими, не жертвуя значительно эффективностью в общем случае. | |||
Еще один любопытный вопрос, который пока, по-видимому, остается открытым, заключается в том, являются ли затраты на внедрение более сильных условий прогрессf при неблокирующей реализации принципиально более высокими, чем в случае отсутствия препятствий. На данный момент общий консенсус заключается в том, что это скорее так. Известно, что существует фундаментальное различие между отсутствием препятствий и отсутствием блокировок в системах, поддерживающих только операции чтения и записи: в этой модели можно обеспечить консенсус в системах без препятствий, но нельзя – в системах без блокировок [ ]. Это весьма любопытное наблюдение, к сожалению, почти неактуально с практической точки зрения, поскольку все современные мультипроцессоры с разделяемой памятью поддерживают более сильные примитивы синхронизации – такие как CAS – с помощью которых можно легко найти консенсус, и даже без ожидания. Таким образом, интересно было бы узнать, существует ли фундаментальное различие в эффективности реальных систем между случаями без блокировки и без препятствий. | |||
Для того чтобы всерьез повлиять на направление разработок, подобные результаты должны рассматривать эффективность алгоритма в общем случае либо некоторые другие метрики (например, объем памяти), актуальные для повседневного использования. Многие результаты для нижних границ подчеркивают различие между сложностью в наихудшем случае, которое не обязательно должно напрямую влиять на решения о разработке, поскольку наихудшие случаи встречаются весьма редко. До сих пор все попытки определить различие при помощи потенциально полезных метрик лишь приводили к более сильным результатам, чем предполагались возможными. Лучанго, Мойр и Шавит [18] сделали попытку определить разницу в количестве инструкций CAS, необходимых для нахождения консенсуса в отсутствие конкуренции, однако обнаружили, что эта метрика является не особенно полезной, поскольку смогли найти реализацию без ожидания, не использующую инструкции CAS в отсутствие конкуренции. Вторая попытка [ ] заключалась в определении различия согласно метрике сложности в шагах для алгоритма без препятствий, которая считает количество шагов, требующихся для выполнения операции в случае, если операция более не встретит конкуренции. Авторы знали о возможности реализации DCAS без препятствий с константной сложностью в шагах и попытались доказать невозможность этого для DCAS без блокировок, однако в результате получили алгоритм, выполняющий эту задачу. Их опыт доказывает, что помимо непосредственных преимуществ алгоритмов без препятствий они к тому же могут оказаться полезным плацдармом для перехода к алгоритмам с более сильными гарантиями прогресса. | |||
Наконец, хотя множество менеджеров конкуренции оказались эффективными для различных рабочих нагрузок, остается открытым вопрос можно ли адаптировать один менеджер конкуренции так, чтобы он работал наравне с лучшими при всех вариантах рабочей нагрузки, и насколько близко он может подойти к принятия оптимальных решений об управлении конкуренцией. Результаты, полученные на данный момент, позволяют предположить, что достичь этой цели будет очень непросто. Следовательно, для любой системы главным приоритетом должна быть возможность устранения конкуренции как таковой. К счастью, транзакционная память потенциально способна сделать эту задачу намного более простой, чем модели программирования на основе блокировок, поскольку ей присущи преимущества мелкомодульной синхронизации без сложности, присущей программированию схем мелкомодульной блокировки. | |||
== См. также == | |||
* [[Параллельное программирование, взаимное исключение]] | |||
* [[Линеаризуемость]] | |||
== Литература == | |||
1. Agarwal, A., Cherian, M.: Adaptive backoff synchronization techniques. In: Proceedings of the 16th Annual International Symposium on Computer Architecture, pp. 396-406. ACM Press, New York (1989) | |||
2. Aguilera, M.K., Frolund, S., Hadzilacos, V., Horn, S.L., Toueg, S.: Brief announcement: Abortable and query-abortable objects. In: Proc. 20th Annual International Symposium on Distributed Computing, 2006 | |||
3. Attiya, H., Guerraoui, R., Hendler, D., Kouznetsov, P.: Synchronizing without locks is inherently expensive. In: PODC '06: Proceedings of the twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, New York, USA, pp. 300-307. ACM Press (2006) | |||
4. Attiya, H., Guerraoui, R., Kouznetsov, P.: Computing with reads and writes in the absence of step contention. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005 | |||
5. Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., Nussbaum, D.: Hybrid transactional memory. In: Proc. 12th Symposium on Architectural Support for Programming Languages and Operating Systems, 2006 | |||
6. Fich, F., Luchangco, V., Moir, M., Shavit, N.: Brief announce ment: Obstruction-free step complexity: Lock-free DCAS as an example. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005 | |||
7. Fich, F., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005 | |||
8. Fraser, K., Harris, T.: Concurrent programming without locks. http://www.cl.cam.ac.uk/netos/papers/ | |||
2004-cpwl-submission.pdf (2004) | |||
9. Guerraoui, R., Herlihy, M., Pochon, B.: Polymorphic contention management. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005 | |||
10. Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: Proc. 24th Annual ACM Symposium on Principles of Distributed Computing, 2005, pp. 258-264 | |||
11. Guerraoui, R., Kapalka, M., Kouznetsov, P.: The weakest failure detector to boost obstruction freedom. In: Proc. 20th Annual International Symposium on Distributed Computing, 2006 | |||
12. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124-149 (1991) | |||
13. Herlihy, M.: A methodology for implementing highly concurrent data objects. ACM Trans. Program. Lang. Syst. 15(5), 745-770(1993) | |||
14. Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free mechanism for atomic update of multiple non-contiguous locations in shared memory. US Patent Application 20040034673 (2002) | |||
15. Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, 2003 | |||
16. Herlihy, M., Luchangco, V., Moir, M., Scherer III., W.: Software transactional memory for supporting dynamic-sized data structures. In: Proc. 22th Annual ACM Symposium on Principles of Distributed Computing, 2003, pp. 92-101 | |||
17. Herlihy, M., Moss, J.E.B.: Transactional memory: Architectural support for lock-free data structures. In: Proc. 20th Annual International Symposium on Computer Architecture, 1993, pp. 289-300 | |||
18. Luchangco, V., Moir, M., Shavit, N.: On the uncontended complexity of consensus. In: Proc. 17th Annual International Symposium on Distributed Computing, 2005 | |||
19. Marathe, V.J., Moir, M.: Toward high performance nonblocking software transactional memory. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming. pp. 227-236, ACM, New York, USA (2008) | |||
20. Marathe, V., Scherer, W., Scott, M.: Adaptive software transactional memory. In: Proc. 19th Annual International Symposium on Distributed Computing, 2005 | |||
21. Michael, M., Scott, M.: Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. J. Parall.Distrib. Comput. 51(1), 1-26(1998) | |||
22. Scherer, W., Scott, M.: Advanced contention management for dynamic software transactional memory. In: Proc. 24th Annual ACM Symposium on Principles of Distributed Computing, 2005 | |||
23. Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput., Special Issue 10,99-116 (1997) | |||
24. Treiber, R.: Systems programming: Coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center (1986) | |||