Programador completamente justo (CFS) y Brain Fuck Scheduler (BFS)

Requisito previo: programación de la CPU 
Completely fair Scheduler (CFS) y Brain Fuck Scheduler (BFS) son dos programadores de procesos diferentes que se utilizan actualmente en Linux. 

Programación de procesos: 
como cualquier programa se carga como proceso en la RAM y luego la CPU ejecuta el proceso de acuerdo con la prioridad del proceso.

 1. Programador completamente justo (CFS):  

• Se basa en el programador de fecha límite de escalera giratoria (RSDL).
• Es el proceso de programación predeterminado desde la versión 2.6.23.
• Manejo elegante de E/S y proceso vinculado a la CPU.

Como sugiere el nombre, divide el tiempo de la CPU entre todos los procesos de manera justa o equitativa. Antes de comprender el CFS, veamos la Programación justa ideal (IFS) de N procesos. Si hay N procesos en la cola de procesos listos, cada proceso recibe (100/N) % del tiempo de CPU según IFS. 

Tomemos cuatro procesos y su tiempo de ráfaga como se muestra a continuación esperando en la cola lista para la ejecución. 

Proceso	Tiempo de ráfaga (en ms)
A	10
B	6
C	14
D	6

Tome un cuanto de tiempo de, digamos, 4 ms. Inicialmente, hay cuatro procesos esperando en la cola de espera para ser ejecutados y, de acuerdo con la programación justa ideal, cada proceso obtiene el mismo tiempo justo para su ejecución (Cuantía de tiempo/N). 

Entonces, 4/4 = 1, cada proceso obtiene 1 ms para ejecutarse en el primer cuanto. Después de la finalización de seis procesos cuánticos, B y D se ejecutan por completo y quedan A y C, que ya se ejecutaron durante 6 ms y su tiempo restante es A = 4 ms y C = 8 ms). 

En el séptimo cuanto de tiempo, A y C se ejecutarán (4/2 = 2 ms ya que solo quedan dos procesos). Esta es una programación justa ideal en la que cada proceso obtiene la misma cantidad de tiempo sin importar la prioridad que tenga. 

A continuación se muestra la descripción de la tabla del IFS. 
P: representa el cuanto de tiempo que es de 4 ms. 

Proceso	Q1	Q2	Q3	Q4	Q5	P6	P7	P8	Q9
A	1	1	1	1	1	1	2	2	–
B	1	1	1	1	1	1	–	–	–
C	1	1	1	1	1	1	2	2	4
D	1	1	1	1	1	1	–	–	–

CFS es similar a la programación basada en ideales, en lugar de priorizar cada proceso de acuerdo con el tiempo de ejecución virtual. 

Idea detrás de CFS –  

• Cada proceso ejecutable tiene un tiempo virtual asociado en PCB (bloque de control de proceso).
• Cada vez que ocurre un cambio de contexto (o en cada punto de programación), el tiempo virtual del proceso en ejecución actual aumenta en virtualruntime_currprocess+=T. 
  donde T es el tiempo durante el cual se ejecuta recientemente.
• Por lo tanto, el tiempo de ejecución del proceso aumenta monótonamente.

Entonces, inicialmente, cada proceso tiene un tiempo virtual de inicio (puede buscar en Google cómo se calcula inicialmente el tiempo de ejecución virtual). 

CFS es un algoritmo bastante simple para la programación de procesos y se implementa utilizando árboles RED BLACK y no colas. 
Entonces, todos los procesos que están en la memoria principal se insertan en los árboles Red Black y cada vez que llega un nuevo proceso, se inserta en el árbol. Como sabemos, los árboles Red Black son árboles de búsqueda binarios autoequilibrados. 

En C++, podemos usar mapas en STL ya que se implementan usando árboles rojos y negros. 

Ahora, cada vez que se produce  un cambio de contexto :

• El tiempo virtual para el proceso actual que se estaba ejecutando se actualiza como se explicó anteriormente.
• Se decide el nuevo proceso que tiene el tiempo virtual más bajo y que sabemos que queda más Node del árbol Rojo Negro.
• Si el proceso actual aún tiene tiempo de ráfaga, se inserta en el árbol Rojo Negro.

Entonces, de esta manera, cada proceso obtiene el tiempo justo para la ejecución, ya que después de cada cambio de contexto, el tiempo virtual de un proceso aumenta y, por lo tanto, la prioridad se baraja. 

Análisis de Complejidad Temporal del CFS –  

1. La inserción en árboles rojos y negros toma O (logn).
2. Encontrar el Node con el tiempo virtual más bajo es O(1) ya que podemos mantener un puntero (en los mapas podemos usar auto it=map.begin()).

So overall time complexity is O(logn) 

Aquí se crea una vez el árbol rojo y negro y luego tenemos un proceso de árbol rojo y negro de N. Por lo tanto, la complejidad del tiempo de programación es O (logn). 

También hay una ventaja de usar RED Black Trees, es decir, si un proceso está vinculado a E/S, su tiempo virtual será mucho menor y aparecerá como el Node más a la izquierda en el Red Black Tree, por lo que se ejecutará primero. Por lo tanto, CFS determina fácilmente los procesos que están vinculados a E/S y cuáles están vinculados a la CPU y le da una mayor prioridad al proceso vinculado de E/S para evitar la inanición. 

2. Brain Fuck Scheduler (BFS): 
A diferencia del programador CFS, BFS es un programador O(n) que usa una lista doblemente enlazada que se trata como una cola. 
Por lo tanto, la selección del nuevo proceso en el momento del cambio de contexto puede ser O(n) en el peor de los casos y la inserción del proceso es O(1) a medida que se usa la cola. 

Se utiliza una cola de ejecución global para que toda la CPU tenga acceso a ella. Durante el cambio de contexto, la cola se escanea hasta que se encuentra el mejor proceso con la prioridad más alta y luego se ejecuta. La prioridad se decide en función de la fórmula de fecha límite virtual para cada proceso y se ejecuta en consecuencia. 

Ya no se usa en Linux debido a la sobrecarga del cambio de contexto y también a la complejidad del tiempo O(n).