planificacion de procesos

1

Módulo 5:

Pl ifi ió d

Sistemas Operativos

JRA©2007 Sistemas Operativos – Planificación de Procesos 1

Planificación de Procesos

Modulo 5: Planificación de CPU

• Conceptos Básicos

• Criterios de Planificación

• Algoritmos de Planificación

• Planificación de Múltiples Procesadores


Planificación de Múltiples Procesadores

• Planificación en Tiempo Real

• Evaluación de Algoritmos

Conceptos Básicos

• Máxima utilización de CPU obtenida con multiprogramación

• Ciclo CPU–ráfagas de E/S – La ejecución de procesos consiste de ciclos de ejecución de CPU y esperas en E/S.


• Distribución de ráfagas de CPU

Secuencia Alternante de Ráfagas de CPU y E/S


Histograma de Tiempos de Ráfagas de CPU


Planificador de CPU

• Selecciona entre los procesos en memoria que están listos para ejecutar, y aloca la CPU a uno de ellos.

• La decisión de planificar la CPU puede tener lugar cuando un proceso:

1.Conmuta de ejecutando a estado de espera.


2.Conmuta de ejecutando a estado de listo.3.Conmuta de espera a listo.4.Termina.

• La planificación de 1 y 4 es no apropiativa.

• Las otras planificaciones son apropiativas.

2

Despachador

• El módulo despachador pasa el control de la CPU al proceso seleccionado por el planificador de corto término; esto implica:

– cambio de contexto– conmutación a modo usuario

lt l di ió i d l d


– salta a la dirección apropiada en el programa de usuario para reiniciarlo

• Latencia de despacho – tiempo que toma al despachador para detener un proceso e iniciar otro.

Criterios de Planificación

• Utilización de CPU – mantener la CPU tan ocupada como sea posible

• Procesamiento total (Throughput) – número de procesos que completan sus ejecución por unidad de tiempo.


• Tiempo de retorno – cantidad de tiempo para ejecutar un determinado proceso.

• Tiempo de Espera – cantidad de tiempo que un proceso ha estado esperando en las colas.

• Tiempo de respuesta – cantidad de tiempo que transcurre desde que fue hecho un requerimiento hasta que se produce la primer respuesta, no salida.

Criterios de Optimización

• Maximizar la utilización de CPU

• Maximizar el procesamiento total

• Minimizar el tiempo de retorno

• Minimizar el tiempo de espera


p p

• Minimizar el tiempo de respuesta

Planificación Primero-Entrar, Primero-Servido (FCFS)

• Ejemplo: Proceso Tiempo de Ráfaga

P1 24

P2 3

P3 3

• Suponer que los procesos llegan en el orden: P1 , P2 , P3


La carta de Gantt para la planificación es:

• Tiempo de espera para P1 = 0; P2 = 24; P3 = 27

• Tiempo medio de espera: (0 + 24 + 27)/3 = 17

P1 P

2P3

24 27 300

Planificación FCFS (Cont.)

Suponer que los procesos llegan en el orden

P2 , P3 , P1 .

• La carta de Gantt para la planificación es:


• Tiempo de espera para P1 = 6; P2 = 0; P3 = 3

• Tiempo medio de espera: (6 + 0 + 3)/3 = 3

• Mucho mejor que el caso anterior.

• Efecto Convoy los procesos cortos delante de los procesos largos

P1

P3

P2

63 300

Planificación Job-Mas Corto Primero (SJF)

• Se asocia con cada proceso la longitud de su próximaráfaga de CPU. Se usa estas longitudes para planificar los procesos con el tiempo mas corto.

• Dos esquemas: – No apropiativo – una vez que la CPU es dada a un

proceso, no puede ser apropiada hasta que el mismo complete s ráfaga de CPU


complete su ráfaga de CPU.– Apropiativo – si un nuevo proceso llega con una

longitud de ráfaga de CPU menor que el resto del tiempo de ejecución que le queda al proceso que está ejecutando entonces se apropia de la CPU. Este esquema es conocido como El Tiempo Remanente Mas Corto Primero (SRTF).

• SJF es óptimo – da el mínimo tiempo de espera promedio para un dado conjunto de procesos.

3

Proceso Tiempo de llegada Ráfaga

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4

Ejemplo de SJF No Apropiativo


4

• SJF (no apropiativo)

• Tiempo medio de espera = (0 + 6 + 3 + 7)/4 = 4

P1

P3

P2

7 160

P4

8 12

Ejemplo SJF Apropiativo

Proceso Tiempo de llegada Ráfaga

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4


4

• SJF (apropiativo)

• Tiempo medio de espera = (9 + 1 + 0 +2)/4 = 3

P1

P3

P2

42110

P4

5 7

P2

P1

16

Determinando la Longitud de la Próxima Ráfaga de CPU

• Se puede solamente estimar la longitud.

• Se puede hacer usando la longitud de las ráfagas de CPU previas. Se usa un promedio exponencial.

1. actual longitud de la ráfaga de CPUmant n=


12. valor predicho para la próxima ráfaga CPU3. , 0 14. Define:

nτα α

+ =≤ ≤

( )1 1 .n n ntτ α α τ+ = + −

Ejemplos de Promedio Exponencial

• α =0– τn+1 = τn

– La historia reciente no cuenta.

• α =1– τn+1 = tn– Solo la última ráfaga de CPU cuenta


Solo la última ráfaga de CPU cuenta.

• Si se expande la fórmula, se tiene:τn+1 = α tn+(1 - α) α tn -1 + …

+(1 - α )j α tn -1 + …+(1 - α )n=1 tn τ0

• Dado que α y (1 - α) son menores o iguales a 1, cada término sucesivo tiene menos peso que su predecesor.

Planificación por Prioridad

• Con cada proceso se asocia un número (entero)

• La CPU es alocada al proceso con prioridad mas alta (entero mas pequeño ⇒ mas alta prioridad o el entero mas grande, depende de la convención).

– Apropiativo


– No apropiativo

• SJF es un algoritmo planificador con prioridad.

• Problema ⇒Inanición – los procesos de baja prioridad pueden no llegar a ejecutarse nunca.

• Solución ≡ Envejecimiento – se incrementa en el tiempo la prioridad de los procesos en espera.

Round Robin (RR)

• Cada proceso toma una pequeña unidad de tiempo de CPU (quantum), usualmente 10-100 milisegundos. Luego de este tiempo el proceso es quitado de la CPU y agregado a la cola de listos.

• Si hay n procesos en la cola de listos y el tiempo del quantum es q, entonces cada proceso toma 1/n del tiempo


q q, p pde CPU en rebanadas de a lo sumo q unidades de tiempo a la vez. Los procesos no esperan mas que (n-1)q unidades de tiempo.

• Rendimiento– q largo ⇒ Primero-Entrar, Primero-Salir– q chico ⇒ q debe ser grande con respecto al cambio de

contexto, sino la sobrecarga es demasiado grande.

4

Ejemplo: RR con Quantum = 20

Proceso Ráfaga

P1 53

P2 17

P3 68

P4 24


• La carta de Gantt:

• Tipicamente, mas tiempo de retorno promedio que SJF, pero mejor respuesta.

P1

P2

P3

P4

P1

P3

P4

P1

P3

P3

0 20 37 57 77 97 117 121 134 154 162

Como un Quantum PEQUEÑO Incrementa los Cambios de Contexto

tiempo de proceso = 10 conmutacióncontexto

quantum


El Tiempo de Retorno Varia con el Quantum

de re

torn

o

tiempoproceso


Tiem

po m

edio

d

tiempo de quantum

Colas Multinivel

• La cola de listos esta particionada en colas separadas:foreground (interactive)background (batch)

• Cada cola tiene su propio algoritmo de planificación, foreground – RRbackground – FCFS


g

• La planificación debe ser hecha entre las colas.– Planificación con prioridad fija; p.e., servir desde el

foreground y luego del background. Posibilidad de inanición.

– Tajada de tiempo – cada cola tiene una cierta cantidad de tiempo de CPU que puede planificar entre sus procesos;p.e., 80% en foreground en RR, 20% en background en FCFS

Planificación de Colas Multinivel


Colas Multinivel Realimentadas

• Un proceso puede moverse entre varias colas.

• El planificador de colas multinivel realimentadas está definido por los siguientes parámetros:

– Número de colas– Algoritmos de planificación para cada cola


g p p– Método usado para determinar cuando mejorar un

proceso– Método usado para determinar cuando degradar un

proceso– Método usado para determinar en que cola entra

un proceso cuando necesita servicio.

5

Colas Multinivel Realimentadas


Ejemplo de Colas Multinivel Realimentadas

• Tres colas: – Q0 – quantum de 8 milisegundos– Q1 – quantum de 16 milisegundos– Q2 – FCFS

• Planificación


Planificación– Un nuevo job entra a la cola Q0 el cual es servido

FCFS. Cuando gana la CPU, el job recibe 8 milisegundos. Si no finaliza en 8 milisegundos, el job es movido a la cola Q1.

– En Q1 el job es nuevamente servido FCFS y recibe 16 milisegundos adicionales. Si aún no completa, es movido a la cola Q2.

Planificación Múltiple-Procesador

• La planificación de CPU es mas compleja cuando hay disponibles múltiples CPUs.

• Procesadores homogéneos en un multiprocesador.

• Carga compartida


• Multiprocesamiento Asimétrico – solo un procesador accede a las estructuras de datos del sistema, simplificando el manejo de datos compartidos.

Planificación Tiempo Real

• Sistemas de Tiempo Real Duro – requiere completar tareas críticas en una cantidad de tiempo garantizado.

• Computación de Tiempo Real Blando – requiere que los procesos críticos reciban prioridad sobre otros.


Latencia de Despacho

evento respuesta al evento

intervalo de respuesta

procesainterrupción

latencia de despacho

proceso disponible


ejecuciónproceso entiempo real

conflictos despacho

tiempo

Evaluación de Algoritmos

• Modelo Determinístico – toma una carga de trabajo predeterminada y define el rendimiento de cada algoritmo para esa carga.

• Modelo de colas

• Implementación


p

6

Evaluación de Planificadores de CPU por Simulación


Planificación Solaris 2


Prioridades Windows 2000 y XP


Planificación en UNIX y Linux

La planificación tradicional en UNIX emplea colas multinivel ( los niveles se definen en bandas de prioridades) usando Round Robin en cada una de ellas:

P ( i ) = Base + CPUj (i )

+ nice (1)


CPUj ( i ) =CPUj (i - 1)

2(2)

Pj ( i ) = Basej + 2

+ nicej (1)


Pj ( i ) =

CPUj (i ) =

Basej =

Mide la utilización del procesador por el proceso j en el intervalo i.Prioridad del proceso j en el comienzo del intervalo i; valores bajos implican prioridades altas.Prioridad base del proceso j.


nicej =j o dad base de p oceso j

Factor de ajuste controlable por el usuario

(1) Es utilizada para ajustar dinámicamente la prioridad (producto del uso de CPU).

(2) Es usada para implementar el “envejecimiento” cuando el proceso espera. Así evita la inanición.


La prioridad de cada proceso es computada cada segundo (en los primeros UNIX, hoy es cada quantum).

El propósito de la prioridad base es dividir todos los procesos en bandas de niveles de prioridad.

L t CPU i tili i l


Los componentes CPU y nice se utilizan para prevenir que los procesos migren fuera de su banda asignada (dada por la prioridad base).

Estas bandas son utilizadas para optimizar el acceso a los dispositivos que se manejan con bloques de información (discos, cintas, CD, etc) y permitir al sistema operativo responder rapidamente a las llamadas al sistema.

7


En orden decreciente de prioridad, las bandas son:

Swapper.

Control de dispositivos de E/S en bloques.

Manipulación de archivos.


p

Control de dispositivos de E/S por caracteres.

Procesos de usuarios.

Dentro de la banda de procesos de usuario, el uso de la historia de ejecución tiende a penalizar a los procesos limitados por procesador a expensas de los procesos limitados por E/S.

planificacion de procesos

Business