Capítulo 4: Elementos y estructura del sistema operativo. Procesos
Planificación de procesos
Una de las claves para que un sistema multiprogramado sea eficaz es la Planificación de procesos, que consiste en ir asignando procesos al procesador (o procesadores / núcleos) a lo largo del tiempo, de forma que se cumplan los objetivos en varios aspectos:
-
Rendimiento: Trata de maximizar el número de acciones que se completan en un plazo de tiempo determinado.
-
Tiempo de respuesta: El sistema debe responder a las solicitudes de los usuarios en un tiempo adecuado.
-
Tiempo de retorno: El sistema debe ofrecer resultados de los procesos por lotes en un tiempo adecuado.
-
Equidad: Todos los procesos deben ser considerados según sus características.
-
Eficiencia: Se debe aspirar a que el procesador esté activo constantemente.
Como cabe esperar, el módulo del sistema operativo que se encarga de esta tarea se denomina Planificador (en inglés, Scheduler).
Según el diseño del sistema operativo, el Planificador utilizará unos criterios u otros para llevar a cabo su tarea. Estos criterios reciben el nombre de Algoritmos de Planificación (o también, Políticas de Planificación).
Una política de planificación es no apropiativa (en inglés, non-preemptive) cuando, una vez que un proceso toma el control del procesador, no lo abandona hasta que termina o hasta que se bloquea. Será apropiativa (en inglés, preemptive) cuando el sistema puede interrumpir el proceso para ejecutar otro diferente.
A continuación, nombramos los más importantes:
Primero en llegar primero en ser servido, o FCFS (del inglés, First Come First Served)
Se emplea en procesos por lotes (sin intervención del usuario) y es no apropiativo. Los procesos se van poniendo en cola según llegan y se les asigna el estado Preparado. Cuando es asignado al procesador, no lo abandona hasta que termina.
Una de sus ventajas principales consiste en que es un algoritmo muy sencillo de implementar y también es fácilmente predecible.
Entre sus principales inconvenientes podemos mencionar que los procesos largos pueden hacer esperar mucho a los procesos cortos y que el tiempo de servicio mínimo variará mucho según el número de procesos ejecutados y la duración de los mismos. Además, el tiempo medio de espera depende de que lleguen antes los procesos más cortos o los más largos.
Para entender su funcionamiento, podemos estudiar el siguiente ejemplo práctico en el que disponemos de cinco procesos que se incorporan al sistema en momentos sucesivos y que tienen diferentes tiempos de duración:
Si analizamos de forma gráfica el comportamiento del sistema, observaremos que se comporta del siguiente modo.
En consecuencia, podemos extraer las siguientes conclusiones:
Actividad 2: Planificación FCFS
Supón que tenemos tres usuarios y que cada uno necesita ejecutar un proceso por lotes distinto:
-
El primero necesitará 18 minutos para ejecutarse.
-
El segundo necesitará 6 minutos.
-
El tercero otros 7 minutos.
Sabiendo que el tiempo medio de respuesta será la suma de los tiempos que espera cada usuario para obtener sus resultados, dividido entre tres, ¿tendrá alguna importancia el orden en el que se planifiquen los procesos si utilizamos un algoritmo FCFS y sólo disponemos de un procesador?
Para ilustrar tu conclusión, deberás crear gráficas con las diferentes combinaciones y calcular el tiempo medio de respuesta en cada caso.
Primero el más corto, o SJF (del inglés, Shortest Job First)
Se emplea en procesos por lotes (sin intervención del usuario) y es no apropiativo. Los procesos se van poniendo en cola según llegan y se les asigna el estado Preparado, pero el Planificador elige el que tiene un menor tiempo previsto de ejecución.
Como en el caso anterior, podemos estudiar un ejemplo práctico para entender su funcionamiento. En este caso, partiremos de los mismos datos, para que puedas comparar los resultados:
Y analizando los resultados, obtendríamos la siguiente tabla:
Existe una versión apropiativa de este algoritmo denominada Primero el de menor tiempo restante, o SRTN (del inglés, Shortest Remaining Time Next). En este caso, si un proceso bloqueado pasa al estado Preparado, el distribuidor comprueba si su tiempo restante es inferior que el del proceso que se encuentra en ejecución. En caso afirmativo, éste toma el control del procesador y el proceso que está ejecutándose pasa al estado Preparado.
Aunque es un algoritmo muy eficaz para los procesos cortos, resulta difícil predecir los intervalos de asignación del procesador e, incluso, puede haber procesos largos que sufran de inanición, es decir, que no lleguen a ejecutarse mientras existan procesos cortos esperando turno.
Como antes, lo ilustraremos con un ejemplo. En este caso, hemos cambiado ligeramente los datos iniciales para que sea más ilustrativo:
Y el gráfico resultante quedará como sigue:
De nuevo, aquí tienes los datos arrojados, representados en forma de tabla:
Actividad 3: Planificación SRTN
Supón que tenemos tres usuarios y que cada uno necesita ejecutar un proceso por lotes distinto:
-
El primero necesitará 18 minutos para ejecutarse, y es el único que está listo al principio.
-
El segundo necesitará 10 minutos y está disponible a partir del minuto 7.
-
El tercero necesitará 6 minutos y está disponible a partir del minuto 21.
A partir de estos datos, crea una gráfica donde se aprecie el orden de ejecución de los procesos suponiendo que usamos el algoritmo SRTN si el Planificador toma el control del sistema una vez por minuto (y desestimamos el tiempo que se está ejecutando).
A continuación, crea una tabla donde expreses el tiempo de respuesta y el tiempo de espera en función de los datos de entrada.
Por turnos, o RR (del inglés, Round Robin)
Se emplea en procesos interactivos (en los que interviene el usuario) y es apropiativo. Los procesos se van poniendo en cola según llegan y se les asigna el estado Preparado. El procesador se irá asignando a cada proceso, por orden, durante una fracción de tiempo llamada Quantum, que es igual para todos. Si el proceso se acaba, se bloquea, o si se agota su tiempo, el procesador es liberado para el siguiente proceso de la lista.
Por lo tanto, la cola de procesos actúa como una estructura circular con organización FIFO.
Para ilustrarlo, comenzaremos por los mismos datos de entrada del ejemplo anterior, suponiendo un Quantum equivalente a tres unidades de tiempo. El resultado sería como el que muestra la siguiente imagen:
Para facilitar la comprensión, hemos incluido también una representación gráfica de los procesos que se encuentran en cola para ser ejecutados y del proceso que se encuentra en ejecución en cada unidad de tiempo.
Finalmente, la siguiente tabla muestra los datos que ofrece:
Actividad 4: Planificación por turnos
Partiendo de los mismos datos de entrada que en la actividad anterior, aplica la planificación por turnos suponiendo un Quantum equivalente a tres unidades de tiempo. Debes realizar las siguientes tareas:
-
Crea un esquema, como el aportado en el capítulo, pero teniendo en cuenta los ‘Momentos de llegada’ y la ‘Duración’ de los procesos de la actividad anterior.
-
A continuación, crea una nueva versión de la tabla de planificación, ajustando su contenido al diseño del esquema creado en el apartado anterior.
Planificación por prioridad
Se emplea en procesos interactivos (en los que interviene el usuario) y es apropiativo. A cada proceso se le asigna un número entero que representa su prioridad, de modo que, cuanto menor es el número, mayor es la prioridad.
Si se considera un algoritmo no apropiativo, funcionaría como el algoritmo Primero el más corto (SJF), pero considerando la prioridad en lugar de la duración.
Aún así, veamos un ejemplo, suponiendo que todos los procesos están disponibles desde el primer momento. Estos serían nuestros datos de partida
Siguiendo la asignación del procesador según el orden de prioridad (el más bajo primero), obtendríamos el siguiente gráfico:
Finalmente, en la siguiente tabla recogemos los datos numéricos obtenidos:
Para evitar que los procesos con una prioridad más elevada monopolicen el uso del procesador (y los de prioridad más baja padezcan inanición), la prioridad de los procesos puede ir reduciéndose cada vez que obtengan el uso del procesador. Así, se convertiría en una versión apropiativa que funcionaría como Primero el de menor tiempo restante (SRTN), pero tomando la prioridad en lugar de la duración y disminuyéndola cada vez.
Como hemos comentado más arriba, en el caso de que los procesos puedan tener diferentes prioridades, el Planificador elegirá siempre al proceso de mayor prioridad para su ejecución. Y en el caso de que existan varios procesos con el mismo grado de prioridad, es común que se establezca un turno rotatorio entre ellos.
El modo de implementar esta característica puede consistir en mantener una cola de procesos en estado Preparado para cada uno de los posibles niveles de prioridad.
Como hemos dicho más arriba, para evitar que los procesos con menor prioridad puedan padecer inanición, en los procesos de mayor prioridad, ésta puede ir degradándose en función de su antigüedad o de la frecuencia con la que hayan obtenido el uso del procesador.
Por lo tanto, el esquema sobre los estados de un proceso que vimos al principio podría quedar como sigue:
Planificación por reparto equitativo, o FSS (del inglés, Fair-share Scheduling)
Se emplea en procesos interactivos (en los que interviene el usuario) y es apropiativo. Se tiene en cuenta el número de usuarios que serán atendidos, de modo que el tiempo de ejecución se reparte entre ellos de forma equitativa. La ejecución del conjunto de procesos de cada usuario no sobrepasará el tiempo asignado a dicho usuario.
Este concepto puede ampliarse a grupos de usuarios, de modo que las decisiones de planificación otorguen a cada grupo de usuarios un servicio equivalente. De este modo, el uso intensivo del sistema por parte de un grupo de usuarios no perjudicará a los demás grupos.
Planificación de Colas Múltiples, o MQS (del inglés, Multilevel Queue Scheduling)
Se emplea tanto en procesos interactivos como en procesos por lotes (en los que no interviene el usuario) y es apropiativo. Consiste en fragmentar la cola de procesos en estado Preparado en varias colas más pequeñas, de modo que cada una puede estar administrada por un algoritmo de planificación diferente. De este modo, cada proceso será asignado a una determinada cola en función de sus características pudiendo tratar de manera diferente, por ejemplo, a los procesos interactivos y a los procesos por lotes.
Del mismo modo que en algunas situaciones puede ser interesante contemplar diferentes colas de procesos en estado Preparado, puede ser conveniente disponer de una cola de procesos en estado Bloqueado para cada tipo de suceso. De esta forma, el sistema evita recorrer toda la lista de bloqueados para localizar el proceso que está esperando un suceso concreto.
