Почта[email protected]


Портируемая реализация атомарного счётчика

Автор Статьи: Vadim Godunko
Дата: 10-09-2010
Статья с сайта http://ru.ada-community.org/

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

В качестве примера будем рассматривать тип данных‐счётчик, инициализируемый начальным значением 1, и три операции над ним:

  • Increment — увеличивает значение счётчика на единицу;
  • Decrement — уменьшает значение счётчика на единицу, возвращает True если значение достигло нуля, в противном случае возвращает False;
  • Is_One — проверяет текущее значение счётчика, возвращает True если оно равно единице, в противном случае возвращает False.

Поставленная задача может быть решена встроенными средствами языка, например так


        
        

        
        
with Interfaces;

package Counters is

   type Counter is limited private;

   procedure Increment (Self : in out Counter);

   function Decrement (Self : not null access Counter) return Boolean;

   function Is_One (Self : Counter) return Boolean;

private

   protected type Counter is
      procedure Increment;
      procedure Decrement (Is_Zero : out Boolean);
      function Is_One return Boolean;
   private
      Value : Interfaces.Unsigned_32 := 1;
   end Counter;

end Counters;

        
#ada  
package body Counters is

   use type Interfaces.Unsigned_32;

   -------------
   -- Counter --
   -------------

   protected body Counter is

      ---------------
      -- Decrement --
      ---------------

      procedure Decrement (Is_Zero : out Boolean) is
      begin
         Value   := Value - 1;
         Is_Zero := Value = 0;
      end Decrement;

      ---------------
      -- Increment --
      ---------------

      procedure Increment is
      begin
         Value := Value + 1;
      end Increment;

      ------------
      -- Is_One --
      ------------

      function Is_One return Boolean is
      begin
         return Value = 1;
      end Is_One;

   end Counter;

   ---------------
   -- Decrement --
   ---------------

   function Decrement (Self : not null access Counter) return Boolean is
      Is_Zero : Boolean;

   begin
      Self.Decrement (Is_Zero);

      return Is_Zero;
   end Decrement;

   ---------------
   -- Increment --
   ---------------

   procedure Increment (Self : in out Counter) is
   begin
      Self.Increment;
   end Increment;

   ------------
   -- Is_One --
   ------------

   function Is_One (Self : Counter) return Boolean is
   begin
      return Self.Is_One;
   end Is_One;

end Counters;

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

        
Значительно интереснее было бы использовать аппаратную поддержку операций атомарного инкремента/декремента, присутствующую в большинстве современных процессоров. Это, однако, требует включения в код ассемблерных вставок, что приводит к невозможности легкого портирования кода. Тем не менее, пользователи компилятора GNAT имеют возможность использовать встроенные функции GCC для выполнения атомарных операций инкремента/декремента. Их использование не делает код портируемым между GNAT‐ом и другим компилятором, но позволяет использовать его на большом количестве современных процессоров (среди которых Alpha, IA64, PowerPC, SPARC V9, X86-64).

        
Семейство встроенных функций GCC для инкремента именуется как __sync_add_and_fetch_X, а для декремента значения как __sync_sub_and_fetch_X, где X — размер операнда в байтах. В Ada эти операции могут быть импортированы с указанием соглашения Intrinsic:

        
#ada 
   procedure Sync_Add_And_Fetch
     (Ptr   : access Interfaces.Unsigned_32;
      Value : Interfaces.Unsigned_32);
   pragma Import
     (Intrinsic, Sync_Add_And_Fetch, "__sync_add_and_fetch_4");

   function Sync_Sub_And_Fetch
     (Ptr   : access Interfaces.Unsigned_32;
      Value : Interfaces.Unsigned_32) return Interfaces.Unsigned_32;
   pragma Import
     (Intrinsic, Sync_Sub_And_Fetch, "__sync_sub_and_fetch_4");

        
Использование встроенных функций требует особого внимания к некоторым аспектам объявления и использования переменной‐счётчика. Это затрагивает:

        
    
          
  • выравнивания объекта в памяти — некоторые процессоры накладывают жесткие ограничения на выравнивание данных в памяти и неспособны выполнить операции чтения/записи невыровненных данных;
    • 
        

        
    
          
  • обеспечения доступа к значению одной неразрывной операцией — необходимо гарантировать, что процессор способен выполнять чтение/запись одной неразрывной операцией, в противном случае возможно получение некорректных данных при чтении или искажение данных при записи;
    • 
        

        
    
          
  • предотвращения оптимизации кода сохранением значения в регистрах и последующим его использованием. ;
    • 
        

        
Стандартные средства языка Ada предоставляют портируемые способы решения этих задач:

        
    
          
  • для обеспечения корректного выравнивания объекта в памяти достаточно объявить переменную как aliased;
    • 
        

        
    
          
  • проверка поддержки неразрывного доступа к значению и использование соответствующих операций гарантируется использованием прагмы Atomic;
    • 
        

        
    
          
  • оптимизация кода путём сохранения ранее прочитанного значения в регистрах отключается применение прагмы Volatile;
    • 
        

        
Прежде чем показать полный код реализации полезно обратить внимание на один небольшой момент — приватный тип Counter объявлен как запись с одним компонентом для хранения значения. Это необходимо для гарантии корректного выравнивания, и снятия с пользователя необходимости контроля за выравниванием объектов Counter; а так же для обеспечения возможности начальной инициализации значения счётчика.

        
А теперь приведём полный код реализации:

        
#ada     
with Interfaces;

package Counters is

   type Counter is limited private;

   procedure Increment (Self : in out Counter);
   pragma Inline (Increment);

   function Decrement (Self : not null access Counter) return Boolean;
   pragma Inline (Decrement);

   function Is_One (Self : Counter) return Boolean;
   pragma Inline (Is_One);

private

   type Counter is record
      Value : aliased Interfaces.Unsigned_32 := 1;
      pragma Atomic (Value);
      pragma Volatile (Value);
   end record;

end Counters;

        
#ada    
package body Counters is

   use type Interfaces.Unsigned_32;

   procedure Sync_Add_And_Fetch
     (Ptr   : access Interfaces.Unsigned_32;
      Value : Interfaces.Unsigned_32);
   pragma Import
     (Intrinsic, Sync_Add_And_Fetch, "__sync_add_and_fetch_4");

   function Sync_Sub_And_Fetch
     (Ptr   : access Interfaces.Unsigned_32;
      Value : Interfaces.Unsigned_32) return Interfaces.Unsigned_32;
   pragma Import
     (Intrinsic, Sync_Sub_And_Fetch, "__sync_sub_and_fetch_4");

   ---------------
   -- Decrement --
   ---------------

   function Decrement (Self : not null access Counter) return Boolean is
   begin
      return Sync_Sub_And_Fetch (Self.Value'Access, 1) = 0;
   end Decrement;

   ---------------
   -- Increment --
   ---------------

   procedure Increment (Self : in out Counter) is
   begin
      Sync_Add_And_Fetch (Self.Value'Access, 1);
   end Increment;

   ------------
   -- Is_One --
   ------------

   function Is_One (Self : Counter) return Boolean is
   begin
      return Self.Value = 1;
   end Is_One;

end Counters;

        
Приведённая реализация с использованием встроенных функций GCC будет успешно работать при использовании компилятора GNAT GPL 2009 и выше. При компиляции кода для процессора x86 в 32‐битном режиме необходимо активировать режим генерации кода для процессора 80486 и выше (указав в ключ компилятора -march=i486, хотя в общем случае можно порекомендовать использовать ключ -march=i686).

        
Для особо пытливых приводятся фрагменты кода подпрограммы Decrement для процессоров x86_64 и SPARC V9 соответственно:

        
counters__decrement:
        movl    $-1, %eax
        lock xaddl      %eax, (%rdi)
        cmpl    $1, %eax
        sete    %al
        ret

        
counters__decrement: lduw [%o0], %g2 .LL11: mov %g2, %g1 add %g2, -1, %g3 membar 15 mov %g3, %g4 cas [%o0], %g2, %g4 cmp %g4, %g1 bne,pt %icc, .LL11 mov %g4, %g2 subcc %g0, %g3, %g0 subx %g0, -1, %o0 jmp %o7+8 nop