1.6.2 Despachador(Scheduler).

Schedulling.-
Colas de Schedulling: Los procesos que están en estado de espera se quedan en una lista llamada lista o cola de ready. Los procesos que hacen uso de E/S se guardan en una cola de E/S. Hay una cola de E/S por cada dispositivo.
Schedullers: Componente del sistema operativo responsable de decidir quien hara uso de la CPU.
Algoritmos de Schedulling.-
FCFS (First Come First Served)
Cuando un proceso llega a la cola de ready su PCB es agregado al final de la lista. El uso de la CPU es otorgado al primero de la lista y una vez que un proceso comienza a ejecutar no deja de hacerlo hasta que se termina. El tiempo medio de espera para este algoritmo suele ser bastante alto.
SJF (Shortest Job First)
Una vez que un proceso ejecuta no deja de hacerlo hasta que voluntariamente cambia de estado (no hay interrupción por tiempo). Asocia a cada proceso el tiempo de CPU que habrá de usar en su próxima vuelta y va a decidir por el más pequeño. Si hubiera mas de uno utiliza FCFS para desempatar. El mayor problema de este algoritmo radica en el cálculo de tiempo de uso de CPU. Este se puede aproximar a:
Tn+1=a .tn+(1-a )Tn
0<a <1 Tiempo calculado en la vuelta n
Próximo uso de CPU Tiempo usado en la vuelta n
El problema de este algoritmo es que el tiempo de espera para los procesos largos puede ser demasiado largo. Constantemente se están entregando los procesos mas cortos y el más grande nunca será ejecutado.
El FJS se puede subdividir en 2 tipos de algoritmos: PREEMPTIVO o NO PREEMPTIVO
Preemptivo significa que si mientras un proceso se esta ejecutando, entra a la cola de ready un proceso mas corto, el proceso en la cola de ready se apropia de la CPU y comienza su ejecución.
Priority Schedulling
Asocia a cada proceso una prioridad. Luego selecciona el proceso con mas prioridad para desempatar. En caso de que hubieran dos o mas procesos con la misma prioridad, se usa FCFS para desempatar. Hay dos tipo de prioridad en los procesos: la prioridad externa definidas a través del sistema operativo y la prioridad interna definida por el tiempo de uso de la CPU, el control de E/S, etc. Este algoritmo también se puede ejecutar de dos maneras: preemptivo y no preemptivo. El algoritmo soluciona el problema del looping pero el problema es que los procesos con prioridad muy baja tienen chance de no ejecutarse nunca. Para solucionar este problema de espera infinita el envejecimiento de un proceso eleva su prioridad.
Round Robin
Este es un algoritmo basado en FCFS. Trata la cola de ready como una lista circular. Introduce el concepto de "Quantum" o "Time slice" : mayor tiempo de cpu que podrá hacer uso un proceso en cada vuelta. Si el valor del Quantum fuese muy grande, el algoritmo funcionara como un FCFS. Si el Quantum fuera muy chico se produce un overhead por context switch (significa que el Quantum se setea en un tiempo menor al que demora el context switch). Este algoritmo es fuertemente dependiente del Quantum o Time Slice. El Quantum debe ser mayor que el 80% de los tiempos de CPU que hagan uso los procesos, pero no el proceso entero sino por cada burst.
MQS (Multilevel Queue Schedulling)
Este algoritmo parte la cola de ready en un numero de colas n. Luego existe un criterio para clasificar en que cola será colocado un proceso cuando que queda en estado de ready. Cada cola puede manejar su propio algoritmo de schedulling
MFQS (Multilevel Feed Back Queue Schedulling)
Define los siguientes parámetros:

·         Numero de colas

·         Algoritmo de schedulling usado en cada cola

·         Método para decidir a que cola entrara un proceso cuando entre a estado de ready

·         Método para decidir cuando un proceso será enviado a una cola de menor prioridad.

Múltiple CPU
Para que mas de una CPU no tomen el mismo proceso de la cola de ready se utilizan mecanismos de sincronización. Otro mecanismo seria partir la cola en n colas (n CPUs), pero si se hiciera esto podría llegar a suceder que los procesos de una CPU fueran todos cortos y los de otra fueran largos por lo cual habría una CPU que quedaría libre y otra ejecutando. Otra forma sería que una CPU decidiera cual CPU va a ejecutar cual proceso. Esto puede llevar a que la CPU que esta seleccionando quede un poco mas cargada porque en algún momento estará ejecutando el algoritmo de selección y un proceso asignado a ella.