Modelo Working-Set y ejemplos de Arquitectura de Paginación

De Departamento de Informatica
Saltar a: navegación, buscar

Cuando la memoria principal se hace insuficiente, los sistemas operativos modernos implementan un mecanismo para emular una memoria de mucho mayor tamaño, haciendo creer a los procesos que tienen más memoria que la disponible realmente, manteniendo parte de ellos en disco. A este tipo de memoria se le llama memoria virtual, ya que en realidad no se tiene físicamente toda esa memoria, por lo que algunos procesos no podrán ser ubicados en la memoria principal.

Una de las maneras de implementar la memoria virtual es el paginamiento en demanda, que es un mecanismo donde el núcleo se encarga de trasladar al disco o a memoria las páginas virtuales de un proceso, dependiendo de la probabilidad de que éstas sean o no referenciadas en un futuro cercano. Un proceso puede continuar ejecutándose con parte de sus páginas en disco, pero con la condición de no accesar esas páginas, de lo contrario ocurren fallos de página.

En el caso de que haya poca memoria disponible y/o una mala implementación de los algoritmos de intercambio de páginas, se puede dar un problema conocido como sobrepaginación o thrashing. En el presente artículo se explicará brevemente qué es thrashing y cómo solucionarlo a través de una estrategia llamada Working-Set, además de dar algunos ejemplos de arquitecturas de paginación.

Contenido

Thrashing

El término sobrepaginación o, en inglés, Thrashing, es usado para describir un estado en que el sistema de memoria virtual está constantemente en proceso de paginación, intercambiando rápidamente datos en memoria por datos en disco y viceversa.

En general, cualquier proceso que no cuente con los frames suficientes para soportar las páginas activas, generará fallos de página muy frecuentemente, debiendo reemplazar alguna que ya esté en memoria. Pero como todas sus páginas están activas, se verá forzado a sustituir una página que casi de inmediato se volverá a necesitar, causando que se generen rápidamente sucesivos fallos de página, que, a su vez, reemplazarán páginas que el proceso se verá forzado a recargar al instante. A este estado de frenética paginación, donde el proceso invierte más tiempo en mecanismos de paginación que de ejecución, se le llama thrashing, que causa una baja o colapso en el rendimiento del computador por una baja utilización de la CPU ocasionando atascos y sobrecarga del sistema.

Causas de Thrashing

Figura 1: Thrashing

Cuando la tasa de utilización de la CPU baja demasiado, el S.O. ordena incrementar el grado de multiprogramación introduciendo un nuevo proceso al sistema. Supongamos que un proceso entra en fase de ejecución y necesita más frames que los disponibles, generará entonces, fallos de página quitando frames a otros procesos que, a su vez, necesitan esas páginas, generando así más fallos de página. A medida que estos procesos se ponen en la cola para ser servidos por el dispositivo de paginación, la cola "ready" se vacía, causando que la tasa de utilización de la CPU disminuya y, como consecuencia, que el S.O. introduzca otro proceso para elevar el grado de multiprogramación, volviéndose a repetir todo el ciclo y creando un círculo vicioso donde los procesos involucrados caen en estado de thrashing, incrementándose el tiempo efectivo de ingreso a memoria, y decayendo vertiginosamente la tasa de procesamiento del sistema.

El gráfico de la figura 1 representa el proceso explicado: al aumentar el grado de multiprogramación, también lo hace la tasa de utilización de la CPU. Esta última alcanza un máximo, pero el grado de multiprogramación sigue creciendo, momento en el que aparece la sobrepaginación, que causa el decaimiento abrupto de la utilización de la CPU. Cuando se llega a tal punto, es de primera necesidad reducir el grado de multiprogramación y acabar con la sobrepaginación para así aumentar la utilización de CPU.

El modelo Working-Set

Para prevenir la sobrepaginación, es necesario proporcionar a los procesos la cantidad de marcos que necesiten. Para conocer dicha cantidad existen varios existen distintas técnicas, la de Working-Set o Conjunto de Trabajo comienza examinando cuántos marcos está utilizando un proceso realmente; esta técnica se basa en el concepto de localidad de ejecución del proceso.

El concepto de localidad se refiere a un conjunto de páginas que se utilizan activamente de forma combinada. Todo programa está compuesto de un conjunto de localidades distintas, que pueden traslaparse unas con otras, y a medida que un proceso se ejecuta, se va desplazando de una localidad a otra.

Este modelo utiliza un parámetro Δ que define la ventana del working set o conjunto de trabajo activo (localidad). Este Δ indica las páginas que están siendo usadas, la idea es examinar las Δ referencias más recientes a páginas. Si una página está activa, se encontrará dentro del working set, mientras que si la página ya no es utilizada, será eliminada de éste Δ unidades de tiempo después de su última referencia. De esta manera, el conjunto de trabajo es una aproximación a la localidad del programa. El sistema operativo supervisa el conjunto de trabajo de cada proceso y le asigna marcos suficientes para proporcionarle el tamaño del conjunto activo. Si hay suficientes marcos iniciales, se puede iniciar otro proceso. Si aumenta la suma de los tamaños de los conjuntos activos, excediendo el número total de marcos disponibles, el sistema operativo selecciona un proceso y lo suspende.

Tabla de referencias de páginas:

Figura 2: Modelo Working-Set

Por ejemplo en la figura anterior, el working set en t1 contiene a las páginas utilizadas en la ventana Δ = 10, {1,2,5,6,7}, en cambio en t2 el working set cambia a {3,4}. Es por esto que la precisión del working set depende del tamaño que tenga Δ. Si Δ es muy pequeño no abarcará la localidad completa, si es muy grande cubrirá gran parte de las localidades y si Δ tiende a \infty el working set contendrá la totalidad de páginas del proceso.

Si calculamos la suma del working set de cada proceso será igual a la demanda D total de frames ( f ). Lo cual se traduce a:

                                          D=\sum WSS_i


Si la demanda es superior a la cantidad de frames (D > f) se produce trashing y en este caso el sistema operativo seleccionará un proceso para suspenderlo.

El sistema operativo es quien también monitoriza los working set de cada proceso y le asigna los suficientes frames para que no se produzca trashing.

Si todo resulta bien la estrategia de working set impide el trashing y mantiene el grado de multiprogramación alto.

Ahora bien, aparece la siguiente duda: ¿cómo estimar el working set de cada proceso?. Esto lo podemos aproximar con una interrupción de temporización a intervalos fijos y un bit de referencia que sirve para saber si es las paginas se consideran dentro del working set actual. Siempre que se produzca una de estas interrupciones se copiará y borrará los valores del bit; lo cual nos indica, según los bit de historia, si una cierta página fue utilizada dentro de una ventana Δ. Sin embargo esto no es del todo preciso, ya que no podemos decir dónde se hizo una referencia a la página. Una alternativa es aumentar los bits de historia o aumentar también la frecuencia de interrupción, pero estas alternativas son más costosas.

Ejemplos de Arquitectura de Paginación

Paginación Simple

Utilizando la arquitectura mostrada en la siguiente figura:

Figura 3: Paginación simple

Si el programa A contiene una referencia a la memoria con dirección 20FE, se realizará el siguiente procedimiento: 20FE es 0010000011111110 en notación binaria (en un sistema de 16 bit), y en este ejemplo se están usando páginas de 4Kb de tamaño. Cuando la petición de la dirección de memoria 20FE es realizada, la Unidad de Gestión de memoria se ve de esta forma:

0010000011111110 siendo 0010 el numero de página que es igual a la pagina numero 2 y 000011111110 la posición de memoria dentro de la página. La página número 2 del proceso A corresponde al marco número 2 en memoria física, con dirección real 1000:2000, por lo tanto, la MMU (Unidad de gestion de memoria) devolverá la dirección del marco en memoria física, con el desplazamiento dentro de esa página: 1000:20FE.

Paginación Multinivel

Ejemplo de Paginación de dos niveles:

Una dirección lógica en una maquina de 32-bits con un tamaño de pagina de 4Kb se divide en:

  • Un numero de página de 20 bits.
  • Una dirección de memoria de 12 bits.

Desde la tabla de páginas, el número de página es a su vez dividido en:

  • Un número de página de 10-bits.
  • Una dirección de memoria de 10-bits.

El esquema de traducción de este tipo de paginación se ve en la figura 4.

Por lo tanto, una dirección lógica es como se muestra en la figura 5, donde también hay un ejemplo de paginación de tres niveles.


Figura 4: esquema de traducción
Figura 5: Paginación de 2 y 3 niveles

Paginación compartida

  • Con el uso de la tabla de páginas varios procesos pueden compartir un marco de memoria; para ello ese marco debe estar asociado a una página en la tabla de páginas de cada proceso.
  • Se puede compartir código común. Por ejemplo, si se tiene un sistema con 20 usuarios usando un editor de texto, sería útil que el código del editor se pudiera compartir. Para que el código pueda ser compartido, este debe ser reentrante' (read-only) y debe aparecer en alguna localización del espacio lógico de todos los procesos. En la figura 6 se muestra un editor de tres páginas que es compartido por tres procesos. Cada proceso tiene su propia página de datos. La tabla de páginas de cada usuario, establece una correspondencia con la misma copia física del editor, pero las páginas de datos corresponden a marcos distintos.
Figura 6: Paginación Compartida

Ejemplo de Paginación invertida

Una crítica al modelo multinivel es que una tabla de páginas puede consistir en millones de entradas, esistiendo una por proceso. Esta situación consume mucha memoria, por lo que una solución son las tablas de páginas invertidas, en la que, como se muestra en la figura 7, hay una entrada para cada página real de memoria, donde cada entrada consiste en la dirección virtual de la página almacenada en el marco con información sobre el proceso que la posee. Disminuye el espacio para almacenar cada tabla de página, pero aumenta el tiempo de búsqueda en la tabla, y para disminuirlo se utiliza hash y memoria asociativa.

  • Dirección lógica es 3-tupla: <pid, p, d>
  • Cada entrada en la tabla tiene el par:<pid, p>
  • Una entrada no encontrada en la tabla significa dirección ilegal.
  • Este modelo es usado en máquinas IBM (IBMSystem/38, IBM RISC 6000, IBM RT)
  • No es un esquema popular (compartir memoria es difícil)
Figura 7: esquema de traducción

Referencias

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas