Unidad 3
Planificación
© Arnoldo Díaz Ramírez - 2007
Planificación
© Arnoldo Díaz Ramírez - 2007
El planificador es un módulo del sistema operativo que asigna tiempo de CPU a los
procesos activos
A la política que utiliza el planificador para hacer la asignación de tiempo de CPU se
le conoce como algoritmo de planificación o política de planificación
Linux utiliza un algoritmo de planificación que tiene como objetivo una distribución
equitativa del tiempo de CPU entre los procesos activos en el sistema
El algoritmo de planificación utilizado por Linux se basa en la técnica de compartir
tiempo (time sharing) y consiste en dividir el tiempo de CPU en trozos o porciones
(slice o quantum) y asignarlo entre los procesos activos
Clasificación de procesos
© Arnoldo Díaz Ramírez - 2007
Los procesos pueden ser clasificados en:
I/O-bound.- Utilizan intensivamente los dispositivos de entrada/salida (b)
CPU-bound.- Utilizan intensivamente tiempo de cómputo (a)
Instantes de planificación
© Arnoldo Díaz Ramírez - 2007
Un instante de planificación es aquél en el cuál el planificador tiene que
decidirdecidir qué tarea debe ejecutarse
Los instantes de planificación instantes de planificación existen cuando:
ConcluyeConcluye la ejecución la ejecución de un proceso o hilo
Un proceso se bloqueabloquea
Se creacrea un nuevo proceso o hilo
Ocurre una interrupción de I/Ointerrupción de I/O
Ocurre una interrupción de reloj
Algoritmos de planificación
© Arnoldo Díaz Ramírez - 2007
Los algoritmos de planificación pueden ser clasificados en:
Expulsivos.- las tareas pueden ser expulsadas del procesador antes de concluir
su ejecución
No expulsivos.- las tareas NO son expulsadas del procesador antes de concluir
su ejecución
Los procesos, al ser planificados, pueden ejecutarse en alguno de los
siguientes entornos:
Procesamiento por lotes (batch).- No requieren de interacción con el usuario
Interactivos.- Tienen constante interacción con el usuario
Tiempo-real.- Deben ejecutarse en un tiempo determinado y tienen restricciones
temporales que deben satisfacerse
Objetivos de los algoritmos de planificación
© Arnoldo Díaz Ramírez - 2007
Los objetivos de los algoritmos de planificación dependen del tipo de sistema:
Para sistemas por lotes:
Maximizar el número de procesosnúmero de procesos ejecutados por unidad de tiempo
Minimizar el tiempo de respuesta tiempo de respuesta de ejecución de los procesos
Mantener la CPUCPU ocupada la mayor parte del tiempo
Para sistemas interactivos:
Reducir el tiempo de respuestatiempo de respuesta
Cumplir las expectativas de los usuarios
Para sistemas de tiempo-real:
Ejecutar tareas antes de su plazoplazo
Evitar degradación de la calidad en aplicaciones multimediaaplicaciones multimedia
Algoritmos de planificación (1/3)
© Arnoldo Díaz Ramírez - 2007
First-Come First-Served (primero en llegar primero en ser atendido)
No expulsivo
Las tareas son atendidas en el orden en que se activan
Fácil de implementar ya que se necesita tan sólo mantener una lista de tareas activas
Una tarea puede cpu-boundcpu-bound puede retrasar la ejecución de tareas i/o-boundi/o-bound
Sistemas por Lotes
No expulsivo
Se calcula el plan de ejecución off-lineoff-line
Mejora el tiempo de respuesta promedio con respecto al anterior
Shortest Job First (primero la tarea mas corta)
a) First-Come First-Served b) Shortes Job First
Algoritmos de planificación (2/2)
© Arnoldo Díaz Ramírez - 2007
Shortest Remaining Time Next (primero la tarea con menor tiempo de
ejecución restante)
Expulsivo
En cada instante de planificación se elige a la tarea a la que quede el menor tiempo de ejecución
Cuando alguna tarea se activa, se compara su tiempo de ejecución con el tiempo de ejecución restante de la tarea actual, y si es menor el tiempo de ejecución de la nueva tarea la actual es expulsada del procesador
Este esquema permite que las tareas pequeñas tengan un mejor tiempo de respuesta
Sistemas por Lotes
Algoritmos de planificación (3/3)
© Arnoldo Díaz Ramírez - 2007
Three-level scheduling (planificación de tres niveles)
Tiene tres componentes básicos:
planificador de admisión
planificador de CPU
planificador de Memoria
Sistemas por Lotes
¿Cuáles tareas deben ser aceptadas?
¿Cuáles tareas deben pasar de disco a memoria principal?
¿Cuál tarea debe utilizar el procesador?
Algoritmos de planificación (1/4)
© Arnoldo Díaz Ramírez - 2007
Round-Robin
Expulsivo
A cada tarea se le asigna un tiempo máximo de ejecución, llamado quantum
Si alguna tarea consume su quantum, es expulsada del procesador y colocada
al final de la lista de tareas activas
La definición del tamaño del quantum es importante
Sistemas interactivos
a) lista de tareas activas b) lista de tareas activas después de que B ha consumido su quantum
Algoritmos de planificación (2/4)
© Arnoldo Díaz Ramírez - 2007
Priority Scheduling (planificación basada en prioridades)
Expulsivo
A cada tarea se le asigna un nivel de prioridad, que representa su importanciaimportancia
Sistemas interactivos
Las prioridades de las tareas pueden asignarse de manera estática o dinámica
estáticaestática.- la prioridad de cada tarea no cambia durante la ejecución del sistema
dinámicadinámica.- la prioridad de cada tarea puede cambiar durante la ejecución del sistema
Algoritmos de planificación (3/4)
© Arnoldo Díaz Ramírez - 2007
Guaranteed Scheduling (planificación garantizada)
Expulsivo
El algoritmo garantiza la asignación equitativa del tiempo de procesador entre
las tareas
Lleva control del tiempo de CPU utilizado por cada tarea
Lottery Scheduling (planificación lotería)
Expulsivo
El planificador asigna “boletos de lotería” a las tareas
Cada boleto de lotería permite el acceso a un recurso
Una tarea puede tener mas de un boleto para el mismo recurso
Sistemas interactivos
Algoritmos de planificación (4/4)
© Arnoldo Díaz Ramírez - 2007
Fair-Share Scheduling (planificación justa)
Sistemas interactivos
Expulsivo
El algoritmo garantiza la
asignación equitativa del tiempo
de procesador entre los usuarios
El tiempo asignado al usuario es
dividido entre sus tareas
Sistemas de tiempo-real
© Arnoldo Díaz Ramírez - 2007
Un sistema de tiempo-real es evaluado no sólo por la exactitud de sus
resultados, sino también por el tiempo en que los resultados se generan
las tareas de tiempo-real tienen un tiempo límite para concluir su ejecución (plazo o
deadline)
Los sistemas de tiempo-real se clasifican en:
Críticos (hard).- si sus tareas no se ejecutan
antes de sus plazos los resultados son
catastróficos
No Críticos (soft).- se busca que las tareas
se ejecuten antes de sus plazos, pero si no lo
consiguen no existen riesgos
Tareas de tiempo-real
© Arnoldo Díaz Ramírez - 2007
Las tareas de tiempo-real tienen los siguientes parámetros:
ci.- tiempo de ejecución en el peor caso
ri.- tiempo de liberación
ϕi.- fase
pi.- periodo
di.- plazo o deadlinedeadline
Algoritmos de planificación (1/2)
© Arnoldo Díaz Ramírez - 2007
Rate Monotonic
Expulsivo
Estático (el valor de prioridad de las tareas no cambia durante la ejecución del
sistema)
A cada tarea se le asigna un valor de prioridad inversamente proporcional a
su periodo
Sistemas de tiempo-real
la tarea con menor periodo, o la tarea
mas frecuente, es siempre la mas
prioritaria
Utilización máxima del procesador ≤
85%
Algoritmos de planificación (2/2)
© Arnoldo Díaz Ramírez - 2007
Eearliest Deadline First
Expulsivo
Dinámico (el valor de prioridad de las tareas puede cambiar durante la
ejecución del sistema)
En cada instante de planificación cada instante de planificación, la tarea mas prioritaria es la que tenga el
plazo (deadline) menor
Utilización máxima del procesador ≤ 100%
Sistemas de tiempo-real
Planificación en Linux
© Arnoldo Díaz Ramírez - 2007
LinuxLinux utiliza un planificador basado en la noción de prioridad, que indica la
importancia del proceso. Entre mayor sea la prioridad, más importante es el
proceso. El planificador elige para ejecución al proceso con la mayor prioridad
En LinuxLinux, la prioridad de los procesos se asigna de manera dinámica, lo que
significa que su valor cambia en el tiempo
La definición de la prioridadprioridad de un proceso depende del uso de CPU del proceso
en el pasado. Si el proceso ha utilizado poco tiempo de CPU, Linux eleva su valor
de prioridad para que pueda ser ejecutado inmediatamente, buscando así una
distribución equitativa del tiempo de CPU
API POSIX para la planificación
© Arnoldo Díaz Ramírez - 2007
nice() Cambia la prioridad estática de un proceso, grupo o usuario
getpriority() Obtiene la prioridad estática de un proceso, grupo o usuario
setpriority() Establece la prioridad estática de un proceso, grupo o usuario
sched_getscheduler() Obtiene la política de planificación de un proceso
sched_setscheduler() Establece la política de planificación de un proceso
sched_getparam() Obtiene los parámetros de planificación de un proceso (tiempo-real)
sched_setparam() Establece los parámetros de planificación de un proceso (tiempo-real)
sched_yield() Obliga al thread a que ceda el procesador
sched_getpriority_max() Obtiene el máximo valor de prioridad para una política determinada
sched_getpriority_min() Obtiene el mínimo valor de prioridad para una política determinada
sched_rr_get_interval() Obtiene el máximo valor de quatum para la política Round Robin
Algoritmos de planificación Linux
© Arnoldo Díaz Ramírez - 2007
El planificadorplanificador debe decidir cuál es el siguiente proceso por ejecutar
cuando un proceso suspende o concluye su ejecución
El planificador de Linux 2.6 Linux 2.6 selecciona el nuevo proceso por ejecutar en
tiempo constante (independiente del número de procesos)
En Linux, cada proceso es siempre planificado con alguna de las siguientes
políticas de planificación:
SCHED_FIFO.- procesos de tiempo-real que siguen la disciplina First-In, First-Out
al mismo nivel de prioridad
SCHED_RR.- procesos de tiempo-real que siguen la disciplina Round Robin al
mismo nivel de prioridad
SCHED_NORMAL.- Procesos convencionales
SCHED_BATCH.- Procesos convencionales, que se ejecutan cuando el
procesador esta inactivo (staircase scheduler)
Planificación Linux (1/2)
© Arnoldo Díaz Ramírez - 2007
Otra característica del planificador de Linux es que es del tipo expulsivo
(preemptable), lo que significa que si algún proceso se activa con una prioridad
mayor a la del proceso que está ejecución, se expulsa al proceso actual y se
ejecuta al proceso mas prioritario
Cuando no existen procesos activos, el planificador ejecuta al proceso inactivo o
proceso 0 (idle process o swapper process, proceso con PID = 0)
Por otra parte, la duración del quantum de ejecución es crítica para el desempeño
del sistema. Linux asigna una prioridad fija a cada proceso y calcula el valor del
quantum de la siguiente manera:
(140 – prioridad estática) x 20, si la prioridad es < 120quantum =
(140 – prioridad estática) x 5, si la prioridad es ≥ 120
Planificación Linux (2/2)
© Arnoldo Díaz Ramírez - 2007
La prioridad fija de un proceso se hereda del proceso padre, y puede
modificarse utilizando las llamadas al sistema nice() y setpriority()
Por otra parte, Se ha comentado que los procesos son planificados en base a
una prioridad dinámica, cuyo valor varía desde 100 (mas alta prioridad)
hasta 139 (mas baja prioridad)
La prioridad dinámica se calcula con la siguiente fórmula:
prioridad dinámica = max (100, min (prioridad estática – bono + 5,139))
El valor de bono varía entre 0 y 10. Su valor final depende del average sleep
time (tiempo promedio de inactividad) del proceso
Un proceso es considerado interactivo si satisface lo siguiente:
prioridad dinámica ≤ 3 - prioridad estática /4 +28
Funciones de planificación
© Arnoldo Díaz Ramírez - 2007
Algunas de las funciones utilizadas por el planificador son las
siguientes:
scheduler_tick().- mantiene actualizado del tiempo de ejecución del proceso
actual
try_to_wake_up().- activa un proceso dormido
recalc_task_prio().- actualiza la prioridad dinámica de un proceso
schedule().- selecciona al nuevo proceso por ejecutar
load_balance().- mantiene balanceadas las colas de ejecución en sistemas
multiprocesadores
Función schedule() (1/4)
© Arnoldo Díaz Ramírez - 2007
La función inicia inhabilitando la expulsión del núcleo e iniciando algunas variables:
need_resched:
preempt_disable();
prev = current;
release_kernel_lock( prev );
need_resched_nonpreemptible:
rq = this_rq();
Calcula el tiempo de CPU utilizado por prev
now = sched_clock();
if ( likely (( long long )( now – prev->timestamp ) < NS_MAX_SLEEP_AVG)) {
run_time = now - prev->timestamp;
if ( unlikely (( long long )( now – prev->timestamp ) < 0))
run_time = 0;
} else
run_time = NS_MAX_SLEEP_AVG;
run_time /= ( CURRENT_BONUS( prev ) ? : 1 );
Función schedule() (2/4)
© Arnoldo Díaz Ramírez - 2007
Revisa el status de prev:
switch_count = &prev->nivcsw;if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
switch_count = &prev->nvcsw;
if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
unlikely(signal_pending(prev))))
prev->state = TASK_RUNNING;
else {
if (prev->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
deactivate_task(prev, rq);
}
}
Función schedule() (3/4)
© Arnoldo Díaz Ramírez - 2007
Se selecciona siguiente proceso por ejecutar:
cpu = smp_processor_id();if ( unlikely ( ! rq->nr_running ) ) {
go_idle:idle_balance(cpu, rq);if ( ! rq->nr_running ) {
next = rq->idle;rq->expired_timestamp = 0;wake_sleeping_dependent(cpu, rq);if ( ! rq->nr_running )
goto switch_tasks;}
} else {if ( dependent_sleeper(cpu, rq)) {
next = rq->idle;goto switch_tasks;
}if ( unlikely ( ! rq->nr_running ) )
goto go_idle;}
Función schedule() (4/4)
© Arnoldo Díaz Ramírez - 2007
sched_info_switch( prev, next );
if ( likely( prev != next)) {
next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
++*switch_count;
prepare_task_switch( rq, next );
prev = context_switch( rq, prev, next);
barrier();
finish_task_switch(this_rq(), prev);
} else
spin_unlock_irq( &rq->lock );
Se lleva a cabo el cambio de contexto:
switch_tasks:
if ( next == rq->idle)
schedstat_inc(rq, sched_goidle);
prefetch(next);
prefetch_stack(next);
clear_tsk_need_resched(prev);
rcu_qsctr_inc(task_cpu(prev));
update_cpu_clock(prev, rq, now);
prev->sleep_avg -= run_time;
if ((long) prev->sleep_avg <= 0)
prev->sleep_avg = 0;
prev->timestamp = prev->last_ran = now;
Cambio de contexto (1/2)
© Arnoldo Díaz Ramírez - 2007
Es común que algún proceso suspenda su ejecución para reanudarla
posteriormente
El proceso puede suspenderse por que se asigna el procesador a otro proceso
más prioritario, por que el proceso se bloquee en espera de un dispositivo, por
que consuma su quantum de ejecución, por que espere que otro proceso libere
un recurso que necesite, entre otras causas
El núcleo debe garantizar que la ejecución del proceso se reanude en el punto en
el que se suspendió
A la actividad de suspender la ejecución de un proceso para iniciar la ejecución
de otro proceso se le conoce como cambio de contexto (context switch)
Cambio de contexto (2/2)
© Arnoldo Díaz Ramírez - 2007
A pesar de que cada proceso tiene asignado un espacio de direcciones exclusivo,
todos los procesos deben compartir los registros del (los) procesador(es)
Antes de que un proceso reanude su ejecución, el núcleo debe cargar el
contenido de los registros del procesador con los valores que tenían cuando el
proceso fue suspendido
Al conjunto de datos que deben ser cargados en los registros del procesador
antes de que el proceso reanude su ejecución se le llama contexto de hardware
En Linux, parte del contexto de hardware de un proceso es almacenado en el
descriptor del proceso, mientras el resto se almacena en la pila del modo del
núcleo (kernel mode stack)
Contexto de hardware
© Arnoldo Díaz Ramírez - 2007
A pesar de que cada proceso tiene asignado un espacio de direcciones exclusivo,
todos los procesos deben compartir los registros del (los) procesador(es)
Antes de que un proceso reanude su ejecución, el núcleo debe cargar el
contenido de los registros del procesador con los valores que tenían cuando el
proceso fue suspendido
Al conjunto de datos que deben ser cargados en los registros del procesador
antes de que el proceso reanude su ejecución se le llama contexto de hardware
En Linux, parte del contexto de hardware de un proceso es almacenado en el
descriptor del proceso, mientras el resto se almacena en la pila del modo del
núcleo (kernel mode stack)
Cambio de contexto en Linux
© Arnoldo Díaz Ramírez - 2007
El cambio de contexto se define como la actividad consistente en
almacenar el contexto de hardware del proceso que suspende ejecución
y reemplazarlo con el contexto de hardware del proceso que reanudará
la suya
Las versiones anteriores de Linux hacen uso del soporte que ofrecen
algunos procesadores para llevar a cabo el cambio de contexto
A partir de la versión 2.6 de Linux versión 2.6 de Linux, el cambio de contexto se lleva a cabo
por medio de software
El cambio de contextocambio de contexto ocurre únicamente en modo del núcleo
Función context_switch()
© Arnoldo Díaz Ramírez - 2007
static inlinetask_t * context_switch( runqueue_t *rq, task_t *prev, task_t *next){
struct mm_struct *mm = next->mm;struct mm_struct *oldmm = prev->active_mm;
if ( unlikely ( ! mm )) {next->active_mm = oldmm;atomic_inc ( &oldmm->mm_count );enter_lazy_tlb ( oldmm, next );
} elseswitch_mm ( oldmm, mm, next );
if ( unlikely ( ! prev->mm ) ) {prev->active_mm = NULL;WARN_ON(rq->prev_mm);rq->prev_mm = oldmm;
}/* Here we just switch the register state and the stack. */switch_to(prev, next, prev);return prev;
}
Algoritmos de planificación POSIX
© Arnoldo Díaz Ramírez - 2007
Por otra parte, POSIX define las siguientes políticas de
planificación:
SCHED_FIFO.- procesos de tiempo-real que siguen la disciplina First-In, First-
Out al mismo nivel de prioridad
SCHED_RR.- procesos de tiempo-real que siguen la disciplina Round Robin al
mismo nivel de prioridad
SCHED_OTHER.- Procesos convencionales
SCHED_SPORADIC.- Procesos planificados por la política de Servidor
Esporádico (tareas esporádicas)
© Arnoldo Díaz Ramírez - 2007
Fin de la Parte 3