Itineración en Linux

De Departamento de Informatica
Revisión a fecha de 19:20 14 nov 2012; Fvenegas (Discusión | contribuciones)
(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)
Saltar a: navegación, buscar

Contenido

Itineracion

Diagrama de Flujo intinerador linux

El algoritmo de itineración de los Sistemas Operativos tipo UNIX tradicionales debe resolver varias porblematicas: un adecuado tiempo de respuesta de procesos, evitar inanición (starvation) de procesos, un buen rendimiento (throughput) para trabajos en segundo plano (background), etc. La política de scheduling corresponde a las reglas que determinan el cómo y cuándo se hace seleccion de un nuevo proceso.

La itineracion en Linux está basada en la técnica de tiempo compartido (time sharing), soportada por el mecanismo de interrupciones de reloj. Lo que hace es permitir correr varios procesos dividiendo el tiempo de uso de la CPU y multiplexando entre procesos. Estas divisiones del tiempo son asignadas a los procesos ejecutables mediante una serie de reglas; en el caso que un proceso ejecutado actualmente no termina su tarea por falta de tiempo, este queda esperando y la CPU es asignada a otro proceso. Uno de los objetivos del scheduling de Linux es tener un algoritmo de Itineración O(1), es decir, constante en el número de procesos.

La política de scheduling también se basa en el ordenamiento de procesos de acuerdo a su prioridad; la idea es la siguiente: asociar a cada proceso un valor numérico, dicho valor es un indicador para el scheduler de qué tan apropiado es hacer correr el proceso en una CPU. En Linux, la prioridad de los procesos es dinámica ya que se realiza una monitorización de los procesos y ajustando sus prioridades constantemente; por ejemplo, aquellos procesos que no han ocupado la CPU por largo tiempo se les hace un incremento dinámicamente su prioridad. Cuando se trata de scheduling, los procesos pueden ser clasificados en:

  • CPU-bound: Hacen un uso intensivo de tiempo de cómputo, por cuanto requieren mucho tiempo de CPU
  • I/O-bound: Hacen un uso intensivo de dispositivos de entrada/salida y gran parte del tiempo están esperando que se completen dichas operaciones


Se puede contar ademas con otro tipo de distinción, a traves de tres clases de procesos:

  • Procesos Batch

Este tipo de procesos no necesitan interacción con el usuario, por lo cual usualmente corren en segundo plano. Estos procesos por sus caracteristicas no es necesario que cuenten con una respuesta muy rapida por lo cual son "penalizados" por el scheduler. Algunos ejemplos de este tipo son los compiladores de lenguajes de programación, los motores de bases de datos, y los programas de cómputos científicos.

  • Procesos de tiempo real

Este tipo de procesos son mas estrictos en cuanto a scheduling, ya que no deben ser bloqueados por procesos que cuenten con una prioridad más baja; deben tener un tiempo de respuesta pequeño garantizado. Algunos ejemplos de este tipo son las aplicaciones de video y audio, controladores de robots, y aquellos que adquieren datos de sensores físicos.

  • Procesos interactivos

Este tipo de procesos tiene una interaccion constante con sus usuarios, lo que los lleva a tener operaciones de E/S. Cuando se recibe input, el proceso debe ser despertado rápidamente, de tal manera de que el sistema tenga una pronta respuesta a sus requerimientos. Típicamente, la demora promedio debe ser entre 50 y 150 milisegundos, contando ademas con que la varianza de dichos tiempos debe estar acotada, para que el usuario no crea que el sistema se comporta erráticamente. Algunos ejemplos de este tipo son los shells de comandos, editores de texto y aplicaciones gráficas.


Para el caso del scheduler de Linux 2.5, está implementado sobre la base de la conducta pasada de los procesos de tal manera de decidir si un proceso debe ser considerado interactivo o batch, favoreciendo a los procesos interactivos por sobre los de tipo batch. Además la seleccion del nuevo proceso por ejecutar es independiente del número de procesos.


Los programadores tienen a su disposición una serie de llamadas al sistema referentes a la itineración:

nice() Cambiar la prioridad estática de un proceso convencional
getpriority() Obtener la prioridad estática máxima de un grupo de procesos convencionales
setpriority() Fijar la prioridad estática de un grupo de procesos convencionales
sched_getscheduler() Obtener la política de scheduling de un proceso
sched_setscheduler() Fijar la política de scheduling y la prioridad de tiempo real de un proceso
sched_getparam() Obtener la prioridad de tiempo real de un proceso
sched_setparam() Fijar la prioridad de tiempo real de un proceso
sched_yield() Liberar el procesador voluntariamente sin bloquearse
sched_get_ priority_min() Obtener la mínima prioridad de tiempo real para una política
sched_get_ priority_max() Obtener la máxima prioridad de tiempo real para una política
sched_rr_get_interval() Obtener el valor del quantum para la política de Round Robin
sched_seta inity() Fijar la máscara de afinidad de CPU de un proceso
sched_geta inity() Obtener la máscara de afinidad de CPU de un proceso

El algoritmo de scheduling

El algoritmo de scheduling usado en versiones anteriores de Linux era bastante simple: cuando se debia hacer un cambio de proceso, el kernel revisaba los procesos ejecutables, analizando sus prioridades, y seleccionando el “mejor” proceso para correr. Lo anterior presenta la desventaja de que hay un cierto tiempo desperdiciado en la seleccion del mejor ya que hay una directa dependencia con el número de procesos ejecutables, haciendo que el algoritmo sea costoso en sistemas que tienen corriendo muchos procesos.

El algoritmo de scheduling de Linux 2.5 es mucho más sofisticado, ya que selecciona el proceso para correr en tiempo constante, sin haber dependencia con la cantidad de procesos corriendo, adaptandose también al número de procesadores debido a que cada CPU tiene su propia cola de procesos corriendo. Además, el nuevo algoritmo funciona mejor a la hora de distinguir procesos interactivos y batch. Todo lo anterior repercute en que los usuarios tienen la sensación de que las aplicaciones interactivas tienen mucho mejor respuesta en Linux 2.5 que en las versiones anteriores.

En Linux, cada proceso es siempre planificado con alguna de las siguientes políticas de planificación:

  • SCHED_FIFO procesos de tiempo-real que están bajo el algoritmo First-In, First-Out al mismo nivel de prioridad
  • SCHED_RR procesos de tiempo-real que están bajo el algoritmo Round Robin al mismo nivel de prioridad
  • SCHED_NORMAL Procesos convencionales
  • SCHED_BATCH Procesos convencionales, los cuales se ejecutan cuando el procesador se encuentra inactivo

Un proceso ejecutable se considera elegible para ejecutarse en la CPU cuando todavia le quede tiempo de su cuanto de tiempo; de este modo si un proceso ya agotó dicho tiempo es considerado como caducado y no puede volver a ejecutarse hasta que las otras tareas hayan agotado sus respectivos cuantos de tiempo. El kernel mantiene una lista de todos los procesos ejecutables en una cola de ejecucion; cada procesador mantiene su propia cola de ejecución planificandola de manera independiente; cada cola de ejecucion tiene dos matrices de prioridades llamadas matrices activa y caducada. La primera tiene todas las tareas que todavia disponen de tiempo en su cuanto de tiempo, la segunda contiene aquellos procesos que están caducados. Cada matriz anteriormente mencionada cuanta con una lista de procesos indexados según la prioridad de los procesos

El planificador de Linux además posee la característica de ser expulsivo, lo que quiere decir que si algún proceso es activado con una prioridad superior a la que posee un proceso que se encuentre en ejecución, entonces el proceso en ejecucion es expulsado para dar paso a la ejecucion del nuevo proceso con mayor prioridad. Cuando no existen procesos activos, el planificador ejecuta al proceso inactivo o proceso 0 (idle process o swapper process, proceso con PID = 0)

La prioridad dinámica se calcula con la siguiente fórmula:

prioridad dinámica = max (100, min (prioridad estática – bono + 5,139))

En donde la prioridad estática de un proceso se hereda del proceso padre, y puede modificarse utilizando las llamadas al sistema nice() y setpriority() Además el valor de bono varía entre 0 y 10 dependiendo del tiempo promedio de inactividad del proceso

Un proceso es considerado interactivo si satisface lo siguiente:

prioridad dinámica ≤ 3 - prioridad estática /4 +28

Scheduling de procesos convencionales

Cada proceso convencional tiene su propia prioridad estática, que es un valor usado por el scheduler para ordenar el proceso con respecto a los demás procesos convencionales en el sistema. El kernel representa la prioridad estática de un proceso convencional con un número que va de 100 (la prioridad más alta) a 139 (la prioridad más baja). Nótese que la prioridad estática baja según los valores aumentan. Un nuevo proceso siempre hereda la prioridad estática de su padre. Sin embargo, un usuario puede cambiar la prioridad estática de los procesos de su propiedad pasando algunos “valores de nice” (nice values) a los system calls nice() y setpriority().

Quantum base La prioridad estática determina esencialmente el tiempo de quantum base de un proceso, es decir, la duración de un quantum asignado al proceso cuando ha agotado su tiempo de quantum previo. La prioridad estática y el tiempo de quantum base se relacionan por la siguiente fórmula:

Prioridad estática (PS) Tiempo de quantum base en ms:

(140 – PS) x 20 si PS < 120

(140 – PS) x 5 si PS >= 120


Prioridad de los Procesos

Linux posee un algoritmo de planificacion de procesos que se basa en prioridades, de tal manera valores numericos inferiores poseen las prioridades mas altas; habiendo para ellos dos rangos en los que se separan:

Prioridad y Tiempos Asignados
  • Tiempo real: prioridades con valores comprendidos entre 0 y 99
  • Normal (Nice): prioridades con valores comprendidos entre 100 y 140

El algoritmo de planificación utilizado por Linux se basa en la técnica de compartir tiempo consiste en dividir el tiempo de CPU en trozos o porciones (slice o quantum) y asignarlo entre los procesos activos. La lista de tareas es inexada de acuerdo a las prioridades; a diferencia con otros sistemas, en el caso de Linux este asigna cuantos de tiempo mayores a procesos que posean prioridades mas altas (numericamente con valores menores). El planificador elige para ejecución al proceso con la mayor prioridad. La prioridad posee la caracteristica de ser dinámica, es decir su valor cambia en el tiempo.


Lista tareas indexada de acuerdo a prioridades

Itinerador I/O

Método mediante el cual el sistema operativo decide el orden en el que se envían las peticiones de lectura y escritura al subsistema de disco. Esto ayuda a mejorar múltiples aspectos tales como:

  • Tiempo de búsqueda (seek time) en el disco.
  • Establecer prioridad a las peticiones de E/S de ciertos procesos.
  • Asignar porciones del ancho de banda de lectura del disco a cada proceso.
  • Garantizar que ciertas peticiones se atenderán antes de un tiempo determinado (deadline).

Si no existiera un itinnerador de I/O, las peticiones de disco se enviarian en el orden en que llegaran. lo que generaría muchas perdidas de tiempo, ya que en muchos casos se realizarían movimientos innecesarios de los brazos del disco.

Algunas técnicas que utilizan los itineradores para mejorar el rendimiento son:

  • Fusión de Solicitudes: el itinerador fusiona las peticiones adyacentes, para minimizar el tiempo de búsqueda.
  • Ascensor: el itinerador ordena las peticiones en base a su ubicación física en el disco, y que básicamente se trata de buscar en una dirección tanto como sea posible.
  • Priorización: el itinerador tiene control total sobre cómo se da prioridad a las solicitudes, y puede hacerlo de varias maneras, teniendo en cuenta que debe asegurarse la atencion a todas las peticiones, para evitar la muerte por inanición(starvation).

Itinerador I/O Linux

Desde la versión 2.6 del Kernel de Linux, este incluye múltiples itineradores de I/O, lo que permite un grado de libertad al usuario, sobre que itinerador elegir dependiendo de sus requerimientos.

Los itineradores disponibles son:

  • No-op Scheduler: este itinerador solamente implementa la fusión de solicitudes.
  • Anticipatory IO Scheduler: este es el itinerador predeterminado, el cual implementa la fusión de solicitudes, el ascensor, lectura y escritura por lotes, e intentos de anticipar las solicitudes de lectura, guardando un bit, si se establece a través del algoritmo que próximamente se realizara una petición de lectura sobre la misma información o una información adyacente, lo que busca minimizar los movimientos de los brazos del disco. Este itinerador presenta un desempeño muy irregular en bases de datos.
  • Deadline Scheduler: este itinerador implementa la fusión de solicitudes, el ascensor, e impone una deadline a todas las operaciones, para prevenir el starvation. este itinerador, siempre asigna una mayor prioridad a las operaciones de lectura. Este intierador es ampliamente recomendado para bases de datos.
  • Complete Fair Queueing Scheduler (CFQ): este itinerador implementa la fusión de solicitudes, el ascensor, y trata de dar a todos los usuarios de un dispositivo en particular el mismo número de solicitudes de I/O durante un intervalo de tiempo determinado. Esto debería hacer que sea más eficiente para los sistemas multiusuario. Este es el itinerador por defecto en la última versión de Ubuntu y a partir del kernel 2.6.18 en versiones kernel.org.

Referencias

Bibliografia

  • "Understanding the Linux Kernel", Daniel P. Bovet, Marco Cesati, Tercera Edicion.
  • "Fundamentos de Sistemas Operativos", Silberschatz, Galvin, Gagne, Séptima Edición, 2005.
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas