In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It functions as an alternative to lock-based synchronization, and is typically implemented in a lock-free way. A transaction in this context is a piece of code that executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in 1993 by Maurice Herlihy and J. Eliot B. Moss. In 1995 Nir Shavit and Dan Touitou extended this idea to software-only transactional memory (STM). STM has recently been the focus of intense research and support for practical implementations is growing.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, deniok, Вы писали:
D>>Какие мнения об идее/технологии?
AF>Очень правильная идея. Хотя в дополнение к ней нужны еще механизмы ограничений на данные, аналогично базам данных. Только помощнее
Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
И каким образом это в STM может быть "встроено"?
ИМХО это задачи приложения.
Здравствуйте, Курилка, Вы писали:
К>Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
Ограничения на значения целых переменных и длин строк, null/not null, допустимые диапазоны значений, допустимые отношения между объектами и так далее. Если ограничения нарушены — исключение и откат транзакции по умолчанию.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, Курилка, Вы писали:
К>>Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
AF>Ограничения на значения целых переменных и длин строк, null/not null, допустимые диапазоны значений, допустимые отношения между объектами и так далее. Если ограничения нарушены — исключение и откат транзакции по умолчанию.
Ты думаешь, что это всё должно быть выведено на "базовый" уровень?
Почему не использовать сам механизм транзакций и реализовать уже логику ограничений под приложение?
Здравствуйте, Курилка, Вы писали:
К>Ты думаешь, что это всё должно быть выведено на "базовый" уровень? К>Почему не использовать сам механизм транзакций и реализовать уже логику ограничений под приложение?
Думаю Такие задачи есть практически в каждом первом приложении, везде практически в неизменном виде. Это конечно не неотъемлемая часть механизма транзакций, но очень тесно с ним связано.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, Курилка, Вы писали:
К>>Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
AF>Ограничения на значения целых переменных и длин строк, null/not null, допустимые диапазоны значений, допустимые отношения между объектами и так далее. Если ограничения нарушены — исключение и откат транзакции по умолчанию.
Что-то мне кажется, что STM — штука более низкоуровневая. А это всё легко обеспечить на уровне библиотеки, её (STM) обёртывающей. Или имеется ввиду уже упаковка под .NET?
Здравствуйте, deniok, Вы писали:
D>Что-то мне кажется, что STM — штука более низкоуровневая. А это всё легко обеспечить на уровне библиотеки, её (STM) обёртывающей. Или имеется ввиду уже упаковка под .NET?
Упаковка чего именно? Библиотека не есть "упаковка"?
deniok wrote: > Какие мнения об идее/технологии?
Я использовал аналогичный подход в своей программе (на С++!) —
действительно, достаточно удобно. Очень напоминает программирование БД
Проблемы в этом подходе будут при работе с циклическими графами
объектов. Для чистых функциональных языков это не важно — там невозможно
создать цикл (все переменные иммутабельны), но вот для императивного
стиля — все плохо.
У себя я обошел эту проблему с помощью понятия "видов" (view) графа, но
у меня они использовались только для некоторых частных случаев изменений.
Здравствуйте, Cyberax, Вы писали:
C>Проблемы в этом подходе будут при работе с циклическими графами C>объектов. Для чистых функциональных языков это не важно — там невозможно C>создать цикл (все переменные иммутабельны), но вот для императивного C>стиля — все плохо.
Циклический граф на чистом функциональном ленивом языке создать элементарно:
-- cyclic list
oneTwoThrees = 1:2:3:oneTwoThrees
-- cyclic graphdata Graph a = Node a [Graph a]
x = Node "x" [y,z]
y = Node "y" [x,z]
z = Node "z" [x,y]
Теперь онтопик: какие проблемы с циклическими графами в транзакциях? Транзакция, насколько я понимаю, связана с атомарным обновлением нескольких значений с сохранением некоторого инварианта. Если граф конечный, то узлов/ребер также конечное число. Какое значение тут имеют циклы?
palm mute wrote: > Теперь онтопик: какие проблемы с циклическими графами в транзакциях? > Транзакция, насколько я понимаю, связана с атомарным обновлением > нескольких значений с сохранением некоторого инварианта. Если граф > конечный, то узлов/ребер также конечное число. Какое значение тут имеют > циклы?
Я имел в виду ненаправленный граф. Проблемы в том, что простое изменение
одного узла в цикле может потребовать хранить в транзакции все узлы, на
которые он ссылается.
PM>Циклический граф на чистом функциональном ленивом языке создать элементарно:
Пардон, ленивость я здесь по инерции приплел, она в данном случае роли не играет.
Здравствуйте, Cyberax, Вы писали:
C>Я имел в виду ненаправленный граф.
Ненаправленный граф делается так же легко.
C> Проблемы в том, что простое изменение C>одного узла в цикле может потребовать хранить в транзакции все узлы, на C>которые он ссылается. C>Я уже об этом писал: http://rsdn.ru/Forum/?mid=2209784
После беглого осмотра ссылки я не понял, как она связана с транзакциями. Насколько я понял, там ты демонстрировал сложности написания чисто-функционального ОО-кода на С++ (задача, несомненно, хитрая, но непревзойденный Олег Киселев ее решал, правда на Схеме, — http://okmij.org/ftp/Scheme/pure-oo-system.scm).
Транзакции не требуют клонирования циклических графов, потому мне по-прежнему непонятно, в чем проблема. Что значит "хранить в транзакции все узлы"? Может быть, приведешь пример (псевдо-)кода?
Здравствуйте, palm mute, Вы писали:
C>>Я имел в виду ненаправленный граф. PM>Ненаправленный граф делается так же легко.
Тормознул. А где в моем примере видно, что граф направленный?
palm mute wrote: > C> Проблемы в том, что простое изменение > C>одного узла в цикле может потребовать хранить в транзакции все узлы, на > C>которые он ссылается. > C>Я уже об этом писал: http://rsdn.ru/Forum/?mid=2209784
Cyberax wrote: > Теперь понятнее?
Да, еще добавлю — в случае чистых функциональных языков мы просто НЕ
МОЖЕМ поменять объект в середине цепи, так что такая ситуация просто
невозможна.
Здравствуйте, Cyberax, Вы писали:
C>Я имел в виду ненаправленный граф. Проблемы в том, что простое изменение C>одного узла в цикле может потребовать хранить в транзакции все узлы, на C>которые он ссылается.
AndreiF wrote: > C>Я имел в виду ненаправленный граф. Проблемы в том, что простое изменение > C>одного узла в цикле может потребовать хранить в транзакции все узлы, на > C>которые он ссылается. > То есть основная проблема — в накладных расходах?
Не знаю. Думать надо.
Проблема в том, что ВСЕ соединения в графе начинают зависеть от
контекста. Мне пришлось искусственно ограничить количество операций, так
как многие частные случаи у меня не были рассмотрены.
Насколько я понимаю, проблема даже не в циклических ссылках. Просто, если нам нужно склонировать объект, то придется клонировать и все объекты, которые имеют ссылки на него (если в пределах транзакции может произойти обращение и к ним тоже).
Здравствуйте, Курилка, Вы писали:
К>Здравствуйте, deniok, Вы писали:
D>>Что-то мне кажется, что STM — штука более низкоуровневая. А это всё легко обеспечить на уровне библиотеки, её (STM) обёртывающей. Или имеется ввиду уже упаковка под .NET?
К>Упаковка чего именно? Библиотека не есть "упаковка"?
Есть ведь разные реализации STM под разные платформы. Первая моя ссылка на твою же ссылку на Кембридж — так они там на сановских многопроцессорных станциях свою STM тестировали.
Я, возможно неправильно, понимаю STM, как механизм разруливания транзакций. То есть есть ядро STM, которое обеспечивает атомарность и изолированность операций (естественно за счёт некоторых накладных расходов по времени и памяти). Доступ к этому механизму — это atomically и retry. А есть всякие доп. сервисы, которые можно надстроить над базовым механизмом.
В отличие от баз данных, откуда пришла сама идея, запись в переменную при обращении к памяти может происходить гораздо чаще, чем запись в таблицу. Я боюсь, что всякие дополнительные проверки диапазонов и т.п., характерные для БД, могут создать узкое место, если они будут неотъемлемой частью STM.
Собственно, меня-то больше всего интересует выигрыш/проигрыш по производительности по сравнению с параллельным программированием с использованием блокировок. Что удобства больше — это понятно, но если это будет работать медленнее аналогичной "однопоточной" программы (что иногда случается due to кривые ручки), то зачем огород городить?
