so-tp1/informe/9-informe.md

\newpage

Ejercicio 9

Descripción del algoritmo

Este scheduler intenta alcanzar un balance entre las tareas con alto uso de recursos y tareas con poco uso de recursos y mucho IO, garantizando mayor CPU a las primeras y un menor waiting time para las segundas. Las tareas con menor prioridad tendrán más rápido acceso al CPU pero por menos tiempo, reduciendo el waiting time y dando una respuesta más rápida. Por otro lado las tareas que requieran más recursos, tendrán menos prioridad para acceder al CPU pero a cambio de esto se les asignará más Quantum empeorando su waiting time pero mejorando el throughput.

Implementacion

Para la implementación de este ejercicio utilizando:

• Map<pid, process>: En dicho Map se almacena un descriptor struct con datos del proceso actual como: pid, state y quantum_count, a los que se accede utilizando el pid como clave.

• vector<queue<pid>>: En este vector se almacenan las distintas colas de ejecución, en las mismas se almacena solo el pid para poder luego consultarlo en el mapa si es necesario accederlo.

• vector<uint>: Este vector tiene el mismo tamaño que el vector utilizado anteriormente y se utiliza para almacenar el cuantum correspondiente al índice de cada cola. Por ejemplo la cola en la posición 0 del arreglo de colas tiene el quantum almacenado en la posición 0 de este arreglo.

Esto nos permite poder mantener cada cola de prioridad con los PIDs que tiene asignados e ir pasandolos de cola en cola sin tener que migrar todos los datos del proceso, ya que al mismo se accede por su PID mientras se encuentre en ejecución.

En el constructor del scheduler se lee la cantidad de parámetros, con esto se inicializan los dos vectores (con las colas y los quantums) y se almacena el quantum correspondiente a cada cola segun el orden en el que se reciben. (Esto le da la 'prioridad' a cada cola).

Cada vez que se carga un nuevo proceso, el mismo se aloja en la cola de mayor prioridad (La cola en la posición 0). Al haber un tick se controla que no se haya cumplido el quantum establecido para dicha cola, si se cumplió se lo intenta mover a una cola de menor prioridad (número más alto) y se marca como READY. Al haber un unblock se intenta 'premiar' a la tarea (que no utilizó completamente su quantum antes de ser desalojada), moviéndola a una cola de mayor prioridad.

Casos de prueba

Para probar el funcionamiento del scheduler, se procedió a correr 3 lotes de tareas en las que se intenta simular distintos casos de usos para ver como se comporta el mismo.

Las tareas consisten en los siguientes 3 casos:

• Uso elevado de CPU Alto uso de CPU casi sin uso de IO, se simulan tareas con mucho consumo de CPU (que superen el quantum estimado) con pequeñas operaciones de IO.
• Uso elevado de I/O: Tareas con poco consumo de CPU (comparadas al uso elevado de CPU) pero con un alto uso de I/O.
• Interacción de usuario: Consiste en varios procesos con uso de I/O seguidos de procesos con alto uso de CPU. Para simular la entrada de un usuario y el procesamiento de programas o scripts del mismo.

Uso elevado de CPU

Se utilizó el siguiente lote de tareas para simular uso intensivo de CPU.

Release time	Cantidad	Tipo	Ticks	Cant. Bloq.	Tiempo Bloq.
0	3	TaskCPU	50	-	-
10	3	TaskConsola	3	3	8 - 10
15	5	TaskCPU	4	-	-
20	1	TaskCPU	10	-	-

En este caso se puede ver claramente la priorización de tareas con IO (3,4,5) sobre las tareas que consumen todo su quantum y son asignadas a una cola de menor prioridad.

Uso elevado de I/O

Para este caso se crearon tareas consitentes casi en su totalidad de llamadas bloqueanes con algún uso esporádico de CPU.

Release time	Cantidad	Tipo	Ticks	Cant. Bloq.	Tiempo Bloq.
0	1	TaskCPU	50	-	-
0	5	TaskBatch	10	8	2
5	2	TaskConsola	4	4	5 - 10
10	2	TaskCPU	10	-	-
10	3	TaskBatch	9	4	2

En este caso se puede ver que la priorización de procesos "interactivos" consume completamente el CPU (hasta ~160), donde finalmente pueden ejecutar los procesos que estaban en la segunda cola.

\newpage

Interacción de usuario

Para este caso se creo una mezcla de tareas bloqueantes de consola, seguidas por tareas de CPU que corren "en background".

Release time	Cantidad	Tipo	Ticks	Cant. Bloq.	Tiempo Bloq.
0	1	TaskCPU	50	-	-
0	3	TaskBatch	6	3	2
5	2	TaskConsola	5	5	10 - 15
15	1	TaskCPU	25	-	-
30	2	TaskConsola	4	4	7 - 10
30	1	TaskCPU	40	-	-
40	1	TaskConsola	4	4	6 - 10

En este caso podemos ver un buen lote de tareas para el scheduler; las tareas "interactivas" tienen bajo waiting time mientras que las tareas con uso intensivo de CPU tienen mayor waiting time pero también reciben mas quantum.

Conclusiones

A continuación se preparó una tabla comparativa con la latencia, waiting time y turnaround promedio para cada lote de pruebas ejecutado anteriormente.

	CPU	IO	USER
M. Latency	4.92	9.3	4.0
M. Ready	89.2	133	76.8
M. Turnaround	110	136	90

En esta tabla se ve que para un lote de tareas "interactivo" los resultados mejoran, como es de esperarse, por el comportamiento del scheduler. Para los otros lotes de tareas:

• CPU: Si las tareas del lote usan principalmente CPU eventualmente todos los procesos terminan en la cola de menor prioridad y con mas quantum, esencialmente se vuelve un round robin.
• IO: Si las tareas del lote usan principalmente IO, toda estas tareas quedan en la lista de prioridad más alta, donde se pierde gran parte del tiempo haciendo context/cpu switch, nuevamente actuando como un Round Robin sin mucha prioridad en particular.

Definiciones

• Latencia: Cantidad de ticks en ready hasta que se ejecuta la primera task. Esta métrica se puede extender para ver la latencia promedio de todos los procesos que corrió el scheduler.
• Waiting time: Cantidad de ticks en ready durante toda la ejecución de un proceso.
• Tiempo total de ejecución / Turn around time: Intervalo de ticks desde que se ejecuta un proceso hasta su terminación. No incluye latencia.
• Throughput : Numero de procesos completado por el sistema por unidad de tiempo.