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

Автор Статьи: 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;

Unknown format: ada

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

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

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

Unknown format: ada

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

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

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

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

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

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

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

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

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

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

Unknown format: ada Unknown format: ada

Приведённая реализация с использованием встроенных функций 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

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

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

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

Поставленная задача может быть решена встроенными средствами языка, например так
{{{
#ada
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;
}}}

Семейство встроенных функций 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;

А теперь приведём полный код реализации:
{{{
#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");

---------------
   -- 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;
}}}

Для особо пытливых приводятся фрагменты кода подпрограммы 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
}}}