planificación de monoprocesadores arquitectura y organización de sistemas de computación por...
Post on 07-Jan-2015
2 Views
Preview:
TRANSCRIPT
Planificación de Planificación de MonoprocesadoresMonoprocesadores
Arquitectura y Organización de Sistemas de Computación
Por Johana Pirela
UdeC
Adaptación: Dr. Joseabel Cegarra.
TemasIntroducciónConceptos básicosTipos de Planificación Funciones de Planificación
Largo Plazo Mediano Plazo Corto Plazo
Planificación Expropiativa
Algoritmos de Planificación Criterios Algunos Algoritmos
Evaluación de Algoritmos Modelos
Conclusiones y Comentarios
1. Introducción
Objetivo Reconocer la importancia de manejar técnicas de
planificación de trabajos en la CPU
Objetivos específicos Diferenciar técnicas de planificación para Mono-
procesadores Estudiar algunos métodos de evaluación y/o criterios de
evaluación
La Planificación es la base de los sistemas multiprogramados.
2. Conceptos básicos
Planificar para... Tener un proceso en ejecución en todo momento Ocupar el tiempo en el cual la CPU se encuentra ociosa Cuando un proceso espera por algún evento, el SO le “quitará”
y se la entregará a otro proceso.
Planificador de CPU Una vez que se “quita” la CPU a un proceso que espera E/S, se
debe escoger entre los procesos que esperan en la cola de procesos listos.
Se supondrá que los procesos listos están en fila, además, los registros de las colas son generalmente los PCB de los procesos.
Conceptos básicos (cont.)
La ejecución de un proceso consiste en un ciclo de ejecución en la CPU y espera por E/S Programa limitado por ráfaga
de E/S: ráfagas CPU cortas Programa limitado por ráfaga
CPU: ráfagas de CPU largas
3. Tipos de Planificación
Funciones de planificación Mejorar tiempo de respuesta Mejorar la productividad Aumentar la eficiencia del procesador
Existen tres tipos de planificadores, cada uno de ellos participa en diferentes momentos de ejecución de los procesos.
Planificador Largo Plazo Controla grado de multiprogramación, determinando qué
programas son admitidos en el sistema. Esta decisión se puede tomar cada vez que finaliza un proceso
Decide qué trabajos son aceptados y convertidos en procesos. Para esto se utilizan diferentes algoritmos.
Tipos de Planificación (cont.)
Planificador Mediano Plazo Es parte de la función de intercambio Decide cuándo y qué proceso mover del estado suspendido al
estado activo.
Planificador Corto Plazo: Despachador Módulo que cede el control de la CPU al proceso seleccionado
en ese momento. Alta frecuencia Realiza entre otras las siguientes funciones:
Cambio de contexto Cambio a modo de usuario
Tipos de Planificación (cont.)
Planificación y transiciones de estado de los procesos
Tipos de Planificación (cont.)
Planificación Expropiativa y No Expropiativa Las decisiones de planificación se toman cuando un
proceso: Pasa del Running a Waiting (bloqueado) (*) Pasa de Running a Ready (interrupción) Pasa de Waiting a Ready Termina (*)
(*) no hay opción, se debe escoger un nuevo proceso de la cola de procesos listos, en este caso, se habla de PLANIFICACIÓN NO EXPROPIATIVA.
En los otros casos, el proceso no entrega la CPU voluntariamente, se habla en este caso de PLANIFICACIÓN EXPROPIATIVA
Criterios de Planificación4. Algoritmos de Planificación
Algoritmos de Planificación (cont)
Planificación por Orden de llegada (FCFS)
Política de cola FIFO Tiempo de espera dependiente del orden de llegada de los procesos
y de las ráfagas de CPU de cada uno
Efecto Convoy No expropiativo
Algoritmos de Planificación (cont)Planificación Primero el Trabajo más Corto (SJF)
Asocia a cada proceso la longitud de la siguiente ráfaga de CPU Cuando la CPU queda libre se asigna el proceso con la ráfaga más
corta En caso de empate se usa el FCFS
Es óptimo, ya que entrega el tiempo promedio mínimo Se utiliza en planificación a largo plazo, pues, en este caso es
posible estimar la duración de la siguiente ráfaga
Algoritmos de Planificación (cont)
Planificación Primero el Trabajo más Corto, Expropiativo (SRTF)
Variación del algoritmo SJF Produce tiempos de retorno mejor que los del SJF, pues los
trabajos cortos tienen atención inmediata y preferente a la de los procesos largos
Algoritmos de Planificación (cont)
Planificación por Prioridad
SJF es un caso especial de este algoritmo A cada proceso se asigna una prioridad, y se ejecutan los
procesos con más alta prioridad, en caso de empate se usa FCFS
Puede ser expropiativa o no expropiativa Problema: Bloqueos Indefinidos o Inanición (procesos de baja
prioridad)
Algoritmos de Planificación (cont)
Planificación por Turno Circular (Round Robin)
Diseñado para sistemas de Tiempo Compartido FCFS con expropiación Se define un quantum, durante el cual cada sistema proceso tiene la
CPU
El desempeño depende de la duración del quantum, si es muy pequeño, la cantidad de conmutaciones será muy grande
Algoritmos de Planificación (cont)
Planificación con colas de múltiples niveles
Se clasifican los procesos en las siguientes colas: Ejecutados en primer plano (interactivos) Ejecutados en segundo plano (por lotes)
Cada una de las colas puede tener su propio algoritmo de planificación, además, debe existir un algoritmo de planificación entre colas: Planificación Expropiativa con Prioridades Fijas
Algoritmos de Planificación (cont)
Realimentación
Algoritmo anterior, con la posibilidad de mover los procesos entre las colas
Puede ser implementado en cualquier sistemas, pero es muy complejo
La idea: separa procesos con diferentes características de acuerdo a sus ráfagas. (Interactivos – Limitados por E/S – Limitados por CPU). Si un proceso pasa mucho tiempo en una cola de baja prioridad, puede ser reasignado a otra de mayor prioridad
5. Evaluación de Algoritmos
Algunas medidas: Maximizar uso CPU Maximizar rendimiento
Modelo Determinista Método de evaluación analítica Evalúa el desempeño de un algoritmo para una carga dada Es sencillo, rápido y exacto, pero requiere como entradas
números exactos, por lo mismo, es aplicable a casos muy particulares
Modelo de Colas Determinar distribución de las ráfagas de CPU y E/S
distribución de tiempos de llegada, luego calcular promedio, uso, etc.
Se realiza análisis de redes de colas
Evaluación de Algoritmos (cont.)
Simulaciones Simulador tiene una variable reloj, la cual, al incrementarse
produce una modificación del estado del sistema. Se recopilan e imprimen datos estadísticos que indican el
desempeño del algoritmo Datos son generados en forma aleatoria, o también realizando
seguimientos a sistemas reales, definiendo así, la distribución verdadera. Para que los resultados sean más exactos se usan Cintas de Rastreo del sistema real.
La implementación de métodos de análisis no es fácil. Por esta razón se aconseja el uso de algoritmos de planificación flexibles.
Son pocos los SO que tienen este tipo de planificación.
Conclusiones y Comentarios
Se debe conocer muy bien el sistema y las funciones que realizará, para elegir un tipo de planificación adecuado.
Los diferentes algoritmos de planificación no son excluyentes (planificación de colas multi-nivel), por lo mismo, es conveniente escoger una combinación adecuada.
Los métodos de evaluación de los algoritmos no son totalmente representativos. Pero sí, ayudan a tener una idea general del rendimiento de un sistema en particular.
La planificación no sólo minimizará índices, a veces se requerirá maximizar el uso de algunos recursos.
GRACIAS.
top related