Обработка задач с различными приоритетами в пуле потоков

Ответ 1

Возможно, вам следует использовать 3 пула потоков. 1 пул из 7 потоков для задач A, 1 пул из 2 потоков для задач B и 1 пул из 1 потока для задач C.

EDIT: иметь parallelism, даже если есть только задачи C (или, если у вас много процессоров, если у вас есть только задачи B и C), умножьте количество потоков в каждом пуле на количество процессоров, или количество процессоров + 1 или любой другой более важный фактор, который вам нравится.

Ответ 2

Предполагая, что никакие другие процессы не выполняются на процессоре, создайте 3 пула потоков, по одному для каждого типа задач, каждый пул с таким количеством потоков, сколько ядер на процессоре (так что весь процессор может потребляться задачами любой тип, если выполняются только задачи этого типа). Каждая новая задача должна проходить через раздел кода, который записывает, сколько из каждого типа задач запущено. Если на процессоре есть свободное ядро, немедленно запустите новую задачу. Если свободного места нет, начните с пула с самым низким приоритетом, который имеет более низкий приоритет, чем новая задача, и при необходимости перейдите к следующему пулу с самым высоким приоритетом: прерывайте/приостанавливайте текущий поток (это предполагает, что задачи предназначены для быть прерываемым/приостановленным), если текущий пул превышает предел его пропорционального использования ядра, дождитесь завершения этой задачи (первая задача может завершиться первой, что так же хорошо). Запустите новую задачу в правильном пуле. Если новая задача не может быть запущена, она ждет очереди в очереди для завершения другого потока, освобождая новый слот. Когда новый слот освобождается, задача только что завершившегося типа получает первый приоритет для освобожденного слота, если такая задача не ждет, тогда запускается задача ожидания с наивысшим приоритетом.

Ответ 3

это на самом деле довольно сложная проблема. в основном вам потребуется реализовать настраиваемую очередь блокировки, которая отслеживает не только ожидающие задания, но и текущие рабочие задания. для ожидающих заданий я бы сохранил отдельные списки для различных уровней приоритета. кроме того, вы должны отслеживать количество запусков для каждого уровня приоритета. когда новое задание запрашивается из очереди, вам необходимо проверить соотношение текущих выполняемых заданий и выбрать следующее доступное задание с наивысшим применимым приоритетом (отложить до других приоритетов, если ни один из них не имеет желаемого приоритета). очевидно, вам понадобится обратная связь в этой очереди для ваших рабочих заданий, поэтому вы, вероятно, захотите обернуть фактические задания с помощью обертки Runnable, которая запускает реальную работу, а затем обновляет вашу очередь, когда это задание будет завершено.

Ответ 4

Напишите механизм прогнозирования, который статистически определяет вероятность того, что заданная задача будет завершена до того, как прибудет задача с более высоким приоритетом. Параметрировать пороговое значение доверительного значения, которое является приемлемым. Чем выше требуемая уверенность, тем более вероятно, что вы будете использовать CPU. Чем ниже порог, тем больше вероятность того, что вы получите слишком много CPU для решения задач с более низким приоритетом.

Ответ 5

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

Предположим, что у нас есть три отдельные очереди для трех типов задач, что означает, что у нас есть три очереди для TypeA, другие для TypeB, другие для Typec.

У нас может быть queueToprocess позволяет сказать, что это Qp.

Существует планировщик, который контролирует Qa, Qb, Qc и заполняет Qp.

Предположим, что каждая Задача в Qa, Qb, Qc будет иметь специальное поле, в котором указано количество циклов ЦП, необходимых для выполнения задачи.

Предположим, что у Qa есть три задачи, в которых для первой задачи требуется 1 такт, вторая задача требует трех тактовых циклов, а третий требует 3 тактовых цикла.

Предположим, что у Qb есть одна задача, для которой требуется 2 такта, а Qc - одна задача, для которой требуется 1 такт.

Планировщик разделит задачу T на небольшие задачи и запишет в Qp.

Тогда Qp будет выглядеть как Tc, Tb, Ta1, Ta2, Ta2, Ta2, Ta3, Ta3, Ta3.

Процессор может выполнить Qp и выполнить задачу.

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

Ответ 6

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

           CPU
            |
-------------------------
|           |           |
A (70)     B (20)      C (10)
            |
       ---------------
       |  |  |  | |  | 
      T1 T2 T3 T4 T5 T6

Обратите внимание, что я не показываю полную иерархию для A и C, но я уверен, что у вас есть идея. Теперь путь к реализации - это очень простой планировщик, основанный на виртуальном времени, который позволяет говорить о стартовой очереди очереди (SFQ) от Goyal для обработки планирования между A, B и C.

Такой планировщик работает консервативно, что означает, что если присутствуют только задачи из C, то C в целом возьмет все это.

Теперь, чтобы иметь дело со вторым уровнем планирования, у вас есть два пути... Либо вы реализуете HSFQ, который является иерархической версией SFQ, либо вы делаете простой круговой поворот среди потоков ниже A, B и C, чтобы каждый нить получает "справедливую" долю циклов, доступных для пула.

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

Вы также можете взглянуть на Stride Scheduling, в частности, на свою иерархическую версию...

Надеюсь, что это поможет,