Para la administración de actividades simultáneas se requiere que el sistema operacional proporcione primitivas para la creación, destrucción, activación y bloqueo de procesos, las cuales idealmente deben estar complementadas por otros instrumentos para el manejo de la exclusión mutua, la sincronización y la comunicación entre procesos.
El sistema operacional debe mantener información sobre todos los procesos del sistema. Para ello pueden crearse bloques de control similares al bloque de control de procesos (BCP) utilizado en los sistemas grandes. Típicamente éstos contienen:
• Número del proceso
• Estado
• Valor del contador ordinal
• Apuntador a la pila asociada al proceso
• Apuntador a información de entrada/salida
• Prioridad.
3.1 PLANEACION TRABAJOS JOB SCHEDULING
1. Introducción
El origen de este grupo de investigación surge por la necesidad de resolver problemas dinámicos. Para ello se empleó técnicas basadas en el conocimiento (sistemas expertos) y métodos de razonamiento temporal. Con la resolución de estos problemas se puso de manifiesto la aplicabilidad de estos modelos y técnicas en problemas de ámbito real. Debido a la amplitud y complejidad de estos problemas, el grupo siguió distintas líneas de investigación. Todas ellas están enmarcadas bajo el área de la Inteligencia Artificial.
El razonamiento temporal constituye un campo activo de investigación, con aplicaciones en varias áreas de Inteligencia Artificial, tales como sistemas basados en el conocimiento, planificación, scheduling, comprensión del lenguaje natural, etc. En estas áreas, el tiempo juega un papel esencial. Los problemas tienen un comportamiento dinámico y es necesario representar y razonar la información sobre su dimensión temporal. A raíz de los trabajos realizados en sistemas basados en el conocimiento y razonamiento temporal, surgieron las principales líneas de investigación, enunciadas a continuación:
• Sistemas basados en el conocimiento con capacidad de razonamiento temporal. Integración en una arquitectura blackboard. Restricciones de tiempo real.
• Sistemas de planificación.
• Modelos temporales: Representación, Algoritmos Temporales.
• Sistemas de scheduling (un problema en el marco del razonamiento temporal).
2. Sistemas basados en el conocimiento. Razonamiento temporal
Dentro de la Inteligencia Artificial y concretamente dentro de los sistemas basados en el conocimiento (de donde surgió la arquitectura REAKT, uno de los campos de mayor difusión ha sido la teoría de agentes inteligentes. Para poder incorporar conocimiento en un sistema que trabaja en un entorno con restricciones de tiempo real, se escogió la representación mediante el modelo de blackboard utilizando el paradigma de agente/sistemas multi-agente. Así, múltiples agentes pueden ejecutarse en paralelo, compartiendo datos comunes. Como consecuencia directa de esta línea de investigación se sigue trabajando en la teoría de agentes: arquitectura, comunicación y lenguajes. Adicionalmente, se sitúa el desarrollo de herramientas para la representación y tratamiento de hechos temporales (TempoClips).
3. Planificación
Uno de los trabajos actuales desarrollados en el grupo, y en este ámbito, consiste en un planificador de orden parcial regresivo POCL (Partial Order Causal Link) denominado SPLIN (Sistema de PLanificación INteligente)
Para poder añadir restricciones de alto nivel entre acciones, se estudia la incorporación de macro-acciones. En un primer nivel de planificación, se obtiene un plan abstracto, compuesto por una secuencia parcialmente ordenada de macro-acciones, que se refinará en sucesivos niveles de planificación. Igualmente, se está trabajando en la planificación de Redes Jerárquicas de Tareas (HTN) y en la aplicación de heurísticas independientes del dominio.
4. Modelos temporales.
Un problema temporal lo especificamos como un conjunto de variables X={xi}, un Dominio de Interpretación D, y un conjunto de restricciones temporales (por defecto, binarias) entre las variables {(xicijxj)}. Las variables pueden representar puntos o intervalos temporales, mientras que las restricciones pueden ser cualitativas o cuantitativas (distancia temporal). Estos problemas dan lugar a una red de restricciones temporales (Temporal Constraint Network o TCN) que pueden representarse como un grafo dirigido. El módulo especial encargado de gestionar as restricciones se denomina Temporal Constraint Network Manager (TCNM). Este módulo debe garantizar la consistencia del TCN, obtener la red mínima y soluciones concretas.
Pueden plantearse diferentes alternativas de gestión. Entre estas, podemos identificar, principalmente:
• Procesos de clausura, donde cada nueva restricción se debe propagar a toda la red de restricciones. El principal inconveniente estriba en la alta complejidad tanto espacial como temporal. Al respecto existen diversos algoritmos de clausura.
• Procesos sin clausura, donde únicamente se mantendrían las restricciones explícitas introducidas, disminuyendo así la complejidad espacial. Tanto en este, como en el método anterior, el objetivo final es obtener unas restricciones consistentes y mínimas.
• Procesos de obtención de soluciones. En este marco, podrían englobarse los procesos basados en CSP.
En general, este campo puede englobarse bajo la denominación de 'Razonamiento sobre Restricciones Temporales'. Actualmente, nuestro grupo está trabajando en la integración de restricciones temporales disyuntivas (cualitativas y cuantitativas) entre puntos, intervalos y duraciones, en el tratamiento de restricciones no binarias, y en la asociación de restricciones a contextos temporales. Referente a ello, definimos, tanto un método de representación como los algoritmos de razonamiento específicos.
5. Proceso de Scheduling.
El objetivo del proceso de scheduling es asegurar la corrección del plan en función de los recursos disponibles y de las restricciones temporales impuestas por el problema. Adicionalmente, dispone de criterios para garantizar la optimalidad del plan generado, de acuerdo a funciones de evaluación de costes y otros criterios. En el proceso de scheduling, a menudo, se utiliza un problema de satisfacción de restricciones o CSP que pueda evaluar todos los posibles valores de asignación a las variables del problema, buscando aquella solución que cumpla con todas las restricciones del problema. Adicionalmente, se está trabajando en la incorporación de razonamiento temporal en la resolución de problemas de scheduling mediante CSP’s.
6. Integración de Planificación y Scheduling
Hoy en día muchos problemas reales pueden ser enmarcados como problemas de planificación y scheduling. Por una parte, se trata de obtener un plan, y por otra, delimitar la ejecutabilidad de las acciones en el tiempo, asignándoles los recursos necesarios y teniendo en cuenta las restricciones generales del problema (posiblemente utilizando criterios de optimización y garantizando su ejecutabilidad).
Tradicionalmente, los métodos para solucionar problemas de planificación y scheduling se dividen en dos etapas diferentes. Sin embargo, la resolución de estos problemas no es abordable mediante estos procesos por separados. La idea principal es la integración de ambos (ver Fig. 2). Si los procesos de planificación y scheduling colaboran durante la resolución del problema, se podría obtener una mejor solución. Por ello, trabajamos en una arquitectura independiente del dominio en la que el planificador opera de forma simultánea con el scheduler. Esta integración permite garantizar la ejecutabilidad del plan y satisfacer óptimamente las restricciones del problema, simultáneamente con la construcción del plan.
Mediante el lenguaje de especificación, basado en frames, del que ya disponemos, se puede definir el dominio del problema. Una vez obtenido el plan óptimo mediante el proceso de planificación-scheduling, éste pasa a ejecución. Durante la ejecución del plan pueden aparecer nuevas restricciones del problema, incidencias, etc., debiéndose producir una reactividad en el proceso readaptando el plan obtenido.
Maximizar la utilización del CPU obtenida con la multiprogramación.
Ciclo de ráfaga CPU–I/O. La ejecución del proceso consiste de un ciclo de CPU y de una espera de I/O.
Distribución de las ráfagas de CPU.
Un planificador de tareas es una aplicación de software de la empresa que se encarga de la ejecución desatendida fondo, comúnmente conocido por razones históricas como del procesamiento por lotes.
Los sinónimos son lote sistema, Sistema de Gestión de Recursos Distribuidos (SGDD), y Distributed Resource Manager (DRM). Hoy en día el trabajo de programadores suelen ofrecer una interfaz gráfica de usuario y un único punto de control para la definición y el seguimiento de las ejecuciones en el fondo de una red distribuida de computadoras. Trabajo cada vez más programadores están obligados a organizar la integración de los negocios en tiempo real con las actividades tradicionales de transformación de fondo que, a través de diferentes plataformas de sistemas operativos y entornos de aplicaciones de negocio.
Algunos conceptos:
- Utilización máxima de la CPU se obtiene vía multiprogramación
- Ciclo ráfagas CPU–I/O – la ejecución de un proceso consiste de un ciclo de ejecución de CPU continuado por un ciclo de espera por I/O
- Distribución de ráfagas de CPU
Conceptos:
• Job – Un job es una tarea de base de datos definida en términos de una secuencia válida de comandos Transact-SQL, como por ejemplo una serie de comandos dump o dbcc.
• Schedule – Un schedule es un horario de ejecución, definido en términos de atributos particulares, como fecha y hora de inicio, periodicidad, fecha y hora de finalización, etc.
• Scheduled Job – Un scheduled job es un job que ha sido asociado a un schedule y que, en consecuencia, se ejecutará automáticamente de acuerdo a lo definido en dicho schedule. La ejecución del scheduled job se lleva a cabo en el ASE denominado Target Server.
• Target Server – Es el servidor ASE en el cual se ejecutará un scheduled job.
• JS Server – Es el servidor ASE que almacena y administra los componentes del Job Scheduler (jobs, Schedule y scheduled jobs) y es el encargado de controlar la ejecución de los scheduled jobs a través de los JS Tasks e interactuando con el JS Agent. En este servidor reside la base de datos sybmgmtdb en donde se almacena toda la información del sistema del Job Scheduler.
• JS Task – Es una tarea interna que corre en el ASE denominado JS Server, encargada de determinar qué scheduled jobs deben ser ejecutados en cada momento del tiempo. Cuando una tarea JS Task determina que una scheduled job debe ser ejecutado, pasa la información al JS Agent, quien inicia la ejecución en el ASE denominado Target Server.
• JS Agent – Es un proceso del sistema operativo que corre en la mísma máquina del JS Server. El JS Agent es el encargado de controlar la ejecución de los scheduled jobs en el Target Server, de acuerdo a la información recibida por los JS Task.
Objetivo de la planificación: Minimizar el tiempo de espera y minimizar el tiempo de respuesta. La planificación (scheduling) es la base para lograr la multiprogramación.
Un sistema multiprogramado tendrá varios procesos que requerirán el recurso procesador a la vez. Esto sucede cuando los procesos están en estado ready (pronto). Si existe un procesador disponible, se debe elegir el proceso que será asignado para ejecutar. La parte del sistema operativo que realiza la elección del proceso es llamada planificador (scheduler).
La planificación hace referencia a un conjunto de políticas Y mecanismos incorporados a sistemas operativos que gobiernan el orden en que se ejecutan los trabajos.
Un planificador es un módulo del S.O que selecciona el siguiente trabajo que hay que admitir en el sistema y el siguiente proceso que hay que ejecutar.
En muchos sistemas, la actividad de planificación se divide en tres funciones independientes:
-Planificación a largo,
-Medio, y
-Corto plazo.
FIRST IN FIRST OUT (FIFO)
Primero en llegar primero en ser tendido. la cpu se asigna a los procesos en el orden que lo solicitan, cuando el primer proceso entra en el sistema, se le inicia de inmediato y se le permite ejecutar todo el tiempo que necesite, cuando llegan otros procesos se les coloca al final de la cola.Cuando se bloquea el proceso en ejecucion, se ejecuta el primer proceso de la cola, si un proceso bloqueado vuelve a estar listo se le coloca al final de la cola como si fuera un proceso recien llegado.
. Es equitativo
. Solo necesita una cola para implementarse
. Presenta desventajas cuando se tienen procesos dedicados a CPU y dedicados a E/S
ROUN ROBIN (RR)
Algoritmo apropiativo consistente en determinar un quantum (tiempo de reloj) que marcará el intervalo de CPU que se le cederá al proceso ejecutando. Cuando finalice el quantum al Proceso se le quitará la CPU y pasará a la cola de listo. La cola de listos sigue la estructura FIFO. Si un proceso no consume su quantum libera la CPU y ésta es asignada al siguiente Proceso de la cola de listo.
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.
Características:
• Fácil de implementar.
• Perjudica a los procesos de E/S.
• Si el quantum es muy grande se comporta como un FCFS.
• El tiempo de respuesta para procesos cortos es bueno.
• Trato equitativo entre procesos, bueno para interactividad.
• No se produce inanición.
• El valor mínimo del quantum debe ser (10 * Tiempo Cambio Contexto)
• El quantum más adecuado es el Tiempo de CPU del proceso más corto.
SHORTEST JOB FIRST (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”.
Características:
-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.
3.3.4 SHORTEST REMAINING TIME JOB SCHEDULING
SHORTEST REMAINING TIME (STR)
Esta disciplina elige siempre al proceso que le queda menos tiempo de ejecución estimado para completar su ejecución; de esta forma aunque un proceso requiera mucho tiempo de ejecución, a medida que se va ejecutando iría avanzando en la lista de procesos en estado listo hasta llegar a ser el primero. Para realizar esta elección, es necesario actualizar el PCB de los procesos a medida que se le asigna tiempo de servicio, lo que supone una mayor sobrecarga adicional.
Es una disciplina apropiativa ya que a un proceso activo se le puede retirar la CPU si llega a la lista de procesos en estado listo otro con un tiempo restante de ejecución estimado menor.
Este algoritmo es la versión no apropiativa o expulsiva del algoritmo Shortest Process Next (SPN) o también llamado Shortest Job First (SJF).
En el algoritmo Shortest Remaining Time el planificador selecciona el proceso más corto, al igual que antes, pero en este caso el cambio se controla cada vez que un proceso llega a la cola. Es decir, cuando un proceso se desbloquea o se crea uno nuevo y el tiempo de ráfaga es menor que el tiempo de ráfaga del proceso que se está ejecutando, entonces se realiza un cambio de contexto, el bloqueado se ejecuta y el que se estaba ejecutando pasa a la cola de procesos listos. De este modo cuando se desbloquea o entra un proceso nuevo, se calcula su tiempo de ráfaga. Si el proceso que se está ejecutando le queda más tiempo de ráfaga que nuestro tiempo de ráfaga calculado entonces se procede a realizar el cambio de contexto.
. Definición: Algoritmo apropiativo (que en cualquier momento se le puede quitar la CPU para asignársela otro proceso) consistente en elegir de la cola de listos el proceso con menos necesidad de tiempo restante de CPU para cada instante de tiempo.
Características:
-Ofrece un buen tiempo de respuesta.
-La productividad es alta a cambio de la sobrecarga del sistema (a cada paso debe decidir a que proceso asignarle la CPU).
-Penaliza los procesos largos.
-Se puede producir inanición.
3.3.5 Highest Response Ratio Next Job Scheduling (HRN)
HIGHEST RESPONSE RATIO NEXT (HRN)
Definición:
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
Donde:
R= Tasa de respuesta
w= Tiempo consumido esperando al procesador
s= Tiempo de servicio esperado
3.4 MULTIPROCESAMIENTO PROCESADOR
MULTIPROCESAMIENTO
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:
En un sistema de multiprocesamiento con tres procesadores disponibles se podrían
Ejecutar concurrentemente.
Reducción de la Altura del Arbol
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
SISTEMAS MULTIPROCESAMIENTO
A pesar de las grandes mejoras acaecidas en monoprocesadores para algunas aplicaciones no es suficiente.
– La solución pueden ser los sistemas multiprocesadores:
o Solución más sencilla, natural y con mejor coste-prestaciones.
o Las mejoras en microprocesadores cada vez son más complejas: cada avance implica crecer en complejidad, potencia y superficie.
o 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 median 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 si dentro de la misma placa base, esto sería un sistema multiprocesador.
CLASIFICACION POR USO DE LOS RECURSOS
Sistemas monoprogramados: Son los que solo 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: Son aquellos que se basan en las técnicas de multiprogramación, existen dos tipos:
Multitarea apropiativa (preemptive): Se utiliza en sistemas operativos cuya gestión es quitar el control del microprocesador al programa que lo tiene.
Multitarea cooperativa: El programa tiene el control del microprocesador, el sistema operativo no puede decidir quien usa el microprocesador.
Sistemas de multiprocesamiento: Formado por varios microprocesadores. 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): Cada programa realiza un conjunto de pasos secuenciales relacionados entre si
Multiprocesamiento
Medios de multiprocesamiento que tienen más de un procesador que opera en la misma memoria pero ejecuta procesos simultáneamente. En un sistema de multiprocesamiento procesadores múltiples son empleados a ejecutado más de una actividad en el tiempo, siempre que la informática masiva deba ser realizada con regularidad.
Multiprocesador.
Como muchas de las actividades principales de la informática se ejecutan simultáneamente por los procesadores diferentes.
Sin embargo, es esencial proporcionar la sincronización entre procesador múltiple ellos tienen acceso a la memoria común tal que ninguna parte del trabajo de informática debería ser descuidada por el procesador individual con una presunción que el otro procesador lo hará.
Un sistema de multiprocesamiento con varios funcionamientos juntos a la vez proporcionará un ambiente de multiprogramación. La multiprogramación permite que programas múltiples residan en áreas separadas de la memoria principal al mismo tiempo. Con este acercamiento, es posible mantener dos o más empleos simultáneamente en la ejecución o en estados de la ejecución.
Los sistemas de ordenador de multiprocesador son caros y encontraron su uso sólo en la aplicación de informática compleja y en la alta velocidad que funda el punto aplicación de cálculo numérica en espacios de Investigación e Industria.
3.6 PARALELISMO MULTIPROCESAMIENTO
PARALELISMO
El paralelismo consiste en ejecutar más instrucciones en menos tiempo, aunque las instrucciones sigan tardando lo mismo en ejecutarse, mediante un simple truco, aunque algo difícil de explicar en detalle. Intentémoslo.
un microprocesador ejecuta instrucciones de código máquina.
Estas instrucciones le dicen cómo 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.
En la realidad, como siempre, no todo es tan fácil y hay muchos problemas al diseñar un procesador con paralelismo. Por citar algunos de los problemas más comunes, hay veces que una instrucción no se puede ejecutar ya que requiere un dato que quizás calculaba la operación anterior (cosa muy habitual). Claro, si ante este problema detuviéramos la anterior instrucción, bloquearía el procesador y se acabaría el paralelismo hasta que acabara la primera instrucción y con ella se pudiera reanudar la segunda. Para evitar estos problemas se recurre a cortocircuitos, o lo que es lo mismo, se comunican diferentes fases del microprocesador internamente para pasarse antes los datos. Esto, sin embargo, también nos da otros problemas, ya mucho más complicados, como el encontrarnos con que hay que decidir que datos son los correctos en cada momento. En estos problemas ya no entraremos, y se podrían resumir en que el procesador ha de decidir como paralelizar las instrucciones. Bien, todo lo que hemos visto sobre el paralelismo involucra única y exclusivamente al microprocesador en sí, y más bien a su diseño. El software que se ejecuta sobre él ignora totalmente si hay paralelismo o no. Esto es el paralelismo implícito.
Por el contrario, Intel implementa una solución que de hecho ya deriva de ideas de principios de los años 80. En el paralelismo explícito, el procesador ya no es el que decide cómo paralelizar las instrucciones, sino que es el compilador del software el que ha empaquetado las instrucciones para que el microprocesador pueda ejecutarlas paralelamente sin tantos problemas. De hecho, esta manera es mucho más eficiente, porque el compilador tiene todo el tiempo del mundo para decidir cómo paralelizar y por supuesto, la lógica que puede aplicar es infinitamente más potente que la que podemos encontrar implementada en cualquier microprocesador. Esto también redunda en una simplificación de la circuitería de control del microprocesador, lo que permite acelerar aún más las instrucciones. Además, queda libre más espacio para incluir aún más registros y hacer los buses internos más anchos, lo que permite ejecutar aún más instrucciones en paralelo.
Paralelismo en software Definamos como paralelismo en software como la ejecución de un programa sin tomar en cuenta el hardware con que va ser ejecutado. El paralelismo en software 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.
Paralelismo en hardware Definamos como paralelismo en hardware como la ejecución de un programa tomando en consideración el hardware con que va a ser ejecutado.
El diagrama de paralelismo en Software representa el caso ideal con que dicho programa puede ser ejecutado. Nótese que la ejecución de las 8 instrucciones se realiza solamente en tres ciclos de máquina. Por otro lado podemos observar las limitantes que genera la ejecución de este mismo programa con un hardware en particular (procesador Superescalar con capacidad de ejecutar un acceso a la memoria y una operación aritmética simultáneamente) obteniendo 6 ciclos de máquina para ejecutar el programa.
Tomando como base este ejemplo, la ejecución paralela de las instrucciones de un programa se mide mediante el parámetro conocido como Promedio de Ejecución Paralela de instrucciones (PEP). Este parámetro se define como la relación entre el número de instrucciones del programa y el número de ciclos de máquina realizados en su ejecución. Su expresión matemática es:
PEP = No. de Instrucciones / No. de Ciclos de Máquina
Por consiguiente, el promedio de ejecución paralela de instrucciones en software para este ejemplo es: 8/3 = 2,667 y el promedio de ejecución paralela de instrucciones en hardware es: 8/6 = 1,333.
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.
Las técnicas estáticas de planificación de instrucciones están compuestas por tres grupos: Planificación de instrucciones de bloques de un programa, Planificación de instrucciones de lazos iterativos continuos y planificación de instrucciones global. La técnica de bloques consiste en dividir un programa en bloques para luego detectar y resolver solamente las dependencias entre las instrucciones de cada bloque. Esta técnica es la mas utilizada en los últimos 20 años ya que es la más simple de implementar. La técnica de lazos iterativos consiste planificar las instrucciones que forman parte de los lazos continuos de un programa. Esta técnica esta compuesta básicamente por dos técnicas: Unrolling y Software Pipeline. Y por ultimo la técnica global consiste en planificar todas las instrucciones que forman parte de un programa.
SISTEMAS MULTIPROCESAMIENTO INTRODUCCION
A pesar de las grandes mejoras acaecidas en monoprocesadores para algunas aplicaciones no es suficiente.
– La solución pueden ser los sistemas multiprocesadores:
o Solución más sencilla, natural y con mejor coste-prestaciones.
o Las mejoras en microprocesadores cada vez son más complejas: cada avance implica crecer en complejidad, potencia y superficie.
o 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 si dentro de la misma placa base, esto sería un sistema multiprocesador.
CLASIFICACION POR USO DE LOS RECURSOS
Sistemas monoprogramados: Son los que solo 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: Son aquellos que se basan en las técnicas de multiprogramación, existen dos tipos:
Multitarea apropiativa (preemptive): Se utiliza en sistemas operativos cuya gestión es quitar el control del microprocesador al programa que lo tiene.
Multitarea cooperativa: El programa tiene el control del microprocesador, el sistema operativo no puede decidir quien usa el microprocesador.
Sistemas de multiprocesamiento: Formado por varios microprocesadores. 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): Cada programa realiza un conjunto de pasos secuenciales relacionados entre si
ORGANIZACIÓN DEL HARDWARE DEL MULTIPROCESADOR
El problema clave es determinar los medios de conexión de los procesadores múltiples y los procesadores de Entrada / Salida a las unidades de almacenamiento.
Los multiprocesadores se caracterizan por los siguientes aspectos:
• Un multiprocesador contiene dos o más procesadores con capacidades aproximadamente comparables.
• Todos los procesadores comparten el acceso a un almacenamiento común y a canales de Entrada / Salida, unidades de control y dispositivos.
• Todo está controlado por un Sistema Operativo que proporciona interacción entre procesadores y sus programas en los niveles de trabajo, tarea, paso, archivo y elementos de datos.
Las organizaciones más comunes son las siguientes:
• Tiempo compartido o bus común (conductor común).
• Matriz de barras cruzadas e interruptores.
• Almacenamiento de interconexión múltiple.
Tiempo Compartido o Bus Común (o Conductor Común)
Usa un solo camino de comunicación entre todas las unidades funcionales
El bus común es en esencia una unidad pasiva.
Un procesador o procesador de Entrada / Salida que desee transferir datos debe efectuar los siguientes pasos:
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.
Las unidades receptoras deben poder reconocer qué mensajes del bus son enviados hacia ellas y seguir y confirmar las señales de control recibidas de la unidad emisora.
Es una organización económica, simple y flexible pero con una sola vía de comunicación, por lo cual:
• 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.
Sistema Operativo de Multiprocesadores Las capacidades funcionales de los Sistema Operativo de multiprogramación y de multiprocesadores incluyen lo siguiente:
• 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 tres últimas son especialmente importantes en Sistemas Operativos de multiprocesadores, donde 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.
• Ejecutivo separado para cada procesador.
• Tratamiento simétrico (o anónimo) para todos los procesadores.
Maestro / Satélite - Es la organización más fácil de implementar.
No logra la utilización óptima del hardware dado que sólo el procesador maestro puede ejecutar el Sistema Operativo y el procesador satélite sólo puede ejecutar programas del usuario.
Las interrupciones generadas por los procesos en ejecución en los procesadores satélites que precisan atención del Sistema Operativo deben ser atendidas por el procesador maestro y por ello pueden generarse largas colas de requerimientos pendientes.
Ejecutivos Separados - Cada procesador tiene su propio Sistema Operativo y responde a interrupciones de los usuarios que operan en ese procesador.
Existen tablas de control con información global de todo el sistema (por ejemplo, lista de procesadores conocidos por el Sistema Operativo) a las que se debe acceder utilizando exclusión mutua.
Es más confiable que la organización maestro / satélite.
Cada procesador controla sus propios recursos dedicados.
La reconfiguración de los dispositivos de Entrada / Salida puede implicar el cambio de dispositivos a diferentes procesadores con distintos Sistemas Operativos.
La contención sobre las tablas del Sistema Operativo es mínima.
Los procesadores no cooperan en la ejecución de un proceso individual, que habrá sido asignado a uno de ellos.
Tratamiento Simétrico - Es la organización más complicada de implementar y también la más poderosa y confiable.
El Sistema Operativo 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 Sistema Operativo precisa código reentrarte y exclusión mutua.
Es posible equilibrar la carga de trabajo más precisamente que en las otras organizaciones.
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.
No hay comentarios:
Publicar un comentario