восстановление памяти без блокировки с помощью 64-битных указателей

StackOverflow https://stackoverflow.com/questions/1061889

  •  21-08-2019
  •  | 
  •  

Вопрос

Книга Херлихи и Шавита (Искусство многопроцессорного программирования) решение для восстановления памяти использует Java AtomicStampedReference<T>;.

Чтобы написать его на C ++ для x86_64, я полагаю, требуется по крайней мере 12-байтовая операция подкачки - 8 для 64-битного указателя и 4 для int.

Существует ли аппаратная поддержка x86 для этого, и если нет, какие-либо указания на то, как выполнить восстановление памяти без ожидания без этого?

Это было полезно?

Решение

Да, есть аппаратная поддержка, хотя я не знаю, доступна ли она библиотекам C ++.В любом случае, если вы не возражаете проделать несколько низкоуровневых трюков с непереносимым языком ассемблера - посмотрите инструкцию CMPXCHG16B в руководствах Intel.

Другие советы

Windows предоставляет вам множество Взаимосвязанные функции они являются атомарными и, вероятно, могут быть использованы для выполнения того, что вы хотите.Аналогичные функции существуют и для других платформ, и я полагаю, что Boost также имеет взаимосвязанную библиотеку.

Ваш вопрос не совсем ясен, и у меня нет ни одной копии "Херлихи и Шавит".Возможно, если вы разработаете или предоставите псевдокод, описывающий, что вы хотите сделать, мы сможем дать вам более конкретный ответ.

Ладно, надеюсь, книга у меня есть,

Для других, которые могут дать ответы, смысл в том, чтобы реализовать этот класс : 

class AtomicReference<T>{
  public:
    void set(T *ref, int stamp){ ... }
    T *get(int *stamp){ ... }
  private:  
    T *_ref; 
    int _stamp;

};

без блокировки, чтобы :

  • set() обновляет ссылку и штамп атомарно.
  • get() возвращает ссылку и устанавливает *stamp на штамп, соответствующий ссылке.

JDonner, пожалуйста, поправьте меня, если я ошибаюсь.

Теперь мой ответ :Я не думаю, что вы можете сделать это где-то без блокировки (блокировка может быть while(test_and_set() != ..)).Поэтому для этого не существует алгоритма без блокировки.Это означало бы, что можно построить N-регистр без блокировки для любого N.

Если вы посмотрите на книгу pragma 9.8.1, AtomicMarkableReference, которая является такой же, с одним битом вместо целочисленной метки.Автор предлагает "украсть" немного из указателя, чтобы извлечь метку и указатель из одного слова (большинство в кавычках) Это, очевидно, означает, что они хотят использовать для этого один атомарный регистр.

Однако, возможно, есть способ отключить восстановление памяти без ожидания и без этого.Я не знаю.

Да, x64 поддерживает это;вам нужно использовать CMPXCHG16B.

Вы можете немного сэкономить память, полагаясь на тот факт, что указатель будет использовать менее 64 бит.Во-первых, определите compare&set функция (этот ASM работает в GCC и ICC):

inline bool CAS_ (volatile uint64_t* mem, uint64_t old_val, uint64_t new_val)
{
  unsigned long old_high = old_val >> 32, old_low = old_val;
  unsigned long new_high = new_val >> 32, new_low = new_val;

  char res = 0;
  asm volatile("lock; cmpxchg8b (%6);"
               "setz %7; "
               : "=a" (old_low),  // 0
                 "=d" (old_high)  // 1
               : "0" (old_low),   // 2
                 "1" (old_high),  // 3
                 "b" (new_low),   // 4
                 "c" (new_high),  // 5
                 "r" (mem),       // 6
                 "m" (res)        // 7
               : "cc", "memory");
  return res;
}

Затем вам нужно будет создать тип помеченного указателя.Я предполагаю 40-битный указатель с шириной строки кэша 128 байт (например, Nehalem).Выравнивание по строке кэша значительно улучшит скорость за счет уменьшения ложного обмена данными, конфликтов и т.д.;это имеет очевидный компромисс с использованием лот в некоторых ситуациях больше памяти.

template <typename pointer_type, typename tag_type, int PtrAlign=7, int PtrWidth=40>
struct tagged_pointer
{
  static const unsigned int PtrMask = (1 << (PtrWidth - PtrAlign)) - 1;
  static const unsigned int TagMask = ~ PtrMask;

  typedef unsigned long raw_value_type;

  raw_value_type raw_m_;

  tagged_pointer () : raw_m_(0) {}
  tagged_pointer (pointer_type ptr) { this->pack(ptr, 0); }
  tagged_pointer (pointer_type ptr, tag_type tag) { this->pack(ptr, tag); }

  void pack (pointer_type ptr, tag_type tag)
  {
    this->raw_m_ = 0;
    this->raw_m_ |= ((ptr >> PtrAlign) & PtrMask);
    this->raw_m_ |= ((tag << (PtrWidth - PtrAlign)) & TagMask);
  }

  pointer_type ptr () const
  {
    raw_value_type p = (this->raw_m_ & PtrMask) << PtrAlign;
    return *reinterpret_cast<pointer_type*>(&p);
  }

  tag_type tag () const
  {
    raw_value_type t = (this->raw_m_ & TagMask) >> (PtrWidth - PtrAlign_;
    return *reinterpret_cast<tag_type*>(&t);
  }
};

У меня не было возможности отладить этот код, так что вам нужно будет это сделать, но такова общая идея.

Обратите внимание, что в архитектуре x86_64 и gcc вы можете включить 128-битный CAS.Это может быть включено с помощью -mcx16 опция gcc.

int main()
{
   __int128_t x = 0;
   __sync_bool_compare_and_swap(&x,0,10);
   return 0;
}

Скомпилировать с помощью:

gcc -mcx16 file.c

Операция cmpxchg16b обеспечивает ожидаемую операцию, но имейте в виду, что некоторые старые процессоры x86-64 не имеют этой инструкции.

Затем вам просто нужно создать объект со счетчиком, указателем и встроенным в asm кодом.Я написал сообщение в блоге на эту тему здесь:Реализация универсального Двойного сравнения слов и Подкачки

Тем не менее, вам не нужна эта операция, если вы просто хотите предотвратить проблемы с досрочным освобождением и ABA.Указатель опасности более прост и не требует специального asm-кода (при условии, что вы используете атомарные значения C ++ 11). У меня есть репозиторий на bitbucket с экспериментальными реализациями различных алгоритмов без блокировки: Эксперимент без блокировки (имейте в виду, что все эти реализации являются игрушками для экспериментов, а не надежным и проверенным кодом для производства.)

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top