🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
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 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 ведь её недостаточно чтобы писать высокопроизводительные программы. В следующих постах разберемся с этим подробнее. Ваши идеи и соображения что не так с кодом выше буду ждать в комментариях😊
На этом все, спасибо что дочитали до конца, до встречи!
