Algoritmo No 3: (RR) Round Robin (RR) Cola de procesos listos tratada como cola FIFO circular A cada proceso se le entrega CPU por un periodo de tiempo, llamado quantum Proceso se ejecuta por la duración del quantum o hasta que pasa a bloqueado Ejemplo P1 : 24 ms, P2 : 3ms, P3 : 3ms, quantum 4ms Ventajas ? Estupendo para procesos interactivos (sistemas de tiempo compartido)
RR (cont) Desventajas Valor del quantum muy importante en rendimiento de RR Problemas si es muy chico? Tiempo de overhead por cambio de contexto Problemas si es muy grande? Se acerca a FCFS Recomendación 80% de tiempo de ejecución de procesos (cada requerimiento antes de bloquearse) debería ser mas cortas que quantum
Algoritmo No 4 : Prioridades Asignar prioridades a procesos Ejecutar proceso con mayor prioridad Si hay procesos con igual prioridad, aplicar FCFS SJF, prioridad es tiempo de próximo requerimiento Ejemplo: Proceso Tiempo Ejecución Prioridad P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2
Prioridades (cont) Como asignar prioridades Internamente por SO, en base a uso de recursos (memoria, archivos, etc) Externamente (no por SO) de acuerdo a importancia de procesos Espera indefinida Si continuamente llegan procesos de alta prioridad, los de baja prioridad esperan indefinidamente Solución Espera indefinida Envejecimiento aumentar prioridad como función acumulada en el tiempo decrementar prioridad como función acumulada de tiempo de procesamiento
Combinando Algoritmos En la práctica los sistemas actuales usan una combinación de estos algoritmos (RR, Prioridad, SJF) Ejemplo: Múltiples colas retroalimentadas Tiene jerarquía de colas Tiene prioridades para ordenar las colas Nuevos procesos entran a cola de mayor prioridad Cada cola planificada con RR Quantums son distintos en cada cola Procesos se cambian de colas en base a historia
Múltiples Colas Retroalimentadas Idea, separar procesos en base a sus necesidades de ejecución Procesos interactivos están en las colas de mayor prioridad Procesos que usan mucha CPU se cambian a colas de menor prioridad Procesos que llevan mucho tiempo en el sistema se cambian a colas de mayor prioridad
Planificación en UNIX Usa múltiples colas realimentadas De acuerdo a tipo de proceso procesos de tiempo compartido procesos de sistema Procesos de tiempo real Planificación por prioridad entre distintas colas y RR dentro de cada cola Procesos con alta prioridad siempre se ejecutan primero Procesos con la misma prioridad se planifican con RR Procesos cambian prioridad dinámicamente Se incrementa si proceso hace E/S antes de terminar quantum Se decrementa si proceso usa todo su quantum Objetivo? Premiar procesos interactivos Típicamente usan CPU por periodos pequeños de tiempo
Planificador Linux Soporta: una CPU SMP (Simultaneous Multi-Processors) Multiprocesadores en un chip o no, cada uno con caches y compartiendo Memoria Principal SMT (Simultaneous Multi-Threading) Procesador con recursos adicionales para soportar hebras. Sistema con Memoria principal compartida NUMA (Non- Uniform Memory Access) Unico sistema usando mas de un nodo (una máquina con un procesador o un multiprocesador es decir con propia CPU o set de CPUs y memorias)
Planificador de CPU en Linux 2.4 2 algoritmos para planificación de procesos Uno para procesos de tiempo compartido, en donde CPU se multiplexa en forma justa entre procesos Una para procesos con requermientos de tiempo real, donde prioridades absolutas son más importantes que justicia Algoritmo para procesos que comparten tiempo Prioridades y créditos asociadas a proceso Proceso con más créditos se ejecuta primero A cada interrupción del timer se decrementan créditos de proceso en ejecución. Cuando llega a 0 se planifica el siguiente proceso Cuando créditos de todos los procesos listos es 0, créditos se recalculan para todos los procesos (incluyendo los bloqueados) créditos = (créditos/2) + prioridad
Algoritmo Planificador Linux 2.4 vs 2.6 Diferencias entre version 2.4 y 2.6 Algoritmos de 2.4 del orden O(n) Tiempo ejecución varía linealmente al aumentar tamaño entrada Algoritmos de 2.6 del orden O(1) Tiempo ejecución constante independiente del número de tareas a ejecutar en sistema Estructuras básicas en 2.6 Runqueues Priority arrays
Algunos problemas mejorados en 2.6 Planificación de tareas de tiempo real (soft) Mayor rapidez en atender este tipo de tareas Algunos problemas para procesos que parecen interactivos (I/O-bound) Procesos/hebras que usan mucho E/S considerados como interactivos A veces están relacionados con BD no necesariamente interactivos Procesos/hebras que son CPU-bound e I/O-bound pueden anular efectos de boost y penalidad de planificador Mayor información http://www.inf.udec.cl/~chernand/links/linux_cpu_scheduler.pdf
Resumen Planificación de procesos puede influenciar fuertemente el rendimiento Como? Generalmente, múltiples objetivos tienen conflictos Como? Existen diversos algoritmos puros, pero normalmente los sistemas implementan lo bueno de varios
| Página siguiente |