Algoritmos de planificación de la CPU.

La multiprogramación es la capacidad del Sistema Operativo de cargar varios programas en la memoria principal los cuales se van alternando el uso de la CPU.
La forma como el Sistema Operativo va alternando la CPU define la eficiencia en el manejo de la CPU respecto a la satisfacción de la ejecución de dichos programas (en realidad procesos).

Algoritmos de planificación.

Imaginemos que tenemos un CPU y un conjunto de procesos que desean ocupar dicho CPU, los algoritmos de planificación nos indican cual proceso y bajo qué condiciones va a ocupar la CPU.

FCFS (First Come First Served):

El primero que llega es atendido, es el algoritmo de planificación más sencillo ya que consiste solamente en ir sirviendo la CPU a los procesos en el orden como van llegando. Cada proceso que llega se forma en una cola al pasar su turno el proceso satisface su requerimiento del CPU y termina su ejecución. Este algoritmo por su comportamiento es del tipo FIFO (First In First Out) para explicar el comportamiento de dicho algoritmo imaginemos que tenemos 3 procesos el proceso P1 que ocupe 24 unidades de tiempo, el proceso P2 que ocupe 4 y el proceso P3 que ocupe 4, y que hayan llegado de forma correspondiente.

FCFS

Como podemos ver la eficiencia del algoritmo FCFS depende del orden en el que van llegando los procesos.

Mayor información:
https://en.wikipedia.org/wiki/First-come,_first-served

SJF (Shortest Job First):

Entonces si la eficiencia del algoritmo FCFS depende del orden esto implica que existe un orden en el cual la eficiencia es óptima, pero… ¿cuál es ese orden optimo?, lo ideal es atender primero a los procesos que requieran menos unidades de tiempo. El algoritmo SJF es una mejora del algoritmo FCFS al ordenar los procesos en la cola en orden ascendente de tal forma que se ejecuten los procesos más ligeros al principio y con esto mejoramos la eficiencia. Como se puede ver en la siguiente imagen:

SJF (Shortest Job First)

SJF (Shortest Job First)

El algoritmo SJF es óptimo, el problema de este algoritmo consiste en el que el Sistema Operativo no siempre sabe cuánto tiempo va a requerir cada proceso, una solución consiste en que el programador de aplicaciones estimule los tiempos de los procesos lo cual a su vez representa ciertas complicaciones.

Round Robin:

Reparte el CPU en unidades de tiempo denominada quantum de tal manera que cada proceso tiene a su disposición el CPU durante un quantum al terminar este tiempo le sede el CPU al siguiente proceso. Si un proceso no concluye su ejecución durante un quantum al finalizar se forma en la cola nuevamente para continuar su ejecución en la siguiente ronda. El concepto de ronda refiere a una iteración en la que a cada proceso se le asigna un quantum. La eficiencia de Round Robin depende en gran medida en el tamaño del quantum que se elija.

Algoritmo de RoundRobin

Algoritmo de RoundRobin

La imagen anterior muestra una implementación de Round Robin en donde cada proceso ocupa un quantum completo sin importar si el proceso ocupa mas o menos tiempo del CPU, siempre se ele asigna un quantum.

Ejercicio:

Calcular el tiempo promedio(tp) para los algoritmos FCFS, SJF y RR(use quantums de 4 unidades), para los siguientes procesos:

  • p0  (15)
  • p1  (25)
  • p2  (3)
  • p3  (10)
  • p4  (8)

Solución:

Veamos la solución:

Código fuente:

Dejo una implementación desarrollada en lenguaje C.