Colas de prioridad en Java

Java incluye colas de prioridad como parte de Collections Framework . La cola de prioridad se llama así por uno de los usos principales: programar el trabajo en el sistema operativo. Es una lista parcialmente ordenada donde no tienes que ordenar todos los elementos, solo asegúrate de que el elemento menos importante esté primero.

Dado que no hay clasificación, este método es más eficiente que una lista ordenada. Sin embargo, aún le permite recuperar elementos de la cola en un orden determinado, del más pequeño al más grande. Esto permite agregar elementos a la cola a medida que se eliminan otros elementos (en este caso, es posible que los elementos eliminados no se ordenen, sino que solo tengan los valores más pequeños en el momento de la solicitud).

Si una aplicación está programada para ejecutarse y tiene una prioridad, donde un valor más bajo significa algo que debería ejecutarse antes, puede agregarla a la cola de prioridad para distribuir los recursos de manera justa entre las aplicaciones. Prioridad cero significa que la aplicación solo compite con otras aplicaciones con prioridad de ejecución cero.

Para demostrar esto, vamos a crear una clase Application. Tiene un valor de prioridad de cero a n y la cantidad de trabajo es un número aleatorio de cero a 100. También vamos a darle a esta clase un nombre para realizar un seguimiento.

Applicationcontiene un bloque de funciones que permite que durante cierto tiempo consuma recursos del procesador en el rango de 0,1 segundos. Cada vez que se ejecuta, el número de tareas ( todo) disminuye y la prioridad aumenta (reduce la posibilidad de reprogramación). Puede haber confusión porque es probable que la prioridad cero esté en la parte superior de la cola de prioridad y es más probable que se vuelva a barajar.

Aquí está mi implementación de esto 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;
        }
    }

La clase Applicationimplementa la comparabilidad ( Comparable) para estar en la cola de prioridad PriorityQueue. Tiene dos métodos principales: hasMoreWorky block. El método hasMoreWorksimplemente comprueba si el valor es mayor que cero todo. El método blockrestablecerá la prioridad a cero y luego comenzará a trabajar.

El método doWorkhace el trabajo. Disminuye todoen uno y aumenta el valor de prioridad. Esto significa que cuanto más trabajo se complete en una llamada antes del bloqueo, es menos probable que cambie el lugar en el cronograma. El único trabajo que realmente se hace es dormir durante 0,1 segundos.

Vamos a crear un método principal que probará este comportamiento en la cola de prioridad. Creará una cola con un número aleatorio de objetos Application, cada uno comenzando con prioridad cero y teniendo que hacer una cantidad aleatoria de trabajo.

Luego sondeará continuamente la cola usando el método Stream.generatehasta que esté vacía. La función pollregresa Applicationlista para ejecutarse, o nullsi la cola está vacía. Dado que las secuencias no pueden tener valores nulos, usaremos Optional.ofNullablepara convertir cero Optional.emptyy luego usaremos el método takeWhilepara detener el hilo cuando la cola esté vacía.

Luego, para cada aplicación que esté lista para ejecutarse, llamamos a la función blockde bloqueo y verificamos si hay más tareas. En caso afirmativo, vuelva a agregar la aplicación a la cola. Aquí está la implementación del método principal:

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);
                    }
                });}

Debido a que la división de tiempo se simula solo para un procesador, aquí se usa un método secuencial para asegurarse de que solo se tome un elemento de la cola a la vez.

Hay algunos detalles artificiales en esta simulación: el trabajo de una aplicación real no será dormir, sino usar el procesador. Hará esto hasta que bloquee la E/S o haya pasado una cierta cantidad de tiempo. Si una aplicación regresó de un bloque porque estaba esperando E/S, no se volverá a agregar a la cola hasta que se haya completado la E/S. En tal caso, el método blockpodría devolver el estado "listo para más trabajo", "bloqueo en E/S" o "listo".

Con solo mirar la salida, puede ver que los recursos de la CPU se comparten entre todas las aplicaciones hasta que todas salen.

Aunque probablemente haya otros usos para la cola de prioridad, el principal es la programación de tareas. Como desarrollador de aplicaciones, probablemente no encuentre esto a menudo. Pero aún así es bueno saberlo y tenerlo en cuenta en caso de que tenga un uso.