Estrategias de Administración del Almacenamiento Virtual
Las diferentes organizaciones de almacenamiento virtual generalmente implementadas son [7, Deitel]:
• Paginación.
• Segmentación.
• Segmentación y paginación.
Las estrategias para la administración de sistemas de almacenamiento virtual condicionan la conducta de los sistemas de almacenamiento virtual que operan según esas estrategias.
Se consideran las siguientes estrategias:
• “Estrategias de búsqueda”:
o Tratan de los casos en que una página o segmento deben ser traídos del almacenamiento secundario al primario.
o Las estrategias de “búsqueda por demanda” esperan a que se haga referencia a una página o segmento por un proceso antes de traerlos al almacenamiento primario.
o Los esquemas de “búsqueda anticipada” intentan determinar por adelantado a qué páginas o segmentos hará referencia un proceso para traerlos al almacenamiento primario antes de ser explícitamente referenciados.
• “Estrategias de colocación”:
o Tratan del lugar del almacenamiento primario donde se colocará una nueva página o segmento.
o Los sistemas toman las decisiones de colocación de una forma trivial ya que una nueva página puede ser colocada dentro de cualquier marco de página disponible.
• “Estrategias de reposición”:
o Tratan de la decisión de cuál página o segmento desplazar para hacer sitio a una nueva página o segmento cuando el almacenamiento primario está completamente comprometido.
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA
3.4.2 Técnicas de reemplazo de páginas.
Reemplazo de Página.-
Si al momento de generarse un page fault no hubiera ningún frame disponible, se debe proceder a reemplazar una pagina de memoria. LA rutina de page fault debe ser modificada para incluir reemplazo de páginas:
1. Encontrar un frame disponible.
2. Si hay un frame disponible usarlo
3. Si no hay frames disponibles utilizar algoritmo de reemplazo de paginas para seleccionar la víctima
4. Escribir la pagina víctima a disco y actualizar tabla de paginas .
Estrategias de Reposición de Página
Las principales son:
• El principio de optimización.
• Reposición de páginas al azar.
• Primero en entrar - primero en salir.
• Menos recientemente usada.
• Menos frecuentemente usada.
• No usada recientemente.
• Conjuntos de trabajo.
El Principio de Optimización
El “principio de optimización” indica que para obtener un rendimiento óptimo, la página que se va a reponer es una que no se va a utilizar en el futuro durante el período de tiempo más largo.
El problema es que no es factible predecir el futuro.
Reposición de Página al Azar
Consiste en escoger al azar la página que va a ser reemplazada.
Todas las páginas del almacenamiento principal deben tener la misma probabilidad de ser reemplazadas.
Debe poder seleccionar cualquier página, incluyendo la que va a ser referenciada a continuación (peor selección).
Este esquema es raramente usado.
Reposición de Página por el Sistema de Primero en Entrar -Primero en Salir (FIFO)
Se registra el momento en que cada página ingresa al almacenamiento primario.
Para reemplazar una página, se selecciona aquella que ha estado más tiempo almacenada.
Se presenta el inconveniente de que se pueden reemplazar páginas muy usadas, que serán llamadas de nuevo al almacenamiento primario casi de inmediato.
Se puede presentar la llamada “anomalía FIFO”:
• Belady, Nelson y Shedler descubrieron que con la reposición FIFO, ciertos patrones de referencias de páginas causan más fallos de páginas cuando se aumenta el número de marcos (celdas) de páginas asignados a un proceso: en esto consiste la “anomalía FIFO”.
• Esta anomalía contradice a la intuición (ver Figura 3.34 [7, Deitel]).
Reposición de Página Menos - Recientemente - Usada (LRU)
Esta estrategia selecciona para ser reemplazada la página que no ha sido usada durante el mayor período de tiempo.
Se basa en la heurística de que el pasado reciente es un buen indicador del futuro próximo.
Requiere que cada página reciba un “sello de tiempo” cada vez que se referencia:
• Puede significar una sobrecarga adicional importante.
• No se implementa frecuentemente.
La página seleccionada para reemplazo podría ser la próxima en ser requerida, por lo que habría que paginarla de nuevo al almacenamiento principal casi de inmediato.
Reposición de Página Menos - Frecuentemente - Usada (LFU)
Acá interesa la intensidad de uso que haya tenido cada página.
La página que será reemplazada es aquella que ha sido usada con menos frecuencia o que ha sido referida con menos intensidad.
El inconveniente es que se puede seleccionar fácilmente para su reposición la página equivocada:
• Ej.: La página de uso menos frecuente puede ser la página de entrada más reciente al almacenamiento principal, y por lo tanto existe una alta probabilidad de que sea usada de inmediato.
Reposición de Página No Usada - Recientemente (NUR)
Presupone que las páginas que no han tenido uso reciente tienen poca probabilidad de ser usadas en el futuro próximo y pueden ser reemplazadas por otras nuevas.
Es deseable reemplazar una página que no ha sido cambiada mientras estaba en el almacenamiento primario.
La estrategia NUR se implementa con la adición de dos bits de hardware por página:
• “Bit referenciado”:
o = 0 si la página no ha sido referenciada.
o = 1 si la página ha sido referenciada.
• “Bit modificado” (también llamado “bit sucio”):
o = 0 si la página no ha sido modificada.
o = 1 si la página ha sido modificada.
La selección de la página que será reemplazada comienza buscando una página que no ha sido referenciada, pero si no la encuentra habrá que reemplazar una página que ha sido referenciada.
Si una página ha sido referenciada se comprueba si ha sido modificada o no:
• Si no ha sido modificada se la reemplaza:
o Su reposición representa menos sobrecarga que la de una página modificada, ya que debería grabarse de nuevo en el almacenamientos secundario.
• Si no se encuentra una página que no ha sido modificada será reemplazada una página modificada.
Con el transcurso del tiempo la mayoría de los “bits referenciados” serán activados:
• Se pierde la capacidad para distinguir las páginas más deseables para ser reemplazadas.
• Para evitarlo se ajustan periódicamente todos los “bits referenciados” a “0”:
o Se logra un nuevo inicio.
o Se vuelve vulnerable al reemplazo aún a las páginas activas, pero solo brevemente, mientras se reajustan los bits.
Los “bits modificados” no se ajustan periódicamente según esta estrategia.
Localidad
El concepto de “localidad” expresa [7, Deitel]:
• “Los procesos tienden a hacer referencia al almacenamiento en patrones no uniformes y muy localizados”.
La “localidad” se manifiesta en el “tiempo” y en el “espacio”:
• Es una propiedad empírica (observada).
• Nunca está garantizada pero es altamente probable.
• Ej.: Los procesos tienden a favorecer ciertos subconjuntos de páginas, las que tienden a ser adyacentes entre sí en el espacio de direcciones virtuales del proceso.
• Está relacionada con la forma en que se escriben los programas y se organizan los datos.
“Localidad temporal ”: significa que las localidades de almacenamiento referenciadas recientemente tienen una alta probabilidad de ser referenciadas en un futuro próximo:
• Se apoya en la utilización de:
o Formación de ciclos (loops).
o Subrutinas.
o Pilas.
o Variables usadas para contar y totalizar.
“Localidad en el espacio”: significa que las referencias de almacenamiento tienden a acumularse de manera tal que, una vez que se hace referencia a una localidad, es muy probable que las localidades cercanas sean también referenciadas:
• Se apoya en la utilización de:
o Recorrido de arreglos.
o Ejecución secuencial de código.
o Tendencia de los programadores a colocar definiciones de variables relacionadas, próximas entre sí.
Un programa puede ejecutar eficientemente mientras su subconjunto de páginas preferido se encuentre en el almacenamiento primario.
El número de fallos de páginas de un proceso depende de la cantidad de almacenamiento primario disponible para sus páginas.
Generalmente los procesos no muestran patrones de referencias aleatorios uniformemente distribuidos por sus diferentes páginas.
Al reducir el número de marcos (celdas) de páginas disponibles para un proceso existe un intervalo durante el cual la razón de fallos de páginas no se afecta excesivamente.
En determinado punto, cuando se reduce más el número de marcos de páginas, el número de fallos de páginas aumenta drásticamente.
Mientras el subconjunto de páginas favorecidas por un proceso permanezca en el almacenamiento primario, el número de fallos de páginas no aumenta mucho.
Tan pronto como las páginas del subconjunto favorecido son retiradas del almacenamiento primario, la actividad de paginación del proceso aumenta en gran medida al referenciar y traer de nuevo estas páginas al almacenamiento primario.
Los “subconjuntos favorecidos” también son llamados “conjuntos de trabajo” o “working sets” (ver Figura 3.35 [7, Deitel]).
Inicio: Fin:
Conjuntos de Trabajo
Denning desarrolló un punto de vista de la actividad de paginación de un programa llamado la “teoría de conjunto de trabajo del comportamiento de un programa” [7, Deitel].
Un “conjunto de trabajo” es una colección de páginas a las cuales un proceso hace activamente referencia.
Denning sostenía que para que un programa se ejecutara eficientemente, su conjunto de trabajo debe ser mantenido en el almacenamiento primario, para evitar la “hiperpaginación”.
Una “política de administración de almacenamiento por conjunto de trabajo” trata de mantener el conjunto de trabajo de los programas activos en el almacenamiento primario.
La decisión de añadir un nuevo proceso al conjunto activo de procesos (aumentar el nivel de multiprogramación):
• Se basa en si hay suficiente espacio disponible en el almacenamiento primario como para acomodar el conjunto de trabajo del nuevo proceso.
• Se toma generalmente de forma heurística ya que es imposible para el sistema conocer por anticipado el tamaño del conjunto de trabajo de un proceso dado.
El conjunto de trabajo de páginas de un proceso “w(t,w)” en el momento “t” es el conjunto de páginas referidas por un proceso durante el intervalo de tiempo del proceso “t - w” a “t ” (ver Figura 3.36 [7, Deitel]).
El “tiempo del proceso” es el tiempo durante el cual este proceso tiene la cpu.
La variable “w” se denomina “tamaño de la ventana del conjunto de trabajo”:
• La determinación del tamaño de “w” es muy importante.
• Al aumentar el tamaño de la ventana “w” aumenta el tamaño del conjunto de trabajo (ver Figura 3.37 [7, Deitel]).
“El verdadero conjunto de trabajo de un proceso es el conjunto de páginas que deben estar en el almacenamiento primario para la ejecución eficaz de este proceso”.
Los conjuntos de trabajo cambian mientras un proceso está en ejecución:
• Complica la administración precisa del almacenamiento primario en base a esta estrategia.
• “Los conjuntos de trabajo son transitorios y el siguiente conjunto de trabajo del proceso puede diferir substancialmente de su conjunto de trabajo anterior”.
• Se debe evitar un exceso de compromiso del almacenamiento primario y la consecuente hiperpaginación.
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA
3.8.3 Paginación por demanda.
Paginación por demanda.-
Es similar a lo visto para la paginación introduciendo el concepto de swapping. Los procesos residen en el disco y al ser ejecutados deben ser cargados en memoria. Cuando un proceso va a ser ejecutado, el mismo es swappeado a memoria, utilizando lazy swapping. El lazy swapping nunca trae paginas a memoria si no van a ser ejecutadas. Se necesita determinar si un pagina esta en memoria o en disco, por lo cual se utiliza el bit de válido / inválido de la tabla de páginas. Si el bit = 1 la página es valida y esta cargada en memoria si es 0 la página es inválida y no esta cargada en memoria (esta en disco).
Cuando un proceso intenta acceder a una página que no esta cargada en memoria ocurre un page fault (tomo de página). El procedimiento para manejar un page fault es el siguiente:
1. Verificar si la referencia a la pagina es valida (se utiliza una tabla interna (generalmente llevada en PCB) donde se indica las paginas validas.
2. Si la referencia no es valida, se cancela la ejecución del proceso.
3. Encontrar un frame disponible para cargarla (la página esta en disco)(por ejemplo de la free frame list)
4. Solicitar operación de I/O para leer la página de disco cargarla en el frame obtenido.
5. Modificar la tabla interna y la tabla de paginas para que ahora esta pagina figure como que esta en memoria.
6. Continuar con la ejecución del proceso en la instrucción en la que fue interrumpido.
Paginación por Demanda
Las paginas son cargadas por demanda [7, Deitel].
No se llevan páginas del almacenamiento secundario al primario hasta que son referenciadas explícitamente por un proceso en ejecución.
Las razones del atractivo de esta estrategia son:
• Los resultados de computabilidad, en especial el “problema de parada”, indican que el camino que tomará la ejecución de un programa no se puede predecir con exactitud.
• Garantiza que solo las páginas que necesita el proceso sean traídas al almacenamiento principal.
• La sobrecarga de proceso para decidir qué página traer al almacenamiento principal es mínima.
El principal inconveniente está en los procesos que requieren acumular sus páginas una por una:
• Los tiempos de espera de páginas son considerables.
• Es creciente la cantidad de almacenamiento primario afectada al proceso que espera páginas, por lo que el “producto espacio - tiempo” se incrementa.
El “producto espacio - tiempo” indica la cantidad de almacenamiento que usa un proceso y la cantidad de tiempo que lo usa.
“La reducción del producto espacio - tiempo de las esperas de páginas de un proceso es una meta importante de las estrategias de administración del almacenamiento” (ver Figura 3.38 [7, Deitel]).
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA
3.8.4 Paginación anticipada.
Paginación Anticipada
El S. O. intenta predecir las páginas que un proceso va a necesitar y a continuación precarga estas páginas cuando hay espacio disponible [7, Deitel].
Mientras el proceso ejecuta sus páginas actuales, el sistema carga páginas nuevas que estarán disponibles cuando el proceso las pida, debido a ello, el tiempo de ejecución de un proceso se puede reducir.
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA
3.8.5 Liberación de página.
Liberación de Página
Un proceso usuario puede emitir una “liberación voluntaria de página” para liberar el marco de página cuando ya no necesitara esa página [7, Deitel].
Se puede eliminar el “desperdicio” y acelerar la ejecución.
El inconveniente es que la incorporación de mandatos de liberación de páginas dentro de los programas de usuarios puede ser peligroso y retrasar el desarrollo de aplicaciones.
“Los compiladores y S. O. deberían detectar automáticamente situaciones de liberación de página mucho antes de lo que es posible con estrategias de conjuntos de trabajo”.
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA
3.8.6 Tamaño de página.
Tamaño de Página
Generalmente el almacenamiento real se divide en marcos o celdas de página de tamaño fijo [7, Deitel].
Los interrogantes tienen que ver con el tamaño de las páginas, si todas las páginas tendrán igual tamaño, si en caso de utilizar páginas de diferente tamaño las páginas mayores deben ser o no múltiplos enteros de las menores, etc.
Algunas consideraciones para determinar el tamaño de página son las siguientes:
• Cuanto más pequeño sea el tamaño de una página, más páginas y marcos de páginas habrá y mayores serán las tablas de páginas:
o El desperdicio de almacenamiento debido al tamaño excesivo de las tablas de página se llama “fragmentación de tablas”.
o Esto indica la necesidad de páginas más grandes.
• Con páginas grandes, grandes cantidades de información que nunca llegaría a ser referenciada, se paginarán hacia el almacenamiento primario:
o Esto indica la necesidad de páginas más pequeñas.
• Debido a que las transferencias de e / s del disco (paginación) consumen bastante tiempo, se debe minimizar la paginación que un proceso requiera:
o Esto indica la necesidad de páginas grandes.
• Los programas tienden a mostrar la propiedad de localidad de referencia y esta localidad tiende a ser pequeña:
o Esto indica la necesidad de páginas pequeñas.
• Los procedimientos y datos rara vez comprenden un número entero de páginas, por lo que los sistemas de paginación experimentan una “fragmentación interna”:
o El desperdicio promedio es de 1 / 2 página no usada por segmento (grupo) de páginas, que estará en la última página del segmento.
o Esto indica la necesidad de páginas pequeñas.
Los tamaños de pagina mas utilizados son: 512 b, 1 kb, 2 kb, 4 kb.
No hay comentarios:
Publicar un comentario