Comparación de diferentes algoritmos de programación de CPU en el sistema operativo

Se utiliza un algoritmo de programación para estimar el tiempo de CPU necesario para asignar a los procesos y subprocesos. El objetivo principal de cualquier algoritmo de programación de CPU es mantener la CPU lo más ocupada posible para mejorar la utilización de la CPU.

Algoritmos de programación

1. First Come First Serve (FCFS) : como su nombre lo indica, los trabajos se ejecutan por orden de llegada. Es un algoritmo simple basado en FIFO que es el primero en entrar, el primero en salir. El proceso que viene primero en la cola de listos puede acceder primero a la CPU. Si el tiempo de llegada es menor, el proceso obtendrá la CPU pronto. Puede sufrir el efecto de convoy si el tiempo de ráfaga del primer proceso es el más largo entre todos los trabajos.

2. El trabajo más corto primero (SJF) : también conocido como el trabajo más corto primero o el trabajo más corto después, es un algoritmo de tipo no preventivo que es fácil de implementar en sistemas por lotes y es mejor para minimizar el tiempo de espera. Sigue las estrategias donde se elige el proceso que está teniendo el menor tiempo de ejecución para la siguiente ejecución.

3. Programación del trabajo más largo primero (LJF) : el trabajo más largo primero (LJF) es la versión no preventiva. Este algoritmo también se basa en el tiempo de ráfaga de los procesos. Los procesos se colocan en la cola de espera de acuerdo con sus tiempos de ráfaga y el proceso con el mayor tiempo de ráfaga se procesa primero.

4. Primera programación del tiempo restante más largo (LRTF) : la versión preventiva de LJF es LRTF. Aquí, el proceso con el tiempo máximo de CPU restante se considerará primero y luego se procesará. Y después de un intervalo de tiempo, comprobará si otro proceso con más tiempo de ráfaga llegó hasta ese momento o no. Si cualquier otro proceso tiene más tiempo de ráfaga restante, entonces el proceso en ejecución será reemplazado por ese proceso.   

5. Tiempo restante más corto primero (SRTF) : este algoritmo se basa en SJF y esta es la versión preventiva de SJF. En este algoritmo de programación, el proceso con el tiempo de ráfaga restante más pequeño se ejecuta primero y puede ser sustituido por un nuevo trabajo que haya llegado con un tiempo de ejecución más corto.

6. Round Robin (RR) : es un algoritmo de programación preventiva en el que a cada proceso se le asigna un tiempo fijo llamado cantidad para ejecutar. En este momento, se permite que un proceso se ejecute durante un cuanto y luego se adelanta y luego se ejecuta otro proceso. De esta forma, existe un cambio de contexto entre procesos para guardar estados de estos procesos reemplazados.

7. Programación prioritaria : Es un algoritmo no preventivo que funciona en sistemas por lotes y cada proceso se le asigna una prioridad y el proceso con la prioridad más alta se ejecuta primero. Esto puede conducir a la inanición de otros procesos.

8. Programación de Colas de Múltiples Niveles : En esta programación, las colas múltiples tienen sus Algoritmos de programación y se mantienen con los procesos que poseen las mismas características. Para ello, se asignan prioridades a cada cola para los trabajos a ejecutar.

9. Multilevel-Feedback-Queue Scheduler : Define varias colas y los algoritmos de programación para cada cola. Este algoritmo se utiliza para determinar cuándo actualizar un proceso, cuándo degradar un proceso y también determinar la cola en la que ingresará un proceso y cuándo ese proceso necesita servicio.

Nota: El algoritmo de programación SJF es hipotético e inimplementable, ya que es imposible determinar el tiempo de ráfaga de cualquier proceso sin ejecutarlo. SJF es un algoritmo de evaluación comparativa, ya que proporciona un tiempo de espera mínimo que cualquier otro algoritmo de programación

Análisis comparativo de diferentes algoritmos de programación de CPU

Aquí hay una breve comparación entre diferentes algoritmos de programación de CPU:

Algoritmo	La asignación es	Complejidad	Tiempo medio de espera (AWT)	Derecho preferente de compra	Inanición	Actuación
FCFS	Según la hora de llegada de los procesos, se asigna la CPU.	No complejo	Largo.	No	No	rendimiento lento
SJF	Basado en el tiempo de ráfaga de CPU (BT) más bajo.	Más complejo que FCFS	Más pequeño que FCFS	No	Sí	Tiempo de espera promedio mínimo
LJFS	Basado en el tiempo de ráfaga de CPU (BT) más alto	Más complejo que FCFS	Dependiendo de algunas medidas, por ejemplo, tiempo de llegada, tamaño del proceso, etc.	No	Sí	Gran tiempo de respuesta
LRTF	Al igual que LJFS, la asignación de la CPU se basa en el tiempo de ráfaga de CPU (BT) más alto. pero es preventivo	Más complejo que FCFS	Dependiendo de algunas medidas, por ejemplo, tiempo de llegada, tamaño del proceso, etc.	Sí	Sí	Se da preferencia a los trabajos más largos.
SRTF	Al igual que SJF, la asignación de la CPU se basa en el tiempo de ráfaga de CPU (BT) más bajo. Pero es preventivo.	Más complejo que FCFS	Dependiendo de algunas medidas, por ejemplo, tiempo de llegada, tamaño del proceso, etc.	Sí	Sí	Se da preferencia a los trabajos cortos.
RR	Según el orden del proceso llega con cuanto de tiempo fijo (TQ)	La complejidad depende del tamaño de TQ	Grande en comparación con SJF y la programación prioritaria.	No	No	Cada proceso ha dado un tiempo bastante fijo
Preferente de prioridad	Según la prioridad. La tarea de mayor prioridad se ejecuta primero	Este tipo es menos complejo.	Más pequeño que FCFS	Sí	Sí	Buen rendimiento pero contiene un problema de inanición
Prioritario no preventivo	Según la prioridad. con el seguimiento de los nuevos trabajos entrantes de mayor prioridad	Este tipo es menos complejo que Prioritario preventivo	preventivo Más pequeño que FCFS	No	Sí	Más beneficioso con los sistemas por lotes
MLQ	Según el proceso que reside en la cola de mayor prioridad	Más complejo que los algoritmos de programación de prioridades	Más pequeño que FCFS	No	Sí	Buen rendimiento pero contiene un problema de inanición
MFLQ	De acuerdo con el proceso de una cola de prioridad más grande.	Es el más complejo pero su tasa de complejidad depende del tamaño de TQ	Más pequeño que todos los tipos de programación en muchos casos	No	No	Buen rendimiento