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

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

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

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

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

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

Синхронизированные блоки

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

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

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

#include <iostream>
#include <thread>
#include <vector>
 
int f()
{
    static int i = 0;
    synchronized { // begin synchronized block
        std::cout << i << " -> ";
        ++i;       // each call to f() obtains a unique value of i
        std::cout << i << '\n';
        return i;  // end synchronized block
    }
}
 
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 (это ошибка времени компиляции).

// each call to f() retrieves a unique value of i, even when done in parallel
int f()
{
    static int i = 0;
    atomic_noexcept { // begin transaction
//  printf("before %d\n", i); // error: cannot call a non transaction-safe function
        ++i;
        return i; // commit transaction
    }
}

Выход из атомного блока любым способом, кроме исключения (достижение конца, 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: not volatile
    p = &x;     // ok: the pointer is not volatile
    int i = *p; // error: read through volatile glvalue
    S s;        // error: invocation of unsafe destructor
}

int f(int x) { // implicitly transaction-safe
    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};
 
// maintenance thread runs this loop
void maintenance_thread(void*)
{
    while (!shutdown)
    {
        synchronized
        {
            if (rehash)
            {
                hash.rehash();
                rehash = false;
            }
        }
    }
}
 
// worker threads execute hundreds of thousands of calls to this function 
// every second. Calls to insert_key() from synchronized blocks in other
// translation units will cause those blocks to serialize, unless insert_key()
// is marked [[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 # Note: this is the serialization point
        movb        $1, rehash(%rip)
        mfence
.L27:
        addq        $8, %rsp
        ret

Примечания

Поддержка компилятора

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