operating-system - usadas - memoria virtual pdf

Algoritmos de reemplazo de página de memoria virtual

Question

Tengo un proyecto en el que me piden que desarrolle una aplicación para simular el rendimiento de los diferentes algoritmos de reemplazo de páginas (con un tamaño variable de conjunto de trabajo y un período de estabilidad). Mis resultados:

• Eje vertical: faltas de página
• Eje horizontal: tamaño de conjunto de trabajo
• Eje de profundidad: periodo estable

¿Son mis resultados razonables? Esperaba que LRU tuviera mejores resultados que FIFO. Aquí, son aproximadamente los mismos.

Para el azar, ¿el período de estabilidad y el tamaño del conjunto de trabajo no parecen afectar en absoluto al rendimiento? Esperaba gráficos similares a los de FIFO y LRU, ¿el peor rendimiento? Si la cadena de referencia es altamente estable (pequeñas ramas) y tiene un tamaño de conjunto de trabajo pequeño, todavía debería tener menos fallas de página que una aplicación con muchas ramas y un tamaño de conjunto de trabajo grande.

Más información

Mi código de Python | La pregunta del proyecto

• Longitud de la cadena de referencia (RS): 200,000
• Tamaño de la memoria virtual (P): 1000
• Tamaño de la memoria principal (F): 100
• número de páginas de tiempo referenciadas (m): 100
• Tamaño del conjunto de trabajo (e): 2 - 100
• Estabilidad (t): 0 - 1

El tamaño del conjunto de trabajo (e) y el período estable (t) afectan la forma en que se generan las cadenas de referencia.

|-----------|--------|------------------------------------|
0           p        p+e                                  P-1

Por lo tanto, supongamos que la memoria virtual de tamaño P anterior. Para generar cadenas de referencia, se utiliza el siguiente algoritmo:

• Repita hasta generar la cadena de referencia
  • escoger m números en [p, p + e]. m simula o hace referencia al número de veces que se hace referencia a la página
  • Escoja un número aleatorio, 0 <= r <1
  • si r <t
    • generar nueva p
    • else (++ p)% P

ACTUALIZACIÓN (En respuesta a la respuesta de @ MrGomez)

Sin embargo, recuerde cómo sembró sus datos de entrada: utilizando random.random, lo que le brinda una distribución uniforme de los datos con su nivel controlable de entropía. Debido a esto, todos los valores tienen la misma probabilidad de ocurrir, y debido a que lo ha construido en un espacio de punto flotante, las recurrencias son altamente improbables.

Estoy usando random , pero tampoco es totalmente aleatorio, ¿las referencias se generan con alguna localidad a través del uso de parámetros de referencia de tamaño de conjunto de trabajo y número de página?

Intenté aumentar el número numPageReferenced con numFrames con la esperanza de que haga referencia a una página actualmente en la memoria, lo que demuestra el beneficio de rendimiento de LRU sobre FIFO, pero eso no me dio un resultado claro. Solo para su información, probé la misma aplicación con los siguientes parámetros (la proporción de Páginas / Marcos sigue siendo la misma, reduje el tamaño de los datos para hacer las cosas más rápido).

--numReferences 1000 --numPages 100 --numFrames 10 --numPageReferenced 20

El resultado es

Todavía no hay una gran diferencia. ¿Tengo derecho a decir que si aumento numPageReferenced relación a numFrames , LRU debería tener un mejor rendimiento ya que hace referencia a las páginas en la memoria más? O tal vez estoy entendiendo mal algo?

Para el azar, estoy pensando en lo siguiente:

• Supongamos que hay alta estabilidad y pequeño conjunto de trabajo. Esto significa que es muy probable que las páginas a las que se hace referencia estén en la memoria. ¿Entonces la necesidad de que se ejecute el algoritmo de reemplazo de página es menor?

Hmm tal vez tengo que pensar en esto más :)

ACTUALIZACIÓN: basura menos evidente en menor estabilidad

En este caso, estoy tratando de mostrar la eliminación de datos como el tamaño del conjunto de trabajo excede la cantidad de cuadros (100) en la memoria. Sin embargo, notar que la paliza parece menos obvia con una menor estabilidad (alto t ), ¿por qué podría ser eso? ¿La explicación es que a medida que la estabilidad disminuye, las fallas de página se aproximan al máximo, por lo tanto, no importa tanto el tamaño del conjunto de trabajo?

Answer 1

Estos resultados son razonables dada su implementación actual. La razón detrás de esto, sin embargo, conlleva cierta discusión.

Cuando se consideran los algoritmos en general, es más importante tener en cuenta las propiedades de los algoritmos actualmente bajo inspección. Específicamente, tenga en cuenta sus casos de esquina y mejores y peores condiciones de caso. Probablemente ya esté familiarizado con este método de evaluación terso, por lo que es principalmente para el beneficio de quienes leen aquí quienes no tengan antecedentes algorítmicos.

Desglosemos su pregunta por algoritmo y exploremos sus propiedades de componentes en contexto:

1. FIFO muestra un aumento en los errores de página a medida que aumenta el tamaño de su conjunto de trabajo (eje de longitud).

   Este es un comportamiento correcto, consistente con la anomalía de Bélády para el reemplazo de FIFO. A medida que aumenta el tamaño de su conjunto de páginas de trabajo, el número de fallas de página también debería aumentar.

2. FIFO muestra un aumento en las fallas de página a medida que disminuye la estabilidad del sistema ( 1 - eje de profundidad ).

   Al notar su algoritmo para la estabilidad de siembra ( if random.random() < stability ), sus resultados se vuelven menos estables a medida que se acerca la estabilidad ( S ) 1. A medida que aumenta bruscamente la entropy en sus datos, también aumenta considerablemente el número de fallas de página. y propaga la anomalía de Bélády.

   Hasta ahora tan bueno.

3. LRU muestra consistencia con FIFO . ¿Por qué?

   Tenga en cuenta su algoritmo de siembra. La LRU estándar es más óptima cuando tiene solicitudes de paginación que están estructuradas en marcos operacionales más pequeños. Para búsquedas ordenadas y predecibles, mejora en FIFO al vencer los resultados que ya no existen en el marco de ejecución actual, lo que es una propiedad muy útil para la ejecución escalonada y la operación modal encapsulada. Una vez más, hasta ahora, todo bien.

   Sin embargo, recuerde cómo sembró sus datos de entrada: utilizando random.random , lo que le random.random una distribución uniforme de los datos con su nivel controlable de entropía. Debido a esto, todos los valores tienen la misma probabilidad de ocurrir, y debido a que lo ha construido en un espacio de punto flotante , las recurrencias son altamente improbables.

   Como resultado, su LRU está percibiendo que cada elemento ocurre un pequeño número de veces, y luego se descarta completamente cuando se calcula el siguiente valor. Por lo tanto, correctamente las páginas de cada valor a medida que cae fuera de la ventana, lo que le da un rendimiento exactamente comparable a FIFO . Si su sistema representara adecuadamente la recurrencia o un espacio de caracteres comprimido, vería resultados marcadamente diferentes.

4. Para el azar, el período de estabilidad y el tamaño del conjunto de trabajo no parecen afectar el rendimiento en absoluto. ¿Por qué estamos viendo este garabato en todo el gráfico en lugar de darnos una variedad relativamente suave ?

   En el caso de un esquema de paginación al azar , usted envejece stochastically cada entrada. Supuestamente, esto debería darnos alguna forma de una variedad vinculada a la entropía y el tamaño de nuestro conjunto de trabajo ... ¿verdad?

   ¿O debería? Para cada conjunto de entradas, asigna aleatoriamente un subconjunto para paginar en función del tiempo. Esto debería proporcionar un rendimiento de paginación relativamente uniforme, independientemente de la estabilidad y de su conjunto de trabajo, siempre y cuando su perfil de acceso sea de nuevo uniformemente aleatorio.

   Por lo tanto, según las condiciones que está verificando, este es un comportamiento totalmente correcto y coherente con lo que esperaríamos . Obtiene un rendimiento de paginación uniforme que no se degrada con otros factores (pero, a la inversa, no mejora por ellos) que es adecuado para una operación eficiente de alta carga. No está mal, simplemente no es lo que cabría esperar intuitivamente.

Entonces, en pocas palabras, ese es el desglose de la implementación actual de su proyecto.

Como un ejercicio para explorar más a fondo las propiedades de estos algoritmos en el contexto de diferentes disposiciones y distribuciones de datos de entrada, recomiendo encarecidamente scipy.stats en scipy.stats para ver qué puede hacer, por ejemplo, una distribución gaussiana o logística en cada gráfica. Luego, volvería a las expectativas documentadas de cada algoritmo y proyecto de casos en los que cada uno es excepcionalmente el más apropiado y el menos apropiado.

En general, creo que tu profesor estará orgulloso. :)