Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmos de Asignación de Procesadores

Sistemas Operativos II
by

Estefania Saldaña

on 12 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmos de Asignación de Procesadores

Sistemas Operativos II Algoritmos de Asignacion de Procesadores Un Sistema Distribuido consta de varios procesadores. Éstos se pueden organizar pero se necesita cierto algoritmo para decidir cuál proceso hay que ejecutar y en qué máquina. Asignación de procesadores Aplicable a sistemas donde se conoce :
* Requerimientos de CPU y de memoria de los procesos.
* Tráfico promedio entre cada par de procesos.

Si el número de procesos supera al número de CPU:
** Habrá que asignar varios procesos a la misma CPU.
** La asignación deberá minimizar el tráfico en la red.

El sistema se puede representar en una gráfica con pesos:
*** Cada nodo es un proceso.
*** Cada arco es el flujo de mensajes entre dos procesos. Un Algoritmo Determinista Según la Teoría de Gráficas Es un coordinador mantiene una tabla de usos:

++ Contiene una entrada por estación de trabajo inicializada en “0”.

++ Cuando ocurren eventos se envían al coordinador mensajes para actualizar la tabla.

++ Se realiza una solicitud, se libera un procesador, el reloj produce una marca de tiempo. Un Algoritmo Centralizado Integrantes:

-Cedillo Mujica Yudit Alexandra
-Flores Uribe Deborha Elizabeth
-García Hernández Juana Maria Guadalupe
-Rincon Juarez Klaudia Marizol
-Saldaña Ibarra Estefania Elizabeth Son preferibles los algoritmos descentralizados, pero se han propuesto algunos algoritmos centralizados por la carencia de alternativas descentralizadas adecuadas centralizados vs distribuidos Los deterministas:
Son adecuados cuando se sabe todo acerca del comportamiento de los procesos, así uno podría intentar todas las posibles asignaciones y tomar la mejor. Algoritmos deterministas vs heurísticos. - Deterministas vs heurísticos.
- Centralizados vs distribuidos.
- Óptimos vs subóptimos.
- Locales vs globales.
- Iniciados por el emisor vs iniciados por el receptor. Las decisiones que deben tomar los diseñadores son los Algoritmos: Se pueden obtener las soluciones óptimas en los dos sistemas, pero por regla son más caros que los subóptimos. Hay que recolectar más información y procesarla un poco más.


La mayoría de los sistemas distribuidos reales buscan soluciones subóptimas, heurísticas y distribuidas, debido a la dificultad para obtener las óptimas. Óptimos vs subóptimos. Cuando se está a punto de crear un proceso, hay que tomar una decisión para ver si se ejecuta o no en la máquina que lo genera.

La opción en este aspecto consiste en basar o no las decisión de transferencia por completo en la información local. locales vs globales.
Una vez que la política de transferencia (de localización) ha decidido deshacerse de un proceso, la política de localización debe decidir dónde enviarlo.

Necesita información de la carga en todas partes para tomar una decisión inteligente. Sin embargo, esta información se puede dispersar de dos maneras:

--Los emisores inician el intercambio de información.
--En el otro, el receptor toma la iniciativa Iniciados por el emisor vs iniciados por el receptor Los heurísticos:
Están los sistemas donde la carga es por completo impredecible. Las solicitudes de trabajo dependen de quién esté haciendo qué y puede variar de manera drástica. Una máquina envía una solicitud de ayuda a las demás máquinas. Aquí el emisor toma la iniciativa para localizar más ciclos del CPU. Una máquina inactiva o subcargada anuncia a las demás que tiene poco trabajo y está preparada para más. Su objetivo es localizar una máquina dispuesta a darle trabajo. > Los arcos que van de una subgráfica a la otra representan el tráfico en la red.
> Cada subgráfica es una unidad de asignación.

El algoritmo debe buscar unidades de asignación fuertemente acopladas:
>> Tráfico intenso dentro de la unidad de asignación.
>> Tráfico escaso entre unidades de asignación Para que casa solución cumpla sus restricciones: ++ No se intenta maximizar el uso de la cpu.

++ Se otorga a cada usuario una parte del poder de cómputo.

++ Cuando la máquina donde se crea un proceso decide que se debe ejecutar en otra parte:
--- Le pide al coordinador de la tabla de usos que le asigne un procesador:
* Si existe uno disponible y nadie más lo desea, se otorga el permiso.
* Si no, la solicitud se niega y se registra. << Si un usuario ejecuta procesos en máquinas de otros usuarios, acumula puntos de penalización, lo que se registra en la tabla de usos.

<< Si un usuario tiene solicitudes pendientes insatisfechas, se restan puntos de penalización.

<< Si no existen solicitudes pendientes y ningún procesador está en uso, la entrada de la tabla de usos se desplaza un cierto número de puntos hacia el “0”, hasta alcanzarlo.

<< El movimiento de puntos hacia arriba y abajo da nombre al algoritmo. << Puntaje positivo en una entrada de la tabla de usos indica que la estación de trabajo relacionada es un usuario de los recursos del sistema.

<< Puntaje negativo significa que precisa recursos.

<< Una puntuación “0” es neutra.
* Mantienen la sencillez de los centralizados.

* Se escalan mejor que los centralizados. ALGORITMO JERÁRQUICO Se establece un árbol jerárquico con distintos niveles.

*- Para cada grupo de máquinas hay una máquina administradora:
** Mantiene un registro de las máquinas ocupadas y las inactivas.

*- Cada procesador se comunica con un superior y subordinados
** El flujo de información es controlable. Un método propuesto consiste enorganizar a los procesadores en jerarquías lógicas, independientes de la estructura física de red: En caso de falla de un administrador en un equipo con funciones jerárquicas, lo puede reemplazar un subordinado:

La elección la pueden hacer los subordinados, los pares jerárquicos del administrador enfermo o el superior jerárquico del mismo Si el administrador determina que sí puede satisfacer la solicitud:

* Divide la solicitud en partes y la distribuye a los administradores subordinados a él.

*Los subordinados repiten esta operación hasta llegar al nivel inferior.

*Los procesadores se señalan como “ocupados” y el número de procesadores asignados se informa hacia arriba Al crearse un proceso, la maquina donde se origina envía mensajes de prueba a una maquina elegida al azar, para preguntar si su carga de trabajo esta por debajo de cierto valor.

En caso afirmativo, el proceso se envía a ese lugar. ALGORITMO HEURISTICO DISTRIBUIDO INICIADO POR EL EMISOR En caso contrario, se elige otra maquina para la prueba. Las pruebas no se realizan por siempre, sino se encuentra una maquina adecuada después de N pruebas, el algoritmo termina y el proceso se ejecuta en la maquina de origen Este algoritmo es iniciado por un receptor subcargado.

Con este algoritmo cuando un proceso termina, el sistema verifica si tiene el trabajo suficiente.

En caso contrario, elige una maquina al azar y le solicita trabajo, si esa maquina no tiene nada que ofrecer, se le solicita a la segunda, o a una tercera maquina ALGORITMO HEURISTICO DISTRIBUIDO INICIADO POR EL RECEPTOR Sino encuentra trabajo en N pruebas, el receptor deja de preguntar durante cierto tiempo, realiza el trabajo que este formado en su cola de trabajos e intenta de nuevo, cuando termina el siguiente proceso. Es posible combinar ambos algoritmos emisor-receptor y hacer que las maquinas intenten deshacerse del trabajo cuando tienen demasiado, o traten de conseguirlo cuando no tienen suficiente Algoritmos de Remates Cada procesador anuncia su precio aproximado a través de un archivo todos pueden leer:

-Da una indicación de que lo vale el servicio. Los procesadores pueden tener distintos precios, según su velocidad, tamaño de memoria, presencia del hardware y otras características. 1) Verifica si alguien ofrece el servicio que necesita.
2) Determina el conjunto de sus procesadores que pueden proporcionar sus servicios.
3) Obtienen el mejor candidato (mas barato, rápido, mejor precio, desempeño)
4) Genera una oferta y envía a su primera opción.
5) Se reúnen todas las ofertas y eligen una
6) Se informa a los ganadores y se ejecuta ese proceso Cuando un proceso desea iniciar, Genera muchas dudas de quien obtiene lo mejor y como lo obtiene
Full transcript