Proyecto Sistemas Operativos- Paginacion de Memoria PDF

Preview

Summary

Este proyecto trata sobre las políticas de reemplazo de paginas.
Todo el contenido esta establecido en un formato de investigación/Informe.
Es un proyecto requerido semestralmente....

Description

UNIVERSIDAD NACIONAL DE SAN ANTONIO ABAD DEL CUSCO FACULTAD DE INGENIERIA ELECTRICA ELECTRONICA INFORMATICA Y MECANICA ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

Sistemas Operativos Políticas de reemplazo de páginas para la gestión de memoria en el sistema operativo Android Docente

: Palomino Olivera Emilio

Alumnos

:

➢-

Cusco – Perú 2017

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

Contenido CAPITULO 1:.................................................................................................................................2 1.1.

Resumen.......................................................................................................................2

1.2. Antecedentes....................................................................................................................3 1.3. Problema...........................................................................................................................4 1.4. Justificación.......................................................................................................................5 1.5. Objetivos...........................................................................................................................5 1.5.1. Objetivo General.........................................................................................................5 1.5.2. Objetivo Específico.....................................................................................................5 1.6. Alcance..............................................................................................................................6 1.7. Limitaciones......................................................................................................................6 CAPÍTULO 2..................................................................................................................................6 2.1. MARCO TEÓRICO...............................................................................................................6 2.1.1. Paginación..................................................................................................................6 2.1.2. Paginación por demanda............................................................................................8 2.1.3. Tratamiento de fallo de página..............................................................................9 2.1.4. Políticas de reemplazo.........................................................................................10 2.1.5. ALGORITMOS DE REEMPLAZO DE PÁGINAS..............................................................10 CAPITULO 3................................................................................................................................17 3.1. Metodología....................................................................................................................17 3.2. Resultados a Priori Esperados..........................................................................................18 3.3. Contribuciones originales esperadas...............................................................................18 3.4. Impacto Social Esperado..................................................................................................18 3.5. DESARROLLO...................................................................................................................19 3.5.1. Resumen de análisis de RESULTADOS de los ejemplos que se realizaron:................28 3.6. Conclusiones...................................................................................................................30 3.7. Anexos.............................................................................................................................30 3.8. Bibliografía......................................................................................................................31

1

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

INTRODUCCION

PRESENTACION

2

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

CAPITULO 1: 1.1. Resumen El presente trabajo realiza el análisis y la evaluación del desempeño de los algoritmos de reemplazo de páginas en Android, el tema de políticas de reemplazo de página es a la vez el surgimiento de los temas como fallo de página, paginación por demanda, y otras. Veremos de manera más detallada todo el proceso de la implementación de los algoritmos de reemplazo en un lenguaje de alto nivel como Java. Las políticas de reemplazo se pueden clasificar en dos categorías: reemplazo global y reemplazo local. Con una estrategia de reemplazo global, se puede seleccionar toda la memoria principal, para satisfacer el fallo de página de otro proceso. Esto es, un proceso puede quitarle un marco de página a otro. La estrategia de reemplazo local requiere que, para servir el fallo de página de un proceso, sólo pueden usarse marcos de páginas libres o marcos ya asociados al proceso. Existen numerosos trabajos, tanto teóricos como experimentales, sobre algoritmos de reemplazo de páginas. En este trabajo de investigación se describirán los algoritmos de reemplazo FIFO, LFU, Envejecimiento, MFU, LRU, de Reemplazo Óptimo, de segunda oportunidad o algoritmo de reloj y reloj mejorado. Cuando se aplica un algoritmo determinado utilizando una estrategia global, el criterio de evaluación del algoritmo se aplicará a todas las páginas en memoria principal. En el caso de una estrategia local, el criterio de evaluación del algoritmo se aplica sólo a las páginas en memoria principal que pertenecen al proceso que causó el fallo de página. La descripción de los algoritmos, por tanto, se realizará sin distinguir entre los dos tipos de estrategias.

3

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

1.2. Antecedentes Al inicio de las computadoras, el concepto de memoria era muy distinto al actual. Primero se usaron las tarjetas perforadas, las cuales servían para ingresar y almacenar datos e instrucciones a un computador, luego una serie de inventores fueron mejorando las capacidades de ésta. A partir del 2003, cada año se fueron realizando mejoras en distintos aspectos de la memoria, ya sea de velocidad de transferencia de datos, de capacidad de almacenamiento, de frecuencias a las que puede trabajar, entre otros. La memoria es uno de los principales recursos de la computadora, la cual debe de administrarse con mucho cuidado. Aunque actualmente la mayoría de los sistemas de cómputo cuentan con una alta capacidad de memoria, de igual manera las aplicaciones actuales tienen también altos requerimientos de memoria, lo que sigue generando escasez de memoria en los sistemas multitarea y/o multiusuario. A medida que el computador utiliza memoria y la memoria libre escasea, el sistema operativo comienza a recortar el conjunto de trabajo del proceso y a utilizar el archivo de paginación de forma más agresiva. El uso del archivo de paginación afecta al rendimiento general porque las operaciones en disco tardan más en realizarse que las operaciones realizadas en la memoria. Además, cuando la paginación hacia y desde el disco sube de nivel lo suficiente, acaba produciendo un cuello de botella en el disco y deterioro del rendimiento. Frente a esta situación se plantea estrategias para reemplazar páginas de memoria.

4

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

1.3. Problema El administrador de memoria se encarga de manejar la gestión de páginas de memoria en RAM o en disco. Los segmentos de memoria virtual se particionan en unidades llamadas páginas. Un espacio de paginación es un tipo de volumen lógico con espacio de disco asignado que almacena la información que reside en la memoria virtual a la que no se accede actualmente. Este volumen lógico tiene un tipo de atributo igual a la paginación, y normalmente se hace referencia a él como espacio de paginación o espacio de intercambio. Cuando la cantidad de RAM libre en el sistema es baja, los programas o datos que no se han utilizado recientemente se mueven de la memoria al espacio de paginación a fin de liberar memoria para otras actividades. El problema más común en relación al espacio de paginación está provocado por quedarse sin espacio asignado. Cuando hablamos de políticas de reemplazo de memoria nos referimos a una serie de mecanismos habilitados por el sistema operativo para simular, de forma transparente para el usuario, la existencia de mayor cantidad de memoria física que la realmente instalada en realidad. A grandes rasgos esto se consigue empleando un dispositivo de almacenamiento secundario (típicamente un disco duro) y una serie de mecanismos hardware y software que permitan mantener en memoria sólo los fragmentos de memoria que se están usando en un momento dado, almacenando en el disco el resto y realizando la carga y el almacenamiento de los mismos según es necesario en cada momento. En sistemas operativos que utilizan paginación para el manejo de memoria, los algoritmos de reemplazo de páginas son usados para decidir qué páginas pueden ser sacadas de memoria cuando se necesita cargar una nueva y ya no hay marcos de páginas libres.

5

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

1.4. Justificación Toda la dificultad del páginamiento en demanda está en decidir qué páginas conviene llevar a disco cuando la memoria se hace escasa. La idea es que la página que se lleve a disco debe causar un fallo de página (page-fault) lo más tarde posible. Por lo tanto se puede deducir que el sistema de páginamiento ideal debe llevar a disco aquella página que no será usada por el período de tiempo más largo posible. Desde luego, en términos prácticos el núcleo no puede predecir por cuánto tiempo una página permanecerá sin ser referenciada, por lo que es necesario recurrir a estrategias que se aproximen al caso ideal. Estas estrategias se denominan estrategias de reemplazo de páginas. Las estrategias de reemplazo de páginas son realizadas por el núcleo del sistema operativo. La componente de código del núcleo que se encarga de esta labor podríamos definirlo como el scheduler de páginas. Por lo tanto dada esta situación surge la necesidad de implementar algoritmos de reemplazo de página que puedan realizar la gestión de memoria de forma que se aproximen a una buena eficiencia.

1.5. Objetivos 1.5.1. Objetivo General Análisis de los resultados de la implementación de los algoritmos de reemplazo de página de Gestión de Memoria en Android.

1.5.2. Objetivo Específico 1. Entender el funcionamiento de los algoritmos de reemplazo. 2. Evaluar el rendimiento del hardware al ejecutar los algoritmos de reemplazo. 3. Mostrar los resultados del análisis. 4. Determinar que algoritmos de reemplazo de páginas son más óptimas y las que tienen una menor número de fallos.

6

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

1.6. Alcance En este documento pretendemos dar a conocer el análisis de implementación de los algoritmos de reemplazo de página.

1.7. Limitaciones No pretendemos optimizar los algoritmos de políticas de reemplazo ni crear estructuras que se les parezcan.

CAPÍTULO 2 2.1. MARCO TEÓRICO 2.1.1. Paginación El espacio virtual de direcciones se divide en unidades llamadas páginas, todas del mismo tamaño. La memoria principal se divide en marcos de páginas (page frames) del mismo tamaño que las páginas virtuales y son compartidas por los distintos procesos del sistema (en cada marco de página se carga una página de un proceso). No todo el espacio virtual de direcciones está cargado en memoria central. Una copia completa se encuentra en disco y las páginas se traen a memoria central cuando se necesitan. -

Tabla de páginas (TP): Relaciona cada página con el marco que la contiene. MMU usa TP para traducir direcciones lógicas a físicas. Típicamente usa 2 TPs: TP usuario y TP sistema (solo se permite usar estas direcciones en modo sistema).

Transformación de la dirección virtual en dirección física: Los bits de mayor peso de la dirección se interpretan como el número de la página en la TP y los de menor peso como el número de palabra dentro de la página (desplazamiento). 7

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

Los tamaños de página (condicionado por diversos factores contrapuestos): Potencia de 2 y múltiplos del tamaño del bloque de disco (compromiso entre 2k y 16k).

Pasos de funcionamiento: 1.- La MMU toma la parte asociada al número de página de la dirección lógica. 2.- Busca la entrada de la tabla de páginas: Obteniendo el marco de página. 3.- Indexa el byte dentro del marco de página de la memoria física.

Figura 1: Esquema de traducción de la paginación Fuente: http://slideplayer.es/slide/1715177/ Se puede observar que con la paginación se le asigna a cada proceso un número entero de marcos de página, aunque, en general, su mapa no tendrá un tamaño múltiplo del tamaño del marco. Por tanto, se desperdiciara parte del último marco asignado al proceso, lo que corresponde con las zonas sombreadas que aparecen en la figura siguiente. A ese fenómeno se le 8

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

denomina fragmentación interna e implica que por cada proceso se desperdiciara, la mitad de una página, lo cual es un valor bastante tolerable. Vemos que esto sucede cuando la memoria asignada > memoria requerida y por lo cual pueden pasar estas 2 situaciones: -

Puede desperdiciarse parte de un marco asignado. Espacio desperdiciado medio (por región de proceso) es la mitad de página.

Figura 2: Fragmentación interna asociada a la paginación Fuente: http://slideplayer.es/slide/1715177/ Cada entrada de la tabla de páginas, además del número de marco que corresponde con esa página, contiene información adicional tal como la siguiente: Tenemos que tener en cuenta que la determinación del tamaño óptimo es un compromiso entre diversos factores: -

-

Un tamaño pequeño reduce la fragmentación y, como se verá más adelante, cuando se usa para implementar memoria virtual, permite ajustarse mejor al conjunto de trabajo del proceso. Un tamaño grande implica tablas más pequeñas y, cuando se usa para implementar memoria virtual, un mejor rendimiento en los accesos a disco.

2.1.2. Paginación por demanda Surge a partir de la necesidad de requerir una página de un proceso la cual fue requerido quizá por otra y esto se lleva a cabo a partir de un evento más conocido como fallo de página que ocurre cuando un proceso necesita de una 9

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

página y no se encuentre en la memoria principal para ejecutarlo veamos sus características: -

Segmentación pura no adecuada para memoria virtual 

-

Paginación y segmentación paginada sí lo son:  

-

tamaño de segmentos variable

Bloque transferido – >Página M. virtual + Paginación - >Paginación por demanda

Estrategia de implementación: Uso del bit de validez  

Página no residente se marca como no válida En acceso: Excepción de fallo de página . S.O. trae la página correspondiente de memoria secundaria . S.O. debe diferenciar entre pág. no residente y pág. inválida

-

Pre paginación: Traer páginas por anticipado (no por demanda)  

En fallo de página se trae además otras páginas que se considera que necesitará el proceso Beneficiosa dependiendo de si hay acierto en la predicción

2.1.3. Tratamiento de fallo de página La paginación por demanda está dirigida por la ocurrencia de excepciones de fallo de página que indican al sistema operativo que debe traer una página de memoria secundaria a primaria, puesto que proceso la requiere. A continuación, se especifican los pasos típicos en el tratamiento de un fallo de página: -

-

La MMU produce una excepción y típicamente deja en un registro especial la dirección que causó el fallo. Se activa el sistema operativo que comprueba si se trata de una dirección correspondiente una página realmente inválida o se corresponde con una página ausente de memoria. Si la página es inválida, se aborta el proceso o se le manda una señal. En caso contrario, se realizan los pasos que se describen a continuación. Se consulta la tabla de marcos para buscar uno libre. Si no hay un marco libre, se aplica el algoritmo de reemplazo para seleccionar una página para expulsar. El marco seleccionado se desconectara de la página a la que esté asociado poniendo como invalida la entrada correspondiente. Si la página está modificada, previamente hay que escribir su contenido a la memoria secundaria. 10

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

-

Una vez que se obtiene el marco libre, ya sea directamente o después de una expulsión, se inicia la lectura de la nueva página sobre el marco y, al terminar la operación, se rellena la entrada correspondiente a la página para que esté marcada como válida y apunte al marco utilizado.

Se puede observar que en el peor de los casos, en un fallo de página puede causar 2 operaciones de entrada/salida al disco.

2.1.4. Políticas de reemplazo Existen una variedad grande de algoritmos de reemplazo de páginas, pero en este apartado se verán los más típicos y primordiales quizá a la hora de querer programarlos, todos estos algoritmos se pueden utilizar tanto como estrategias globales como locales. Cuando aplicamos la estrategia global el criterio de evaluación del algoritmo se aplicará a todas las páginas en memoria principal. En caso contrario de una estrategia local el criterio de evaluación del algoritmo se aplica sólo a páginas de memoria principal que pertenezcan al proceso que causó el fallo de página.

2.1.5. ALGORITMOS DE REEMPLAZO DE PÁGINAS 2.1.5.1. Algoritmo FIFO Asocia cada página el instante en que dicha página fue cargada en memoria. Cuando hace falta sustituir una página se elige la página más antigua. Se crear una cola FIFO para almacenar todas las páginas en memoria y sustituir la página situada al principio de la cola. Es fácil de entender y de programar, sin embargo su rendimiento no siempre es bueno. Anomalía de Belady la tasa de fallos de página puede incrementarse a medida que se incrementa el número de marcos asignados.

2.1.5.1.1 Anomalía de Belady

Es un efecto, por el cual es posible tener más fallos de página al aumentar el número de marcos en la memoria física utilizando el método FIFO como 11

ESCUELA PROFESIONAL DE INGENIERÍA INFORMÁTICA Y DE SISTEMAS

algoritmo de reemplazo de páginas en sistemas de gestión de memoria virtual con paginación. Antes de esta fecha, se creía que incrementar el número de marcos físicos siempre llevaría a un descenso del número de fallos de página o, en el peor de los casos, a mantenerlos. Así, pues, antes del descubrimiento de la anomalía de Belady, el algoritmo FIFO era aceptable. El siguiente es un ejemplo de la anomalía de Belady. Utilizando tres marcos ocurren 9 fallos de página. Aumentando a cuatro marcos obtenemos 10 fallos de página.

2.1.5.2. Algoritmo LFU (Less frecuently used, por sus siglas en ingles) En el algoritmo NFU (página no referenciada frecuentemente - no frecuentemente utilizada), se establece si en un intervalo de tiempo (por ejemplo, un tick de reloj) una página ha sido o no referenciada. Se lleva la cuenta del número de intervalos que cada página ha sido referenciada, eligiendo como víctima la de cuenta más baja. Para cada página se requiere, además del bit R que se activa en cada referencia, un contador. En cada tick de reloj, para cada página, el bit R se acumula en el contador. Comparado con LRU puro, en NFU los conta...