Sistemas Operativos I - Tema 2

Gestión de procesos |1

2. GESTION DE PROCESOS 2.1 Introducción a los procesos SO se define como “un conjunto de extensiones software del hardware original, que culminan en una máquina virtual que sirve como un entorno de programación de alto nivel que gestiona el flujo de trabajo en una red de computadores”. Un proceso es la unidad más pequeña de trabajo individualmente planificable por un SO. La intención de activar un programa ejecutable (compilado y enlazado) es anunciada al SO mediante una orden especializada o por una llamada al SO provista para este fin. El SO responde creando un proceso. Así pues, el proceso es un concepto dinámico que se refiere a un programa en ejecución, que sufre frecuentes cambios de estado y atributos. Multiprogramación: Ejecución concurrente de más de un trabajo o programa que hace obtener una mejor utilización del sistema. Sistemas de tiempo compartido: A cada programa se le asigna un mismo intervalo de tiempo de ejecución en un sistema con multiprogramación interactiva. Multitarea: Capacidad que tienen los sistemas operativos de ejecutar de forma simultánea varios procesos. Multiprocesamiento: Computador que dispone de varios procesadores.

2.2 Relación entre los procesos El SO debe suministrar los servicios necesarios que permitan el procesamiento concurrente. Estos servicios proporcionan los medios para la realización de: a) Ejecución concurrente de los procesos b) Sincronización entre procesos c) Comunicación entre procesos El SO debe disponer de algoritmos de planificación y gestión de procesos que se encarguen de: 1) Decidir qué proceso se ejecutará o tomará el procesador 2) Llevar cuenta de los estados de los procesos, sus prioridades y toda la restante información relevante acerca de ellos. Dependiendo de la interacción entre los procesos, se pueden clasificar: a) Procesos independientes: No se comunican o sincronizan entre ellos. En sistemas monoprocesador, no existen, ya que todos los procesos compiten entre ellos por la posesión del procesador. b) Procesos cooperativos: Se comunican y sincronizan sus actividades para realizar una labor común. c) Procesos competitivos: Al compartirse los recursos de un computador, los procesos necesariamente deben competir entre ellos.

2.3 Especificación de los procesos Los procesos generados por el sistema operativo se denominan implícitos. Una vez terminada su ejecución, su eliminación también la realiza el propio SO. Así mismo, el SO proporciona en tiempo real los servicios que son necesarios para que el usuario pueda definir procesos de forma explícita. Los programas acceden a estos servicios realizando llamadas al sistema. Estas llamadas pueden aparecer incrustadas en el código de un programa de usuario o del propio sistema.

Gestión de procesos |2 Al comienzo de la ejecución del programa principal de un usuario se inicia la ejecución de un proceso. El proceso que crea otro nuevo se denomina proceso padre (parent process), y el proceso creado se denomina proceso hijo (child process). Una vez creado el proceso hijo, la ejecución de ambos transcurre de manera concurrente.

2.4 Estados de los procesos Un proceso puede encontrarse en un instante determinado en uno de los siguientes estados: a) Activo. Está ejecutándose en un instante dado. b) Preparado. En este estado se encuentran todas las tareas que están listas para ejecutarse pero que esperan a que un/el procesador quede libre. c) Bloqueado o suspendido. Tareas que están a la espera de que se cumpla alguna condición y, por lo tanto, no están preparadas para ejecutarse. d) Nonato. El programa existe pero todavía no es conocido por el SO. e) Muerto. El proceso ha terminado su ejecución o bien el SO ha detectado un error fatal y lo ha transferido a dicho estado. Se denomina estado global del sistema en un instante determinado, al conjunto de recursos y procesos existentes con sus estados correspondientes. El SO cambia el estado global del sistema modificando el estado de los procesos y la asignación de los recursos, en respuesta a eventos externos o internos.

2.4.1 Transiciones entre los estados El SO posee un módulo, el planificador, que se encarga de activar los procesos que están en estado preparado. Toda interrupción hace que la tarea que está activa en ese instante deje de ejecutarse a favor del SO que decidirá de entre los procesos preparados, cuál de ellos tiene que ponerse en el estado activo.

Gestión de procesos |3

2.5 El bloque de control de procesos El sistema mantiene toda la información sobre un proceso en una estructura de datos denominada bloque de control de procesos (BCP). En el BCP se guarda la información que necesita el sistema para controlar al proceso y dar cuenta de sus recursos y toda la que influye en la ejecución de un programa: a) El identificador único del proceso (pid) b) El estado de proceso c) La prioridad d) El estado hardware e) La información para gestionar la memoria f) La información de estado del sistema E/S g) La información de contabilidad y planificación Cuando el sistema operativo cambia el procesador entre tareas, utiliza la zona del BCP en la que deja toda la información necesaria para que se pueda proseguir la ejecución de la tarea cuando ésta retome el procesador. En la información contable se mantiene la información necesaria para permitir que los algoritmos de planificación del SO puedan conseguir organizar los procesos de modo que se obtenga el mejor comportamiento posible del sistema o lo que es equivalente, el rendimiento óptimo en el uso de procesador. Informaciones relevantes son: hora de inicio del proceso, el tiempo real del uso del procesador, el tiempo de espera para conseguir un determinado recurso y el tiempo medio transcurrido desde que el proceso está preparado hasta que consigue el procesador.

2.5.1 Listas de procesos El SO mantiene listas de BCP para cada uno de los estados del sistema. Cada proceso pertenece a una única lista. El planificador del SO se encarga de gestionar el paso de los procesos de una lista a otra, manteniendo las listas ordenadas y actualizadas de la forma más conveniente para las rutinas que operan sobre ellas. El proceso puede estar en una lista única de estados bloqueados o en una lista de estados suspendidos ligada en exclusiva a un dispositivo o evento.

2.6 Procesos y hebras Podemos ver el proceso como una entidad formada por una o más unidades de ejecución denominadas hebras (threads) y un conjunto de recursos asociados. Si un proceso pasa al estado activo una hebra toma posesión del procesador; ésta se puede interrumpir para que se pase a ejecutar otra hebra, y así sucesivamente hasta que el proceso sale de dicho estado. Los recursos no están asociados a las hebras, si no al proceso; éste es el que puede acceder de forma protegida a los recursos del sistema y se encarga de su gestión entre las hebras. La creación de una hebra dentro de un proceso requiere menos tiempo que la creación de un proceso nuevo. También mejora el tiempo de conmutación entre hebras con respecto al de los procesos. Además, las hebras comparten la memoria y los ficheros asignados al proceso, lo que facilita su comunicación y sincronización. La implementación en base a hebras en lugar de procesos aumenta la velocidad del sistema. Parte de la planificación se realiza tomando como base a éstas. Un proceso está en ejecución cuando se está ejecutando al menos una de sus hebras. En el estado preparado alguna hebra debe de estarlo para poder pasar a ejecución. La suspensión del proceso, sin embargo, afecta a todas las hebras, ya que el sistema operativo lo transfiere fuera de la memoria principal y la gestión se realiza, por lo tanto, a nivel de proceso.

Gestión de procesos |4

2.7 El planificador de procesos Planificador: software del SO encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Hay dos tipos fundamentales que coexisten en un SO.

a) Planificador a largo plazo (PLP): o planificador de trabajos. Determina qué trabajos se admiten en el sistema para su procesamiento y son, por lo tanto, cargados en la memoria disponible. Es el principal responsable de que se cumplan los criterios de gestión establecidos para la utilización global del sistema; debe realizar una mezcla adecuada de trabajos destinados al procesador y trabajos destinados al sistema de E/S. Lo más usual es definir una función de prioridad y asignarle a cada programa un valor para la misma que se actualiza en instantes determinados por el PLP. Las tareas con mayor prioridad se llevan al estado preparado. Como norma general se puede afirmar que el PLP sólo existe en sistemas que admiten procesamiento por lotes. b) Planificador a corto plazo (PCP): Selecciona al proceso que pasará al estado activo de entre todos los procesos residentes en memoria que están en el estado preparado. Este algoritmo se ejecuta muchas veces entre dos invocaciones al PLP. Su elevada frecuencia de uso hace que el algoritmo suela ser sencillo para evitar gastar mucho tiempo del procesador en su ejecución. Este algoritmo se llama, siempre que un evento origina un cambio en el estado general del sistema, para determinar si dicho evento implica un cambio en el proceso que debe pasar al estado activo. Entre los eventos que suelen producir una invocación al PCP están: a) Las señales del reloj del sistema b) Las interrupciones c) La finalización de las operaciones de E/S d) Las llamadas al SO e) El envío y la recepción de señales f) La activación de programas interactivos Algunos sistemas introducen un planificador de nivel intermedio denominado planificador a medio plazo (PMP). Se basa en el hecho de que a veces es conveniente llevar a la memoria secundaria un proceso que ha sido suspendido en su ejecución por algún evento.

Gestión de procesos |5 2.7.1 Algoritmos de planificación En los sistemas actuales es posible encontrar una gran variedad de algoritmos. Los algoritmos tienen distintas propiedades según los criterios en los que se basen para su construcción. Se debe considerar: a) Eficacia. Porcentaje del tiempo medio de utilización. b) Rendimiento. Número de procesos completados por unidad de tiempo. c) Tiempo de retorno o regreso. Intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que se completa por el sistema. d) Tiempo de espera. Tiempo que el proceso espera hasta que se le concede el procesador. e) Tiempo de respuesta a un evento. Intervalo de tiempo que transcurre desde que se señala un evento hasta que se ejecuta la primera instrucción de la rutina de servicio de dicho evento.

2.7.2 Planificación por expropiación El proceso que se está ejecutando puede ser interrumpido y pasado al estado de preparado por parte del SO. En los algoritmos con estrategia de no expropiación el proceso que está activo permanece con el procesador hasta que él mismo devuelve el control al SO.

2.7.3 Planificación por prioridades Cada proceso tiene asignada una prioridad, el que tenga mayor prioridad en el estado preparado es el que toma el procesador. La asignación puede ser: a) Estática. No cambia durante el tiempo en que el proceso existe. b) Dinámica. Cuando la prioridad puede ser modificada por el propio usuario o por el sistema. La modificación se suele realizar en función de ciertos parámetros como la cantidad de memoria que utiliza, el número de acciones de E/S que lleva realizado, el tiempo medio de utilización del procesador hasta ese momento, el número de ficheros abiertos, etc. Los algoritmos con expropiación y con prioridades se dice que están guiados por eventos (eventdriven). Problema: que los procesos con menor prioridad queden relegados y sin posibilidades de utilizar el procesador. Para evitar esto, la solución que se suele adoptar es la de ir aumentando la prioridad de aquellos procesos que llevan un tiempo de espera muy elevado (estrategia de prioridad por envejecimiento, aging).

2.7.4 Planificación FCFS: primero en llegar, primero en ser servido “First Come, First Served”. Modo más sencillo de planificación. No expropiación. Rara vez se utiliza en la actualidad, pero se emplea dentro de otros esquemas.

2.7.5 Planificación SJF: primera tarea más corta “Shortest Job First”. No expropiativa. A cada trabajo o proceso se le asocia una estima del tiempo que le resta para finalizar su ejecución y la selección se realiza en base a dicho tiempo. Si dos trabajos tienen el mismo tiempo se seleccionan según la estrategia FCFS. En entornos de producción donde los trabajos se ejecutan regularmente es posible tener una estima aceptable, pero en entornos de desarrollo rara vez se conoce el tiempo que tardará en ejecutarse un programa.

Gestión de procesos |6 2.7.6 Planificación SRT: tiempo que queda más corto “Shortest Remaining Time”. Versión expropiativa del método SJF. Se elige al proceso al que le quede menos tiempo de ejecución, incluyendo a los nuevos que lleguen. Tiene mayor frecuencia de invocación del planificador, a la vez que una carga superior en las labores que tiene que realizar.

2.7.7 Planificación RR: prioridad circular “Round Robin” (RR). A todos los procesos en el estado preparado se les asigna un tiempo de ejecución denominado cuanto. El planificador va asignando el procesador a cada tarea de forma secuencial por el cuanto de tiempo definido. Si un proceso necesita un tiempo de ejecución mayor que su cuanto asociado, una vez transcurrido éste y si existen más procesos en espera de ejecución, se coloca al final de la lista del estado preparado y el procesador pasa al proceso que queda en la cabeza de la lista. Resulta muy adecuado en sistemas de tiempo compartido. Necesita un temporizador que controle el cuanto asignado a los procesos y genere una interrupción siempre que se produzca su finalización. El problema más importante que se plantea en un algoritmo del tipo RR, es el de fijar el valor del cuanto ya que su elección supone llegar a un compromiso entre la eficacia del procesador y el tiempo de respuesta.

2.7.8 Planificación basada en el reloj de tiempo real La mayoría de los sistemas disponen de un reloj de tiempo real (RTR) que se encarga de generar una señal de forma periódica utilizada para producir una interrupción a un intervalo de tiempo fijo. La atención a estas interrupciones se debe diseñar para que se realice rápidamente ya que si se tarda mucho tiempo en atenderla, o si se opera con la interrupción inhibida durante más de un ciclo de reloj, ésta se perderá. En muchos casos puede ser conveniente ralentizar al reloj para, a pesar de perder precisión, lograr una funcionalidad más rica. A la velocidad real de ejecución efectiva del código de tratamiento se la conoce como velocidad de tic. El SO utiliza el RTR para: a) Limitar el intervalo de tiempo en el que un proceso puede estar en ejecución. b) Proporcionar servicios a los usuarios, como iniciar tareas cíclicas y la función retardo. La rutina de tratamiento de la interrupción del RTR se encarga de mirar la lista de los procesos retardados y de pasar al estado preparado a aquellos para los que haya transcurrido el tiempo de retardo.

2.7.9 Planificación MLQ: colas multinivel “Multi Level Queue”. Se utilizan algoritmos de planificación en los que se clasifican las tareas en diferentes grupos a los que se aplican distintas estrategias de planificación. Se crean colas de tareas separadas que se gestionan por criterios diferentes. Cada tarea se asigna a una sola cola de acuerdo con alguna propiedad de la tarea. La cola de procesos del SO debe tener prioridad absoluta sobre la de los programas interactivos y por lotes y sólo se ejecutará una tarea de lotes si las otras dos colas están vacías.

2.7.10 Planificación MLFQ: colas multinivel con realimentación “Multi Level Feedback Queue”. En MLQ a las tareas se les asigna una cola de forma fija. En las colas multinivel con realimentación si se permite la movilidad entre las colas. Para ello, las colas se organizan según sus características de uso del procesador. Las tareas que emplean poco el procesador se mantienen en las colas de mayor prioridad y las que lo utilizan mucho se sitúan en las colas de menor prioridad.

Gestión de procesos |7 Una tarea que entra en el estado preparado se coloca en el nivel 1. Si no finaliza su ejecución en 10 milisegundos se pasa a la cola del nivel 2. Si la cola del nivel 1 está vacía se pasa a ejecutar la tarea que se encuentra en cabeza de la cola del nivel 2. Si ésta no finaliza su ejecución en los 20 milisegundos que tiene asignada resulta expropiada y pasa a la cola de nivel 3. Existen muchos algoritmos posibles de planificación por MLFQ que pueden definirse de forma más general por los parámetros siguientes: a) el número de colas b) el algoritmo de planificación de cada cola c) los métodos que determinan el movimiento de las tareas entre colas d) el método que indica la cola en la que entra una tarea cuando necesita un servicio

Gestión de procesos |8