​​Порядок взятия замков. Ч2
#опытным

Так в каком же порядке блокируются мьютексы в std::scoped_lock? Как я уже и говорил - в неопределенном. Но и здесь можно немного раскрыть детали.

The objects are locked by an unspecified series of calls to lock, try_lock, and unlock.

Mutex-like объекты блочатся недетерминированной серией вызовов методов lock(), unlock() и try_lock().

Алгоритм можно представить некой игрой в поддавки. Мы пытаемся поочереди захватить мьютексы. И если на каком-то из какой-то из них занят, то мы не ждем, пока он освободится. Мы освобождаем все свои мьютексы, давая возможность другим потокам их захватить, и после этого начинаем пытаться захватывать замки заново.

Зачем так сложно?

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

При запуске кода из предыдущего поста вы можете увидеть вот такую картину(но не гарантирую):

128616222426688 Lock at address 0x56aef94a31e0 is acquired.
128616222426688 Try lock at address 0x56aef94a3220. Success
128616222426688 Try lock at address 0x56aef94a3260. Failed
128616222426688 Lock at address 0x56aef94a3220 is released.
128616222426688 Lock at address 0x56aef94a31e0 is released.
128616222426688 Lock at address 0x56aef94a31e0 is acquired.
128616222426688 Try lock at address 0x56aef94a3220. Success
128616222426688 Try lock at address 0x56aef94a3260. Failed
128616222426688 Lock at address 0x56aef94a3220 is released.
128616211940928 Lock at address 0x56aef94a3260 is acquired.
128616211940928 Try lock at address 0x56aef94a3220. Success
128616211940928 Try lock at address 0x56aef94a31e0. Success

Надо понимать, что это многопоточка и каких-то упорядоченных логов между потоками быть не может, поэтому надо немного напрячь извилины.

(0x56aef94a31e0 - первый мьютекс, 0x56aef94a3220 - второй, 0x56aef94a3260 - третий)

Смотрим. Поток 128616222426688 локает первый замок, пытается локнуть второй и делает это успешно, а вот третий не получается. Значит он освобождает свои два и пытается начать заново. Дальше видим такую же картину - на третьем мьютексе try_lock прошел неудачно -> освобождаем имеющиеся.

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

То есть поток 128616222426688 пожертвовал своими захваченными замками в пользу потока 128616211940928.

Вот так выглядит реализация функции std::lock(которая лежит под капотом std::scoped_lock) в gcc:

template<typename _L1, typename _L2, typename... _L3>
void lock(_L1& __l1, _L2& __l2, _L3&... __l3)
{
#if __cplusplus >= 201703L
  if constexpr (is_same_v<_L1, _L2> && (is_same_v<_L1, _L3> && ...))
  {
    constexpr int _Np = 2 + sizeof...(_L3);
    unique_lock<_L1> __locks[] = {
      {__l1, defer_lock}, {__l2, defer_lock}, {__l3, defer_lock}...
    };
    int __first = 0;
    do {
      __locks[__first].lock();
      for (int __j = 1; __j < _Np; ++__j)
      {
        const int __idx = (__first + __j) % _Np;
        if (!__locks[__idx].try_lock())
        {
          for (int __k = __j; __k != 0; --__k)
          __locks[(__first + __k - 1) % _Np].unlock();
          __first = __idx;
          break;
        }
      }
    } while (!__locks[__first].owns_lock()); 
    for (auto& __l : __locks)
      __l.release();
  }
  else
#endif
  {
    int __i = 0;
    __detail::__lock_impl(__i, 0, __l1, __l2, __l3...);
  }
}

Кто сможет - разберется, но что тут происходит в сущности - я описал выше.

Give something up to get something else. Stay cool.

#concurrency #cpp17

Почему не используют стратегию блокировки по адресам?
#опытным

Точного ответа от разработчиков стандартной библиотеки мы не услышим, но я приведу некоторые рассуждения, которые могут натолкнуть на некоторые мысли.

Начнем с того, что локать один мьютекс - это норма. Все так делают, никто от этого не помер.

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

А именно это и происходит при вызове метода lock(). Поток мытается захватить мьютекс и если не получается - блокируется до того момента, пока мьютекс не освободится.

Поэтому любая схема с последовательным вызовом методов lock() будет подвержена дедлокам.

А в схеме с упорядоченным по адресам блокировкой именно так и происходит.

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

А что если в одном потоке замки будут лочиться через scoped_lock по адресной схеме, а в другом потоке - одиночно?

            1 поток            |            2 поток              |
-------------------------------|---------------------------------|
 lock(mutex2) // УСПЕШНО       |                                 |
                               | scoped_lock()                   |
                               |    lock(mutex1) // УСПЕШНО      |
                               |    lock(mutex2) // ОЖИДАНИЕ ... |
 lock(mutex1) // ОЖИДАНИЕ...   |                                 |

В этом случае настанет дедлок. Спасибо за пример Сергею Борисову.

Ну или другую ситуацию рассмотрим: есть 4 замка l1, l2, l3, l4. Поток захватил замок с самым большим адресом l4 и надолго(потенциально навсегда) заблокировался.
Но другие треды продолжают нормально работать. И они иногда захватывают пары мьютексов. Все продолжается нормально, пока один из потоков не пытается залочить l3 и l4. Из-за ордеринга захватится l3, а дальше поток будет ждать освобождения l4 aka заблокируется. Дальше другой поток будет пытаться захватить l2 и l3. Он захватит l2 и будет дожидаться l3.

Логику можно продолжать и дальше. Таким образом из-за одного мьютекса и немного поломанного потока может остановиться вся программа.

std::mutex l1, l2, l3, l4;
// Пусть я как-то гарантирую, что они пронумерованы в порядке
 возрастания адресов и std::scoped_lock(sc_lock для краткости) 
работает с помощью сортировки по адресам

1 поток      |     2 поток    |     3 поток    |       4 поток       
-------------|----------------|----------------|----------------
 l4.lock();  |                |                |
//blocks here|                |                |
             |sc_lock(l3, l4);|                |
             | // lock l3     |                |
             | // blocks on l4|                |
                              |sc_lock(l2, l3);|
                              | // lock l2     |
                              | // blocks on l3|
                              |                | sc_lock(l1, l2);
                                               | // lock l1      
                                               | // blocks on l2

Примеры немного преувеличены, но тем не менее они говорят о том, что схема с адресами не совсем безопасна.

Так может тогда вообще не будем блокироваться при уже захваченном мьютексе? Именно это и делают в реализации стандартной библиотеки. Первый захват мьютекса происходит через обычный lock(), а остальные мьютексы пытаются заблокировать через try_lock. Можно сказать, что это lock-free взятие замка. Если мьютекс можно захватить - захватываем, если нет, то не блокируемся и дальше продолжаем исполнение. Так вот в случае, если хотя бы один try_lock для оставшихся замков вернул false, то реализация освобождает все захваченные замки и начинает попытку снова.

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

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#concurrency

​​Еще один способ залочить много мьютексов

Последний пост из серии.

Вот у мьютекса есть метод lock, который его захватывает. А разработчики stdlib взяли и сделали функцию std::lock, которая лочит сразу несколько замков.

Также у мьютекса есть метод try_lock, который пытается в неблокирующем режиме его захватить. "Авось да получится". И видимо по аналогии с lock в стандартной библиотеке существует свободная функция std::try_lock, которая пытается захватить несколько мьютексов так же в неблокирующем режиме.

template< class Lockable1, class Lockable2, class... LockableN >  
int try_lock( Lockable1& lock1, Lockable2& lock2, LockableN&... lockn );

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

Чтобы с помощью std::try_lock наверняка захватить все замки, нужно крутиться в горячем цикле и постоянно вызывать std::try_lock, пока она не вернет -1.

Непонятно, зачем эта функция нужна в прикладном программировании при наличии std::scoped_lock и std::lock, которые еще и удобно оборачивают все эти циклы, скрывая все эти кишки в деталях реализации.

Единственное, что пришло в голову - реализация своего scoped_lock'а с блэкджеком и другим алгоритмом предотвращения дедлока. Этот алгоритм должен быть чем-то похож на поддавки, но как-то изменен. У кого есть кейсы применения - отпишитесь в комменты.

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

Stay useful. Stay cool.

#concurrency

​​std::jthread

С std::thread в С++ есть один интересный и возможно назойливый нюанс. Давайте посмотрим на код:

int main()
{
  std::thread thr{[]{ std::cout << "Hello, World!" << std::endl;}};
}

Простой Хелло Ворлд в другом потоке. Но при запуске программы она тут же завершится примерно с таким сообщением: terminate called without an active exception.

Эм. "Я же просто хотел быть счастливым вывести в другом потоке сообщение. Неужели просто так не работает?"

В плюсах много чего просто так не работает)

А вот такая программа:

int main()
{
  std::thread thr{[]{ std::cout << "Hello, World!" << std::endl;}};
  std::this_thread::sleep_for(std::chrono::seconds(1));
}

Все-таки напечатает Hello, World!, но потом все равно завершится с std::terminate.

Уже лучше, но осадочек остался. Ничего не понятно. Давайте разбираться.

С помощью слипа мы немного затормозили main тред и сообщение появилось. То есть мы оттянули выход из main и завершение программы и дали возможность подольше поработать новосозданному потоку. А что происходит при выходе из скоупа функции? Вызов деструкторов локальных объектов.

Так вот в деструкторе единственного локального объекта и проблема. Согласно документации, для каждого потока мы обязательно должны выбрать одну из 2-х стратегий поведения: отсоединить его от родительского потока или дождаться его завершения. Делается это методами detach и join соответственно.

И если мы не вызовем один из этих методов для объекта потока, то в своем деструкторе он вызовет std::terminate. То есть корректный код выглядит так:

int main()
{
  std::thread thr{[]{ std::cout << "Hello, World!" << std::endl;}};
  thr.join();
}

Мы дожидаемся конца исполнения потока и только после этого завершаем программу. Теперь никаких терминаторов.

Но зачем эти формальности? Вообще говоря, часто мы хотим присоединить поток почти сразу перед вызовом его деструктора. А вот отсоединяем поток мы почти сразу после создания объекта. Мы же заранее знаем, хотим ли мы отпустить поток в свободное плавание или нет. И, учитывая эти факты, было бы приятно иметь возможность не вызывать join самостоятельно, а чтобы он за нас вызывался в деструкторе.

И С++20 приходит здесь нам на помощь с помощью std::jthread. Он делает ровно это. Если его не освободили и не присоединили мануально, то он присоединяется в деструкторе.

Поэтому такой код сделает то, что мы ожидаем:

int main()
{
  std::jthread thr{[]{ std::cout << "Hello, World!" << std::endl;}};
}

jthread не только этим хорош. Его исполнение можно еще отменять/приостанавливать. Но об этом уже в другой раз.

Кстати. Вопрос на засыпку. Слышал, что там какие-то сложности у кланга с jthread были. Сейчас все нормально работает?

Make life easier. Stay cool.

#cpp20 #concurrency

RAII обертки мьютекса
#новичкам

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

Для начала - для работы с мьютексами нужны обертки. Очень некрасиво в наше время использовать чистые вызовы lock и unlock. Это наплевательское отношение к современному и безопасному(посмеемся) С++.

Здесь прямая аналогия с выделением памяти. Для каждого new нужно вызывать соответствующий delete. Чтобы случайно не забыть этого сделать(а в большом объеме кода что-то забыть вообще не проблема), используют умные указатели. Это классы, используя концепцию Resource Acquisition Is Initialization, помогают нам автоматически освобождать ресурсы, когда они нам более не нужны.

Также для каждого lock нужно вызвать unlock. Так может по аналогии сделаем класс, который в конструкторе будет лочить мьютекс, а в деструкторе - разблокировать его?

Хорошая новость в том, что это уже сделали за нас. И таких классов даже несколько. Если не уходить в специфическую функциональность, то их всего 2. Это std::lock_guard и std::unique_lock.

lock_guard - базовая и самая простая обертка. В конструкторе лочим, в деструкторе разлачиваем. И все. Больше ничего мы с ним делать не можем. Мы можем только создать объект и удалить его. Даже получить доступ к самому мьютексу нельзя. Очень лаконичный и безопасный интерфейс. Но и юзкейсы его применения довольно ограничены. Нужна простая критическая секция. Обезопасил и идешь дальше.

bool MapInsertSafe(std::unordered_map<Key, Value>& map, const Key& key, Value value) {
    std::lock_guard lck(mtx);
    if (auto it = map.find(key))
        return false;
    else {
        it->second = std::move(value);
        return true;
    }
}

unique_lock же больше походит на std::unique_ptr. Уже можно получить доступ в объекты, поменяться содержимым с другим объектом unique_lock, поменять нижележащий объект на другой. Ну и раз мы все равно даем возможность пользователю получить доступ к нижележащему объекту, то удобно вынести в публичный интерфейс unique_lock те же методы, которыми можно управлять самим мьютексом. То есть lock, unlock, try_lock и тд - это часть интерфейса std::unique_lock.

Уже понятно, что этот вид обертки нужно использовать в более сложных случаях, когда функциональности lock_guard не хватает.

А в основном не хватает возможности использовать методы lock и unlock. Например, при работе в кондварами std::unique_lock просто необходим. Читатель заходит в критическую секцию, локает замок и затем видит, что определенные условия еще не наступили. Допустим еще нет данных для чтения. В такой ситуации надо отпустить мьютекс и заснуть до лучших времен. А при пробуждении и наступлении подходящих условий, опять залочить замок и начать делать работу.

void worker_thread()
{
    std::unique_lock lk(m);
    cv.wait(lk, []{ return ready; });
  // process data
    lk.unlock();
}

Кондвар в методе wait при ложном условии вызывает unlock у unique_lock. При пробуждении и правдивом условии вызывает lock и ждет освобождения мьютекса.

Юзкейсы можно обсуждать очень долго, но вывод один: всегда используйте обертки над мьютексами! Возможно, они спасут вашу жизнь.

А уж какую обертку использовать подскажет сама задача.

Stay safe. Stay cool.

#concurrency

Еще один плюс RAII
#опытным

Основная мотивации использования raii - вам не нужно думать об освобождении ресурсов. Мол ручное управление ресурсами небезопасно, так как можно забыть освободить их и вообще не всегда понятно, когда это нужно делать.

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

Это такие противные малявки, которые прерывают нормальное выполнение программы в исключительных ситуациях. Так вот вы рассчитываете на "нормальное выполнение программы" и, исходя из этого, расставляете освобождения. А тут бац! И программа просто не доходит до нужной строчки.

std::shared_ptr<Value> DB::SelectWithCache(const Key& key) {
    mtx_.lock();
    if (auto it = cache.find(key); it != cache_.end()) {
        mtx_.unlock();
        return it->second;
    } else {
        std::shared_ptr<Value> result = Select(key);
        cache.insert({key, result});
        mtx_.unlock();
        return result;
    }
}

Простой код запроса к базе с кэшом. Что будет в том случае, если метод Select бросит исключение? unlock никогда не вызовется и мьютекс коннектора к базе будет навсегда залочен! Это очень печально, потому что ни один поток больше не сможет получить доступ к критической секции. Даже может произойти deadlock текущего потока, если он еще раз попытается захватить этот мьютекс. А это очень вероятно, потому что на запросы к базе скорее всего есть ретраи.

Мы могли бы сделать обработку исключений и руками разлочить замок:

std::shared_ptr<Value> DB::SelectWithCache(const Key& key) {
    try {
        mtx_.lock();
        if (auto it = cache.find(key); it != cache_.end()) {
            mtx_.unlock();
            return it->second;
        } else {
            std::shared_ptr<Value> result = Select(key);
            cache.insert({key, result});
            mtx_.unlock();
            return result;
        }
    }
    catch (...) {
        Log("Caught an exception");
        mtx_.unlock();
    }
}

Однако самое обидное, что исключения, связанные с работой с базой, мы даже обработать не может внутри метода SelectWithCache. Это просто не его компетенция и код сверху некорректен с этой точки зрения.

А снаружи метода объекта мы уже не сможем разблокировать мьютекс при обработке исключения, потому что это приватное поле.

Выход один - использовать RAII.

std::shared_ptr<Value> DB::SelectWithCache(const Key& key) {
    std::lock_guard lg{mtx_};
    if (auto it = cache.find(key); it != cache_.end()) {
        return it->second;
    } else {
        std::shared_ptr<Value> result = Select(key);
        cache.insert({key, result});
        return result;
    }
}

При захвате исключения происходит раскрутка стека и вызов деструкторов локальных объектов. Это значит, что в любом случае вызовется деструктор lg и мьютекс освободится.

Спасибо Михаилу за идею)

Stay safe. Stay cool.

#cpp11 #concurrency #cppcore #goodpractice

​​Потокобезопасный интерфейс
#новичкам

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

Возьмем максимально простую реализацию самой простой очереди:

struct Queue {
    void push(int value) {
        storage.push_back(value);
    }
    void pop() {
        storage.pop_front();
    }
    bool empty() {
        return storage.empty();
    }
    int& front() {
        return storage.front();
    }
private:
    std::deque<int> storage;
};

Она конечно потокоНЕбезопасная. То есть ей можно адекватно пользоваться только в рамках одного потока.

Как может выглядеть код простого консьюмера этой очереди?

while(condition)
    if (!queue.empty()) {
        auto & elem = queue.front();
        process_elem(elem);
        queue.pop();
    }

И вот мы захотели разделить обязанности производителя чисел и их потребителя между разными потокам. Значит, нам надо как-то защищать очередь от многопоточных неприятностей.

Бабахаем везде лок гард на один мьютекс и дело в шляпе!

struct Queue {
    void push(int value) {
        std::lock_guard lg{m};
        storage.push_back(value);
    }
    void pop() {
        std::lock_guard lg{m};
        storage.pop_front();
    }
    bool empty() {
        std::lock_guard lg{m};
        return storage.empty();
    }
    int& front() {
        std::lock_guard lg{m};
        return storage.front();
    }
private:
    std::deque<int> storage;
    std::mutex m;
};

Все доступы к очереди защищены. Но спасло ли реально это нас?

Вернемся к коду консюмера:

while(true)
    if (!queue.empty()) {
        auto & elem = queue.front();
        process_elem(elem);
        queue.pop();
  }

А вдруг у нас появится еще один консюмер? Тогда в первом из них мы можем войти условие, а в это время второй достанет последний элемент. Получается, что мы получим доступ к неинициализированной памяти в методе front.

То есть по факту в многопоточном приложении полученный стейт сущности сразу же утрачивает свою актуальность.

Что делать? Не только сами методы класса должны быть потокобезопасными. Но еще и комбинации использования этих методов тоже должны обладать таким свойством. И с данным интерфейсом это сделать просто невозможно.

Если стейт утрачивает актуальность, то мы вообще не должны давать возможность приложению получать стейт очереди. Нам нужны только команды управления. То есть push и pop.

struct ThreadSafeQueue {
    void push(int value) {
        std::lock_guard lg{m};
        storage.push_back(value);
    }
    std::optional<int> pop() {
        std::lock_guard lg{m};
        if (!storage.empty()) {
            int elem = storage.front();
            storage.pop_front();
            return elem;
        }
        return nullopt;
    }
private:
    std::deque<int> storage;
    std::mutex m;
};

Внутри метода pop мы можем использовать проверять и получать стейт очереди, так как мы оградились локом. Возвращаем из него std::optional, который будет хранить фронтальный элемент, если очередь была непуста. В обратном случае он будет пуст.

Теперь консюмер выглядит так:

while(true) {
    auto elem = queue.pop();
    if (elem)
        process_elem(elem.value());
}

Можно конечно было использовать кондвары и прочее. Но я хотел сфокусироваться именно на интерфейсе. Теперь реализация просто не позволяет получать пользователю потенциально неактульные данные.

Stay safe. Stay cool.

#concurrency #design #goodpractice

Ответ
#опытным

Правильный ответ на квиз из предыдущего поста- 0. Вообще ни одного мьютекса не нужно.
Много можно вариантов придумать. И даже в комментах написали несколько рабочих способов.

Вообще говоря, в определении дедлока не звучит слово "мьютекс". Потоки должны ждать освобождения ресурсов. А этими ресурсами может быть что угодно.
Для организации дедлока достаточно просто, чтобы 2 потока запустились в попытке присоединить друг друга. Естественно, что они будут бесконечно ждать окончания работы своего визави.

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

Заметьте, что мы пытаемся сделать грязь. Так давайте же применим самые опасные вещи из плюсов и у нас все получится! Надо лишь добавить 50 грамм указателей и чайную ложку глобальных переменных. Получается вот такая каша:

std::thread * t_ptr = nullptr;

void func1() {
  std::this_thread::sleep_for(std::chrono::seconds(1));
  t_ptr->join();
  std::cout << "Never reached this point1" << std::endl;
}

void func2(std::thread& t) {
  t.join();
  std::cout << "Never reached this point2" << std::endl;
}

int main() {
  std::thread t1{func1};
  t_ptr = new std::thread(func2, std::ref(t1));
  while(true) {
    std::this_thread::sleep_for(std::chrono::seconds(1));
  }
}

Все просто. Вводим глобальный указатель на поток. В функции первого потока мы даем время инициализировать указатель и присоединяем поток по указателю. А тем временем в main создаем динамический объект потока и записываем его по указателю t_ptr. Таким образом первый поток получает доступ ко второму. В функцию второго потока передаем объект первого потока по ссылке и присоединяем его. Обе функции после инструкции join выводят на консоль запись.

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

И действительно. При запуске программы ничего не выводится. Более того, пока писался этот пост, программа работала и ничего так и не вывела. Учитывая, что потоки особо ничего не делают, то логично предположить, что ситуация и не поменяется.

Естественно, что потоков может быть больше и кольцо из ожидающих потоков может быть больше. Но это такой минимальный пример.

Если вы думаете, что это какая-то сова в вакууме, то подумайте еще раз. Владение потоками можно передавать в функции. Могут быть довольно сложные схемы организации взаимодействия потоков. И если вы присоединяете поток не в его родителе, то возникает благоприятные условия для возникновения такого безлокового дедлока.

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

Stay surprised. Stay cool.

#concurrency #cppcore

​​Дедлокаем один поток
#опытным

Мы привыкли, что для дедлоков нужно несколько потоков. Не удивительно. Давайте прочитаем определение дедлока по Коффману. Там речь про процессы, но если поменять слово "процесс" на "поток" ничего не изменится. Ну и перевод будет вольный.

Дедлок - это ситуация в коде, когда одновременно выполняются все следующие условия:

А ну, мальчики, играем поочереди. Только один поток может получить доступ к ресурсу в один момент времени.

У меня уже есть красный паровозик, но я хочу синий!. Поток в настоящее время хранит по крайней мере один ресурс и запрашивает дополнительные ресурсы, которые хранятся в других потоках.

Я тебя захватил, я тебя и отпущу. Ресурс может быть освобожден только добровольно потоком, удерживающим его.

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

Судя по этому определению, минимальное количество потоков, чтобы накодить дедлок - 2.

Но это такая общая теория работы с многозадачностью в программах.

Определение оперирует общим термином ресурс. И не учитывает поведение конкретного ресурса и деталей его реализации. А они важны!

Возьмем пресловутый мьютекс. Что произойдет, если я попытаюсь его залочить дважды в одном потоке?

std::mutex mtx;
mtx.lock();
mtx.lock();

Стандарт говорит, что будет UB. То есть поведение программы неопределено, возможно она заставит Ким Чен Ира спеть гангам стайл.

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

1️⃣ Компилятор имплементировал умный мьютекс, который может задетектить double lock и, например, кинуть в этом случае исключение.

2️⃣ Мьютекс у нас обычный, подтуповатый и он делает ровно то, что ему говорят. А именно пытается залочить мьютекс. Конечно у него ничего не получится и он вечно будет ждать его освобождения. Результат такого сценария - дедлок одного потока одним мьютексом!

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

Be self-sufficient. Stay cool.

#concurrency #cppcore #compiler

std::exchange
#опытным

В прошлом посте мы пасхалкой использовали std::exchange, давайте же разберем эту функцию по-подробнее.

По названию в целом понятно, что она делает - что-то обменивает. Но не как std::swap, меняет значения местами. Все немного хитрее.

Она заменяет старое значение новым и возвращает старое значение. Вот примерная реализация:

template<class T, class U = T>
constexpr // Since C++20
T exchange(T& obj, U&& new_value) {
    T old_value = std::move(obj);
    obj = std::forward<U>(new_value);
    return old_value;
}

Как говорил Константин Владимиров: "единожды научившись использовать std::exchange, вы дальше будете делать std::exchange всю оставшуюся жизнь".

Понятное дело, что это не какой-нибудь std::move, который реально постоянно приходится использовать. Однако важен сам паттерн. Если посмотреть в кодовые базы, то будет куча мест, где можно использовать эту функцию. Приведу пару примеров работы std::exchange, чтобы вы поняли смысл.

Начнем со знакомого:

auto gen = [current = start, step]() mutable {
  return std::exchange(current, current + step);
};

std::vector<int> numbers(5);
std::generate(numbers.begin(), numbers.end(), gen);

Мы определяем мутабельную лямбду(кстати это один из удачных примеров использования таких лямбд), которая может изменять свои захваченные по значению переменные current и step. Дальше на каждом вызове мы должны вернуть текущее значение current, но перед этим как-то его увеличить. Можно использовать прокси-переменную:

int val = current;
current += step;
return val;

Но зачем, если у нас уже есть готовая и протестированная функция std::exchange? Это прекрасный способ немного уменьшить код и увеличить его читаемость.

Другой пример - генерация чисел Фибоначчи:

auto gen = [current = 0, next = 1]() mutable {
  return current = std::exchange(next, current + next);
};

std::vector<int> fib(10);
std::generate(fib.begin(), fib.end(), gen);
for (int i = 0; i < fib.size(); ++i) {
  std::cout << fib[i] << " ";
}
// OUTPUT:
// 1 1 2 3 5 8 13 21 34 55 

Хорошенько вдумайтесь и осознайте, что здесь происходит. Ну ведь красиво, правда?)

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

class Dispatcher {
    // ...

    // All events are dispatched when we call process
    void process() {
        const auto tmp = [&] {
            std::lock_guard lock{mutex_};
            return std::exchange(callbacks_, {});
        }();
        for (const auto& callback : tmp) {
            std::invoke(callback);
        }
    }
};

И все. Копию(на самом деле перемещенную копию) получаем под локом, а обрабатываем все без замков. Круто!

Ну и конечно, без принципа exchange не обойтись в lock-free программировании. Та же std::atomic_exchange работает ровно по той же логике.

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

Be elegant. Stay cool.

#cppcore #cpp14 #concurrency #fun

Volatile
#опытным

Ключевое слово, которое не embedded С++ разработчик вряд ли когда-нибудь встречал в код. Сегодня мы поговорим, для чего оно используется.

Предположим, что у нас есть переменная keyboard_press, память под которую замаплена на память устройства ввода-вывода. Когда нажимается кнопка клавиатуры, изменяется переменная keyboard_press. Оставим сам маппинг за скобками и попробуем написать какую-то детсадовскую логику с переменной keyboard_press:

int keyboard_press = 0;
size_t count_test = 0;

void some_function() {
  while(keyboard_press == 0) {
    count_test++;
  }
  // doing stuff
}

Что в ассемблере?

some_function():
  mov eax, DWORD PTR keyboard_press[rip]
  test eax, eax
  jne .L1
.L3: // это кстати пустой бесконечный цикл, куда нельзя попасть и откуда нельзя выбраться
  jmp .L3
.L1:
  ret
count_test:
  .zero 8
keyboard_press:
  .zero 4

А где цикл? А где инкремент count_test?

На самом деле код собран с -О3 и компилятор просто выкинул цикл. Он не видит, что в данном коде где-то еще изменяется keyboard_press, поэтому разумно полагает, что мы написали бесконечный цикл без сайдэффектов, который вообще-то ub.

Но keyboard_press может изменяться, просто это никак не понятно по коду программы.

Теоретически компилятор мог бы увидеть, что мы замапили устройство ввода-вывода на эту переменную. А может и не увидеть. Если маппинг происходит в другой единице трансляции, то точно не увидит. Компилятор технически не может знать всего, что творится в коде. Он оптимизирует какой-то локальный участок кода на основе своих эвристик, которые просто не могут учитывать весь код программы.

Однако компилятор точно видит тип переменной. И на него мы можем повлиять. Вот чтобы отучить компилятор от таких фокусов, нужно пометить keyboard_press ключевым словом volatile.

volatile int keyboard_press = 0;
size_t count_test = 0;

// same

Теперь ассемблер выглядит так:

some_function():
  mov eax, DWORD PTR keyboard_press[rip]
  test eax, eax
  jne .L1
  mov rax, QWORD PTR count_test[rip]
  add rax, 1
.L3:
  mov edx, DWORD PTR keyboard_press[rip]
  mov rcx, rax
  add rax, 1
  test edx, edx
  je .L3
  mov QWORD PTR count_test[rip], rcx
.L1:
  ret

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

Говорится ли здесь что-нибудь о потоках? Нет! Здесь говорится только об оптимизациях компилятора.

Поэтому использовать volatile можно только для обработки сигналов(хэндлер которых вызывается в том же прерванном потоке), либо в тех местах, где вы работаете с переменной строго в одном потоке.

Доступ к volatile переменным не атомарный + с их помощью нельзя делать синхронизацию неатомарных переменных между потоками, так как volitile не подразумевает барьеров памяти.

Именно из-за этих ограничений volatile используется в очень узком спектре задач работы с I/O. Во всех остальных случаях в С++ используются атомики.

Don't be optimized out. Stay cool.

#cppcore #concurrency #memory

Отличия volatile от std::atomic
#опытным

Кратко пробежимся по особенностям volatile переменных и атомиков, чтобы было side-by-side сравнение.

volatile переменные:

- Компилятору запрещается выкидывать операции над volatile переменными. Грубо говоря, компилятору запрещается "запоминать" значение таких переменных и он обязан их каждый раз читать из памяти.

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

- Физически это значит, что volatile переменные запрещается кэшировать в регистрах и их всегда нужно честно читать из памяти.

- Запрещается реордеринг операций volatile переменных с другими операциями с видимыми спец-эффектами, расположенных выше и ниже по коду.

- Любой другой реордеринг разрешен.

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

- Запись и чтение volatile переменных не связаны между собой отношением synchronized-with, поэтому на их основе нельзя выстроить межпотоковое отношение happens-before. А это значит, что по стандарту С++ доступ к volatile переменной из разных потоков - это гонка данных и ub.


std::atomic:

- Операции над атомиками - это также видимые спецэффекты, только ситуация немного другая. Запись в атомике и других переменных, синхронизируемые атомиком, становятся видимыми сайд эффектами только для потоков, которые прочитают последнюю запись в атомик.

- По сути, если компилятор докажет, что поток будет всегда читать одно и то же значение атомика, то он может его закэшировать. Если ваш код только читает из memory mapped io, то компилятор теоритически может выкинуть чтение и заменить заранее вычисленным значением. Поэтому атомик нельзя использовать, как замену volatile.

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

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

- Запись и чтение атомиков связаны между собой отношением synchronized-with, поэтому на их основе можно построить межпотоковое отношение happens-before. Это значит, что по стандарту операции непосредственно над атомарными переменными не могут приводить к гонке данных.

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

Про атомики можно говорить еще долго, но эти разговоры уже будут сильно оторваны от volitile. В этом посте хотелось бы сравнить их, чтобы можно быть проследить отличия по одним и тем же характеристикам.

Compare things. Stay cool.

#cppcore #cpp11 #concurrency

​​data race
#новичкам

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

Начнем с data race. Это по сути единственная категория, которая четко определена в стандарте С++.

Скажем, что два обращения к памяти конфликтуют, если:

- они обращаются к одной и той же ячейке памяти.
- по крайней мере одно из обращений - запись.

Так вот гонкой данных называется 2 конфликтующих обращения к неатомарной переменной, между которыми не возникло отношение порядка "Произошло-Раньше".

Если не вдаваться в семантику отношений порядков, то отсутствие синхронизации с помощью примитивов(мьютексов и атомиков) при доступе к неатомикам карается гонкой данных и неопределененным поведением.

Простой пример:

int a = 0;

void thread_1() {
  for (int i = 0; i < 10000; ++i) {
    ++a;
  }
}

void thread_2() {
  for (int i = 0; i < 10000; ++i) {
    ++a;
  }
}

std::jthread thr1{thread_1};
std::jthread thr1{thread_2};
std::cout << a << std::endl;

В двух потоках пытаемся инкрементировать a. Проблема в том, что при выводе на консоль a не будет равна 20000, а скорее всего чуть меньшему числу. Инкремент инта - это неатомарная операция над неатомиком, поэтому 2 потока за счет отсутствия синхронизации кэшей будут читать и записывать неактуальные данные.

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

Have an order. Stay cool.

#cppcore #concurrency

race condition
#новичкам

Теперь состояние гонки. Это более общее понятие, чем гонка данных. Это ситуация в программе, когда поведение системы зависит от относительного порядка выполнения операций в потоках.

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

Но нам и не важно это предсказание, потому что имеет значение поведение всей программы целиком.

Проблемы возникают, когда такие спорадические эффекты приводят к некорректным результатам. И именно эти ситуации обычно называют состоянием гонки. Мне кажется важным проговорить, что потоки всегда в состоянии гонки за чем-то и в этом отражение недетерминированности многопоточной среды. Но далее буду употреблять "состояние гонки" в негативном контексте.

Проблемы из-за состояния гонки могут происходить даже в программах без гонки данных.

Например:

std::atomic<int> x = 2;

void thread_1() {
  x = 3;
}

void thread_2() {
  if (x % 2 == 0) {
    std::cout << x << std::endl;
  }
}

Может так произойти, что поток 1 выполнится в промежутке между условием и выводом x на консоль. Это очень маловероятная ситуация, однако на консоль может вывестись нечетное число 3 с учетом того, что перед выводом мы проверили на четность. Как минимум удивительный результат, хотя с программе нет гонки данных.

Состояние гонки - это в основном ошибка проектирования в условиях многопоточности. Знаменитая проблема наличия метода size() у многопоточной очереди - состояние гонки:

template <typename T>
class ThreadSafeQueue {
...
  size_t size() {
    std::lock_guard lg{mtx_};
    return queue_.size();
  }
private:
  std::deque<T> queue_;
  ...
};


ThreadSafeQueue<int> queue;
...
if (queue.size() > 0) {
  auto item = std::move(queue.front());
  queue.pop();
  // process item
}

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

Основные черты состояния гонки:

🙈 Наличие логической ошибки при проектировании системы

🙈 Зависимость от планирования потоков

🙈 Зависимость от времени выполнения операции. Вчера в чате скинули мем, иллюстрирующий эту зависимость.

Многие путают или не понимают разницы между race condition и data race. Это даже частый вопрос на собеседованиях, на который 50% кандидатов отвечают что-то вообще невнятное. Но теперь вы подготовлены и вооружены правильным словарным аппаратом.

Be independent of other's schedule. Stay cool.

#design #concurrency #interview

​​Deadlock
#новичкам

Еще одна частая проблема из мира многопоточки. На канале уже много материалов про нее есть:

Определение и демонстрация

Начало серии статей про блокировку нескольких мьютексов, что часто приводит к дедлоку

Сколько нужно мьютексов, чтобы задедлокать 2 потока?

Что будет, если 2 раза подряд залочить мьютекс?

Но это все для чуть более опытных ребят. Что если вы совсем не понимаете эти потоки и мьютексы на практике, но очень хотите понять, что такое дедлок?

Есть знаменитая проблема обедающих философов. Формулируется она так:

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

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

Каждый философ может взять ближайшую вилку (если она доступна) или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

Вопрос задачи заключается в том, чтобы разработать модель поведения, при которой ни один из философов не будет голодать, то есть будет вечно чередовать приём пищи и размышления.

В рамках этой проблемы можно продемонстрировать много проблем многопоточки, но сегодня о deadlock.

Представьте 5 философов по кругу. И у них стратегия - брать всегда первой левую вилку, а затем правую.

Что получится, если все философы одновременно возьмут левую вилку?

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

Это классический deadlock и наглядная его демонстрация. Вот так просто.

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

Как будто бы про дедлоки больше и не о чем писать. Если хотите разобрать какой-то их аспект - черканите в комментах.

Be unblockable. Stay cool.

#concurrency

Лайвлок
#новичкам

Лайвлок(livelock) — это ситуация в многопоточном программировании, когда потоки не блокируются полностью, как при дедлоке, а продолжают выполняться, но не могут продвинуться в решении задачи из-за постоянной реакции на действия друг друга.

Потоки находятся в состоянии "живой блокировки" — они активны, cpu жжется, но их работа не приводит ни к какому прогрессу.

Лайвлоки не всегда приводят к вечной блокировке потоков. Просто в какие-то рандомные моменты времени условный rps может неконтролируемо вырасти в разы, а то и на порядки.

И так как ситуация сильно зависит от планирования потоков, то воспроизвести ее будет сложно.

Однако у этой проблемы есть характерные черты, облегчающие ее поиск:

🔍 Активное ожидание — потоки постоянно проверяют какие-то условия и крутятся в циклах.
🔍 Взаимозависимость — действия одного потока влияют на условия выполнения другого.
🔍 Неблокирующие алгоритмы - активное ожидание обычно идет за ручку с lockfree алгоритмами.
🔍 Поддавки - при потенциальном конфликте интересов стороны предпочитают уступать.

Аналогия из реальной жизни: вы идете по узкому тротуару и вам навстречу идет человек. Вы хотите разминуться, но отшагиваете вместе в одну и ту же сторону. И вы, как крабики, ходите вместе из стороны в сторону. Рано или поздно вы разойдетесь, но заранее нельзя сказать когда.

К лайвлоку может привести и использование стандартных инструментов. Например, std::scoped_lock, который предназначен для безопасной блокировки нескольких мьютексов. Стандарт требует, чтобы его реализация не приводила к дедлоку. Они используют неопределенную последовательность вызовов методов lock(), try_lock() и unlock(), которая гарантирует отсутствие дедлока. Но не гарантирует отсутствия лайвлока. Алгоритм там примерно такой: попробуй заблокировать столько мьютексов, сколько можешь, а если не получилось, то освободи их и попробуй сначала. Тут есть и циклы, и активное ожидание, и взаимозависимость, и поддавки.

Но компиляторы понимают эту проблему и современные реализации используют разные приемы, типа экспоненциального backoff'а, чтобы все-таки рано или поздно дать шанс одному из потоков полностью захватить все ресурсы.

Вот более "надежный" пример:

std::atomic<bool> lock1 = false;
std::atomic<bool> lock2 = false;

void thread1_work() {
    while (true) {
        // lock lock1
        while (lock1.exchange(true))
            ;
        std::cout << "Thread 1 has acquired lock1, try to acquire lock2..."
                  << std::endl;
        // try to lock lock2
        if (!lock2.exchange(true)) {
            std::cout << "Thread 1 has acquired both locks!" << std::endl;
            lock2 = false;
            lock1 = false;
            break;
        } else {
            // Failed, release lock1 and try again
            std::cout << "Thread 1 failed to acquire lock2, release lock1..."
                      << std::endl;
            lock1 = false;
        }
    }
}

void thread2_work() {
    while (true) {
        // lock lock2
        while (lock2.exchange(true))
            ;
        std::cout << "Thread 2 has acquired lock2, try to acquire lock1..."
                  << std::endl;
        // try to lock lock1
        if (!lock1.exchange(true)) {
            std::cout << "Thread 2 has acquired both locks!" << std::endl;
            lock1 = false;
            lock2 = false;
            break;
        } else {
            // Failed, release lock2 and try again
            std::cout << "Thread 2 failed to acquire lock1, release lock2..."
                      << std::endl;
            lock2 = false;
        }
    }
}

int main() {
    std::jthread t1(thread1_work);
    std::jthread t2(thread2_work);
}

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

Unlock your life. Stay cool.

#concurrency

Contention
#опытным

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

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

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

И вот тут может появиться проблема. Один ресурс, а желающих завладеть им слишком много. Только один в итоге овладевает, а все остальные отправляются спать. И это конечно приводит к простою потоков и замедление общего прогресса.

template <Key, Value>
class ThreadSafeMap {
    mutable std::mutex mtx;
    std::map<Key, Value> map;

public:
    void Insert(const Key &key, const Value &value) {
        std::lock_guard lg{mtx};
        map.insert(key, value);
    }
    Value &Get(const Key &key) const {
        std::lock_guard lg{mtx};
        return map.at(key);
    }
};

Если к такой мапе одновременно будет получать доступ куча потоков, то все кроме одного будут простаивать. А если таких потоков 10 или 20? Неприятненько.

Как можно снизить Contention?

👉🏿 Read-Write Lock. Если у вас много читателе и мало писателей, то можно разрешить нескольким читателям одновременно получать доступ к данным с помощью std::shared_mutex:

template <Key, Value>
class ThreadSafeMap {
    mutable std::shared_mutex mtx;
    std::map<Key, Value> map;

public:
    void Insert(const Key &key, const Value &value) {
        std::unique_lock ul{mtx};
        map.insert(key, value);
    }
    Value &Get(const Key &key) const {
        std::shared_lock sl{mtx};
        return map.at(key);
    }
};

👉🏿 Thread-Local Storage. Потоки пишут данные в свои локальные буферы, которые централизованно синхронизируют данные друг с другом, чтобы как можно меньше блокировать потоки.

👉🏿 Можно организовать свою структуру данных так, чтобы у нее была ячеистая структура и к каждой ячейке был отдельный замок. Теперь потребители данных распределятся по разным ячейкам и не будут толкаться.

template <Key, Value>
class FineGrainedMap {
    struct Node {
        std::mutex mtx;
        std::map<Key, Value> data;
    };
    std::vector<Node> buckets{16};  // Много мелких блокировок
    
public:
    Value& Get(const Key& key) const {
        auto& bucket = buckets[std::hash<Key>{}(key) % buckets.size()];
        std::lock_guard lock(bucket.mtx);
        return bucket.data.at(key);
    }
};

👉🏿 Используйте lock-free структуры данных. Ну как бы тут логично: нет мьютексов, нет и сontention. Не в каждой задаче это реально применить, но иногда все же можно.

Compete and win. Stay cool.

#concurrency

​​Starvation
#опытным

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

Итого, вы ждете своей очереди, но всегда появляется кто-то важнее вас, который влезает перед вами. А вы продолжаете ждать. Потенциально до окончания приема и полного обугливания жопы.

Эта сцена наглядно демонстрирует еще одну проблему многопоточного мира - starvation или голодание.

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

Какие предпосылки появления голодания?

👉🏿 Приоритеты потоков. Хоть в стандарте С++ нельзя выставить приоритет потоков, это можно сделать, например, в pthreads. Потоки с большим приоритетом могут забирать всю работу у низкоприоритетных.

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

👉🏿 Все хотят доступ к одному ресурсу. Когда много потоков пытаются получить доступ к ресурсу, охраняемому всего одним мьютексом, то полезную работу делает только один из них, а все остальные ждут.

👉🏿 Длинные задачи под мьютексом. В дополнение к предыдущему пункту. Мало того, что потоки просто долго ждут очереди, чтобы занять замок, так еще и каждый из них вечность делает свою задачу.

Простой пример:

std::mutex mtx;
int counter = 0;

void worker(int id) {
    for (int i = 0; i < 100; ++i) {
        std::lock_guard lg{mtx};
        ++counter;
        std::cout << "Thread " << id
                  << " entered critical section, counter = " << counter
                  << std::endl;
        // do work
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

int main() {
    std::jthread t1(worker, 1);
    std::jthread t2(worker, 2);
}

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

Но! Если вы добавите слип после релиза мьютекса, то картина становится более справедливой.

Как избавиться от голодания?

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

✅ Минимальный размер критической секции. Она должна менеждить хранение задачи, но не быть ответственной за выполненеие задачи. Это позволит ограничивать простой других потоков.

✅ Грамотно проектируйте разделяемые данные. Если у вас 100 потоков пинают одну несчастную потокобезопасную мапу, то есть высока вероятность пересмотреть архитектуру и межпоточное взаимодействие.

✅ Давайте возможность другим войти в критическую секцию. Учитывая второй пункт, поток, который постоянно стучится в критическую секцию, скорее всего выполняет в ней лишний код. Разгрузите секцию, займите поток чем-нибудь в перерывах между критическими секциями и будет вам счастье.

Remember that you have the highest priority. Stay cool.

#concurrency

Голодание. Приоритетные очереди
#опытным

Голодание бывает не только у потоков, но и у других сущностей с приоритетами.

Допустим у вас есть система задач с 3-мя приоритетами: High, Medium, Low. Продюсеры кладут каждую задачу в очередь, соответствующую ее приоритету. А консюмеры всегда должны потреблять задачи с самым высоким возможным приоритетом.

То есть, пока High очередь не опустеет, никто не будет брать Middle задачи. И никто не возьмет в обработку Low задачи, пока High и Middle очереди не пусты.

Может возникнуть такая ситуация, при которой задачи High будут постоянно приходить так, что обработчики редко будут брать задачи Middle и никогда не дойдут до Low очереди. Таким образом, эти очереди будут голодать от недостатка обработки.

class Scheduler {
private:
    std::vector<ThreadSafeQueue<std::string>> queues;
    std::vector<std::string> priority_names;

public:
    Scheduler() : queues(3), priority_names{"HIGH", "MEDIUM", "LOW"} {}

    std::string Get() {
        while(true) {
            for(int i = 0; i < queues.size(); ++i) {
                auto task = queues[i].take();
                if (!task)
                    continue;
                std::cout << "Get task " << priority_names[i] << ": " << task << std::endl;
                return task;
            }
            // some kind of waiting mechanism in case of every queue is full
            }
    }

    void AddTask(int priority, const std::string& task) {
        queues[priority].push(task);
        std::cout << "Add task " << priority_names[priority] << ": " << task << std::endl;
    }
};

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

Кстати сам алгоритм называется Fixed-priority pre-emptive scheduling. В каждый момент времени выполняется задача с самым высоким приоритетом.

Решение проблемы - сменить алгоритм взятия задач из очередей.

Например, можно установить правило, что вы обрабатываете не более f(priority) элементов в любой данной очереди, прежде чем рассматривать элементы из очереди с более низким приоритетом.

Функция f может быть:

👉🏿 Линейной: f(p) = p. Обрабатывается не более 4 элементов с приоритетом 4 (высший), затем не более 3 с приоритетом 3,..., 1 с приоритетом 1.

👉🏿 Экспоненциальной: f(p) = 2^(p-1). Обрабатывается не более 8 элементов с приоритетом 4 (высший), затем не более 4 с приоритетом 3, затем не более 2 с приоритетом 2,..., 1 с приоритетом 1.

Конкретная функция выбирается из ожидаемой частоты появления задач

Возьмем экспоненциальный случай и предположим, что в каждой очереди много ожидающих задач. Мы планируем: 8 высших, 4 высоких, 2 средних, 1 низкий, 8 высших и т.д... Каждый цикл содержит 8 + 4 + 2 + 1 = 15 задач, поэтому задачи высшего приоритета занимают 8/15 времени потребителя, следующие — 4/15, следующие — 2/15, следующие — 1/15.

Сравниваем эти частоты с ожидаемыми и корректируем коэффициенты или используем другую функцию.

You are the highest priority. Stay cool.

#concurrency

​​Тулзы для поиска проблем многопоточности
#опытным

Мы уже с вами убедились, что в мире многопоточности куча проблем. И шанс на них наткнуться, мягко говоря, немаленький. А на самом деле почти любой мало-мальски полезный конкурентный код, написаный с нуля, будет содержать как минимум одну такую проблему.

А уж если она есть, то просто так вы от нее не отвяжитесь. Это же многопоточность, тут нет места детерминизму. На одной машине все работает, а на другой - зависает. Поэтому очень важно применять полный спектр инструментов для валидации многопоточного кода, как нам и говорят кор гайдлайны. Перечислим некоторые известные инструменты, которые могут помочь.

✅ Юнит тесты. Код без тестов - деньги на ветер. Это я перефразировал известную поговорку, но она и в данном контексте хорошо отражает суть. Если вы не тестируете код, то проблема может проявиться в самый неподходящий момент и это может стоить вам кучу зеленых фантиков.

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

✅ Cppcheck. Пользуйтесь инструментами статического анализа, например Cppcheck. Определять проблемы синхронизации по коду программы - занятие конечно увлекательное и вряд ли вы много багов так найдете, но собственно почему бы и нет.

Надо лишь установить сам cppcheck, а запускается он просто:

cppcheck --enable=all --inconclusive thread_app.cpp

✅ Thread San. Без динамического анализа в многопоточке никуда. ThreadSanitizer - это детектор гонок данных для C/C++. Санитайзер определяет гонку ровно как в стандарте: если у вас много потоков получают доступ к ячейке памяти и хотя бы один из них - несинхронизированная запись. И это же и является принципом детектирования гонок.

Работает на GCC и Clang. Достаточно лишь при сборке указать нужные флаги и ждать прилета сообщений о багах:

clang++ -fsanitize=thread -g -O2 -o my_app main.cpp

g++ -fsanitize=thread -g -O2 -o my_app main.cpp

✅ Helgrind. Это одна из тулзов Valgrind'а, работающая конкретно с багами многопоточности. Достаточно при запуске валгринда указать --tool=helgrind и ждите писем счастья. Главное, чтобы ваши примитивы синхронизации использовали под капотом pthread.

Helgrind детектирует такие проблемы, как:
- разблокировка невалидного мьютекса
- разблокировка не заблокированного мьютекса
- разблокировка мьютекса, удерживаемого другим потоком
- уничтожение невалидного или заблокированного мьютекса
- рекурсивная блокировка нерекурсивного мьютекса
- освобождение памяти, содержащей заблокированный мьютекс
и еще кучу всего.

✅ Vtune. Не все проблемы конкурентности связаны с некорректным использованием инструментов. С точки зрения стандартов, программа может корректно работать, но в ней будут лайв локи или голодовки. Тогда нужен хороший профилировщик, способный отследить, например, влияние lock contention на общую производительность, неэффективную синхронизацию или неравномерную нагрузку между потоками.

vtune -collect threading -result-dir my_analysis ./my_application

VTune в принципе очень мощный профилировщик даже не касательно многопоточности. Если есть возможность заморочится с ним, то это стоит сделать.

Test your system. Stay cool.

#concurrency #tools