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

Question

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

Эти задачи

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

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

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