Транзакционная память – вторая часть

  • Article

В прошлом посте мы рассмотрели концепцию транзакционной памяти - средство высокоуровневой организации работы параллельно выполняющихся задач. Рассмотрев основы операционной семантики, во многом совпадающие с семантикой транзакций, мы не упомянули несколько интересных расширений, предложенных в работе Composable Memory Transactions и воплощенных в языке Concurrent Haskell. О них и пойдет речь сегодня.

Оператор retry

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

Одним из первых предложений в этом направлении было введение условных критических областей (conditional critical regions, CCR) - аннотация транзакций некоторым условием, без правдивости которого транзакция не начинает выполнение. Этот подход работает, но не очень изящен, ибо требует создания новой транзакции даже тогда, когда транзакция уже запущена - то есть, только ради того, чтобы выразить семантику условного ожидания.

Современный взгляд на решение этой проблемы заключается в введении оператора retry, который сигнализирует о необходимости перезапуска транзакции - комбинация этого оператора с условным оператором предоставляет конструкт ожидания некоторого события и во многих случаях делает явную сигнализацию события избыточной. Ниже приведено сравнение реализаций блокирующей коллекции ограниченной емкости, аналогичной коллекции BlockingCollection<T> из .NET Framework 4.0 (реализация, основанная на примитивах синхронизации намеренно упрощена в целях краткости).

Блокирующая коллекция

(реализована при помощи примитивов синхронизации)

Блокирующая коллекция

(реализована при помощи оператора retry)

 
 public class BlockingCollection<T>
 {
     private Object _lock = new Object();
     
     public void Put(T item)
     {
         while (Monitor.Wait(_lock, Timeout.Inifinite))
         {
             try 
             {
                 Monitor.Enter(_lock);
                 if (_impl.Count == _maxSize) continue;
                 _impl.Enqueue(item);
             }
             finally
             {
                 Monitor.Pulse(_lock);
             }
         } 
     }
  
     public T Take()
     {
         while (Monitor.Wait(_lock, Timeout.Inifinite))
         {
             try 
             {
                 Monitor.Enter(_lock);
                 if (_impl.Count == 0) continue;
                 return _impl.Dequeue();
             }
             finally
             {
                 Monitor.Pulse(_lock);
             }
         }        
     }
 }
 
 public class BlockingCollection<T>
 {
     public void Put(T item)
     {
         atomic
         {
             if (_impl.Count == _maxSize) retry;
             _impl.Enqueue(item);
         }
     }
  
     public T Take()
     {
         atomic
         {
             if (_impl.Count == 0) retry;
             return _impl.Dequeue();
         }
     }
 }

Важно отметить, что реализация оператора retry совсем не обязана в цикле перезапускать транзакцию, занимая процессорное время и впустую растрачивая энергию - для корректной работы достаточно перезапускать транзакцию только лишь в случае, когда один из элементов данных, прочитанных транзакцией до выполнения retry, изменился. Например, для метода Take в примере выше система исполнения, обнаружив, что поток вызвал retry, приостановит его до того момента, пока не изменится ссылка на объект _impl или поле Count объекта _impl (это возможно, так как типичная реализация STM контролирует все операции с данными приложения - см. раздел "Детали реализации" предыдущего поста).

Для полноты изложения отметим особенность операционной семантики оператора retry в контексте вложенных транзакций. Как упоминалось в предыдущем посте в разделе "Операционная семантика", вложенность транзакций проявляется только лишь в откате, но не в фиксации. Тот же самый принцип верен и здесь - если вложенная транзакция вызывает retry, то сигнал о перезапуске получает вся транзакция целиком, то есть retry работает как выброс необрабатываемого исключения (с поправкой на то, что, как указано выше, система исполнения может не обрабатывать retry немедленно, а подождать наилучшего момента).

Комбинатор orElse

В дополнении к оператору retry, который позволяет последовательно комбинировать блокирующие транзакции (например, два подряд идущих вызова Take, которые поочередно получают элементы из различных коллекций), можно ввести оператор orElse, который позволяет комбинировать альтернативные транзакции.

Этот бинарный оператор вначале выполняет транзакцию в левой части. При успешном завершении левой части комбинатор завершает свою работу, а в случае, если эта транзакция вызвала retry, то вместо обычного ожидания она будет отменена, и будет запущена транзакция в правой части. В случае вызова retry и транзакцией в правой части, retry распространится выше по дереву транзакций. Продолжая аналогию - если retry можно рассматривать как выброс исключения, то orElse представляет собой нечто вроде блока catch (с поправкой на то, что и retry, и orElse могут обрабатываются отложенно).

Оставляя в стороне красивые математические свойства этого комбинатора (то, что множество транзакций является относительно него моноидом), рассмотрим его применение в преобразовании между блокирующими и неблокирующими вызовами на примере выше:

 public bool NonBlockingTake(out T item)

 {

     atomic

     {

         item = Take();

         return true; 

     }

     ||

     atomic

     {

         item = null;

         return false;

     }

 }

Если в очереди есть элементы, то этот метод работает предсказуемо - возвращает последний элемент в out-параметре. Если же в очереди нет элементов, то транзакция, объявленная в методе Take, выполнит оператор retry, который распространится и на родительскую транзакцию, объявленную в методе NonBlockingTake, в результате чего будет выполнена правая часть комбинатора orElse и будет возвращен false.