Ao del Centenario de Machu Picchu para el mundo
TRABAJO DE INVESTIGACION
15 de Julio 2011
SISTEMAS DISTRIBUIDOS DOCENTE: - Ing. EdwingMaquera INTEGRANTES:
- Carmen Mara Chino cervantes - Jaime Molina Calzina UNIVERSIDAD
NACIONAL DE MOQUEGUE Ing. Sistemas e Informtica VII
2
ING. SISTEMAS E INFORMATICA - VII
OPTIMIZACIN DE OPERACIONES DE BSQUEDA EN DISCO CON REDES
NEURONALES
1. INTRODUCCION El Estudio de la Optimizacin de Operaciones de
Bsqueda en Disco con Redes Neuronales, lo desarrollaremos
utilizando el software Mathematica, como herramienta para el clculo
numrico y el clculo simblico. Las operaciones de acceso a disco,
consecuencia de los requerimientos de lectura y/o grabacin que
efectan al S.O. los distintos procesos, son la causa de
considerables demoras en los tiempos de respuesta. Asimismo, si
consideramos cmo se compone el tiempo de acceso a disco,
encontramosque el mismo est integrado por el tiempo de bsqueda
(movimiento del mecanismo deacceso que contiene el cabezal de
lectura / grabacin hasta posicionarse en el cilindroque contiene a
la pista que aloja al registro que se debe acceder), el tiempo de
demorarotacional o latencia (tiempo que demora la rotacin del disco
hasta que el registro que sepretende acceder queda bajo el cabezal
de lectura / grabacin, previamente posicionadoen el cilindro que
aloja a la pista correcta) y el tiempo de transferencia de la
informacinpropiamente dicha (lectura o grabacin). 2. Optimizacin de
la Bsqueda en Discos Las estrategias ms comunes de optimizacin de
la bsqueda son las siguientes: FCFS. SSTF. SCAN. SCAN de N - Pasos.
C - SCAN. Esquema Eschenbach. Planificacin FCFS (Primero en Llegar,
Primero en Ser Servido) Una peticin no puede ser desplazada por la
llegada de una peticin con prioridad msalta. No hay reordenamiento
de la cola de peticiones pendientes. Se ignoran las relaciones
posicionales entre las peticiones pendientes. Ofrece una varianza
pequea aunque perjudica a las peticiones situadas al final de
lacola.
Veamos un ejemplo para explicar cmo el algoritmo FCFS:
SISTEMAS DISTRIBUIDOS
3
ING. SISTEMAS E INFORMATICA - VII
Asumimos la siguiente situacin: Un cabeza dura de mvil con 200
cilindros, numerados del 0 a 199, donde,
Posicin de la cabeza: 53 Cola: 95, 175, 32, 117, 15, 131, 47,
56
Como podemos ver en la imagen para determinar el movimiento de
carga total para satisfacer las peticiones de la cola se encuentra
a 661 cilindros. Esto se calcula sumando el desplazamiento de la
cabeza entre las aplicaciones ejecutadas. Por lo tanto,
De 53 a 95 hay un movimiento de 42 cilindros. De 95 a 175 hay un
movimiento de 80 cilindros. De 32 a 175 hay un movimiento de 143
cilindros. De 32 a 117 hay un movimiento de 85 cilindros. De 15 a
117 hay un movimiento de 102 cilindros. De 15 a 131 hay un
movimiento de 116 cilindros. De 47 a 131 hay un movimiento de 84
cilindros. Entre 47 y 56 hay un movimiento del cilindro 9.
As, la adicin de los movimientos parciales de la cabeza calcula
el movimiento de la cabeza total: Movimiento de carga total =
42+80+143+ 85+ 102+116+84+9 = 661cilindros.
Como podemos ver en la imagen de este algoritmo presenta un
recorrido total ms alto (en el ejemplo tenemos el total de los
movimientos de la cabeza tener el
SISTEMAS DISTRIBUIDOS
4
ING. SISTEMAS E INFORMATICA - VII
valor de 661 cilindros) y los movimientos bruscos, pero tiene
una implementacin ms sencilla.
Planificacin SSTF (Menor Tiempo de Bsqueda Primero) El brazo del
disco se sita en la siguiente peticin que minimice el movimiento
del brazo. No respeta el orden de llegada de las peticiones a la
cola. Tiende a favorecer a las pistas del centro del disco. La
media de tiempos de respuesta tiende a ser ms baja que con FCFS,
para cargasmoderadas. Las varianzas tienden a ser mayores que con
FCFS por el efecto de las pistas interioresy exteriores. Veamos un
ejemplo para explicar cmo funciona el algoritmo SSTF:
Asumimos la siguiente situacin: Un cabeza dura de mvil con 200
cilindros, numerados del 0 a 199, donde,
Posicin de la cabeza: 53 Cola: 95, 175, 32, 117, 15, 131, 47,
56
Como podemos ver en la imagen para determinar el movimiento de
carga total para satisfacer las peticiones de la cola se establece
en 204 cilindros. Esto se calcula sumando el desplazamiento de la
cabeza entre las aplicaciones ejecutadas. Por lo tanto,
SISTEMAS DISTRIBUIDOS
5
ING. SISTEMAS E INFORMATICA - VII
De 53 a 56 hay un movimiento de 3 cilindros. 56 a 47 hay un
movimiento del cilindro 9. De 47 a 32 hay un movimiento de 15
cilindros. 32 a 15 hay un movimiento de 17 cilindros. De 15 a 95
hay un movimiento de 80 cilindros. De 95 a 117 hay un movimiento de
22 cilindros. De 117 a 131 hay un movimiento de 14 cilindros. De
131 a 175 hay un movimiento de 44 cilindros.
As, la adicin de los movimientos parciales de la cabeza calcula
el movimiento de la cabeza total: Movimiento de carga total = 3+ 9+
15+ 17+ 80+ 22+ 14+ 44 = 204cilindros. Como podemos ver en la
imagen de este algoritmo tiene una ruta de baja total (en el
ejemplo tenemos el total de los movimientos de la cabeza tener el
valor de los cilindros de 204), pero la cabeza oscila en la zona
central que se puede presentar con el hambre, desde la entrada en
la cola de inscripciones vence el que se est ejecutando puede
causar un retraso indefinido a las solicitudes que no se cierren se
est ejecutando.
Planificacin SCAN El brazo del disco se desplaza sirviendo a
todas las peticiones que encuentra a su paso. Cambia de direccin
cuando ya no hay peticiones pendientes en la direccin actual. Ha
sido la base de la mayora de las estrategias de planificacin
implementadas. Elimina las discriminaciones de SSTF y tiene menor
varianza. Las pistas exteriores son menos visitadas que las
intermedias, pero no es tan gravecomo con SSTF. Planificacin SCAN
de N Pasos La estrategia de movimiento del brazo es como en SCAN;
solo da servicio a las peticionesque se encuentran en espera cuando
comienza un recorrido particular. Las peticiones que llegan durante
un recorrido son agrupadas y ordenadas y sernatendidas durante el
recorrido de regreso. Posee menor varianza de los tiempos de
respuesta si se compara con las planificacionesSSTF y SCAN
convencionales. Veamos un ejemplo para explicar cmo funciona el
algoritmo de escaneo:
SISTEMAS DISTRIBUIDOS
6
ING. SISTEMAS E INFORMATICA - VII
Asumimos la siguiente situacin: Un cabeza dura de mvil con 200
cilindros, numerados del 0 a 199, donde,
Posicin de la cabeza: 53 Cola: 95, 175, 32, 117, 15, 131, 47, 56
Significado de la bsqueda: disminucin del nmero de cilindros (de
derecha a izquierda)
Como podemos ver en la imagen para determinar el movimiento de
carga total para satisfacer las peticiones de la cola se encuentra
a 228 cilindros. Esto se calcula sumando el desplazamiento de la
cabeza entre las aplicaciones ejecutadas. Por lo tanto,
De 53 a 47 hay un movimiento de 6 cilindros. De 47 a 32 hay un
movimiento de 15 cilindros. 32 a 15 hay un movimiento de 17
cilindros. 15 a 0, porque tenemos que llegar al final del disco,
hay un movimiento de 15 cilindros. De 0 a 56 produce un movimiento
de 56 cilindros. 56 a 95 hay un movimiento de 39 cilindros. De 95 a
117 hay un movimiento de 22 cilindros. De 117 a 131 hay un
movimiento de 14 cilindros. De 131 a 175 hay un movimiento de 44
cilindros.
As, la adicin de los movimientos parciales de la cabeza calcula
el movimiento de la cabeza total:
SISTEMAS DISTRIBUIDOS
7
ING. SISTEMAS E INFORMATICA - VII
Movimiento de carga total = 6+ 15+ 17 +15+ 56+ 39+ 22+ 14+ 44 =
228cilindros. Como podemos ver en la imagen de este algoritmo tiene
una ruta de baja total (en el ejemplo tenemos el total de los
movimientos de la cabeza tener el valor de 228 cilindros), castiga
a los extremos, pero tiene hambre, ya que el algoritmo determina
una direccin de bsqueda.
Planificacin C - SCAN (Bsqueda Circular) El brazo se mueve del
cilindro exterior al interior, sirviendo a las peticiones sobre
unabase de bsqueda ms corta. Finalizado el recorrido hacia el
interior, salta a la peticin ms cercana al cilindroexterior y
reanuda su desplazamiento hacia el interior. No discrimina a los
cilindros exterior e interior. La varianza de los tiempos de
respuesta es muy pequea. Veamos un ejemplo para explicar cmo
funciona el algoritmo C-Scan:
Asumimos la siguiente situacin: Un cabeza dura de mvil con 200
cilindros, numerados del 0 a 199, donde,
Posicin de la cabeza: 53 Cola: 95, 175, 32, 117, 15, 131, 47, 56
Sentido de la investigacin: aumento del nmero de cilindros (de
izquierda a derecha)
SISTEMAS DISTRIBUIDOS
8
ING. SISTEMAS E INFORMATICA - VII
Como podemos ver en la imagen para determinar el movimiento de
carga total para satisfacer las peticiones de la cola se encuentra
a 390 cilindros. Esto se calcula sumando el desplazamiento de la
cabeza entre las aplicaciones ejecutadas. Por lo tanto,
De 53 a 56 hay un movimiento de 3 cilindros. 56 a 95 hay un
movimiento de 39 cilindros. De 95 a 117 hay un movimiento de 22
cilindros. De 117 a 131 hay un movimiento de 14 cilindros. De 131 a
175 hay un movimiento de 44 cilindros. De 175 a 199, debe alcanzar
el final del disco, hay un movimiento de 22 cilindros. De 0 a 199,
entonces tenemos que volver al primer cilindro, hay un movimiento
de 199 cilindros. De 0 a 15 hay un movimiento de 15 cilindros. 15 a
32 hay un movimiento de 17 cilindros. 32 a 47 hay un movimiento de
los cilindros de 15
As, la adicin de los movimientos parciales de la cabeza calcula
el movimiento de la cabeza total: Movimiento de carga total = 3+
39+ 22+ 14+ 44+ 22+ 199+ 15+ 17 +15 = 390cilindros. Como podemos
ver en esta imagen presenta el mismo algoritmo para escanear un
itinerario completo ms abajo, pero una mayor exploracin en contra
(en el ejemplo tenemos el total de los movimientos de la cabeza
tener el valor de 390 cilindros). As que tambin penaliza a los
extremos, pero el hambre no est presente, entonces el algoritmo
determina una direccin de bsqueda.
Esquema Eschenbach El brazo del disco se mueve como en C - SCAN,
pero: Las peticiones se reordenan para ser servidas dentro de un
cilindro para tomar ventajade la posicin rotacional. Si dos
peticiones trasladan posiciones de sectores dentro de un cilindro,
solo se sirveuna en el movimiento actual del brazo del disco. Esta
estrategia tiene en cuenta el retraso rotacional. Conclusiones
SISTEMAS DISTRIBUIDOS
9
ING. SISTEMAS E INFORMATICA - VII
Mediante trabajos de simulacin y de laboratorio se demostr lo
siguiente: La estrategia SCAN es la mejor con carga baja. La
estrategia C - SCAN es la mejor con cargas medias y pesadas. La
estrategia C - SCAN con optimizacin rotacional es la mejor para
cargas muypesadas (mejor que la estrategia Eschenbach
inclusive).
3. INTELIGENCIA ARTIFICIAL La Inteligencia Artificial tiene en
comn la creacin de mquinas que pueden "pensar". La Inteligencia
Artificial incluye varios campos de desarrollo tales como: La
robtica que interviene en los procesos de fabricacin Comprensin de
lenguajes y traduccin; visin en mquinas que distinguen formas y que
se usan en lneas de ensamblaje; reconocimiento de palabras y
aprendizaje de mquinas; sistemas computacionales expertos.
La Inteligencia Artificial est dividida en varias reas de
estudio, como por ejemplo: Robtica, Lenguaje Natural, Razonamiento
Lgico, Habla, Redes Neurales, Visin, y Sistemas Expertos. Los
investigadores en inteligencia artificial se concentran
principalmente en los sistemas expertos, la resolucin de problemas,
redes neuronales, el control automtico, las bases de datos
inteligentes y la ingeniera del software (diseos de entornos de
programacin inteligente). Otros investigadores estn trabajando en
el reto del reconocimiento de patrones donde se espera un rpido
progreso en este campo que abarca la comprensin y la sntesis del
habla, el proceso de imgenes y la visin artificial. 4. REDES
NEURONALES Las redes neuronales son una rama de la Inteligencia
Artificial. - Una red neuronal es "un nuevo sistema para el
tratamiento de la informacin, cuya unidad bsica de procesamiento
est inspirada en la clula fundamental del sistema nervioso humano:
la neurona". - Las neuronas son un componente relativamente simple
pero conectadas de a miles forman un poderoso sistema. - Unidades
de procesamiento que intercambian datos o informacin. - Se utilizan
para reconocer patrones, incluyendo imgenes, manuscritos,
tendencias financieras, etc. - Tienen la capacidad de aprender y
mejorar su funcionamiento. Fundamentos - El modelo biolgicoSISTEMAS
DISTRIBUIDOS
10
ING. SISTEMAS E INFORMATICA - VII
-
El cerebro humano contiene ms de cien mil millones de neuronas.
La clave para el procesamiento de la informacin son las conexiones
entre ellas llamadas sinpsis.
Modelo matemtico de la neurona Neurona de una entrada
Otra entrada 1, que se multiplica por un sesgo (offset) b,
tambin va al sumador. La entrada escalar p se multiplica por el
peso escalar w para formarwp, un trmino que entra al sumador. La
salida del sumador n, que se conoce como entrada de red va a la
funcin de transferencia f (funcin de activacin), la cual produce la
salida escalar a de la neurona. El peso w se corresponde con el
efecto de la sinpsis, el cuerpo de la clula se representa por la
sumatoria y la funcin de transferencia, y la salida a de la neurona
representa la seal sobre el axn. La salida depende de la funcin de
transferencia que se escoja.
SISTEMAS DISTRIBUIDOS
11
ING. SISTEMAS E INFORMATICA - VII
El sesgo b es un peso con una entrada constante de valor 1, ( se
puede omitir). W y b son los parmetros ajustables de la neurona. La
funcin de transferencia la escoge el diseador.
UNA NEURONA
5. CASOS DE ESTUDIOS
Del libro: SISTEMAS OPERATIVOS Magister David Luis la Red
Martnez Objetivo del Caso de Estudio Conforme a lo antes indicado,
el objetivo del caso de estudio desarrollado fue el de programar un
paquete con Mathematica (Colas3pn.m) que implementara los
principales algoritmos de bsqueda y que permitiera generar archivos
para entrenamiento y testeo de redes neuronales (Colas3en.ma y
Colas3fn.txt) y posteriormente efectuar comparaciones entre los
distintos modelos y herramientas de redes utilizados. El paquete
desarrollado con Mathematica permite analizar un conjunto de
requerimientos con tres algoritmos de bsqueda distintos, calculando
para cada uno de ellos la cantidad de movimientos del mecanismo de
acceso (nmero de cilindros del disco recorridos por el mecanismo de
acceso) y sealando en cada caso cul es el ms adecuado segn el
criterio indicado de minimizar los movimientos; adems de desplegar
los datos y resultados en pantalla, el paquete genera un archivo de
texto que permite entrenar y testear las redes neuronales, teniendo
presente que se trata de un problema de clasificacin.
SISTEMAS DISTRIBUIDOS
12
ING. SISTEMAS E INFORMATICA - VII
Descripcin de los Algoritmos Utilizados
FCFS: Las operaciones requeridas se atienden segn el orden de
llegada de los requerimientos. SSF: Las operaciones requeridas se
atienden dando prioridad a las que significan menos movimiento
(salto de cilindros) del mecanismo de acceso. SCAN o del Elevador:
Las operaciones requeridas se atienden dando prioridad a las que
significan menos movimiento del mecanismo de acceso, pero
respetando el sentido del movimiento del mismo (desde los cilindros
(conjuntos de pistas homnimas) de direccin ms alta hacia los
cilindros de direccin ms baja, o viceversa).
Programa Desarrollado El paquete de Mathematica desarrollado se
encuentra en el archivo Colas3pn.m y posee las siguientes
caractersticas: Se lo puede invocar utilizando, por ejemplo, el
archivo Colas3en.ma que recibe como entradas los datos referidos
a:
Nmero de cilindros del dispositivo de disco que se simular.
Total de peticiones que se evaluarn en cada ciclo, es decir el
nmero mximo de peticiones que se pueden encolar para ser luego
atendidas segn algn algoritmo de bsqueda. Nmero de ciclos que se
evaluarn, es decir nmero de registros que tendr el archivo
generado.
Es necesario sealar adems que las peticiones de acceso a
determinadas pistas del disco se expresan por el nmero del cilindro
al que pertenece la pista, siendo estos requerimientos generados
(por el paquete) al azar, al igual que el nmero que determina la
posicin inicial del mecanismo de acceso antes de atender las
peticiones de cada ciclo. Respecto del archivo generado, el mismo
tendr un tamao variable segn los datos que se hayan suministrado al
paquete que lo produce, siendo posible efectuar la generacin del
archivo en varias etapas, es decir en sucesivas ejecuciones del
paquete, en cuyo caso y por una simple cuestin de estructura de los
datos, el nmero de cilindros y el nmero de peticiones por ciclo
debern ser los mismos, ya que de lo contrario el archivo generado
no podr ser utilizado para el entrenamiento y testeo de las redes
directamente por no ser homogneo, sino que habra que segmentarlo
con algn editor previamente.
SISTEMAS DISTRIBUIDOS
13
ING. SISTEMAS E INFORMATICA - VII
El cdigo del programa desarrollado (Colas3pn.m) es el siguiente:
(* ALGORITMOS DE BUSQUEDA EN DISCO *) (* Clculo del nmero de
cilindros del disco recorridos por el mecanismo de acceso en las
operaciones de bsqueda de los cilindros requeridos segn las
peticiones de entrada / salida que precisan los procesos; generacin
del archivo de resultados correspondiente *) (* Caso 1: Algoritmo
FCFS: Las operaciones requeridas se atienden segn el orden de
llegada de los requerimientos. *) (* Caso 2: Algoritmo SSF: Las
operaciones requeridas se atienden dando prioridad a las que
significan menos movimiento (salto de cilindros) del mecanismo de
acceso. *) (* Caso 3: Algoritmo SCAN o del Elevador: Las
operaciones requeridas se atienden dando prioridad a las que
significan menos movimiento del mecanismo de acceso, pero
respetando el sentido del movimiento del mismo (desde los cilindros
(conjuntos de pistas homnimas) de direccin ms alta hacia los
cilindros de direccin ms baja, o viceversa. *) (* Referencias y
aclaraciones: cildisc: Total de cilindros en el disco. peticalea:
Lista de cilindros involucrados en las peticiones, segn el orden de
llegada de las mismas. totpetic: Total mximo de peticiones en una
lista de peticiones. posinit: Posicin inicial del mecanismo de
acceso. numpetic: Nmero de listas de peticiones. tfcfs: Total de
cilindros recorridos por el mecanismo de acceso segn planificacin
FCFS. tssf: Total de cilindros recorridos por el mecanismo de
acceso segn planificacin SSF. tscan: Total de cilindros recorridos
por el mecanismo de acceso segn planificacin SCAN. *)
BeginPackage[Colas3pn] Colas3pn::usage=
Colas3pn[cildisc,totpetic,numpetic]; Clculo del nmero de cilindros
del disco \n recorridos por el mecanismo de acceso en las \n
operaciones de bsqueda de los cilindros \n requeridos segn las
peticiones de entrada \n salida que precisan los procesos;
generacin \nSISTEMAS DISTRIBUIDOS
14
ING. SISTEMAS E INFORMATICA - VII
del archivo de resultados correspondiente. \n Colocar los
valores para cildisc, totpetic y \n numpetic.
Colas3pn[incildisc_,intotpetic_,innumpetic_]:=
Colas3pnAux[incildisc,intotpetic,innumpetic];
Colas3pnAux[incildisc_,intotpetic_,innumpetic_]:= Module[{tfcfs,
tssf, tscan, fcfs, ssf, scan, peticalea, posinit, result,
resultclas, peticiones, peticaux, movmin, indice, posinitaux},
Caso3[cildisc_,totpetic_,numpetic_]:= (posinit=Random[Integer, {1,
cildisc}]; peticalea=Table[Random[Integer, {1, cildisc}],
{totpetic}]; tfcfs=0; tssf=0; tscan=0; fcfs=0; ssf=0; scan=0;
indice=0; (* Clculo para FCFS *) tfcfs=Abs[peticalea[[1]]-posinit];
For[j=2, j
