Planificación de procesos (página 2)

Partes: 1, 2

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