Теория и практика параллельных вычислений
Проблема взаимоблокировки
Возможный подход для получения однозначных результатов (уход от состязания потоков) может состоять в ограничении доступа к узлам сетки, которые обрабатываются в параллельных потоках программы. Для этого можно ввести набор замков row_lock[N], который позволит потокам закрывать доступ к "своим" строкам сетки.
// поток обрабатывает i строку сетки omp_set_lock(row_lock[i]); omp_set_lock(row_lock[i+1]); omp_set_lock(row_lock[i-1]); // обработка i строки сетки omp_unset_lock(row_lock[i]); omp_unset_lock(row_lock[i+1]); omp_unset_lock(row_lock[i-1]);
Закрыв доступ к своим данным, параллельный поток уже не будет зависеть от динамики выполнения других параллельных участков программы. Результат вычислений потока однозначно определяется значениями данных в момент начала расчетов.
Данный подход позволяет продемонстрировать еще одну проблему, которая может возникать в ходе параллельных вычислений. Эта проблема состоит в том, что при организации доступа к множественным общим переменным может появляться конфликт между параллельными потоками и этот конфликт не может быть разрешен успешно. Так, в приведенном фрагменте программного кода при обработке потоками двух последовательных строк (например, строк 1 и 2) может сложиться ситуация, когда потоки блокируют сначала строки 1 и 2 и только затем переходят к блокировке оставшихся строк (см. рис. 11.6). В этом случае доступ к необходимым строкам не может быть обеспечен ни для одного потока – возникает неразрешимая ситуация, обычно именуемая тупиком. Как можно показать, необходимым условием тупика является наличие цикла в графе распределения и запросов ресурсов. В рассматриваемом примере уход от цикла может состоять в строго последовательной схеме блокировки строк потока.
// поток обрабатывает i строку сетки omp_set_lock(row_lock[i+1]); omp_set_lock(row_lock[i]); omp_set_lock(row_lock[i-1]); // <обработка i строки сетки> omp_unset_lock(row_lock[i+1]); omp_unset_lock(row_lock[i]); omp_unset_lock(row_lock[i-1]);
(следует отметить, что и эта схема блокировки строк может оказаться тупиковой, если рассматривать модифицированную задачу Дирихле, в которой горизонтальные границы являются "склеенными").
Рис. 11.6. Ситуация тупика при доступе к строкам сетки (поток 1 владеет строкой 1 и запрашивает строку 2, поток 2 владеет строкой 2 и запрашивает строку 1)
