Мой вопрос заключается в том, какие примитивы синхронизации я должен использовать здесь.
Существует множество объектов синхронизации, которые можно использовать для защиты очереди и любых других общих объектов от скачек данных. Среди них выделяются мьютексы и семафоры, но есть и другие.
Однако, поскольку одна из возможностей заключается в том, что поток должен приостановить работу, пока не будет выполнено условие (становится доступной задача нового цвета, или задача выполнена) вам нужна переменная условия. Переменные условия обязательно используются вместе с мьютексами, при этом естественным признаком является то, что мьютекс защищает (как минимум) общие данные, к которым необходимо получить доступ для оценки условия. Таким образом, «один мьютекс и одна условная переменная» - хороший ответ на поставленный вопрос.
Но вы, похоже, также не уверены, как структурировать очередь и как использовать примитивы синхронизации. Это конкретно c для вашего конкретного проекта, но можно сделать некоторые общие замечания и предложения. Ваше объяснение кейса в реальном мире предполагает, что значения цвета по существу произвольны, а не взяты из небольшого фиксированного словаря. Это исключает выделение отдельного потока каждому цвету, вместо этого вы попадаете в ситуацию, когда в любой момент времени каждый свободный поток является жизнеспособным для выполнения каждой задачи, которая может быть выполнена.
Схематически, то каждый работник поток будет делать что-то вроде этого:
- Блокировка мьютекса .
Если задача, поставленная в очередь, не может быть запущена, то
а. Ожидать переменную условия .
b. Когда поток возвращается из ожидания, go возвращается к (2).
(Если управление достигает этой точки, то в очереди имеется соответствующая задача.) Исключите подходящую задачу , T , цвета C ( T ).
- Обновите данные отслеживания цвета, чтобы показать, что задача цвет C ( T ) запущен.
- Разблокировать мьютекс .
- Выполнить задачу T .
- Блокировка мьютекса .
- Обновление данных отслеживания цвета, чтобы показать, что больше нет цветовой задачи C ( T ) работает.
- Передача в переменную условия .
- Go обратно в (2).
Полагаю, вы захотите включить условие завершения, чтобы ваши потоки могли корректно завершаться. Это, вероятно, будет оценено как часть шага (2). Убедитесь, что после выхода из l oop потоки разблокируют мьютекс .
Также обратите внимание, что поток, который хочет поставить в очередь новую задачу во время работы рабочих - сам рабочий поток или какой-то другой - должен удерживать мьютекс при этом, и после этого должен транслироваться в резюме.
Я думал о группировании очереди по цветам, и я могу прикрепить мьютекс каждой цветовой группе, но затем я застрял на том, как использовать эти мьютексы.
Действительно. Мьютекс на группу не помогает, потому что с CV может быть связан только один мьютекс. Этот мьютекс должен храниться, пока поток оценивает, удовлетворяется ли условие для продолжения, и пока поток обновляет любые данные, участвующие в оценке этого условия. Дополнительные мьютексы, защищающие подмножества этих данных, были бы бесполезны, потому что никогда не могло быть более чем одного потока, борющегося за них (тот, который содержит основной мьютекс).
Возможно, все еще разумно добавить структуру в вашу очередь облегчить оценку того, какие задачи могут быть выполнены, но вы не предоставили нам достаточно информации, чтобы предложить детали. (И этот вопрос уже достаточно широк, поэтому, пожалуйста, не раскрывайте его такой информацией.)