SISTEMAS OPERATIVOS
4M1- IS
Planificador de Procesos
29 de Abril del 2011
PLANIFICADOR DE
PROCESOS
2 /58
Utilidad de la Planificación
•
•
•
•
Asignar los procesos a ser ejecutados por el procesador
Definir el tiempo de respuesta.
Rendimiento del procesador
Eficiencia del procesador
3 /58
Niveles de la Planificación
Planificador de Largo Plazo.
Planificador de Mediano Plazo
Planificador de Corto plazo.
Suspendido
Listo
Nuevo
Listo
Suspendido
Bloqueado
Bloqueado
Corriendo
Terminado
4 /58
Tipos de Planificación
• Planificación de Largo Plazo,
– Para admitir nuevos procesos al sistema
– La decisión de adicionar al grupo de procesos a ser
ejecutados.
• Planificación de mediano plazo
– Problema de administración de memoria
– La decisión de adicionar a un número de procesos
que están parcialmente o completamente en
memoria. A veces es mejor dejarlos fuera de
memoria.
5 /58
Tipos de Planificación
• Planificación de corto plazo.
– Qué proceso escoger para ser ejecutado.
– Se ejecuta en todos los cambios de contexto.
– Tiene que ser muy rápido
– La decisión en cuanto a cual proceso disponible
puede ser ejecutado por el procesador
• Planificación de la E/S
– La decisión de qué proceso pendiente de E/S puede
ser ejecutado por el procesador, dado que existe una
E/S disponible
6 /58
Planificación y Transiciones entre los
estados de un proceso
7 /58
Planificador de Largo Plazo
• Determina que programas son admitidos al sistema para
su procesamiento.
• Controla el grado de multiprogramación.
• Mucho procesos, cada proceso es ejecutado en pequeños
porcentajes de tiempo.
8 /58
Planificador de Mediano Plazo
• Parte de la función de intercambio (swaping).
• Basado en la necesidad de administrar el grado de multiprogramación.
9 /58
Planificador de Corto Plazo
• Conocido como el despachador.
• Se ejecuta muy frecuentemente.
• Se invoca cuando ocurre alguno de los siguientes
eventos:
– Interrupción de reloj
– Interrupción de E/S
– Llamadas al SO
– Señales
10 /58
Diagrama de colas para el planificador
11 /58
Criterios de planificación a corto plazo
• Orientado al usuario.
– Tiempo de respuesta
(TS) Inicio  1ra respuesta
– Tiempo de retorno
(TR) Inicio  Fin
– Tiempo ponderado retorno (TPR = TR/TC)
– Plazos  Maximizar el Nro. Plazos cumplidos.
– Previsibilidad  El mismo trabajo, tiempos parecidos.
– Para comparar los planificadores se usa el tiempo
promedio de cada criterio.
12 /58
Criterios de planificación a corto plazo
• Orientado al sistema.
– Efectividad. Nro de procesos terminados.
– Eficiencia. % tiempo usado del procesador
– Prioridad, si es que se usa favorecer a la > prioridad
– Equilibrio. Mantener ocupados a los recursos, evitar los
sobrecarga y la subcarga.
13 /58
Prioridades
• El planificador siempre puede escoger un proceso de alta
prioridad sobre un proceso de baja prioridad.
• Se tiene multiples colas preparadas para representar
cada nivel de prioridad.
• Bajos niveles de prioridad pueden sufrir inanición.
– Por lo que es necesario permitir a los procesos
cambiar su prioridad basado en su edad
(envejecimiento).
14 /58
Cola de Prioridades
15 /58
Modo de decisión
• No apropiativa.
– Únicamente un proceso está en estado corriendo, este
puede continuar hasta que termine o sea bloqueado a
si mismo por una E/S
• Apropiativa
– Los proceso en ejecución pueden ser interrumpidos o
movidos al estado listo por el sistema operativo.
– Permite un mejor servicio dado que ningún proceso
puede monopolizar el procesador por largo tiempo.
16 /58
POLÍTICAS DE
PLANIFICACION
17 /58
Políticas de Planificación
1.
2.
3.
4.
5.
6.
7.
8.
Primero en llegar primero en ser servido.
Turno rotatorio (round robin) q = 1
Turno rotatorio (round robin) q = 4
Primero el proceso más corto
Menor tiempo restante.
Mayor tasa de respuesta.
Realimentación q = 1
Realimentación q = 2n
18 /58
Ejemplo de Planificación de procesos
19 /58
1
Primero en llegar primero en ser servido
First-Come-First-Served (FCFS)
• Todos los proceso hacen la cola de listos.
• Cuando el proceso actual deja de correr, el siguiente
proceso en la cola de listos es seleccionado.
• Un pequeño grupo de procesos puede esperar largos
periodos de tiempo antes de ser ejecutados.
• Favorece los proceso con carga del procesador en lugar
los que tienen carga
de E/S.
5
0
10
15
20
1
2
3
4
5
20 /58
2
Round-Robin
•
•
•
•
Prevención del uso basada en un reloj.
Cada quantum de tiempo un proceso usa la CPU
Las interrupciones de reloj se generan en intervalos fijos
Cuando ocurre una interrupción, el proceso en ejecución es
colocado en la cola de listos y el siguiente proceso es
seleccionado.
0
5
10
15
20
1
q=1
2
3
4
5
21 /58
Tamaño de quantum de tiempo
Quantum de tiempo
mayor que la
interacción normal
Quantum de tiempo
menor que la
interacción normal
22 /58
Diagrama de colas para el planificador
Round Robin Virtual
23 /58
4
Siguiente proceso más corto
Shortest Process Next (SPN)
•
•
•
•
•
•
Política no preventiva
Proceso con tiempo esperado más corto es seleccionado.
Los procesos pequeños saltan delante de los grandes.
Predicibilidad de los procesos grandes es reducida (Predictability)
Si el tiempo estimado es incorrecto, el SO puede abortarlo
Posibilidad de inanición de los procesos grandes.
0
5
10
15
20
1
2
3
4
5
24 /58
5
Menor tiempo restante
• Versión preventiva de la política el siguiente proceso más
corto
• Puede estimarse el tiempo de procesamiento.
0
5
10
15
20
1
2
3
4
5
25 /58
6
Mayor tasa de respuesta
Highest Response Ratio Next (HRRN)
• Escoge el siguiente proceso con el mayor ratio:
tiempo esperado + tiempo de servicio esperado
tiempo de servicio esperado
0
5
10
15
20
1
2
3
4
5
26 /58
7
Retroalimentación
Feedback
• Penaliza los trabajos que han corrido más tiempo.
• Si no se conoce el tiempo de ejecución restante, entonces
es mejor utilizar el tiempo de ejecución consumido hasta
el momento
0
5
10
15
20
1
2
3
4
5
27 /58
7
Retroalimentación
Feedback
q=1
q = 2i
28 /58
Planificación feedback
29 /58
ANALISIS
30 /58
Características
w = tiempo consumido hasta el momento en el sistema, esperando y ejecutando
e = tiempo consumido hasta el momento de la ejecución
s = tiempo total de servicio exigido por el proceso, incluido e
31 /58
Ejercicios 1
• Considere el siguiente conjunto de procesos:
Proceso
Tiempo
Llegada
Tiempo
Proceso
1
0
3
2
2
6
3
4
4
4
6
5
5
8
2
• Simular cada una de las 6 políticas vistas, con q = 1.
32 /58
Ejercicios 2
• Considere el siguiente conjunto de procesos:
Proceso
Tiempo
Llegada
Tiempo
Proceso
1
0
3
2
1
5
3
3
2
4
9
5
5
12
5
• Simular cada una de las 6 políticas vistas, con q = 1.
33 /58
Bibliografía
• Sistemas Operativos, William Stallings. 2da edición.
Capítulo 8
34 /58
Descargar

Planificador de Procesos