Planificación de sistemas operativos
Concepto
El término planificación de procesos hace referencia a un conjunto de políticas y mecanismos del SO que gobiernan el orden en que se ejecutan los procesos.
Básicamente el planificador de procesos es un módulo del SO que se encarga de mover los procesos entre las distintas colas de planificación.
La ejecución de un proceso va a alternar entre ráfagas de CPU y ráfagas de E/S.
● Las ráfagas de CPU son un periodo de tiempo en que un proceso se ejecuta en CPU hasta que se bloquea o termina.
● Las ráfagas de E/S son el periodo de tiempo entre que un proceso hace una llamada bloqueante de E/S (como leer de disco) hasta que llega la interrupción de fin de E/S.
Existen dos tipos de procesos distintos:
1. I/O Bound: Es un tipo de proceso limitado por E/S que pasa más tiempo haciendo E/S que usando la CPU (tiene ráfagas de CPU cortas).
2. CPU Bound: Es un tipo de proceso limitado por CPU que pasa más tiempo procesando que haciendo E/S (tiene ráfagas de CPU largas).
Tipos de Planificación de sistemas operativos
El planificador escoge el proceso de entre los que están en memoria listos para ejecutarse y le asigna a la CPU el proceso elegido.
La decisión de replanificación puede ocurrir:
➢ Cuando un proceso deja la CPU voluntariamente (por ejemplo, cuando se bloquea, es decir, hace una llamada de E/S bloqueante). En este caso el planificador es no expropiativo o SIN DESALOJO.
➢ Cuando un proceso entra en la cola de listos (es decir, o porque entro a new, o porque se desbloquea, o porque se desuspende). En este caso el planificador es expropiativo o CON DESALOJO.
Dispatcher
El Dispatcher es un módulo que cede la CPU al proceso elegido por el planificador de la CPU. Para ello el dispatcher tiene que:
● Realizar un cambio de contexto
● Cambiar la máquina a modo usuario (no privilegiado)
● Saltar al punto apropiado del programa para continuar con su ejecución
El tiempo que tarda el dispatcher en detener un proceso y poner otro en ejecución se denomina latencia del dispatcher.
● Debe ser lo más pequeña posible, con el fin de generar el menor overhead posible.
Criterios de planificación
● Utilización de la CPU –> mantener la CPU tan ocupada como sea posible (maximizar)
● Rendimiento –> número de procesos que se completan por unidad de tiempo (maximizar)
● Tiempo de retorno –> tiempo transcurrido desde que se presenta el proceso hasta que se completa (minimizar)
● Tiempo de espera –> tiempo que un proceso pasa en la cola de procesos listos esperando la CPU (minimizar)
● Tiempo de respuesta –> tiempo que tarda un proceso desde que se le presenta una solicitud hasta que se produce la primera respuesta (minimizar / hacerlo previsible). Esto es lo que más le importa al usuario, la velocidad en el tiempo de respuesta.
Algoritmos de planificación
FCFS / FIFO
En esta imagen podemos ver que si los procesos llegaban en otro orden, por ejemplo, P2->P3->P1, entonces el tiempo de espera medio hubiera sido MUCHO menor.
Otro ejemplo de FIFO:
Aclaración: Cuando P1 sale de estar bloqueado, se va a seguir ejecutando, no vamos a pasar a ejecutar P3. ¿Por qué pasa esto? Porque P1 se desbloquea a través de una interrupción y P3 llegó de NEW, es decir, no estaba en la cola de listos, sino que estaba por ingresar en esta.
El tema en FIFO es que la CPU no controla qué proceso le entra primero, va ejecutando en el orden en que van ingresando, por eso mismo se lo llama así. Este algoritmo tiene el menor overhead posible, pero la contra es que no optimiza nada.
SJF – Shortest Job First
Este algoritmo asigna la CPU al proceso cuya siguiente ráfaga de CPU es más corta. Si dos procesos empatan se resuelve el empate por FIFO.
Tiene dos posibilidades:
● Sin desalojo: Cuando se asigna la CPU a un proceso no se puede desalojar hasta que complete su ráfaga de CPU.
● Con desalojo: Si llega un proceso a la cola de listos con una ráfaga de CPU más corta que el tiempo restante, lo desaloja.
SJF es óptimo, da el mínimo tiempo de espera medio para un conjunto de procesos dado. Requiere conocer de antemano la duración de la siguiente ráfaga de CPU.
Puede producir starvation, ¿qué significa esto?, significa que puede generar que un proceso nunca se ejecute por tener este una ráfaga de CPU larguísima.
Lo que pasa con el SJF, es que no sabemos cuántas ráfagas de tiempo se van a ejecutar, no tenemos la bola de cristal, por ende lo que hacemos es estimar, ¿y cómo vamos a estimar?, usando la duración de las ráfagas anteriores, lo que nos lleva a sacar un promedio exponencial:Ejemplo de SJF con estimación:
Llegado este punto podemos decir que SJF es un algoritmo prioritario, ya que va eligiendo el proceso que va a pasar a ejecutarse de acuerdo a la duración predicha para la siguiente ráfaga de CPU.
Los algoritmos con prioridad asocian a cada proceso con una prioridad (número entero), valga la redundancia.
● La CPU se asigna al proceso con la prioridad más alta
Como dijimos antes, el problema que tenía el SJF es la inanición (starvation). Ante este problema, lo que nosotros podríamos aplicar es una solución llamada aging (envejecimiento), en donde conforme el tiempo pasa, aumentaremos la prioridad de los procesos que esperan mucho en el sistema.
El aging da lugar al siguiente algoritmo.
HRRN (Highest Response Ratio Next)
Este algoritmo elimina POR COMPLETO la inanición (starvation). Su nombre indica su comportamiento, se prioriza a los procesos con mayor RR (Response Ratio).
● R.R. = (S + W) / S = 1 + (W / S)
● S = Tiempo de servicio (próxima ráfaga)
● W = Espera
Cuanto mayor sea la espera, respecto al tamaño de su ráfaga, mayor será su prioridad para ejecutar.
Ejemplo de HRRN:
Todos los algoritmos anteriores que vimos tienen un problema -> Existen procesos que pueden monopolizar la CPU, es decir que por ejemplo se pueden llegar a ejecutar solo los procesos con ráfagas de CPU más cortas. Este problema nos lleva al siguiente algoritmo.
Round Robin
● Cada proceso obtiene la CPU durante un breve espacio de tiempo (cuanto o quantum de tiempo). Cuando el tiempo pasa, el proceso es expropiado e insertado al final de la cola de listos.
● Si hay n procesos en la cola de listos y el quantum es q, cada proceso recibe 1/n del tiempo de CPU en intervalos de q unidades de tiempo como mucho. Ningún proceso espera más de (n-1)q unidades de tiempo.
● ¿Qué tamaño debería tener el quantum?
Ni muy pequeño porque se generaría mucho overhead, ni muy grande porque se convertiría en un algoritmo FIFO. El Quantum debe ser de un tamaño considerable.
Virtual Round Robin
Lo que ocurre en el RR es que se priorizan más los CPU Bound que a los I/O Bound, los cuales generalmente suelen tener ráfagas más cortas. A diferencia del Round Robin común, lo que va a hacer el VRR es darle más importancia a los I/O Bound, priorizarlos un poco más.
En el Virtual Round Robin van a existir dos colas de ready, el ready común y un ready +, que va a ser más prioritario que el anterior.
Supongamos que tenemos un proceso en ready, y el quantum es de Q = 10. En el momento de ejecutar un proceso, este ejecuta solo 2 ráfagas y se bloquea, entonces lo que va a suceder, es que este proceso luego de que se desbloquee va a ir a la cola de ready+ con un quantum de 8, ¿Y por qué 8?, porque se le va a restar el quantum dado (10) con las ráfagas que usó antes de bloquearse (2).
En el caso de que el quantum que ese proceso haya usado sea de 10 y se bloquee, cuando se desbloquee va a pasar a la cola de ready común, ya que no tendría sentido mandarlo a la cola ready+ con un quantum de 0.
Colas Multinivel
● Feedback / Retroalimentadas
Virtual Round Robin vendría a ser un ejemplo de una cola multinivel retroalimentada.
La diferencia con el algoritmo anterior radica en la cantidad de colas que hay, en donde los procesos van a ir moviéndose entre colas de acuerdo a la prioridad que se les dé a cada uno.
Es importante saber que cada proceso cuando llegue va a entrar primero por la primera cola, en el caso del ejemplo de abajo, ready RR 2, y después va a ir moviéndose entre colas (o no).
Ejemplo de cola multinivel retroalimentada:
● Prioridades absolutas / No retroalimentadas
La diferencia con las colas multinivel retroalimentadas, es que en las no retroalimentadas la idea no va a ser ir moviendo a los procesos entre colas, sino que a cada proceso se le va a predefinir la cola a la que va a ir, ya sea por el tipo del mismo, por su prioridad, etc.
Cada cola va a tener su quantum propio. Ejemplo ilustrativo:
ULTs
● ULTs sin jacketing Ejemplo:
Hay algo a lo que le tenemos que prestar muchísima atención, cuando el hilo U21 se ejecuta y luego se bloquea con un bib_f_open (), la próxima instrucción a ejecutar pasa a ser replanificar (), ¿y por qué pasa esto? Porque justamente la biblioteca nos permite hacerlo, sin continuar si o si con la instrucción_2 () del U21, ¿y cuál es el fin de replanificar en esta parte? No darle toda la prioridad a un solo hilo ULT, en este caso, el U21, y poder tener la chance de pasar a ejecutar el ULT U22.
En el caso de que en vez de ejecutar bib_f_open (), hubiéramos ejecutado simple y llanamente f_open (), lo que hubiera ocurrido es que el PC quedaría apuntando a la instrucción_2 () del U21, lo cual haría que este se siga ejecutando una vez que el KLT K20 se desbloquee.
IMPORTANTE: En ULTs SIN JACKETING, si uno de los ULTs se bloquea, se bloquea todo el KLT, ya que el S.O toma al proceso como si fuera el KLT, debido a que no conoce a los ULTs.
● ULTs con jacketing
¿Qué es jacketing (o enchaquetamiento)? En resumidas cuentas usar jacketing significa hacer llamadas bloqueantes como no bloqueantes.
o La biblioteca de hilos además de proveerme funciones como bib_f_open (), me provee funciones no bloqueantes. Esto quiere decir que si yo tengo un KLT, y este a su vez está ejecutando dos ULTs, si uno de ellos se ejecuta y después de X ráfagas de CPU se bloquea, con jacketing esto genera que el KLT NO SE BLOQUEE, por lo que podría seguir ejecutándose el otro ULT.
o La diferencia entre ULTs con jacketing y KLTs, es que por más que yo tenga
30.000 núcleos nunca voy a poder ejecutar ULTs en paralelo, mientras que entre KLTs si puedo.
o En los ULTs con jacketing, también se puede replanificar.
Lo malo de usar jacketing es que si se están ejecutando dos ULTs de un KLT1 y yo tengo otro KLT2, si los ULTs del KLT1 no se encuentran ambos bloqueados, entonces no van a tener ningún motivo como para bloquear al KLT1, por lo que el KLT2 se podría no ejecutar nunca.