Algoritmo apropiativo parecido al SRT consistente en calcular el Reponse Ratio (Ratio de respuesta) para asignar la CPU a procesos más viejos. (Para evitar la inanición).
Características:
•Es muy productivo pero se sobrecarga el sistema.
•Ofrece un buen tiempo de respuesta.
•Equilibra los procesos, aunque da prioridad a los procesos más cortos.
•Evita la inanición (los procesos que envejecen serán ejecutados).
Las prioridades, que son dinámicas, se calculan según la siguiente fórmula, donde pr es la “prioridad”, te es el “tiempo de espera” y ts es el “tiempo de servicio”:
•Elige proceso listo con valor mayor de R
•Tiene en cuenta edad del proceso
•Debe estimarse el tiempo se servicio previamente: en base a historia pasada o valor dado por usuario o administrador.
•R= w + s
S
R= tasa de respuesta
w= tiempo consumido esperando al procesador
s = tiempo de servicio esperado
Que corrige algunas deficiencias de SJF, particularmente el retraso excesivo de trabajos largos y el favoritismo excesivo para los trabajos cortos. HRN es un disciplina de planificación no apropiativa en la cual la prioridad de cada proceso no sólo se calcula en función del tiempo de servicio, sino también del tiempo que ha esperado para ser atendido. Cuando un trabajo obtiene el procesador, se ejecuta hasta terminar. Las prioridades dinámicas en HRN se calculan de acuerdo con la siguiente expresión: Prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio Como el tiempo de servicio aparece en el denominador, los procesos cortos tendrán preferencia. Pero como el tiempo de espera aparece en el numerador, los procesos largos que han esperado también tendrán un trato favorable. Obsérvese que la suma tiempo de espera + tiempo de servicio es el tiempo de respuesta del sistema para el proceso si éste se inicia de inmediato.
Para cada proceso, basado en el tiempo que va a ocupar el procesador(s) y el tiempo que lleva esperando para ocuparlo (w), Se calcula w+s/s, una vez hecho esto el proceso que tenga un valor mayor será asignado al procesador. Este algoritmo es bastante bueno, porque además de dar preferencia a los procesos cortos también tiene en cuenta el envejecimiento de los procesos para evitar así la “inanición”. Cuando el proceso actual termina o se bloquea, se elige el proceso listo con un mayor valor de R.
viernes, 6 de noviembre de 2009
3.4 Multiprocesamiento procesador
Un multiprocesador se define como una computadora que contiene dos o más unidades de procesamiento que trabajan sobre una memoria común bajo un control integrado. Si el sistema de multiprocesamiento posee procesadores de aproximadamente igual capacidad, estamos en presencia de multiprocesamiento simétrico; en el otro caso hablamos de multiprocesamiento asimétrico.
Si un procesador falla, los restantes continúan operando, lo cual no es automático y requiere de un diseño cuidadoso. Un procesador que falla habrá de informarlo a los demás de alguna manera, para que se hagan cargo de su trabajo . Los procesadores en funcionamiento deben poder detectar el fallo de un procesador determinado.
El Sistema Operativo debe percibir que ha fallado un procesador determinado y ya no podrá asignarlo y también debe ajustar sus estrategias de asignación de recursos para evitar la sobrecarga del sistema que está degradado.
Distribución de Ciclos
Una “estructura de ciclos o de repetición” implica la repetición de una serie de proposiciones (cuerpo del ciclo) hasta que ocurre alguna condición de terminación, por ejemplo:
For i = 1 to 3
Do
El procesador secuencial realizará en secuencia lo siguiente:
1.En un sistema de multiprocesamiento con tres procesadores disponibles se podrían
2.Ejecutar concurrentemente.
3.Reducción de la Altura del Árbol
4.Utilizando las propiedades asociativa, conmutativa y distributiva de la aritmética, los Compiladores pueden:
1.Detectar el paralelismo implícito en expresiones algebraicas.
2.Producir un código objeto para multiprocesadores que indique las operaciones que se pueden realizar simultáneamente.
3.Reordenar expresiones para que sean más apropiadas para la computación en paralelo.
Si un procesador falla, los restantes continúan operando, lo cual no es automático y requiere de un diseño cuidadoso. Un procesador que falla habrá de informarlo a los demás de alguna manera, para que se hagan cargo de su trabajo . Los procesadores en funcionamiento deben poder detectar el fallo de un procesador determinado.
El Sistema Operativo debe percibir que ha fallado un procesador determinado y ya no podrá asignarlo y también debe ajustar sus estrategias de asignación de recursos para evitar la sobrecarga del sistema que está degradado.
Distribución de Ciclos
Una “estructura de ciclos o de repetición” implica la repetición de una serie de proposiciones (cuerpo del ciclo) hasta que ocurre alguna condición de terminación, por ejemplo:
For i = 1 to 3
Do
El procesador secuencial realizará en secuencia lo siguiente:
1.En un sistema de multiprocesamiento con tres procesadores disponibles se podrían
2.Ejecutar concurrentemente.
3.Reducción de la Altura del Árbol
4.Utilizando las propiedades asociativa, conmutativa y distributiva de la aritmética, los Compiladores pueden:
1.Detectar el paralelismo implícito en expresiones algebraicas.
2.Producir un código objeto para multiprocesadores que indique las operaciones que se pueden realizar simultáneamente.
3.Reordenar expresiones para que sean más apropiadas para la computación en paralelo.
3.5 Conceptos basicos multiprocesamiento
A pesar de las grandes mejoras acaecidas en monoprocesadores para algunas aplicaciones no es suficiente.
La solución pueden ser los sistemas multiprocesadores:
•Solución más sencilla, natural y con mejor coste-prestaciones.
•Las mejoras en microprocesadores cada vez son más complejas: cada avance implica crecer en complejidad, potencia y superficie.
•Lenta pero clara mejora en el software, que permite explotar el paralelismo.
– Las arquitecturas actuales son muy diversas: hay más investigación que resultados definitivos.
– Hablaremos de multiprocesadores de pequeña y mediana escala
Dos factores clave para la extensión de los Multiprocesadores
1. Flexibilidad: El mismo sistema puede usarse para un único usuario incrementado el rendimiento en la ejecución de una única aplicación o para varios usuarios y aplicaciones en un entorno compartido.
2. Coste-rendimiento: Actualmente estos sistemas se basan en procesadores comerciales, por lo que su coste se ha reducido drásticamente. La inversión más fuerte se hace en la memoria y la red de interconexión.
Como su nombre indica son aquellos sistemas operativos que están montados sobre ordenadores que están compuestos por más de un procesador, supongamos un PC que en vez de tener un Pentium, tuviera dos o más Pentium conectados entre sí dentro de la misma placa base, esto sería un sistema multiprocesador.
Hilos
Es una característica que permite a una aplicación realizar varias tareas a la vez. Los distintos hilos de ejecución comparten una serie de recursos tales como el espacio de memoria, los archivos abiertos, situación de autenticación, etc.
Diferencia entre hilos y procesos
Los procesos son generalmente independientes, llevan bastante información de estados, e interactúan solo a través de mecanismos de comunicación dados por el sistema. Por otra parte muchos hilos generalmente otros recursos de forma directa. En muchos de los sistemas operativos que dan facilidades a los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro.
La solución pueden ser los sistemas multiprocesadores:
•Solución más sencilla, natural y con mejor coste-prestaciones.
•Las mejoras en microprocesadores cada vez son más complejas: cada avance implica crecer en complejidad, potencia y superficie.
•Lenta pero clara mejora en el software, que permite explotar el paralelismo.
– Las arquitecturas actuales son muy diversas: hay más investigación que resultados definitivos.
– Hablaremos de multiprocesadores de pequeña y mediana escala
Dos factores clave para la extensión de los Multiprocesadores
1. Flexibilidad: El mismo sistema puede usarse para un único usuario incrementado el rendimiento en la ejecución de una única aplicación o para varios usuarios y aplicaciones en un entorno compartido.
2. Coste-rendimiento: Actualmente estos sistemas se basan en procesadores comerciales, por lo que su coste se ha reducido drásticamente. La inversión más fuerte se hace en la memoria y la red de interconexión.
Como su nombre indica son aquellos sistemas operativos que están montados sobre ordenadores que están compuestos por más de un procesador, supongamos un PC que en vez de tener un Pentium, tuviera dos o más Pentium conectados entre sí dentro de la misma placa base, esto sería un sistema multiprocesador.
Hilos
Es una característica que permite a una aplicación realizar varias tareas a la vez. Los distintos hilos de ejecución comparten una serie de recursos tales como el espacio de memoria, los archivos abiertos, situación de autenticación, etc.
Diferencia entre hilos y procesos
Los procesos son generalmente independientes, llevan bastante información de estados, e interactúan solo a través de mecanismos de comunicación dados por el sistema. Por otra parte muchos hilos generalmente otros recursos de forma directa. En muchos de los sistemas operativos que dan facilidades a los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro.
3.6 Paralelismo multirpocesamiento
El paralelismo consiste en ejecutar más instrucciones en menos tiempo. Aunque las instrucciones sigan tardándose lo mismo al ejecutarse. A continuación mostraremos un ejemplo:
Un microprocesador ejecuta instrucciones de código máquina
Estas instrucciones le dicen como tiene que ir modificando diferentes posiciones de memoria, y como debe ir modificando el flujo de ejecución. Se tiende a pensar, erróneamente, que un procesador con un reloj a 200 MHz (200 millones de ciclos por segundo) ejecuta 200 millones de estas operaciones por segundo. Esto no es así, por una sencilla razón. Una instrucción no se ejecuta en un solo ciclo de reloj, salvo alguna rara excepción. De hecho, algunas instrucciones tardan bastantes más ciclos, llegando algunas a necesitar 50 o más ciclos para completarse. En cambio, las más rápidas se ejecutan en tan sólo 3 o 4 ciclos de reloj. Aquí es donde entra el paralelismo para solucionar este problema. Se puede dividir cualquier instrucción en fases más o menos comunes a todas:
-fetch (carga de la instrucción desde la memoria al procesador)
-decodificación (identificación de qué instrucción nos hemos encontrado)
-carga de operandos
-operación en sí
-escritura de resultados
Este esquema, expresamente simplificado, nos da una idea de las fases que todo microprocesador tiene. Vamos a suponer un microprocesador ideal donde todas las operaciones que se pueden ejecutar en él tardan 15 ciclos, correspondientes a tres ciclos por cada una de las 5 fases que hemos descrito. Si ejecutáramos tres de estas operaciones sin ningún tipo de paralelismo, tardaríamos 45 ciclos, según el siguiente esquema:
instr.1:111222333444555
instr.2:_________111222333444555
instr. 3:________111222333444555
Ahora supongamos que somos capaces de dividir el microprocesador en circuitos separados capaces cada uno de trabajar independientemente y ejecutar cada una de las 5 fases anteriores. Si logramos que sean independientes, cuando la instrucción uno ha acabado ya la fase de fetch y pasa a la decodificación, deja libre el módulo que se encarga del fetch, donde puede ir ya ejecutándose la segunda instrucción. De esta forma, logramos paralelizar las instrucciones.
instr.1111222333444555
instr.2:___111222333444555
instr. 3:______111222333444555
Resultado: las tres instrucciones, por separado, siguen ejecutándose en el mismo tiempo, pero en conjunto ya no tardan 45 ciclos, sino solo 21 ciclos. Más de un 45% de incremento en el rendimiento. De esta forma es como algunos procesadores muy paralelizados logran ejecutar, en promedio, más de una instrucción por ciclo de reloj, aunque estas instrucciones tarden, por sí mismas, más de un ciclo en ejecutarse.
El paralelismo en el software es la ejecución de un programa sin tomas en cuenta el hardware con que va ser ejecutado. Es considerado como el caso ideal de la ejecución de las instrucciones que forman parte de un programa, ya que no toma en cuenta las limitantes del hardware con que el mismo va ser ejecutado.
El paralelismo del hardware es la ejecución de un programa tomando en consideración el hardware con que va a ser ejecutado.
El desarrollo de hardware y software es un proceso integral que busca soluciones que permitan satisfacer cada vez más las condiciones de paralelismo con el fin de incrementar el promedio de ejecución paralela de instrucciones. Para lograr este objetivo es necesario detectar y resolver las dependencias entre instrucciones. El proceso de detección y resolución de dependencias entre instrucciones se conoce como el proceso de planificación de instrucciones.
Cuando la planificación de instrucciones es llevada a cabo únicamente por el compilador se dice que la planificación de instrucciones es estática. Y cuando la planificación de instrucciones es llevada a cabo únicamente por hardware (Ejemplo: microprocesador) se dice que la planificación de instrucciones es dinámica. La planificación de instrucciones en los microprocesadores súper escalares es un proceso de planificación de instrucciones estático y dinámico.
Un microprocesador ejecuta instrucciones de código máquina
Estas instrucciones le dicen como tiene que ir modificando diferentes posiciones de memoria, y como debe ir modificando el flujo de ejecución. Se tiende a pensar, erróneamente, que un procesador con un reloj a 200 MHz (200 millones de ciclos por segundo) ejecuta 200 millones de estas operaciones por segundo. Esto no es así, por una sencilla razón. Una instrucción no se ejecuta en un solo ciclo de reloj, salvo alguna rara excepción. De hecho, algunas instrucciones tardan bastantes más ciclos, llegando algunas a necesitar 50 o más ciclos para completarse. En cambio, las más rápidas se ejecutan en tan sólo 3 o 4 ciclos de reloj. Aquí es donde entra el paralelismo para solucionar este problema. Se puede dividir cualquier instrucción en fases más o menos comunes a todas:
-fetch (carga de la instrucción desde la memoria al procesador)
-decodificación (identificación de qué instrucción nos hemos encontrado)
-carga de operandos
-operación en sí
-escritura de resultados
Este esquema, expresamente simplificado, nos da una idea de las fases que todo microprocesador tiene. Vamos a suponer un microprocesador ideal donde todas las operaciones que se pueden ejecutar en él tardan 15 ciclos, correspondientes a tres ciclos por cada una de las 5 fases que hemos descrito. Si ejecutáramos tres de estas operaciones sin ningún tipo de paralelismo, tardaríamos 45 ciclos, según el siguiente esquema:
instr.1:111222333444555
instr.2:_________111222333444555
instr. 3:________111222333444555
Ahora supongamos que somos capaces de dividir el microprocesador en circuitos separados capaces cada uno de trabajar independientemente y ejecutar cada una de las 5 fases anteriores. Si logramos que sean independientes, cuando la instrucción uno ha acabado ya la fase de fetch y pasa a la decodificación, deja libre el módulo que se encarga del fetch, donde puede ir ya ejecutándose la segunda instrucción. De esta forma, logramos paralelizar las instrucciones.
instr.1111222333444555
instr.2:___111222333444555
instr. 3:______111222333444555
Resultado: las tres instrucciones, por separado, siguen ejecutándose en el mismo tiempo, pero en conjunto ya no tardan 45 ciclos, sino solo 21 ciclos. Más de un 45% de incremento en el rendimiento. De esta forma es como algunos procesadores muy paralelizados logran ejecutar, en promedio, más de una instrucción por ciclo de reloj, aunque estas instrucciones tarden, por sí mismas, más de un ciclo en ejecutarse.
El paralelismo en el software es la ejecución de un programa sin tomas en cuenta el hardware con que va ser ejecutado. Es considerado como el caso ideal de la ejecución de las instrucciones que forman parte de un programa, ya que no toma en cuenta las limitantes del hardware con que el mismo va ser ejecutado.
El paralelismo del hardware es la ejecución de un programa tomando en consideración el hardware con que va a ser ejecutado.
El desarrollo de hardware y software es un proceso integral que busca soluciones que permitan satisfacer cada vez más las condiciones de paralelismo con el fin de incrementar el promedio de ejecución paralela de instrucciones. Para lograr este objetivo es necesario detectar y resolver las dependencias entre instrucciones. El proceso de detección y resolución de dependencias entre instrucciones se conoce como el proceso de planificación de instrucciones.
Cuando la planificación de instrucciones es llevada a cabo únicamente por el compilador se dice que la planificación de instrucciones es estática. Y cuando la planificación de instrucciones es llevada a cabo únicamente por hardware (Ejemplo: microprocesador) se dice que la planificación de instrucciones es dinámica. La planificación de instrucciones en los microprocesadores súper escalares es un proceso de planificación de instrucciones estático y dinámico.
3.7 Sistema del multiprocesamiento
Multiprocesadores de pequeña y mediana escala.
Existen dos factores claves para la extensión de estos: la flexibilidad y el coste-rendimiento
Flexibilidad.
El mismo sistema puede usarse para un único usuario incrementado el rendimiento en la ejecución de una única aplicación o para varios usuarios y aplicaciones en un entorno compartido.
Coste-rendimiento.
Son aquellos sistemas operativos que están montados sobre ordenadores que están compuestos por más de un procesador. Se basan en procesadores comerciales.
Clasificación por uso de recursos:
Sistemas mono programados: Permiten la ejecución de un programa en el sistema, se instalan en la memoria y permanecen allí hasta que termine su ejecución.
Sistemas multiprogramados: Se basan en las técnicas de multiprogramación, existen 2 tipos: Multitarea apropiativa (preemptive) y Multitarea cooperativa
Sistemas de multiprocesamiento: Esta formados por varios procesadores, depende del tipo de trabajo y los objetivos que debe cumplir cada sistema para dar el mejor servicio al usuario. Se clasifican en Procesamiento por lotes (batch) aquí Cada programa realiza un conjunto de pasos secuenciales relacionados entre si.
Existen dos factores claves para la extensión de estos: la flexibilidad y el coste-rendimiento
Flexibilidad.
El mismo sistema puede usarse para un único usuario incrementado el rendimiento en la ejecución de una única aplicación o para varios usuarios y aplicaciones en un entorno compartido.
Coste-rendimiento.
Son aquellos sistemas operativos que están montados sobre ordenadores que están compuestos por más de un procesador. Se basan en procesadores comerciales.
Clasificación por uso de recursos:
Sistemas mono programados: Permiten la ejecución de un programa en el sistema, se instalan en la memoria y permanecen allí hasta que termine su ejecución.
Sistemas multiprogramados: Se basan en las técnicas de multiprogramación, existen 2 tipos: Multitarea apropiativa (preemptive) y Multitarea cooperativa
Sistemas de multiprocesamiento: Esta formados por varios procesadores, depende del tipo de trabajo y los objetivos que debe cumplir cada sistema para dar el mejor servicio al usuario. Se clasifican en Procesamiento por lotes (batch) aquí Cada programa realiza un conjunto de pasos secuenciales relacionados entre si.
3.8 Organizaci{on del Multiprocesador
Las organizaciones más comunes son:
Tiempo compartido o bus común (conductor común).
Tiene un solo camino de comunicación entre todas las unidades funcionales. El bus común es en esencia una unidad pasiva. El procesador de e/s que quiere transferir datos realiza lo siguiente:
1. Verificar la disponibilidad del conductor y de la unidad de destino.
2. Informar a la unidad de destino de lo que se va a hacer con los datos.
3. Iniciar la transferencia de datos.
Es una organización económica, simple y flexible pero con una sola vía de comunicación, así que el sistema falla totalmente si falla el bus. La tasa neta de transmisiones está limitada por la tasa neta de transmisión del conductor. La contención por el uso del bus en un sistema sobrecargado puede ocasionar una seria degradación.
Matriz de barras cruzadas e interruptores.
La multiplicidad de caminos de transmisión puede proporcionar tasa de transferencia muy alta puesta que las referencias a dos unidades diferentes de almacenamiento no son bloque antes sino simultánea.
Almacenamiento de interconexión múltiple.
Es obtenida al sacar las lógicas del control, de conmutación y de arbitraje de prioridades fuera del interruptor de barras cruzadas se las coloca en la interfaz de cada unidad de almacenamiento. Hay una conexión de almacenamiento por unidad funcional.
Tiempo compartido o bus común (conductor común).
Tiene un solo camino de comunicación entre todas las unidades funcionales. El bus común es en esencia una unidad pasiva. El procesador de e/s que quiere transferir datos realiza lo siguiente:
1. Verificar la disponibilidad del conductor y de la unidad de destino.
2. Informar a la unidad de destino de lo que se va a hacer con los datos.
3. Iniciar la transferencia de datos.
Es una organización económica, simple y flexible pero con una sola vía de comunicación, así que el sistema falla totalmente si falla el bus. La tasa neta de transmisiones está limitada por la tasa neta de transmisión del conductor. La contención por el uso del bus en un sistema sobrecargado puede ocasionar una seria degradación.
Matriz de barras cruzadas e interruptores.
La multiplicidad de caminos de transmisión puede proporcionar tasa de transferencia muy alta puesta que las referencias a dos unidades diferentes de almacenamiento no son bloque antes sino simultánea.
Almacenamiento de interconexión múltiple.
Es obtenida al sacar las lógicas del control, de conmutación y de arbitraje de prioridades fuera del interruptor de barras cruzadas se las coloca en la interfaz de cada unidad de almacenamiento. Hay una conexión de almacenamiento por unidad funcional.
3.9 Sistemas Operativos del miltiprocesador
Sus capacidades funcionales incluyen:
Asignación y administración de recursos.
Protección de tablas y conjuntos de datos.
Prevención contra el ínter bloqueo del sistema.
Terminación anormal.
Equilibrio de cargas de Entrada / Salida.
Equilibrio de carga del procesador. Reconfiguración.
Las últimas 3 son importantes ya que es fundamental explotar el paralelismo en el hardware y en los programas y hacerlo automáticamente. Las organizaciones básicas de los Sistemas Operativos para multiprocesadores son las siguientes:
Maestro / satélite: No logra la utilización óptima del software dado que el procesador maestro ejecuta el sistema operativo y el de satélite solo programas de usurario.
Ejecutivo separado para cada procesador: cada procesador tiene su S.O. Y responde a interrupciones de los usuarios que operan en ese procesador. Es más confiable que la organización maestro/satélite. Cada procesador controla sus recursos dedicados. Los procesadores no cooperan en la ejecución de un proceso individual, que habrá sido asignado a uno de ellos
Tratamiento simétrico (o anónimo) para todos los procesadores: Es la más complicada de implementar la más poderosa y confiable. El S.O. administra un grupo de procesadores idénticos, donde cualquiera puede utilizar cualquier dispositivo de Entrada / Salida y cualquiera puede referenciar a cualquier unidad de almacenamiento. El S.O. precisa código reentrarte y exclusión mutua. Adquieren significativa importancia el hardware y el software para resolución de conflictos. Todos los procesadores pueden cooperar en la ejecución de un proceso determinado. El procesador ejecutivo es el responsable (uno sólo) en un momento dado de las tablas y funciones del sistema; así se evitan los conflictos sobre la información global.
Asignación y administración de recursos.
Protección de tablas y conjuntos de datos.
Prevención contra el ínter bloqueo del sistema.
Terminación anormal.
Equilibrio de cargas de Entrada / Salida.
Equilibrio de carga del procesador. Reconfiguración.
Las últimas 3 son importantes ya que es fundamental explotar el paralelismo en el hardware y en los programas y hacerlo automáticamente. Las organizaciones básicas de los Sistemas Operativos para multiprocesadores son las siguientes:
Maestro / satélite: No logra la utilización óptima del software dado que el procesador maestro ejecuta el sistema operativo y el de satélite solo programas de usurario.
Ejecutivo separado para cada procesador: cada procesador tiene su S.O. Y responde a interrupciones de los usuarios que operan en ese procesador. Es más confiable que la organización maestro/satélite. Cada procesador controla sus recursos dedicados. Los procesadores no cooperan en la ejecución de un proceso individual, que habrá sido asignado a uno de ellos
Tratamiento simétrico (o anónimo) para todos los procesadores: Es la más complicada de implementar la más poderosa y confiable. El S.O. administra un grupo de procesadores idénticos, donde cualquiera puede utilizar cualquier dispositivo de Entrada / Salida y cualquiera puede referenciar a cualquier unidad de almacenamiento. El S.O. precisa código reentrarte y exclusión mutua. Adquieren significativa importancia el hardware y el software para resolución de conflictos. Todos los procesadores pueden cooperar en la ejecución de un proceso determinado. El procesador ejecutivo es el responsable (uno sólo) en un momento dado de las tablas y funciones del sistema; así se evitan los conflictos sobre la información global.
Suscribirse a:
Entradas (Atom)