Evaluacin y Explotacin de Sistemas Informticos

Tcnicas de modelado analtico

Introduccin

Conceptos bsicos Teora de Colas

Anlisis Operacional

Aplicaciones del Anlisis Operacional

Introduccin

La prediccin cuantitativa implica la existencia de un

modelo matemtico del modelo observado.
Modelo matemtico: abstraccin de un sistema real que
pueda ser utilizado para propsitos de prediccin y control.
Debe ser capaz de analizar cuando uno o ms cambios en
algn aspecto del sistema modelado, puede afectar a otros
aspectos del sistema o bien al sistema en su conjunto.
Los modelos, en general, constan de los siguientes
elementos:

Variables
Estado
Entrada (control)
Salida

Parmetros
Relaciones funcionales

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Elementos del modelo:

Variables

Estado:

Entrada:

Determinan completamente, cuando son conocidas, en que

situacin se encuentra el sistema representado en el modelo.
Variables que describen el estado de un componente del sistema
en el tiempo t.
Sirven para modificar la evolucin del sistema.
Representan los aspectos del sistema que se van a modificar
cuando lo utilicemos.
Normalmente describen las caractersticas de la carga de trabajo
y los componentes.

Salida

Tienen observacin directa en el sistema representado por el

modelo.
Valores se determinan por la resolucin del modelo
Normalmente representan los ndices de rendimiento internos y
externos del sistema.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Elementos del modelo:

Parmetros y Relaciones Funcionales

Parmetros

En este contexto hace referencia a ciertos valores

numricos que se introducen con la finalidad de poder
establecer las relaciones que unen las distintas variables.
NO CONFUNDIR con la acepcin de parmetro utilizada
como sinnimo de variable de entrada.

Relaciones funcionales

Conjunto de ecuaciones o inecuaciones de tipo

matemtico que determinan la evolucin del sistema.
Describen las interacciones entre las variables de estado y
de entrada.
Han de ser resolubles por mtodos analticos.
Variables no controlables, introduccin de simplificaciones.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Descomposicin jerrquica

Enfoque que permite ampliar el conjunto de problemas

resolubles analticamente.
Se identifican mdulos, o subsistemas, contenidos unos en otros.
Los resultados del anlisis de un modulo puede ser utilizados en
el anlisis del siguiente mdulo en la jerarqua que le contiene.
Partiendo de los subsistemas ms elementales, cada subsistema
puede ser estudiado de forma aislada.
Sistema Completo
Subsistema i

Subsistema j

Subsistema h

Subsistema k

M.A.V.S. nov-10

Sistema Completo
(componentes equivalentes)
Subsistema i
Subsistema j

Subsistema h

Dpto. Informtica ETSII U. Valladolid

Subsistema k
5

Teora de colas

Agner Krarup Erlang, ingeniero Dans que trabajo para la Copenhagen

Telephone Exchange, public el primer artculo sobre teora de colas en
1909.
David G. Kendall introdujo la notacin de colas A/B/C en 1953.

A: Llegadas
B: Servicio
C: Nmero de servidores

La teora de colas o de lneas de espera se puede aplicar a todos aquellos

problemas que pueden caracterizarse como problemas de congestin
llegada-partida.
Una cola es una lnea de espera.
Teora de colas

Es el estudio matemtico del comportamiento de lneas de espera.

Modelos matemticos que describen sistemas de lneas de espera o de
sistemas de colas.
Estas se producen cuando un conjunto de clientes llegan a un sitio
(centro de servicio) para obtener un servicio de un servidor que dispone
de cierta capacidad de atencin. Si el servidor no est disponible y el
cliente decide esperar, entonces se forma la lnea de espera.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Modelo de colas aplicados al anlisis de

Sistemas Computacionales

Los trabajos en los ordenadores comparten los recursos

En un instante de tiempo solamente un trabajo puede
utilizar un recurso. El resto han de esperar en una cola
para utilizarlo.
Determinacin del tiempo que los trabajos consumen en
las diferentes colas del sistema.
Clientes llegan al centro de servicio, esperan en cola si es
preciso, reciben el servicio del servidor y abandonan el
sistema.
Parmetros

Intensidad de carga
Demanda de servicio: tiempo medio de servicio requerido
por un cliente

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Centro de servicio

Es un conjunto compuesto por un servidor y una cola de

espera.
El servidor representa el recurso fsico del ordenador
La cola de espera modela la cola de trabajos que esperan
recibir servicio, utilizar el recurso fsico.
Parmetros temporales

Tiempo de servicio: tiempo que transcurre desde que un

trabajo empieza a utilizar el recurso hasta que lo deja
libre.
Tiempo de respuesta: tiempo de servicio ms el tiempo
que el trabajo permanece en la cola de espera.

Tipos

Servidor nico, una cola de espera

Dos (varios) servidores y una cola de espera
Infinitos servidores (no tiene cola de espera): los trabajos
que llegan siempre encuentran un servidor disponible.
Centro de tipo retardo o demora.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Centro de servicio

Intensidad de la carga: tasa de llegada de los clientes ( )

Tiempo de servicio: tiempo que, por trmino medio,
requiere cada cliente (S)
Tiempo de espera: tiempo consumido por una peticin en
espera de acceso al recurso (W)

Cola

Servidor

Llegada de
Clientes

Salida de
Clientes
W

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

Componentes de una cola

Disciplina
de servicio
Distribucin
del tiempo
de servicio

Posiciones
en espera

...

Poblacin
de Clientes

Proceso de
llegada

Nmero de
Servidores

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

10

Notacin Colas (Kendall: A/S/m/B/K/SD)

A
Proceso de llegadas: La distribucin de probabilidad de los
periodos entre llegadas al centro de servicio.
S
Tiempo de servicio: La distribucin de probabilidad de los
periodos de servicio para cada peticin en el centro de servicio
m
Nmero de servidores
B
Capacidad del sistema: El nmero mximo de clientes que
pueden estar en el centro de servicio. Capacidad de
almacenamiento.
K
Tamao de la poblacin: El nmero total de clientes potenciales
que pueden llegar al sistema.
SD
Disciplina de servicio: La poltica de servicio (FIFO, LIFO, .)

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

11

Notacin Colas (Kendall: A/S/m/B/K/SD)

La distribucin de los tiempos entre llegadas y los tiempos de

servicio (parmetros A y S) se denotan de forma general por:

M
Exponencial (la M es por Markov)
Ek
Erlang con parmetro k
Hk
Hiperexponencial con parmetro k
D
Determinista
G
General

Cuando se supone capacidad infinita de almacenamiento, tamao

infinito de la poblacin y disciplina de servicio FCFS o FIFO los
parmetros B, K y SD se suprimen.

Colas M/M/1

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

12

Modelado de sistemas de computacin.

Modelos de redes de colas.

Un modelo en el cual los trabajos que salen de una cola

(centro de servicio) llegan a otra cola (o posiblemente a la
misma cola) se denominan redes de colas.
Queueing network modeling (QN)

El sistema se representa como una red de colas

El sistema se puede evaluar analticamente.

Modelo de red de colas

Coleccin de centros de servicio interconectados que

representan los recursos del sistema
Servidor : modelo del recurso del sistema (hardware)
Cola: modelo de la cola software asociada al recurso
hardware.
Clientes (customer): usuarios, transacciones o trabajos en
el sistema.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

13

Modelos de redes de colas:

Tipos de redes

Redes abiertas (modelos abiertos).

Existencia de, al menos, una fuente de trabajos y uno o

ms sumideros que absorben los trabajos que salen del
sistema.
Existe al menos un camino que, a partir de dada nodo,
lleve al sumidero.
Tienen llegadas y salidas externas
El n de trabajos en el sistema vara a lo largo del tiempo.
En los estudios de este tipo de sistemas se parte de
productividad conocida. Su valor es igual a la tasa de
entrada al sistema.
Los clientes que completan su servicio abandonan el
sistema.
El objetivo es caracterizar el nmero de trabajos en el
sistema y el tiempo de respuesta.
Ej: Sistemas transaccionales.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

14

Modelos de redes de colas

Redes Abiertas

Llegada

Servidor 0

Servidor 1
Salida

Servidor 2

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

15

Modelos de redes de colas:

Tipos de redes

Redes cerradas (modelos cerrados)

No tienen llegadas ni salidas externas.

El n de trabajos o clientes en el sistema permanece
constante.
Puede verse como un sistema donde su salida (out) se
conecta con su entrada (in).
El flujo de trabajos saliendo del out y entrando por el
in puede verse como el throughput del sistema cerrado.
Se parte del n de trabajos en el sistema (N).
Se intenta determinar el throughput (tasa de finalizacin
de trabajos) y el tiempo de respuesta.
Ej: sistemas interactivos.
Terminal: estacin de retardo
N <= que el n de terminales.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

16

Modelos de redes de colas

Redes Cerradas

Terminal
(Retardo)

CPU

Disco 1

Disco 2

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

17

Modelos de redes de colas:

Centros de servicio simples

[Lazowska 93, pp5] [Fortier & Michel, 2003, pp.236]

El modelo tiene dos parmetros

Intensidad de la carga: tasa a la que llegan los clientes

Un cliente cada dos segundos o 0.5 clientes/segundo

Demanda de servicio: media del tiempo de servicio requerido por

un cliente
1.25 segundos.

Es posible realizar evaluaciones de rendimiento del tipo:

Utilizacin: proporcin de tiempo que el servidor est ocupado

Tiempo de residencia: tiempo medio consumido en el centro de
servicio
Longitud de la cola : nmero medio de clientes en el centro de
servicio, esperando y recibiendo servicio.
Throughput: Tasa a la que se procesan las peticiones.
Cola
Llegada de
Clientes

M.A.V.S. nov-10

Servidor
Salida de
Clientes

Dpto. Informtica ETSII U. Valladolid

18

Modelo del servidor central

Patrn de interconexin entre las estaciones de servicio.

Introducido por Buzen en 1973.
Intenta reproducir el comportamiento de los programas
cuando se ejecutan en el ordenador.
No considera la memoria del sistema, nicamente el
procesador y las unidades de almacenamiento.
Terminal
(Retardo)

CPU

Disco 1

Disco 2

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

19

Modelos de redes de colas:

Centros de servicio mltiples

Servidores
Cola
Salida de
Clientes
...

Llegada de
Clientes

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

20

10

Anlisis Operacional

Tcnica analtica
Toma en cuenta las relaciones entre los elementos del
sistema.
Presentado por Buzen y Denning a finales de los 1970.
Su origen se encuentra en la teora de colas
Utiliza variables de ms fcil verificacin

Relaciones entre variables directamente observables en el

sistema
En este contexto Operacional equivale a Directamente
medible
Una hiptesis operacionalmente comprobable es una
hiptesis que puede ser verificada por su medida
Ej: El nmero de llegadas de peticiones al sistema es igual
al nmero de finalizaciones
en un tiempo suficientemente largo.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

21

Variables operacionales

Directamente medibles en un periodo de tiempo finito.

Ejemplo: Si se observa un dispositivo i de un sistema
informtico como una caja negra durante un periodo de
tiempo T se pueden obtener las siguientes medidas:
T (tiempo). Intervalo de observacin o de medida del

sistema.
Ai (trabajos o clientes). Nmero de llegadas de peticiones
observadas durante el intervalo T. (Arrivals)
Ci (trabajos o clientes). Nmero de peticiones completadas
o servidas durante el intervalo T. (Completions)
Bi (tiempo). Tiempo durante el que el recurso observado
(la estacin de servicio) ha estado ocupado. (Busy).

En un tiempo suficientemente largo

Ai Ci

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

22

11

Variables operacionales deducidas

Tasa de llegadas
i = Ai/ T trabajos por unidad de tiempo

Productividad o Throughput
Xi = Ci / T trabajos por unidad de tiempo

Utilizacin
Ui = Bi / T

Tiempo medio de servicio

Si = Bi / Ci unidades de tiempo por trabajo

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

23

Hiptesis

Periodo de observacin T

Sistema en estado estable o de equilibrio

Hiptesis de flujo de trabajos

Ai = Ci , i

En tiempos de observacin grandes

Ai - Ci 0

Se debe observar que Ai = Ci implica

Xi = i

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

24

12

Ley de la Utilizacin

La utilizacin de un dispositivo se puede expresar en

funcin del nmero de terminaciones mediante la siguiente
formula:

Ui

Bi Ci Bi

T
T Ci

U i X i Si

Esta expresin permite relacionar la productividad de un

dispositivo con su tiempo de servicio.

Si adems se cumple la hiptesis de flujo equilibrado de

trabajo se obtiene una expresin equivalente a la anterior
en funcin de la tasa de llegada.

Ui = i Si
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

25

Ley del Flujo Forzado

Es de gran importancia.
Relaciona la productividad del sistema Xo con la
productividad de un dispositivo individual Xi.
En un modelo abierto la productividad est definida por el
nmero de trabajos que abandonan el sistema por unidad
de tiempo.
En un modelo cerrado ningn trabajo abandona el sistema.
Sin embargo al atravesar el enlace que une la salida con la
entrada se comportan como si abandonaran el sistema e
inmediatamente reentraran en l.
La productividad en este ltimo caso viene dada por el
nmero de trabajos que atraviesan este enlace por unidad
de tiempo.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

26

13

Ley del Flujo Forzado

Supongamos que cada tarea realiza Vi peticiones o visitas

al dispositivo i.
Si el flujo est equilibrado, el nmero de trabajos que sale
del sistema Co (o atraviesa el enlace exterior) y el nmero
de trabajos que atraviesan el dispositivo i estn
relacionados por la expresin:
Ci = C0 Vi y por tanto Vi = Ci / C0
La variable Vi recibe el nombre de razn de visitas al
dispositivo i.
La productividad del sistema durante el periodo de
observacin es:
X0 = C0 / T
La productividad del dispositivo i es:

Xi
M.A.V.S. nov-10

Ci C i C 0

T C0 T
Dpto. Informtica ETSII U. Valladolid

27

Ley del Flujo Forzado

Finalmente se obtiene una expresin de Xi en funcin de las

variables X0 y Vi .
(Ley del flujo forzado)
Xi = X0 Vi
Esta ley establece que el flujo a travs de un determinado
dispositivo de la red determina el flujo en cualquier otro
dispositivo.
Es vlida solo si lo es la hiptesis de flujo equilibrado.
Combinando este resultado y la ley de utilizacin se puede
obtener la siguiente expresin para el valor de la utilizacin del
dispositivo.
Ui = Xi Si= X0 Vi Si= X0 Di
donde Di =Vi Si recibe el nombre de Demanda de servicio sobre el
dispositivo i en todas las visitas que un trabajo realiza al mismo.
La relacin anterior establece que la utilizacin de cada
dispositivo es proporcional a su demanda de servicio.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

28

14

Ley del Flujo Forzado

Las razones de visita son otra forma de especificar el

encaminamiento de los trabajos a travs de la red.
Otra descripcin equivalente se puede realizar mediante la
proporcin de trabajos, tambin llamada probabilidad de
encaminamiento o de transicin.

Las probabilidades de encaminamiento pij indican la proporcin de

trabajos que salen de la estacin i y se dirigen a la estacin j.
Equivalente: La probabilidad de que un trabajo pase a la estacin
j despus de terminar su servicio en la estacin i.

En este sentido se tendr que:

pij = Cij / Ci y
En particular:
p0j = Coj / C0 y
pi0 = Ci0 / Ci

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

29

Ley del Flujo Forzado

Razones de visita y probabilidades de encaminamiento son equivalentes

en el sentido de que a partir de una se obtienen las otras.

En un sistema con K estaciones de trabajo en que se cumple la hiptesis

del flujo equilibrado de trabajos se tiene:
K

C j Ci pij
i 0

donde el subndice 0 representa el exterior del sistema y pi0 es la

proporcin de trabajos que, despus de recibir servicio en la estacin i,
abandonan la red.

Dividiendo ambos lados de la igualdad por C0 obtenemos

K

V j Vi pij
i 0

que representan las denominadas ecuaciones de razones de visita.

Como cada visita al mundo exterior corresponde a una terminacin de un

trabajo, tendremos que siempre se cumplir la ecuacin:
V0 = 1

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

30

15

Ley de Little

Enunciada a principios de la dcada de 1960.

La nica hiptesis requerida para su aplicacin es la del flujo
equilibrado de trabajos.
Si llamamos Ni al nmero de trabajos y Ri al tiempo de respuesta
de la estacin de servicio i, la ley de Little establece que:
Ni = i Ri
Al exigirse que se cumpla la hiptesis del flujo equilibrado de
trabajos se puede sustituir i por Xi.
Ni = Xi Ri
Esta ley es de gran inters en el estudio de modelos de colas, ya
que combina ndices de suma importancia en los estudios de
rendimiento:

Tiempo de Respuesta y
Productividad

Se puede aplicar a cualquier parte del modelo con la nica

condicin que se cumpla la hiptesis del flujo equilibrado de
trabajos.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

31

Ley General del Tiempo de Respuesta

El nmero de trabajos en una red de colas formada por K estaciones se

puede expresar como
N = N1 + N2 + + NK

Si se sustituyen los valores de Ni de acuerdo con la Ley de Little se tiene:

X0 R = X1 R1 + X2 R2 + + XK RK
K

X 0 R X i Ri
i 1

Dividiendo ambos miembros de la igualdad por X0 y aplicando la ley del

flujo forzado quedar la expresin
R = V1 R1 + V2 R2 + + VK RK
K

R Vi Ri
i 1

Esta expresin recibe el nombre de ley general del tiempo de respuesta,

y permite ver claramente que el tiempo de permanencia de un trabajo en
el sistema depende del nmero de visitas que realiza a cada dispositivo y
del tiempo de respuesta que experimenta en l por cada una de las
visitas.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

32

16

Ley del Tiempo de Respuesta Interactivo

Todos los modelos con carga interactiva pueden dividirse

conceptualmente en dos partes:

El tiempo de reflexin (think time), identificado

habitualmente mediante la variable Z, es el tiempo que
transcurre desde que un trabajo abandona el subsistema
central hasta que entra de nuevo en l.

Subsistema de terminales, modela el tiempo de reflexin.

Subsistema central, contiene los dispositivos fsicos del
computador contemplados por el modelo.

Para sistemas interactivos Z>0

Para sistemas por lotes el valor de Z es cero.

El tiempo de respuesta del sistema, R, corresponder al

tiempo que un trabajo pasa en el subsistema central.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

33

Ley del Tiempo de Respuesta Interactivo

El funcionamiento del sistema es el que sigue:

Los usuarios generan peticiones desde los terminales que se

sirven del subsistema central.
Una vez atendidas las peticiones vuelven a los terminales.

Los terminales estn modelados por una estacin con infinitos

servidores (no hay tiempo de espera en la cola).
Transcurrido el tiempo de reflexin los usuarios generan la
siguiente peticin.

M.A.V.S. nov-10

Subsistema de
Terminales

Subsistema
Central

Dpto. Informtica ETSII U. Valladolid

34

17

Ley del Tiempo de Respuesta Interactivo

Podemos aplicar la Ley de Little al conjunto de los dos

subsistemas (subsistema central y subsistema de terminales).
El nmero de trabajos en el conjunto es N.
El tiempo medio que permanece en el conjunto es igual a Z+R.
Aplicando la Ley de Little se puede escribir:
N = (Z+R) X0
y despejando la variable R obtenemos la expresin de la ley del
tiempo de respuesta interactivo.

N
Z
X0

Ntese que el nmero de trabajos en los terminales viene dado,

empleando la ley de Little, por
Z X0
y el nmero de trabajos dentro del sistema que compiten por los
recursos es:
R X0

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

35

Ley de Little:
Trabajos en el sistema y Tiempo
ni(t)
Wi

5
4
3
2
1
0

10

15

20

Ni = Wi /T
Ri = Wi /Ci, considerando que X = C/T se tiene

Ni = Xi Ri
M.A.V.S. nov-10

Ley de Little
Dpto. Informtica ETSII U. Valladolid

36

18

Ley de Little:
Aplicacin a distintos niveles

Disco 1

CPU

Terminal
(Retardo)

Disco 2

Disco 3

4
M.A.V.S. nov-10

Disco n

Dpto. Informtica ETSII U. Valladolid

37

Ley de Little:
Aplicacin a nivel 1

El recurso es utilizado siempre que haya una peticin presente.

La utilizacin puede interpretarse como el nmero medio de
peticiones del recurso

Hay una peticin utilizando el recurso durante un Ui% del tiempo

Cero peticiones durante (1- Ui )% de tiempo

Poblacin

Utilizacin del recurso

Ni Ui

Productividad
Tasa de satisfaccin de peticiones: Xi

Tiempo de residencia
Tiempo medio de servicio requerido por una peticin en el
recurso Ri
Ri Si

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

38

19

Ley de Little:
Aplicacin a nivel 2

Se toman en cuenta el servicio y la cola de tareas

Poblacin
Nmero de peticiones en cola y en servicio: Ni
Productividad
Tasa de satisfaccin de peticiones: Xi

Tiempo de residencia
Tiempo medio de servicio requerido por una peticin en el
recurso ms el tiempo medio en cola : Ri

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

39

Ley de Little:
Aplicacin a nivel 3 (Subsistema central)

Las peticiones al sistema se tratan como interacciones

Poblacin
Nmero de usuarios (N). Interacciones a nivel de
sistema. Usuarios que no estn pensando
Productividad
Tasa a la que las interacciones fluyen entre las terminales
y el subsistema central: Xi (interacciones segundo)

Tiempo de residencia
Tiempo de respuesta convencional : Ri
Tiempo transcurrido entre que un usuario enva una
peticin hasta que la respuesta es devuelta al usuario.
(seg.)

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

40

20

Ley de Little:
Aplicacin a nivel 4

Poblacin
Nmero total de usuarios (N) interactivos
Productividad
Tasa a la que las interacciones fluyen entre las terminales
y el subsistema central: Xi (interacciones segundo)

Tiempo de residencia: R+ Z
Tiempo de respuesta ms tiempo de reflexin de los
usuarios
Tiempo de respuesta de un sistema interactivo.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

41

Aplicaciones del Anlisis Operacional

Se aplicarn los instrumentos del anlisis operacional para:

Se presentarn dos algoritmos para estimar el tiempo de respuesta y la

productividad de un sistema informtico.

Se considerar una nica clase de trabajos.

Se supondr que los tiempos entre llegadas y los tiempos de servicio se
distribuyen de forma exponencial.
La simplificacin es satisfactoria para los tiempos entre llegadas pero no
tanto para los tiempos de servicio, aunque es una aproximacin
aceptable.

Tambin se calcularn los valores ms optimistas del rendimiento.

Estimar el rendimiento de un sistema informtico.

Cuantificar el efecto en las prestaciones de mejoras a los componentes del
sistema.

Estos lmites reciben el nombre de lmites asintticos.

Se establecen de manera sencilla.
Proporcionan una cota superior del tiempo de respuesta como de la
productividad alcanzable.

Finalmente se ver una forma sencilla de evaluar cuantitativamente el

efecto sobre las prestaciones de una mejora en el sistema.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

42

21

Estimacin del rendimiento (1/2)

Se presentarn dos algoritmos clsicos para resolver

modelos de colas sencillos.
Hiptesis:

Las hiptesis equivalen a suponer que tanto las distribucin

del tiempo de servicio como la distribucin del tiempo de
llegadas en un modelo abierto son exponenciales.

Si un trabajo est sirvindose en una estacin, el tiempo

que le falta para abandonar el servidor es independiente del
tiempo que ya lleva en servicio.
En un sistema abierto, el tiempo que transcurre hasta la
prxima llegada es independiente del instante en que se
produjo la ltima.

Debido a sus propiedades estadsticas se dice que est

distribucin carece de memoria (memoryless property).

Antes de plantear los algoritmos de resolucin

introduciremos una expresin para calcular el tiempo de
respuesta de una estacin de servicio i de tipo cola.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

43

Estimacin del rendimiento (2/2)

Ri = (Ni+1)Si

Un trabajo que llega a la estacin i encuentra Ni trabajos en ella y

esperar NiSi unidades de tiempo a que se sirvan, ms, Si para
recibir su propio tiempo de servicio.
Se est utilizando la propiedad de que el tiempo de servicio se
distribuye exponencialmente (carece de memoria), y, por tanto no
es necesario tener en cuenta el tiempo de servicio ya recibido por el
cliente que esta en el servidor cuando se produce la llegada.
La propiedad de carencia de memoria no puede ser comprobada
operacionalmente, por eso no es considerada como una ley
operacional.
Sustituyendo Ni por XiRi (Ley de Little) podemos relacionar el
tiempo de respuesta de una estacin i con su tiempo de servicio Si y
su utilizacin Ui para calcular fcilmente Ri y aplicar las leyes
operacionales vistas anteriormente.
Ri ( X i Ri 1) S i , entonces :
Si
Ri
1 X i Si
Si
Ri
1Ui

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

44

22

Estimacin del rendimiento:

Algoritmo para redes abiertas (1/2)

Los tiempos de servicio y los tiempos entre llegadas estn

distribuidos exponencialmente.
Se conocen la razn de visita Vi y el tiempo de servicio Si de las
K estaciones de la red.
Adems se supone conocida la tasa de llegada al sistema, la
que ser igual a la productividad del sistema. (se supone vlida
la hiptesis de flujo equilibrado de trabajos).
Se calcularn las variables
Para cada estacin: Xi , Ni, Ri y Ui.
Para toda la red: R y N.
Demanda de servicio: Di = ViSi
Utilizaciones: Ui = Di
Productividades Xi = Vi
Tiempos de respuesta por estacin:
Si es tipo cola: Ri = Si/(1-Ui)
Si es tipo retardo: Ri = Si

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

45

Estimacin del rendimiento:

Algoritmo para redes abiertas (2/2)

Finalmente el tiempo de respuesta del sistema se obtiene

a partir de los Ri y Vi aplicando la ley general del tiempo
de respuesta:
K

R Vi R i
i 1

El nmero de trabajos en el sistema se calcula sumando

los trabajos contenidos en todas las estaciones del
modelo:
K

N Ni
i 1

o aplicando la ley de Little al sistema completo.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

46

23

Ejemplo

Sea una red de colas abierta con dos dispositivos 1 y 2 y una

tasa de llegadas de 2 trabajos por segundo. Con los siguientes
tiempos de servicio y razones de visita:
Razn de Visita
Tiempo de servicio(seg)

Dispositivo1
6
0,01

Dispositivo2
7
0,02

Se calculan las utilizaciones:

U1 = D1= V1S1 = 260.01=0.12
U2 = D2= V2S2 = 270.02=0.28

Se calculan los tiempos de respuesta de cada estacin:

R1 = S1 /(1-U1)= 0.01/(1-0,12)=0.0114 s
R2 = S2 /(1-U2)= 0.02/(1-0,28)=0.0278 s

Finalmente el tiempo de respuesta del sistema y el nmero de

trabajos contenidos en l se calculan utilizando las relaciones:
R = V1R1 + V2R2 = 60.0114+70.0278 = 0.263 s
N = R = 20.263 = 0.526 trabajos

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

47

Estimacin del rendimiento:

Algoritmo para redes cerradas (1/3)

Tambin denominado anlisis del valor medio (MVA:

Mean-Value Analysis)
Se conocen la razn de visita Vi y el tiempo de servicio Si
de las K estaciones de la red, adems del tiempo de
reflexin Z (que ser nulo para un sistema por lotes).
Las variables a calcular son similares al caso anterior.
La diferencia estriba en que no se conoce la
productividad del sistema, sino que se ha de estimar.
Al tratarse de un modelo cerrado se conoce el nmero
de trabajos N en el sistema.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

48

24

Estimacin del rendimiento:

Algoritmo para redes cerradas (2/3)

Se emplea una ecuacin que permite estimar Ri para las

estaciones de tipo cola teniendo en cuenta que ahora su valor
depender del nmero de trabajos N en el sistema:
Ri(N) = [ Ni(N-1) + 1 ] Si
donde Ni(N-1) es el nmero de trabajos en la estacin i cuando en
la red cerrada hay (N-1) trabajos.
Esta relacin establece que el estado de la red visto por un
trabajo que est en trnsito de una estacin a otra (el
trabajo ha abandonado una estacin, pero an no se ha
incorporado a la siguiente), tiene la misma distribucin que
el estado que vera un observador aleatorio si el nmero
total de trabajo en la red fuese N-1.
Esta afirmacin es bastante intuitiva, que un trabajo en
transito no puede observarse a s mismo en ninguna
estacin.
La ecuacin anterior relaciona dos ndices de prestaciones, uno
para N y otro para N-1 dando lugar a un procedimiento de clculo
iterativo.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

49

Estimacin del rendimiento:

Algoritmo para redes cerradas (3/3)

Los valores para la primera iteracin son fciles de

establecer:
Para N=0 se cumple

Ni =0 y por tanto Ri(1)= Si para i=1, , K

Para las estaciones de tipo retardo se cumple, adems,

que Ri(N)= Si , N
As el algoritmo de resolucin tendr la siguiente forma.
Para n desde 1 hasta N hacer :

Ri ( n ) N i ( n 1) 1 S i , con N i (0) 0
K

R ( n ) Vi Ri ( n ),

X (n)

i 1

n
Z R (n)

N i ( n ) X ( n ) Vi Ri ( n )
X i ( n ) X ( n ) Vi
U i ( n ) X ( n ) Vi S i
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

50

25

Ejemplo

Sea una red cerrada con 3 trabajos y dos dispositivos, 1 y 2, que tienen los
siguientes tiempos de servicio y razones de visita.
Razn de Visita
Tiempo de servicio(seg)

Dispositivo2
14
0,5

Se supone que la carga es interactiva con un tiempo de reflexin Z=5.

Para aplicar el algoritmo hay que aplicar 4 iteraciones, una por cada trabajo
presente en el sistema.
Para cada iteracin se calcula:

El tiempo de respuesta y la productividad del sistema

El tiempo de respuesta, nmero de trabajos, la productividad y la utilizacin
de cada estacin del modelo.

Trabajos: n
1
2
3

Dispositivo1
15
0,03

R1
0,0300
0,0311
0,0317

R2
0,5000
0,7811
1,1667

R
7,4500
11,4020
16,8098

X0
0,0803
0,1219
0,1376

N1
0,0361
0,0569
0,0654

N2
0,5622
1,3335
2,2468

El tiempo de respuesta del sistema, a partir de los datos presentados en la

tabla, es de 16.8090 seg., mientras que la productividad es de 0.1376
trabajos por segundo.
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

51

Cuellos de botella

Una consecuencia de la ley del flujo forzado es que las

utilizaciones de los dispositivos son proporcionales a las
demandas totales de servicios.
Un cuello de botella es aquel dispositivo con mayor demanda de
servicio y por tanto mayor utilizacin.

Su papel resulta determinante en las prestaciones del sistema

completo.
Cuando la carga incrementa su magnitud el dispositivo que
tiende a congestionarse primero es este cuello de botella.
Cuando su utilizacin presenta valores cercanos a 1 se dice que
est saturado.

Es deseable que las utilizaciones de los distintos dispositivos

sean lo ms parecidas posible.

La mejora del comportamiento del dispositivo cuello de botella

redundar en un incremento significativo del rendimiento del
sistema completo.

Cuando esto ocurre el sistema est equilibrado (balanced system).

La mejora ser marginal cuando se haga en los restantes

dispositivos.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

52

26

Lmites asintticos

Representan una tcnica de aplicacin sencilla para

acotar, desde un punto de vista optimista, los mejores
valores de la productividad y el tiempo de respuesta de un
sistema informtico.

Se denotar al dispositivo cuello de botella del sistema

informtico mediante el subndice b.

Una vez localizado est dispositivo se cumpliran las

siguientes igualdades:
Db= mx{D1, D2, DK} = VbSb
Ub= X0Db

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

53

Lmites asintticos
Sistemas abiertos (1/2)

Como primera aproximacin al establecimiento de lmites asintticos

optimistas se considera inicialmente un modelo de colas abierto.

El valor mximo de la tasa de llegadas que el sistema puede

soportar ser aquel que sature completamente el dispositivo cuello
de botella.
Es decir Ub= 1

Como se cumple la hiptesis de flujo equilibrado de trabajos se

puede escribir:
Ub= XbSb= XoVb Sb = X0Db= Db
Sea opt el valor ms alto de la tasa de llegadas que el sistema puede
aceptar, la cual ser equivalente a la productividad del sistema, que
denotaremos por Xopt.
Particularizando la expresin anterior para Ub= 1 se tiene:
Si Ub=1

=>

XoptDb=1

=>

Xopt=1 / Db

Cuando la tasa de llegadas al sistema toma el valor =Xopt el sistema

satura el cuello de botella. El nmero de trabajos en el sistema
crece de forma indefinida, haciendo que ste se vuelva inestable.
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

54

27

Lmites asintticos
Sistemas abiertos (2/2)

Si tomamos en cuenta el tiempo de respuesta, el valor optimista

del mismo Ropt viene dado cuando un trabajo que llega al sistema
lo encuentra vaco.

El trabajo no habr de esperar en ningn dispositivo.

En este caso, el valor del tiempo de respuesta ser equivalente a
la suma de las demandas de servicio que haga a los diferentes
dispositivos del sistema.
Si el modelo tiene K estaciones:
K

Ropt Di D
i 1

Resumiendo los resultados obtenidos para el modelo abierto se

obtienen las siguientes expresiones para los lmites asintticos:

X opt D

K
R D
Di

opt

i 1
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

55

Lmites asintticos
Sistemas cerrados (1/3)

Se analizar una red de colas cerrada que modela un sistema

interactivo
Para un sistema por lotes basta con hacer Z=0.
Dado que la carga del sistema viene establecida por N, se
consideran dos situaciones:
Carga muy baja (sistema vaco: N=0)

Carga muy alta (sistema saturado, valores de N suficientemente

grandes para saturar el cuello de botella)

Supongamos que el sistema no tiene ningn dispositivo

saturado. El valor ms optimista para el tiempo de respuesta,
Ropt, es aquel que experimenta un trabajo que no tiene que
esperar en ningn dispositivo.
K

Ropt Di D
i 1

La particularizacin de la ley del tiempo de respuesta interactivo

para el valor Ropt permite obtener una expresin optimista para la
productividad:
N
N

Si

M.A.V.S. nov-10

Ropt

X opt

Z X opt

Dpto. Informtica ETSII U. Valladolid

DZ
56

28

Lmites asintticos
Sistemas cerrados (2/3)

Si ahora se considera un sistema en el cual el cuello de

botella est saturado (Ub=1) el valor ms alto que cabra
esperar para la productividad ser:
Si Ub=1 =>

Xopt =1/Db

Particularizando la expresin de la ley del tiempo de

respuesta interactivo para este valor de la productividad
se tiene:
N
Ropt

XbSb=Xopt Vb Sb =1 =>

X opt

Ropt N Db Z

Resumiendo los resultados obtenidos para el modelo

cerrado se obtienen las siguientes expresiones para los
lmites asintticos:

N
1
,
X opt mn

D Z Db
R mx D , D N Z
b
opt
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

57

Lmites asintticos
Sistemas cerrados (3/3)

El punto de interseccin de las rectas definidas por las anteriores

expresiones es: N
DZ
1

DZ

Db

Db

Al valor anterior de N se lo conoce como punto terico de

saturacin, ya que desde un punto de vista optimista y
asinttico, en el se alcanza la productividad terica ms alta del
sistema.
Si se considera el tiempo de respuesta, a partir de este valor no
se puede garantizar el tiempo mnimo establecido por D por que
los trabajos en el sistema experimentan esperas en los
dispositivos, al menos en el cuello de botella.
Como el nmero de trabajos en el sistema viene dado por un
nmero entero, en la prctica el valor anterior se suele expresar
como un valor entero.

D Z
N*

Db

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

58

29

Ejemplo

Sea un modelo de sistema basado en el servidor central con una

carga de tipo interactivo.
Los trabajos tienen un tiempo medio de reflexin de 6 segundos.
La red de colas tiene tres dispositivos: un procesador y dos discos.
Las razones de visita y tiempos de servicio se indican en la
siguiente tabla.
Dispositivo
Procesador (1)
Disco (2)
Disco (3)

Razn de Visita Tiempo de servicio

32
0,0375
25
0,02
6
0,05

Se calculan las demandas de servicio:

D1 = V1S1=320.0375=1,2 s
D2 = V2S2=250.02=0.5 s
D3 = V3S3=60.05=0.3 s
Es evidente que el cuello de botella es el procesador.

Supera con diferencia las demandas de servicio de los discos.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

59

Ejemplo

La demanda total del sistema es la suma de las demandas

de los dispositivos
D = D1+D2+D3 =1,2 s + 0,5 s + 0,3 s = 2 s

Si se calculan los lmites asintticos de rendimiento se

obtiene:

N
1
N

,
X opt mn
mn , 0 .833
8

D Z Db
R mx D , D N Z mx 2, 1 .2 N 6
b
opt

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

60

30

Ejemplo
40,0
35,0

Tiempo de Respuesta

30,0
25,0

R
D=2
1,2N-6

20,0

0,5N-6
0,3N-6

15,0
10,0
5,0
0,0
1

11

16

21

26

31

Trabajos en el sistem a

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

61

Ejemplo
4,0
3,5

Productividad

3,0
X0

2,5

N/8

2,0

1/1,2
1/0,5

1,5

1/0,3

1,0
0,5

34

31

28

25

22

19

16

13

10

0,0

Trabajos en el Sistem a

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

62

31

Mejora del rendimiento

Debido a la multitud de factores que influyen en el rendimiento de

un sistema informtico la mejora del rendimiento es una tarea
compleja.
La solucin ms sencilla al problema de mejora de rendimiento
ser la localizacin del cuello de botella del sistema y realizar
actuaciones sobre l.
La primera aproximacin consiste en actuar sobre los
componentes fsicos del mismo, mejorndolos o incrementando su
nmero (upgradign techniques).

La adicin de nuevos componentes puede suponer una gran

inversin o el reemplazo puede ser complicado.

La segunda tcnica (ajuste o sintonizacin: tunning techniques)

engloba todas las acciones realizadas sobre los programas que se
ejecutan en el ordenador para mejorar el uso que hacen de los
dispositivos.

Su aplicacin depende del grado de conocimiento del programa a

modificar como del comportamiento e interaccin del mismo con
los dispositivos fsicos del sistema. Siempre y cuando los
programas sean susceptibles de modificacin o ajuste.

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

63

Ejemplo

Para mejorar el sistema del ltimo ejemplo se debe actuar

sobre el procesador.

Qu pasar si se sustituye por una unidad dos veces ms

rpida?

Se reduce el tiempo de servicio de 0,0375 a 0,0175.

La nueva demanda de servicio es
D1 = V1S1=320.001875=0.6 s
Aunque se ha reducido a la mitad, an es el dispositivo con
la demanda ms alta del sistema.
Los nuevos lmites asintticos sern:

N
1
N

,
, 1 .667
X opt mn
mn
7 .4

D Z Db
R mx D , D N Z mx 1 .4, 0 .6 N 6
b
opt
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

64

32

Ejemplo (cont.)
40,0
35,0

Tiempo de Respuesta

30,0
25,0

R
D=2
1,2N-6

20,0

0,5N-6
0,3N-6

15,0
10,0
5,0

40,0

0,0
1

11

16

21

26

31

Trabajos en el sistem a

35,0

Tiempo de Respuesta

30,0
R

25,0

D=1,4
0,6N-6

20,0

0,5N-6
15,0

0,3N-6

10,0
5,0
0,0
1

11

16

21

26

31

Trabajos en el sistem a

M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

65

Ejemplo (cont.)
4,0
3,5

X0

2,5

N/8
1/1,2

2,0

1/0,5

1,5

1/0,3

1,0
0,5

4,0

34

31

28

25

22

19

16

13

10

0,0

Trabajos en el Sistem a

3,5
3,0
Productividad

Productividad

3,0

X0

2,5

N/7,4
1/0,6

2,0

1/0,5

1,5

1/0,3

1,0
0,5
0,0
1

11

16

21

26

31

Trabajos en el Sistem a
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

66

33

Ejemplo (cont.)

Se puede observar que el tiempo de respuesta mnimo y la

productividad mxima han mejorado. Las asntotas del cuello de
botella se han desplazado.

La asntota D del sistema original ha pasado de 2 a 1,4 segundos.

La asntota del cuello de botella que pasa de 1,2N-6 a 0,6N-6 la
pendiente pasa a valer la mitad.
Si se analiza la evolucin de la productividad, cuyo valor mximo
ha crecido de 1/1,2=0.833 a 1/0,6=1.667.
Las asntotas de los discos han permanecido iguales.

El punto terico de saturacin ha mejorado sensiblemente

pasando de 7 a 13 trabajos.
D Z 1 .4 6
N*

12 .33 13
Db 0 .6

Si la mejora del procesador hubiese sido de un factor de 3,

entonces su demanda hubiera pasado a valer 0.4 segundos, valor
por debajo de la demanda del primer disco: Ese disco sera el
nuevo cuello de botella.
M.A.V.S. nov-10

Dpto. Informtica ETSII U. Valladolid

67

34