Post on 29-Jun-2015
description
SISTEMAS OPERATIVOS
Administración del procesador
Unidad 4
Conceptos Básicos
Conviene revisar primero algunos conceptos básicos con respecto a este tema: Planificador de CPU Ciclo de ráfagas (burst) de CPU y E/S Planificación apropiativa Despachador
Planificación del procesador
Las políticas y mecanismos comunes que
poseen los S.O. para realizar la administración del procesador se le conoce
como
PLANIFICACION
Su objetivo es dar un buen
servicio a todos los procesos que
existan en el sistema.
Niveles de planificación del Procesador
Ejecución de un trabajo por el usuario
Carga y creación
Proceso bloqueado
o suspendido
Corto plazo
Medio plazo
Largo plazo
Preparado
Ejecución
Planificación del procesador
Planificación a largo plazo – planificador de trabajos
Decide cual será el próximo trabajo que se va a ejecutar, existe en los sistemas de proceso por lotes. Este nivel es el encargado de crear los procesos.Planificación a medio plazo – planificador de Swapping
Es el que decide si un proceso que esta en ejecución, bloqueado o suspendido debe ser extraído de la memoria temporalmente, posteriormente cuando el sistema se encuentre más descargado devolverá dicho proceso a la memoria. Existe en los sistemas de tiempo compartidoPlanificación a corto plazo – planificador del procesador
Es el encargado de decidir cómo y cuando tendrá acceso al procesador un proceso que está preparado para utilizarlo, lleva a cabo las funciones de multiprogramación, estando siempre residente en memoria.
Políticas de Planificación
LAS POLITICAS
DE PLANIFICACION
JUSTICIA: La política debe ser justa con todo proceso.
MAXIMA CAPACIDAD DE EJECUCIÓN: Que todos los trabajos se realicen lo más rápidamente posible.
MAXIMO NUMERO DE USUARIOS INTERACTIVOS: Se tratará de que puedan estar trabajando el mayor número de usuarios simultáneamente.
PREDECIBILIDAD: La política de planificación se debe concebir de tal forma que en todo momento se pueda saber como será su ejecución.
MINIMIZACION DE LA SOBRECARGA: La computadora debe tener poca sobrecarga.
EQUILIBRIO EN EL USO DE LOS RECURSOS: Que los recursos estén ocupados equitativamente el mayor tiempo posible.
SEGURIDAD DE PRIORIDADES: Un proceso debe ejecutarse más rápido si tiene mayor prioridad.
Criterios de Planificación
Algunos criterios que se utilizan para comparar los algoritmos de planificación: Utilización del CPU Rendimiento Tiempo de retorno Tiempo de espera Tiempo de respuesta
Se procura maximizar la utilización y el rendimiento y minimizar los demás tiemposNormalmente se intenta afectar el promedio, aunque lo ideal sería afectar la varianza
CriteriosPARA DISEÑAR UN ALGORITMO DE PLANIFICACION
TIEMPO DE RESPUESTA
Velocidad en que el ordenador da
respuesta a una petición.
TIEMPO DE SERVICIO
Tiempo que tarda en ejecutarse un
programa
TIEMPO DE EJECUCION
Tiempo que necesita el proceso para ser ejecutado menos el tiempo de espera en la cola de
procesos preparados
TIEMPO DE PROCESADOR
Tiempo que el proceso esta utilizando el
procesador.
TIEMPO DE ESPERA
Tiempo en el que los procesos están activos pero sin ser ejecutados
EFICIENCIA
La mayor utilización posible del procesador, para lograr un
gran rendimiento.
RENDIMIENTO
El mayor numero de trabajos o procesos
realizados por unidad de tiempo
Medidas para estudiar el comportamiento de las distintas
políticas de planificación
t es el tiempo de que un proceso P necesita estar en
ejecución para llevar a cabo su
trabajo, ti el instante en que el
usuario da la orden de
ejecución del proceso y tf el
instante en que el proceso termina
su ejecución
Tiempo de servicio (T): T= tf - ti
Tiempo de espera (E): E=T - t
•TIEMPO MEDIO DE SERVICIO
•TIEMPO MEDIO DE ESPERA
•EFICIENCIA (INDICE MEDIO DE SERVICIO.
Índice de servicio I= t/T
Algoritmos de planificación
Políticas apropiativas
Son las que producen un cambio de proceso con
cada cambio de contexto.
Politicas no apropiativas
Son aquellas en que un proceso no abandona nunca el procesador
desde su comienzo hasta su fin.
Cuando un proceso deja de estar en estado de ejecución y no existen causas para su bloqueo, o deja de estar bloqueado pasa nuevamente a la cola de procesos preparados.Las políticas de planificación se
agrupan en:
El planificador del procesador tiene como misión la asignación del mismo a los procesos que están en cola de procesos preparados. Esta cola es alimentada desde dos puntos distintos:Cada vez que un usuario inicie la ejecución de un programa el planificador recibe la orden de ejecución, crea el proceso y lo pasa al planificador colocándose en la cola de procesos preparados.
Planificación
Hay 4 momentos en los que se puede planificar:
Cuando un proceso pasa del estado en ejecución al estado en espera
Cuando un proceso pasa de en ejecución a listo Cuando un proceso pasa de en espera a listo Cuando un proceso termina
Si la planificación sólo se realiza en los casos 1 y 4, se dice que es un proceso no apropiativa y apropiativa de lo contrarioSi se es apropiativa, se debe asegurar que las operaciones internas delicadas funcionen bien.
Algoritmos de PlanificaciónDistintos algoritmos de planificación: Planificación de servicio por orden de llegada
(FCFS) Planificación de primero el trabajo más corto
(SJN) Planificación de primero el que tenga el menor
tiempo restante (SRTF) Planificación por prioridad Planificación por turno circular Planificación con colas de múltiples niveles Planificación con colas de múltiples niveles y
realimentación. Planificación con Múltiples Procesadores
Planificación de Servicio por Orden de Llegada
Este algoritmo, también denominado FCFS (First Come First Served), es el más sencilloSe utiliza el esquema normal del funcionamiento de una cola (FIFO), donde el primer proceso que llega a la cola de listos será el primer proceso a ser despachadoSin embargo, este método tiene la desventaja de que normalmente el tiempo de espera promedio es muy alto, y se puede producir el efecto convoyEste algoritmo es no apropiativo
Planificación de Servicio por Orden de Llegada – Ejemplo
P1 P3P2
0 24 27 30
Proceso Tiempo de Ráfaga P1 24 P2 3 P3 3
P1P3P2
0 63 30
T.E.P. = (0+24+27)/3 = 17
T.E.P. = (6+0+3)/3 = 3
Planificación de Primero el Trabajo más Corto
También se le denomina SJF (Shortest Job First)En este algoritmo, a cada proceso se le asocia la duración de su siguiente ráfaga de CPUAl momento de despachar un proceso, se escoge aquél que tenga la ráfaga más cortaSi dos procesos tienen la misma duración a la hora de despachar, se aplica el método FCFSPuesto que no es posible saber la duración de las ráfagas por adelantado, se utiliza un método predictivo que se basa en la historia de ese proc.Algoritmo no apropiativo
Planificación de Primero el Trabajo más Corto – Ejemplo
P2P1P4
0 163 24
Proceso Tiempo de Ráfaga P1 6 P2 8 P3 7 P4 3
T.E.P. = (3+16+9+0)/4 = 7
P3
9
Planificación de Primero el que Tenga el Menor Tiempo Restante (SRTF)
El algoritmo puede ser apropiativo o no apropiativo, dependiendo de su implementaciónSi se implementa de forma apropiativa, cuando un nuevo proceso llegue a la cola de listos, se verifica su longitud asignada con el tiempo que le queda al que se está ejecutando; si es menor, entonces el proceso ejecutándose se desaloja y se despacha el nuevoA este método se le conoce como Primero el que Tenga el Menor Tiempo Restante (SRTF, Shortest Remaining Time First)
P3P2P1
0 171 26
Proceso Tiempo de Llegada Tiempo de Ráfaga P1 0 8 P2 1 4 P3 2 9 P4 3 5
P4
5
P1
10
T.E.P. = ((10-1)+(1-1)+(17-2)+(5-3))/4 = 26/4 = 6.5
Planificación de Primero el que Tenga el Menor Tiempo Restante (SRTF)
Planificación por Prioridad
En este método, se le asigna a cada proceso una prioridad y el que tenga la prioridad más alta es el que se despacha; los procesos que tengan la misma prioridad se planifican en orden FCFSLas prioridades se manejan internamente como números, aunque la forma en que se interpretan éstos varía de un sistema a otroLas prioridades pueden ser internas o externasCon este algoritmo se puede presentar la inanición (starvation), la cual se combate con envejecimiento (aging)
Planificación por Prioridad – Ejemplo
P4P5P2
0 181 19
Proceso Tiempo de Ráfaga Prioridad P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2
P1
6
P3
16
T.E.P. = (6+0+16+18+1)/4 = 41/5 = 8.2
Planificación por Turno Circular
También se le denomina RR (Round-Robin) y se diseñó especialmente para sistemas interactivos y de tiempo compartido; es similar al FCFS pero con expropiación, para conmutar entre procesosLo que se hace es que se define una unidad de tiempo pequeña, llamada cuanto de tiempoEl algoritmo toma el proceso que sigue de la cola de listos, pone un temporizador (timer) para que levante una interrupción y despacha el procesoCuando se dispara la interrupción el planificador desaloja el proceso y despacha otro nuevo
Planificación por Turno Circular – Ejemplo
P1P3P2
0 224 30
Proceso Tiempo de Ráfaga P1 24 P2 3 P3 3
Cuanto de Tiempo = 4
7 26
T.E.P. = ((10-4)+4+7)/3 = 17/3 = 5.66
P1P1P1P1P1
10 14 18
Planificación por Turno Circular
Si el proceso termina antes de la interrupción, o solicita E/S, en ese momento se desalojaEste algoritmo es apropiativoSe debe buscar un buen cuanto de tiempo, que no sea ni demasiado chico ni demasiado grandeEn general, se debe procurar que el cuanto de tiempo se grande con respecto al tiempo de conmutación; si el tiempo de conmutación es el 10% del cuanto, entonces se gastará aprox. el 10% del tiempo total en conmutaciones
Planificación con Colas de Múltiples Niveles
Este método se puede aplicar cuando los procesos son clasificables fácilmente en grupos distintosAquí se divide la cola de procesos listos en varias colas distintas, con un nivel asociado cada unaUn proceso siempre se asigna a la misma cola, dependiendo de algún atributo en particular de éste (tipo, prioridad, tamaño, etc.)Cada cola maneja su propio algoritmo de planificación y se debe utilizar planificación entre las colas para ver cuál despacha su procesoEste algoritmo es apropiativo
Planificación con Colas de Múltiples Niveles
Planif. con Colas de Múltiples Niveles y Realimentación
A diferencia del método anterior, aquí los procesos sí pueden cambiar de una cola a otraLa idea es separar procesos con distintas características basados en sus ráfagas de CPU; si un proceso gasta demasiado tiempo de CPU se le pasará a una cola de menor prioridadEsto permite que los procesos limitados por E/S y los procesos interactivos se coloquen en las colas de más alta prioridad, pues ellos no consumen mucho tiempo de CPU
Planif. con Colas de Múltiples Niveles y Realimentación
Planif. con Colas de Múltiples Niveles y Realimentación
El algoritmo funciona de la siguiente manera: Inicialmente un proceso se asigna a la cola de
prioridad más alta, si en el cuanto de tiempo no desocupó el CPU se le pasa a la cola inferior y así sucesivamente
Una cola no puede despachar sus procesos hasta que la cola superior esté completamente vacía
Cada cola puede manejar su propio algoritmo de planificación y/o cuantos de tiempo diferentes
Normalmente, si un proceso lleva demasiado tiempo sin ejecutarse se le asciende a la cola superior, con lo que se logra el envejecimiento y se evita la inanición
Planificación con Múltiples Procesadores
Cuando los procesadores son compatibles, lo que se puede hacer es compartir la carga ente ellosPara evitar desbalances se maneja una sola cola de procesos listos y se despachan los procesos al procesador que esté desocupadoSe pueden manejar dos esquemas distintos:
Cada procesador se planifica por su cuenta, donde cada uno revisa la cola y escoge el proceso; hay que programar muy bien éstos para que no haya conflictos
Nombrar un procesador como planificador, lo que produce una estructura de maestro-esclavo