Modelado
Analítico con Relación al
Rendimiento
Universidad Nacional del Nordeste
Facultad de Ciencias Exactas y
Naturales y Agrimensura
Materia: Sistemas Operativos
Profesor: La red Martinez, David
Luis
Grupo: 17
Integrantes: Matijasevich, Claudia
Melero, Maria
Paula
Mendoza, Marcelo
Pace, Carlos
Repizo, Mariana
Saint Jean,
Fernando
Stacciuoli,
Romina
Tonsich, Marcelo
Año: 2001
1
Indice:
3.1.1 Introducción a la teoría de colas
3.1.2 Costos de los sistemas de colas.
3.1.3 Sistema de costo mínimo.
3.1.4 Evaluación del sistema cuando se conoce el
costo de espera
3.3 Variable
aleatoria de Poisson
2
Introducción
Los modelos analíticos son una representación matemática de los sistemas computacionales y permiten al evaluador del rendimiento sacar conclusiones rápidas y precisas acerca del comportamiento del sistema. Sé a desarrollado un gran cuerpo de resultados matemáticos que pueden ser aplicados por el modelador experto.
3
Desarrollo
3.1Sistemas de Colas:
3.1.1
Introducción
a la teoría de colas
Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o sistemas de colas. Los modelos sirven para encontrar el comportamiento de estado estable, como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado. Esta información, junto con los costos pertinentes, se usa, entonces, para determinar la capacidad de servicio apropiada.
3.1.2 Costos de los sistemas de colas.
Un sistema de colas puede dividirse en sus dos componentes de mayor importancia, la cola y la instalación de servicio. Las llegadas son las unidades que entran en el sistema para recibir el servicio. Siempre se unen primero a la cola; si no hay línea de espera se dice que la cola esta vacía. De la cola, las llegadas van a la instalación de servicio de acuerdo con la disciplina de la cola, es decir, de acuerdo con la regla para decidir cuál de las llegadas se sirve después. El primero en llegar primero en ser servido es una regla común, pero podría servir con prioridades o siguiendo alguna otra regla. Una vez que se completa el servicio, las llegadas se convierten en salidas.
Ambas componentes del sistema tienen costos asociados que deben de considerarse.
3.1.2.1 Costo de Espera.
Esperar significa desperdicio de algún recurso activo que bien se puede aprovechar en otra cosa y esta dado por:
Costo total de espera = CwL
Donde Cw = costo de espera por hora (en cecacor’s) por llegada por unidad de tiempo y L= longitud promedio de la línea.
3.1.2.2 Costo de Servicio.
Este en la mayoría se trata de comprar varias instalaciones de servicio, en estos casos solo se ocupan los costos comparativos o diferenciales.
3.1.3 Sistema de costo mínimo.
Aquí hay que tomar en cuenta que para tasas bajas de servicio, se experimenta largas colas y costos de espera muy altos. Conforme aumenta el servicio disminuyen los costos de espera, pero aumenta el costo de servicio y el costo total disminuye, sin embargo, finalmente se llega a un punto de disminución en el rendimiento. Entonces el propósito es encontrar el balance adecuado para que el costo total sea el mínimo.
3.1.4 Evaluación del sistema cuando se conoce el costo de espera
Los costos de servicio influyen en el método para encontrar el sistema de menor costo. Si el costo de servicio es un función lineal de la tasa de servicio, puede encontrarse una solución general para la tasa óptima.
Para aplicar una solución general, se necesita una tasa de servicio que pueda variar de manera continua.
Cuando los costos de servicio cambian en forma escalonada, se usa la técnica de prueba y error para encontrar el sistema de menor costo. Se calcula el costo total para una tasa de servicio, después para la siguiente y así sucesivamente. Esto continúa hasta que se encuentra un límite inferior o un mínimo tal, que el aumentar o el disminuir las tasas de servicio da costos totales más altos.
3.1.5 Estructuras típicas.
Permitiendo que varíen el número de colas y el número de servidores, pueden hacerse los diagramas de los cuatro tipos de sistemas de la siguiente figura. Cada línea de espera individual y cada servidor individual se muestra por separado.
El primer sistema que se muestra en la figura, se llama un sistema de un servidor y una cola o puede describir un lavado de autos automático o un muelle de descarga de un solo lugar. El segundo, una línea con múltiples servidores, es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando llega el turno. El tercer sistema, aquél en que cada servidor tiene una línea de separada, es característico de los bancos y las tiendas de autoservicio. El cuarto sistema, es una línea con servidores en serie, puede describir una fábrica. Este modelo puede aplicarse a personas esperando en una cola para comprar boletos para el cine, a mecánicos que esperan obtener herramientas de un expendio o a trabajos de computadora que esperan tiempo de procesador.
3.1.5.1 Llegadas.
Consiste en la entrada al sistema que se supone es aleatoria. No tienen horario, es impredecible en que momento llegarán. El modelo también supone que las llegadas vienen de una población infinita y llegan una a la vez.
3.1.5.2 Cola.
En este modelo se considera que el tamaño de la cola es infinito. La disciplina de la cola es: primero en llegar, primero en ser servido sin prioridades especiales. También se supone que las llegadas no pueden cambiar lugares en la línea (cola) o dejar la cola antes de ser servidas.
Se supone que un solo servidor proporciona el servicio que varía aleatoriamente.
3.2Teoría
de colas
Los
Sistemas De Colas De Espera pueden definirse mediante cinco componentes:
·
La
función de densidad de probabilidad del tiempo entre llegadas;
·
La
función de densidad de probabilidad del tiempo de servicio;
·
El
número de servidores;
·
La
disciplina de ordenamiento en las colas;
·
El
tamaño máximo de la cola.
La
densidad de probabilidad del tiempo entre llegadas describe el intervalo de
tiempo entre llegadas consecutivas. Por ejemplo si nos imaginamos que
encargamos a una persona para que observe la llegada de los clientes, entonces
a cada llegada el observador registraría el tiempo transcurrido desde que
ocurrió la llegada previa. Luego de un determinado tiempo la lista de datos
recogidos podría clasificarse y agruparse y de allí obtendríamos la función de
densidad de probabilidad que caracteriza al proceso de llegadas.
Cada
cliente requiere de cierta cantidad de tiempo proporcionado por el servidor.
El tiempo
de servicio requerido varia entre un cliente y otro. El registro de los tiempos
de servicio requeridos entre los clientes conforman La densidad de Probabilidad
del tiempo de servicio.
Tanto el
tiempo entre llegadas como el tiempo de servicio son variables aleatorias
Continuas.
La
literatura sobre colas de espera utilizada en sistemas con capacidad infinita,
un solo servidor y una disciplina FCFS (primero en llegar primero en ser
servido)es la notación A/B/m (Kendall abreviada); donde A es la densidad de probabilidad
de tiempo entre llegadas, B es la dencidad de probabilidad de tiempo de servicio
y m representa al número de servidores.
Las
densidades de probabilidades A y B son escogidas a partir del conjunto:
M - dencidad de probabilidad exponencial ( M significa Markov ).
D - todos los clientes tienen el mismo valor ( D significa
determinístico).
G - general ( es decir densidad de probabilidad arbitraria ).
La
hipótesis de utilizar una probabilidad de tiempo entre llegadas exponencial es
totalmente razonable para cualquier sistema que maneja una gran cantidad de
clientes independientes, en estas condiciones la probabilidad de que lleguen
exactamente n clientes durante un intervalo de tiempo estará dada por la ley de
Poisson.
En cambio
es más difícil de defender la hipótesis de que los tiempos de servicio sean
también de carácter exponencial. sin embargo para las situaciones en donde mas
grande es el tiempo de servicio menor será su probabilidad de ocurrir.
3.3Variable aleatoria de Poisson
Una variable aleatoria de Poisson v
de parámetro 
es
una variable aleatoria discreta caracterizada por la siguiente
probabilidad P:
Sus funciones densidad de probabilidad [f(v)] y distribución de probabilidad [F(v)] son
Su media (
)
y su varianza (
) son
3.3.1 Proceso de Poisson
Un proceso de Poisson de tasa 
es
un proceso estocástico 
que cumple:
A(t) representa el número total de llegadas de clientes a un recurso entre los instantes 0 y t, y, para s < t, A(t) - A(s) es el número de llegadas en el intervalo (s, t].
Los números de llegadas en intervalos disjuntos son independientes.
El número de llegadas en un intervalo cualquiera de longitud
se
modela mediante una variable aleatoria de Poisson de parámetro 
. Esto es, para todo 
,
El número medio de llegadas en un intervalo de longitud es
. Esto conduce a una interpretación de como
tasa de llegadas (número medio de llegadas al recurso por unidad
de tiempo).
Una propiedad importante de los procesos de Poisson es que
el tiempo entre llegadas, definido como aquél que transcurre
entre la llegada de dos clientes consecutivos, tiene una distribución
exponencial de parámetro y
los distintos tiempos entre llegadas son independientes. Esto es, si llamamos tn
al instante de llegada del cliente n-ésimo, los tiempos 
son
independientes y tienen una distribución probabilística:
3.4Sistema de colas M/M/1
Un sistema de colas M/M/1
consta de una única cola (en el contexto de las redes de comunicación,
parte de la memoria de los nodos donde se almacenan temporalmente los mensajes)
y un único servidor (en el mismo contexto, una línea de transmisión o canal).
Los clientes llegan de acuerdo a un proceso de Poisson de tasa (tasa
de llegada de clientes al sistema), y el tiempo de servicio,
definido como aquél en que el servidor (por tanto, no la cola) está ocupado con
un cliente, tiene una distribución exponencial de parámetro 
,
que llamaremos tasa de servicio (lo representamos así porque,
en el contexto de las redes de comunicación, 
es
el tamaño medio de los mensajes y C la capacidad del canal o línea
de transmisión). Los tiempos de servicio de los distintos clientes son
independientes entre sí e independientes del tiempo entre llegadas al sistema.
Definiremos los siguientes parámetros:
Factor de utilización
del servidor, o fracción de tiempo en que está ocupado.
Número medio
de clientes en el sistema.
Tiempo medio
de estancia de un cliente en el sistema.
Nú mero medio de clientes
esperando en la cola.
Tiempo medio
de espera de un cliente en la cola.
3.5Otros tipos de colas
Una red de colas es un conjunto de nudos interconectados entre si. Las redes de colas pueden ser cerradas, cuando hay un numero fijo de clientes circulando, abiertas, cuando los clientes pueden abandonar el sistema y/o incorporarse a el, y mixtas, donde hay una población fija y una población flotante.
La red mas sencilla, es una formada por dos nudos en serie, cada uno de los cuales tiene distribuciones exponenciales para los tiempos entre llegadas y para los tiempos entre servicios.
El estudio de redes de colas se facilita por el teorema de Burke, quien demostró, que en régimen estacionario, la salida de un sistema M/M/m con una tasa de entrada es estadísticamente independiente del proceso de entrada . El tiempo medio de respuesta de la red es igual a la suma de los tiempos medios de respuesta en cada uno de los nodos, por ser cada nodo independiente. Si existe realimentación el teorema de Burke no es aplicable.
Jackson demostró que a pesar de que las llegadas a los nudos no sean procesos de Poisson, cada uno de ellos se comporta como si fuese un sistema M/M/m, de esta forma podemos considerar cada nudo como independiente de los demás.
Existen cuatro familias de nudos diferentes:
· Un único servidor exponencial y disciplina FCFS.
· Un sistema con una infinidad de servidores con distribución de servicio genérica y donde cada cliente tiene su propio servidor. Es decir no hay cola.
· Un único servidor con distribución de servicios genérica y disciplina de tiempo compartido.
· Un único servidor con distribución de servicio genérica y disciplina LCFS.
3.5.1 COLAS M/M/Q
Es un modelo de nodo, donde llegan distintas tramas por segundo, las cuales van a ser canalizadas por líneas de salida , cuando en un momento dado llega una trama y todas las líneas de salidas están ocupadas, la trama es descartada.
El número de transiciones por unidad de tiempo hacia un estado inferior depende del estado actual; cuantas más líneas haya ocupadas en un momento dado, mayor es la probabilidad de que alguna quede libre en el instante siguiente.
En un modelo sencillo, el nodo podría disponer de un buffer para almacenar aquellas llamadas que llegan cuando todas las líneas estén ocupadas, para de esta forma al quedar una línea libre se toma uno de los paquetes del buffer y se coloca en esa línea.
3.5.2 COLAS M/G/1
Aquí se representa el área de almacenamiento temporal al cumplirse el servicio, o sea el tiempo de salida. Donde representaremos con j al instante en que j-ésimo usuario abandona la cola, con nj indicaremos el numero de usuarios que quedan en la cola, y una relación simple conectando el numero de usuarios en la cola en el instante j con el numero de usuarios en el instante j-1. Entonces:
Nj
= nj-1
– 1+ vj si nj-1 >=1
vj si nj-1= 0
Esta ecuación representa la dinámica de la cola en los tiempos de cumplimiento de servicios.
3.6Markov
Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. " Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.
En los negocios, las cadenas de Markov se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades de personal y para analizar el reemplazo de equipo.
El análisis de Markov, llamado así en honor de un matemático ruso que desarrollo el método en 1907, permite encontrar la probabilidad de que un sistema se encuentre en un estado en particular en un momento dado. Algo más importante aún, es que permite encontrar el promedio a la larga o las probabilidades de estado estable para cada estado. Con esta información se puede predecir el comportamiento del sistema a través del tiempo.
La tarea más difícil es reconocer cuándo puede aplicarse. La caracteristica más importante que hay que buscar en la memoria de un evento a otro.
3.6.1 LA CADENA DE MARKOV
En la figura se muestra el proceso para formular una cadena de Markov. El generador de Markov produce uno de n eventos posibles, Ej , donde j = 1, 2, . . . , n, a intervalos discretos de tiempo (que no tiene que ser iguales ). Las probabilidades de ocurrencia para cada uno de estos eventos dependen del estado del generador. Este estado se describe por el último evento generado. El último evento generado fue Ej , de manera que el generador se encuentra en el estado Mj.
La probabilidad de que Ek sea el siguiente evento generado es una probabilidad condicional : P ( Ek / Mj ). Esto se llama probabilidad de transición del estado Mj al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición.
Probabilidades de transición.
Una forma de describir una cadena de Markov es con un diagrama de estados, como el que se muestra en la figura 4.1.2. En ésta se ilustra un sistema de Markov con cuatro estados posibles: M1, M2 , M3 y M4 . La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama
Otro método para exhibir las probabilidades de transición es usar una matriz de transición. . La matriz de transición para el ejemplo del diagrama de estados se muestra en la tabla Matriz de transición.
Otro método para exhibir las probabilidades de transición es usar una matriz de transición. .
Para n = 0, 1, 2, ....
El superíndice n no se escribe cuando n = 1.
