Unidad V. Administración de procesos
El administrador de procesos se encarga de seleccionar el proceso en turno a ser ejecutado en el CPU.
- El "scheduler" elige el próximo proceso a ejecutarse por el procesador. Esto depende de una estrategia de calendarización que debe tomar en cuenta la prioridad del proceso.
- El administrador de recursos asigna memoria y un procesador para el proceso a ejecutarse.
- El despachador toma el proceso de la lista, lo carga en el procesador y empieza la ejecución.
Proceso.- Un proceso es un programa en ejecución: aquél cuyas instrucciones son ejecutadas en ese momento por el CPU. Entidad que puede ser asignada y ejecutada por un procesador. Un proceso tiene un espacio de direcciones (ambiente, recursos) privado. Espacio virtual de direcciones e información de control necesaria para la ejecución de un programa.
Diferencia entre proceso y programa :
- Un programa lo forma sólo un código. Es un concepto estático.
- Un proceso lo forma el programa, la pila, los registros del procesador (como puede ser el Contador de Programa (CP), Acumuladores,.). Es un concepto dinámico.
Identificador de proceso (PID).- Identificador numérico que distingue de forma única un proceso en curso. Este es un entero no negativo asignado por el sistema. Puede ser usado para garantizar unicidad dentro de una máquina.
Además de la identificación del proceso, un proceso tiene asociado un identificador de usuario real (identificador de usuario del propietario), un identificador de usuario efectivo (que determina los privilegios que un proceso tiene cuando se ejecuta), un identificador de grupo (al que pertenece el usuario) y un identificador de grupo efectivo.
Estados de procesos.- Dado que en un sistema de tiempo compartido coexiste en forma concurrente un conjunto de procesos en el sistema, en donde se incluyen procesos del sistema y procesos de los usuarios. Esta concurrencia produce que los procesos se puedan encontrar en diferentes estados, ya que por ejemplo, en un momento dado solo un proceso puede estar en ejecución. A continuación se presenta una figura que refleja la relación entre los distintos estados posibles que puede presentar un proceso.
Los tres estados básicos son:
- En ejecución: Proceso esta utilizando la CPU, las instrucciones se están ejecutando.
- Listo: Proceso está en condiciones de ejecutarse, pero esta esperando que se le asigne tiempo de CPU.
- Bloqueado : Proceso está esperando que ocurra un evento externo (como la terminación de una E/S).
Los procesos pueden tomar cualquiera de los estados mencionados y la transición entre uno y otro estado tiene su explicación. Las siguientes son las transiciones posibles:
• Ejecución - Bloqueado: Un proceso pasa de ejecución a bloqueado cuando ejecuta una instrucción que implica la espera de un evento, por ejemplo debe esperar que ocurra efectivamente la E/S, espera por la activación de un semáforo, etc.
• Ejecución - Listo: Un proceso pasa de ejecución a listo, cuando se le acaba el tiempo asignado por el planificador de procesos del sistema, en este momento el sistema debe asignar el procesador a otro proceso.
• Listo - Ejecución: Un proceso pasa de listo a ejecución cuando el sistema le otorga un tiempo de CPU.
• Bloqueado - Listo: Un proceso pasa de bloqueado a listo cuando el evento externo que esperaba sucede.
Tabla de Procesos.- Para manejar la información de todos los procesos, el sistema operativo maneja una tabla de procesos, la que contiene una entrada por la información de cada proceso, a cada una de estas entradas en la tabla de procesos se le conoce con el nombre de PCB (Process Control Block).Por lo general esta estructura posee diversa información asociada al proceso, en general esta información incluye:
- Estado del proceso: El estado puede ser en ejecución, listo o bloqueado.
- Contador de programas: El PC contiene la dirección de la siguiente instrucción a ejecutar por el proceso.
- Información de planificación: Esta información incluye prioridad del proceso, apuntadores a colas de planificación, etc.
- Información contable: Esta información incluye cantidad de tiempo de CPU asignado, hora de inicio del proceso, etc.
- Información de planificación de memoria: Esta información incluye información de registros límites de acceso, punteros a segmentos de datos, códigos, etc.
- Información del Sistema de archivos: Esta información incluye protecciones, identificación de usuario, grupo, etc.
- Información del estado de E/S: Esta información incluye, solicitudes pendientes de E/S, dispositivos de E/S asignados al proceso, etc.
La concurrencia es la activación de varios procesos a la vez. La concurrencia se consigue haciendo que:
- Los procesadores se asignen a distintos procesos (paralelismo o concurrencia real).
- Se alternen varios procesos en un mismo procesador (concurrencia aparente o simulada).
Sólo tendremos concurrencia real en sistemas multiprocesador (en un sistema uniprocesador existe una concurrencia aparente).
El procesado concurrente o paralelo aparece cuando varios procesos se encuentran en un instante determinado en un estado intermedio entre sus estados inicial y final.
La programación concurrente es mucho más difícil que la secuencial. Los programas concurrentes son más difíciles de escribir, depurar y modificar, y es más difícil probar que son correctos. La programación concurrente ha despertado un gran interés porque permite expresar de una forma natural las soluciones a ciertos problemas de carácter inherentemente paralelo y también por el paralelismo de hardware que se logra con los multiprocesadores y sistemas distribuidos.
Ya sabemos que un proceso es un programa en ejecución, es decir, es la actividad que resulta de la ejecución de un algoritmo, con sus datos, sobre un procesador. En un ordenador los procesos no se suelen ejecutar de forma aislada, sino que acostumbran a ejecutarse con otros de forma solapada en el tiempo, ya que compartiendo adecuadamente los recursos físicos se puede obtener una aceleración global de la velocidad de cálculo del sistema. Así, en general, decimos que dos procesos son concurrentes si su ejecución se solapa en el tiempo. Si tales procesos comparten el procesador, decimos que se ejecutan en multiprogramación , mientras que si n procesos se ejecutan sobre n procesadores, entonces tenemos ejecución paralela . En este último caso, si los procesadores comparten una memoria central común, se tiene un sistema multiprocesador , mientras que si los procesadores están conectados mediante una red de comunicaciones, entonces tenemos procesamiento distribuido.
Planificación por orden de llegada: FCFS (First Come First Served)
Es la disciplina de planificación más simple. La carga de trabajo se procesa por orden de llegada. Ofrece un bajo rendimiento y un índice de productividad bajo al no considerar el estado del sistema y las necesidades de recursos de los procesos, y un pobre tiempo de respuesta a sucesos del sistema debido a la falta de prioridad de los procesos y a no ser una planificación apropiativa.
Planificación del trabajo más corto primero: SJF (Shortest Job First)
Es una planificación no apropiativa según la cual se ejecuta primero el proceso en espera que tenga menor tiempo estimado de ejecución hasta terminar. SJF reduce el tiempo de espera promedio del FCFS.
SJF favorece a los trabajos cortos frente a los largos.
El problema que tiene es que se exige conocer con exactitud el tiempo que tardará en ejecutarse un proceso y esa información no suele estar disponible; por ello, se basará en los tiempos estimados de otras ejecuciones (esto se puede obtener en sistemas de producción). Por otra parte, SJF requiere que todos los trabajos se encuentren disponibles simultáneamente. Esta planificación, al igual que FCFS, no es apropiativa y, por tanto, no resulta útil en ambientes de tiempo compartido en los que se deben garantizar tiempos de respuesta razonables.
En el caso de 4 trabajos con tiempos de ejecución a, b, c y d, el primer trabajo finaliza en el tiempo a, el segundo en tiempo a+b, el tercero en tiempo a+b+c y el cuarto en tiempo a+b+c+d, con lo que
"a" contribuye más al promedio que los otros tiempos, por lo que debe ser el trabajo más corto, "b" el siguiente, ...
Planificación por fracciones de tiempo: RR (Round-Robin)
En los entornos interactivos (como los sistemas de tiempo compartido) el objetivo principal es dar buenos tiempos de respuesta y, en general, compartir equitativamente los recursos del sistema entre todos los usuarios. Por ello, sólo las planificaciones apropiativas se pueden considerar en tales entornos y una de las más populares es la división en el tiempo en fracciones o Round Robin.
Básicamente, el tiempo de CPU se divide en fracciones o cuantums que se asignan a los procesos. Ningún proceso puede ejecutarse durante más de una fracción de tiempo habiendo procesos esperando.
Puede ocurrir que:
- Un proceso necesite más de un cuantum: El proceso pasará a la cola de procesos preparados.
- Un proceso ceda el control de la CPU (por ejemplo, operación de E/S): Se planifica otro proceso para que se ejecute.
Cada proceso recibirá 1/N (siendo N el número de procesos preparados) del tiempo de la CPU.
Los procesos cortos tendrán buenos tiempos de respuesta (ya que se pueden ejecutar en un único quantum de tiempo).
¿Qué longitud debe tener el cuantum?
Supongamos que la conmutación de un proceso a otro toma 5 ms (ocupado en salvar y cargar registros, mapas de memoria,...).
Supongamos que tcuantum = 20 ms.
Por tanto, cada proceso tarda en total 25 ms (20 ms por el proceso y 5 ms por la conmutación de la CPU). Esto significa que el 20% del tiempo de CPU lo gasta el S.O. Para mejorar la eficacia, podemos aumentar el tamaño del cuantum a 500 ms, con lo que el S.O. gasta el 1%.
Problema: Si 10 usuarios pulsan <return> al mismo tiempo, entonces habrá 10 procesos en la lista de procesos ejecutables. Inmediatamente, uno de los procesos comenzará, el segundo tendrá que esperar aproximadamente ½ sg, ... y el último tendrá que esperar 5 sg antes de tener una oportunidad, siempre y cuando todos los procesos agoten su cuantum. Es decir, el tiempo de respuesta de un comando corto es grande.
Conclusión:
- Cuantum pequeño: Se conmutan muchos procesos y, por tanto, menos eficiencia de CPU.
- Cuantum grande: Respuesta pobre a demandas de usuarios interactivos.
Solución de compromiso: t cuantum = unos 100 ms.
NOTA: Se supone que todos los procesos son de la misma importancia
Planificación por colas de niveles múltiples: MLQ (Multi Level Queues)
La idea de esta planificación es clasificar la carga de trabajo de acuerdo con sus características y mantener colas separadas de procesos atendidos por distintos planificadores.
Un ejemplo de división de la carga de trabajo podría ser: procesos del sistema, programas interactivos y trabajos por lotes.
Un proceso se adscribe a una cola específica en virtud de sus atributos, que pueden ser suministrados por el usuario o por el sistema.
La planificación que se puede usar entre las colas son por prioridad absoluta o de división del tiempo con alguna variante que refleje la prioridad relativa de los procesos colocados en las colas específicas.
En el caso de la planificación por prioridad absoluta, a los procesos procedentes de la cola que tiene la prioridad más alta se les da servicio hasta que la cola se quede vacía.
Una posible planificación para las colas de procesos individuales es: para colas de procesos interactivos usar planificación por fracción de tiempo y para colas de procesos por lotes (batch) una planificación FCFS.
Planificación por colas de niveles múltiples con realimentación: MLFQ (Multi Level Feedback Queues)
Es una variante de la planificación MLQ. En lugar de hacer que se asignen clases fijas de procesos a colas específicas, la idea es hacer depender el paso de un proceso por el sistema según el tiempo de ejecución. Así, por ejemplo, cada proceso puede comenzar en la cola de nivel superior. Si el proceso se completa en una fracción de tiempo dada, podrá salir del sistema. Los procesos que necesiten más de una fracción de tiempo para completarse, pasarán a una cola de procesos con prioridad inferior.
La idea es dar tratamiento preferente a los procesos cortos y hacer que los que consumen recursos o los procesos largos se "hundan" lentamente en colas de nivel inferior para mantener elevada la utilización de la CPU.
Una posible variante de la organización sería:
Cola más alta Se asigna 1 quantum de tiempo
... Se asignan 2 quantums de tiempo
... Se asignan 4 quantums de tiempo
... ...
Este algoritmo de planificación es válido con vistas a los procesos que se van incorporando.
Planificación primero con el tiempo de ejecución más corto: SRTF (Shortest Run-Time First)
Es una versión más dinámica y apropiativa que el SJF. Como el SJF, este algoritmo requiere estimación del tiempo de procesamiento requerido para cada proceso. Sin embargo, estas estimaciones sirven para determinar sólo las prioridades iniciales. Cada vez que un proceso necesita parar o es interrumpido, el tiempo de procesamiento transcurrido hasta ese instante es restado del estimado. Cuando el proceso vuelve a estar preparado otra vez, adquiere una prioridad más alta, reflejando la realidad de que le queda menos trabajo.
Planificación de procesos en Unix de SUN
El sistema Unix de SUN realiza la planificación de procesos asignando prioridades base (la más alta es la -20 y la más baja la +20) y efectuando ajustes de prioridad. Estos ajustes se calculan en respuesta a cambios en las condiciones del sistema. Los ajustes se suman a las prioridades base para calcular las prioridades actuales. El proceso con la prioridad actual mayor se despacha primero.
El ajuste de prioridades favorece en gran medida a los procesos que recientemente han utilizado poco tiempo de CPU.
5.5 Operaciones remotas sobre procesos
La gestión de procesos en un sistema operativo centralizado se ocupa de los mecanismos y políticas para compartir o repartir un procesador entre diversos procesos de usuario. El objetivo de la gestión de procesos en los sistemas operativos distribuidos es compartir todos los recursos de proceso (distribuidos por toda la red) entre todos los procesos de usuario de toda la red del sistema distribuido.
Para conseguir esto, es necesario proporcionar mecanismos y políticas para realizar operaciones con los procesos (crear, nombrar, borrar, ejecutar,.), tanto locales como remotos, para gestionarlos, comunicarlos y sincronizarlos.
Estos mecanismos van a tener que ampliar los ya existentes en los sistemas centralizados, para poder tratar con la distribución de recursos y la distribución de la información del estado de los recursos por toda la red.
Para mejorar el tiempo de respuesta de los procesos, se va a necesitar la posibilidad de repartir la carga de trabajo de una estación entre otras que estén más descargadas, por lo que se deberá proporcionar la posibilidad de ejecución remota de procesos y de migración de procesos entre estaciones.
5.6 Mecanismos para la migración de procesos
La migración de procesos es la transferencia de una parte suficiente del estado de un proceso desde una máquina a otra para que el proceso se pueda ejecutar en la máquina de destino. El interés surgió de la investigación sobre las formas de equilibrar la carga entre varios sistemas en red.
Anteriormente algunas publicaciones sobre la distribución de la carga se basaban en implementaciones reales de migración de procesos, lo que incluía la capacidad de expulsar un proceso de una máquina y reactivarlo en otra mas tarde. Se demostró que era posible la migración preferente de procesos, con una complejidad y coste mayores que los conocidos.
Debemos considerar una serie de cuestiones a la hora de diseñar un servicio de migración de procesos.
INICIO DE LA MIGRACIÓN: Dependerá del objetivo del servicio de migración.
- Si el objetivo es equilibrar la carga, algún módulo supervisor de la carga del sistema operativo será el responsable de decidir cuando se realizara la migración y de indicar a un proceso que va a migrar. Para determinar dónde va a migrarse, el módulo tiene que estar en comunicación con módulos similares de otros sistemas y así poder supervisar la composición de la carga de otros sistemas. La función de migración completa, como la existencia de varios sistemas, es transparente al proceso.
- Si el objetivo es llegar a unos recursos determinados, el proceso puede emigrar por sí mismo cuando surja la necesidad. En este caso, el proceso debe ser consciente de la existencia de un sistema distribuido.
¿QUE MIGRA?
Cuando un proceso migra, es necesario destruirlo del sistema de origen y crearlo en el sistema de destino. Esto es un movimiento de procesos y no una duplicación. Es responsabilidad del S.O. mover el bloque de control de proceso, y actualizar cualquier enlace entre éste y otros procesos, como los de paso de mensajes y señales.
La transferencia del proceso de una máquina a otra es invisible al proceso que migra y a los que se comunican con él.
Se tiene en cuenta las siguientes estrategias:
- TRANSFERENCIA (COMPLETA): Consiste en transferir todo el espacio de direcciones en el momento de la migración. Si el espacio de direcciones es muy grande y si es probable que el proceso no necesite la mayor parte de él, éste procedimiento puede ser costoso sin necesidad.
El coste inicial de la migración puede ser del orden de minutos. Es apropiado usar ésta solución en una implementación que ofrezca la capacidad de retroceso si todo el espacio de direcciones está localizado.
Esta estrategia libera al origen de la necesidad de tener todas las páginas del proceso que migran en la memoria principal, liberando un bloque de memoria que puede ser usado por otro proceso.
Si el proceso no utiliza la mayoría de su espacio de direcciones mientras está en la máquina de destino, tiene más sentido la segunda estrategia. Por otra parte, si accede a una gran parte del espacio de direcciones mientras está en la máquina de destino, puede ser menos eficaz la transferencia por partes del espacio de direcciones que trasladar, todo el espacio de direcciones en el momento de la migración, usando una de las dos primeras estrategias.
En muchos casos, puede que no se conozca si hará falta gran parte del espacio de direcciones no residentes. Si los procesos se estructuran en hilos y si la unidad básica de la migración es el hilo en lugar del proceso, una estrategia basada en la paginación remota puede ser la mejor. Esta estrategia es de obligado cumplimiento ya que los hilos restantes del proceso no se llevan consigo, también necesitan acceder al espacio de direcciones del proceso.
En el traslado de los archivos abiertos, si el archivo esta inicialmente en el mismo sistema que el proceso que va a migrar y si el archivo está bloqueado para acceso exclusivo de los procesos, tiene sentido transferir el archivo junto con el proceso. El peligro reside en que el proceso puede migrar sólo temporalmente y no necesitar al archivo hasta su vuelta. Puede tener sentido transferir el archivo sólo después de que el proceso migrado haga una solicitud de acceso. Si un archivo está compartido por varios procesos distribuidos, se debe mantener el acceso distribuido al archivo sin mover el archivo.
Si un proceso tiene un archivo abierto para escritura, crea un hijo y el proceso hijo migra: el archivo estaría entonces abierto para escritura en dos máquinas diferentes. El algoritmo de consistencia de cache Sprite dispone que el archivo no se mantenga en la cache de ninguna de las máquinas en las que están ejecutándose ambos procesos.
La migración es una actividad dinámica en la que intervienen una serie de pasos para trasladar la imagen de un proceso. Cuando la migración la inicia otro proceso, en lugar de ser auto migración un posible enfoque consiste en copiar la imagen del proceso y todo su espacio de direcciones a un archivo, destruir el proceso, copiar el archivo a la otra máquina mediante un servicio de transferencia de archivo y volver a crear el proceso a partir del archivo de la máquina de destino.
