Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

TEMA 4. MODELADO DE ALGORITMOS DEPAGINACIÓN

No description
by

Omar Torres

on 11 July 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of TEMA 4. MODELADO DE ALGORITMOS DEPAGINACIÓN

Modelado de algoritmos de paginación
Conclusión
¡Gracias por su atención!
¿Dudas?
Normalmente se podria pensar que la memoria al tener mas marcos de página resultaria en menos fallos de página.
Belady, Nelson y Shedler descubrieron esta anomalia cuando un FIFO provocó mas fallos de página con cuatro marcos que con tres.
Cada proceso genera una serie de referencias a la memoria durante su ejecucción.
Estas referencias generadas corresponden a una página virtual determinada.
Es por eso que la manera en que cada proceso tiene acceso a la memoria se puede determinar por una lista ordenada de números de paginas. Esta lista es conocida como cadena de referencias.
Anomalía de Belady
Algoritmos de Pila
La cadena de distancias
Predicción de tasas
de fallos de página
Esta figura muestra un arreglo del registro de memoria de un proceso
Cálculo de predicción
Predicción efectuada gracias a la cadena de distancias, se usa esta información para predecir cuantos fallos habría en cada proceso de 1 a n marcos de página, donde n es el número de páginas virtuales del espacio de direcciones del proceso.
Anomalía de Belady
Para hacer este cálculo usaremos dos vectores, el vector C nos dirá cuantas veces aparece cada número en la cadena de distancias (desde 1 a n) y el vector F es una suma de todos los elementos del vector C después de i (de 1 a n).
Cadena de referencias a páginas pedidas por el proceso
Fallos de página marcados con P
Cadena de distancias, usaremos esos datos para el cálculo de la predicción
Cálculo de predicción
Vector C:
Significado de la predicción
Fórmula para calcular el vector F:
Los números del vector F indican el número de fallos que habrá con m marcos de página y una distancia determinada.
Considerando este ejemplo tenemos en el caso de un marco de página, que habrá 20 fallos; visto de otra forma cada vez que haya un número en la cadena de distancias que sea mayor que m, habrá un fallo de página
A veces los algortimos de pila son más eficientes si representamos la cadena de referencias usando una manera abstracta. Dicha abstracción es conocida como cadena de distancias.
La cadena de distancias
Se reemplaza cada número de la cadena de referencias por la distancia que hay desde la parte superior de la pila. Se usa infinito si la referencia no está en la pila.
1. La cadena de referencias del proceso en ejecucción
2. El algoritmo de reemplazo de páginas
3. El número de marcos para página disponibles en la memoria, m.
Sistema de paginación
Pongamos un interprete:
Este mantiene un arreglo interno "M" el cual lleva un registro del estado de la memoria, que contiene un número de elementos "n" igual al número de páginas del proceso "n".
El arreglo M se divide en dos, la parte superior tiene "m" entradas las cuales se encuentran por el momento en memoria.
La parte inferior con n-m páginas contiene las páginas referenciadas al menos una vez.
En un inicio M es vacio!
Ejemplo:
La primera gráfica muestra que la mayoría de las entradas están entre 1 y k, lo que indica que dar k marcos hace que sucedan pocos fallos. La segunda gráfica muestra entradas dispersas, lo que ocasionaría que tendrías que darle tantos marcos como referencias haya.
Esto nos muestra la importancia estadística de las cadenas de distancias y cuándo usar k número de marcos.
Cada referencia a una página, está siempre se desplaza al principio de la parte superior de M.
Si la página a la cual se hace referencia ya estaba en M, todas las demas se desplazan una posición hacia abajo.
Las páginas que se encuentran debajo de la página de referencia no se desplazan. Por lo que M refleja exactamente el contenido de un algoritmo LRU.
Analizando el modelo
Los algoritmos con la propiedad:


Donde m varia en los marcos para página y r es un índice a la cadena de referencias.
Los algoritmos con esta propiedad se llaman algoritmos de pila.
Estos no padecen la anomalía de Belady.
Algoritmos de pila
Previo a la elección de un algoritmo de paginación se debe de verificar:
Evasión de Anomalía de Belady
Escoger el algoritmo de pila adecuado
Necesidad de cadenas de distancia
Realizar la predicción de tazas de fallos
Full transcript