Planificación de Dos Niveles

Los esquemas analizados hasta ahora suponen que todos los procesos ejecutables están en la memoria principal.
Si la memoria principal es insuficiente, ocurrirá lo siguiente [23, Tanenbaum]:

• Habrá procesos ejecutables que se mantengan en disco.
• Habrá importantes implicaciones para la planificación, tales como las siguientes:
  • El tiempo de alternancia entre procesos para traer y procesar un proceso del disco es considerablemente mayor que el tiempo para un proceso que ya está en la memoria principal.
  • Es más eficiente el intercambio de los procesos con un planificador de dos niveles.

El esquema operativo de un planificador de dos niveles es como sigue:

1. Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
2. El planificador se restringe a ellos durante cierto tiempo.
3. Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:
   1. Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
   2. Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.
4. El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
5. El planificador de nivel superior se encarga de desplazar los procesos de memoria a disco y viceversa.

Los criterios que podría utilizar el planificador de nivel superior para tomar sus decisiones son los que se indican a continuación:

• ¿Cuánto tiempo ha transcurrido desde el último intercambio del proceso?.
• ¿Cuánto tiempo de cpu ha utilizado recientemente el proceso?.
• ¿Qué tan grande es el proceso? (generalmente los procesos pequeños no causan tantos problemas en este sentido).
• ¿Qué tan alta es la prioridad del proceso?.

El planificador de nivel superior podría utilizar cualquiera de los métodos de planificación analizados.

[23] A. S. Tanenbaum. Sistemas Operativos Modernos. Prentice Hall Hispanoamericana, S.A., México, 1993. 

Tipos de Planificación

Planificación a Plazo Fijo
 

Ciertos trabajos se planifican para ser terminados en un tiempo específico o plazo fijo. Es una planificación compleja debido a los siguientes factores:

• El usuario debe suministrar anticipadamente una lista precisa de recursos necesarios para el proceso, pero generalmente no se dispone de dicha información.
• La ejecución del trabajo de plazo fijo no debe producir una grave degradación del servicio a otros usuarios.
• El sistema debe planificar cuidadosamente sus necesidades de recursos hasta el plazo fijo, lo que se puede complicar con las demandas de recursos de nuevos procesos que ingresen al sistema.
• La concurrencia de varios procesos de plazo fijo (activos a la vez) puede requerir métodos sofisticados de optimización.
• La administración intensiva de recursos puede generar una considerable sobrecarga adicional. 

Planificación Garantizada
 
Se establecen compromisos de desempeño con el proceso del usuario, por ejemplo, si existen “n” procesos en el sistema, el proceso del usuario recibirá cerca del “1 / n” de la potencia de la cpu.
El sistema debe tener un registro del tiempo de cpu que cada proceso ha tenido desde su entrada al sistema y del tiempo transcurrido desde esa entrada.
Con los datos anteriores y el registro de procesos en curso de ejecución, el sistema calcula y determina qué procesos están más alejados por defecto de la relación “1 / n” prometida y prioriza los procesos que han recibido menos cpu de la prometida.



Planificación del Primero en Entrar Primero en Salir (FIFO)

Es muy simple, los procesos se despachan de acuerdo con su tiempo de llegada a la cola de listos.
Una vez que el proceso obtiene la cpu, se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”.
Puede ocasionar que procesos largos hagan esperar a procesos cortos y que procesos no importantes hagan esperar a procesos importantes.
Es más predecible que otros esquemas.
No puede garantizar buenos tiempos de respuesta interactivos.
Suele utilizarse integrado a otros esquemas, por ejemplo, de la siguiente manera:

• Los procesos se despachan con algún esquema de prioridad.
• Los procesos con igual prioridad se despachan “FIFO”.

Planificación de Asignación en Rueda (RR: Round Robin)
 
Los procesos se despachan en “FIFO” y disponen de una cantidad limitada de tiempo de cpu, llamada “división de tiempo” o “cuanto”.
Si un proceso no termina antes de expirar su tiempo de cpu ocurren las siguientes acciones:

1. La cpu es apropiada.
2. La cpu es otorgada al siguiente proceso en espera.
3. El proceso apropiado es situado al final de la lista de listos.

Es efectiva en ambientes de tiempo compartido. La sobrecarga de la apropiación se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos.



Tamaño del Cuanto o Quantum
 
La determinación del tamaño del cuanto es decisiva para la operación efectiva de un sistema computacional [7, Deitel].
Los interrogantes son: ¿cuanto pequeño o grande?, ¿cuanto fijo o variable? y ¿cuanto igual para todos los procesos de usuarios o determinado por separado para cada uno de ellos?.
Si el cuanto se hace muy grande, cada proceso recibe todo el tiempo necesario para llegar a su terminación, por lo cual la asignación en rueda (“RR”) degenera en “FIFO”.
Si el cuanto se hace muy pequeño, la sobrecarga del intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada, puesto que la mayor parte del tiempo de cpu se invierte en el intercambio del procesador (cambio de contexto) y los procesos de usuario disponen de muy poco tiempo de cpu.
El cuanto debe ser lo suficientemente grande como para permitir que la gran mayoría de las peticiones interactivas requieran de menos tiempo que la duración del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a un proceso hasta que genera una petición de Entrada / Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la petición la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo transcurrido hasta la petición de Entrada / Salida, los procesos trabajan al máximo de velocidad, se minimiza la sobrecarga de apropiación y se maximiza la utilización de la
Entrada / Salida.
El cuanto óptimo varía de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos).




Planificación del Trabajo Más Corto Primero (SJF)
 
Es una disciplina no apropiativa y por lo tanto no recomendable en ambientes de tiempo compartido.
El proceso en espera con el menor tiempo estimado de ejecución hasta su terminación es el siguiente en ejecutarse.
Los tiempos promedio de espera son menores que con “FIFO”.
Los tiempos de espera son menos predecibles que en “FIFO”.
Favorece a los procesos cortos en detrimento de los largos.
Tiende a reducir el número de procesos en espera y el número de procesos que esperan detrás de procesos largos.
Requiere un conocimiento preciso del tiempo de ejecución de un proceso, lo que generalmente se desconoce.
Se pueden estimar los tiempos en base a series de valores anteriores.


Planificación del Tiempo Restante Más Corto (SRT)
 
Es la contraparte apropiativa del SJF.
Es útil en sistemas de tiempo compartido.
El proceso con el tiempo estimado de ejecución menor para …nalizar es el siguiente en ser ejecutado.
Un proceso en ejecución puede ser apropiado por un nuevo proceso con un tiempo estimado de ejecución menor.
Tiene mayor sobrecarga que la planificación SJF.
Debe mantener un registro del tiempo de servicio transcurrido del proceso en ejecución, lo que aumenta la sobrecarga.
Los trabajos largos tienen un promedio y una varianza de los tiempos de espera aún mayor que en SJF.
La apropiación de un proceso a punto de terminar por otro de menor duración recién llegado podría significar un mayor tiempo de cambio de contexto (administración del procesador) que el tiempo de finalización del primero.
Al diseñarse los Sistemas Operativos se debe considerar cuidadosamente la sobrecarga de los mecanismos de administración de recursos comparándola con los beneficios esperados.



Planificación el Siguiente con Relación de Respuesta Máxima (HRN)
 
Corrige algunas de las debilidades del SJF, tales como el exceso de perjuicio hacia los procesos (trabajos) largos y el exceso de favoritismo hacia los nuevos trabajos cortos.
Es una disciplina no apropiativa.
La prioridad de cada proceso está en función no sólo del tiempo de servicio del trabajo, sino que también influye la cantidad de tiempo que el trabajo ha estado esperando ser servido.
Cuando un proceso ha obtenido la cpu, corre hasta terminar.
Las prioridades, que son dinámicas, se calculan según la siguiente fórmula, donde p_r es la “prioridad”, t_e es el “tiempo de espera” y t_s es el “tiempo de servicio”:

 

Planificación por Prioridad
 
Considera factores externos al proceso [23, Tanenbaum].
Las ideas centrales son que cada proceso tiene asociada una prioridad y que el proceso ejecutable con máxima prioridad es el que tiene el permiso de ejecución.
Los procesos de alta prioridad podrían ejecutar indefinidamente, ya que el planificador del sistema puede disminuir la prioridad del proceso en ejecución en cada interrupción del reloj.
Las prioridades también pueden ser asignadas dinámicamente por el sistema para lograr ciertas metas relacionadas con el procesador o la Entrada / Salida.
Los procesos limitados por la Entrada / Salida (requerimientos intensivos de Entrada / Salida) ocupan mucho de su tiempo en espera de operaciones de Entrada / Salida, por lo tanto:

• Deben tener prioridad para usar la cpu y efectuar la siguiente petición de Entrada / Salida, ya que se ejecutará (la operación de Entrada / Salida) en paralelo con otro proceso que utilice la cpu.
• Si deben esperar mucho tiempo a la cpu estarán ocupando memoria por un tiempo innecesario.

Un algoritmo sencillo consiste en establecer que la prioridad sea “1 / f”, donde “f” es la fracción del último cuanto utilizado por el proceso. Un proceso que utilice 2 mseg (dos milisegundos) de su cuanto de 100 mseg (cien milisegundos) tendrá prioridad 50 (cincuenta).
Un proceso que se ejecutó 50 mseg antes del bloqueo tendrá prioridad 2.
Un proceso que utilizó todo el cuanto tendrá prioridad 1.
Frecuentemente los procesos se agrupan en “Clases de Prioridad”, en cuyo caso se utiliza la Planificación con Prioridades entre las clases y con Round Robin (RR) dentro de cada clase. Si las prioridades no se reajustan en algún momento, los procesos de las clases de prioridad mínima podrían demorarse indefinidamente.



Colas de Retroalimentación de Niveles Múltiples
 
Proporcionan una estructura para lograr los siguientes objetivos:

• Favorecer trabajos cortos.
• Favorecer trabajos limitados por la Entrada / Salida para optimizar el uso de los dispositivos de Entrada / Salida.
• Determinar la naturaleza de un trabajo lo más rápido posible y planificar el trabajo (proceso) en consecuencia.

Un nuevo proceso entra en la red de línea de espera al final de la cola superior. Se mueve por esta cola “FIFO” hasta obtener la cpu.
Si el trabajo termina o abandona la cpu para esperar por la terminación de una operación de Entrada / Salida o la terminación de algún otro suceso, el trabajo abandona la red de línea de espera.
Si su cuanto expira antes de abandonar la cpu voluntariamente, el proceso se coloca en la parte trasera de la cola del siguiente nivel inferior.
El trabajo recibe servicio al llegar a la cabeza de esta cola si la primera está vacía.
Mientras el proceso continúe consumiendo totalmente su cuanto en cada nivel, continuará moviéndose hacia el final de las colas inferiores.
Generalmente hay una cola en la parte más profunda a través de la cual el proceso circula en asignación de rueda hasta que termina.
Existen esquemas en los que el cuanto otorgado al proceso aumenta a medida que el proceso se mueve hacia las colas de los niveles inferiores, en tal caso, cuanto más tiempo haya estado el proceso en la red de línea de espera, mayor será su cuanto cada vez que obtiene la cpu y no podrá obtener la cpu muy a menudo debido a la mayor prioridad de los procesos de las colas superiores.
Un proceso situado en una cola dada no podrá ser ejecutado hasta que las colas de los niveles superiores estén vacías.
Un proceso en ejecución es apropiado por un proceso que llegue a una cola superior.
Es un mecanismo adaptable, es decir que se adapta a cargas variables.
A los efectos de una revisión gráfica de lo enunciado precedentemente, ver la figura 2.5 [7, Deitel].


Política Versus Mecanismo de Planificación
 
Puede ocurrir que haya procesos con muchos procesos hijos ejecutándose bajo su control, por ejemplo, un proceso en un DBMS con procesos hijos atendiendo funciones específicas, tales como, análisis de interrogantes, acceso a discos, etc.
Es posible que el proceso principal (padre) pueda identificar la importancia (o criticidad) de sus procesos hijos, pero los planificadores analizados no aceptan datos de los procesos de usuario relativos a decisiones de planificación.
La solución es separar el mecanismo de planificación de la política de planificación, para ello se parametriza el algoritmo de planificación y los parámetros pueden ser determinados por medio de procesos del usuario; así el mecanismo está en el núcleo del Sistema Operativo pero la política queda establecida por un proceso del usuario.

[7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987.

[23] A. S. Tanenbaum. Sistemas Operativos Modernos. Prentice Hall Hispanoamericana, S.A., México, 1993.

Criterios de Planificación

Para realizar los objetivos de la planificación, un mecanismo de planificación debe considerar lo siguiente [7, Deitel]:

• La limitación de un proceso a las operaciones de Entrada / Salida: cuando un proceso consigue la cpu, ¿la utiliza solo brevemente antes de generar una petición de Entrada / Salida?.
• La limitación de un proceso a la cpu: cuando un proceso obtiene la cpu, ¿tiende a usarla hasta que expira su tiempo?.
• Si un proceso es por lote (batch) o interactivo: los usuarios interactivos deben recibir inmediato servicio para garantizar buenos tiempos de respuesta.
• ¿Qué urgencia tiene una respuesta rápida?: por ejemplo, un proceso de tiempo real de un sistema de control que supervise una refinería de combustible requiere una respuesta rápida, más rápida que la respuesta requerida por un proceso en lotes (batch) que deberá entregarse al día siguiente.
• La prioridad de un proceso: a mayor prioridad mejor tratamiento.
• Frecuentemente un proceso genera fallos (carencias) de página:
  • Probablemente los procesos que generan pocos fallos de página hayan acumulado sus “conjuntos de trabajo” en el almacenamiento principal.
  • Los procesos que experimentan gran cantidad de fallos de página aún no han establecido sus conjuntos de trabajo.
  • Un criterio indica favorecer a los procesos que han establecido sus conjuntos de trabajo.
  • Otro criterio indica favorecer a los procesos con una tasa alta de fallos de página ya que rápidamente generarán una petición de Entrada / Salida.
• Frecuentemente un proceso ha sido apropiado por otro de más alta prioridad, lo cual significa lo siguiente:
  • A menudo los procesos apropiados deben recibir un tratamiento menos favorable.
  • Cada vez que el Sistema Operativo asume la sobrecarga para hacer ejecutar este proceso, el corto tiempo de ejecución antes de la apropiación no justifica la sobrecarga de hacer ejecutar al proceso en primer lugar.
• ¿Cuánto tiempo de ejecución real ha recibido el proceso?: un criterio considera que debe ser favorecido un proceso que ha recibido muy poco tiempo de cpu.
• ¿Cuánto tiempo adicional va a necesitar el proceso para terminar?: los tiempos promedio de espera pueden reducirse priorizando los procesos que requieren de un tiempo de ejecución mínimo para su terminación, pero pocas veces es posible conocer la cantidad de tiempo adicional que cada proceso necesita para terminar. 

[7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987. 

Objetivos de la Planificación

Los objetivos de la planificación del procesador son los siguientes e involucran a los conceptos detallados seguidamente [7, Deitel]:

• Ser justa:
  • Todos los procesos son tratados de igual manera.
  • Ningún proceso es postergado indefinidamente.
• Maximizar la capacidad de ejecución:
  • Maximizar el número de procesos servidos por unidad de tiempo.
• Maximizar el número de usuarios interactivos que reciban unos tiempos de respuesta aceptables:
  • En un máximo de unos segundos.
• Ser predecible:
  • Un trabajo dado debe ejecutarse aproximadamente en la misma cantidad de tiempo independientemente de la carga del sistema.
• Minimizar la sobrecarga:
  • No suele considerarse un objetivo muy importante.
• Equilibrar el uso de recursos:
  • Favorecer a los procesos que utilizarán recursos infrautilizados.
• Equilibrar respuesta y utilización:
  • La mejor manera de garantizar buenos tiempos de respuesta es disponer de los recursos suficientes cuando se necesitan, pero la utilización total de recursos podrá ser pobre.
• Evitar la postergación indefinida:
  • Se utiliza la estrategia del “envejecimiento” .
  • Mientras un proceso espera por un recurso su prioridad debe aumentar, así la prioridad llegará a ser tan alta que el proceso recibirá el recurso esperado.
• Asegurar la prioridad:
  • Los mecanismos de planificación deben favorecer a los procesos con prioridades más altas.
• Dar preferencia a los procesos que mantienen recursos claves:
  • Un proceso de baja prioridad podría mantener un recurso clave, que puede ser requerido por un proceso de más alta prioridad.
  • Si el recurso es no apropiativo, el mecanismo de planificación debe otorgar al proceso un tratamiento mejor del que le correspondería normalmente, puesto que es necesario liberar rápidamente el recurso clave.
• Dar mejor tratamiento a los procesos que muestren un “comportamiento deseable”:
  • Un ejemplo de comportamiento deseable es una tasa baja de paginación.
• Degradarse suavemente con cargas pesadas:
  • Un mecanismo de planificación no debe colapsar con el peso de una exigente carga del sistema.
  • Se debe evitar una carga excesiva mediante las siguientes acciones:
    • No permitiendo que se creen nuevos procesos cuando la carga ya es pesada.
    • Dando servicio a la carga más pesada al proporcionar un nivel moderadamente reducido de servicio a todos los procesos.

Muchas de estas metas se encuentran en conflicto entre sí, por lo que la planificación se convierte en un problema complejo.

[7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987. 

Niveles de Planificación del Procesador

Se consideran tres niveles importantes de planificación, los que se detallan a continuación (ver Figura 2.4 [7, Deitel]):

• Planificación de alto nivel:
  • También se denomina Planificación de trabajos.
  • Determina a qué trabajos se les va a permitir competir activamente por los recursos del sistema, lo cual se denomina Planificación de admisión.
• Planificación de nivel intermedio:
  • Determina a qué procesos se les puede permitir competir por la cpu.
  • Responde a fluctuaciones a corto plazo en la carga del sistema y efectúa “suspensiones” y “activaciones” (“reanudaciones”) de procesos.
  • Debe ayudar a alcanzar ciertas metas en el rendimiento total del sistema.
• Planificación de bajo nivel:
  • 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.
  • La efectúa el Despachador del Sistema Operativo, el que opera muchas veces por segundo y reside siempre en el almacenamiento primario. 
  
    Los distintos Sistemas Operativos utilizan varias Políticas de Planificación, que se instrumentan mediante Mecanismos de Planificación.
  
  [7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987.

Planificación de Procesos

Cuando más de un proceso es ejecutable desde el punto de vista lógico, el Sistema Operativo debe decidir cuál de ellos debe ejecutarse en primer término.
El Planificador es la porción del Sistema Operativo que decide y el Algoritmo de Planificación es el utilizado.
Los principales “criterios” respecto de un buen algoritmo de planificación [23, Tanenbaum] son la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento (ver Tabla 2.2 [23, Tanenbaum]).

Tabla 2.2: Criterios de un buen algoritmo de planificación.

Criterio	Descripción
Equidad	Garantizar que cada proceso obtiene su proporción justa de la cpu
Eficacia	Mantener ocupada la cpu el ciento por ciento del tiempo
Tiempo de respuesta	Minimizar el tiempo de respuesta para los usuarios interactivos
Tiempo de regreso	Minimizar el tiempo que deben esperar los usuarios por lotes (batch) para obtener sus resultados
Rendimiento	Maximizar el número de tareas procesadas por hora

Algunas de estas metas son contradictorias, por ejemplo, minimizar el tiempo de respuesta para los usuarios interactivos significaría no ejecutar las tareas batch.

Cada proceso es único e impredecible, es decir que pueden requerir intensivamente operaciones de Entrada / Salida o intensivamente cpu; el planificador del Sistema Operativo no tiene la certeza de cuánto tiempo transcurrirá hasta que un proceso se bloquee, ya sea por una operación de Entrada / Salida o por otra razón .
Para evitar que un proceso se apropie de la cpu un tiempo excesivo, los equipos poseen un dispositivo que provoca una interrupción en forma periódica, por ejemplo 60 hz, o sea sesenta veces por segundo.
En cada interrupción del reloj el Sistema Operativo decide si el proceso que se está ejecutando continúa o si el proceso agotó su tiempo de cpu y debe suspenderse y ceder la cpu a otro proceso.
Los principales conceptos relacionados con Planificación del Procesador son los siguiente:

• Planificación apropiativa: es la estrategia de permitir que procesos ejecutables (desde el punto de vista lógico) sean suspendidos temporalmente.
• Planificación no apropiativa: es la estrategia de permitir la ejecución de un proceso hasta terminar.
• Planificación del procesador: determinar cuándo deben asignarse los procesadores y a qué procesos, lo cual es responsabilidad del Sistema Operativo.

[23] A. S. Tanenbaum. Sistemas Operativos Modernos. Prentice Hall Hispanoamericana, S.A., México, 1993.

Modelos de la concurrencia 27 - Sep- 2011

Multiprogramación y tiempo compartido

La mayoría de los sistemas operativos utilizan una técnica de gestión del procesador denominada multiprogramación, o una variante de ésta llamada tiempo compartido. Los primeros sistemas operativos gestionaban el procesador mediante otra técnica llamada monoprogramación (utilizada en los monitores de batch de flujo único). En este apartado comentaremos el por qué se evolucionó de la monoprogramación a la multiprogramación. Antes de entrar en esta discusión vamos a ver cómo se realizan las operaciones de entrada/salida (E/S), es decir, las operaciones que permiten la comunicación con los dispositivos de E/S.

Realización de las operaciones de E/S

Para facilitar el uso de los dispositivos, éstos se dividen en dos componentes. La primera es la componente eléctrica, a la cual se le llama controlador del dispositivo. La segunda es la componente mecánica, y es a lo que se llama propiamente dispositivo. Esta división permite un diseño más modular del dispositivo, además de simplificar su uso, ya que la CPU casi siempre trabaja con el controlador (más fácil de usar), que hace de interfaz entre la CPU y el dispositivo.

El controlador contiene una serie de registros llamados puertos de entrada/salida. Estos registros son accesibles (pueden ser leídos y modificados) mediante la ejecución de instrucciones máquina. Las operaciones de E/S se realizan a través de la carga y lectura de estos registros. Casi todo controlador dispone de los siguientes registros:

*Registro de estado. Indica la situación actual del dispositivo. Un bit del registro, al que llamaremos bit de ocupación, indica si el dispositivo está ocupado (el bit tendrá el valor uno) realizando una operación de E/S o si está desocupado (el bit tendrá el valor cero), y, por tanto, preparado para recibir una orden.

*Registro de órdenes. En este registro se escribe la operación de E/S que se desea que realice el dispositivo. Por ejemplo, en una cinta un código de 00 puede indicar rebobinar la cinta, 01 leer de la cinta, 10 escribir en la cinta, etc. El controlador se encarga de traducir estas órdenes en órdenes comprensibles para el dispositivo.

Buffer. Un buffer es un almacén de información. El buffer del controlador se utiliza para guardar temporalmente los datos implicados en una operación de E/S. Por ejemplo, si se quiere escribir en una impresora, se carga la información a escribir desde memoria principal al buffer. Posteriormente, el controlador mandará dicha información desde el buffer a la impresora.

Monoprogramación

Pasemos ahora a introducir el concepto de monoprogramación. En un sistema de monoprogramación todos los recursos del ordenador -CPU, memoria, discos, impresoras, etc- se dedican a la ejecución de un único programa. Este modo de trabajar lleva a una baja utilización de los recursos del ordenador como se justifica a continuación. Cuando el programa en ejecución realiza una operación de E/S se introduce la orden precisa en el registro de órdenes. El controlador responde a esto traduciendo esas órdenes al dispositivo, y poniendo a uno el bit de ocupación para indicar que el dispositivo está ocupado realizando una operación de E/S. Cuando termine la operación, el controlador pone a cero este bit para indicar que la operación concluyó, y el dispositivo está desocupado. Para saber cuándo termina la E/S, el programa, después de mandar la orden, tiene que ejecutar un ciclo del siguiente estilo:

Leer el registro de estado

     Mientras (el bit de ocupación esté a uno)

           Leer el registro de estado

                                                  Fin Mientras

Figura 6.1 Utilización de los recursos con monoprogramación

Obsérvese que esta forma de realizar las operaciones de E/S nos lleva a una situación en la que en un momento dado se tiene que, o bien la CPU está ejecutando instrucciones de un programa que no son de E/S, y los dispositivos de E/S están ociosos, o bien un único dispositivo de E/S está trabajando, mientras la CPU está en un ciclo comprobando si ha finalizado la operación. Esto se ilustra en la figura 6.1, donde los rectángulos rellenos a trazas representan el ciclo de comprobación. Para dar una medida de la infrautilización de los recursos que conlleva esta forma de realizar las E/S, piénsese que en el tiempo en que una impresora imprime una línea, la CPU, en lugar de ejecutar el ciclo de comprobación que aparece líneas más arriba, podría ejecutar millones de instrucciones de otro programa. A esta forma de realizar la E/S de los sistemas de monoprogramación se le llama E/S controlada por programa.

Multiprogramación

Para paliar la baja utilización de los recursos se desarrolló la multiprogramación. La multiprogramación se apoya en varios elementos del hardware: la interrupción, el DMA y el canal. En un sistema multiprogramado la memoria principal alberga a más de un programa de usuario. La CPU ejecuta instrucciones de un programa, cuando el programa en ejecución (es decir, el que ocupa la CPU) realiza una operación de E/S, emite ciertas órdenes al controlador (al igual que en los sistemas monoprogramados); pero en lugar de esperar a que termine la operación de E/S comprobando el bit de ocupación, se pasa a ejecutar otro programa. Si este nuevo programa realiza, a su vez, otra operación de E/S, se mandan las órdenes oportunas al controlador, y pasa a ejecutarse otro programa. Esto permite que varios dispositivos trabajen simultáneamente, además, en la CPU no se tienen que ejecutar ciclos de comprobación del estado de los dispositivos.

Esto se ilustra en la figura 6.2, en ella P1, P2 y P3 representan programas que residen en la memoria principal. Los rectángulos representan si el recurso está siendo utilizado, salvo para P1, P2 y P3 que representan si el programa ocupa la CPU. Al principio se está ejecutando P1, cuando inicia una operación de E/S con la impresora se cede la CPU a P2. P2 se ejecuta hasta que comienza una operación con el scanner, entonces se cede la CPU a P3, éste se ejecuta hasta que utiliza la impresora, momento en el cual se reanuda P1. Obsérvese que en este ejemplo la CPU siempre está activa. No obstante, podría suceder que todos los programas que residen en la memoria inicien una operación de E/S y en un momento dado todos estén esperando la finalización de su operación, esto conllevaría la no utilización de la CPU hasta que acabe la operación de E/S de cualquiera de los programas.

Figura 6.2 Utilización de los recursos con multiprogramación

Cuando un dispositivo acaba una operación de E/S debe de poder comunicárselo al programa que espera su finalización, para que así, el programa pueda proseguir su ejecución. Para indicar el fin de la operación el controlador manda una interrupción a la CPU. Una interrupción no es más que una señal eléctrica que provoca que el contador del programa y la PSW del programa en ejecución se salven en un lugar seguro de memoria, para, a continuación, cargar el contador de programa con una dirección fija de memoria donde reside un programa del sistema operativo que gestiona la interrupción. Este programa ejecutará cierto código para indicar al programa que esperaba la finalización de la operación de E/S que ésta ya terminó. Una vez que este programa del sistema operativo acaba su trabajo ejecuta una instrucción de retorno de interrupción, la cual restaura el contador de programa y la PSW del programa interrumpido, prosiguiéndose así su ejecución sin que éste sea consciente de que ha sido interrumpido. A esta forma de realizar la E/S se le llama E/S controlada por interrupción.

Analicemos ahora el DMA y el canal. Cuando un dispositivo realiza una operación de E/S, por ejemplo, una lectura de una cinta, la información leída pasa al buffer del controlador. Después, el programa que inició la lectura ejecuta ciertas instrucciones para copiar esta información desde el buffer hacia la memoria principal. La copia se realiza mediante un ciclo, copiando en cada iteración del ciclo un byte o una palabra desde el buffer del controlador a la memoria principal. En un controlador que disponga de DMA (acrónimo de Direct Memory Access, acceso directo a memoria) la copia del buffer a memoria la realiza el propio controlador; para ello, el programa ha de indicarle al controlador la dirección de memoria de inicio de la copia y el número de bytes a copiar, esto lo hace en el momento de darle la orden de E/S, metiendo esta información en algunos registros del controlador. Pasemos ahora a ver lo que es un canal, un canal es un pequeño procesador de E/S (es decir, un ordenador que sólo entiende instrucciones de E/S), su utilidad es proporcionar DMA a varios dispositivos, resultando más económico que tener un controlador DMA por dispositivo.

Después de la aparición de la multiprogramación surgieron los ordenadores de acceso múltiple o multiusuario. En ellos cada usuario dispone de un terminal, es decir, un teclado y una pantalla conectados al ordenador. Los usuarios ejecutan programas interactivos. Un programa interactivo es aquel que se comunica con el usuario por medio de un terminal, el usuario le suministra información al programa mediante el teclado, y recibe información del programa a través de la pantalla. Los programas de los usuarios comparten los recursos (CPU, memoria, discos, impresoras, etc) del ordenador. Estos sistemas hacen uso de una variante de la multiprogramación llamada tiempo compartido. 

Multiprocesador

Multiprocesamiento o multiproceso es tradicionalmente conocido como el uso de múltiples procesos concurrentes en un sistema en lugar de un único proceso en un instante determinado. Como la multitarea que permite a múltiples procesos compartir una única CPU, múltiples CPUs pueden ser utilizados para ejecutar múltiples hilos dentro de un único proceso.

El multiproceso para tareas generales es, a menudo, bastante difícil de conseguir debido a que puede haber varios programas manejando datos internos (conocido como estado o contexto) a la vez. Los programas típicamente se escriben asumiendo que sus datos son incorruptibles. Sin embargo, si otra copia del programa se ejecuta en otro procesador, las dos copias pueden interferir entre sí intentando ambas leer o escribir su estado al mismo tiempo. Para evitar este problema se usa una variedad de técnicas de programación incluyendo semáforos y otras comprobaciones y bloqueos que permiten a una sola copia del programa cambiar de forma exclusiva ciertos valores.

Las computadoras que tienen mas de un CPU son llamadas multiproceso. Un sistema operativo multiproceso coordina las operaciones de la computadoras multiprocesadoras. Ya que cada CPU en una computadora de multiproceso puede estar ejecutando una instrucci ón, el otro procesador queda liberado para procesar otras instrucciones simultáneamente. Al usar una computadora con capacidades de multiproceso incrementamos su velocidad de respuesta y procesos. Casi todas las computadoras que tienen capacidad de mu ltiproceso ofrecen una gran ventaja. 

Los primeros Sistemas Operativos Multiproceso realizaban lo que se conoce como: Multiproceso asimétrico: Una CPU principal retiene el control global de la computadora, así como el de los otros procesadores. Esto fue un primer paso hacia el multiproceso pero no fue la dirección ideal a seguir ya que la CPU principal podía conv ertirse en un cuello de botella. Multiproceso simétrico: En un sistema multiproceso simétrico, no existe una CPU controladora única. La barrera a vencer al implementar el multiproceso simétrico es que los SO tienen que ser rediseñados o diseñados desde el principio para trabajar en u n ambiente multiproceso. Las extensiones de Unix, que soportan multiproceso asimétrico ya están disponibles y las extensiones simétricas se están haciendo disponibles. Windows NT de Microsoft soporta multiproceso simétrico.

Multicomputdora

 

Multicomputadora con base de en Buses:

Es un esquema sin memoria compartida [25, Tanenbaum].

Cada cpu tiene una conexión directa con su propia memoria local.

Un problema importante es la forma en que las cpu se comuniquen entre sí.

El tráfico es solo entre una cpu y otra; el volumen de tráfico será varios órdenes de magnitud menor que si se utilizara la red de interconexión para el tráfico cpu - memoria.

Topológicamente es un esquema similar al del multiprocesador basado en un bus.

Consiste generalmente en una colección de estaciones de trabajo en una LAN (red de área local) (ver Figura 7.5 [25, Tanenbaum]). 

Multicomputadoras con Conmutador:

Cada cpu tiene acceso directo y exclusivo a su propia memoria particular [25, Tanenbaum].
Existen diversas topologías, las más comunes son la retícula y el hipercubo.
Las principales características de las retículas son:

• Son fáciles de comprender.
• Se basan en las tarjetas de circuitos impresos.
• Se adecúan a problemas con una naturaleza bidimensional inherente (teoría de gráficas, visión artificial, etc.) (ver Figura 7.6 [25, Tanenbaum]). 

Las principales características del hipercubo son:

• Es un cubo “n” - dimensional.
• En un hipercubo de dimensión 4:
  • Se puede considerar como dos cubos ordinarios, cada uno de ellos con 8 vértices y 12 aristas.
  • Cada vértice es un cubo.
  • Cada arista es una conexión entre 2 cpu.
  • Se conectan los vértices correspondientes de cada uno de los cubos.
• En un hipercubo de dimensión 5:
  • Se deberían añadir dos cubos conectados entre sí y conectar las aristas correspondientes en las dos mitades, y así sucesivamente.
• En un hipercubo de “n” dimensiones:
  • Cada cpu tiene “n” conexiones con otras cpu.
  • La complejidad del cableado aumenta en proporción logarítmica con el tamaño.
  • Solo se conectan los procesadores vecinos más cercanos:
    • Muchos mensajes deben realizar varios saltos antes de llegar a su destino.
    • La trayectoria más grande crece en forma logarítmica con el tamaño:
      • En la retícula crece como la raíz cuadrada del número de cpu.
  • Con la tecnología actual ya se pueden producir hipercubos de 16.384 cpu (ver Figura 7.7 [25, Tanenbaum]).

Ejemplos de Concurrencia y Sincronizacion

Concurrencia

1.- El hecho de reservar un asiento en una avión mediante un sistema basado en aplicaciones web, cuando decenas de personas en el mundo pueden reservarlo también, nos da una idea de lo importante y crucial que es el control de concurrencia en un sistema de base de datos a mediana o gran escala.

2.- En una Base de Datos bancaria podría ocurrir que se paguen dos cheques en forma simultánea sobre una cuenta que no tiene saldo suficiente para cubrirlos en su totalidad, esto es posible evitarlo si se tiene un control de concurrencia.

Sincronizacion

1.- Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo coge un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger el otro tenedor, para luego empezar a comer.

Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.

Si todos los filósofos cogen el tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.

El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre.

Sincronizacion y Exclusion mutua

Históricamente los lenguajes de programación concurrente y Las APIs de los sistemas operativos ofrecen un conjunto de primitivas que facilitan la interacción entre procesos de forma sencilla y eficiente.

Estas primitivas deben hacer posible:

􀂄Sincronización: Un proceso tiene acceso al estado de flujo de control que en ese instante tiene otro proceso.

􀂄Exclusión mutua: Garantiza que mientras que un proceso accede a un recurso o actualiza una variables compartida, ningún otro proceso accede al mismo recurso o a la variable compartida.

􀂄Sincronización condicional: Garantiza que un recurso sólo es accedido cuando se encuentra en un determinado estado interno.

Síncrono se conocen los límites para el ritmo de deriva de los relojes, al máximo retardo de
transmisión de mensajes y el tiempo para ejecutar cada paso de un proceso.

En un sistema síncrono, por definición hay también un límite superior max del tiempo tomado para transmitir cualquier mensaje.

2.4 Concurrencia y secuenciabilidad

La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, comparició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
Los procesos son concurrentes si existen simultáneamente. 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 relación entre ellos
La concurrencia puede presentarse en tres contextos diferentes:

• Varias aplicaciones: La multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varios trabajos o aplicaciones activas.

• Aplicaciones estructuradas: Como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.

• Estructura del sistema operativo: Las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos.

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

• Multiprogramación con un único procesador. El sistema operativo se encarga de ir repartiendo el tiempo del procesador entre los distintos procesos, intercalando la ejecución de los mismos para dar así una apariencia de ejecución simultánea.

• Multiprocesador. Es una maquina formada por un conjunto de procesadores que comparten memoria principal. En este tipo de arquitecturas, los procesos concurrentes no sólo pueden intercalar su ejecución sino también superponerla.

• Multicomputadora. Es una maquina de memoria distribuida, que está formada por una serie de computadoras. En este tipo de arquitecturas también es posible la ejecución simultánea de los procesos sobre los diferentes procesadores.

En general, la concurrencia será aparente siempre que el número de procesos sea mayor que el de procesadores disponibles, es decir, cuando haya más de un proceso por procesador. La concurrencia será real cuando haya un proceso por procesador. Aunque puede parecer que la intercalación y la superposición de la ejecución de procesos presentan formas de ejecución distintas, se verá que ambas pueden contemplase como ejemplos de procesos concurrentes
Existen diversas razones que motivan la ejecución de procesos concurrentes en un sistema:

• Facilita la programación de aplicaciones al permitir que éstas se estructuren como un conjunto de procesos que cooperan entre sí para alcanzar un objetivo común.

• Acelera los cálculos. 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 demás.

• Posibilita el uso interactivo a múltiples usuarios que trabajan de forma simultánea.

• Permite un mejor aprovechamiento de los recursos, en especial de la 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 ejecución de procesos concurrentes, también existen sus contras:

• Inanición e interrupción de procesos

• Ocurrencia de bloqueos

• Que dos o mas 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 cooperación de otros procesos. Un claro ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultánea en un sistema.
Procesos son cooperantes: Son aquellos que están diseñados 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 físicos o lógicos. Por ejemplo, dos procesos independientes compiten por el acceso a disco o para modificar una base de datos.

• Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar un objetivo común, Por ejemplo, un compilador que tiene varios procesos que trabajan conjuntamente para obtener un solo archivo de salida.

Elementos a gestionar y diseñar a causa de la concurrencia.
Se pueden enumerar los siguientes:

1. El sistema operativo debe ser capaz de seguir la pista de los distintos procesos activos. Esto lo hace por medio de PBC’s (Bloque de Control de Procesos)

2. El sistema operativo debe asignar y quitar los distintos recursos a cada proceso activo. Entre estos recursos se incluyen:

• Tiempo de procesador: Es función de la planificación.
• Memoria: La mayoría de los sistemas operativos emplean esquemas de memoria virtual.
• Archivos:
• Dispositivos de E/S:

3. El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.

4. Los resultados de un proceso deben ser independientes de la velocidad relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.

*Instituto tecnológico de Celaya, Sistemas operativos unidad III, (n.d.). Extraído el 24 de octubre de 2008 desde http://sisinfo.itc.mx/ITC-APIRGG/Materias/Mat1/SistOp-I_Unid3.php#

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 ejecución.
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 ejecución (una traza) a través de uno o más programas. Esta ejecución se entremezcla con la de otros procesos. De tal forma, que un proceso tiene un estado (en ejecución, listo, etc) y una prioridad de expedición u origen. La unidad planificada y expedida por el sistema operativo es el proceso.
En la mayoría de los sistemas operativos, estas dos características 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 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.
Un ejemplo de aplicación que podría hacer uso de los hilos es un servidor de ficheros de una red de área local. Cada vez que llega una solicitud de una operación sobre un fichero, se puede generar un nuevo hilo para su gestión. 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 simultáneamente y en diferentes procesadores.[1]

Un proceso ligero (thread o hebra) es un programa en ejecución que comparte la imagen de la memoria y otras informaciones con otros procesos ligeros.

Figura 1 Procesos ligeros

Es una unidad básica de utilización de la CPU consistente en un juego de registros y un espacio de pila. Comparte el código, los datos y los recursos con sus hebras pares

Una tarea (o proceso pesado) está formada ahora por una o más hebras

Una hebra sólo puede pertenecer a una tarea

 Figura 2 Tareas con una y varias hebras

CARACTERISTICAS


Se comparten recursos. La compartición de la memoria permite a las hebras pares comunicarse sin usar ningún mecanismo de comunicación inter-proceso del SO.

La conmutación de contexto es más rápida gracias al extenso compartir de recursos

No hay protección entre las hebras. Una hebra puede escribir en la pila de otra hebra del mismo proceso

Estado de los procesos ligeros

Un proceso ligero puede estar ejecutando, listo o bloqueado.

   

Figura 3 Estados de los Procesos ligeros

Paralelismo
Los procesos ligeros permiten paralelizar una aplicación.[2]

Figura 4 Paralelismo

[1] Milenkovic M. (1994). Sistemas Operativos. Conceptos y Diseño, 2ª Edición, McGraw-Hill.
Stallings, W. (1993).Computer Organization and Architecture, 3ª Edición. New York: Macmillan.
[2] HILOS (THREAD) (n.d.). Extraído el 24 de octubre de 2008 desde http://xue.unalmed.edu.co/~gsanchez/downloads/hilos.pdf

2.2.- Estados y transiciones de un proceso

El principal trabajo del procesador es ejecutar las instrucciones de máquina que se encuentran en memoria principal. Estas instrucciones se encuentran en forma de programas. Para que un programa pueda ser ejecutado, el sistema operativo crea un nuevo proceso, y el procesador ejecuta una tras otra las instrucciones del mismo. En un entorno de multiprogramación, el procesador intercalará la ejecución de instrucciones de varios programas que se encuentran en memoria. El sistema operativo es el responsable de determinar las pautas de intercalado y asignación de recursos a cada proceso.

Aunque cada proceso se una entidad independiente, con su propio contador de programa y estado interno, los procesos a menudo necesitan interactuar con otros procesos. Un proceso podría generar ciertas salidas que otro proceso utilizan como entradas, en el comando de Shell.

Hay varias formas de ver los estados de un proceso, en este caso vamos a basarnos en el de 5 estados y estos son:

1.- Inicio (New)

2.- Ejecuntadose (Running)

3.- Pausa (Waiting)

4.- Listo (Ready)

5.- Terminado (Terminated)

2.1.- Concepto de proceso

Un proceso es un programa en ejecución. Los procesos son gestionados por el sistema operativo y están formados por:

• Las instrucciones de un programa destinadas a ser ejecutadas por el microprocesador.
• Su estado de ejecución en un momento dado, esto es, los valores de los registros de la unidad central de procesamiento para dicho programa.
• Su memoria de trabajo, es decir, la memoria que ha reservado y sus contenidos.
• Otra información que permite al sistema operativo su planificación.

Esta definición varía ligeramente en el caso de sistemas operativos multihilo, donde un proceso consta de uno o más hilos, la memoria de trabajo (compartida por todos los hilos) y la información de planificación. Cada hilo consta de instrucciones y estado de ejecución.

Los procesos son creados y destruidos por el sistema operativo, así como también este se debe hacer cargo de la comunicación entre procesos, pero lo hace a petición de otros procesos. El mecanismo por el cual un proceso crea otro proceso se denomina bifurcación (fork). Los nuevos procesos pueden ser independientes y no compartir el espacio de memoria con el proceso que los ha creado o ser creados en el mismo espacio de memoria.

En los sistemas operativos multihilo 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.