consulta sistemas operativos

Sistemas Operativos I

Parte 3

Arnoldo Díaz Ramí[email protected]

Septiembre de 2007

mailto:[email protected]

Unidad 3

Planificación

© Arnoldo Díaz Ramírez - 2007

Planificación


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


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


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


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


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)


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



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



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?



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



Priority Scheduling (planificación basada en prioridades)

Expulsivo

A cada tarea se le asigna un nivel de prioridad, que representa su importanciaimportancia


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



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




Fair-Share Scheduling (planificación justa)


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


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


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



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


la tarea con menor periodo, o la tarea

mas frecuente, es siempre la mas

prioritaria

Utilización máxima del procesador ≤

85%



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%


Planificación en Linux


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


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


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)


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)


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


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)


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 );



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);

}

}



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;}



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)


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)


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


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


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()


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


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)


Fin de la Parte 3

Documents

consulta sistemas operativos