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 |