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

Question

У меня много входящих задач с приоритетом A, B и C, и я хочу обрабатывать задачи с помощью пула потоков на многоядерном процессоре.70% ЦП следует использовать для обработки задач типа A, 20% ЦП для задач типа B и 10% ЦП для задач типа C.

Если, однако, поступают только задачи типа C, то 100% ЦП должно быть выделено для них.Если только задачи B и C arirve, то 66% будут выполнять задачи B и 33% задачи C и т. Д. *

Как бы вы реализовали это в Java?

ps: очередь с приоритетами не будет работать, потому что тогда будут обрабатываться только задачи типа.Кроме того, назначение приоритетов для потоков не будет работать, потому что это не точно.

Answer 1

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

РЕДАКТИРОВАТЬ: иметь параллелизм, даже если есть только задачи C (илиу вас много процессоров, если у вас есть только задачи B и C), умножьте количество потоков в каждом пуле на количество процессоров, или количество процессоров + 1, или любой другой больший коэффициент, который вам нравится.

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

Предположим, у нас есть три отдельные очереди для трех типов задач, что означает, что у нас есть три очереди, одна для Типа А, другаядля 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 и выполнить задачу.

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

Answer 4

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

Answer 5

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

Answer 6

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