В рамках поддержки формы и необходимости размяться перед серьезным поиском работы я походил по разным собеседованиям и надо сказать, вопросы по многопоточности в связке с С++ на них стали появляться. Очень редко по сравнению с количеством вопросов по сортировке гномиков и прочей ересью, но тем не менее за этот год я столкнулся аж с 2 вопросами из этой области в компаниях, которые активно используют C++11 и выше. Что удивительно, некоторые до сих пор сидят на С++98, а то и на вообще Си-с-классами.
Первый и самый простой вопрос был посвящен порядку блокировки мьютексов. К примеру, у нас есть несколько объектов над которыми нужно провести некую атомарную операцию параллельно из разных потоков. В качестве иллюстрации обычно используют несколько банковских аккаунтов над которыми нужно провести разные операции.
В данном случае всё довольно просто, так как единственное правило это – блокировка объектов должна всегда происходить в одном и том же порядке. Такой подход к блокировке можно организовать двумя разными способами:
1. При помощи функции std::lock, если количество объектов участвующих в блокировке заранее известно. Функция
2. Ввести некий признак позволяющий определить какой из мьютексов “больше” и всегда блокировать мьютексы от большего к меньшему (или от меньшего к большему, главное всегда в одном и том же порядке), что позволит избежать взаимной блокировки. В случае с примером с банковскими аккаунтами, в роли такого атрибута может выступать номер счета.
Второй вопрос чуть более интересный. Как распараллелить сортировку слиянием? Возьмем наивную сортировку слиянием для иллюстрации:
void merge_sort( It begin, It end )
{
auto len = std::distance( begin, end );
if( len <= 1 )
return;
auto middle = begin + len / 2;
auto left = std::vector<T>( begin, middle );
auto right = std::vector<T>( middle, end );
merge_sort( left.begin(), left.end() );
merge_sort( right.begin(), right.end() );
std::merge( left.begin(), left.end(), right.begin(), right.end(), begin );
}
Параллелить слияние можно, но довольно сложно и в общем случае это выходит за рамки собеседования, но можно довольно легко и быстро распараллелить разделение на подмассивы:
std::thread tr( merge_sort<It>, right.begin(), right.end() );
tl.join();
tr.join();
При этом в варианте приведенном выше есть как минимум две проблемы:
1. При возникновении не обработанного исключения в функции
2. При сколь-нибудь серьезном размере сортируемых данных количество запущенных потоков перекроет все плюсы распараллеливания.
Поэтому:
if( threads_remaining > 0 )
{
threads_remaining -= 2;
policy = std::launch::async;
}
auto fl = std::async( policy, merge_sort<It>, left.begin(), left.end() );
auto fr = std::async( policy, merge_sort<It>, right.begin(), right.end() );
fl.get();
fr.get();
Получить максимальное количество одновременно выполняемых потоков можно через std::hardware_concurrency, а при возникновении исключения
Не густо, конечно, но тенденция есть. Думаю к C++2x начнут активнее интересоваться многопоточностью