Одновременный доступ к группам объектов

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

Эти задачи

  • получить доступ к заранее определенному набору объектов;
  • должен «атомарно» получить разрешения на чтение/запись для всех объектов, к которым он обращается, перед фактическим запуском;
  • после завершения (и гарантированно в конечном итоге закончится) отпустите объекты, которые они приобрели.

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

Однако этот метод увеличивает вероятность зависания задач с большими объектными зависимостями и даже может привести к активным блокировкам.

Есть ли другой способ получить набор блокировок при максимальном параллелизме? (без глобальной блокировки) Или, возможно, изменить систему так, чтобы она больше не требовалась? Если да, то какие-нибудь хорошие документы об этом?

ps: Как ответил Титон, это обобщенная версия проблемы «обедающих философов». Я ищу нецентрализованные решения, в частности алгоритмы, хорошо справляющиеся с высокой нагрузкой (добавление и удаление задач).


scheduled-tasks concurrency scheduling mutual-exclusion
person João Rafael    schedule 01.08.2011    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Ваша проблема называется Обедающие философы. По этому ключевому слову вы должны найти любое количество необходимой вам литературы :-).

person thiton    schedule 02.08.2011
comment
Я вспомнил! наиболее точно это обобщенная проблема обедающих философов без ограничения на 2 вилки на философа. - person João Rafael; 02.08.2011

arrow_upward
1
arrow_downward

Заказ ресурсов — правильный подход. Еще один простой подход, который приходит на ум, — ввести общий арбитр, содержащий информацию о доступности ресурсов. Задачи будут блокировать все необходимые им ресурсы через арбитра за один атомарный шаг «получить (r1, r2, ..., rn)» и освободить их аналогичным образом с помощью «release (r1, r2, ..., rn)».

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

Арбитр может использовать несколько стратегий для удовлетворения входящих запросов:

  1. Отклонить запрос, который не может быть немедленно удовлетворен - задачи придется повторить. Это открывает дверь к живым замкам и голодной смерти.
  2. Держите все входящие запросы в очереди и обслуживайте их в порядке FIFO по мере того, как ресурсы, необходимые для запроса в голове, становятся доступными.
  3. Храните все неудовлетворенные запросы в списке (не блокируя требуемые ресурсы) и перебирайте их (возможно, с приоритетом для более старых запросов) каждый раз, когда некоторые ресурсы освобождаются, чтобы найти запрос, который может быть удовлетворен.
person Vaclav Pech    schedule 02.08.2011
comment
Это верное решение. Однако, поскольку есть один арбитр, все задачи должны ожидать в очереди блокировки арбитра, что вызывает конкуренцию. Кроме того, поток для проверки возможных параллельных задач выполняется в одном потоке, что ограничивает максимальный параллелизм. - person João Rafael; 02.08.2011
comment
Теперь, думая о вашем очень правильном комментарии, я бы, вероятно, разработал такую ​​систему арбитров таким образом, чтобы арбитр работал не с потоками, а с задачами. Блокировка задачи (фрагмента работы) при ожидании ресурса, скорее всего, окажет гораздо меньшее влияние на пропускную способность по сравнению с блокировкой потоков. только распределять ресурсы по задачам и - person Vaclav Pech; 02.08.2011
comment
(продолжение) Арбитр постепенно считывал задачи, назначал им запрошенные ресурсы и выплевывал те, которые получили все ресурсы, в пул потоков для обработки. При условии, что задачи выполняются некоторое время, однопоточный арбитр не может стать узким местом. - person Vaclav Pech; 02.08.2011
comment
Думаю, все дело в размере задачи. Как я представляю систему, эти задачи будут очень небольшими, возможно, порядка тысячи циклов процессора. Вот почему я прошу децентрализованный алгоритм. Возможно, я реализую оба и посмотрю, что работает лучше. - person João Rafael; 03.08.2011

arrow_upward
0
arrow_downward

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

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

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

person MRAB    schedule 01.08.2011
comment
Теоретически эти задачи выполняются очень быстро, и большую часть времени потоки будут пытаться определить задачу для запуска. Использование глобальной блокировки усугубит проблему, потому что процесс принятия решения будет выполняться одним потоком, а не распределенным. - person João Rafael; 02.08.2011