В Java включает очереди с приоритетом в рамках Collections Framework. Очередь приоритетов называется так по одному из главных способов применения — планирования работы в операционной системе. Она представляет собой частично упорядоченный список, где не нужно сортировать все элементы, а нужно только убедиться, что наименее важный объект находится в начале.
Поскольку сортировка не происходит, этот способ эффективнее отсортированного списка. При этом он все же позволяет извлекать элементы из очереди в определенном порядке, от меньшего к большему. Благодаря этому можно добавлять элементы в очередь по мере удаления других элементов (в этом случае удаленные элементы могут быть не отсортированы, а только обладать наименьшими значениями на момент запроса).
Если приложение запланировано к выполнению и имеет приоритет, где меньшее значение означает то, что должно выполняться раньше, можно добавить его в очередь приоритетов, чтобы справедливо распределять ресурсы между приложениями. Нулевой приоритет означает, что приложение конкурирует только с другими приложениями с нулевым приоритетом выполнения.
Чтобы продемонстрировать это, создадим класс Application. Он имеет приоритет со значением от нуля до n и объем работы — случайное число от нуля до 100. Также дадим этому классу имя, чтобы его отслеживать.
Application содержит функциональный блок, который позволяет в течение определенного времени потреблять ресурсы процессора в промежутке 0,1 секунды. Каждый раз, когда он выполняется, количество задач (todo) уменьшается и увеличивается приоритет (снижается вероятность перестановки в расписании). Может возникать путаница, поскольку нулевой приоритет, скорее всего, будет находиться в верхней части очереди приоритетов и с большей вероятностью будет подвергнут перестановке.
Вот моя реализация этого Application.java:
public static class Application implements Comparable<Application> {
private int priority;
private int todo;
private final String name;
public Application(String name) {
this.name = name;
this.priority = 0;
this.todo = r.nextInt(100);
}
public boolean hasMoreWork() {
return todo > 0;
}
public void block() {
System.out.println("priority was " + priority);
priority = 0;
IntStream.range(0, r.nextInt(5))
.forEach(i -> doWork());
}
private void doWork() {
System.out.println("doing work for " + this);
todo--;
priority++;
try {
Thread.sleep(100); // тяжелая работа!
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public int compareTo(Application o) {
return priority-o.priority;
}
public String toString() {
return "Application " + name;
}
}Класс Application реализует сопоставимость (Comparable), чтобы находиться в очереди приоритетов PriorityQueue. У него два основных метода: hasMoreWork и block. Метод hasMoreWork просто проверяет, больше ли нуля значение todo. Метод block сбросит приоритет до нуля, а затем начнет выполнять работу.
Метод doWork выполняет работу. Он уменьшает todo на единицу и увеличивает значение приоритета. А значит, чем больше работы будет выполнено за один вызов до блокировки, тем меньше вероятность того, что место в расписании изменится. Единственная работа, которая выполняется на самом деле, — это сон в течение 0,1 секунды.
Создадим основной метод, который протестирует это поведение в очереди приоритетов. Он создаст очередь со случайным количеством объектов Application, каждый из которых начинает с нулевого приоритета и должен выполнить случайный объем работы.
Затем он будет непрерывно опрашивать очередь с помощью метода Stream.generate, пока она не опустеет. Функция poll возвращает Application, готовое к запуску, или значение null, если очередь пуста. Поскольку потоки не могут иметь нулевых значений, воспользуемся Optional.ofNullable для превращения нуля в Optional.empty, а затем применим метод takeWhile, чтобы остановить поток, когда очередь опустеет.
Затем для каждого приложения, готового к запуску, вызываем функцию блокировки block и проверяем, стоят ли еще задачи. Если да, то добавляем приложение обратно в очередь. Вот реализация основного метода:
public static void main( String[] args )
{
final PriorityQueue<Application> pq =
IntStream.rangeClosed(0, r.nextInt(10))
.mapToObj(i -> new Application(Integer.toString(i)))
.collect(PriorityQueue::new,
PriorityQueue::offer,
AbstractQueue::addAll); Stream.generate(() -> Optional.ofNullable(pq.poll()))
.sequential()
.takeWhile(Optional::isPresent)
.map(Optional::get)
.forEach(s -> {
s.block();
if(s.hasMoreWork()) {
pq.offer(s);
}
});}Поскольку квантование времени имитируется только для одного процессора, здесь применен последовательный метод, чтобы убедиться, что из очереди берется только один элемент за раз.
В этой симуляции есть некоторые искусственные детали: работа реального приложения будет заключаться не в том, чтобы спать, а в том, чтобы использовать процессор. Оно будет делать это до тех пор, пока не будет заблокировано при вводе-выводе или не пройдет определенное время. Если приложение вернулось из блока, потому что ждало ввода-вывода, оно не будет добавлено обратно в очередь до тех пор, пока не завершится ввод-вывод. В таком случае метод block мог бы возвращать статус “готовность к дополнительной работе”, “блокировка при вводе-выводе” или “готово”.
Просто взглянув на вывод, вы увидите, что ресурсы процессора разделяются между всеми приложениями до тех пор, пока все они не завершат работу.
Хотя, вероятно, существуют и другие применения очереди приоритетов, но основным остается планирование задач. Как разработчик приложений, вы, вероятно, нечасто будете сталкиваться с подобным. Но все равно полезно знать об этом и держать в голове на случай, если для этого появится применение.
Здесь можно найти весь код, используемый в статье.
Читайте также:
- Основы API Time для Java
- 3 применения исключений, которые улучшат навыки программирования на Java
- Осваиваем реактивное программирование на Java
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Randal Kamradt Sr: Priority Queues in Java
