Sistemas Operativos - Unidad II

Sistemas Operativos
Unidad II - Administracin de Procesos y del procesador.
Competencia especfica a desarrollar: Aplicar las tcnicas de administracin de procesos.

2.1 - Concepto de proceso.

Proceso: Conjunto de actividades o eventos (coordinados u organizados) que se realizan o suceden (alternativa o simultneamente) bajo ciertas circunstancias con un fin determinado. En informtica, un proceso es un conjunto de procedimientos o funciones que tienen uno o ms objetivos. Los programas y aplicaciones informticos pueden ejecutar ms de un proceso simultneamente, ayudados o no por un procesador con mltiples ncleos. Esta forma de trabajar se conoce como multi-threading (mltiples hilos).Un ejemplo de esto puede ser en un juego que tiene un proceso para la msica de fondo, otro para el dibujado de sus personajes y escenarios y un tercero para la inteligencia artificial. En sistemas operativos, un proceso es un concepto que consiste en el conjunto formado por: Las instrucciones de un programa destinadas a ser ejecutadas por el procesador. Su estado de ejecucin en un momento dado, esto es, los valores de los registros de la CPU para dicho programa. Su memoria de trabajo, es decir, la memoria que ha reservado y sus contenidos. Otra informacin que permite al sistema operativo su planificacin.

Esta definicin vara ligeramente en el caso de sistemas operativos multi-hilos (multi-threading), donde un proceso consta de uno o ms hilos, la memoria de trabajo (compartida por todos los hilos) y la informacin de planificacin. Cada hilo consta de instrucciones y estado de ejecucin. Los procesos son creados y destruidos por el sistema operativo, as como tambin este se debe hacer cargo de la comunicacin entre procesos, pero lo hace a peticin de otros procesos. En los sistemas operativos multi-hilos (multi-threading) es posible crear tanto hilos como procesos. La diferencia estriba en que un proceso solamente puede crear hilos para s mismo y en que dichos hilos comparten toda la memoria reservada para el proceso y los nuevos procesos son independientes y no comparten memoria (es decir, informacin) con el proceso que los ha creado. Tipos de procesos Existen dos tipos de procesos, aquellos que se ejecutan en modo kernel y aquellos que se ejecutan en modo usuario. Los primeros son ms lentos por las llamadas al sistema que realizan, sin embargo, son ms seguros por la integridad que representan. Para los procesos de usuario, se puede decir que el sistema operativo podra no ser multiproceso, ya que se vale de libreras para hacer un multiplexado y dar la apariencia de trabajar como multiproceso. Otra clasificacin podra ser: Procesos en primer plano (Foreground)y Procesos en segundo plano (Background). Los primeros interactan con el usuario, es decir, el usuario proporciona los datos que el proceso utilizar. Los segundos, son creados para tareas bien definidas y no necesitan la intervencin del usuario. Por ejemplo, se puede tener un proceso en segundo plano para revisar la temperatura el disco duro constantemente, stos tambin son conocidos como demonios (Daemon)

2.2 - Estados y transiciones de los procesos.

Los estados de un proceso obedecen a su participacin y disponibilidad dentro del sistema operativo y surgen de la necesidad de controlar la ejecucin de cada proceso. Los procesadores slo pueden ejecutar un slo proceso a la vez, turnndolos para el uso de ste. Existen procesos apropiativos que bsicamente ocupan todo el tiempo del procesador hasta que ellos deciden dejarlo. Los procesos no apropiativos son aquellos que ocupan por un periodo de tiempo el procesador hasta que una interrupcin o seal llega al procesador para hacer el cambio de proceso, a esto se le conoce como cambio de contexto. Los posibles estados que puede tener un proceso son: 1. En ejecucin.- Es un proceso que est haciendo uso del procesador. 2. Bloqueado.- No puede ejecutarse hasta que un evento externo sea llevado a cabo. 3. Listo.- Ha dejado disponible al procesador para que otro proceso pueda ocuparlo. Las posibles transiciones de proceso son cuatro: La primera transicin (1) se realiza cuando el sistema operativo determina que el proceso no puede continuar, por lo que se puede hacer una llamada al sistema "pause" para pasar al estado bloqueado.

Las transiciones (2) y (3) son llevadas a cabo por el planificador de procesos, ya que el proceso no tiene conocimiento de ste. La transicin (2) se da cuando el planificador de procesos decide que el proceso ya estuvo el tiempo suficiente en ejecucin y debe dar paso a la ejecucin de otros procesos (adquieran tiempo del procesador). La transicin 3 se realiza cuando todos los procesos han ocupado tiempo del procesador y debe retomarse el primer proceso. La transicin (4) ocurre cuando se produce un evento externo por el que un proceso estaba en espera, por ejemplo, introducir datos desde la terminal. Si no hay otro proceso en ejecucin en ese instante, la transicin 3 se activa y el proceso comienza a ejecutarse; tambin podra pasar al estado de "listo" y esperar un momento para iniciar la ejecucin.

1. El proceso se bloquea en espera de datos 2. El planificador elige otro proceso 3. El planificador elige a este proceso 4. Datos disponibles

Figura 2.1 Transiciones de un proceso

Modelo de cinco estados Para este modelo, se agregan dos nuevos estados, un estado Nuevo y otro Terminado, por lo que los cinco estados de este modelo son los siguientes: 1. Ejecucin: el proceso est actualmente en ejecucin. 2. Listo: el proceso est listo para ser ejecutado, slo est esperando que el planificador as lo disponga. 3. Bloqueado: el proceso no puede ejecutar hasta que no se produzca cierto suceso, como una operacin de Entrada/Salida. 4. Nuevo: El proceso recin fue creado y todava no fue admitido por el sistema operativo. En general los procesos que se encuentran en este estado todava no fueron cargados en la memoria principal. 5. Terminado: El proceso fue expulsado del grupo de procesos ejecutables, ya sea porque termin o por algn fallo, como un error de proteccin, aritmtico, etc. Los nuevos estados Nuevo y Terminado son tiles para la gestin de procesos. Los estados Bloqueado y Listo tienen una cola de espera. Cuando un nuevo proceso es admitido por el sistema operativo, se sita en la cola de listos. Los procesos suspendidos son mantenidos en una cola de bloqueados. Cuando se da un suceso se pasan a la cola de listos los procesos que esperaban por ese suceso.

Figura 2.2 Transiciones en el modelo de cinco estados

2.3 - Procesos ligeros (Hilos o hebras).

El concepto de proceso engloba dos conceptos separados y potencialmente independientes: uno relativo a la propiedad de recursos y otro que hace referencia a la ejecucin. Unidad que posee recursos: A un proceso se le asigna un espacio de memoria y, de tanto en tanto, se le puede asignar otros recursos como dispositivos de E/S o ficheros. Unidad a la que se le asigna el procesador: Un proceso es un flujo de ejecucin (una traza) a travs de uno o ms programas. Esta ejecucin se entremezcla con la de otros procesos. De tal forma, que un proceso tiene un estado (en ejecucin, listo, etc) y una prioridad de expedicin u origen. La unidad planificada y expedida por el sistema operativo es el proceso. En la mayora de los sistemas operativos, estas dos caractersticas son, de hecho, la esencia de un proceso. Sin embargo, son independientes, y pueden ser tratadas como tales por el sistema operativo. Esta distincin ha conducido en los sistemas operativos actuales a desarrollar la construccin conocida como thread, cuyas traducciones ms frecuentes son hilo, hebra y proceso ligero. Si se tiene esta divisin de caractersticas, la unidad de asignacin de la CPU se conoce como hilo, mientras que a la unidad que posee recursos se le llama proceso. Dentro de un proceso puede haber uno o ms hilos de control cada uno con: Un estado de ejecucin (en ejecucin, listo, bloqueado).

Un contexto de procesador, que se salva cuando no est ejecutndose. Una pila de ejecucin. Algn almacenamiento esttico para variables locales. Acceso a la memoria y a los recursos de ese trabajo que comparte con los otros hilos.

Los beneficios clave de los hilos se derivan de las implicaciones del rendimiento: se tarda menos tiempo en crear un nuevo hilo de un proceso que ya existe, en terminarlo, y en hacer un cambio de contexto entre hilos de un mismo proceso. Al someter a un mismo proceso a varios flujos de ejecucin se mantiene una nica copia en memoria del cdigo, y no varias. Un ejemplo de aplicacin que podra hacer uso de los hilos es un servidor de archivos de una red de rea local. Cada vez que llega una solicitud de una operacin sobre un archivo, se puede generar un nuevo hilo para su gestin. El servidor gestiona multitud de solicitudes, por tanto, se pueden crear y destruir muchos hilos en poco tiempo para dar servicio a estas peticiones. Si el servidor es un multiprocesador, se pueden ejecutar varios hilos de un mismo proceso simultneamente y en diferentes procesadores. Un proceso ligero (thread o hebra) es un programa en ejecucin que comparte la imagen de la memoria y otras informaciones con otros procesos ligeros.

Figura 2.3 Procesos ligeros

2.4 - Concurrencia y secuenciabilidad.

La concurrencia comprende un gran nmero de cuestiones de diseo, incluyendo la comunicacin entre procesos, comparticin y competencia por los recursos, sincronizacin de la ejecucin de varios procesos y asignacin del tiempo de procesador a los procesos y es fundamental para que existan diseos como Multiprogramacin, Multiproceso y Proceso distribuido Los procesos son concurrentes si existen simultneamente. Cuando dos o ms procesos llegan al mismo tiempo a ejecutarse, se dice que se ha presentado una concurrencia de procesos. Es importante mencionar que para que dos o ms procesos sean concurrentes, es necesario que tengan alguna relacin entre ellos La concurrencia puede presentarse en tres contextos diferentes: Varias aplicaciones.- La multiprogramacin se cre para permitir que el tiempo de procesador de la mquina fuese compartido dinmicamente entre varios trabajos o aplicaciones activas. Aplicaciones estructuradas.- Como ampliacin de los principios del diseo modular y la programacin estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes. Estructura del sistema operativo.- Las mismas ventajas de estructuracin son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos estn implementados como un conjunto de procesos. Multiprogramacin con un nico procesador.- El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecucin de los mismos para dar as una apariencia de ejecucin simultnea. Multiprocesador.- Es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no slo pueden intercalar su ejecucin sino tambin superponerla. Multicomputadora.- Es una maquina de memoria distribuida, que est formada por una serie de computadoras. En este tipo de arquitecturas tambin es posible la ejecucin simultnea de los procesos sobre los diferentes procesadores.

Existen tres modelos de computadora en los que se pueden ejecutar procesos concurrentes:

En general, la concurrencia ser aparente siempre que el nmero de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya ms de un proceso por procesador. La concurrencia ser real cuando haya un proceso por procesador. Aunque puede parecer que la intercalacin y la superposicin de la ejecucin de procesos presentan formas de ejecucin distintas, ambas pueden contemplase como ejemplos de procesos concurrentes Existen diversas razones que motivan la ejecucin de procesos concurrentes en un sistema: Facilita la programacin de aplicaciones al permitir que stas se estructuren como un conjunto de procesos que cooperan entre s para alcanzar un objetivo comn. Acelera los clculos. Si se quiere que una tarea se ejecute con mayor rapidez, lo que se puede hacer es dividirla en procesos, cada uno de los cuales se ejecuta en paralelo con los dems. Posibilita el uso interactivo a mltiples usuarios que trabajan de forma simultnea.

Permite un mejor aprovechamiento de los recursos, en especial del CPU, ya que pueden aprovechar las fases de entrada-salida de unos procesos para realizar las fases de procesamiento de otros.

As como existen las razones que motivan la ejecucin de procesos concurrentes, tambin existen sus contras: Inanicin e interrupcin de procesos Ocurrencia de bloqueos Que dos o ms procesos requieran el mismo recurso (No apropiativo)

Tipos de procesos concurrentes. Los procesos que ejecutan de forma concurrente en un sistema se pueden clasificar como: Proceso independiente: Es aquel que ejecuta sin requerir la ayuda o cooperacin de otros procesos. Un claro ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultnea en un sistema. Proceso cooperante: Son aquellos que estn diseados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos. En ambos tipos de procesos (independientes y cooperantes), puede producirse una serie de interacciones entre ellos y pueden ser de dos tipos: Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos fsicos o lgicos. Por ejemplo, dos procesos independientes compiten por el acceso a disco o para modificar una base de datos. Interacciones motivadas porque los procesos se comunican y sincronizan entre s para alcanzar un objetivo comn, Por ejemplo, un compilador que tiene varios procesos que trabajan conjuntamente para obtener un solo archivo de salida.

2.5 - Niveles, objetivos y criterios de planificacin.

La planificacin es el proceso por el cual el sistema operativo selecciona que proceso ejecutar. La seleccin del proceso se basa en alguno de los algoritmos de planificacin. La planificacin de la CPU, en el sentido de conmutarla entre los distintos procesos, es una de las funciones del sistema operativo. Este despacho es llevado a cabo por un pequeo programa llamado planificador a corto plazo o dispatcher (despachador). La misin del dispatcher consiste en asignar la CPU a uno de los procesos ejecutables del sistema, para ello sigue un determinado algoritmo. Los acontecimientos que pueden provocar la llamada al dispatcher dependen del sistema (son un subconjunto de las interrupciones), pero son alguno de estos: 1. El proceso en ejecucin acaba su ejecucin o no puede seguir ejecutndose (por una E/S, operacin WAIT, etc). 2. Un elemento del sistema operativo ordena el bloqueo del proceso en ejecucin 3. El proceso en ejecucin agota su cuantum o cuanto de estancia en la CPU. 4. Un proceso pasa a estado listo. Hay que destacar el hecho de que cuanto menos se llame al dispatcher menos tiempo ocupa la CPU un programa del sistema operativo, y, por tanto, se dedica ms tiempo a los procesos del usuario (un cambio de proceso lleva bastante tiempo). Se puede definir el scheduling (planificacin) como el conjunto de polticas y mecanismos construidos dentro del sistema operativo que gobiernan la forma de conseguir que los procesos a ejecutar lleguen a ejecutarse. Existen tres niveles de scheduling, estos niveles son: 1. Planificador de la CPU o a corto plazo. 2. Planificador a medio plazo. 3. Planificador a largo plazo. En la planificacin de procesos se suelen incluir varios niveles, en funcin del periodo temporal que cubren: Planificacin a largo plazo Este planificador est presente en algunos sistemas que admiten adems de procesos interactivos trabajos por lotes. Usualmente, se les asigna una prioridad baja a los trabajos por lotes, utilizndose estos para mantener ocupados a los recursos del sistema durante perodos de baja actividad de los procesos interactivos. Normalmente, los trabajos por lotes realizan tareas rutinarias como el clculo de nminas; en este tipo de tareas el programador puede estimar su gasto en recursos, indicndoselo al sistema. Esto facilita el funcionamiento del planificador a largo plazo.

El objetivo primordial del planificador a largo plazo es el de dar al planificador de la CPU una mezcla equilibrada de trabajos, tales como los limitados por la CPU (utilizan mucho la CPU) o la E/S. As, por ejemplo, cuando la utilizacin de la CPU es baja, el planificador puede admitir ms trabajos para aumentar el nmero de procesos listos y, con ello, la probabilidad de tener algn trabajo til en espera de que se le asigne la CPU. A la inversa, cuando la utilizacin de la CPU llega a ser alta, y el tiempo de respuesta comienza a reflejarlo, el planificador a largo plazo puede optar por reducir la frecuencia de admisin de trabajos. Planificacin a Medio Plazo En los sistemas de multiprogramacin y tiempo compartido varios procesos residen en la memoria principal. El tamao limitado de sta hace que el nmero de procesos que residen en ella sea finito. Puede ocurrir que todos los procesos en memoria estn bloqueados, desperdicindose as la CPU. En algunos sistemas se intercambian procesos enteros (swap) entre memoria principal y memoria secundaria (normalmente discos), con esto se aumenta el nmero de procesos, y, por tanto, la probabilidad de una mayor utilizacin de la CPU. El planificador a medio plazo es el encargado de regir las transiciones de procesos entre memoria principal y secundaria, acta intentando maximizar la utilizacin de los recursos. Por ejemplo, transfiriendo siempre a memoria secundaria procesos bloqueados, o transfiriendo a memoria principal procesos bloqueados nicamente por no tener memoria. Planificacin a corto plazo. Esta indica qu proceso ser el que se ejecutar en el procesador en el instante siguiente.

Figura 2.4 - Niveles de planificacin

Expulsin denota si un proceso acapara el procesador cuando est ejecutndose. Existen sistemas con y sin expulsin: a) Sin expulsin: un proceso conserva el uso del procesador mientras lo desee; es decir, mientras no solicite del SO un servicio que lo bloquee. Ventajas: minimiza tiempo de planificacin. Inconvenientes: un proceso podra monopolizar el uso del procesador. b) Con expulsin: el SO puede desalojar a un proceso del uso del procesador (sin que el proceso lo haya solicitado). Ventaja: control sobre el tiempo de ejecucin de cada proceso. Inconveniente: gasto de tiempo.

Objetivos y Criterios de Planificacin Los objetivos del planificador se resumen en: 1. Reparto equitativo del tiempo de procesador 2. Eficiencia en el uso del procesador 3. Menor tiempo de respuesta en uso interactivo 4. Cumplir plazos de ejecucin de los sistemas de tiempo real El principal objetivo de la planificacin a corto plazo es repartir el tiempo del procesador de forma que se optimicen algunos puntos del comportamiento del sistema. Generalmente se fija un conjunto de criterios con los que evaluar las diversas estrategias de planificacin. El criterio ms empleado establece dos clasificaciones. En primer lugar, se puede hacer una distincin entre los criterios orientados a los usuarios y los orientados al sistema. Los criterios orientados al usuario se refieren al comportamiento del sistema tal y como lo perciben los usuarios o los procesos. Uno de los parmetros es el tiempo de respuesta. El tiempo de respuesta es el periodo de tiempo transcurrido desde que se emite una solicitud hasta que la respuesta aparece en la salida. Sera conveniente disponer de una poltica de planificacin que ofrezca un buen servicio a diversos usuarios.

Los criterios orientados al sistema se centran en el uso efectivo y eficiente del procesador. Un ejemplo puede ser la productividad, es decir, el ritmo con el que los procesos terminan. La productividad es una medida muy vlida del rendimiento de un sistema y que sera deseable maximizar. Otra forma de clasificacin es considerar los criterios relativos al rendimiento del sistema y los que no lo son. Los criterios relativos al rendimiento son cuantitativos y, en general, pueden evaluarse o ser analizados fcilmente. Algunos ejemplos son el tiempo de respuesta y la productividad. Los criterios no relativos al rendimiento son, en cambio cualitativos y no pueden ser evaluados fcilmente. Un ejemplo de estos criterios es la previsibilidad. Sera conveniente que el servicio ofrecido a los usuarios tengan las mismas caractersticas en todo momento, independientemente de la existencia de otros trabajos ejecutados por el sistema.

2.6 - Tcnicas de administracin del planificador.

Se denomina planificador (scheduling) al software del sistema operativo encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya que tomar una decisin, el planificador debe decidir cul de los procesos que compiten por la posesin de un determinado recursos lo recibir. Los algoritmos (tcnicas) tienen distintas propiedades segn los criterios en los que se basen para su construccin, lo cual se refleja en qu tipo de procesos se puede ver favorecido frente a otro en la disputa del procesador. Antes de realizar la eleccin de un algoritmo se debe considerar las propiedades de estos frente al criterio de diseo elegido. Algunas de estos son: a) Eficacia: Se expresa como un porcentaje del tiempo medio de utilizacin. Aunque puede parecer lgico intentar mantener este parmetro prximo al 100%, con un valor tan elevado otros aspectos importantes de medida del comportamiento del sistema pueden verse deteriorados, como por ejemplo el tiempo medio de espera. b) Rendimiento: Es una medida del numero de procesos completados por unidad de tiempo. Por ejemplo 10 procesos por segundo. c) Tiempo de retorno o regreso: Es el intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que es completado por el sistema. d) Tiempo de espera: Es el tiempo que el proceso espera hasta que se le concede el procesador. Puede resultar una medida ms adecuada de la eficiencia del sistema, ya que se elimina de la media el tiempo que tarda en ejecutarse el mismo. e) Tiempo de respuesta a un evento: Se denomina as el intervalo de tiempo que transcurre desde que se seala un evento hasta que se ejecuta la primera instruccin de la rutina de servicio de dicho evento. Los algoritmos de planificacin son los que definen que poltica se va a seguir para que un proceso pase al estado de ejecucin. Planificacin Round-Robin En este tipo de planificacin cada proceso tiene asignado un quantum de tiempo para ejecutarse y en el caso de que no pueda terminar la ejecucin en su quantum el proceso pasa de nuevo a la cola de procesos para ser ejecutado por otro quantum luego de recorrer la cola para asegurarse que todos los procesos reciban ese quantum de procesamiento.

Planificacin por prioridad En la planificacin round-robin todos los procesos son tratados con la misma prioridad. Para el caso de este tipo de planificacin a cada proceso se le asigna una prioridad y los mismos son ejecutados.

Colas mltiples Las colas mltiples estn basadas en una pila que sirve como ndice de una lista de procesos que se tienen que ejecutar. Primero el trabajo ms corto. Este tipo de algoritmo de planificacin se usa para trabajos en batch o de procesamiento por lotes en los

cuales se puede saber cul es el tiempo de duracin de la ejecucin de cada proceso y entonces se puede seleccionar primero el trabajo ms corto. El problema que se presenta con ste algoritmo es que los grandes procesos podran sufrir de inanicin dado que cualquier proceso pequeo se "cuela" sobre uno de mayor tamao y como resultado final se podra dar el caso que el proceso grande nunca obtenga procesamiento.

Planificacin garantizada En este modelo de planificacin se tiene en cuenta la cantidad de usuarios en el sistema y se le asigna a cada uno el tiempo de ejecucin de 1/n (siendo n la cantidad total de usuarios) de esa forma el planificador tiene que llevar cuenta del tiempo de ejecucin de los procesos y balancear el tiempo que estn utilizando el procesador para cumplir con la ecuacin previa.

Algoritmos de Planificacin

1. Planificacin a la Tasa de Respuesta ms Alta (HRRN, highest-response-ratio-next) 2. Planificacin con clases de prioridades 3. Planificacin de Colas de Retroalimentacin de Mltiples Niveles ((MLQ, multiple level queue) 4. Planificacin de Mltiples colas (MQS - Multilevel Queue Schedulling) 5. Planificacin de Plazo Fijo 6. Planificacin garantizada 7. Planificacin por el Comportamiento 8. Planificacin por orden de llegada (FCFS - First Come, First Served) 9. Planificacin por Prioridad al ms Corto (SJF, Shortest Job First). 10. Planificacin por Prioridad al Tiempo Restante ms Corto (SRTF, Short Remaining Time First). 11. Planificacin por prioridades (estticas o dinmicas) 12. Planificacin por Turno Rotatorio (Round Robin) 13. Planificacin Primero-Entrar-Primero-Salir (FIFO, First In First Out)
11