Planificación de Procesos
Recordando cambio de contexto
Cambiando CPU de un proceso a otro
Procesos cambian de estados
ejecución a bloqueado (ejecución instrucción I/O)
bloqueado a listo por interrupciones
Proceso espera por evento, evento se produce
Reloj interrumpe y SO planifica a otro proceso
Planificación: Elegir que proceso de la cola de listos ejecutar
Planificación implica una decisión (política)
Cambio de contexto es una forma de hacerlo (mecanismo)
Multiprogramación y planificación
Multiprogramación permite aumentar la utilización de recursos y productividad sobreponiendo E/S y procesamiento
Que procesos/hebras ejecutar y por cuanto tiempo?
2 visiones para la planificación en CPU
Largo plazo: determina nivel de multiprogramación
Cuantos trabajos se cargan a memoria
Ingresarlo a memoria o sacarlo (swapping)
Corto plazo: qué trabajo ejecutar a continuación para proporcionar un buen servicio
Ocurre frecuentemente, idea minimizar sobrecarga por cambio de contexto
Idea de buen servicio depende de muchas cosas
Objetivos de Planificación
Maximizar la utilización de CPU (CPU Utilization)
Maximizar la Productividad número de requerimientos atendidos por unidad de tiempo (throughput)
Minimizar tiempo de respuesta promedio (Response time)
Desde inicio hasta obtención primera respuesta de sistema
Minimizar tiempo de espera promedio (Waiting time)
Tiempo en cola de listos
Minimizar tiempo que tarda en proceso ejecutarse completamente, de inicio a fin (Turnaround time)
Favorecer algunos procesos, prioridad (Priority)
Evitar espera indefinida
Algunos sistemas favorecen algunos objetivos frente a otros
Productividad. Sistema de procesamiento de transacciones
Tiempo de respuesta. Sistema interactivo
Diferencia entre sistemas batch e interactivos
Sistemas batch
Importa maximizar throughput y minimizar turnaround time
Sistemas interactivos
Importa maximizar throughput y minimizar turnaround time y response time
De acuerdo a como se comportan procesos o hebras en un sistema
Procesos batch (CPU-bound)
Procesos interactivos (I/O-bound)
También importante para planificadores
Típicamente tratan de evitar inanición (starvation)
Cuando un proceso es prevenido de progresar porque otro proceso tiene el recurso que necesita
Ejemplo. Procesos de alta prioridad no permiten a procesos de baja prioridad ejecutarse
Inanición también se puede producir en hebras/procesos sincronizados
Planificador
Módulo que mueve trabajos entre colas
Algoritmo de planificación determina que trabajo ejecutar a continuación
Se ejecuta cuando
Un trabajo pasa de listo a bloqueado
Ocurre una interrupción del timer
Se crea o termina un trabajo
2 tipos de sistemas de planificación
No apropiativa
Planificador espera que trabajo termine o ceda CPU
Apropiativa
Planificador interrumpe trabajo en ejecución y fuerza un context switch
Planificación Apropiativa/No Apropiativa
No Apropiativa. Una vez que procesos adquieren CPU no la liberan, excepto
Proceso pasa a estado de espera (bloqueado)
Proceso termina
Apropiativa. SO puede decidir quitar CPU a proceso para dársela a otro
Usa interrupciones de reloj
Algoritmos No 1 (FCFS)
FCFS (First Come, First Served)
Atención por orden de llegada
Justo, simula mundo real (banco, supermercado, etc)
Típicamente No Apropiativo
Ejemplo: P1 : 24ms, P2 : 3ms, P3 : 3ms
Tiempo de respuesta promedio? Tiempo de espera promedio?
Ventajas?
Desventajas?
FCFS (cont)
Ventajas
Ningún proceso espera indefinidamente
Desventajas
Tiempo de espera promedio puede ser alto, depende de:
tiempo de ejecución de procesos
orden de llegada
procesos cortos tienen espera alta si están detrás de los largos
Puede producir baja utilización de recursos
cuando procesos esperan podrían ocupar otros recursos
Algoritmo No2 (SJF)
Short-Job-First (SJF)
Asocia cada proceso con el tiempo de ejecución, tiempo que ocupo CPU la ultima vez antes de cambiarse a estado de espera
CPU es asignada a proceso con el menor tiempo de ejecución
Si dos procesos tienen igual tiempo de ejecución se aplica FCFS
Calcule tiempo de respuesta y espera promedios usando ejemplo anterior
Puede ser apropiativo y no apropiativo
SJF (cont)
Versión apropiativa Shortest-Remaining-Time-First
Calcula tiempo de ejecución mas corto y tiempo de llegada
Ejemplo: Calcular tiempo de respuesta y espera promedio
Proceso Tiempo llegada Tiempo ejecución
P1 0 8
P2 1 4
P3 2 9
P4 3 5
SJF (cont)
Ventajas
Parece perfecto
Mejor tiempo de espera promedio que FCFS
Desventajas
Espera indefinida?
Como estimar tiempo de procesamiento de próximo requerimiento de proceso?
Página siguiente |