Todos los sistemas operativos tienen algún tipo de algoritmo de planificación más o menos eficiente que permite a todos los procesos del sistema y del usuario poder hacer uso de la CPU. Un buen algoritmo de planificación debe ser capaz de controlar todos estos parámetros:
+ equitatividad: cada proceso debe recibir su parte justa de CPU y recursos.
+ eficiencia: la CPU debe ser usada todo el tiempo. No desaprovecharla.
+ throughput: producir el mayor numero de trabajos terminados por hora.
+ respuesta: minimizar el tiempo de respuesta en las aplicaciones interactivas.
Manejar todos estos parámetros es muy difícil ya que dentro de un sistema podemos encontrar diferentes tipos de procesos y tareas cada una con sus propias características y necesidades. Por ejemplo, tenemos procesos que utilizan intensamente la CPU y otros que estarían todo el día parados esperando E/S. Por tanto, cuando Linux empieza a ejecutar un proceso, no sabe 100% cuanto tiempo necesitará ese proceso la CPU.
Durante el diseño de sistemas de compartición y scheluding han ido surgiendo diferentes tipos de algoritmos de palanificación:
+ planificación por round-robin: quizás el más conocido y que se estudia más durante la carrera informática. Es uno de los más antiguos y tal vez el más sencillo de implementar y justo. Se basa en mantener una cola o lista de procesos, asignándoles un tiempo de ejecución a cada proceso. Pasado ese tiempo le quitamos al proceso la CPU y se la damoss a otro. Lo más difícil de calcular es el ¿cuanto tiempo?. Si ponemos poco tiempo haremos mucho swaping entre procesos y eso puede ser malo porque podemos perder mucho tiempo en cambiar de contexto. Si decidimos poner mucho tiempo, podemos perjudicar a otros procesos que son muy interactivos con el usuario.
+ planificación por prioridades: consiste en dar una prioridad al proceso. Contra más prioridad tenga un proceso antes utilizará la CPU. Dentro de este tipo de planificación podemos encontrar que las prioridades se pueden asignar estática o dinámicamente.
+ planificación por colas: consiste en tener varias colas donde los procesos alojados en una cola utilizan la CPU X ms., los alojadas en la segunda cola la utilizan 2X ms., y así sucesivamente. Una vez los procesos utilizan todo su tiempo van rotando por las diferentes colas.
+ planificación en tiempo real: quizás estos algoritmos son los más complicados ya que deben asegurar respuestas a posibles eventos. Por ejemplo, un sistema que controle la altura de un vuelo. Si salta la alarma de altura, el proceso que controla este evento tiene que estar dentro de la CPU para poder tomar el control. Una respuesta correcta pero tarde, puede ser peor que no obtener respuesta.
+ otros planificadores: planificación por lotería, planificación garantizada, planificación en varios niveles, etc.
En Linux tenemos una mezcla de varios de los planificadores que he explicado, pero básicamente sería algo como un round-robin con prioridades. En realidad podemos planificar cada proceso con una política diferente. Estas son las políticas de Linux:
+ SCHED_OTHER: en Unix es la planificación clásica. No es aplicable en tiempo real. Examina las prioridades dinámicas (calculadas como combinación de las especificadas por el usuario y las calculadas por el sistema). Los procesos que llevan más tiempo en el sistema van perdiendo prioridad.
+ SCHED_FIFO: El primero en entrar en la cola es el primero en ser servido. Los procesos esperan en cola y se ejecutan secuencialmente. Se sigue calculando un cuanto de tiempo para el proceso, aunque normalmente no se use porque con esta planificación no se fuerza al proceso a abandonar la CPU. Se usa en procesos de tiempo real.
+ SCHED_RR: round-robin. Funciona como el FIFO pero ahora cuando un proceso acaba su cuanto de tiempo (time slice) se le desaloja. El siguiente proceso se escoge de la lista de procesos con SCHED_RR o de la lista SCHED_FIFO. Son procesos en tiempo real.
+ SCHED_YIELD: No es una política de planificación, sino un modificador que afecta a las tres políticas anteriores. El proceso cede la CPU a cualquier otro que esté listo.
Más información:
- Understanding the Linux 2.6.8.1 CPU Scheduler
suscribirse
Hace 8 horas
0 comentarios:
hacer un comentario en esta entrada