Concurrency and Consistency. Non-blocking, lock-free and async. Пост №4. Obstruction-free или Гарантия отсутствия препятствий.

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

Гарантию obstruction-free легче всего начать объяснять на примере кода, который мы все хотя бы раз в жизни писали - thread-safe структура данных закрытая мьютексом, например мой любимый счетчик:

std::mutex m;
int shared_value = 0;

void increment() {
    m.lock();          // (*)
    shared_value++;    // долгая критическая секция
    m.lock();
}

Потоков N, где N > 1. Соответствует ли код obstruction-free? Нет, не соответствует.

Вспоминаем как у нас работает ОС. У нас есть планировщик который может остановить выполнение программы в любой момент, чтобы дать ресурс кому то еще. И теперь ситуация:
- Поток №1 захватывает мьютекс и его сразу же усыпляет ОС чтобы разбудить поток №2
- Поток №2 проснулся, пытается тоже сделать increment, но терпит неудачу, так как сосед уже захватил мьютекс.
- Поток №2 после нескольких попыток засыпает потерпев неудачу.

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

———

Еще ситуация, "работаем в криптовалюте" переводим виртуальные денежки между счетами, естественно с гарантиями отсутствия потерь и дублирования:

struct Account { std::atomic<int> version; int balance; };

void transfer(Account& from, Account& to, int amount) {
    while (true) {
        int v1 = from.version.load();
        int v2 = to.version.load();

        int newFromBalance = from.balance - amount;
        int newToBalance    = to.balance + amount;

        if (from.version.compare_exchange_strong(v1, v1 + 1)) {
            if (to.version.compare_exchange_strong(v2, v2 + 1)) {
                from.balance = newFromBalance;
                to.balance   = newToBalance;
                return; // успех
            }
            from.version.store(v1);
        }
    }
}

Здесь ситуация отличается значительно. Если у нас несколько потоков, но работает только один - мы всегда будем достигать прогресса, так как у нас нет конкурентов за значения атомарных переменных. CAS операции всегда будут успешны и больше одной итерации в цикле нам не грозит. Такой код соответствует гарантии obstruction-free. Но обольщаться рано, не зря в быту обычно все упоминают lock-free а не obstruction-free ведь её недостаточно чтобы писать высокопроизводительные программы. В следующих постах разберемся с этим подробнее. Ваши идеи и соображения что не так с кодом выше буду ждать в комментариях😊

На этом все, спасибо что дочитали до конца, до встречи!