На главную -> MyLDP -> Тематический каталог -> Аппаратное обеспечение

---

Что каждый программист должен знать о памяти. Часть 8. Технологии будущего

Оригинал: Memory part 8: Future technologies
Автор: Ulrich Drepper
Дата публикации: ноябрь 2007 г.
Перевод: М.Ульянов
Дата перевода: май 2010 г.

8. Грядущие технологии: что нас ждет?

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

8.1. Проблемы с атомарными операциями

Традиционно, синхронизация доступа к разделяемым структурам данных реализуется двумя способами:

• применением взаимных исключений (мьютексов), для чего обычно используются возможности системной среды исполнения;
• применением безблокировочных (lock-free) структур данных.

Недостаток второго варианта: от процессора требуется поддержка примитивов, способных выполнить полностью всю операцию атомарно. Не все процессоры поддерживают такие примитивы. На большинстве архитектур поддержка сводится к атомарным операциям чтения и записи одного [машинного] слова. Есть два основных способа их реализации (см. раздел 6.4.2):

• использование атомарной операции "сравнение и замена" (CAS);
• использование пары инструкций load lock/store conditional (LL/SC).

Нетрудно заметить, что операция CAS может быть реализована с применением инструкций LL/SC. И поэтому именно она применяется в качестве основы большинства атомарных операций и безблокировочных структур данных.

Некоторые процессоры, в особенности архитектуры x86 и x86-64, поддерживают куда более широкий набор атомарных инструкций. Многие из которых представляют собой версии CAS, оптимизированные под отдельные задачи. Например, атомарный инкремент хранящегося в памяти значения может быть реализован с помощью инструкций CAS и LL/SC, но родная, "нативная" поддержка атомарного инкрементирования на процессорах x86/x86-64 работает быстрее. Важно, чтобы программисты при работе знали об этих инструкциях и о том, как их применять. Хотя в этом нет ничего нового.

Но что действительно выделяет эти две архитектуры, так это поддержка операций CAS с двойными словами (DCAS). Это значительный плюс для некоторых (но не для всех, см. [dcas]) приложений . В качестве примера использования DCAS давайте попробуем написать безблокировочную структуру данных стека LIFO, основанную на массиве. Первая попытка, с применением встроенных средств gcc, показана на рисунке 8.1.

  struct elem {
    data_t d;
    struct elem *c;
  };
  struct elem *top;
  void push(struct elem *n) {
    n->c = top;
    top = n;
  }
  struct elem *pop(void) {
    struct elem *res = top;
    if (res != NULL)
      top = res->c;
    return res;
  }

Рисунок 8.1: Стек LIFO, не ориентированный на многопоточность

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

Для начала попытаемся решить проблему, применив CAS при вставке и удалении элементов списка. В итоге получим код, показанный на рисунке 8.2.

  #define CAS __sync_bool_compare_and_swap
  struct elem {
    data_t d;
    struct elem *c;
  };
  struct elem *top;
  void push(struct elem *n) {
    do
      n->c = top;
    while (!CAS(&top, n->c, n));
  }
  struct elem *pop(void) {
    struct elem *res;
    while ((res = top) != NULL)
      if (CAS(&top, res, res->c))
        break;
    return res;
  }

Рисунок 8.2: Стек LIFO, организованный с применением CAS

На первый взгляд, должно работать. Переменная top не изменяется до тех пор, пока не совпадет с элементом, который находился на вершине стека при начале операции. Но нужно принимать во внимание параллельность на всех уровнях. Другой поток, работающий с этой же структурой, может вступить в дело в самый неподходящий момент. Один из таких случаев - так называемая проблема ABA. Представьте, что произойдет, если второй поток запланирован прямо перед инструкцией CAS в pop и он выполняет следующие действия:

1. l = pop()
2. push(newelem)
3. push(l)

В результате этих действий элемент, находящийся на вершине стека, возвращается на своё место, но второй элемент изменился. При этом в первом потоке, поскольку верхний элемент остался прежним, операция CAS выполнится успешно. Но значение res->c уже не верно. Это указатель на второй элемент первоначального стека, а не на newelem. И что в итоге? Новый элемент потерян.

В литературе [см. lockfree] можно найти предложения по решению этой проблемы, основанные на особенностях некоторых процессоров. А именно, имеются в виду процессоры x86 и x86-64 и их способность выполнять инструкции DCAS. На рисунке 8.3 показана третья версия кода, на этот раз с применением DCAS.

  #define CAS __sync_bool_compare_and_swap
  struct elem {
    data_t d;
    struct elem *c;
  };
  struct lifo {
    struct elem *top;
    size_t gen;
  } l;
  void push(struct elem *n) {
    struct lifo old, new;
    do {
      old = l;
      new.top = n->c = old.top;
      new.gen = old.gen + 1;
    } while (!CAS(&l, old, new));
  }
  struct elem *pop(void) {
    struct lifo old, new;
    do {
      old = l;
      if (old.top == NULL) return NULL;
      new.top = old.top->c;
      new.gen = old.gen + 1;
    } while (!CAS(&l, old, new));
    return old.top;
  }

Рисунок 8.3: Стек LIFO, основанный на CAS с двойными словами

В отличие от предыдущей пары примеров, это лишь псевдокод (на данный момент), поскольку gcc пока "не понимает" передачу структур в качестве параметров CAS. Тем не менее, такого примера должно быть достаточно для понимания принципов подхода. К указателю на вершину стека добавляется счетчик обращений. Так как он изменяется при любой операции, будь то push или pop, описанная выше проблема ABA решается сама собой. К тому времени как первый поток возобновит работу, пытаясь обновить указатель top, счетчик обращений уже будет увеличен трижды. Следовательно, инструкция CAS завершится неудачей, и на следующей итерации цикла будут определены верные значения первого и второго элементов стека. Мы избежали ошибки. Проблема решена!

Но решена ли она на самом деле? Авторы данного труда [lockfree] убеждены, что да - и надо отдать им должное, такой подход стоит упоминания. Действительно, вполне возможно создать структуры данных для стека LIFO, позволяющие использовать вышеприведенный код. Но в общем случае, этот подход не лучше предыдущего. Проблемы с параллельностью не исчезли - они лишь переместились в другое место. Предположим, поток выполняет pop и затем прерывается сразу после проверки old.top == NULL. Тут второй поток использует pop и завладевает бывшим первым элементом стека. Поток может сделать с ним что угодно - поменять все значения, к примеру, или (в случае динамически выделяемых элементов) освободить память.

Затем первый поток возобновляет работу. В переменной old все еще хранится предыдущее значение вершины стека. А если точнее, указатель top ссылается на элемент, только что обработанный вторым потоком. Оператором new.top = old.top->c первый поток обращается к значению элемента через указатель. Но элемент, на который ссылается указатель, возможно, уже освобожден. А часть адресного пространства, где он находился, возможно, недоступна - происходит сбой. В случае работы с данными родового типа подобные ситуации недопустимы. Любое решение этой проблемы обходится чрезвычайно дорого: память нельзя освобождать, ну или необходимо получить подтверждение того, что ни один поток более не ссылается на нее, прежде чем выполнить освобождение. Учитывая, что безблокировочные структуры данных по определению должны работать быстрее других и лучше поддерживать параллельность, видим, что эти дополнительные требования попросту сводят на нет все преимущества. Решить проблему может так называемая "сборка мусора" при работе с памятью, но она поддерживается не всеми языками. А где поддерживается - имеет свою цену.

Для более сложных структур данных обычно всё еще хуже. В вышеупомянутом документе также описана реализация FIFO, с некоторыми уточнениями в последующих материалах. Но и там всё те же проблемы. Поскольку на существующем оборудовании (x86, x86-64) инструкции CAS могут изменять только пару последовательно расположенных в памяти слов, то в других часто встречающихся ситуациях они вообще бывают бесполезны. К примеру, невозможно атомарное добавление либо удаление элементов в любом месте двусвязного списка. {Для справки: разработчики IA-64 также не реализовали эту возможность. Они позволяют сравнивать два слова, но заменять - только одно.}

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

---

Назад

Оглавление

Вперед

---

---