• Author / Uploaded
• chechejgv

• Categories
• Unidad Central de procesamiento
• Programación (Computación)
• Sistema operativo
• Planificación
• Arquitectura de Computadores

Citation preview

Planificación (scheduling)

Sistemas Operativos I

Objetivos  Al

terminar esta unidad aprenderás a:

• Analizar políticas de planificación • Diferenciar políticas de planificación • Aplicar políticas de planificación

Sistemas Operativos I

Agenda

1. Objetivos de la planificación 2. Planificación PEPS 3. Planificación por Prioridad 4. Planificación RR 5. Planificación Multinivel 6. Planificación a dos niveles 7. Planificación en multiprocedadores 8. Tarea para la casa Sistemas Operativos I

El problema  Cuando

hay más de un proceso que está en condiciones de ejecutar en la CPU.

• ¿Cuál elegir?

 El

modulo planificador (scheduler) toma la decisión

• El algoritmo que se aplica se denomina algoritmo de planificación.

Sistemas Operativos I

Objetivos 

Algunos de ellos son contradictorios:

• • • • •

a) Justicia. Asegurarse que todos los procesos tengan su turno de CPU b) Eficiencia. Eficiencia Mantener la CPU ocupada todo el tiempo c) Tiempo de respuesta. respuesta Minimizar el tiempo de respuesta de los usuarios interactivos d) Rendimiento o productividad. productividad Maximizar el número de trabajos terminados por unidad de tiempo e) Tiempo de espera. espera Minimizar el tiempo medio de espera (en la cola listos) de los procesos

Sistemas Operativos I

Complicaciones 





Cada proceso es único y de comportamiento impredecible Algunos trabajan la mayor parte del tiempo usando un dispositivo E/S (son intensivos en E/S), otros requieren más tiempo de CPU (son intensivos en CPU) Modelos de planificación:

• •

con conmutación (Expropiadora ). El planificador puede conmutar el proceso en cualquier instante Sin conmutación (No-Expropiadora). No esta permitido conmutar procesos

Sistemas Operativos I

Casos  La

planificación no-expropiadora (nonpreemptive)

•

ej.: MSDOS, Windows 3.x.

 problema:

• un proceso puede quedar en ciclo infinito y el sistema operativo no tiene forma de saber.

Sistemas Operativos I

Algoritmo PEPS PEPS (El primero que llega es atendido primero)



• • •

Sin conmutación La atención es por estricto orden de llegada a la cola Cada proceso corre hasta que termina, o hasta que hace una llamada a E/S (bloqueo de I/O)

• Desventaja  El tiempo medio de respuesta no es bueno

termina

Cola PEPS llegada CPU Se bloquea procesos

Sistemas Operativos I

Primero el trabajo más corto (Shortest Job First) 





La cola de procesos se ordena por tiempo requerido de CPU requiere conocer la duración de la próxima fase de CPU de cada proceso No es práctico pedir al usuario el tiempo requerido termina Cola SJF

llegada 2

15 3 10

4

Sistemas Operativos I

CPU

Planificación por prioridad (PPP)  





¿PEPS es una planificación justa? PPP reglas:

• • •

A cada proceso se le da una prioridad La cola se forma por prioridad La CPU se asigna al proceso con mayor prioridad en la cola

• •

Estática

La prioridad puede definirse de manera:

•

No cambia

•

Cambia a medida que pasa el tiempo

Dinámica

Ejemplos:

• • • •

Según categoría del usuario (externa) Según tipo de proceso: sistema, interactivo, por lotes; bien, CPUbound o I/O bound (interna) Según cuanto hayan ocupado la CPU hasta el momento (dinámica) Mientras más tiempo lleve esperando su prioridad crece maduración o aging (dinámica)

Sistemas Operativos I

Round-robin (RR) 

Se debe evitar que un proceso de alta prioridad ejecute por demasiado tiempo

• • • • • •

Introducir la conmutación antes de cederle la CPU a un proceso se inicia el timer, que después de un plazo (quantum) genera una interrupción para conmutar de proceso El proceso ejecuta hasta que haga una llamada de E/S bloqueante o hasta que use toda su tajada se tiempo El problema es encontrar el quantum adecuado Si es muy grande degenera en PEPS Tampoco puede ser demasiado pequeño, porque entonces el costo en cambios de contexto es preponderante Cola PEPS

quantum CPU

Sistemas Operativos I

Múltiples Colas Multiple Nivel  

Los procesos interactivos y los procesos por lotes tienen distintos requerimientos en cuanto a tiempos de respuesta Planificar los procesos interactivos usando RR y los procesos por lotes según PEPS, teniendo los primeros prioridad absoluta sobre los segundos Cola PEPS

CPU

RR

Sistemas Operativos I

Ejemplo  Varias

colas planificadas, de prioridad decreciente y quantum:

• Complejo de implementar • También es difícil de afinar, hay múltiples parámetros que definir

Sistemas Operativos I

Planificación a dos niveles 

Se simplifica si se divide el problema en dos y se usa un planificador distinto para cada caso

• •

Corto plazo

Un planificador de corto plazo se encarga sólo de decidir a qué proceso se le asigna la CPU, de entre todos los que están en memoria Periódicamente, otro planificador de largo plazo decide qué procesos han estado demasiado tiempo en memoria y pasar a disco para dar oportunidad a procesos que han estado mucho tiempo en el disco. Cola PEPS

CPU q

disco Largo plazo

Sistemas Operativos I

Funciones de los planificadores a dos niveles  



Los procesos en ejecución están en memoria Si la memoria disponible es escasa y hay muchos procesos en el sistema, entonces algunos procesos deben mantenerse en disco Problema:

•



el tiempo requerido para hacer una conmutación de contexto que involucre traer un proceso del disco es muchísimo mayor que el tiempo de conmutación de contexto entre procesos en memoria

Tarea: Cómo planifica UNIX?

Sistemas Operativos I

planificadores a dos niveles: reglas de decisión  Problema:

¿cómo decidir qué procesos deben ser llevados de una cola a otra?  Reglas:

• Se pueden usar factores como el tiempo que • •

un proceso lleva en memoria o disco, Cantidad de CPU usada hasta el momento, tamaño del proceso Prioridad, etc. Sistemas Operativos I

Planificación en multiprocesadores  

¿Qué es un multiprocesador?

•

varias CPUs y una memoria común

•

Podría asignarse una cola a cada procesador, pero se corre el riesgo de que la carga quede desbalanceada:

Solución a:

•

algunos procesadores pueden llegar a tener una cola muy larga de procesos para ejecutar, mientras otros están desocupados (con la cola vacía)

CPU1

CPU2

CPUi …

CPUn …

Memoria

Sistemas Operativos I

Solución b) Cola común de procesos listos 

Este enfoque tiene dos alternativas:

• • •

1. Cada procesador es responsable de su planificación. Hay ineficiencia por la necesaria sincronización entre los procesadores para acceder la cola 2. Dejar que sólo uno de los procesadores planifique y decida qué procesos deben correr los demás procesadores: multiprocesamiento asimétrico

CPU1

CPU2

CPUi …

CPUn …

Memoria

Sistemas Operativos I

Evaluación de los algoritmos  Está

claro que hay numerosas alternativas de planificación  Metodología de evaluación:

• Primero, definir una métrica • Después elegir un método para evaluar los algoritmos y ver cuál se ajusta mejor al criterio elegido

Sistemas Operativos I

Métodos de evaluación de algoritmos 

A pesar de que cada proceso es único e impredecible a) simular b) determinar experimentalmente



Simulación:

• • •

Típicamente la distribución de tiempo de uso de CPU es exponencial Los eventos que conducirán la simulación pueden generarse según su distribución probabilística, o también pueden provenir del monitoreo de un sistema real (caso experimental) Los resultados van a ser muy exactos, pero es costoso

Sistemas Operativos I

Determinando experimentalmente  En

términos de exactitud, lo mejor es programar en el sistema operativo el algoritmo que queremos evaluar, ejecutarlo y ver cómo se comporta.  también es caro!

Sistemas Operativos I

Tarea para la casa  1.

¿Qué forma de planificación se implementa en Linux?  2. Del libro de Tanenbaum A.

• Sistemas Operativos Modernos, pp. 82 •

resolver en grupo los siguientes problemas: 20 al 25 manuscrito

Sistemas Operativos I

FIN

Sistemas Operativos I