Тренды

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

17.09.2021

В 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 мог бы возвращать статус “готовность к дополнительной работе”, “блокировка при вводе-выводе” или “готово”.

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

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

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