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

. В первой статье Шавита (Shavit) и Туиту (Touitou), посвященной STM [29], было показано, что можно полностью программным образом реализовать свободные от блокировок (lock-free) атомарные операции над несколькими переменными, но для этого в программе нужно заранее объявить, к каким ячейкам памяти будет обращаться данная транзакция.

Описанная Херлихи и др. в [14] система Dynamic STM (DSTM) была первой системой STM, в которой это требование снималось. DSTM является системой STM с гранулированностью на уровне объектов и откладываемыми изменениями (deferred-update). Это означает, что транзакция модифицирует частные копии объектов и делает видимыми изменения другим транзакциям при своей фиксации. Транзакция имеет монопольный доступ к этим копиям без синхронизации. Однако к исходным объектам могут обращаться другие транзакции, что приводит к возникновению логического конфликта, распознаваемого системой STM и разрешаемого путем аварийного завершения одной из транзакций.

Система STM может распознать конфликт при первом обращении транзакции к объекту (early detection, раннее выявление) или в то время, когда транзакция пытается выполнить операцию фиксации (late detection, отложенное выявление). Оба подхода приводят к одним и тем же результатам, но могут выполняться по-разному, и, к сожалению, ни один из них не обладает существенными преимуществами над другим. Раннее выявление предотвращает выполнение транзакциями излишних вычислений, которые будут отброшены при последующем откате. При отложенном выявлении можно избежать излишних откатов, которые могут возникнуть, когда конфликтующая транзакция откатывается сама по причине конфликта с третьей транзакцией.

Еще одной сложностью является конфликт между транзакцией, которая только читает некоторый объект, и другой транзакцией, которая изменяет этот объект. Поскольку чтения более распространены, чем записи, системы STM клонируют только модифицируемые объекты. Для сокращения накладных расходов транзакция отслеживает прочитанные объекты и до своей фиксации убеждается в том, что эти объекты не модифицировались никакой другой транзакцией.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий