PDF de programación - Desarrollo de Applets Para la Simulación de Algoritmos de Administración del Sistema Operativo

Universidad Nacional del Nordeste

Facultad de Ciencias Exactas y Naturales y

Agrimensura

Monografía de Adscripción

Asignatura: Sistemas Operativos



Desarrollo de Applets Para

la Simulación de

Algoritmos de

Administración del Sistema

Operativo



APELLIDO Y NOMBRE: Rodríguez Nelson Fabián

L.U: 32945

PROF. DIRECTOR: David Luis La Red Martínez

LICENCIATURA EN SISTEMAS DE INFORMACIÓN

Corrientes - Argentina

2009



Análisis del Rendimiento de un Subsistema de

Disco de Una Petición a la Vez



Introducción

Este trabajo práctico de Adscripción consiste en la investigación, análisis y desarrollo de

los diferentes casos de estudio propuestos en el SistOper, se han desarrollados applets

utilizando el lenguaje Java y como IDE a NetBeans, una poderosa herramienta para el

desarrollo de aplicaciones orientadas a objetos y el desarrollo de applets para su utilización

en Internet.

Los casos de estudio desarrollados fueron: Análisis del Rendimiento de un Subsistema de

Disco de Una Petición a la Vez,, Análisis del Rendimiento de un Subsistema de Disco de

Varias Peticiones a la Vez; este informe consta de un marco teórico de cada caso de

estudio, el código desarrollado y cada una de las ventanas de los applets.



Objetivo del Caso de Estudio

El objetivo del presente caso consistió en la realización de un programa en JAVA que
implementara el algoritmo de análisis de rendimiento para el caso señalado.
Asimismo también se estableció como objetivo del caso la inclusión en el programa de la
posibilidad de generar información detallada respecto de los cálculos efectuados con las
distintas simulaciones y un análisis estadístico de los resultados logrados, como así también
un gráfico ilustrativo de los mismos.


Descripción del problema planteado


Si existe una población de clientes que demandan cierto servicio prestado por servidores:


Algunos clientes ingresaran a la red de colas y esperaran que un servidor quede
disponible.


Algunas colas son:


Ilimitadas: pueden crecer tanto como sea necesario para contener a los clientes que
esperan.

Limitadas: solo pueden contener un número fijo de clientes en espera y quizás hasta
ninguno.


Se deben tener en cuenta variables aleatorias que pueden ser descritas por distribuciones
probabilísticas.
La variable aleatoria “q” representa el tiempo que emplea un cliente esperando en la cola a
ser servido.
La variable aleatoria “s” representa la cantidad de tiempo que emplea un cliente en ser
servido.
La variable aleatoria “w” representa el tiempo total que emplea un cliente en el sistema de
colas: “w = q + s”.

Fuente.
Los clientes son proporcionados a un sistema de colas desde una fuente que puede ser
infinita o finita.
Con una fuente infinita la cola de servicio puede llegar a ser arbitrariamente grande.
Para una fuente finita la cola de servicio es limitada.
Una fuente finita pero muy grande suele considerar como infinita.

Llegadas.
Supondremos que los clientes llegan a un sistema de colas
En los tiempos:
t0 < t1 < t2< ... < tn.
Los clientes llegan de uno en uno y nunca hay una colisión.

Las variables aleatorias “ τκτκτκτκ”” miden los tiempos entre las llegadas sucesivas (arbitrario) y
se denominan tiempos entre
Llegadas:
Son variables aleatorias independientes y están
Idénticamente distribuidas.
ττττκκκκ = tk - tk-1 (k (k ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ 1). 1).

Llegadas de poisson.
Las llegadas pueden seguir distintos patrones arbitrarios
Pero suele suponerse que forman un proceso de llegadas de poisson:


 Los tiempos entre llegadas están distribuidos exponencialmente:


P( τ ≤ τ ≤ τ ≤ τ ≤ tt) = 1- e-λλλλt t


 La probabilidad de que lleguen exactamente n clientes en cualquier intervalo de

longitud t es:
[e -λλλλt t (λ λ λ λ λλλλt) t) n ] / n! (n = 0, 1, 2, ...).

λ λ λ λ es una tasa promedio de llegadas constante expresada en “clientes por unidad de
tiempo”.




 El número de llegadas por unidad de tiempo se dice que tiene distribución de

poisson con una media λ.λ.λ.λ.


Tiempos de servicio.
Se supone que los tiempos de servicio son aleatorios.

“s k ” es el tiempo de servicio que el k-esimo cliente requiere del
Sistema.

Un tiempo de servicio arbitrario se designa por “s”.

La distribución de los tiempos de servicio es:


 Ws (t) = p (s ≤≤≤≤ t).



Para un servicio aleatorio con una tasa promedio de servicio “ µµµµ ”:


 Ws (t) = p(s ≤ ≤ ≤ ≤ t) = 1-e-µµµµ t (t ≥ ≥ ≥ ≥ 0).


Capacidad de la cola.
Las colas deben tener:

Capacidad infinita:

o Cada cliente que llegue puede entrar en el sistema de colas y esperar,

independientemente de cuantos clientes hay en espera.

Capacidad cero (o sistemas de pérdidas):

o Los clientes que llegan cuando la instalación de servicio está ocupada no

podrán ser admitidos el sistema.

Capacidad positiva:

o Los clientes que llegan solo esperan si hay lugar en la cola.

Numero de servidores en el sistema.
Los sistemas de colas se pueden categorizar según el número de
Servidores en:

Sistemas de un solo servidor:

o Tienen un solo servidor y nada mas pueden darle servicio a un solo cliente a

la vez.

Sistemas de servidores múltiples:

o Tienen “c” servidores con idéntica capacidad y pueden dar servicio a “c”

clientes a la vez.



RESUMEN DEL PROCESO DE POISSON

Se define “p(k,t)” como la probabilidad de exactamente “k” llegadas en un intervalo de
tiempo de longitud “t”.
Un proceso es de poisson si y solo si:



Para intervalos apropiadamente pequeños ∆ ∆ ∆ ∆ ∆∆∆∆t: t:

 P(k,t) = :

• λ∆λ∆λ∆λ∆ t para k = 1 ( λλλλ es la tasa promedio de llegadas).
• 1 - λ∆λ∆λ∆λ∆. T para k = 0.
• 0 para k > 1.


Cualesquiera eventos definidos para tener lugar en intervalos de tiempo no superpuestos
son mutuamente independientes.
Un proceso también es de poisson si los tiempos entre llegadas sucesivas (tiempos entre
llegadas de primer orden):
Son variables aleatorias exponenciales idénticamente distribuidas.
Si la variable aleatoria “k” indica el número de llegadas:
La probabilidad de, exactamente, “k” llegadas en un intervalo de longitud “t” es:


• P(k,t) = [(λ λ λ λ λλλλt) t) k e e -λ λ λ λ λλλλt t ] / k! t ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ 00; k = 0, 1, 2, ...


El valor esperado o valor medio de k es:


• E(k) = λ λ λ λ λλλλt. t.


La varianza de k es:


•

(σ(σ(σ(σκ κ κ κ ) ) ) ) 2 2 2 2 = λ= λ= λ= λt. t.


de poisson aleatorias independientes “x” e “y” tambi

también describen

La suma de dos variables de po
un proceso de poisson:
Los valores esperados son:


• E(y) = µµµµ2 = λλλλ2222 t.
• E(x) = µµµµ 1 = λλλλ1 1 1 1 t.



La probabilidad de “k” llegadas


egadas en el tiempo “t” es:



La suma de “n” procesos de p
una tasa de llegada:


s de poisson independientes resulta en un proceso de

eso de poisson con



Para un proceso de poisson c

son con una tasa de llegada “ λλλλ ” se puede form

formar un nuevo

proceso de poisson utilizando

ndo borradas aleatorias independientes:

Cada llegada al proceso

oceso original:

 Se acepta al nuev

al nuevo proceso con probabilidad “p”.

 Se rechaza con p

con probabilidad “1 - P”.

La tasa de llegada del n

del nuevo proceso derivado es “λ λ λ λ λ λ λ λ P”.

La generalización para la des

la descomposición de un proceso de poisson en “

en “n” procesos

derivados independientes, cada

, cada uno con una probabilidad asociada “pi” resulta:
sulta:


En un proceso de poisson:



La probabilidad de que no haya

o haya llegadas en un intervalo de longitud “t” es:



 P(0,t) = [(λ λ λ λ λ λ λ λ

t) 0 e - λλλλ t ] / 0! = e -λλλλ t .



La probabilidad de una o más ll

más llegadas en un intervalo de longitud “t” es:



 1 - P(0,t) = 1 - e

e - - λλλλ t .


La función de densidad de pr
(tiempo hasta la primera llegad
f t (t) = λλλλ e-λλλλt t (t (t ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ 0). 0).
El valor esperado “t” es:

egada) es:

de probabilidad para el tiempo entre llegadas de p

de primer orden

 E(t) = 1 / λ. λ. λ. λ. λ.λ.λ.λ.


La varianza es:



(σ(σ(σ(σt ))))2222 = 1 / λ
= 1 / λ2.
= 1 / λ
= 1 / λ

La función de densidad de pro
(tiempo hasta la r-esima llegad


gada) es:

de probabilidad para el tiempo entre llegadas de o

e orden r-esimo



ft(t) = λλλλr t r--1 e

e -λλλλt t ) / (r - - 1)! (t ≥ ≥ ≥ ≥ 0, r = 1, 2, ...)

El valor esperado “t” es:


 E(t) = r /λ.λ.λ.λ.
La desviación estándar es:


(σ(σ(σ(σ t )))) 2222 ====r / λ/ λ/ λ/ λ2.






Las instalaciones de servicio pueden proporcionar tiempos de servicio exponenciales:


La probabilidad de que el tiempo de servicio sea menor o igual a “t” es:


 P(S ≤ ≤ ≤ ≤ t) = 1-e - µµµµt t (t (t ≥ ≥ ≥ ≥ 0).


La tasa promedio de servicio es “ µµµµ.”.

El tiempo promedio de servicio es “1 / µµµµ”. ”.

La función de densidad de probabilidad para el tiempo de servicio “t” es:


ft(t) = µe -µt t (t (t ≥ 0).




La media del tiempo de servicio es:

 E(s) = 1 / µ.µ.µ.µ.


La varianza es “1 / µµµµ2222 ”.


Un servidor que opera de esta manera se denomina servidor exponencial.



Descripción del algoritmo desarrollado



Se supone la siguiente situación:

Las peticiones de acceso a disco llegan como un proceso de poisson con una tasa promedio

de λ λ λ λ peticiones por minuto.

Si el disco está en uso, la petición se coloca en una cola primero en llegar, primero en ser

servido.

Cuando el disco queda disponible se sirve la primera petición de la cola.

El tiempo de ser