ALGORITMO

CENTRALIZADO
 Es un algoritmo heurístico que a diferencia del
anterior no precisa información anticipadamente.
Es un algoritmo arriba-abajo (Mutka y Livny)
centralizado porque un coordinador mantiene una tabla de
usos:
* Contiene una entrada por estación de trabajo inicializada
en “0”.
* Cuando ocurren eventos significativos se envían al
coordinador mensajes para actualizar la tabla.
* Las decisiones de asignación se basan en la tabla:
Se toman cuando ocurren eventos de planificación, tales
como: se realiza una solicitud, se libera un procesador, el
reloj produce una marca de tiempo
* No se intenta maximizar el uso de la cpu.
* Se procura otorgar a cada usuario una parte justa 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:
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 por segundo, 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.
Un 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.

*Un puntaje negativo significa que precisa recursos.

*Una puntuación “0” es neutra.

La heurística utilizada para la asignación de
procesadores es la siguiente:
* Cuando un procesador se libera gana la solicitud
pendiente cuyo poseedor tiene la puntuación
menor.
* Un usuario que no ocupe procesadores y que
tenga pendiente una solicitud durante mucho
tiempo:
* Siempre vencerá a alguien que utilice muchos
procesadores.
* Se cumple con el principio de asignar la capacidad
de manera justa.
• Este modelo basa su funcionamiento en la teoría
de colas.

• En general este modelo puede reducir

significativamente el tiempo de espera al tener
una sola cola de procesadores a repartir.
• La capacidad de cómputo se puede gestionar de
mejor forma si se tiene micros con mayores
capacidades.

• Los usuarios no disponen de estaciones de

trabajo sino de terminales gráficas de alto
rendimiento.

• No existe el concepto de propiedad de los

procesadores, los que pertenecen a todos y se
utilizan compartidamente.
• Llamamos “l” a la tasa de entradas totales de
solicitudes por segundo de todos los usuarios
combinados.

• Llamamos “m” a la tasa de procesamiento de

solicitudes por parte del servidor.
• Para una operación estable debe darse que “m
> l”:

• Se pueden permitir pequeños lapsos de tiempo en los que la tasa

de entrada exceda a la de servicio.

• Llamamos “T” al promedio de tiempo entre la

emisión de una solicitud y la obtención de una
respuesta completa:

• T = 1 / ( m - l ).
 • Cuando “ l ” tiende a “0”, “T” no tiende a “0”.

• Supongamos que tenemos “n”

multiprocesadores personales, cada uno con
cierto número de cpu y con su propio sistema de
colas con tasas “ l ” y “ m ” y tiempo “T”:

• Si reunimos todas las cpu y formamos una sola

pila de procesadores tendremos un solo
sistema de colas en vez de “n” colas
ejecutándose en paralelo.
• La tasa de entrada será “n l”, la tasa de servicio será
“n m” y el tiempo promedio de respuesta será:

• T1 = 1 / (n m - n l) = 1 / n ( m - l) = T / n.

Conclusión: si reemplazamos “n” pequeños recursos

por uno grande que sea “n” veces más poderoso:
• Podemos reducir el tiempo promedio de respuesta
“n” veces.
 Algoritmo Jerárquico

Los algoritmos jerárquicos:

Mantienen la sencillez de los centralizados.

Se escalan mejor que los centralizados.

Un método consiste en organizar a los procesadores en

jerarquías lógicas independientes de la estructura física:
 Se establece un árbol jerárquico con distintos niveles.

 Para cada grupo de máquinas hay una máquina

administradora:
o Mantiene un registro de las máquinas ocupadas y
las inactivas.

 Cada procesador se comunica con un superior y un

número reducido de subordinados:
o El flujo de información es controlable.
En caso de falla de un equipo con funciones jerárquicas:

 Lo puede reemplazar un subordinado:

 La elección la pueden hacer los subordinados, los

pares jerárquicos del equipo fallado o el superior
jerárquico del mismo.

Para disminuir la vulnerabilidad se puede tener en la cima

del árbol jerárquico no uno sino un grupo de equipos; si
alguno del grupo falla los restantes eligen a un subordinado
para integrar el grupo superior.
Las tareas se pueden crear en cualquier parte de la
jerarquía y pueden requerir varios procesos, es decir varios
procesadores.

Cada administrador debe mantener un registro de sus

equipos dependientes que estén disponibles.

Si el administrador que recibe una solicitud determina que

no tiene suficientes procesadores disponibles, transfiere la
solicitud hacia arriba a su superior, quien también podría
trasladarla hacia arriba nuevamente.
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.
Un importante problema consiste en que podría haber varias
solicitudes en distintas etapas del algoritmo de asignación:

 Puede conducir a estimaciones no actualizadas del número

de procesadores disponibles (también pudieron salir de
servicio algunos de los considerados disponibles).

 Podrían presentarse situaciones de competencia, bloqueo,

etc. en el intento de asignación de procesadores.
UN ALGORITMO DETERMINISTA
SEGÚN LA TEORÍA DE
GRÁFICAS

Andrea Yaneth Cano Hernández

Antonio Sánchez Herrera
 ¿QUÉ ES UN ALGORITMO DETERMINISTA?
• Es un algoritmo que, en términos informales, es completamente
predictivo si se conocen sus entradas. Dicho de otra forma, si
se conocen las entradas del algoritmo siempre producirá la
misma salida, y la máquina interna pasará por la misma
secuencia de estados. Este tipo de algoritmos ha sido el más
estudiado durante la historia y por lo tanto resulta ser el tipo
más familiar de los algoritmos, así como el más práctico ya que
puede ejecutarse en las máquinas eficientemente.
• Formalmente los algoritmos deterministas se pueden
definir en términos de una máquina de estado; un
«estado» describe qué está haciendo la máquina en un
instante particular de tiempo. Justo cuando se produce
la entrada, la máquina comienza en su «estado inicial»
y, posteriormente, si la máquina es determinista,
comenzará la ejecución de la secuencia de estados
predeterminados. Una máquina puede ser determinista
y no tener límite temporal para la ejecución o quedarse
en un bucle de estados cíclicos eternamente.
 EL ALGORITMO DETERMINISTA ES 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.
• El problema es encontrar la forma de partir la gráfica
en subgráficas sujetas a restricciones (ej.: de cpu y de
memoria)
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.
Coplanificación
• Planifica un grupo de procesos o dicho de otro
modo, planificar los procesos de un entorno
distribuido.
• La coplanificación se realiza utilizando la
combinación de los siguientes algoritmos.
FCFS(Frist Come Frist Severd, Primero
en llegar, Primero en ser Servido)
• La carga de trabajo se procesa simplemente en
un orden de llegada. Por no tener en
consideración el estado del sistema ni las
necesidades de recursos de los procesos
individuales, la planificación FCFS puede dar
lugar a pobres rendimientos.
SJF (Shortest Job First ,
• Este algoritmo selecciona al proceso con el
próximo tiempo de ejecución más corto. Un
proceso corto saltará a la cabeza de la cola.
• La ejecución de un proceso consiste en ciclos de
ejecución de CPU y ciclos de espera por E/S. El
algoritmo selecciona aquel proceso cuyo
próximo ciclo de ejecución de CPU sea menor. El
problema está en conocer dichos valores, pero
podemos predecirlos usando la información de
los ciclos anteriores ejecutados.
RR (Round Robin)
• Round Robin es particularmente efectivo para
sistemas generales de tiempo compartido. Se
implementa con una cola FIFO de procesos.
Nuevos procesos son agregados al final de la
cola, y toma el proceso que se encuentra en la
cabeza de la cola. Actualiza el timer para que
interrumpa después del quantum de tiempo.
MLQ (Multi Level Queues)
• La planificación mediante colas
multinivel es un algoritmo de planificación de
procesos en un sistema operativo. Su objetivo es
diferenciar entre distintos tipos de trabajos, para
ello dividen la cola de procesos preparados en
varias colas, una por cada tipo de trabajo, y no
permiten el movimiento de los procesos entre las
distintas colas.
MLFQ (Multi Level Forward Serverd)
• Mediante la planificación con colas multinivel
realimentadas, un proceso se puede mover de una cola a
otra dependiendo de su comportamiento en tiempo de
ejecución.

• En las colas multinivel realimentadas se separan los

procesos en grupos pero dependiendo de las
características de su ráfaga de CPU. Los procesos con
ráfagas cortas irán a una cola más prioritaria de procesos
preparados que los procesos con ráfagas largas
SRTF (Shortest Run – Time First)
• Planificación por Prioridad al Tiempo Restante más.

• Es similar al SJF, con la diferencia de que si un

nuevo proceso pasa a listo se activa el dispatcher
para ver si es más corto que lo que queda por
ejecutar del proceso en ejecución. Si es así, el
proceso en ejecución pasa a listo y su tiempo de
estimación se decrementa con el tiempo que ha
estado ejecutándose.
Concepto de Coplanificación

• TOMA EN CUENTA LOS PATRONES DE COMUNICACION

ENTRE LOS PROCESOS DURANTE LA PLANIFICACION.

• DEBE GARANTIZAR QUE TODOS LOS MIEMBROS DEL

GRUPO SE EJECUTEN AL MISMO TIEMPO.
Coplanificación
• SE EMPLEA UNA MATRIZ CONCEPTUAL DONDE:
LAS FILAS SON ESPACIOS DE TIEMPO.

• CADA PROCESADOR DEBE UTILIZAR UN

ALGORITMO DE PLANIFICACION ROUND ROBIN:

* TODOS LOS PROCESADORES EJECUTAN EL PROCESO

EN EL ESPACIO “0” DURANTE UN CIERTO PERIODO FIJO.
* TODOS LOS PROCESADORES EJECUTAN EL PROCESO
EN EL ESPACIO “1” DURANTE UN CIERTO PERIODO FIJO, ETC.
Coplanificación

• SE DEBEN MANTENER SINCRONIZADOS LOS INTERVALOS DE

TIEMPO.

• TODOS LOS MIEMBROS DE UN GRUPO SE DEBEN COLOCAR

EN EL MISMO N° DE ESPACIO DE TIEMPO PERO EN
PROCESADORES DISTINTOS.
Coplanificación
• El algoritmo de Ousterhout toma en cuenta los patrones de
comunicación entre los procesos durante la planificación.
Debe garantizar que todos los miembros del grupo se
ejecuten al mismo tiempo.
Ejemplo: Algoritmo de Ousterhout