Algoritmos de Planificacion
Los algoritmos de planificación se encargan de asegurar que un proceso no monopoliza el procesador. Un proceso es un programa que está en ejecución. Este proceso puede estar en 3 estados distintos "Listo" "Bloqueado" y "En Ejecución". Los procesos son almacenados en una lista junto con la información que indica en qué estado está el proceso, el tiempo que ha usado el CPU, etc.
Algoritmo de planificación FCFS
El algoritmo de planificación FCFS (First-Come, First-Served) es uno de los más simples y fáciles de entender. Como su nombre indica, este algoritmo asigna el tiempo de procesamiento a los procesos en el orden en que llegan al sistema operativo. Es decir, el primer proceso que llega es el primero en ser atendido, seguido por el segundo proceso, el tercero, y así sucesivamente.
La principal ventaja del algoritmo FCFS es su simplicidad. Es fácil de implementar y comprender, y no requiere ningún tipo de estimación de tiempo para los procesos. Sin embargo, esta simplicidad también es su mayor desventaja. Debido a que el algoritmo FCFS no tiene en cuenta la duración del proceso, puede llevar a una baja utilización del procesador y a un retraso en los procesos más largos. Además, si un proceso muy largo llega al sistema operativo, puede bloquear todos los demás procesos que esperan para ser atendidos.
ejercicio
Supongamos que tenemos tres procesos listos para ejecutarse con los siguientes tiempos de llegada (arrival time) y tiempos de ejecución (burst time):
Proceso P1:
- Tiempo de llegada: 0
- Tiempo de ejecución: 8
Proceso P2:
- Tiempo de llegada: 1
- Tiempo de ejecución: 4
Proceso P3:
- Tiempo de llegada: 2
- Tiempo de ejecución: 6
Usando el algoritmo FCFS, los procesos se ejecutarán en el orden en que llegaron. Aquí está el diagrama de Gantt y los tiempos de espera para cada proceso:
Proceso Tiempo de llegada Tiempo de ejecución Tiempo de inicio Tiempo de finalización Tiempo de espera
P1 0 8 0 8 0
P2 1 4 8 12 7
P3 2 6 12 18 10
- Tiempo de espera promedio: (0 + 7 + 10) / 3 = 5.67 unidades de tiempo
- En este ejemplo, los procesos se ejecutan en el orden en que llegaron (FCFS). Aunque P2 llegó después de P1, tiene un tiempo de espera más largo debido a que P1 tenía un tiempo de ejecución más largo y se ejecutó primero. Esto ilustra una de las desventajas del algoritmo FCFS: puede conducir a tiempos de espera prolongados para procesos con tiempos de ejecución más cortos que llegan después de procesos con tiempos de ejecución más largos.
Algoritmo de planificación SJF
El algoritmo de planificación SJF (Shortest Job First) es uno de los más populares y efectivos. En este algoritmo, el procesador asigna el tiempo de procesamiento al proceso que tenga la duración más corta. Es decir, se da prioridad a los procesos más cortos.
La principal ventaja del algoritmo SJF es su eficiencia. Este algoritmo asegura que el procesador siempre esté procesando el proceso más corto disponible, lo que lleva a una alta utilización del procesador y una respuesta rápida del sistema. Sin embargo, el algoritmo SJF también tiene una desventaja: es difícil de implementar en un sistema real, ya que requiere información precisa sobre la duración de los procesos. Además, este algoritmo puede llevar a un fenómeno conocido como «inanición», en el que los procesos más largos nunca se ejecutan si hay suficientes procesos más cortos para mantener al procesador ocupado.
ejercicios
Supongamos que tenemos tres procesos listos para ejecutarse con los siguientes tiempos de llegada (arrival time) y tiempos de ejecución (burst time):
Proceso P1:
- Tiempo de llegada: 0
- Tiempo de ejecución: 6
Proceso P2:
- Tiempo de llegada: 1
- Tiempo de ejecución: 4
Proceso P3:
- Tiempo de llegada: 2
- Tiempo de ejecución: 8
Usando el algoritmo SJF, ordenamos los procesos según su tiempo de ejecución y los ejecutamos en ese orden. Aquí está el diagrama de Gantt y los tiempos de espera para cada proceso:
Proceso Tiempo de llegada Tiempo de ejecución Tiempo de inicio Tiempo de finalización Tiempo de espera
P2 1 4 1 5 0
P1 0 6 5 11 5
P3 2 8 11 19 9
- Tiempo de espera promedio: (0 + 5 + 9) / 3 = 4 unidades de tiempo
En este ejemplo, los procesos se ejecutan en el orden de P2, P1 y P3. Aunque P3 llegó después de P2 y P1, se ejecutó después debido a su mayor tiempo de ejecución. Esto muestra cómo el algoritmo SJF minimiza el tiempo de espera promedio, ya que prioriza la ejecución de los procesos más cortos primero. Sin embargo, puede llevar a la inanición de los procesos más largos si constantemente llegan procesos cortos.
Algoritmo de planificación Round Robin
El algoritmo de planificación Round Robin es un enfoque diferente al de los algoritmos FCFS, SJF y SRTF. En este algoritmo, cada proceso recibe un tiempo de procesamiento limitado, conocido como «quantum». Cuando se agota el tiempo de procesamiento de un proceso, se suspende y se da paso al siguiente proceso. Si un proceso no se completa antes de que se agote su tiempo de procesamiento, se mueve al final de la cola y se le da otra oportunidad para ejecutarse en su próximo turno.
La principal ventaja del algoritmo Round Robin es que asegura una distribución equitativa del tiempo de procesamiento entre todos los procesos. Además, como cada proceso recibe un tiempo de procesamiento limitado, ningún proceso puede bloquear el procesador indefinidamente. Sin embargo, el algoritmo Round Robin también tiene una desventaja: puede llevar a una latencia adicional debido al tiempo de cambio de contexto. Es decir, el tiempo que se tarda en cambiar de un proceso a otro puede ralentizar el sistema.
ejercicios
Supongamos que tenemos tres procesos listos para ejecutarse con los siguientes tiempos de llegada (arrival time) y tiempos de ejecución (burst time):
Proceso P1:
- Tiempo de llegada: 0
- Tiempo de ejecución: 5
Proceso P2:
- Tiempo de llegada: 1
- Tiempo de ejecución: 4
Proceso P3:
- Tiempo de llegada: 2
- Tiempo de ejecución: 2
Usando el algoritmo Round Robin con un quantum de tiempo de CPU de 3 unidades de tiempo, aquí está el diagrama de Gantt y los tiempos de espera para cada proceso:
Proceso Tiempo de llegada Tiempo de ejecución Tiempo de inicio Tiempo de finalización Tiempo de espera
P1 0 5 0 3 0
P2 1 4 3 6 2
P3 2 2 6 8 4
- Tiempo de espera promedio: (0 + 2 + 4) / 3 = 2 unidades de tiempo
En este ejemplo, cada proceso recibe un tiempo de CPU de hasta 3 unidades de tiempo (quantum) antes de ser interrumpido y colocado en la parte posterior de la cola de listos. Esto se repite hasta que todos los procesos hayan completado su tiempo de ejecución. El algoritmo Round Robin garantiza que ningún proceso tenga que esperar indefinidamente y ofrece una distribución justa de la CPU entre los procesos. El tiempo de espera promedio es relativamente bajo en este caso debido a la naturaleza corta de los tiempos de ejecución de los procesos.