Round Robin (Apropiativo)

Es un método para seleccionar todos los elementos en un grupo de manera equitativa y en un orden racional, normalmente comenzando por el primer elemento de la lista hasta llegar al último y empezando de nuevo desde el primer elemento.

El nombre del algoritmo viene del principio de Round-Robin conocido de otros campos, donde cada persona toma una parte de un algo compartido en cantidades parejas.

Una forma sencilla de entender el Round-robin es imaginar una secuencia para "tomar turnos". En operaciones computacionales un método para ejecutar diferentes procesos de manera concurrente, para la utilización equitativa de los recursos del equipo, es limitando cada proceso a un pequeño período (quantum), y luego suspendiendo este proceso para dar oportunidad a otro proceso y así sucesivamente.

En este algoritmo de planificación cada proceso tiene un quantum (es un rango de tiempo), una regla general sobre este quantum es que tiene que ser mayores a las ráfagas de CPU pues si la ráfaga es menor al quantum el proceso termina antes del quantum y se planifica nuevamente, y si la ráfaga es mayor, se saca de la CPU y se pasa a otro proceso. El rendimiento depende del quantum pues solo existe una cola de trabajo.

Este algoritmo siempre debe ir de la mano de otro algoritmo de ordenamiento, ya que solo no puede funcionar.

Ejemplo:

Con un quantum de 4

Por último se tiene un vídeo explicativo del algoritmo Round Robin, en donde se evidencia un ejercicio. 

SRT (Apropiativo)

Significa  Shortest - Remaining -Time (El tiempo restante más corto) es una versión con adquisición de prioridad (SPN), en ella el planificador siempre elige el proceso que tiene el tiempo restante de procesamiento esperado más corto: Cuando un nuevo proceso se integra a la cola de listos, puede tener un tiempo restante más corto que el del proceso que corre en ese momento. SPN= Shortest Process Next (El proceso más corto sigue)

Por lo tanto, el planificador puede dar preferencia cuando un nuevo proceso está listo. Al igual que con SPN, el planificador debe estimar el tiempo de procesamiento para ejecutar la función de selección, aquí hay un riesgo de inanición de proceso largos, entendiéndose por inanición la postergación indefinida. Inanición: cuando a un proceso se le niega el acceso a un recurso. Sin este recurso, la tarea a ejecutar no puede ser nunca finalizada

SRT también dará un desempeño de tiempo total superior al de SPN (Shortest Process Next) porque a un trabajo corto se le conoce preferencia inmediata sobre un trabajo más largo que está corriendo.

En resumen: 

-       Ofrece un buen tiempo de respuesta.

-       La productividad es alta a cambio de la sobrecarga del sistema (a cada paso debe decidir a qué proceso asignarle la CPU).

-       Penaliza los procesos largos.

-       Se puede producir inanición.

Por último se tiene un vídeo explicativo del algoritmo SRT, en donde se evidencia un ejercicio. 

SJF (No apropiativo)

SJF, significa  (Short Job First – El trabajo más corto primero) se refiere al proceso que tenga el próximo ciclo de CPU más corto. La idea es escoger entre todos los procesos listos el que tenga su próximo ciclo de CPU más pequeño, que asocia a cada proceso la longitud de la siguiente ráfaga de CPU de ese proceso. Cuando la CPU queda disponible, asigna al proceso cuya siguiente ráfaga de CPU sea más corta. Si hay dos procesos cuyas siguientes ráfagas de CPU tienen la misma duración, se emplea planificación FiFo

Puede comprobarse que el algoritmo SJF es óptimo, ya que ofrece el menor tiempo promedio para un conjunto de procesos dados.

Este algoritmo presenta una gran ventaja, pues el tiempo de espera será mucho menor, pues mientras los procesos de tiempo inferior terminan y ocupan tiempo en operaciones de E/S, el CPU se ocupa de resolver el proceso con mayor tiempo.

Este algoritmo puede ser preemptive y nonpreemptive. En el caso depreemptive, cuando un proceso llega a la cola de procesos listos, su prioridad es comparada con la prioridad del proceso que está corriendo. Si la prioridad del nuevo proceso es mayor, entonces se atiende al nuevo proceso

Ejemplo: 

1. Se tiene el siguiente listado de tareas

2. Se empiezan a ingresar las tareas para ser procesadas, escogiendo la tarea mas corta (cual aplica para todas las tareas), por lo tanto se ingresa la T3, con un tamaño de 8 

3. Luego se ingresa la tarea T4, esta tiene un tamaño de 9, mas los 8 ocupados por T3, para un total de 17. 

4. Posteriormente se ingresa T1 con un tamaño de 12, mas los 17 ya ocupados por T3 y T4, para un total de 29. 

5. Ahora se ingresa la T5, la cual ocupa 13, mas los 29 ya ocupados por las tareas ingresadas 

anteriormente, serian 42.

6. Por último entra T2, con 15 de tamaño, mas el tamaño de las tareas previamente ingresadas, son 57

7. Luego se suman todos los tamaños de cuando son procesadas las tareas: 

8 + 17 + 29 + 42 + 57 = 153

y para hallar el tiempo promedio de ejecución, se toma el resultado de la suma y se divide en la cantidad de tareas que ingresaron. 

153 / 5 = 30.6

Por último se tiene un vídeo explicativo del algoritmo SJF, en donde se evidencian algunos ejercicios. 

FiFo (No apropiativo)

Consiste en atender a los tareas por estricto orden de llegada a la lista de tareas, como su siglas lo indican (First in, First out - Primero en entrar, Primero en salir), Cuando una tarea está siendo procesada, se ejecuta hasta terminar, o hasta que hace una llamada bloqueante. 

Se puede decir que es justo en la lógica, de que si llega una tarea primero, esta se ejecute antes que otra que llega en tercer lugar, pero a la vez es injusto en cuanto a que las tareas largas hacen esperar a las cortas y las tareas sin importancia hacen esperar a las importantes y esto desencadena que no puede garantizar buenos tiempos de respuesta, por lo tanto rara vez se usa como esquema principal en los sistemas actuales, pero puede presentarse en un segundo plano, por ejemplo, muchos esquemas de planificación despachan las tareas de acuerdo con la prioridad, pero los procesos con la misma prioridad se despachan de acuerdo con el esquema FiFo. 

El tiempo promedio de servicio es muy variable ya que está en función del número de procesos y la duración promedio que tenga.

Ejemplo: 

1. Se tiene el siguiente listado de tareas

2. Se empiezan a ingresar las tareas para ser procesadas, se ingresa la T1, con un tamaño de 12 

3. Luego se ingresa la tarea T2, esta tiene un tamaño de 15, mas los 12 ocupados por T1, para un total de 27. 

4. Posteriormente se ingresa T3 con un tamaño de 8, mas los 27 ya ocupados por T1 y T2, para un total de 35. 

5. Ahora se ingresa la T4, la cual ocupa 9, mas los 35 ya ocupados por las tareas ingresadas 

anteriormente, serian 44.

6. Por último entra T5, con 13 de tamaño, mas el tamaño de las tareas previamente ingresadas, son 57

7. Luego se suman todos los tamaños de cuando son procesadas las tareas: 

12 + 27 + 35 + 44 + 57 = 175 

y para hallar el tiempo promedio de ejecución, se toma el resultado de la suma y se divide en la cantidad de tareas que ingresaron. 

175 / 5 = 35 

Por último se tiene un vídeo explicativo del algoritmo FiFo, en donde se evidencian algunos ejercicios.