MEMORY
MANAGEMENT-3
Cátedra: Sistemas Operativos
UTN-FRSF
Atención de fallo de página
En el vector de interrupciones hay una rutina especifica
1. Notificación al sistema operativo para el fallo de pagina.
Se produce un fallo, se invoca al SO, y se le dan datos
para determinar el fallo especifico y donde ocurrio.
2. Guardar los registros del usuario y estado del proceso
Para despues restituirlo cuando el SO resuleva el fallo
3. Determinar que la interrupción fue un fallo de página
4. Verificar que la referencia a la página fue válida y determinar
la posición de la página en disco
5. Leer del disco a un marco libre
6. Durante la espera asignar la CPU a algún otro usuario
Atención de fallo de página
Atención de fallo de página
7. Interrupción del disco (E/S terminada) Para notificar al SO que termino de leer la
pagina
8. Guardar los registros y el estado de proceso del otro usuario
(si se llevó a cabo el paso 6)
9. Corregir la tabla de páginas y las demás tablas de modo que
indiquen que la página ya está en memoria (con el bit de Presente/Ausente)
10. Esperar que la CPU se asigne otra vez a este proceso
11. Restaurar los registros de usuario, el estado de proceso y la
nueva tabla de páginas y reanudar la ejecución interrumpida
Atención de fallo de página
Desempeño de la paginación
• La Paginación por demanda puede tener un efecto importante
sobre el desempeño de un sistema
• Es Necesario calcular el tiempo de acceso efectivo
• Tiempo acceso memoria típico (am) varía entre 10 y 200
nanosegundos
• Si no hay fallos: tiempo acceso efectivo es el mismo que el
tiempo de acceso a memoria
Rendimiento de la paginación
• Si ocurre un fallo hay que leer del disco la página y luego
acceder a la palabra deseada
• Entonces:
– si p es la probabilidad de que ocurra un fallo,
– el tiempo efectivo de acceso (tea) es:
Tiempo de acceso a memoria
tea = (1− p) am+ p ( tiempo fallóde página)
Si p = 0, entonces tea = 1 x am
• Para calcular lo anterior necesitamos saber cuánto tiempo toma
resolver un fallo de página
Tiempo servicio fallo página
• Tiene tres componentes
– Atender la interrupción de fallo de página
– Traer la página a la memoria
– Reiniciar los procesos
• Primera y última tarea podrían tomar entre 1 y 100 ms c/u
Relacionado con la cantidad de rpm del disco
• Tiempo intercambio:
– promedio latencia disco duro: 15 s
– tiempo de búsqueda: 8 ms Promedio que tiene el brazo
del disco para moverse de la
– tiempo de transferencia: 1 ms pista mas interna a la mas
externa
– total: 24 ms
• Tiempo total paginación: aprox. 25 ms
Tiempo servicio fallo página
• Sólo se considera tiempo de servicio
– si hay una cola de procesos hay que considerar el tiempo de espera
para que el dispositivo esté libre
• Si tiempo acceso memoria es de 100 ns, el tiempo de acceso
efectivo es:
tae = (1-p) x (100) + p ( 25 ms)
(1-p) x 100 + p x 25,000,000
100 + 24, 999,900 x p
Eso nos dice que el impaco de p e muy grande en el tiempo de servicio de fallo de pagina, por lo que se debe buscar que p
sea lo mas chico posible.
Entonces, mientras mas chico sea p, mejor es el rendimiento, ya que no habra tantos fallos de pagina (que consumen mucho
tiempo en ser resueltos/atendidos)
Tiempo servicio fallo página
• Tiempo de acceso efectivo es directamente proporcional a la
frecuencia de los fallos de página
• Si un acceso de cada 1000 causa un fallo de página, el tiempo
de acceso efectivo será de 25 s
¡¡ El Rendimiento se reduce en un factor de 250 a causa
de la paginación por demanda !!!
• Si se desea una degradación de menos del 10%, se necesita
que:
» 110 > 100 + 25,000,000 x p
» 10 > 25,000,000 x p
» p > 0.0000004
Algoritmos de reemplazo
• Dos aspectos a cuidar en la implementación de la paginación
por demanda:
– desarrollar un algoritmo de asignación de marco
– desarrollar un algoritmo de reemplazo de páginas
• En el primero, si se tienen varios procesos en memoria, hay
que decidir cuántos marcos se asignarán a cada uno
• En el último, si hay que reemplazar páginas hay que
seleccionar cuáles se reemplazarán
Algoritmos de reemplazo
• ¿Cómo escoger un algoritmo de reemplazo específico?
– En general lo que se busca es el algoritmo con la frecuencia de
fallos de página más baja Porque cuanto mas fallos de pagina tengo, menor es el rendimiento
Factores de los que dependen los fallos de pagina:
-La cantidad de marcos (a mas marcos, mejor desempeño)
-El algoritmo de reemplazo (c/algoritmo tiene un desempeño diferente)
• Evaluación: -La cadena de referencia (la secuencia de paginas que el proceso accedio)
– Se ejecuta con una serie específica de referencias a memoria y
se calcula el número de fallos de página
– Serie específica = Cadena de Referencias
– Se puede generar en forma aleatoria o a partir del rastreo de
unsistema dado
– Se requiere saber el número de marcos que se dispone
Algoritmo Óptimo Este algoritmo requeriria saber cuales son las
paginas que se van a utilizar, por lo que resulta
imposible. Es un modelo ideal que no existe.
• Cuando ocurre fallo página cierto conjunto de páginas se
encuentran en memoria
• En la siguiente instrucción se hará referencia a una de estas
páginas.
• Otras páginas no se usarán hasta 20, 200 o 1500 instrucciones
más adelante
• Cada página se va a etiquetar con:
•Cantidad de instrucciones a ejecutar antes de hacer la
primera referencia a dicha página
Algoritmo Óptimo Aquella que se va
a usar dentro de
• Principio algoritmo:
mucho tiempo.
•Eliminar página con la máxima etiqueta
•Si una página no va a ser referenciada hasta dentro de X
instrucciones y otra página se usará hasta dentro Y
instrucciones, siendo X > Y: eliminar primero a la página
que retrasa el fallo lo más posible (la de X)
Página 1 Página 2 Página 3
Etiqueta: 10 Etiqueta: 30 Etiqueta: 5
Como 30 es la etiqueta mayor (la que se va a usar a lo
ultimo) se elimina
• Eliminar la página que más va a tardar en ser referenciada
No Recientemente Usado (NRU)
•En las Tablas de Página hay 2 bits de estado:
Indica que alguien accedio a la pagina, ya sea
en modalidad lectura o escritura
•R: se activa si se hace Referencia a la página
•M: se activa cuando se Modifica la página
•La CPU setea los bits R/M en cada referencia a memoria
•El sistema operativo los puede Resetear a través de
instrucciones de máquina
No Recientemente Usado (NRU)
Principio Algoritmo:
•Al iniciar un proceso el S.O. asigna 0 a R y M de todas las
páginas
Osea que el bit R indica que desde que se limpio la pagina hasta un momento dado la pagina fue o no accedida
•En cada interrupción de Reloj se limpia el bit R, (para distinguir
páginas que no tengan referencia de las que sí).
Si el bit R = 1, quiere decir que se uso, y si se uso, es probable que se vuelva a usar
•Fallo de página: S.O. inspecciona todas las páginas y las divide
en cuatro clases (según valores R y M ):
•clase 0: no referenciada, no modificada (R=0, M=0)
•clase 1: no referenciada, pero ha sido modificada (R=0, M=1)
•clase 2: se ha hecho referencia, pero no modificada (R=1, M=0)
•clase 3: se ha hecho referencia y ha sido modificada (R=1, M=1)
No Recientemente Usado (NRU)
• Algoritmo NRU elimina página de la primera clase no vacía
con el número más pequeño, (número de clase).
• Si todas tienen el mismo nivel se elimina el que llegó primero
• Hipótesis implícita:
– Es mejor eliminar una página modificada sin referencia en al
menos un intervalo de reloj, que una página en blanco de uso
frecuente.
• Ventajas:
– Fácil de comprender
– Implantación eficiente
– Rendimiento que, aún sin ser el óptimo, sí es adecuado con mucha frecuencia.
First In First Out (FIFO)
• Principio los primeros en entrar, son los primeros en salir.
• El S.O. tiene una lista de todas las páginas en memoria, siendo
la primera página la más antigua y la última la más reciente
en ingresar a memoria.
Problema: Que algo sea viejo, no necesariamente implica que no se va a usar
• En un fallo de página se elimina la primera página y se añade
la nueva al final de la lista.
0 3 7 8 12 15 18
A B C D E F H
página que se página de carga
cargó en 1er. lugar más reciente
(1a. página en salir) (última página en salir)
First In First Out (FIFO)
# ./fifo
reference string: 6 2 4 6 4 5 4 2 4 2 1 0
FIFO -1 -1 -1 -1
ref[ 0] 6: 6 -1 -1 -1 Fault
ref[ 1] 2: 2 6 -1 -1 Fault
ref[ 2] 4: 4 2 6 -1 Fault
ref[ 3] 6: 4 2 6 -1
ref[ 4] 4: 4 2 6 -1
ref[ 5] 5: 5 4 2 6 Fault
ref[ 6] 4: 5 4 2 6
ref[ 7] 2: 5 4 2 6
ref[ 8] 4: 5 4 2 6
ref[ 9] 2: 5 4 2 6
ref[10] 1: 1 5 4 2 Fault
ref[11] 0: 0 1 5 4 Fault
no of page faults :6
Segunda Oportunidad
•Modificación simple de FIFO
• Evita deshacerse de una página de uso frecuente
• Inspeccionando el bit R de la página más antigua.
•si (R = 0) => La página más antigua y no referenciadas se
reemplaza en forma inmediata
•si (R=1) => El bit R se pone en 0 y la página se coloca al
final de la lista su tiempo de carga se actualiza
Segunda Oportunidad
Una variante del algoritmo es usar dos bits M y R para decidir
si se da una segunda oportunidad
R1 R1 R0 R1 R0 R1 R0
A B C D E F G
página que se
cargó en 1er. lugar página de carga
más reciente
R1 R1 R0 R1 R0 R0 R1
D E F G A B X
página que se
cargó en 1er. lugar página de carga
más reciente
Algoritmo del Reloj
•Mantiene las páginas en una lista circular con forma de reloj.
•Un puntero (aguja) apunta hacia la página más antigua. (A la candidata
a sacar)
•Al ocurrir un fallo de página se inspecciona la página a la que
apunta la aguja.
•Si bit R = 0
•La página se retira de memoria
•Se inserta nueva página en su lugar en el reloj
•La aguja avanza una posición
•Si bit R = 1
•Se pone R=0
•La aguja avanza una posición
•Difiere del anterior sólo por la implementación
Algoritmo del Reloj
Indica que fue accedida
cuandd se la trajo a
7 R=1 memoria o cuando fue 7 R=0
candidata a salir y tenia el
bit R=1.
1 R=1 5 R=1 5 R=1
1 R=1
3 R=0 3 R=0
7 R=0 7 R=0
1 R=1 5 R=0 1 R=1 5 R=0
3 R=0 9 R=1
Algoritmo del Reloj
# ./reloj
reference string: 0 3 4 0 3 2 6 4 1 6 4 3 1 3 4
RELOJ -1:0 -1:0 -1:0 -1:0
ref[ 0] 0: 0:1 -1:0 -1:0 -1:0 Fault
ref[ 1] 3: 3:1 0:1 -1:0 -1:0 Fault
ref[ 2] 4: 4:1 3:1 0:1 -1:0 Fault
ref[ 3] 0: 4:1 3:1 0:1 -1:0
ref[ 4] 3: 4:1 3:1 0:1 -1:0
ref[ 5] 2: 2:1 4:1 3:1 0:1 Fault
ref[ 6] 6: 6:1 2:0 4:0 3:0 Fault
ref[ 7] 4: 6:1 2:0 4:1 3:0
ref[ 8] 1: 1:1 6:1 2:0 4:1 Fault
ref[ 9] 6: 1:1 6:1 2:0 4:1
ref[10] 4: 1:1 6:1 2:0 4:1
ref[11] 3: 3:1 4:0 1:1 6:1 Fault
ref[12] 1: 3:1 4:0 1:1 6:1
ref[13] 3: 3:1 4:0 1:1 6:1
ref[14] 4: 3:1 4:1 1:1 6:1
no of page faults :7
FIFO no cumple con la caracteristica de que
Anomalia de Belady mientras mas memoria se dispone, menos
fallos de pagina se tendran.
Anomalia de Belady
Anomalia de Belady
Menos recientemente usado (LRU)
No se lo puede usar en paginacion
•Las Páginas recientemente usadas tienen cierta probabilidad en
ser las siguientes. Por lo que se mantendran en memeoria
•Es probable que las páginas que no hayan sido utilizadas
durante mucho tiempo permanezcan sin uso por bastante
tiempo. Por lo que seran candidatas a salir
•Esto induce al siguiente algoritmo:
•
Al ocurrir un fallo de página se elimina la página que
no haya sido utilizada durante el mayor tiempo.
Menos recientemente usado (LRU)
•LRU: realizable en teoría, no es barato.
•Implementación: Es necesario mantener una lista de todas las
páginas en memoria, en donde la página de uso más reciente este
al principio de la lista y la de uso menos reciente al final.
Implementado con caches
•Dificultad:
• La lista debe actualizarse en cada referencia a la memoria.
•Búsqueda de la página en la lista, su eliminación y posterior
traslado al frente de la misma NO debe ser una operación muy
lenta.
Menos recientemente usado (LRU)
Menos recientemente usado (LRU)
# ./lru
reference string: 4 6 4 5 3 0 6 5 3 0 6 0
LRU -1 -1 -1 -1
ref[ 0] 4: 4 -1 -1 -1 Fault
ref[ 1] 6: 6 4 -1 -1 Fault
ref[ 2] 4: 4 6 -1 -1
ref[ 3] 5: 5 4 6 -1 Fault
ref[ 4] 3: 3 5 4 6 Fault
ref[ 5] 0: 0 3 5 4 Fault
ref[ 6] 6: 6 0 3 5 Fault
ref[ 7] 5: 5 6 0 3
ref[ 8] 3: 3 5 6 0
ref[ 9] 0: 0 3 5 6
ref[10] 6: 6 0 3 5
ref[11] 0: 0 6 3 5
no of page faults :6
LRU: Solución 1 No se suele tomar porque NO se usa
•Requiere de un contador de 64 bits, C, en hardware. Se
incrementa en forma automática después de cada referencia.
•Cada entrada en tabla de páginas debe contener espacio
necesario para almacenar el contador.
•Después de cada referencia el valor actual de C se almacena en
la entrada de la tabla de páginas correspondiente a la página a la
que se hizo referencia.
•Fallo de página:
•=> S.O. examina todos los contadores de la tabla de páginas y
elige la página con menor contador.
LRU: Solución 1 No se suele tomar porque NO se usa
Valor inicial cont = 0;
P0 P1 P2 P3 cont = 1;
Referencias: P0, P1, P3, P1
1 0 0 0
P0 P1 P2 P3 cont = 2; Página más recientemente usada:
P1, (cont = 4)
1 2 0 0
Página menos usada:
P0 P1 P2 P3 cont = 3; P2 , (cont = 0)
1 2 0 3
P0 P1 P2 P3 cont = 4;
1 4 0 3
LRU: Solución 2 No se suele tomar porque NO se usa
•Se requiere para una Máquina con n marcos para página,
hardware LRU que es una matriz de n x n la cual se inicializa en
en cero.
•Por cada Referencia al marco k, el hardware primero activa
todos los bits del renglón k y después desactiva todos los bits de
la columna k.
•En cualquier instante:
renglón con valor binario mínimo es de uso menos
frecuente,
renglón con el siguiente valor más pequeño es el segundo
de uso menos reciente, etc.
LRU: Solución 2 No se suele tomar porque NO se usa
Máquina con cuatro marcos, con referencias a las páginas en el orden:
0, 1, 2, 3, 2, 1, 0, 3, 2, 3
Después hacer referencia a la página 0 tenemos la situación siguiente:
LRU: Simulación por Software
•Existe la Posibilidad de usar un algoritmo de uso no frecuente o
NFU . Se necesita un contador en software asociado a c/página
valor inicial = 0;
NFU: No Frecuentemente Usado
•En cada interrupción de reloj, el S.O. examina todas las
páginas de la memoria y se suma al contador el contenido del
bit R.
•Principal problema NFU: nunca olvida.
•Ejemplo: Compilador
Marcos libres Cantidad de memoria/marcos libres que pueden contener paginas
• Muchos sistemas mantienen una reserva de marcos libres. En
general esto se hace con el Demonio de Paginación quien se
activa al disminuir un número dado de marcos libres.
• Cuando ocurre un fallo de página, se escoge un marco víctima
igual que antes:
– Sin embargo la página deseada se coloca en un marco libre
de la reserva antes de escribir la víctima en el disco
– Este procedimiento permite al proceso reiniciarse lo más
pronto posible, sin esperar a que la página víctima se
escriba en el disco
– Cuando la víctima termina de escribirse en el disco, su
marco se añade a la reserva de marcos libres
Maduración o Envejecimiento
Se usa un registro de desplazamiento, donde se escribe la historia de que si la pagina fue referida o no en el ultimo
tik de reloj. Busca eliminar al que fue menos referida, viendo los bits mas significativos.
Se desplazan los bits
anteriores
Reemplazo Global
No interesa de que proceso es la pagina mas vieja, interesa el tiempo de acceso, o la frecuencia de acceso
de esa pagina.
• Un factor importante de como se asignan los marcos es el
reemplazo de páginas
Si el proceso 1 produjo un fallo de pagina, aplico el algoritmo de reemplazo de pagina a todos los procesos y encuentro otro
proceso menos frecuente, entonces se le saca un marco de pagina a ese proceso y se le otorga al proceso que ocasiono el fallo.
• Si hay varios procesos compitiendo por los marcos, es posible
clasificar algoritmos de reemplazo en global y local.
• Reemplazo global
– Si se produce un Fallo de página y no hay marcos libres, se permite
que la página a reemplazar pertenezca a cualquier proceso.
– Ventaja: todos los marcos del sistema participan en el algoritmo de
selección de la víctima.
– Desventaja: No se puede controlar la tasa de frecuencia de Fallos de
Página de un proceso en particular.
Reemplazo Local
• Reemplazo local:
– Si se produce un Fallo de página y no hay marcos libres, se permite que
la página a reemplazar pertenezca a al conjunto de marcos que tiene
asignado ese proceso.
– El número de marcos asignado a un proceso no cambia
– Ventaja: El conjunto de páginas de un proceso que están en la memoria
sólo depende del comportamiento de paginación de ese proceso
– Desventaja: podría obstaculizar ejecución de un proceso por no dejar
que aproveche otras páginas de memoria de poco uso.
• El Reemplazo global generalmente aumenta el rendimiento de
un sistema, y es el más usado.
• En sistemas como AS/400 se combinan ambos métodos. Se
asigna memoria a un grupo de procesos (Local), y todos los del
grupo compiten por los marcos (Global).
Reemplazo Local vs Global
Algoritmo Local Algoritmo Global
A
Menor
contador
dentro del
proceso A
Menor
contador
dentro de
todos los
procesos
Tasa de Fallos
Thrashing = Hiperpaginación
Paginación por Demanda vs
Prepaginación
• Paginación Por Demanda:
– Al cargarse un proceso se le asigna solo un marco de
Página.
– A medida que va haciendo referencias se producen fallos
que terminan cargando su Working Set.
• Prepaginación:
– Al cargarse un proceso se le asignan aproximadamente
tantos marcos como su Working Set
Working Set – Conjunto de
Estos picos de fallos se interpretan a que
Trabajo aumenta la tasa de fallos del procesos porque
se van produciendo falklos los cuales generan
que se vayan cargando el working set.
Una vez se cargo todo el working set,
comienza a estabilizarse, por lo que la grafica
comienza a decrecer.
transition from one working set to another
Gestión del Almacenamiento
Secundario
• Lo más simple es asignar un área dedicada (inicialmente vacía),
separada del sistema de Archivos.
AREA DE SWAP
SISTEMA DISCO
DE
El resto se utiliza para
ARCHIVOS el sistema de archivos
a los que puedo
acceder
Area de swapp, es
independiente, a la
que no se puede
acceder
Administrado por el
Adm de memoria del
SO
Gestión del Almacenamiento
Secundario
utn-so:~# cat /etc/fstab
# <file system> <mount point> <type> <options> <dump> <pass>
proc /proc proc defaults 0 0
/dev/hda1 / ext3 defaults,errors=remount-ro 0 1
/dev/hda5 none swap sw 0 0
/dev/hdc /media/cdrom0 udf,iso9660 user,noauto 0 0
/dev/fd0 /media/floppy0 auto rw,user,noauto 0 0
utn-so:~# fdisk -l /dev/hda
Disk /dev/hda: 8589 MB, 8589934592 bytes
255 heads, 63 sectors/track, 1044 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
Device Boot Start End Blocks Id System
/dev/hda1 * 1 998 8016403+ 83 Linux
/dev/hda2 999 1044 369495 5 Extended
/dev/hda5 999 1044 369463+ 82 Linux swap / Solaris
Gestión del Almacenamiento
Secundario
– Cada vez que se crea un proceso se reserva una zona del área
contigua de intercambio igual al tamaño de imagen del
proceso. Cada vez que se crea un proceso, se crea en el area de swapp del disco un conjunto de bloques
contiguos igual al tamaño del proceso.
– A cada proceso se le asigna la dirección en disco de su área
de intercambio, que se almacena en la Tabla de Proceso.
– El acceso se realiza sumando el número de página virtual a la
dirección de comienzo del área asignada al proceso.
Gestión del Almacenamiento
Secundario
– Si los datos y/o la pila pueden crecer, es mejor reservar zonas
independientes.
– A cada zona se le asignan varios bloques.
– No se asigna nada inicialmente. A cada página se le asigna su
espacio en disco cuando se va a intercambiar, y el espacio se
libera cuando la página vuelve a memoria. Problema: se debe
llevar contabilidad en memoria -página a página- de la
localización de las páginas en disco.
Gestión del Almacenamiento
Secundario
La otra alternativa es usar un Archivo especial y delegar la
Gestión del Disco al Sistema de Archivos
ARCHIVO
DE SWAP
Ya no esta en el disco, sino en el sistema de
archivos (es parte de este). Osea que c/ vez que se
produce un fallos de pagina se debe ir al sistema
de archivos y encontrar la localizacion de la pagina
(esto lo hace sistema de adm de memoria).
Es como un intermediario entre el fallos y el adm
de memoria.
Es mas lento pero no desperdicio espacio en disco
SISTEMA DE ARCHIVOS
Gestión del Almacenamiento
Secundario
Gestión del Almacenamiento
Secundario
ÁREA DE SWAP ARCHIVO ESPECIAL
(DE SWAP)
• Tamaño Fijo: => límitado • Tamaño Variable: => No
para crecimiento. limitado para crecimiento.
• Tamaño Fijo: => puede • Tamaño Variable: => utiliza
desperdiciar espacio de mejor el espacio de disco.
disco. • Menor Rendimiento:
• Mejor Rendimiento: no interactúa con Archivos
interactúa con Archivos • Menor Rendimiento, el MM
• Mejor Rendimiento, el utiliza al FS quien gestiona
MM usa directamente el el Disco usando el Driver de
Driver de Disco. Disco.
Consideraciones de
Implementación
• Se requiereArquitectura Específica para Paginación:
– Problemas con instrucciones de copias de strings y autoincremento
– Problemas con instrucciones “partidas al medio”
• Retención de Páginas en Memoria:
– En operaciones de E/S.
– En buffers utilizados en System Calls.
• Páginas compartidas: Hay que tener un contador de
referencias a la página.
Consideraciones de
Implementación
Si se esta haciendo una transferencia de datos desde el
RAM disco hacia el buffer que ocupa 2 paginas, a esas paginas
deberían ser inamovibles en la memoria hasta que se
termine la transferencia de datos.
Process A pages
Process B pages
Process A starts I/O and then blocks.
Process B runs and needs a frame. We should not remove A’s page.
Programación con Paginación
Programa 1
Array A[1024,1024] of integer
for j := 1 to 1024 do
for i := 1 to 1024 do
A[ i, j]:=0;
=> Fallos de Página = 1024 x 1024!!!!
Programa 2
Array A[1024,1024] of integer
for i := 1 to 1024 do
for j := 1 to 1024 do
A[ i, j]:=0;
=> Fallos de Página = 1024 !!!!
Programación con Paginación
/* scan square matrix */
void matscan(double *a, int n)
{
int i, j, t;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
t+= a[i*n + j];
}
/*****************************************************************/
/* inverse scan square matrix */
void imatscan(double *a, int n)
{
int i, j, t;
for (j = 0; j < n; j++)
for (i = 0; i < n; i++)
t+= a[i*n + j];
}
Programación con Paginación
nessus:/home/so# ./matrixscan 1000
Scan matrix order 1000
Back from column scan in 0.012459 seconds
Back from row scan in 0.017833 seconds
nessus:/home/so# ./matrixscan 5000
Scan matrix order 5000
Back from column scan in 0.313992 seconds
Back from row scan in 0.492337 seconds
nessus:/home/so# ./matrixscan 10000
Scan matrix order 10000
Back from column scan in 1.313757 seconds
Back from row scan in 2.606237 seconds
Programación con Paginación
MATRIX SCAN
6,000000000
5,000000000
4,000000000
scan time [s]
3,000000000
2,000000000
1,000000000
0,000000000
10 50 100 500 1000 5000 10000 11000
Matrix order
Programación con Paginación
# vmsat
procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu----
r b swpd free buff cache si so bi bo in cs us sy id wa
2 2 408748 12792 284 11888 1412 320 1412 320 370 666 0 2 0 98
0 2 408452 12208 284 11880 1612 236 1612 236 406 760 4 2 0 94
1 2 408656 12280 284 11896 996 536 996 536 335 569 0 2 0 98
0 2 408872 12556 284 11868 844 544 844 544 365 605 1 2 0 97
1 2 408916 12376 284 11880 1244 532 1244 532 379 690 0 2 0 98
0 2 409248 12172 284 11876 756 684 756 684 374 621 0 4 0 96
0 2 409528 12776 284 11644 496 484 496 484 320 526 0 2 0 98
0 2 409416 12164 284 11676 1376 428 1376 428 381 676 4 1 0 95
1 2 409388 12404 284 11668 1360 456 1360 456 372 654 0 4 0 96
0 2 409516 13120 284 11340 1052 464 1052 464 363 614 0 5 0 95
1 2 409048 12324 284 11136 1664 232 1664 232 357 674 0 1 0 99
0 2 409356 12312 284 11112 672 540 672 540 354 589 3 2 0 95
1 2 409616 13152 280 10372 796 512 796 512 337 551 0 2 0 98
0 2 409464 13160 264 9784 1628 408 1628 408 377 659 0 2 0 98
0 2 409464 12156 264 9784 1088 388 1088 388 353 613 0 1 0 99
1 2 409516 13168 264 9804 1032 448 1032 448 357 601 0 14 0 86
1 2 409304 12260 264 9808 1120 264 1120 264 350 620 5 1 0 94
1 1 409616 15180 264 9768 724 520 724 520 359 556 0 18 0 82
1 1 408812 13416 264 9796 2404 4 2404 4 398 765 0 3 0 97
0 2 408688 12688 264 9776 1584 588 1584 588 387 698 0 3 0 97
Programación con Paginación
Cadenas de Referencia
http://cs.gmu.edu/cne/workbenches/local/Locality.html
Cadenas de Referencia
Predicción de tasa de Fallos
Predicción de tasa de Fallos
Predicción de tasa de Fallos
Predicción de tasa de Fallos
utn-so:/home/so# ./distance-lru
reference string: 6 0 7 5 1 4 2 8 6 1 3 5 6 4 8
LRU -1 -1 -1 -1 -1
ref[ 0] 6: 6 -1 -1 -1 -1 -1 -1 -1 -1 dist=-1 Fault
ref[ 1] 0: 0 6 -1 -1 -1 -1 -1 -1 -1 dist=-1 Fault
ref[ 2] 7: 7 0 6 -1 -1 -1 -1 -1 -1 dist=-1 Fault
ref[ 3] 5: 5 7 0 6 -1 -1 -1 -1 -1 dist=-1 Fault
ref[ 4] 1: 1 5 7 0 6 -1 -1 -1 -1 dist=-1 Fault
ref[ 5] 4: 4 1 5 7 0 6 -1 -1 -1 dist=-1 Fault
ref[ 6] 2: 2 4 1 5 7 0 6 -1 -1 dist=-1 Fault
ref[ 7] 8: 8 2 4 1 5 7 0 6 -1 dist=-1 Fault
ref[ 8] 6: 6 8 2 4 1 5 7 0 6 dist=7 Fault
ref[ 9] 1: 1 6 8 2 4 5 7 0 6 dist=4
ref[10] 3: 3 1 6 8 2 4 5 7 0 dist=-1 Fault
ref[11] 5: 5 3 1 6 8 2 4 5 7 dist=6 Fault
ref[12] 6: 6 5 3 1 8 2 4 5 7 dist=3
ref[13] 4: 4 6 5 3 1 8 2 4 5 dist=6 Fault
ref[14] 8: 8 4 6 5 3 1 8 2 4 dist=5 Fault
Distance Freq: [0]=0 [1]=0 [2]=0 [3]=1 [4]=1 [5]=1 [6]=2 [7]=1 [8]=0 [oo]=9
Number of Pages :9
Number of Frames :5
Number of Faults :13
