Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Важно также, что обращение к get_tail()производится под защитой захваченного мьютекса head_mutex. Если бы это было не так, то между вызовом get_tail()и захватом head_mutexмог бы вклиниться вызов pop_head(), потому что другой поток вызвал try_pop()(и, следовательно, pop_head()) и захватил мьютекс первым, не давая первому потоку продолжить исполнение:

│ Эта реализация

std: :unique_ptr pop_head()←┘ некорректна

{ (1) Старое значение tail

│ получено не

node* const old_tail = get_tail();←┘ под защитой head_mutex

std::lock_guard head_lock(head_mutex);

if (head.get() == old_tail) ← (2)

return nullptr;

}

std::unique_ptr old_head = std::move(head);

head = std::move(old_head->next);← (3)

return old_head;

}

При такой — некорректной — реализации в случае, когда get_tail() (1)вызывается вне области действия блокировки, может оказаться, что и head, и tailизменились к моменту, когда первому потоку удалось захватить head_mutex, и теперь возвращенный хвост мало того что больше не является хвостом, но и вообще не принадлежит списку. Тогда сравнение headс old_tail (2)не прошло бы, хотя headв действительности является последним узлом. Следовательно, после обновления (3)узел headмог бы оказаться в списке дальше tail, то есть за концом списка, что полностью разрушило бы структуру данных. В корректной реализации, показанной в листинге 6.6, вызов get_tail()производится под защитой head_mutex. Это означает, что больше никакой поток не сможет изменить head, a tailбудет только отодвигаться от начала списка (по мере добавления новых узлов с помощью push()) — это вполне безопасно. Указатель headникогда не сможет оказаться дальше значения, возвращенного get_tail(), так что инварианты соблюдаются.

После того как pop_head()удалит узел из очереди, обновив head, мьютекс освобождается, и try_pop()может извлечь данные и удалить узел, если таковой был (или вернуть NULL-экземпляр класса std::shared_ptr<>, если узла не было), твердо зная, что она работает в единственном потоке, который имеет доступ к этому узлу.

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

Вопрос об исключениях более интересен. Поскольку мы изменили порядок выделения памяти, исключения могут возникать в других местах. Единственные операции в try_pop(), способные возбудить исключение, — это захваты мьютексов, но пока мьютексы не захвачены, данные не модифицируются. Поэтому try_pop()безопасна относительно исключений. С другой стороны, push()выделяет из кучи память для объектов Tи node, и каждая такая операция может возбудить исключение. Однако оба вновь созданных объекта присваиваются интеллектуальным указателям, поэтому в случае исключения память корректно освобождается. После того как мьютекс захвачен, ни одна из последующих операций внутри push()не может возбудить исключение, так что мы снова в безопасности.

Поскольку мы не изменяли интерфейс, то новых внешних возможностей для взаимоблокировки не возникло. Внутренних возможностей также нет; единственное место, где захватываются два мьютекса, — это функция pop_head(), но она всегда захватывает сначала head_mutex, а потом tail_mutex, так что взаимоблокировки не случится.

Осталось рассмотреть только один вопрос — в какой мере возможно распараллеливание. Эта структура данных предоставляет куда больше таких возможностей, чем приведенная в листинге 6.2, потому что гранулярность блокировок мельче, и больше работы выполняется не под защитой блокировок . Например, в push()память для нового узла и нового элемента данных выделяется, когда ни одна блокировка не удерживается. Это означает, что несколько потоков могут спокойно выделять новые узлы и элементы данных в одно и то же время. В каждый момент времени только один поток может добавлять новый узел в список, но выполняющий это действие код сводится к нескольким простым присваиваниям указателей, так что блокировка удерживается совсем недолго по сравнению с реализацией на основе std::queue<>, где мьютекс остается захваченным в течение всего времени, пока выполняются операции выделения памяти внутри std::queue<>.