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

20:00 | Статьи Автор: Vadim Godunko

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

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

  • Increment — увеличивает значение счётчика на единицу;

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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:

1
2
3
4
5
6
7
8
9
10
11
   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; а так же для обеспечения возможности начальной инициализации значения счётчика.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 соответственно:

1
2
3
4
5
6
counters__decrement:
        movl    $-1, %eax
        lock xaddl      %eax, (%rdi)
        cmpl    $1, %eax
        sete    %al
        ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

Полный исходный текст примеров можно скачать по ссылке [download id="1"].

Комментариев нет »