Duda de RR en implementación de algoritmo de Colas Multinivel

[ArielSurco]

🛠️ Lenguaje

C

🖋️ Descripción

Buenas! Tengo una duda respecto a la "correcta" implementación de Colas Multinivel con Round Robin.

Estaría bien plantear el algoritmo de CMN como un algoritmo de prioridades que además setea un temporizador (tiempo=Quantum) para enviar la interrupción a la CPU? En la sección de soluciones posibles adjunto cómo estaba planteando la implementación, para más contexto

Mi interpretación de RR es que funciona como un FIFO que agrega el temporizador (para desalojar por Quantum) para que un proceso no monopolice la CPU, y sumando a esto que se combina con CMN con algoritmo de Prioridades (entre colas) resulta en que primero tienen que finalizar todos los procesos de la cola de mayor prioridad para pasar a la siguiente, donde al utilizarse RR se desempatan por FIFO los que tengan la misma prioridad. Cosa que, teniendo en cuenta que no hay desalojo entre colas, si le quitara la interrupción por quantum el funcionamiento lo veo muy similar al algoritmo de prioridades.

📔 Citas del enunciado/videos

Colas Multinivel Se elegirá al siguiente hilo a ejecutar según el siguiente esquema de colas multinivel:

• Se tendrá una cola por cada nivel de prioridad existente entre los hilos del sistema.
• El algoritmo entre colas es de prioridades sin desalojo.
• Cada cola implementará un algoritmo Round Robin con un quantum (Q) definido por archivo de configuración.
• Al llegar un hilo a ready se posiciona siempre al final de la cola que le corresponda.

💭 Soluciones posibles

En mi planificador a corto plazo llamo a una función obtener_siguiente_a_exec que es quien se encarga de seleccionar la función que utiliza el algoritmo definido en la configuración.

En la función correspondiente al algoritmo por prioridades hago algo tal que:

// Se obtiene una lista de los TCBs en READY que tengan la misma prioridad que el TCB con la mayor prioridad en la lista
// Esto es lo que me permite manejar cualquier cantidad de prioridades
t_list* lista_mayor_prioridad = obtener_lista_mayor_prioridad();

// Como mantiene el mismo orden que tenían en la lista de READY, el primer elemento es el que "ingresó primero" para la mayor prioridad de READY (en ese instante)
return list_get(lista_mayor_prioridad, 0)

Y en la función que corresponde al algoritmo de CMN queda algo similar a esto:

t_tcb* siguiente_a_exec = obtener_siguiente_a_exec_prioridades();

crear_hilo_desalojo_por_quantum(siguiente_a_exec);

return siguiente_a_exec;

Por lo que técnicamente estoy implementando listas y no colas, y aunque lo modificara para que obtener_lista_mayor_prioridad retorne colas, el algoritmo de prioridades estaría implementando más de una cola (intermedias/auxiliares) y no solo una como se menciona en la primera respuesta del issue #4289

FIFO y Prioridades: Van a poder trabajar con una sola cola de hilos, Colas Multinivel: En este caso, necesitarán implementar varias colas, cada una representando un nivel de prioridad.

📝 Normas del foro

• [X] Leí los lineamientos del foro

[iago64]

Buenas! Cómo va?

El planteo que haces de como estas pensando Colas Multi Nivel esta correcto, algo importante del TP es que no hay una única solución a los problemas.

En la resolución que planteas lo único que me preocupa es como manejan si por ejemplo estan ejecutando un hilo de una queue de prioridad 3 y aparece justo uno de prioridad 0, 1 o 2, ya que si llega un hilo de esas prioridades el próximo a ejecutar sería el nuevo y no otro de la cola de prioridad 3.

Saludos.-

[ArielSurco]

En la resolución que planteas lo único que me preocupa es como manejan si por ejemplo estan ejecutando un hilo de una queue de prioridad 3 y aparece justo uno de prioridad 0, 1 o 2, ya que si llega un hilo de esas prioridades el próximo a ejecutar sería el nuevo y no otro de la cola de prioridad 3.

Para resolver eso, la responsabilidad recae en la función obtener_lista_mayor_prioridad que:

• Primero recorre la lista de TCBs buscando el que tenga la prioridad más alta en el momento en que se llama, nos interesa saber el valor de esa prioridad más alta, 0, 2, 5 o el que sea
• Filtra la lista de TCBs en READY según aquellos que tengan la misma prioridad que se encontró en el paso anterior
• Y de esta lista, para desempatar por FIFO obtenemos el primero de la lista (index=0)

Y como esta función se llama cada vez que se quiere saber cuál es el siguiente hilo a ejecutar (solo en prioridades y CMN) siempre estaría actualizada con cualquier cambio que se haga en READY (bloqueando con mutex la lectura para evitar condiciones de carrera)

[iago64]

Excelente! Como estan asegurandose de que si cae algun hilo nuevo a READY en una prioridad mayor lo atienden, esta bien como lo etan planteando.

Saludos.-

[ArielSurco]

Excelente, muchas gracias!!