8  Práctica 02. Colas con prioridad

8.1 Teoría de colas con prioridad

Tu profesor te habrá explicado las colas con prioridad. Repásalo y asegúrate de entenderlo todo bien.

8.2 Frames

En los ejemplos de la teoría, el dato era simplemente una letra mayúscula. Ahora el dato será un frame de PDRouter. Por tanto tendrás que crear, almacenar y mostrar estas tramas. Es sencillo. Tu profesor te habrá explicado cómo. Repasa la documentación para tenerlo claro:

  • Uso de Frame

  • En el fichero ~/pst2/pdrouter/src/bin/test_frame_01.rs tienes un ejemplo muy ilustrativo que genera e imprime una de estas tramas. Si no lo tienes, es que no has configurado bien tu repositorio upstream.

8.3 Práctica 201: tramas en un vector

Aunque nuestro objetivo es tener una cola de tramas con prioridad, vamos a empezar por algo más sencillo: meter tramas ethernet (frames) en un vector. De momento, tramas a secas.

  • Cuando trabajemos con colas con prioridad, tendremos un item que contendrá un dato (la trama) y una prioridad. Pero ahora no: solo frames.

  • También tendremos que usar enumerados Option<T> para considerar el caso de la cola vacía. Ahora no: solo frames.

Escribe un programa en el fichero ~/pst2/pdrouter/src/bin/prac_201.rs según la siguiente especificación. Recuerda que aunque es un binario independiente de PDRouter, pertenece al proyecto PDRouter, por tanto no debes ejecutar cargo new. Ni para este programa ni para ningún otro en pdrouter/src/bin/.

Haz que:

  1. Prepare una trama. Pon cualquier valor de prueba en el origen, destino y carga.

  2. Meta la trama en un vector.

  3. Prepare otra trama. Para simplificar, que sea igual en todo a la primera, excepto en el destino.

  4. Meta la trama en el vector.

  5. Repita los pasos 3 y 4, dos o tres veces. Con diferente destino cada vez. No es necesario un bucle, este es un pequeño programa de prueba.

  6. Muestre, usando un bucle, todas las tramas que haya en el vector.

El resultado será algo similar a esto:

Frame
  Longitud: 19 bytes
  Ethernet
    Origen:  00:11:22:33:44:55
    Destino: 00:00:00:00:00:0a
    Tipo:    desconocido (0x1234)
    Payload: [01, 02, 03, 04, 05]

Frame
  Longitud: 19 bytes
  Ethernet
    Origen:  00:11:22:33:44:55
    Destino: 00:00:00:00:10:0b
    Tipo:    desconocido (0x1234)
    Payload: [01, 02, 03, 04, 05]

Frame
  Longitud: 19 bytes
  Ethernet
    Origen:  00:11:22:33:44:55
    Destino: 00:00:00:00:00:0c
    Tipo:    desconocido (0x1234)
    Payload: [01, 02, 03, 04, 05]

8.4 Práctica 202: Cola con prioridad de tramas

Prepara un programa en el fichero ~/pst2/pdrouter/src/bin/prac_202.rs que cumpla la siguiente especificación.

Ahora que te has familiarizado con el uso de tramas, implementarás una cola con prioridad. Ya sabes: un vector donde cada item será una trama y una prioridad.

Este código lo integrarás posteriormente en PDRouter. Por este motivo, las funciones principales tendrán que seguir el API previsto en PDRouter y deberán tener exactamente el nombre y parámetros indicados aquí. Las funciones auxiliares, podrás organizarlas como te parezca conveniente.

Cualquier programador con experiencia sabe que lo más habitual es escribir una función, probarla y no pasar a la siguiente hasta tener la anterior razonablemente madura.

Por si no tienes este principio interiorizado todavía, estas instrucciones te sugieren un orden paso a paso:

  1. La estructa del item será la siguiente:

    struct QueueItem {
    frame: Frame,
    priority: u8,
}

  2. Escribe una función que cree un item (trama + prioridad).

    fn new_item(frame: Frame, priority: u8) -> QueueItem

  3. Escribe una función que añada un item al final del vector.

    fn enqueue(queue: &mut Vec<QueueItem>, item: QueueItem)

  4. Prueba ambas funciones, mete el item en la cola. Esto es solo un test que luego puedes borrar.

  5. Escribe el contenido del item que está en la cola. A modo de test, bórralo luego.

  6. Mete varios items en la cola. Con prioridades variadas. Las tramas, como en el ejercicio anterior: todas con el mismo origen, tipo y contenido, pero distinto destinatario.

  7. Escribe una función que muestre en pantalla el contenido de toda la cola. Si está vacía, que lo indique.

    No forma parte del API, ponle el nombre que quieras.

  8. Escribe una función que averigüe el ordinal del item más prioritario. Devolverá Some(usize) o None, dependiendo de si en la cola hay elementos o está vacía. Recuerda que usize es el tipo de entero sin signo que se utiliza habitualmente para representar tamaños e índices de estructuras como los vectores. Si varios items tienen la misma prioridad, que devuelva el primero en aparecer.

    No forma parte del API, ponle el nombre que quieras.

  9. Muestra esta trama más prioritaria.

    A modo de test, bórralo luego.

  10. Escribe una función que extraiga de la cola el item más prioritario y lo devuelva como un Option.

    fn pop_highest_priority(queue: &mut Vec<QueueItem>) -> Option<QueueItem>

Cuando todo funcione, prepara el programa para que genere algo similar a esto:

    Iniciamos cola vacía
    Cola vacía. No se ha extraido nada
    Contenido de la cola:
        0-"Frame\n  Longitud: 19 bytes\n  Ethernet\n    Origen:  00:11:22:33:44:55\n    Destino: 00:00:00:00:00:0a\n    Tipo:    desconocido (0x1234)\n    Payload: [01, 02, 03, 04, 05]": prioridad 3
        1-"Frame\n  Longitud: 19 bytes\n  Ethernet\n    Origen:  00:11:22:33:44:55\n    Destino: 00:00:00:00:00:0b\n    Tipo:    desconocido (0x1234)\n    Payload: [01, 02, 03, 04, 05]": prioridad 5
        2-"Frame\n  Longitud: 19 bytes\n  Ethernet\n    Origen:  00:11:22:33:44:55\n    Destino: 00:00:00:00:00:0c\n    Tipo:    desconocido (0x1234)\n    Payload: [01, 02, 03, 04, 05]": prioridad 2
    Extraemos Frame
      Longitud: 19 bytes
      Ethernet
        Origen:  00:11:22:33:44:55
        Destino: 00:00:00:00:00:0b
        Tipo:    desconocido (0x1234)
        Payload: [01, 02, 03, 04, 05]
    Extraemos Frame
      Longitud: 19 bytes
      Ethernet
        Origen:  00:11:22:33:44:55
        Destino: 00:00:00:00:00:0a
        Tipo:    desconocido (0x1234)
        Payload: [01, 02, 03, 04, 05]
    Extraemos Frame
      Longitud: 19 bytes
      Ethernet
        Origen:  00:11:22:33:44:55
        Destino: 00:00:00:00:00:0c
        Tipo:    desconocido (0x1234)
        Payload: [01, 02, 03, 04, 05]

En el contenido de la cola podemos observar que la más prioritaria tiene como destino la dirección 00:00:00:00:00:0b, la siguiente es la 00:00:00:00:00:0a, y luego la 00:00:00:00:00:0c.

No es necesario que utilices estos mismos datos, pero sí unos parecidos, que produzcan un resultado análogo.