Definición
Se estudiarán las políticas de planificación para un Sistema
Mono-Procesador
Estas son las que posea un solo procesador con un solo núcleo de procesamiento
First In, First Out (FIFO)
Definición
El algoritmo más básico para implementar como política de planificación es el First In, First Out. Ventajas:
Link to original
- Es simple
- Es fácil de implementar
- Funciona bárbaro para las suposiciones
Shortest Job First (SJF)
Definición
Para resolver el problema que se presenta en la política FIFO, se modifica la política para que se ejecute el proceso de duración mínima, una vez finalizado esto se ejecuta el proceso de duración mínima, y así sucesivamente.
Link to original
Shortest time-to-completion (STCF)
Definición
Para poder solucionar este problema que aparecen con la política FIFO y con la política SJF, se necesita relajar la suposiciones que dice que los procesos tienen que terminar hasta el final. La idea es que el planificador o scheduler pueda adelantarse y determinar qué proceso debe ser ejecutado.
Suponiendo que A dura
, y B y C duran , y A llegue en , y B y C llegan segundos después. El scheduler, al ver que llegan B y C puede desalojar al proceso A y poner a ejecutarse a los otros procesos, y cuando terminen, volver a ejecutar a A. Esta política es preemptive
Link to original
Round Robin (RR)
Definición
La idea del algoritmo es bastante simple, se ejecuta un Proceso por un período determinado de tiempo y transcurrido el período se pasa a otro proceso, y así sucesivamente cambiando de proceso en la cola de ejecución.
Lo importante del round robin es la elección de un buen time slice. Se dice que el time slice tiene que amortizar el cambio de contexto sin hacer que esto resulte en que el Sistema no responda más.
Link to original
Multi-Procesador
Estas son aquellas que posea más de un procesador y/o con más de un núcleo de procesamiento.
Multi-Level Feedback Queue (MLFQ)
Definición
Esta técnica de planificación intenta acatar a los siguientes dos problemas
Link to original
- Intentar optimizar el tiempo de turn around, que se realiza mediante la ejecución de la tarea más corta primero, desafortunadamente el sistema operativo nunca sabe a priori cuanto va a tardar en correr una tarea
- Intenta minimizar el tiempo de respuesta, desafortunadamente los algoritmos como round-robin reducen el tiempo de respuesta pero son terribles en turn around.
Proportional share
Definición
Existen otros tipos de algoritmos de planificación que utilizan diferentes mecanismos para realizar esta tarea. Por ejemplo el mecanismo de llamado Proportional-Share, algunas veces también conocido como fair-share. Este se basa en un concepto muy simple: En vez de optimizar el turnaround o el response time el planificador en su lugar intentara garantizar que cada tarea obtenga cierto porcentaje de tiempo de Procesador.
El concepto también es conocido como planificación por lotería la idea básica es muy sencilla. Los boletos, son utilizados para representar cuanto se comparte de un determinado recurso para un determinado proceso. El porcentaje de los boletos que un proceso tiene es el porcentaje de cuanto va a compartir el recurso en cuestión.
Utilizar la aleatoriedad lleva a una correcta visión desde el punto de vista probabilístico pero no garantiza que esa proporción deseada se lleve a cabo. De hecho en el ejemplo anterior no sucede que se ejecute los porcentajes correctos.
Link to original
Cola única
Definición
La forma más fácil para tener un planificador para un sistema multiprocesador es la de reutilizar el marco de trabajo básico para un planificador de monoprocesador.
Entonces se ponen todos los trabajos que tienen que ser planificados en una única cola, que se llamara Single Queue Multiprocessor Scheduling.
Esta forma de plantear la planificación tiene la ventaja de la simplicidad, ya que no requiere mucho trabajo tomar la política existente que agarra la major tarea y la pone a ejecutar y adaptarla para que trabaje con más de una Procesador, sin embargo tiene sus limitaciones
Link to original
- No es escalable
- Tiene problemas con la afinidad del cache
Colas multiples
Definición
Debido a los problemas que tiene el cola única varia gente opto por crear un planificador de multiples colas.
El esquema básico de la planificación consiste en múltiples colas. Cada cola va a seguir una determinada disciplina de planificación, cuando una tarea entra en el sistema ésta se coloca exactamente en una única cola de planificación, de acuerdo con alguna heurística. Esto implica que es esencialmente planificada en forma independiente.
Link to original
Completely Fair Scheduler (CSF)
Definición
El planificador de Linux llamado Completely Fair implementa el que se denomina fair-share scheduling de una forma altamente eficiente y de forma escalable.
Para lograr la meta de ser eficiente, CFS, intenta gastar muy poco tiempo tomando decisiones de planificación, de dos formas, por su diseño y debido al uso inteligente de estructuras de datos para esa tarea
Link to original