1
Planificación del Procesador
Capítulo 9
2
Principales objetivos del Scheduling
• Asignar procesos a ejecución por el procesador
• Minimizar tiempo de respuesta
• Maximizar throughput
• Maximizar eficiencia del procesador
• Minimizar tiempo de espera
• Satisfacer todos estos requerimientos al mismo tiempo es extremadamente difícil
3
Tipos de Scheduling• Largo plazo
– Determina qué programas son admitidos al sistema para ejecución
– Controla el grado de multiprogramación
– Mientras más procesos son admitidos, cada uno tendrá un porcentaje menor de uso del procesador
• Mediano plazo– Determina si agregar más programas a los que ya están parcialmente o totalmente
en memoria principal.
– Es parte de la función de swapping
• Corto plazo– También conocido como el despachador, determina qué proceso es ejecutado en
el procesador
– Se ejecuta frecuentemente debe ser eficiente
– Evento típicos que gatillan al despachador: Interrupciones del reloj (quantum), interrupciones de I/O, llamados al sistemas, señales, etc.
• De I/O– Determina cuál requerimiento pendiente de I/O se atiende primero
4
Relación tipo de scheduling y estado de un proceso
5
Criterios para un algoritmo de corto plazo
• El objetivo principal de un scheduler de corto plazo es asignar procesos a la CPU de tal forma de optimizar uno o más aspectos de rendimiento del sistema
• Desde el punto de vista del usuario– Tiempo de respuesta
• Tiempo transcurrido entre el sometimiento (submission) de un requerimiento hasta que existe alguna salida o respuesta
• Ejemplo: maximizar el número de usuarios que experimentan dos segundos como tiempo de respuesta
– Tiempo turnaround o tiempo de reloj (TAT)• Tiempo entre el sometimiento de un trabajo y el término de éste
• Desde el punto de vista del sistema– Throughput: número de trabajos (procesos) por unidad de tiempo
– Utilización del procesador: porcentaje de tiempo que la CPU está ocupada
• ¿Qué sería importante en un sistema mono usuario?
6
7
8
Prioridades
• Si los procesos tienen asignada alguna prioridad, el scheduler siempre eligirá aquel proceso con prioridad más alta para ejecutar
• Usar varias colas para cada nivel de prioridad
• Problema: inanición
• Solución: permitir que un proceso cambie su prioridad en la medida que pasa el tiempo
9
Modo de decisión
• Apropiativo (Nonpreemptive)– Una vez que el proceso entra a la CPU, continuará ejecutándose hasta que termina, se
bloquea por una operación de I/O o realiza un llamado al sistema
• No apropiativo (Preemptive)– El proceso en el estado de Running puede ser interrumpido por el SO y sacado del
procesador
– Permite que ningún proceso monopolice la CPU
10
11
Aplicaciones clinicas: PET
Childress, A.R., et al. Limbic activation during cue-induced cocaine craving. American Journal of Psychiatry 156(1):11-18, 1999.
Regiones límbicas de individuos en tratamiento por abuso de drogas, son activadas al mirar videos con eventos relacionados con cocaína.
Paciente con cáncer al pulmón
Positron Emission Tomography (PET) Scanning at Mayo Clinic Mayo Clinicwww.mayoclinic.org/pet
CT PET Fusion
12
Crump Institute for Molecular Imaging, UCLA
PET dinámico
13
GATE: toolkit de simulación
14
Process Scheduling Example
15
El primero en llegar, el primero en ser servidoFirst-Come-First-Served (FCFS)
• Cada proceso entra en la cola de listos
• Cuando el proceso actualmente en la CPU termina, el proceso que ha estado esperando más tiempo en la cola de listo es seleccionado para ejecución
• Note que un proceso corto podría esperar mucho tiempo antes de entrar a la CPU
• Favorece procesos pesados en CPU (CPU bound)
16
Otro ejemplo FCFS
Proceso
Tiempo de
Llegada
Tiempo de servicio (Ts)
Tiempo de inicio
Tiempo de término
TAT TAT/Ts
W 0 1 0 1 1 1
X 1 100 1 101 100 1
Y 2 1 101 102 100 100
Z 3 100 102 202 199 1.99
promedio 100 26
TAT/Ts = TAT normalizado
TAT es Turnaround Time
El rendimiento de FCFS es mejor para procesos largos
17
Round-Robin
• El SO interrumpe al proceso cuando el quantum de tiempo asignado termina
• Uso del reloj
• El próximo proceso seleccionado se determina con FCFS
• Procesos pesados en CPU son favorecidos con respecto a procesos pesados en I/O. ¿Por qué?
18
• Un quantum pequeño favorece a procesos cortos
• Si el quantum es muy pequeño, muchos procesos necesitarán más de un intento en la CPU para producir algún tipo de resultado
19
Round Robin virtual
• Una forma de mejorar RR es VRR (round robin virtual)
• Cuando un proceso se desbloquea de I/O, en vez de ir a la cola de listos va a una cola auxiliar.
• Cuando el despachador necesita cargar un nuevo proceso en CPU, le da prioridad a los proceso de la cola auxuliar, pero
• el tiempo asignado es el quantum menos el tiempo que corrió la última vez que fue seleccionado de la cola de listos
20
El trabajo más corto (SPN)
• Se selecciona el proceso cuyo tiempo estimado de procesamiento es el menor
• Política apropiativa
• Procesos cortos son favorecidos sobre procesos largos
• Es posible inanición de procesos muy largos
21
El trabajo con tiempo restante menor(SRT)
• Versión no apropiativa del SPN
• Si llega un proceso nuevo con tiempo incluso menor que aquel que está en la CPU, se saca al que está en la CPU y se planifica el menor
• ¿Cómo estimar el tiempo restante?
22
Razón de respuesta más alto (HRRN) Highest Response Ratio Next
• La idea es– Minimizar el TAT normalizado
– Minimizar el promedio entre todos los procesos
• Considere la siguiente razón
• R = razón de respuesta
• w = tiempo esperando por el procesador
• s = tiempo estimado de servicio
• Luego, el algoritmo elige aquel proceso con R más alto
R = w+ss
23
Feedback• Si no es posible conocer o estimar el tiempo de servicio futuro, no se podría usar
SPN, SRT, y HRRN.
• Una alternativa para dar preferencia a trabajos cortos es penalizar aquellos trabajos que han estado corriendo por más tiempo.
• Cuando un proceso entra al sistema, es colocado en una cola de prioridad RQ0.
• Después de ser desapropiado del procesador (quantum o I/O) y vuelve al estado de Ready, vuelve a una cola de prioridad más baja RQ1.
• Cada vez que sale y vuelve a la cola de listo, pasa a una cola de menor prioridad.
• Las colas se manejan con FCFS, excepto la de más baja prioridad, la que se maneja con Round-Robin
24
25
26