Блог

Проблема

Резюме: Параллельное применение функции F к каждому элементу массива, где F НЕ является потокобезопасным.

У меня есть набор элементов E для обработки, скажем, их очередь. Я хочу обрабатывать все эти элементы параллельно, используя одну и ту же функцию f(E ) .

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

• Каждый элемент содержит пару из 2 объектов.( E = (A,B) )
• Два элемента могут совместно использовать объект. ( E1 = (A1, B1); E2 = (A1, B2))
• Функция f не может обрабатывать два элемента, которые совместно используют объект. таким образом, E1 и E2 не могут обрабатываться параллельно.

Каков правильный способ сделать это?

Мои мысли таковы,

1. тривиальная мысль: сохраните набор активных As и Bs и начинайте обработку элемента только тогда, когда ни один другой поток уже не использует A ИЛИ B.
   • Итак, когда вы передаете элемент потоку, вы добавляете As и Bs в активный набор.
   • Выберите первый элемент, если его элементов нет в активном наборе, создайте новый поток, в противном случае переместите его в конец очереди элементов.
   • Делайте это, пока очередь не опустеет.
   • Приведет ли это к взаимоблокировке? В идеале, когда обработка завершена, некоторые элементы станут доступными, верно?

2. -Другая мысль состоит в том, чтобы составить график этих связанных объектов. Каждый узел представляет объект (A / B) . Каждый элемент представляет собой ребро, соединяющее A и B, а затем каким-то образом обрабатывает данные таким образом, чтобы мы знали, что элементы никогда не перекрываются.

Вопросы

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

Здесь «Лучший» подход зависит от множества факторов:

1. Сколько элементов «E» у вас есть и сколько работы требуется для f (E). —> Проверьте, действительно ли стоит работать с элементами параллельно (если вам нужно много блокировок и у вас мало работы, вы, вероятно, замедлите процесс, работая параллельно)
2. Есть ли какая-либо возможность изменить дизайн, который может сделать f (E) многопоточность безопасной?
3. Сколько элементов «A» и «B» существует? Есть ли какая-либо логика, по которой элементы «E» совместно используют определенные версии A и B? —> Если вы можете отсортировать элементы E в отдельные списки, где каждый A и B отображаются только в одном списке, то вы можете обрабатывать эти списки параллельно без какой-либо дальнейшей блокировки.
4. Если существует много разных A и B, и вы не используете слишком много из них, вы можете использовать тривиальный подход, при котором вы просто блокируете каждый «A» и «B» при вводе и ждете, пока не получите блокировку.

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

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

1. поток 1 блокирует
2. поток 2 блокирует B
3. поток 1 пытается заблокировать B и завершается неудачно
4. поток 2 пытается заблокировать A и завершается неудачно
5. поток 1 снимает блокировку A
6. поток 2 снимает блокировку B
7. Переходим к 1 и повторяем…

Вероятность того, что это действительно происходит «бесконечно», относительно невелика, но в любом случае этого следует избегать

Редактировать 2: в принципе, я думаю, я бы просто разделил E (Ax, Bx) на разные списки на основе Ax (например, один список для всех E, которые имеют один и тот же A). Затем обрабатывайте эти списки параллельно с блокировкой «B» (там вы все еще можете «попробовать заблокировать» и продолжить, если требуемый B уже используется.