Транзакционная память

2008 г.

Транзакционная память

Джеймс Лярус, Кристос Козиракис
Пересказ: Сергей Кузнецов

Открытые проблемы

Кроме обсуждавшихся выше реализационных проблем, в области TM имеется ряд проблем, являющихся предметом активных исследований. Одной из серьезных трудностей оптимистической TM является то, что в результате конфликта может откатиться транзакция, выполняющая операцию ввода-вывода. Под вводом-выводом в данном случае понимается любое взаимодействие с миром, расположенным вне системы TM. Если транзакция аварийно завершается, ее операции ввода-вывода также требуется откатить, что в общем случае сделать очень трудно, если не невозможно. Некоторые откаты позволяет производить буферизация данных, прочитанных или записанных транзакцией, но буферизация не удается даже в простых ситуациях, например, когда транзакция выдает приглашение и ожидает ввода данных от пользователя. Более общий подход состоит в назначении одной из транзакций привилегированного статуса, которой всегда гарантируется возможность завершения в ущерб всем конфликтующим с ней транзакцией. Ввод-вывод может производиться только привилегированной транзакцией (но эта привилегия может передаваться между транзакциями), что, к сожалению, ограничивает объем ввода-вывода, который может произвести программа.

Другой важной проблемой является сильная и слабая атомарность. В системах STM, вообще говоря, реализуется слабая атомарность, когда не транзакционный код не изолируется от кода транзакций. С другой стороны, в системах HTM реализуется сильная атомарность, обеспечивающая более детерминированную программную модель, в которой не транзакционный код не влияет на атомарность транзакции. Из-за этого различия возникает несколько проблем. Кроме потребности в ответе на основной вопрос (какая модель является лучшим базисом для написания программного обеспечения?), это семантическое различие затрудняет разработку программного обеспечения, которое может выполняться в системах обоих типов. Наименьшим общим знаменателем является слабая модель, но ошибочные программы будут производить на разных системах отличающиеся результаты. Альтернативная точка зрения состоит в том, что доступ к общим данным в двух потоках управления без синхронизации вообще является ошибкой, и если только в одном потоке выполняется транзакция, то это не является достаточной синхронизацией между потоками. Следовательно, языки программирования, инструментальные средства, системы поддержки времени выполнения или аппаратура должны предотвращать или выявлять совместную работу с данными без синхронизации транзакционного и не транзакционного кода, и программисты должны исправлять этот дефект.

Системы со слабой атомарностью также сталкиваются с трудностями, когда некоторый объект совместно используется транзакционным и не транзакционным кодом [30]. Когда некоторый поток управления делает некоторый объект видимым для других потоков (например, путем добавления его к некоторой глобальной очереди), происходит публикация этого объекта. Когда некоторый поток управления удаляет некоторый объект из разделяемого глобального пространства, происходит приватизация этого объекта. Частные (приватные) данные можно обрабатывать за пределами транзакции без синхронизации, но изменение состояния объекта с публичного на частный и наоборот должно координироваться системой TM, чтобы она не пыталась откатить состояние объекта, в то время как другой поток управления предполагает, что имеет к этому объекту исключительный, частный доступ.

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

Заключение

Вряд ли транзакционная память сама по себе сделает многоядерные компьютеры полностью пригодными для программирования. Для этого также требуются многочисленные усовершенствования языков программирования, инструментальных средств, систем поддержки времени выполнения и компьютерных архитектур. Однако TM обеспечивает проверенную временем модель для взаимной изоляции одновременно проводимых вычислений. Эта модель повышает уровень абстракции для понимания параллельных задач и помогает избежать многочисленных коварных ошибок параллельного программирования. Однако многие аспекты семантики и реализации TM все еще остаются предметом активных исследований. Если эти трудности удастся своевременно преодолеть, то TM, вероятно, станет основным принципом параллельного программирования.

Литература

Adl-Tabatabai, A.R., Lewis, B.T., Menon, V., Murphy, R., Saha, B., and Shpeisman, T. Abstract compiler and runtime support for efficient software transactional memory. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY 26–37.
Blundell, C., Lewis, E.C., and Martin, M.M.K. Subtleties of transactional memory atomicity semantics. IEEE Computer Architecture Letters 5 (Nov. 2006).
Bobba, J., Moore, K.E., Volos, H., Yen, L., Hill, M.D., Swift, M.M., and Wood, D.A. Performance pathologies in hardware transactional memory. In Proceedings of the 34th International Symposium on Computer Architecture (San Diego, CA, 2007). ACM, NY, 81–91.
Carlstrom, B. D., McDonald, A., Carbin, M., Kozyrakis, C., and Olukotun, K. Transactional collection classes. In Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (San Jose, CA, 2007). ACM, NY, 56–67.
Carlstrom, B.D., McDonald, A., Chafi, H., Chung, J., Minh, C.C., Kozyrakis, C., and Olukotun, K. The Atomos transactional programming language. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY, 1–13.
Ceze, L., Tuck, J., Torrellas, J., and Cascaval, C. Bulk disambiguation of speculative threads in multiprocessors. In Proceedings of the 33rd International Symposium on Computer Architecture (Boston, MA, 2006). ACM, NY, 227–238.
Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., and Nussbaum, D. Hybrid transactional memory. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (San Jose, CA, 2006). ACM, NY, 336–346.
Gray, J. and Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers, San Francisco, CA, 1992.
Grossman, D. The transactional memory / garbage collection analogy. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Montreal, Canada, 2007). ACM, NY, 695–706.
Guerraoui, R., Herlihy, M., and Pochon, B. Polymorphic contention management. In Proceedings of the 19th International Symposium on Distributed Computing (Krakow, Poland, 2005). Springer Verlag, 303–323.
Harris, T., Marlow, S., Peyton-Jones, S., and Herlihy, M. Composable memory transactions. In Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Chicago, IL, 2005), ACM, NY, 48–60.
Harris, T., Plesko, M., Shinnar, A., and Tarditi, D. Optimizing memory transactions. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY, 14–25.
Herlihy, M. and Moss, J.E.B. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th International Symposium on Computer Architecture. ACM, 1993, 289–300.
Herlihy, M., Luchangco, V., Moir, M., and Scherer III, W.N. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (Boston, MA, 2003), 92–101
Isard, M., and Birrell, A. Automatic mutual exclusion. In Proceeding of the Usenix 11th Workshop on Hot Topics in Operating Systems (San Diego, CA, 2007).
Knight, T.F. An architecture for mostly functional languages. In Proceedings of the 1986 ACM Lisp and Functional Programming Conference. ACM, NY.
Kumar, S., Chu, M., Hughes, C.J., Kundu, P., and Nguyen, A. Hybrid transactional memory. In Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, NY, 2006, 209–220.
Larus, J.R. and Rajwar, R. Transactional Memory. Morgan & Claypool, 2006.
Lomet, D.B. Process structuring, synchronization, and recovery using atomic actions. In Proceedings of the ACM Conference on Language Design for Reliable Software (Raleigh, NC, 1977). ACM, NY, 128–137.
McDonald, A., Chung, J., Brian, D.C., Minh, C.C., Chafi, H., Kozyrakis, C., and Olukotun, K. Architectural semantics for practical transactional memory. In Proceedings of the 33rd International Symposium on Computer Architecture. ACM, 2006, 53–65.
McDonald, A., Chung, J., Chafi, H., Cao Minh, C., Carlstrom, B.D., Hammond, L., Kozyrakis, C., and Olukotun, K. Characterization of TCC on chip-multiprocessors. In Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques. (St Louis, MO, 2005). IEEE, 63–74.
Minh, C. C., Trautmann, M., Chung, J., McDonald, A., Bronson, N., Casper, J., Kozyrakis, C., and Olukotun, K. An effective hybrid transactional memory system with strong isolation guarantees. In Proceedings of the 34th International Symposium on Computer Architecture (San Diego, CA, 2007) ACM, NY, 69–80.
Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., and Wood, D.A. LogTM: Log-based transactional memory. In Proceedings of the 12th International Symposium on High-Performance Computer Architecture (Austin, TX, 2006). IEEE, 254–265.
Moravan, M.J., Bobba, J., Moore, K.E., Yen, L., Hill, M.D., Liblit, B., Swift, M.M., and Wood, D.A. Supporting Nested Transactional Memory in LogTM. Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (San Jose, CA, 2006). ACM, NY, 359–370.
Rajwar, R., Herlihy, M., and Lai, K. Virtualizing transactional memory. In Proceedings of the 32nd International Symposium on Computer Architecture (Madison, WI, 2005). ACM. NY, 494–505.
Saha, B., Adl-Tabatabai, A. R., and Jacobson, Q. Architectural support for software transactional memory. In Proceedings of the 39th International Symposium on Microarchitecture (Orlando, FL, 2006). IEEE, 185–196.
Saha, B., Adl-Tabatabai, A.R., Hudson, R.L., Minh, C.C., and Hertzberg, B. McRT-STM: A high performance software transactional memory system for a multi-core runtime. In Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2006). ACM, NY, 187–197.
Scherer III, W.N., and Scott, M.L. Advanced contention management for dynamic software transactional memory. In Proceedings of the Twentyfourth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Las Vegas, NV, 2005). ACM Press, 240–248.
Shavit, N. and Touitou, D. Software transactional memory . In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (Ottawa, Canada, 1995). ACM, NY, 204–213.
Shpeisman, T., Menon, V., Adl-Tabatabai, A.-R., Balensiefer, S., Grossman, D., Hudson, R.L., Moore, K.F., and Saha, B. Enforcing isolation and ordering in STM. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, CA, 2007). ACM, NY, 78–88.
Shriraman, A., Spear, M.F., Hossain, H., Marathe, V.J., Dwarkadas, S., and Scott, M.L. An integrated hardware-software approach to flexible transactional memory. In Proceedings of the 34th International Symposium on Computer Architecture (San Diego, CA, 2007). ACM, NY, 104–115.
Zilles, C. and Baugh, L. Extending hardware transactional memory to support nonbusy waiting and nontransactional actions. In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (Ottawa, Canada, 2006). ACM, NY.

Назад Оглавление