13,8 тыс подписчиков

Очереди с приоритетом в Java

17 сентября 202117 сен 2021

3 мин

Источник: Nuances of Programming В Java включает очереди с приоритетом в рамках Collections Framework. Очередь приоритетов называется так по одному из главных способов применения — планирования работы в операционной системе. Она представляет собой частично упорядоченный список, где не нужно сортировать все элементы, а нужно только убедиться, что наименее важный объект находится в начале. Поскольку сортировка не происходит, этот способ эффективнее отсортированного списка. При этом он все же позволяет извлекать элементы из очереди в определенном порядке, от меньшего к большему. Благодаря этому можно добавлять элементы в очередь по мере удаления других элементов (в этом случае удаленные элементы могут быть не отсортированы, а только обладать наименьшими значениями на момент запроса). Если приложение запланировано к выполнению и имеет приоритет, где меньшее значение означает то, что должно выполняться раньше, можно добавить его в очередь приоритетов, чтобы справедливо распределять ресурс

Источник: Nuances of Programming

В Java включает очереди с приоритетом в рамках Collections Framework. Очередь приоритетов называется так по одному из главных способов применения — планирования работы в операционной системе. Она представляет собой частично упорядоченный список, где не нужно сортировать все элементы, а нужно только убедиться, что наименее важный объект находится в начале.

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

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

Чтобы продемонстрировать это, создадим класс Application. Он имеет приоритет со значением от нуля до n и объем работы — случайное число от нуля до 100. Также дадим этому классу имя, чтобы его отслеживать.

Application содержит функциональный блок, который позволяет в течение определенного времени потреблять ресурсы процессора в промежутке 0,1 секунды. Каждый раз, когда он выполняется, количество задач (todo) уменьшается и увеличивается приоритет (снижается вероятность перестановки в расписании). Может возникать путаница, поскольку нулевой приоритет, скорее всего, будет находиться в верхней части очереди приоритетов и с большей вероятностью будет подвергнут перестановке.

Вот моя реализация этого Application.java:

Класс Application реализует сопоставимость (Comparable), чтобы находиться в очереди приоритетов PriorityQueue. У него два основных метода: hasMoreWork и block. Метод hasMoreWork просто проверяет, больше ли нуля значение todo. Метод block сбросит приоритет до нуля, а затем начнет выполнять работу.

Метод doWork выполняет работу. Он уменьшает todo на единицу и увеличивает значение приоритета. А значит, чем больше работы будет выполнено за один вызов до блокировки, тем меньше вероятность того, что место в расписании изменится. Единственная работа, которая выполняется на самом деле, — это сон в течение 0,1 секунды.

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

Затем он будет непрерывно опрашивать очередь с помощью метода Stream.generate, пока она не опустеет. Функция poll возвращает Application, готовое к запуску, или значение null, если очередь пуста. Поскольку потоки не могут иметь нулевых значений, воспользуемся Optional.ofNullable для превращения нуля в Optional.empty, а затем применим метод takeWhile, чтобы остановить поток, когда очередь опустеет.

Затем для каждого приложения, готового к запуску, вызываем функцию блокировки block и проверяем, стоят ли еще задачи. Если да, то добавляем приложение обратно в очередь. Вот реализация основного метода:

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

В этой симуляции есть некоторые искусственные детали: работа реального приложения будет заключаться не в том, чтобы спать, а в том, чтобы использовать процессор. Оно будет делать это до тех пор, пока не будет заблокировано при вводе-выводе или не пройдет определенное время. Если приложение вернулось из блока, потому что ждало ввода-вывода, оно не будет добавлено обратно в очередь до тех пор, пока не завершится ввод-вывод. В таком случае метод block мог бы возвращать статус “готовность к дополнительной работе”, “блокировка при вводе-выводе” или “готово”.

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

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

Здесь можно найти весь код, используемый в статье.