Стратегии и методы блокировки для предотвращения тупиков в коде

Question

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

Например, для заданных потоков T1 и T2, где T1 обращается к ресурсу A, а затем B и T2 обращается к ресурсу B, а затем A. Блокировка ресурсов в том порядке, в котором они необходимы, вызывает взаимную блокировку. Простое решение состоит в том, чтобы заблокировать A, а затем заблокировать B, независимо от того, какой конкретный порядок потока будет использовать ресурсы.

Проблемная ситуация:

Thread1                         Thread2
-------                         -------
Lock Resource A                 Lock Resource B
 Do Resource A thing...          Do Resource B thing...
Lock Resource B                 Lock Resource A
 Do Resource B thing...          Do Resource A thing...

Возможное решение:

Thread1                         Thread2
-------                         -------
Lock Resource A                 Lock Resource A
Lock Resource B                 Lock Resource B
 Do Resource A thing...          Do Resource B thing...
 Do Resource B thing...          Do Resource A thing...

У меня вопрос: какие еще методы, шаблоны или обычные практики используются в кодировании, чтобы гарантировать предотвращение блокировки?

Answer 1

Техника, которую вы описываете, не просто распространена: это единственная техника, которая доказала свою эффективность постоянно.Есть несколько других правил, которым вы должны следовать при кодировании многопоточного кода в C ++, однако наиболее важными из них могут быть:

• не удерживать блокировку при вызове виртуальной функции : даже если во время написания кода вы знаете, какая функция будет вызываться и что она будет делать, код эволюционирует, и виртуальные функции должны быть переопределены, так что в конечном итоге вы не будете знать, что он делает и будет ли он использовать другие блокировки, то есть вы потеряете гарантированный порядок блокировки
• следите за условиями гонки : в C ++ вам ничего не сообщат, когдаданный поток данных распределяется между потоками, и вы не используете какую-либо синхронизацию для него.Один из примеров этого был опубликован Люком в C ++ Lounge на SO-чате несколько дней назад, как пример этого (код в конце этого поста): просто пытаюсь синхронизировать что-то else , котороеслучается, что в окрестности не означает, что ваш код правильно синхронизирован.
• попытайтесь скрыть асинхронное поведение : вы обычно лучше скрываете свой параллелизм в своемархитектура программного обеспечения, такая, что большинству вызывающего кода все равно, есть ли там поток или нет.Это облегчает работу с архитектурой - особенно для тех, кто не привык к параллелизму.

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

Более общий совет:

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

Следующий код не выполнится:

#include <thread>
#include <cassert>
#include <chrono>
#include <iostream>
#include <mutex>

void
nothing_could_possibly_go_wrong()
{
    int flag = 0;

    std::condition_variable cond;
    std::mutex mutex;
    int done = 0;
    typedef std::unique_lock<std::mutex> lock;

    auto const f = [&]
    {
        if(flag == 0) ++flag;
        lock l(mutex);
        ++done;
        cond.notify_one();
    };
    std::thread threads[2] = {
        std::thread(f),
        std::thread(f)
    };
    threads[0].join();
    threads[1].join();

    lock l(mutex);
    cond.wait(l, [done] { return done == 2; });

    // surely this can't fail!
    assert( flag == 1 );
}

int
main()
{
    for(;;) nothing_could_possibly_go_wrong();
}

Answer 2

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

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

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

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

Answer 3

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

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

Упрощенная отправная точка для чтения по теме: Транзакционная память .

Answer 4

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

• Классифицировать каждую функцию (метод) как блокирующий , неблокирующий или имеющий неизвестное поведение блокировки.
• A блокирование функция - это функция, которая получает блокировку или вызывает медленный системный вызов (что на практике означает, что она выполняет ввод / вывод), или вызывает блокирующую функцию .
• Функция гарантированно неблокируемая является частью спецификации этой функции, так же как и ее предварительные условия и степень безопасности исключений.Поэтому он должен быть задокументирован как таковой.В Java я использую аннотацию;в C ++, задокументированном с использованием Doxygen, я бы использовал формальную фразу в комментарии заголовка для функции.
• Рассмотрим вызов функции, которая не указана , чтобы быть неблокирующей, удерживая блокировку длябыть опасным.
• Переформулировать такой опасный код, чтобы устранить опасность или сконцентрировать опасность в небольшой части кода (возможно, в рамках своей собственной функции).
• Для оставшегося опасного кода предоставьтенеофициальное доказательство того, что код на самом деле не опасен в комментарии к коду.

Answer 5

Несмотря на то, что вы не упомянули упомянутое решение с известной последовательностью, Андрей Александреску написал о некоторых методах проверки времени компиляции, что получение блокировок осуществляется с помощью предполагаемых механизмов. Смотри http://www.informit.com/articles/article.aspx?p=25298