PLANIFICACIÓN DE MONOPROCESADORES
En un sistema multiprogramado, la memoria principal contiene varios procesos. Cada proceso alterna entre usar el procesador y esperar que se realice una operación de E/S o que ocurra algún otro suceso. El procesador o los procesadores se mantienen ocupados ejecutando un proceso mientras los demás esperan. La clave de la multiprogramación está en la planificación.
![]()
![]()
|
Tipos de Planificación |
Planificación del procesador |
Planificación a Largo Plazo ® De Nuevo a Listo Planificación a Medio Plazo ® De Suspendidos a No Suspendidos Planificación a Corto Plazo ® De Listo a Ejecución |
|
|
Planificación de E/S |
|
PLANIFICACIÓN A LARGO PLAZO
- Determina cuáles programas son admitidos en el sistema. Una vez aceptado, el programa de usuario se convierte en proceso y se añade a la cola del planificador a corto plazo
- Controla el grado de multiprogramación
- En un sistema de procesos por lotes, los procesos recién incorporados se encaminan hacia el disco y permanecen detenidos en una cola de procesamiento por lotes.
- Primera decisión a tomar: decidir si el S.O. puede acoger algún proceso más (o sea si se debe crear un proceso nuevo aceptando un programa). Cuanto más procesos se crean, menor es el porcentaje de tiempo en el que cada proceso puede ejecutar. Así pues, el planificador a largo plazo puede limitar el grado de multiprogramación para ofrecer un servicio satisfactorio al conjunto de procesos actual. Además, si la fracción de tiempo que el procesador está desocupado supera cierto umbral, se puede volver a invocar al planificador a largo plazo.
Segunda decisión a tomar: cuál va a ser el siguiente proceso a admitir. Puede basarse en el algoritmo FCFS o algún otro criterio que tenga en cuenta prioridades, tiempos de ejecución esperados y exigencias de E/S
PLANIFICACIÓN A MEDIO PLAZO
La planificación a medio plazo forma parte de la función de intercambio. Los temas relacionados se tratan en los capítulos 3 y 6. Generalmente, la decisión de cargar un proceso en memoria principal se basa en la necesidad de controlar el grado de multiprogramación. Así pues, la decisión de carga en memoria tendrá en cuenta las necesidades de memoria del proceso descargado. Este nivel de planificación es realizado por el Planificador de trabajos o Job Scheduler.
PLANIFICACION A CORTO PLAZO
El planificador a corto plazo, llamado dispatcher o distibuidor, se ejecuta cuando ocurre un suceso que puede conducir a la interrupción del proceso actual o que ofrece la oportunidad de expulsar de la ejecución al proceso actual a favor de otro. Como ejemplos de estos sucesos se tienen: interrupciones de reloj, interrupciones de E/S, llamadas al S.O., señales, etc.
ALGORITMOS PARA LA PLANIFICACION A CORTO PLAZO
El planificador a corto plazo es el módulo del sistema operativo que decide qué proceso se debe ejecutar, usando para ello un algoritmo de planificación que debe cumplir con los siguientes objetivos:
- Imparcialidad
- Política justa
- Eficiencia: mantener la CPU ocupada en lo posible el mayor tiempo con procesos de usuario.
- Minimizar el tiempo de espera de usuarios.
- Maximizar el número de procesos ejecutados.
- Tiempo de respuesta excelente.
First Come – First Server (FCFS)
- También se denomina FIFO (First in - first out)
- Rinde mucho mejor con procesos largos que con procesos cortos. Puede existir una larga espera para un proceso si un proceso corto llega justo después que un proceso largo.
- Tiende a favorecer a los procesos con carga de CPU frente a los que tienen carga de E/S. Cuando un proceso con carga de CPU está ejecutando, todos los que tienen carga de E/S deben esperar. Algunos de ellos pueden estar en colas de E/S (estado bloqueado) pero puede ser que regresen a la cola de Listos mientras el de la carga de CPU todavía está ejecutando, quedando ociosos los dispositivos de E/S. Cuando un proceso abandona el estado de ejecución, los procesos Listos con carga de E/S pasarán rápidamente por el estado de ejecución y volverán a bloquearse por sucesos de E/S. Si el proceso con carga de CPU también está bloqueado, el procesador pasa a estar desocupado. FCFS puede dar como resultado un uso ineficiente tanto del procesador como de los dispositivos de E/S.
Round Robin (Turno rotatorio)
- Reduce la penalización que sufren los trabajos cortos con FCFS
- Periódicamente se genera una interrupción de reloj, el proceso que está ejecutando se sitúa en la cola de Listos y se selecciona el siguiente trabajo, según un FCFS.
- La longitud del quantum de tiempo a usar es importante. Si el quantum es muy pequeño, los procesos cortos pasan por el sistema rápidamente. Por otro lado, se produce una sobrecarga en la gestión de las interrupciones del reloj y en la ejecución de las funciones de planificación y expedición. En el caso límite de un quantum mayor que el mayor tiempo de ejecución, el round robin se transforma en FCFS.
- Generalmente, un proceso con carga de E/S tiene ráfagas de procesador más cortas que un proceso con carga de CPU. Un proceso con carga de procesador generalmente hace uso de un quantum de tiempo completo cuando ejecuta e inmediatamente regresa a la cola de Listos. Así, los procesos con carga de CPU tienden a recibir una porción desigual de tiempo de procesador, lo que origina un rendimiento pobre de los procesos con carga de E/S, un mal aprovechamiento de los dispositivos de E/S y un incremento en la variabilidad del tiempo de respuesta.
Virtual Round Robin
Evita el último problema mencionado en el Round Robin utilizando una cola auxiliar. Los nuevos procesos se unen a la cola de Listos, gestionada según FCFS. Cuando un proceso termina su quantum de ejecución, vuelve a la cola de Listos. Cuando un proceso se bloquea por E/S, se añade a la cola de E/S. La nueva característica consiste en una cola FCFS auxiliar a la que se desplazan los procesos una vez que son liberados de la espera por E/S. Al tomar una decisión sobre el siguiente proceso a expedir, los procesos de la cola auxiliar tienen preferencia sobre los de la cola principal de Listos. Cuando se expide un proceso desde la cola auxiliar, no puede ejecutar más que un tiempo igual al quantum básico menos el tiempo total de ejecución consumido desde que fue seleccionado por última vez en la cola de Listos.
Shortest Process Next (SPN)
- Selecciona el proceso con menor tiempo esperado de ejecución.
- Un proceso corto saltará a la cabeza de la cola, sobrepasando a trabajos largos. Puede generar inanición para los procesos largos si existe un flujo continuo de procesos más cortos.
- Plantea la necesidad de conocer o por lo menos estimar, el tiempo exigido por cada proceso.
- No es conveniente para ser usado en entornos de tiempo compartido o de procesamiento de transacciones, debido a la ausencia de apropiación.
Shortest Remaining Time (SRT)
- Es una versión apropiativa del SPN.
- El planificador debe disponer de una estimación del tiempo de proceso para poder llevar a cabo la función de selección, existiendo el riesgo de inanición para procesos largos.
Highest Response Ratio Next (HRRN)
- Se elige el proceso Listo con un valor mayor de RR (Response Ratio).
RR = (m + s) / s
Siendo m = tiempo consumido esperando al procesador
s = tiempo de servicio esperado
- Tiene en cuenta la edad del proceso.
- Aunque favorece a los trabajos más cortos (un denominador menor produce una razón mayor), el envejecimiento sin que haya servicio incrementa el valor de la razón, de forma que los procesos más largos pasen finalmente primero, en competición con los más cortos.
Feed-Back (Realimentación)
- Penaliza a los trabajos que han estado ejecutando por más tiempo.
- Planificación apropiativa y aplicando un mecanismo dinámico de prioridades.
- Cuando un proceso entra por primera vez en el sistema, se sitúa en RQ0. Cuando vuelve al estado Listo, después de su primera ejecución, se incorpora a RQ1. Y ante cada ejecución siguiente, se envía al nivel inferior de prioridad. Dentro de las colas se usa un mecanismo FCFS.
- Si un proceso está en la cola de menor prioridad existente, no puede descender, sino que vuelve a la misma cola repetidamente hasta completar su ejecución. Por lo tanto, esa cola se trata con turno rotatorio.
- Presenta el problema de que el tiempo de retorno de un proceso largo puede alargarse mucho, o hasta puede ocurrir inanición si llegan regularmente nuevos trabajos al sistema. Para compensar, se puede variar el tiempo de apropiación en función de la cola: un proceso planificado para RQ1 dispone de 1 unidad de ejecución hasta ser expulsado; a un proceso en RQ2, se le permite ejecutar durante 2 unidades de tiempo; y así sucesivamente.
- Se puede evitar la inanición promocionando un proceso a la cola de mayor prioridad luego de que haya esperado servicio en su cola actual durante un cierto tiempo.
Fair-Share Scheduling (FSS – Planificación por reparto equitativo)
- Todos los algoritmos propuestos hasta ahora tratan el conjunto de procesos Listos como una única reserva de procesos en donde se selecciona el que pasará a ejecución. Pero en un sistema multiusuario, si las aplicaciones o trabajos de los usuarios pueden organizarse en forma de varios procesos (o hilos), se dispone de una estructura para el conjunto de procesos que no se identifica con ningún planificador tradicional. Desde el punto de vista del usuario, el interés no está en cómo se comporta un proceso en particular, sino en cómo se comporta el conjunto de procesos de usuario que constituyen una aplicación.
- La FSS tiene en cuenta el historial de ejecución de un grupo afín de procesos, junto con el historial de ejecución individual de cada proceso.
- La planificación se lleva a cabo por prioridades. Cuanto mayor es el valor numérico de la prioridad, menor es ésta. Se tiene en cuenta para la asignación de prioridades:
. Prioridad básica del proceso
. Uso de CPU recientemente por parte del proceso
. Uso de CPU recientemente por parte del grupo al que pertenece