lunes, 27 de octubre de 2008

Unidad 2 Administración de procesos y del procesador

Bienvenidos.
Este blog ha sido creado con la funcion de recopilar informacion sobre la segunda unidad de la asignatura sistemas operativos de la carrera ing. en sistemas de computo perteneciente al instituto tecnologico de villahermosa.
A lo largo de esta unidad abarcaremos conceptos importantes en todo sistemas, hablando asi de sus principales actores que son los procesos y el cpu; como se comunican entre ellos, que son y cuales problemas pueden ocurrir es el tema abordar, pero por supuesto para evitar estos problemas existen ya varias tecnicas administrativas y/o algoritmos que nos ayudaran a prevenir, detectar y recuperarnos de cualquier falla.
Dentro de las tareas administrativas veremos la planeación, pero claro orientada al cpu y a los procesos, asi como tecnicas que nos ayudan a evitar bloqueos, por ultimo involucramos al planificador mostrando una breve descripcion de los algoritmos mas usuales.

2.1 Concepto de Proceso

Según la investigación de Tanenbaum y Woodhull (1997) puedo deducir que un proceso no es más que un conjunto de threads que ejecutan el mismo código, junto con las zonas de memoria asociadas a ellos y los ficheros que tienen abiertos.

Tanenbaum y Woodhull (1997) mencionan que un programa consta, al menos, de un proceso, y un proceso, al menos, de un thread. Cuando un programa tiene varios procesos, lo normal es que cada uno ejecute un código distinto, los cuales se encuentran en ficheros ejecutables separados. Dos procesos solo pueden compartir una zona de memoria si esta es definida expresamente como tal. Así mismo, es en este caso cuando los sistemas de sincronización a la hora de compartir memoria (de los que hablaremos más adelante) se vuelven especialmente necesarios e importantes.

2.2 Estados y Transiciones de Procesos

En 1997 Tanenbaum y Woodhull describen los estados de un proceso como un ciclo de vida. Durante su vida, un proceso puede pasar por una serie de estados discretos, algunos de ellos son:
  • En ejecución: El proceso ocupa la CPU actualmente, es decir, se está ejecutando.
  • Listo o preparado: El proceso dispone de todos los recursos para su ejecución, sólo le falta la CPU.
  • Bloqueado: Al proceso le falta algún recurso para poder seguir ejecutándose, además de la CPU. Por recurso se pueden entender un dispositivo, un dato, etc. El proceso necesita que ocurra algún evento que le permita poder proseguir su ejecución.

Según Tanenbaum y Woodhull (1997) hay otros estados de los procesos, pero en la presente exposición se tratarán estos tres. Por sencillez, se considera un sistema con una sola CPU, aunque no es difícil la extensión a múltiples procesadores. Solamente puede haber un proceso en ejecución a la vez, pero pueden existir varios listos y varios pueden estar bloqueados. Así pues, se forman una lista de procesos listos y otra de procesos bloqueados. La lista de procesos listos se ordena por prioridad, de manera que el siguiente proceso que reciba la CPU será el primero de la lista. La lista de procesos bloqueados normalmente no está ordenada; los procesos no se desbloquean (es decir, no pasan a ser procesos listos) en orden de prioridad, sino que lo hacen en el orden de ocurrencia de los eventos que están esperando. Como se verá más adelante, hay situaciones en las cuales varios procesos pueden bloquearse esperando la ocurrencia del mismo evento; en tales casos es común asignar prioridades a los procesos que esperan.

2.3 Procesos Ligeros Hilos o hebras

Basándonos en la investigación de Tanenbaum y Woodhull (1997) en la mayoría de los sistemas operativos, hay dos características que son, de hecho, la esencia de un proceso. Sin embargo, son independientes, y pueden ser tratadas como tales por el sistema operativo. Esta distinción ha conducido en los sistemas operativos actuales a desarrollar la construcción conocida como thread, cuyas traducciones más frecuentes son hilo, hebra y proceso ligero. Si se tiene esta división de características, la unidad de asignación 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 más hilos de control cada uno con:
  • Un estado de ejecución (en ejecución, listo, bloqueado).
  • Un contexto de procesador, que se salva cuando no esté ejecutándose.
  • Una pila de ejecución.
  • Algún almacenamiento estático para variables locales.
  • Acceso a la memoria y a los recursos de ese trabajo que comparte con los otros hilos.

Los autores Tanenbaum y Woodhull (1997) mencionan que 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 ejecución se mantiene una única copia en memoria del código, y no varias.

2.4 Concurrencia y Secuenciabilidad

Según Tanenbaum y Woodhull (1997) La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, comparación y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos y es fundamental para que existan diseños como Multiprogramación, Multiproceso y Proceso distribuido.

Tanenbaum y Woodhull (1997) indican que cuando dos o más 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 más procesos sean concurrentes, es necesario que tengan alguna relaciones entre ellos como puede ser la cooperación para un determinado trabajo o el uso de información y recursos compartidos, por ejemplo: en un sistema de un procesador , la multiprogramación es una condición necesaria pero no suficiente para que exista concurrencia, ya que los procesos pueden ejecutarse de forma totalmente independiente. Por otro lado en un sistema de varios procesos se puede presentar la concurrencia siempre y cuando las actividades necesiten actuar entre ellos sea para utilizar información como para cualquier otra cosa.

2.4.1 Exclusión Mutua Secciones Criticas

Según Tanenbaum y Woodhull (1997) La exclusión mutua la podríamos definir como una operación de control que permite la coordinación de procesos concurrentes, y que tiene la capacidad de prohibir a los demás procesos realizar una acción cuando un proceso haya obtenido el permiso.

Los autores Tanenbaum y Woodhull (1997) mencionan que el control de la competencia involucra al sistema operativo inevitablemente, porque es el sistema operativo el que asigna los recursos. Además, los procesos deben ser capaces por sí mismos de expresar de algún modo los requisitos de exclusión mutua, como puede ser bloqueando los recursos antes de usarlos.

Cabe mencionar que la exclusión mutua puede presentarse en los mismos procesos, en el hardware o como soporte en el sistema operativo.

2.4.2 Sincronización Procesos en SO

Según la investigación de Tanenbaum y Woodhull (1997) la sincronización es la transmisión y recepción de señales que tiene por objeto llevar a cabo el trabajo de un grupo de procesos cooperativos. Es la coordinación y cooperación de un conjunto de procesos para asegurar la comparación de recursos de cómputo. La sincronización entre procesos es necesaria para prevenir y/o corregir errores de sincronización debidos al acceso concurrente a recursos compartidos. La sincronización permite intercambiar señales de tiempo (arranque/parada entre procesos cooperantes para garantizar las relaciones específicas de precedencia impuestas por el problema que se resuelve. Sin una sincronización adecuada entre procesos, la actualización de variables compartidas puede inducir a errores de tiempo relacionados con la concurrencia que son con frecuencia difíciles de depurar.

Tanenbaum y Woodhull (1997) recalcan que para que los procesos puedan sincronizarse es necesario disponer de servicios que permitan bloquear o suspender bajo determinadas circunstancias la ejecución de un proceso. Los principales mecanismos de sincronización que ofrecen los sistemas operativos son:
  • Señales.
  • Tuberías.
  • Semáforos.
  • Mutex y variables condicionales.
  • Paso de mensajes.
  • Tuberías.

Tanenbaum y Woodhull (1997) plantean que una tubería es un mecanismo de comunicación y sincronización. Conceptualmente, cada proceso ve la tubería como un conducto con dos extremos, uno de los cuales se utiliza para escribir o insertar datos y el otro para extraer o leer datos de la tubería.

2.4.2.1 Mecanismo de Semáforos

En 1965, E.W. Dijkstra sugirió el uso de una variable entera para contar el número de despertares almacenados para su uso posterior. En su propuesta se presentó un nuevo tipo de variable, llamada Semáforo. Un semáforo puede tener el valor 0, lo que indica que no existen despertares almacenados; o bien algún valor positivo si están pendientes uno o más despertares.
Dijkstra, propuso dos operaciones, DOWN y UP (generalizaciones de SLEEP y WAKEUP, respectivamente). La operación Down verifica si el valor de un semáforo es mayor que 0. En este caso, decrementa el valor (es decir, utiliza un despertar almacenado) y continúa. Si el valor es cero, el proceso se va a dormir. La verificación y modificación del valor, así como la posibilidad de irse a dormir se realiza en conjunto, como una sola e indivisible acción atómica. Se garantiza que al iniciar una operación con un semáforo, ningún otro proceso puede tener acceso a semáforo hasta que la operación termine o se bloquee. Esta atomicidad es absolutamente esencial para resolver los problemas de sincronización y evitar condiciones de competencia.

2.4.2.2 Mecanismo de Monitores

Según Olivares Rojas (2004) Es un proceso que se encarga de verificar el funcionamiento de algún recurso garantizando la exclusión mutua (mutex).
  • En un monitor los procesos se bloquean y desbloquean.
  • Pueden existir diversas implementaciones no estandarizadas de un monitor.
  • En Java los monitores están implementados de manera nativa con el modificador de los métodos syncronized.
  • El monitor es el mecanismo que nos permite controlar el acceso a una región crítica, en este caso un método. También se puede utilizar semáforos como objetos mutex disponibles en el paquete java.util.concurrent.

2.4.3 Interbloqueo DeadLock

Según Tanenbaum y Woodhull (1997) el interbloqueo puede definirse formalmente como sigue: Un conjunto de procesos está en interbloqueo si cada proceso del conjunto está esperando un evento que sólo otro proceso del conjunto puede causar. Puesto que todos los procesos están esperando, ninguno de ellos puede causar ninguno de los eventos que podrían despertar a cualquiera de los demás miembros del conjunto, y todos los procesos continúan esperando indefinidamente.

2.4.3.1 Prevencion Interbloqueo DeadLock

Según Tanenbaum y Woodhull (1997) la estrategia de prevención del interbloqueo consiste, a grandes rasgos, en diseñar un sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo. Los métodos para prevenir el interbloqueo son de dos tipos. Los métodos indirectos consisten en impedir la aparición de alguna de las tres condiciones necesarias. Los métodos directos consisten en evitar la aparición del círculo vicioso de espera.

Tanenbaum y Woodhull (1997) exponen que los bloqueos mutuos pueden ser evitados si se sabe cierta información sobre los procesos antes de la asignación de recursos. Para cada petición de recursos, el sistema controla si satisfaciendo el pedido entra en un estado inseguro, donde puede producirse un bloqueo mutuo. De esta forma, el sistema satisface los pedidos de recursos solamente si se asegura que quedará en un estado seguro. Para que el sistema sea capaz de decidir si el siguiente estado será seguro o inseguro, debe saber por adelantado y en cualquier momento el número y tipo de todos los recursos en existencia, disponibles y requeridos.

2.4.3.2 Deteccion Interbloqueo DeadLock

Según William Stallings (1999) las estrategias de prevención del interbloqueo son muy conservadoras; solucionan el problema del interbloqueo limitando el acceso a los recursos e imponiendo restricciones a los procesos. En el lado opuesto, las estrategias de detección del interbloqueo no limitan el acceso a los recursos ni restringen las acciones de los procesos. Con detección del interbloqueo, se concederán los recursos que los procesos necesiten siempre que sea posible. Periódicamente, el sistema operativo ejecuta un algoritmo que permite detectar la condición de círculo vicioso de espera. Puede emplearse cualquier algoritmo de detección de ciclos en grafos dirigidos.

Tanenbaum y Woodhull (1997) exponen que el control del interbloqueo puede llevarse a cabo tan frecuentemente como las solicitudes de recursos o con una frecuencia menor, dependiendo de la probabilidad de que se produzca el interbloqueo. La comprobación en cada solicitud de recurso tiene dos ventajas: Conduce a una pronta detección y el algoritmo es relativamente simple, puesto que está basado en cambios increméntales del estado del sistema. Por otro lado, tal frecuencia de comprobaciones consume un tiempo de procesador considerable.
Una vez detectado el interbloqueo, hace falta alguna estrategia de recuperación.

2.4.3.3 Recuperacion Interbloqueo DeadLock

Según William Stallings (1999) Las técnicas siguientes son posibles enfoques, enumeradas en orden creciente de sofisticación:

1.Abandonar todos los procesos bloqueados. Esta es, se crea o no, una de las soluciones más comunes, si no la más común, de las adoptadas en un sistema operativo.
2.Retroceder cada proceso interbloqueado hasta algún punto de control definido previamente y volver a ejecutar todos los procesos. Es necesario que haya disponibles unos mecanismos de retroceso y reinicio en el sistema. El riesgo de esta solución radica en que puede repetirse el interbloqueo original. Sin embargo, el no determinismo del procesamiento concurrente asegura, en general, que esto no va a pasar.

3.Abandonar sucesivamente los procesos bloqueados hasta que deje de haber interbloqueo. El orden en el que se seleccionan los procesos a abandonar seguirá un criterio de mínimo coste. Después de abandonar cada proceso, se debe ejecutar de nuevo el algoritmo de detección para ver si todavía existe interbloqueo.

4. Apropiarse de recursos sucesivamente hasta que deje de haber interbloqueo. Como en el punto 3, se debe emplear una selección basada en coste y hay que ejecutar de nuevo el algoritmo de detección después de cada apropiación. Un proceso que pierde un recurso por apropiación debe retroceder hasta un momento anterior a la adquisición de ese recurso.

2.5 Niveles Objetivos Criterios Planificación

De acuerdo con Tanenbaum y Woodhull (1997) se consideran tres niveles importantes de planificación, los que se detallan a continuación:
  • Planificación de alto nivel: Se encarga de llevar procesos de disco a memoria y viceversa. Seleccionando los trabajos que deben admitirse en el sistema.
  • Planificación de nivel intermedio: En algunos casos, en especial cuando el sistema está sobrecargado, el planificador de nivel medio encuentra ventajoso retirar trabajos activos de la memoria para reducir el grado de multiprogramación, y por lo tanto, permitir que los trabajos se completen mas aprisa.
  • Planificación de bajo nivel: Se encarga de pasar de un proceso a otro en memoria principal. Determinando a cuál proceso listo se le asignará el CPU cuando éste se encuentra disponible. O Determina a qué proceso listo se le asigna la cpu cuando esta queda disponible y asigna la cpu al mismo, es decir que “despacha” la cpu al proceso.

Los objetivos de la planificación del procesador:

  • Ser justa.
  • Maximizar la capacidad de ejecución.
  • Maximizar el número de usuarios interactivos.
  • Ser predecible.
  • Equilibrar el uso de recursos.
  • Equilibrar respuesta y utilización.
  • Evitar la postergación indefinida.
  • Asegurar la prioridad.
  • Dar preferencia a los procesos que mantienen recursos claves.
  • Dar mejor tratamiento a los procesos que muestren un “comportamiento deseable”.
  • Degradarse suavemente con cargas pesadas.

Criterios de la planeación del procesador

  • Equidad
  • Eficacia
  • Tiempo de respuesta
  • Tiempo de regreso
  • Rendimiento

2.6 Técnicas Administración del Planificador

Según Tanenbaum y Woodhull (1997) se denomina planificador al software del sistema operativo encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya tomar una decisión, el planificador debe decidir cuál de los procesos que compiten por la posesión de un determinado recursos lo recibirá.

Tanenbaum y Woodhull (1997) mencionan que los algoritmos (técnicas) tienen distintas propiedades según los criterios en los que se basen para su construcción, 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 elección de un algoritmo se debe considerar las propiedades de estos frente al criterio de diseño elegido.

2.6.1 Fifo

Según la investigación Tanenbaum y Woodhull (1997) se concluye lo siguiente:FIFO: First In First Out.

Tanenbaum y Woodhull (1997) lo definen como un Mecanismo de scheduling en el cual los procesos se ordenan en una fila, en la cual se ejecutan cada uno de los procesos hasta su finalizacion secuencialmente. Es tremendamente ineficiente. Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente. Para implementar el algoritmo sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

2.6.2 Sjf

Según Tanenbaum y Woodhull (1997) vemos que al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas.

Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos. La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio.

2.6.3 Rr

Según Tanenbaum y Woodhull (1997) vemos que cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado cuantum o cuánto. Si el proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU. El round robin (Rr) es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos.

2.6.4 QuevesMultilevel

Según Tanenbaum y Woodhull (1997) es un algoritmo de planificación multinivel particiona la cola de listos en colas separadas. Se asignan en forma permanente los trabajos a una cola, generalmente, basándose en alguna propiedad del mismo (requerimientos de memoria, tipo de trabajo), teniendo cada cola su propio algoritmo. Por ejemplo, la cola interactiva podría planificarse usando RR y la batch FIFO. Ningún trabajo en una cola de baja prioridad puede ejecutarse si las colas con mayor prioridad no están vacías. Si algún trabajo entra en una cola de mayor prioridad, el trabajo de otras colas es interrumpido.

2.6.5 MultiLevel Feedback Queves

Según Tanenbaum y Woodhull (1997) En colas multinivel realimentadas los trabajos pueden moverse dentro de distintas colas. La idea es separar procesos con distintos tipos de interrupciones de la CPU. Si un trabajo consume mucho tiempo de CPU, será movido a una cola con menor prioridad. En forma similar, si un proceso espera demasiado tiempo en una cola de baja prioridad, lo moveremos a una cola de mayor prioridad.

Tanenbaum y Woodhull (1997) concluyen que en general un planificador de este tipo está definido por los siguientes parámetros:

1. El número de colas.
2. El tipo de algoritmo de planificación de cada cola.
3. Un método de determinación de cuando mover un trabajo a una cola de mayor prioridad.
4. Un método de determinación de cuando mover un trabajo a una cola de menor prioridad.
5. Un método de determinación de a qué cola se enviará un trabajo cuando necesita servicio.