S.E.P D.G.E.S.T

S.N.E.S.T

INSTITUTO TECNOLGICO

Del Istmo

MATERIA: SISTEMAS OPERATIVOS 3 UNIDAD ADMINISTRACIN DEL PROCESO PRESENTAN: XUNASHI ORTIZ LPEZ SHEILA ROSADO RIVERA JAVIER DE LA CRUZ MARTINEZ NOEL JUAREZ RAMIREZ ELEAZAR JIMENEZ GARCIA ESPECIALIDAD: ING.SISTEMAS COMPUTACIONALES CATEDRATICO: ALEXANDRO ARAGN REYES VERA TERCER SEMESTRE GRUPO: X1

H.JUCHITAN DE ZARAGOZA, OAX. A 01 DE DICIEMBRE DEL 2011

INDICE INTRODUCCIN. .............................................................. 3 UNIDAD 3.- ADMINISTRACIN DEL PROCESADOR. 3.1.- Planeacin de trabajos (job scheduling).......7 3.2.- Conceptos bsicos.......9 3.3. - Tipos de Planeacin ........11 3.3.1. - First In First Out (FIFO)..............................11 3.3.2. - Round Robin (RR).....12 3.3.3. - Shortest Job First (SJF)....13 3.3.5. - Shortest Remaining Time (STR).14 3.3.6. - Highest Response Ratio Next (HNR).........15 3.4. - Multiprocesamiento..17 3.5. - Conceptos bsicos ..18 3.6. - Paralelismo.20 3.7.- Sistemas multiprocesamiento..25 3.8.- Organizacin del multiprocesador......27 3.9.- Sistemas operativos del multiprocesador..34 Conclusin37 Bibliografa382

INTRODUCCIN

El siguiente documento describe el tema de administracin del proceso. As como la planeacin de trabajo (Job Scheduling), sus conceptos bsicos, tambin hablaremos de los tipos de planeaciones que existen en una administracin del procesador tales estn el First In First (FIFO), Round Robn (RR), el Shortest Job First (SJF), Shortest Remaining Time (STR) y por ultimo el Highest Response Ratio Next (HNR). Un procesos pasa por una serie de estados discretos, que pueden ser ocasionados por varios eventos. Se dice que un procesos esta en estado de ejecucin si tiene asignado un procesador para si realizacin, otro estado es el listo en el que el procesador puede utilizar un procesador que este libre o disponible. Otro tema tambin que tocaremos en esta unidad es el multiprocesamiento en el cual conoceremos el concepto de multiprocesador que es como una computadora que contiene dos o ms unidades de procesamiento que trabajan sobre una memoria comn bajo un control integrados. Tambin hablaremos de sus conceptos bsicos de paralelismo, sistemas multiprocesamiento, organizacin del multiprocesador y los sistemas operativos del multiprocesador. Esperando que sea de su agrado.

3

UNIDAD 3: ADMINISTRACIN DEL PROCESADOR.Administracin del Procesador: se encarga de seleccionar el proceso en turno a ser ejecutado en el CPU. La planificacin del procesador determina cundo deben asignarse los procesadores a cules procesos. Se consideran tres niveles importantes de planificacin que son:

Planificacin de alto nivel o Planificacin de trabajos: Determina a qu trabajos se les va a permitir competir activamente por los recursos del sistema, lo cual se denomina Planificacin de admisin. Planificacin de nivel intermedio: Determina a que procesos se les puede permitir competir por la CPU. 4

Debe ayudar a alcanzar ciertas metas en el rendimiento total del sistema. Responde a fluctuaciones a corto plazo en la carga del sistema y efecta "suspensiones" y "activaciones" ("reanudaciones") de procesos.

Planificacin de bajo nivel: La efecta el Despachador del Sistema Operativo, el que opera muchas veces por segundo y reside siempre en el almacenamiento primario. Determina a qu proceso listo se le asigna la CPU cuando esta queda disponible y asigna la CPU al mismo, es decir que "despacha" la CPU al proceso.

Los objetivos de la planificacin del procesador son: Ser justa: todos los procesos son tratados de igual manera y ningn proceso es postergado indefinidamente. 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 utilizarn recursos infrautilizados. Equilibrar respuesta y utilizacin: La mejor manera de garantizar buenos tiempos de respuesta es disponer de los recursos suficientes cuando se necesitan, pero la utilizacin total de recursos podr ser pobre. Asegurar la prioridad: Los mecanismos de planificacin deben favorecer a los procesos con prioridades ms altas. 5

Dar mejor tratamiento a los procesos que muestren un "comportamiento deseable": Un ejemplo de comportamiento deseable es una tasa baja de paginacin. Degradarse suavemente con cargas pesadas: Un mecanismo de planificacin no debe colapsar con el peso de una exigente carga del sistema. Maximizar la capacidad de ejecucin: Maximizar el nmero de procesos servidos por unidad de tiempo. Maximizar el nmero de usuarios interactivos que reciban unos tiempos de respuesta aceptables: en un mximo de unos segundos.

Evitar la postergacin indefinida: 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. Se utiliza la estrategia del "envejecimiento". Dar preferencia a los procesos que mantienen recursos claves: Un proceso de baja prioridad podra mantener un recurso clave, que puede ser requerido por un proceso de ms alta prioridad. Si el recurso es no apropiativo, el mecanismo de planificacin debe otorgar al proceso un tratamiento mejor del que le correspondera normalmente, puesto que es necesario liberar rpidamente el recurso clave. Se debe evitar una carga excesiva mediante las siguientes acciones:

6

Dando servicio a la carga ms pesada al proporcionar un nivel moderadamente reducido de servicio a todos los procesos. No permitiendo que se creen nuevos procesos cuando la carga ya es pesada.

Las Disciplinas de Planificacin pueden ser: Apropiativa: Una vez que se le ha otorgado la CPU a un proceso, le puede ser retirada.

Caractersticas: Es til cuando los procesos de alta prioridad requieren atencin rpida. Es importante para garantizar buenos tiempos de respuesta en sistemas interactivos de tiempo compartido. Tiene su costo en recursos, ya que el intercambio de contexto implica sobrecarga y adems requiere mantener muchos procesos en el almacenamiento principal, en espera de la cpu, lo que tambin implica sobrecarga.

No apropiativa: Una vez que se le ha otorgado la CPU a un proceso, no le puede ser retirada. Caractersticas: Significa que los trabajos "largos" hacen esperar a los trabajos "cortos". Logra ms equidad en el tratamiento de los procesos.

7

Logra hacer ms predecibles los tiempos de respuesta puesto que los trabajos nuevos de prioridad alta no pueden desplazar a los trabajos en espera.

3.1 PLANEACIN DE TRABAJOS (JOBSCHEDULING)La CPU debe escoger algn proceso cuando hay ms de un proceso en condiciones de ejecutarse. El encargado de tomar esa decisin es el planificador o scheduler, y el algoritmo que usa se llama algoritmo de planificacin. (Scheduler = planificacin). Objetivo de la planificacin: Minimizar el tiempo de espera y minimizar el tiempo de respuesta. La planificacin (scheduling) es la base para lograr la multiprogramacin. Un sistema multiprogramado tendr varios procesos que requerirn el recurso procesador a la vez. Esto sucede cuando los procesos estn en estado ready (pronto). Si existe un procesador disponible, se debe elegir el proceso que ser asignado para ejecutar. EL planificador (Schedule) es la parte del sistema operativo que realiza la eleccin. La planificacin hace referencia a un conjunto de polticas Y mecanismos incorporados a sistemas operativos que gobiernan el orden en que se ejecutan los trabajos. Un planificador es un mdulo 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 planificacin se divide en tres funciones independientes: planificacin a largo, medio, y corto plazo. En la planificacin, se trata de obtener un plan, y por otra parte delimitar la ejecucion de las acciones en el tiempo, asignndoles los recursos necesarios y teniendo en cuenta las restricciones generales del problema.

8

Los mtodos para solucionar problemas de planificacin y scheduling se dividen en dos etapas diferentes. Sin embargo, la resolucin de estos problemas no es abordable mediante estos procesos por separados. La idea principal es la integracin de ambos. Cundo hay que planificar? Una decisin de planificacin puede o debe tomarse cuando ocurre cualquiera de las siguientes transiciones entre estados de un proceso: EJECUTANDO a BLOQUEADO. EJECUTANDO a TERMINADO. EJECUTANDO a LISTO. BLOQUEADO a LISTO. En los casos 1 y 2, necesariamente hay que escoger un nuevo proceso, pero en los casos 3 y 4 podra no tomarse ninguna decisin de scheduling, y dejar que contine ejecutando el mismo proceso que estaba ejecutando. En ese caso, se habla de planificacin no-expropiadora. Si en cambio se toma una decisin de scheduling en los casos 3 y 4, entonces se habla de planificacin expropiadora. Esta ltima es ms segura y ms justa, pero tiene un problema: consideremos dos procesos que comparten informacin, y que a uno de ellos se le quita la CPU justo cuando estaba en medio de una actualizacin de los datos compartidos. Cuando sea el turno del segundo proceso, ste podra intentar leer los datos cuando estn en un estado inconsistente. Este problema se remedia con sincronizacin.

Posibles objetivos del algoritmo de planificacin son: Justicia: Asegurarse que todos los procesos tengan su turno de CPU. Eficiencia: Mantener todo el tiempo ocupada ala CPU. Tiempo de respuesta: Minimizar el tiempo de respuesta de los usuarios interactivos.

9

Rendimiento o productividad (throughput): Maximizar el nmero de trabajos terminados por hora. Tiempo de espera: Minimizar el tiempo medio de espera (en la cola READY) de los procesos. Una complicacin adicional que hay que tener presente es que cada proceso es nico e impredecible. Algunos son procesos limitados por I/O, es decir, pierden la mayor parte del tiempo esperando por I/O; otros son procesos limitados por CPU, es decir, requieren principalmente tiempo de CPU. En cualquier caso, todos los procesos alternan entre una fase de ejecucin de CPU y otra de espera por I/O. Aunque la duracin de las fases de CPU es impredecible y vara mucho entre un proceso y otro, tiende a tener una frecuencia.

3.2 CONCEPTOS BSICOS.Un planificador de tareas: es una aplicacin de software de la empresa que se encarga de la ejecucin desatendida fondo, comnmente conocido por razones histricas como del procesamiento por lotes. Un procesamiento de lotes: es la ejecucin de una serie de programas. Hoy en da el trabajo de los programadores suelen ofrecer una interfaz grfica de usuario y un nico punto de control para la definicin y el seguimiento de las ejecuciones en el fondo de una red distribuida de computadoras.

Existen dos arquitecturas principales para el software de planificacin de trabajo, los cuales son: Maestro / Agente de la arquitectura: El software Job Scheduling se instala en una sola mquina (Master), mientras que en equipos de produccin slo un componente muy pequeo (agente) est instalado que le espera a las

10

rdenes del Maestro, los ejecuta, y devuelve el cdigo de salida de nuevo al Maestro. Arquitectura Cooperativa: Esto permite equilibrar la carga de trabajo dinmico para maximizar la utilizacin de los recursos de hardware y de alta disponibilidad para garantizar la prestacin de servicios. Es necesario tomar en cuenta que para realizar cualquier actividad se necesita obtener una utilizacin mxima de la CPU, lo cual se obtiene va multiprogramacin. Un ciclo rfagas CPUI/O es la ejecucin de un proceso, consiste de un ciclo de ejecucin de CPU continuado por un ciclo de espera por I/O. Distribucin de rfagas de CPU. Job: Es una tarea de base de datos definida en trminos de una secuencia vlida de comandos Transact-SQL. Schedule: es un horario de ejecucin, definido en trminos de atributos particulares, como fecha y hora de inicio, periodicidad, fecha y hora de finalizacin, etc. Scheduled Job: es un Job que ha sido asociado a un schedule y que, en consecuencia, se ejecutar automticamente de acuerdo a lo definido en dicho schedule. La ejecucin 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 ejecucin de los scheduled jobs a travs 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 informacin del sistema del Job Scheduler. JS Task: Es una tarea interna que corre en el ASE denominado JS Server, se encarga de determinar qu scheduled jobs deben ser ejecutados en cada momento del tiempo. Cuando una tarea JS Task determina que una scheduled job 11

debe ser ejecutado, pasa la informacin al JS Agent, quien inicia la ejecucin en el ASE denominado Target Server. JS Agent: Es un proceso del sistema operativo que corre en la misma mquina del JS Server. El JS Agent es el encargado de controlar la ejecucin de los scheduled jobs en el Target Server, de acuerdo a la informacin recibida por los JS Task.

3.3 TIPOS DE PLANEACION JOB SCHEDULING3.3.1 FIRST IN FIRST OUT JOB SCHEDULING (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 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 ejecucin, 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 recin llegado.

Es del tipo no expropiativo Es equitativo Solo necesita una cola para implementarse Presenta desventajas cuando se tienen procesos dedicados a CPU y a E/S.

3.3.2.- ROUND ROBIN (RR) 12

Es un mtodo que selecciona todos los elementos en un grupo de manera equitativa y en un orden racional, normalmente comenzando por el primer elemento de la lista hasta llegar al ltimo y empezando de nuevo desde el primer elemento. El planeamiento Round Robin es simple y fcil de implementar, tambien esta libre de inanicin. Una forma sencilla de entender el Round Robin es imaginar una secuencia para tomar turnos. En operaciones computacionales, un mtodo para ejecutar diferentes procesos de manera concurrente para la utilizacin equitativa de los recursos del equipo, es limitando cada proceso a un pequeo periodo de tiempo, y luego suspendiendo ste proceso para dar oportunidad a otro proceso y as sucesivamente. A esto se le denomina comnmente como Planificacin Round-Robin. Los procesos se despachan en FIFO y disponen de una cantidad limitada de tiempo de cpu, llamada divisin de tiempo o cunto. 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 apropiacin se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos. Caractersticas: Fcil 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 inanicin. 13

El valor mnimo del quantum debe ser 10 * Tiempo Cambio Contexto. El quantum ms adecuado es el Tiempo de CPU del proceso ms corto.

3.3.3.- SHORTEST JOB FIRST (SJF) O PRIORIDAD DE TRABAJO MAS CORTO Primero el proceso ms cort Es una disciplina no apropiativa y no recomendable en ambientes de tiempo compartido. El proceso en espera con el menor tiempo estimado de ejecucin hasta su terminacin es el siguiente en ejecutarse. Los tiempos de espera son menos predecibles que en FIFO. Favorece a los procesos cortos en detrimento de los largos. Tiende a reducir el nmero de procesos en espera y el nmero de procesos que esperan detrs de procesos largos. Requiere un conocimiento preciso del tiempo de ejecucin 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 (STR) O TIEMPO RESTANTE MAS CORTO. 14

Elige al proceso que le queda menos tiempo de ejecucin estimado para completar su ejecucin; de esta forma aunque un proceso requiera mucho tiempo de ejecucin, a medida que se va ejecutando ira avanzando en la lista de procesos en estado listo hasta llegar a ser el primero. Para realizar esta eleccin, es necesario actualizar el PCB de los procesos a medida que se le asigna tiempo de servicio, lo que supone una mayor sobrecarga adicional. Este algoritmo es la versin no apropiativa o espulsiva del algoritmo ShortestProcessNext (SPN) o tambin llamado Shortest Job First (SJF). En el algoritmo ShortestRemaining Time el planificador selecciona el proceso ms 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 rfaga es menor que el tiempo de rfaga 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 rfaga. Si el proceso que se est ejecutando le queda ms tiempo de rfaga que nuestro tiempo de rfaga calculado entonces se procede a realizar el cambio de contexto. Definicin: Algoritmo apropiativo (que en cualquier momento se le puede quitar la CPU para asignrsela 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.

Caractersticas: 15

Ofrece un buen tiempo de respuesta. La productividad es alta a cambio de la sobrecarga del sistema (a cada paso debe decidir a qu proceso asignarle la CPU). Penaliza los procesos largos. Se puede producir inanicin.

3.3.5 HIGHEST RESPONSE RATIO NEXT JOB SCHEDULING (HNR) Primero el de mayor tasa de respuesta Algoritmo apropiativo parecido al SRT consistente en calcular el Reponse Ratio (Ratio de respuesta) para asignar la CPU a procesos ms viejos. (Para evitar la inanicin). Para cada proceso individual, se desea minimizar esta razn, as como minimizar el valor medio de todos los procesos. Aunque sta es una medida a posteriori, es posible aproximarla a una medida a priori, como el criterio de seleccin de un planificador no apropiativo. En concreto, considrese la siguiente tasa de respuesta (RR, Response Ratio): RR=_w+s_ s Donde: R= tasa de respuesta w= tiempo consumido esperando al procesador 16

s= tiempo de servicio esperado Si el proceso con este valor se expide inmediatamente, R es igual al tiempo de retorno normalizado. Ntese que el valor mnimo de RR es 1,0, alcanzado cuando un proceso entra por primera vez en el sistema. Hasta ahora, la regla de planificacin ha sido: Cuando el proceso actual termina o se bloquea, se elige el proceso listo con un valor mayor de RR. Este mtodo es atractivo porque tiene en cuenta la edad del proceso. Aunque se favorece a los trabajos ms cortos (un denominador menor produce una razn mayor), el envejecimiento sin que haya servicio incrementa el valor de la razn, de forma que los procesos ms largos pasen finalmente primero, en competicin con los ms cortos.El tiempo esperado de servicio debe estimarse antes de emplear la tcnica de la mayor tasa de respuesta (HRRN, Highest Response Ratio Next), como ya ocurra con SRT y SPN.

17

3.4 MULTIPROCESAMIENTOSe define como una computadora que contiene dos o ms unidades de procesamiento que trabajan sobre una memoria comn bajo un control integrado. Si el sistema de multiprocesamiento posee procesadores de aproximadamente igual capacidad, estamos en presencia de multiprocesamiento simtrico; en el otro caso hablamos de multiprocesamiento asimtrico. Si un procesador falla, los restantes continan operando, lo cual no es automtico y requiere de un diseo cuidadoso. Un procesador que falla habr de informarlo a los dems de alguna manera, para que se hagan cargo de su trabajo. Los procesadores en funcionamiento deben detectar el fallo de un procesador. Determinado. El sistema operativo debe percibir que ha fallado un procesador determinado y ya podr asignarlo y tambin debe ajustar sus estrategias de asignacin de recursos para evitar la sobrecarga del sistema que esta degradado. Tipos de multiprocesamiento Simtrico: Se trata de un tipo de arquitectura de ordenadores en que dos o ms procesadores comparten una nica memoria central. Todos los microprocesadores compiten en igualdad de condiciones por dicho acceso, de ah la denominacin "simtrico" Ventaja: Este tipo de sistema tiende a ser ms eficientes por que las tareas tanto del sistema operativo como de los usuarios pueden ser distribuidas en forma balanceada a todos los procesadores Desventaja: Es que el haber solo una copia del sistema operativo en un solo procesador (maestro) cuando este procesador falla todo el sistema falla porque todos los recursos que son manejados por el sistema operativo no pueden ser accesado. 18

Asimtrico: Hay un procesador (maestro) en el cual se ejecuta el sistema operativo y dems (esclavo) donde se ejecutan las dems tareas Ventaja: Es que al aumentar ms procesadores se tiene que hacer un cambio mnimo y fcil para el manejo de estos y en general se eliminan muchos problemas de integridad de datos.

3.5 CONCEPTOS BSICOSDos factores clave para la extensin de los Multiprocesadores

19

1. Flexibilidad: El mismo sistema puede usarse para un nico usuario incrementado el rendimiento en la ejecucin de una nica aplicacin 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 drsticamente. La inversin ms fuerte se hace en la memoria y la red de interconexin. Como su nombre indica son aquellos sistemas operativos que estn montados sobre ordenadores que estn compuestos por ms de un procesador, supongamos un PC que en vez de tener un Pentium, tuviera dos o ms Pentium conectados entre si dentro de la misma placa base, esto sera un sistema multiprocesador. CLASIFICACION POR USO DE LOS RECURSOS Sistemas monoprogramados: Son los que solo permiten la ejecucin de un programa en el sistema, se instalan en la memoria y permanecen all hasta que termine su ejecucin. Sistemas multiprogramados: Son aquellos que se basan en las tcnicas de multiprogramacin, existen dos tipos:

Multitarea apropiativa (preemptive): Se utiliza en sistemas operativos cuya gestin 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. 20

Multiprocesamiento Medios de multiprocesamiento que tienen ms de un procesador que opera en la misma memoria pero ejecuta procesos simultneamente. En un sistema de multiprocesamiento procesadores mltiples son empleados a ejecutado ms de una actividad en el tiempo, siempre que la informtica masiva deba ser realizada con regularidad.

3.6 PARALELISMOOrganizaciones con varios procesadores El paralelismo es una forma de computacin en la cual varios clculos pueden realizarse simultneamente, basado en el principio de dividir los problemas grandes para obtener varios problemas pequeos, que son posteriormente solucionados en paralelo. Hay varios tipos diferentes de paralelismo: nivel de bit, nivel de instruccin, de datos y de tarea. El paralelismo ha sido empleado durante muchos aos, sobre todo para la Computacin de alto rendimiento. Paralelismo: Consiste en romper con la ejecucin secuencial de las instrucciones para simultanear su ejecucin. Hay distintas formas de explotar el paralelismo: Segmentacin Superescalaridad Segmentacin y superescalaridad Supersegmentacin Aplicaciones: Como la computacin paralela se convierte cada da en ms grande y rpida, muchos problemas considerados anteriormente muy largos y costosos se han podido solucionar. El paralelismo se ha utilizado para muchas temticas diferentes, desde bioinformtica (para hacer plegamiento de protenas) hasta economa (para hacer simulaciones en matemtica financiera).

21

Los problemas tpicos encontrados en el paralelismo son:

Simulacin de Montecarlo lgica combinacional (como las tcnicas de fuerza bruta) Graph traversal Programacin dinmica Mtodos de ramificacin y poda Modelo en grafo Simulacin de autmata finito

Arquitectura de Computadores: Paralelismo Paralelismo: o procesamiento paralelo es una forma eficaz de explotar los sucesos concurrentes en el proceso de computacin. Sucesos paralelos: pueden darse en dif. recursos durante el mismo intervalo de tiempo. Sucesos simultaneos: aquellos que se producen en el mismo instante de tiempo. Sucesos solapados: los que se producen en intervalos de tiempo superpuestos Granularidad: tamao de tarea computable Planificacin: asignacin de recursos a las tareas Comunicacin: sincronizacin de tareas dependientes. Paralelismo de grano grueso: programa o trabajo y modulo proceso (menos paralelismo) Paralelismo de grano medio: modulo proceso y task Paralelismo de grano fino: bucle e Instruccion sentencia (ms paralelismo) Paralelismo a nivel de procesador: segmentacin, divisin funcional, procesadores vectoriales Paralelismo en multiprocesadores: memoria compartida, memoria distribuida Paralelismo en multicomputadores: clster, sistemas distribuidos Clasificacin de sistemas paralelos: 22

-Flujo de control: las instrucciones se van ejecutando segn el orden en el que se encuentran en memoria -Flujo de datos: el flujo de ejecucin es conducido por los datos; una instruccin ser ejecutada cuando los operandos estn disponibles. Son una clase de las de flujo de datos: SISD: arquitectura de simple construccin sobre simple dato. Serie en datos e instrucciones, arquitectura von neumann.

SIMD: un solo flujo de instrucciones y mltiples en datos. Computadores matriciales. Una unidad de control que gobierna varias unidades aritmeticologicas. MISD: varios flujos de instrucciones y uno solo de datos. Arquitectura no implementada, consecuencia terica de la clasificacin. Superestructura pipeline, varios conjuntos de unidad de control ms unidad aritmtico lgica realizan partes de una operacin sobre un flujo de datos. MIMD: arquitectura multiprocesador con varios flujos tanto de instrucciones como de datos. Varios procesadores serie convencionales que manejan cada uno un flujo de instrucciones sobre un flujo de datos.. -Reduccin: la ejecucin se realiza por demanda: una instruccin ser ejecutada cuando otra necesite sus resultados. Tipos de paralelismo: Interno o implcito. Se programa en lenguaje secuencial y el compilador se encarga de paralelizar y asignar recursos. Queda oculta la arquitectura del comput, aumentando su velocidad sin modificar su funcionamiento. Bajo aprovechamiento, aprovecha cdigo secuencial. Externo o explcito: se usan dialectos paralelos de programacin. Queda visible al usuario. Mejor aprovechamiento a las posibilidades de la maquina, ms trabajo para el programador, SIMD (computadores matriciales), MISD, MIMD. 23

Paralelismo segn SW: Depende del entorno de programacin en dos facetas: herramientas de programacin, S.O MPMD (multiple program-multiple data): cada procesador ejecuta programas distintos. Esta estructura suele ser del tipo maestro esclavo en la que un procesador coordina el trabajo al resto SPMD(single program-multiple data): el mismo programa es cargado en multiples procesadores y se ejecuta sobre conjuntos de datos distintos Segmentacin: encauzamiento o pipeline es una tcnica para explotar concurrencia en sistemas monoprocesador. Consiste en dividir una funcion en subfunciones independientes que pueden realizarse de manera concurrente(solapados) En un instante de tiempo determinado se esta trabajando a la vez sobre un numero de elementos igual al numero de etapas. Es una estructura segmentada si cada unidad independiente procesa una subfuncion en un periodo T/n, en el tiempo T se habrn podido procesar n funciones La segmentacin se puede aplicar a cualquier p compleja concretamente en la unidad de control y en la ALU cauce de procesamiento: cuantas subfuciones o elementos de procesamiento se estn procesando a la vez. Condiciones que permiten segmentar una funcin: debe admitir su descomposicion en etapas. Es necesario que las entradas de una etapa estn determinadas unicamente por la salida de la anterior. Cada etapa debe poder ser realizada por un circuito especfico de forma ms rpida que el conjunto de proceso.

24

Organizaciones paralelas La Figura 16.2 muestra los esquemas generales de las clases de la taxonoma de la Figura 16.1. La Figura 16.2a corresponde a la estructura de un SISD. Se dispone de una unidad de control (UC) que proporciona una secuencia de instrucciones (SI) a una unidad de proceso (UP). La unidad de proceso acta sobre una nica secuencia de datos (SD) captados desde la unidad de memoria (UM). En una maquina SIMD, tambin existe una sola unidad de control, que proporciona una nica secuencia de instrucciones a cada elemento de proceso. Cada elemento de proceso puede tener su propia memoria dedicada (mostrada en la Figura 16.2b), o puede haber una memoria compartida. Finalmente, en un computador MIMD hay mltiples unidades de control, y cada una proporciona una secuencia de instrucciones separada a su propio elemento de proceso. El MIMD puede ser un multiprocesador de memoria compartida (Figura 16.2c), o un multicomputador de memoria distribuida (Figura 16.2d). Los aspectos de diseo relacionados con los SMP, los clusters, y los NUMA, son complejos, implicando cuestiones relativas a la organizacin fsica, las estructuras de interconexin, el diseo de los sistemas operativos, y el software de las aplicaciones. Nuestro inters se centra fundamentalmente

25

en la organizacin, aunque se describirn brevemente aspectos del diseo de los sistemas operativos.

3.7 SISTEMAS MULTIPROCESAMIENTOUn sistema operativo multiproceso o multitarea es aquel que permite ejecutar varios procesos de forma concurrente, la razn es porque actualmente nuestras CPUs slo pueden ejecutar un proceso cada vez. La nica forma de que se ejecuten de forma simultnea varios procesos es tener varias CPUs (ya sea en una mquina o en varias, en un sistema distribuido). Multiprocesadores Simtricos Los fabricantes han introducido los sistemas SMP. El termino SMP se refiere a la arquitectura hardware del computador, y tambin al comportamiento del sistema operativo que utiliza dicha arquitectura. Un SMP puede definirse como un computador con las siguientes caractersticas: 26

1.

Hay dos o ms procesadores similares de capacidades

comparables. 2. Estos procesadores comparten la memoria principal y las E/S, y

estn interconectados mediante un bus u otro tipo de sistema de interconexin, de forma que el tiempo de acceso a memoria es aproximadamente el mismo para todos los procesadores. 3. Todos los procesadores comparten los dispositivos de E/S, bien a

travs de los mismos canales, o bien mediante canales distintos que proporcionan caminos de acceso al mismo dispositivo. 4. Todos los procesadores pueden desempear las mismas funciones

(de ah el trmino simtrico). 5. El sistema est controlado por un sistema operativo integrado,

que proporciona la interaccin entre los procesadores y sus programas en los niveles de trabajo, tarea, fichero, y datos.

El punto 5 corresponde a una de las diferencias con los sistemas multiprocesador dbilmente acoplados, tales como los clusters. En estos, la unidad de interaccin fsica es normalmente un mensaje o un fichero completo. En un SMP, la interaccin se puede producir a travs de elementos de datos individuales, y puede existir un elevado nivel de cooperacin entre procesadores.

27

Un SMP tiene las siguientes ventajas potenciales con respecto a una arquitectura monoprocesador: Prestaciones: Si el trabajo a realizar por un computador puede organizarse de forma que partes del mismo se puedan realizar en paralelo, entonces un sistema con varios procesadores proporcionara mejores prestaciones que uno con un solo procesador del mismo tipo. Disponibilidad: En un multiprocesador simtrico, debido a que todos los procesadores pueden realizar las mismas funciones, un fallo en un procesador no har que el computador se detenga. Crecimiento incremental: Se pueden aumentar las prestaciones del

sistema, aadiendo ms procesadores. Escalado: Los fabricantes pueden ofrecer una gama de productos

con precios y prestaciones diferentes, en funcin del nmero de procesadores que configuran el sistema. Es importante resaltar que los anteriores son beneficios potenciales, ms que beneficios garantizados. El sistema operativo debe disponer de herramientas y funciones que permitan explotar el paralelismo presente en un SMP.

28

Una caracterstica atractiva de un SMP es que la existencia de varios procesadores es transparente al usuario. El sistema operativo se encarga de la sincronizacin entre los procesadores, y de la planificacin de los hilos o de los procesos, asignndolos a los distintos procesadores.

3.8 ORGANIZACIN DEL MULTIPROCESADOR

El problema clave es determinar los medios de conexin de los procesadores mltiples y los procesadores de Entrada / Salida a las unidades de almacenamiento Los multiprocesadores se caracterizan por los siguientes aspectos:

Un multiprocesador contiene dos o ms procesadores con capacidades aproximadamente comparables. Todos los procesadores comparten el acceso a un almacenamiento comn y a canales de Entrada / Salida, unidades de control y dispositivos. Todo est controlado por un Sistema Operativo que proporciona interaccin entre procesadores y sus programas en los niveles de trabajo, tarea, paso, archivo y elementos de datos.

Las organizaciones ms comunes son las siguientes:

Tiempo compartido o bus comn (conductor comn). Matriz de barras cruzadas e interruptores. Almacenamiento de interconexin mltiple.

Tiempo Compartido o Bus Comn (o Conductor Comn) Usa un solo camino de comunicacin entre todas las unidades funcionales (figura 3). 29

El bus comn es en esencia una unidad pasiva. Pasos para que un procesador o procesador de Entrada / Salida que desee transferir datos: 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 seales de control recibidas de la unidad emisora. Es una organizacin econmica, simple y flexible pero con una sola va de comunicacin, por lo cual:

El sistema falla totalmente si falla el bus. La tasa neta de transmisiones est limitada por la tasa neta de transmisin del conductor. La contencin por el uso del bus en un sistema sobrecargado puede ocasionar una seria degradacin.

Matriz de Barras Cruzadas e Interruptores. En este caso existe un camino diferente para cada unidad de almacenamiento, por lo cual las referencias a dos unidades diferentes de almacenamiento no son 30

bloqueantes sino simultneas y la multiplicidad de caminos de transmisin puede proporcionar tasas de transferencia muy altas

Almacenamiento de Interconexin Mltiple. Se obtiene al sacar las lgicas de control, de conmutacin y de arbitraje de prioridades fuera del interruptor de barras cruzadas y se las coloca en la interfaz de cada unidad de almacenamiento

Cada unidad funcional puede acceder a cada unidad de almacenamiento, pero slo en una conexin de almacenamiento especfica, es decir que hay una conexin de almacenamiento por unidad funcional. El conexionado es ms complejo que en los otros esquemas.

31

Se puede restringir el acceso a las unidades de almacenamiento para que no todas las unidades de procesamiento las accedan, en tal caso habr unidades de almacenamiento privadas de determinados procesadores

Multiprocesamiento Simtrico (MPS) Cada procesador posee capacidades funcionales completas. Los dispositivos de Entrada / Salida pueden ser conectados a cada uno de los procesadores

32

Todas las llamadas al supervisor pueden ser ejecutadas en todos los procesadores, inclusive las de Entrada / Salida. Si un programa en ejecucin en un procesador pide una operacin de Entrada / Salida en un dispositivo conectado a un procesador diferente, el procesador puede continuar ejecutando el trabajo y la Entrada / Salida se coloca en una cola para su iniciacin por el procesador apropiado. Se considera procesador ejecutante al que est ejecutando un proceso determinado. Se considera procesador propietario al que est conectado a los diferentes dispositivos utilizados por el proceso. Es ms eficiente que la organizacin maestro / satlite, ya que los requerimientos de Entrada / Salida se encolan y no sobrecargan con intercambio de contexto y a que en la organizacin maestro / satlite las peticiones de Entrada / Salida en el satlite provocan un intercambio de contexto en el maestro. 33

Cada procesador puede ejecutar el planificador para buscar el siguiente trabajo a ejecutar, de forma que un proceso determinado se ejecuta en diferentes procesadores en distintos momentos; adems, el MPS utiliza una sola cola de trabajos y cada procesador puede seleccionar trabajos de ella, con lo cual se equilibra la carga entre los procesadores. Para minimizar la contencin en el despacho de procesos, los relojes de los procesadores tienen oblicuidad, debido a ello las interrupciones de reloj ocurren en diferentes momentos. Tendencias de los Multiprocesadores. Todo indica que el uso de los multiprocesadores se incrementar

considerablemente en el futuro Las principales razones son las siguientes:

La confiabilidad requerida es cada vez mayor. La reduccin de costos consecuencia de los avances en microelectrnica. El previsible desarrollo de lenguajes que permitan a los usuarios expresar el paralelismo explcitamente. El progreso en la deteccin automtica del paralelismo . El hecho de que se estara llegando a los lmites del uniprocesador debido a la compactacin de componentes, es decir que se estara prximo a los lmites de longitud y de proximidad de los caminos electromagnticos (longitud del recorrido de la seal electromagntica); alcanzados los lmites mencionados, la nica posibilidad de incrementar capacidad de cmputo es mediante multiprocesamiento.

Existen estudios de tendencias en arquitectura de computadoras que apuntan a los poliprocesadores, es decir, sistemas que combinan el multiprocesamiento, simtrico y asimtrico, para crear una jerarqua de procesadores dentro de un sistema. 34

Grados de Acoplamiento en Multiprocesamiento Los grados de acoplamiento en multiprocesamiento pueden clasificarse de ligeramente acoplados ver Figura o rgidamente acoplados ver Figura, segn las caractersticas que se detallan en la Tabla. Grados acoplamiento de Descripcin en Incluye la conexin de dos o ms sistemas independientes por medio de un enlace de comunicacin. Cada sistema tiene su propio Sistema Operativo y almacenamiento. Los sistemas pueden funcionar independientemente y se comunican cuando sea necesario. Los sistemas separados pueden acceder a los archivos de los otros e intercambiar tareas a procesadores menos Rgidamente acoplado cargados. Utiliza un solo almacenamiento compartido por varios procesadores. Emplea un solo Sistema Operativo que controla todos los procesadores y el hardware del sistema. Tabla: Grados de acoplamiento en multiprocesamiento.

multiprocesamiento Ligeramente acoplado

35

3.9 SISTEMA OPERATIVO DE MULTIPROCESADORLas capacidades funcionales de los Sistema Operativo de multiprogramacin y de multiprocesadores incluyen lo siguiente:

Asignacin y administracin de recursos. Proteccin de tablas y conjuntos de datos. Prevencin contra el interbloqueo del sistema. Terminacin anormal. Equilibrio de cargas de Entrada / Salida. Equilibrio de carga del procesador. Reconfiguracin.

36

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 automticamente.

Las organizaciones bsicas de los Sistemas Operativos para multiprocesadores son las siguientes:

Maestro / satlite. Ejecutivo separado para cada procesador. Tratamiento simtrico (o annimo) para todos los procesadores.

Maestro / Satlite Es la organizacin ms fcil de implementar. No logra la utilizacin ptima del hardware dado que slo el procesador maestro puede ejecutar el Sistema Operativo y el procesador satlite slo puede ejecutar programas del usuario. Las interrupciones generadas por los procesos en ejecucin en los procesadores satlites que precisan atencin 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 informacin global de todo el sistema (por ejemplo, lista de procesadores conocidos por el Sistema Operativo) a las que se debe acceder utilizando exclusin mutua. 37

Es ms confiable que la organizacin maestro / satlite. Cada procesador controla sus propios recursos dedicados. La reconfiguracin de los dispositivos de Entrada / Salida puede implicar el cambio de dispositivos a diferentes procesadores con distintos Sistemas Operativos. La contencin sobre las tablas del Sistema Operativo es mnima. Los procesadores no cooperan en la ejecucin de un proceso individual, que habr sido asignado a uno de ellos. Tratamiento Simtrico Es la organizacin ms complicada de implementar y tambin la ms poderosa y confiable. El Sistema Operativo administra un grupo de procesadores idnticos, donde cualquiera puede utilizar cualquier dispositivo de Entrada / Salida y cualquiera puede referenciar a cualquier unidad de almacenamiento. El Sistema Operativo precisa cdigo reentrante y exclusin mutua. Es posible equilibrar la carga de trabajo ms precisamente que en las otras organizaciones. Adquieren significativa importancia el hardware y el software para resolucin de conflictos. Todos los procesadores pueden cooperar en la ejecucin de un proceso determinado. El procesador ejecutivo es el responsable (uno slo) en un momento dado de las tablas y funciones del sistema; as se evitan los conflictos sobre la informacin global. 38

CONCLUSINTodos los temas que se han visto en esta unidad, pues podemos concluir que pudimos comprender, entender y ms que nada sacarnos de dudas de algunos conceptos que quizs no conocamos. De tal manera pes este es un tema amplio en donde comprendimos los conceptos bsicos de planeacin de trabajo( job scheduling), tambin que tiene muchos tipos de planeacin que son varias, el multiprocesamiento, asi como su conceptos bsicos, el paralelismo es una forma de computacin en la cual varios clculos pueden realizarse simultneamente , basado en el principio de dividir los problemas grandes para obtener varios problemas pequeos, que son posteriormente solucionados en paralelo. Hay varios tipos diferentes de paralelismo: nivel de bit, nivel de instruccin, de datos y de tarea. El paralelismo ha sido empleado durante muchos aos, sobre todo para la Computacin de alto rendimiento., sistemas multiprocesamiento, organizacin del multiprocesador y los sistemas operativos del multiprocesador.

39

BIBLIOGRAFIAhttp://www.itistmo.edu.mx/desarrollo%20dl%20proyecto/unidad2.htm http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO2.htm http://www.agendistas.com/computadoras/administracion-procesador.html http://www.mitecnologico.com/Main/OrganizacionDelMultiprocesador http://epsc.upc.edu/projectes/usuaris/miguel.valero/materiales/docencia/doctorado/ introduccion.pdf www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r2961.DOC http://251m01so.blogspot.com/2009/11/38-organizacion-del-multiprocesador.html http://jvargasi2011.blogspot.com/2011/04/portafolio-de-sistemas-operativos.html http://252m4so.blogspot.com/2009/11/32-conceptos-basicos-job-scheduling.html http://252m5so.blogspot.com/2009/11/32-conceptos-basicos-job-scheduling.html http://tesciequipo7.blogspot.com/2009/11/32-conceptos-basicos.html www.wikipedia.com

40