Транзакционная память

Работа в процессе Эта страница находится в разработке

Экспериментальная Функциональность Функциональные возможности, описанные на этой странице, являются частью Технической Спецификации Транзакционной Памяти ISO/IEC ТС 19841:2015 (ТС TM)

Транзакционная память это механизм синхронизации конкуренции, который объединяет группы операторов в транзакциях, которые

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

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

Обратите внимание, что доступ к переменной в транзакции и вне транзакции без другой внешней синхронизации это гонка данных.

Если тестирование функциональных возможностей поддерживается, описанные здесь функциональные возможности обозначаются макроконстантой __cpp_transactional_memory со значением, равным или большим 201505.

[править] Синхронизированные блоки

synchronized составной-оператор

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

Синхронизированные блоки не являются транзакциями (в отличие от атомарных блоков, описанных ниже) и могут вызывать функции, небезопасные для транзакций.

#include <iostream>
#include <thread>
#include <vector>
int f()
{
    static int i = 0;
    synchronized { // начало синхронизированного блока
        std::cout << i << " -> ";
        ++i;       // каждый вызов f() получает уникальное значение i
        std::cout << i << '\n';
        return i; // конец синхронизированного блока
    }
}
int main()
{
    std::vector<std::thread> v(10);
    for(auto& t: v)
        t = std::thread([]{ for(int n = 0; n < 10; ++n) f(); });
    for(auto& t: v)
        t.join();
}

0 -> 1
1 -> 2
2 -> 3
...
99 -> 100

Выход из синхронизированного блока любым способом (достижение конца, выполнение goto, break, continue или return или выбросом исключения) завершает блок и синхронизируется со следующим блоком в едином общем порядке, если завершённый блок был внешним блоком. Поведение не определённо, если для выхода из синхронизированного блока используется std::longjmp.

Вход в синхронизированный блок с помощью goto или switch не допускается.

Хотя синхронизированные блоки выполняются как будто под глобальной блокировкой, ожидается, что реализации будут проверять код в каждом блоке и использовать оптимистичную конкуренцию (поддерживаемую аппаратной транзакционной памятью, если она доступна) для безопасного для транзакций кода и минимальную блокировку для небезопасного для транзакций кода. Когда синхронизированный блок вызывает не встроенную функцию, компилятору может потребоваться выйти из спекулятивного выполнения и удерживать блокировку всего вызова, если только функция не объявлена как transaction_safe (смотрите ниже) или используется атрибут [[optimize_for_synchronized]] (смотрите ниже).

[править] Атомарные блоки

atomic_noexcept составной-оператор

atomic_cancel составной-оператор

atomic_commit составной-оператор

Исключения, используемые для отмены транзакции в блоках atomic_cancel это std::bad_alloc, std::bad_array_new_length, std::bad_cast, std::bad_typeid, std::bad_exception, std::exception и все исключения стандартной библиотеки, производные от них, и особый тип исключения std::tx_exception<T>

Составному-оператору в атомарном блоке не разрешается выполнять какое-либо выражение или инструкцию или вызывать любую функцию, которая не является transaction_safe (это ошибка времени компиляции)

// каждый вызов f() извлекает уникальное значение i, даже если выполняется параллельно
int f()
{
   static int i = 0;
   atomic_noexcept { // начало транзакции
//   printf("перед %d\n", i); // ошибка: невозможно вызвать транзакционно-небезопасную
//                                       функцию
      ++i;
      return i; // фиксация транзакции
   }
}

Выход из атомарного блока любым способом, кроме исключения (достижение конца, goto, break, continue, return), фиксирует транзакцию. Поведение не определено, если для выхода из атомарного блока используется std::longjmp.

[править] Транзакционно-безопасные функции

Функцию можно явно объявить безопасной для транзакций, используя ключевое слово transaction_safe в её объявлении.

В объявлении лямбда оно появляется либо сразу после списка захвата, либо сразу после ключевого слова mutable (если оно используется).

extern volatile int * p = 0;
struct S {
  virtual ~S();
};
int f() transaction_safe {
  int x = 0; // ok: не volatile
  p = &x; // ok: указатель не volatile
  int i = *p; // ошибка: чтение через volatile glvalue
  S s; // ошибка: вызов небезопасного деструктора
}

int f(int x) { // неявно безопасна для транзакций
  if (x <= 0)
    return 0;
  return x + f(x-1);
}

Если функция, которая не является безопасной для транзакций, вызывается через ссылку или указатель на безопасную для транзакций функцию, поведение не определено.

Указатели на безопасные для транзакций функции и указатели на безопасные для транзакций функции-элементы неявно преобразуются в указатели на функции и указатели на функции-элементы соответственно. Не указано, сравнивается ли результирующий указатель с оригиналом.

[править] Транзакционно-безопасные виртуальные функции

Если последний переопределитель функции transaction_safe_dynamic не объявлен как transaction_safe, его вызов в атомарном блоке является неопределённым поведением.

[править] Стандартная библиотека

Помимо введения нового шаблона исключения std::tx_exception, техническая спецификация транзакционной памяти вносит следующие изменения в стандартную библиотеку:

• делает следующие функции явно transaction_safe:

• std::forward, std::move, std::move_if_noexcept, std::align, std::abort, глобальный по умолчанию operator new, глобальный по умолчанию operator delete, std::allocator::construct если вызываемый конструктор транзакционно-безопасный, std::allocator::destroy если вызываемый деструктор транзакционно-безопасный, std::get_temporary_buffer, std::return_temporary_buffer, std::addressof, std::pointer_traits::pointer_to, каждая невиртуальная функция-элемент всех типов исключений, поддерживающих отмену транзакции (смотрите atomic_cancel выше)

  Этот раздел не завершён Причина: есть больше

• делает следующие функции явно transaction_safe_dynamic

• каждая виртуальная функция-элемент всех типов исключений, которые поддерживают отмену транзакции (смотрите atomic_cancel выше)

• требует, чтобы все операции, транзакционно-безопасные на Allocator X, были транзакционно-безопасными на X::rebind<>::other

[править] Атрибуты

Атрибут [[optimize_for_synchronized]] может применяться к декларатору в объявлении функции и должен появляться в первом объявлении функции.

Если функция объявлена как [[optimize_for_synchronized]] в одной единице трансляции, и та же функция объявлена без [[optimize_for_synchronized]] в другой единице трансляции, программа имеет неправильный формат; диагностика не требуется.

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

std::atomic<bool> rehash{false};
 
// поток обслуживания запускает этот цикл
void maintenance_thread(void*) {
    while (!shutdown) {
        synchronized {
            if (rehash) {
                hash.rehash();
                rehash = false;
            }
        }
    }
}
 
// рабочие потоки каждую секунду выполняют сотни тысяч вызовов этой функции.
// Вызовы insert_key() из синхронизированных блоков в других единицах
// трансляции вызовут сериализацию этих блоков, если insert_key()
// не отмечен [[optimize_for_synchronized]]
[[optimize_for_synchronized]] void insert_key(char* key, char* value) {
  bool concern = hash.insert(key, value);
  if (concern) rehash = true;
}

GCC ассемблер без атрибута: вся функция сериализуется

insert_key(char*, char*):
	subq	$8, %rsp
	movq	%rsi, %rdx
	movq	%rdi, %rsi
	movl	$hash, %edi
	call	Hash::insert(char*, char*)
	testb	%al, %al
	je	.L20
	movb	$1, rehash(%rip)
	mfence
.L20:
	addq	$8, %rsp
	ret

GCC ассемблер с атрибутом:

transaction clone for insert_key(char*, char*):
	subq	$8, %rsp
	movq	%rsi, %rdx
	movq	%rdi, %rsi
	movl	$hash, %edi
	call	transaction clone for Hash::insert(char*, char*)
	testb	%al, %al
	je	.L27
	xorl	%edi, %edi
	call	_ITM_changeTransactionMode # Примечание: это точка сериализации
	movb	$1, rehash(%rip)
	mfence
.L27:
	addq	$8, %rsp
	ret

[править] Примечания

[править] Поддержка компиляторами

Эта техническая спецификация поддерживается GCC начиная с версии 6.1 (для включения требуется -fgnu-tm). Более старый вариант этой спецификации поддерживался GCC с версии 4.7.