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

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

Эти задачи

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

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

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

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

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

Источник

3 ответа

Решение

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

Источник

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

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

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

  1. Отклонить запрос, который не может быть немедленно удовлетворен - задачи придется повторить. Это открывает двери для живых замков и голода.
  2. Храните все входящие запросы в очереди и обслуживайте их в порядке FIFO, когда станут доступны ресурсы, необходимые для запроса.
  3. Храните все неудовлетворенные запросы в списке (не блокируя их требуемые ресурсы) и просматривайте их (возможно, с приоритетом для более старых запросов) каждый раз, когда освобождаются некоторые ресурсы, чтобы найти запрос, который можно удовлетворить.
Источник

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

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

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

Источник
Другие вопросы по тегам