´ de la memoria] Sistemas Operativos [Administracion ´ ´ M. en C. Sergio Luis Perez Perez

´ UAM C UAJIMALPA , M EXICO , D. F. Trimestre 13-O

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

1 / 56

´ La memoria basica

´ La memoria basica I La mayor´ıa de las computadoras tienen una jerarqu´ıa de memoria. ´ piramidal La jerarqu´ıa de memoria se refiere a la organizacion de la memoria en niveles. El objetivo es conseguir el rendimiento de una memoria de gran velocidad al costo de una memoria de baja velocidad. Lo anterior se logra con base en el principio de cercan´ıa de referencias. La cercan´ıa de referencias es el agrupamiento de las lecturas de memoria por medio del procesador. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

2 / 56

´ La memoria basica

´ La memoria basica II La cercan´ıa de referencias permite que los programas que cuentan con un cierto numero de ciclos y subrutinas iterativas ´ ˜ produzcan referencias repetidas que consideren un pequeno conjunto de instrucciones. Las agrupaciones de uso con el tiempo son variables, pero son fijas dentro de per´ıodos cortos de tiempo. ´ permite que un programa en ejecucion ´ no necesite Tambien, ´ todas sus paginas cargadas en la memoria principal. ´ procesos en memoria listos para Con esto es posible tener mas ´ correr y no se tienen que cargar y descargar sus paginas en el momento de un intercambio. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

3 / 56

´ La memoria basica

´ La memoria basica III La localidad de las referencias (principio de localidad), ´ basandose en el pasado reciente de un programa, permite ´ en un futuro. predecir que´ instrucciones y datos se utilizaran Se dividen en tres grupos: ´ de memoria es Localidad temporal. Cuando una posicion ´ referenciada, entonces muy probablemente la misma ubicacion vuelva a ser referenciada en un futuro cercano. ´ de memoria es Localidad espacial. Si una localizacion referenciada en un momento concreto, probablemente las ´ referenciadas pronto. localizaciones cercanas a ella sean tambien ´ Localidad secuencial. Las direcciones de memoria que se estan utilizando suelen ser contiguas.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

4 / 56

´ La memoria basica

´ La memoria basica IV

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

5 / 56

´ La memoria basica

´ La memoria basica V La parte del sistema operativo que administra la jerarqu´ıa de memoria se llama administrador de memoria. Las funciones del administrador de memoria son: ´ ´ en uso y cuales ´ Determinar cuales partes de la memoria estan no. Asignar memoria a los procesos cuando la necesitan y liberarla cuando terminan. Administrar los intercambios entre la memoria principal y el disco.

´ se describen algunos mecanismos para la A continuacion ´ de la memoria. administracion

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

6 / 56

´ La memoria basica

´ La memoria basica VI ´ sin intercambio ni paginacion ´ Mono-programacion ´ programa a la vez, repartiendo la Consiste en ejecutar un solo memoria entre ese programa y el sistema operativo. Hay tres enfoques: 1

´ baja de la RAM y en lo demas ´ un El SO estaba en la parte mas programa de usuario (mainframes y minicomputadoras antiguas).

2

El SO estaba en la ROM y un programa de usuario en RAM (sistemas integrados).

3

´ alta de la ROM y el resto del Los controladores en la parte mas ´ baja de la RAM (la parte del sistema que sistema en la parte mas estaba en ROM era el BIOS).

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

7 / 56

´ La memoria basica

´ La memoria basica VII ´ con particiones fijas Multiprogramacion ´ permite la ejecucion ´ de varios procesos a la La multiprogramacion vez. ´ de E/S, Si un proceso se bloquea en espera de una operacion entonces otro puede usar el procesador al mismo tiempo. ´ consiste en dividir la Una forma sencilla de multiprogramacion memoria en n particiones no necesariamente iguales. ´ puede realizarse de forma manual al arrancar el Dicha particion sistema. ´ ´ mas ´ Cuando llega un trabajo este se coloca en la particion ˜ que cabe. pequena ´ Con este metodo hay parte de la memoria que se desperdicia. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

8 / 56

´ La memoria basica

´ La memoria basica VIII ´ con particiones fijas Estrategias para la multiprogramacion 1

´ de la memoria, donde se Se crea una cola por cada particion encuentran esperando los procesos que caben en ella

2

Se crea una cola para todos los procesos y cada uno de ellos es ´ disponible mas pequena ˜ en la que cabe. colocado en la particion

3

´ Teniendo una sola cola, esta es analizada y se elige al programa ´ grande que cabe en cada particion ´ disponible. mas

4

´ de procesos se establece un l´ımite Para evitar la discriminacion en el numero de veces que se puede ignorar un proceso. ´

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

9 / 56

´ La memoria basica

´ La memoria basica IX ´ Modelado de la multiprogramacion ´ es de forma Una forma de modelar la multiprogramacion probabil´ıstica. ´ de su tiempo que un proceso espera a que Sea p la fraccion terminen operaciones de E/S. Si hay n procesos en la memoria la probabilidad de que todos ´ esperando a la vez es pn . esten El aprovechamiento del procesador (AP) esta´ dado entonces por ´ la formula: AP = 1 − pn ´ de n que El aprovechamiento de un procesador esta´ en funcion ´ se conoce como grado de multiprogramacion. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

10 / 56

´ La memoria basica

´ La memoria basica X Ejercicio Suponga que una computadora tiene 64 MB de memoria de los cuales 32 MB son ocupados por el SO. Supongamos que cualquier programa de usuario utiliza 8 MB. Si la espera media de un proceso en operaciones E/S es el 80 %. ´ es el AP de dicha computadora? ¿Cual ¿Cual ser´ıa el AP de esta computadora si incrementamos la memoria en 32 MB? ´ ¿Cuanta memoria debe ser agregada si deseamos obtener un AP de 90 %?

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

11 / 56

´ La memoria basica

´ La memoria basica XI ´ se deben resolver dos problemas Con la multiprogramacion ´ y la proteccion. ´ importantes: la reubicacion ´ se refiere al problema de reubicar las direcciones La reubicacion absolutas de un programa (indicadas en el archivo binario) en ´ donde es direcciones relativas (considerando la particion colocado el programa). ´ es modificar las instrucciones en el momento que el Una solucion programa se carga en la memoria. ´ que inicia en Por ejemplo si el programa se carga en la particion ´ 100 KB entonces se suman 100 KB a cada una de las la posicion direcciones mencionadas en el. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

12 / 56

´ La memoria basica

´ La memoria basica XII ´ se refiere al problema de evitar que programas mal La proteccion intencionados escriban y lean de la memoria perteneciente a otros usuarios. ´ es utilizar dos registros especiales de hardware: Una solucion base y l´ımite. ´ de inicio de la particion ´ En el registro base se carga la direccion asignada a un proceso calendarizado. ´ El registro l´ımite se carga con la longitud de la particion. El registro l´ımite se encarga de verificar que las direcciones utilizadas por el programa no intenten hacer acceso a memoria ´ actual. fuera de la particion ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

13 / 56

´ de memoria Administracion

´ de memoria Administracion Cuando no hay suficiente memoria principal para contener a todos los procesos activos se acostumbra tener a los procesos excedentes en disco. ´ Existen dos enfoques generales para realizar esta administracion de memoria: el intercambio (swapping) y la memoria virtual. El intercambio es un enfoque que consiste en traer a la memoria un proceso, ejecutarlo un tiempo y devolverlo a disco. La memoria virtual permite que los programas se ejecuten ´ una parte de ellos este en memoria la principal. aunque solo

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

14 / 56

´ de memoria Administracion

Intercambio (swapping)

Intercambio (swapping) I ´ Cuando se realiza intercambio en una maquina con memoria con particiones fijas el intercambio es sencillo pues las direcciones de las particiones no cambian. Si la memoria se administra mediante particiones variables el problema es que las direcciones de las particiones cambian constantemente. ´ es La ventaja de las particiones fijas es que la administracion sencilla pero el desperdicio es grande. La ventaja de las particiones variables es que el desperdicio es ´ y liberacion ´ de memoria es complicado m´ınimo pero la asignacion y lento. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

15 / 56

´ de memoria Administracion

Intercambio (swapping)

Intercambio (swapping) II ´ ´ de memoria para Se puede utilizar la tecnica de compactacion ayudar a administrar la memoria durante los intercambios. ´ Dicha tecnica se utiliza cuando se crean huecos durante el intercambio. ´ de memoria permite unir tales huecos en uno La compactacion ´ mas ´ grande, tal que los procesos activos son desplazados solo ´ hacia una ubicacion. Por otro lado si se conoce de antemano la cantidad de memoria a asignar a un proceso el intercambio es sencillo. Si la cantidad de memoria que puede manejar un proceso es variable entonces puede ocurrir lo siguiente: ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

16 / 56

´ de memoria Administracion

Intercambio (swapping)

Intercambio (swapping) III ´ Si existe espacio adyacente libre entonces este es asociado a el proceso. Si no existe espacio adyacente libre pero existe un espacio disponible que lo soporte entonces se mueve el proceso. Si ya no hay espacio disponible (ni en la memoria ni en disco) el proceso tendra´ que esperar o terminar.

Cuando los procesos tienen dos segmentos diferentes capaces ´ tal que de crecer (datos y pila) se puede utilizar una organizacion ambos segmentos puedan crecer dentro de un espacio previamente reservado. ´ de memoria basadas en Existen dos formas de administracion intercambio: con mapas de bits y con listas ligadas. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

17 / 56

´ de memoria Administracion

Intercambio (swapping)

Intercambio (swapping) IV ´ de memoria con mapas de bits Administracion ´ y Un mapa de bits divide la memoria en unidades de asignacion asigna un 1 a las unidades ocupadas y 0 a las desocupadas. ´ es grande entonces se Si el numero de unidades de asignacion ´ requiere un mapa de bits costoso. ´ es pequeno ˜ el mapa de Si el numero de unidades de asignacion ´ bits es barato. ´ o tener ¿Que´ es mejor, tener muchas unidades de asignacion pocas? El problema de los mapas de bits son las busquedas de espacio. ´ ´ Para un proceso que requiere k unidades se requiere un metodo de busqueda de k unidades consecutivas disponibles. ´ ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

18 / 56

´ de memoria Administracion

Intercambio (swapping)

Intercambio (swapping) V ´ de memoria con listas ligadas Administracion Se mantiene una lista ligada con cuatro campos: Tipo de entrada. H para hueco y P para proceso. ´ donde comienza. Que es la suma de las longitudes La direccion de sus predecesores. La longitud. Longitud de la memoria asignada al proceso o hueco. Un apuntador a la siguiente entrada.

¿Que ocurre con la estructura cuando un proceso X termina de ejecutarse? Pista: Existen 4 casos (A,X,B), (A,X,H), (H,X,B), (H,X,H). ´ en forma de lista doblemente ligada? ¿Ayudar´ıa la organizacion

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

19 / 56

´ de memoria Administracion

Intercambio (swapping)

Intercambio (swapping) VI ´ de memoria con listas ligadas Algoritmos de administracion Primer ajuste. Se explora la lista hasta encontrar un espacio donde quepa el proceso. Siguiente ajuste. Se explora la lista pero continuando donde se quedo´ la busqueda anterior. ´ ˜ mas ´ Mejor ajuste. Se explora toda la lista y se elige el tamano adecuado. ˜ mas ´ grande. Peor ajuste. Se elige siempre el tamano ˜ mas ´ solicitados en ´ Ajuste rapido. Mantiene listas de los tamanos forma comun. ´

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

20 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual I

´ ´ Este metodo fue ideado por Fotheringham en 1961. ˜ combinado de un Esta idea surge de considerar que el tamano programa, sus datos y su pila pueden exceder la memoria f´ısica. De este modo se mantiene en memoria principal la parte del ´ y en disco el resto. programa en ejecucion ´ es la forma mas ´ comun ´ para la La paginacion ´ de administracion memoria virtual.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

21 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual II ´ I Paginacion ´ Cuando se escribe un programa, este realiza operaciones de escritura y lectura a memoria. Sin embargo en lugar de escribir sobre la memoria f´ısica la mayor´ıa de los sistemas escriben en una memoria virtual. De modo que las direcciones generadas por un programa se conocen como direcciones virtuales. Las direcciones virtuales viven en lo que se conoce como espacio de direcciones virtual. Cuando se utiliza memoria virtual las direcciones no se van de forma directa al bus de memoria. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

22 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual III ´ II Paginacion Las direcciones virtuales son administradas por una unidad de ´ de memoria (MMU Memory Management Unit). administracion El espacio de direcciones se divide en unidades llamadas ´ paginas. Las unidades en la memoria f´ısica que les corresponden a las ´ ´ paginas se denominan marcos de paginas. ´ entre ´ Se utiliza una tabla de paginas que mantiene la relacion las direcciones virtuales y la memoria f´ısica. ´ ´ Las unidades de las paginas y de los marcos de paginas son ˜ siempre del mismo tamano. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

23 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual IV ´ III Paginacion La memoria virtual permite que un programa de 128 MB pueda ser ejecutado en un sistema con 64 MB. ´ No todas las paginas tienen correspondencia con un marco de ´ pagina en todo momento. ´ Un fallo de pagina es cuando un programa trata de usar una ´ pagina que no tiene correspondencia en memoria f´ısica. ´ El sistema resuelve los fallos de pagina de la siguiente manera: ´ Busca un marco de pagina poco utilizado y lo reescribe en el disco. ´ ´ Va por la pagina que fue referenciada y la pone en el marco recien desocupado. ´ interrumpida. Modifica el mapa y reinicia la instruccion ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

24 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual V ´ ¿Como funciona la MMU? I

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

25 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual VI ´ ¿Como funciona la MMU? II ´ virtual 20818. Supongamos que se desea procesar la direccion

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

26 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual VII ´ Tablas de pagina ´ ´ ´ que En terminos de funciones la tabla de paginas es una funcion ´ ´ f´ısica toma un una pagina virtual y devuelve una direccion (aunque quien hace la labor es la MMU). ´ Los principales problemas de las tablas de paginas son: ´ La tabla de paginas puede ser muy grande. ´ debe ser rapida. ´ La transformacion

Las computadoras modernas utilizan direcciones virtuales de al menos 32 bits. ´ Si se consideran paginas de 4KB entonces un espacio de 32 bits ´ de paginas. ´ puede tener como un millon ´ ´ de entradas. Por tanto la tabla de paginas debe tener un millon ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

27 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual VIII ´ Tablas de pagina multinivel Este tipo de tablas elimina el problema de almacenar enormes ´ tablas de paginas en la memoria. Una forma de manejar direcciones virtuales de 32 bits es como sigue: ´ virtual de 32 bits, dividida en tres registros Se utiliza un direccion de 10(TN1), 10(TN2) y 12(desplazamiento) bits respectivamente. ´ Lo anterior significa que hay 220 paginas de 4KB cada una de ellas. ´ se utiliza una tabla de Nivel 1 con 210 entradas y 210 Tambien tablas de Nivel 2 con 210 entradas cada una. Suponga que un proceso requiere 12MB de memoria, divididos en 4MB para texto del programa, 4MB para datos y el resto para la pila.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

28 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual IX ´ ´ Como opera la MMU las tablas de pagina multinivel Del ejemplo anterior, primero la MMU toma primero el campo TP1 ´ virtual. de la direccion Ese valor sirve como ´ındice para consultar la tabla de Nivel 1. Cada entrada de la tabla de Nivel 1 representa 4MB (el espacio total es de 4GB). La entrada de la tabla de Nivel 1 proporciona el ´ındice de la correspondiente tabla de Nivel 2. La entrada de Nivel 2 proporciona el numero de marco donde se ´ ´ encuentra la pagina. ´ virtual 0x00403004? ¿Como se procesar´ıa la direccion ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

29 / 56

´ de memoria Administracion

La memoria virtual

La memoria virtual X ´ Estructura de una entrada de tabla de paginas ´ importante es el numero ´ El campo mas de marco de pagina. ´ ´ se encuentra el bit presente/ausente (A). Despues ´ (P) que indican los tipos de Luego siguen los bits de proteccion acceso que se encuentran permitidos. ´ Luego viene el bit modificada (M) que se enciende en automatico ´ (v´ıa hardware) cuando se escribe en una pagina. Luego sigue el bit solicitada (R) que se enciende cuando se hace ´ referencia a una pagina. Finalmente, el bit opcional uso de cache´ (C), habilita o deshabilita ´ el uso de cache´ para paginas que corresponden a registros. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

30 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas I ´ ´ Cuando ocurre un fallo de pagina el SO debe elegir la pagina a sacar de la memoria y colocar la que traera´ a disco. ´ Si la pagina a quitar fue modificada durante su estancia en memoria esta debe ser reescrita en disco. ´ Finalmente se sobreescribe la pagina a reemplazar. ´ ¿Que´ pagina es la que debe ser reemplazada? ´ El mismo problema se presenta cuando se utiliza cache. ´ se presentan diversos Para resolver esta pregunta a continuacion algoritmos. ´ ´ Algoritmo optimo de reemplazo de paginas. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

31 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas II ´ Algoritmo de reemplazo de paginas no utilizadas recientemente. ´ Algoritmo de reemplazo de paginas de PEPS (FIFO). ´ Algoritmo de reemplazo de paginas de segunda oportunidad. ´ Algoritmo de reemplazo de paginas tipo reloj. ´ Algoritmo de reemplazo de pagina menos utilizada recientemente. ´ de LRU en software. Simulacion ´ Algoritmo de reemplazo de paginas de conjunto de trabajo. ´ Algoritmo de reemplazo de paginas WSClock.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

32 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas III ´ ´ Algoritmo optimo de reemplazo de paginas ´ Suponga que cada pagina se rotula con el numero de ´ ´ antes de que se haga referencia instrucciones que se ejecutaran ´ a esa pagina. ´ Cuando ocurre un fallo de pagina lo ideal entonces es liberar la ´ ´ grande. pagina con el numero mas ´ ´ ´ pequeno? ˜ ¿Por que no liberar la pagina con el numero mas ´ ´ ¿El sistema operativo tiene forma de saber cuando se volvera´ a ´ hacer referencia a cualquiera de las paginas? ´ ¿Ser´ıa posible implementar este algoritmo? ¿Como?

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

33 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas IV ´ Algoritmo de reemplazo de paginas no utilizadas recientemente ´ Supongamos que a cada pagina se encuentran asociados los bits R y M. ´ Lo anterior da pie a categorizar las paginas como sigue: Clase 0 0 0 No solicitada, no modificada Clase 1 0 1 No solicitada, modificada Clase 2 1 0 Solicitada, no modificada Clase 3 1 1 Solicitada, Modificada ´ Cuando se presenta un fallo de pagina el SO examina todas las ´ ´ ´ paginas y elegira´ al azar una de las paginas con la clase mas baja. ´ ¿Como es posible que ocurra la clase 1? ¿Que´ tienen que ver las interrupciones? ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

34 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas V

´ Algoritmo de reemplazo de paginas de PEPS (FIFO) ´ En este caso el SO mantiene una lista de todas las paginas que ´ actualmente en memoria. estan ´ la lista esta´ ordenada colocando la pagina ´ ´ antigua Ademas mas ´ nueva al final. al principio de la lista y las mas ´ ´ Cuando ocurre un fallo de pagina se libera la pagina al principio de la lista. ¿Que´ problemas tiene este algoritmo?

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

35 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas VI ´ Algoritmo de reemplazo de paginas de segunda oportunidad ´ de llevar la cuenta de la antiguedad Este algoritmo ademas de ¨ ´ cada pagina considera el bit R. ´ ´ En el momento que ocurre un fallo de pagina, si la pagina que se encuentra al principio de la lista tiene encendido el bit R entonces se apaga el bit. ´ dicha pagina ´ Despues, se coloca al final de la lista como si fuera ´ una nueva pagina. ´ ¿Que´ significa el hecho de que el bit R de una pagina antigua se encuentre encendido? ´ ¿Que ocurre con este algoritmo en el peor de los casos? ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

36 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas VII

´ Algoritmo de reemplazo de paginas tipo reloj Es similar al algoritmo anterior pero con la diferencia de que las ´ ´ paginas no se cambian de ubicacion. ´ ´ En lugar de ello se mantiene un apuntador a la pagina mas ´ antigua y este se mueve en forma de manecillas del reloj. ´ se conoce como de cola circular. Este algoritmo tambien ´ ´ ´ Graficamente, ¿como visualiza este metodo?

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

37 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas VIII ´ Algoritmo de reemplazo de pagina menos utilizada recientemente I ´ Si una pagina se ha utilizado bastante recientemente probablemente se siga utilizando durante las siguientes instrucciones. ´ Un algoritmo factible consistir´ıa en liberar la paginas que no se han utilizado mucho recientemente. Esta estrategia se conoce como LRU (Least recently used). Una forma de implementarla ser´ıa utilizando un contador hardware C digamos de 64 bits. ´ cada pagina ´ Ademas tiene como entrada un campo de 64 bits para almacenar el valor de dicho contador. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

38 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas IX ´ Algoritmo de reemplazo de pagina menos utilizada recientemente II ´ de cada referencia a memoria el valor de C se almacena Despues ´ en la entrada de la pagina referenciada. ´ ´ bajo es la menos utilizada La pagina con el contador mas recientemente. ´ tambien ´ en hardware, ser´ıa utilizar una Otra implementacion, ˜ nxn considerando que hay n marcos de pagina. ´ matriz de tamano ´ ´ i Cada que se utiliza la pagina i todas las columnas del renglon se activan y todas las filas de la columna i se pagan. ´ ¿Cuales son las ventajas y desventajas de ambas implementaciones? ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

39 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas X ´ de LRU en software I Simulacion Se pueden realizar dos implementaciones. ´ consiste en asociar un contador a La primera implementacion ´ ´ de cada pagina e ir sumando el valor del bit R cada interrupcion reloj. ´ ´ Cuando ocurre un fallo de pagina se elige la pagina con el ´ bajo. contador mas ´ El problema de este metodo es que no necesariamente se ´ consideran las paginas menos utilizadas recientemente para su ´ liberacion. ´ ¿Por que´ puede ocurrir esta situacion?

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

40 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XI ´ de LRU en software II Simulacion ´ tambien ´ consiste en utilizar una La segunda implementacion ´ variable de pagina pero con un comportamiento diferente. ´ ahora cada interrupcion ´ de reloj Con la segunda implementacion se realiza un corrimiento a la derecha de cada variable de cada ´ marco de pagina. El bit R se suma en la parte alta de la variable en lugar de en la baja. ´ Cuando ocurre el fallo de pagina se libera la que tiene el menor valor en su variable. Las implementaciones suelen utilizar 8 bits si el tic de reloj ocurre cada 20 milisegundos. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

41 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XII ´ Algoritmo de reemplazo de paginas de conjunto de trabajo I ´ ´ Con este metodo todos los procesos comienzan sin tener paginas en la memoria. ´ ejecutada provoca un fallo de pagina ´ La primera instruccion y ´ paginas ´ segun a memoria. ´ se requiere el proceso trae sus demas ´ se le conoce como paginacion ´ por A esta estrategia tambien demanda. ´ Pocas veces los procesos referenc´ıan a todas sus paginas ´ esto por el principio de localidad. durante su tiempo de ejecucion, ´ El conjunto de paginas que un proceso utiliza en un momento dado se conoce como conjunto de trabajo. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

42 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XIII ´ Algoritmo de reemplazo de paginas de conjunto de trabajo II Si el proceso no logra tener en memoria a todo su conjunto de ´ trabajo provocara´ demasiados fallos de pagina, lo que se conoce ´ como hiperpaginacion. ´ sera´ el conjunto de trabajo de un Si se logra determinar cual ´ ´ proceso entonces se puede utilizar la tecnica de prepaginacion. ´ ´ se suele utilizar un Para implementar la tecnica de prepaginacion valor por defecto k y cada vez que se carga un proceso debieron ´ recientes a la memoria. haberse precargado las k referencias mas ´ las paginas ´ Otro criterio es considerar solo empleadas durante los ´ ultimos X milisegundos de ejecucion. ´

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

43 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XIV ´ Algoritmo de reemplazo de paginas de conjunto de trabajo III ´ Sin embargo, la idea es desalojar paginas que no pertenecen al conjunto de trabajo actual. Para esto es necesario introducir dos conceptos: Tiempo virtual. Es el tiempo de procesador utilizado por un ´ proceso desde que inicio´ su ejecucion. Tiempo real. Es el tiempo total que lleva un proceso desde el inicio ´ de su ejecucion.

´ Se fija un parametro τ que considerara´ dentro del conjunto de ´ trabajo actual a todas aquellas paginas referenciadas en los ultimos τ segundos del tiempo virtual. ´ ´ sobre desalojar una pagina ´ La decision al ocurrir un fallo se decide en base a τ . ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

44 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XV ´ Algoritmo de reemplazo de paginas WSClock I ´ del algoritmo de conjunto de trabajo con el Es una combinacion algoritmo de reloj. Se utiliza una lista en forma de anillo inicialmente vac´ıa. ´ se necesitan considerar el bit R y el tiempo virtual de Ademas ´ vida de la pagina. ´ ˜ Cada que se necesita una pagina se anade a la lista. La lista tendra´ un l´ımite tan grande como el numero de marcos ´ existentes.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

45 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XVI ´ Algoritmo de reemplazo de paginas WSClock II Cuando ocurre un fallo primero se recorre la lista buscando los marcos con el bit R = 0. ´ Si el bit es cero, entonces se checa su edad τ y si el valor es mas ´ grande que τ entonces la pagina se calendariza para copiarse a disco (si es que es requerido) o simplemente se libera. ´ ´ se podr´ıa considerar Para reducir el trafico a disco solo ´ calendarizar hasta n paginas. ¿Que ocurre si la manecilla da toda la vuelta y regresa a su punto de partida? 1 2

Se pudo haber calendarizado al menos una escritura. Pudieron no calendarizarse escrituras.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

46 / 56

´ Algoritmos para el reemplazo de paginas

´ Algoritmos para el reemplazo de paginas XVII ´ Algoritmo de reemplazo de paginas WSClock III En el primer caso la manecilla sigue avanzando hasta que una de ´ las paginas calendarizadas quede limpia. ´ La primera pagina encontrada sera´ reemplazada por la que se requiere. ´ En el segundo caso quiere decir que todas las paginas caen en el conjunto de trabajo. ´ sencillo sera´ desalojar cualquier pagina ´ Lo mas limpia (con bit M = 0). ´ Si ninguna pagina esta´ limpia, entonces se debe calendarizar una ´ (cualquiera) para escribirse a disco y luego se desalojara.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

47 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion I

´ ¿Cuando ocurre la paginacion? Cuando se crea un proceso. Cuando se ejecuta un proceso. ´ Cuando se presenta un fallo de pagina. Cuando termina un proceso.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

48 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion II Cuando se crea un proceso ˜ tendra´ al principio el El SO operativo debe determinar que tamano programa y los datos. ´ Se crea una tabla de paginas para el programa y datos. ´ La tabla de paginas no debe estar residente mientras el proceso esta en estado listo pero s´ı cuando se esta´ ejecutando el proceso. ´ se le debe asignar algun Ademas ´ espacio en disco para que en ´ ´ los intercambios de paginas estas tengan a donde ir. ´ acerca Por ultimo se registra en la tabla de procesos informacion ´ ´ ´ de la tabla de paginas y del area de intercambio en disco.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

49 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion III

Cuando se ejecuta un proceso Se debe preparar la MMU para el nuevo proceso. ´ Se debe actualizar la tabla de paginas del nuevo proceso. Puede que antes de comenzar a ejecutar el proceso sean tra´ıdas ´ todas sus paginas a memoria.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

50 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion IV ´ Cuando se presenta un fallo de pagina ´ El SO debe de leer los registros a fin de determinar la direccion ´ ´ que causo el fallo de pagina. ´ el SO debe determinar cual ´ es la pagina ´ Con esa informacion que se requiere traer de disco. ´ sobre la pagina ´ El SO toma una decision a desalojar y trae la nueva a memoria. Finalmente el SO retrocede el PC para que apunte a la ´ que causo´ el fallo. instruccion

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

51 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion V Cuando termina un proceso ´ ´ El SO debe liberar la tabla de paginas, las paginas y el espacio en disco ocupado por el proceso. ´ ´ Si las mismas paginas son utilizadas por otros procesos, estas ´ podran ´ ser liberadas cuando el ultimo solo proceso termine de ´ utilizarlas. ´ Otro aspecto importante es como se lleva a cabo el manejo de ´ fallos de pagina. Independientemente del algoritmo implementado para escoger la ´ pagina a liberar de la memoria, el proceso que ocurre durante un ´ fallo de pagina es el mismo. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

52 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion VI 1

El hardware salta al kernel y almacena el PC en la pila.

2

Se ejecuta una rutina en lenguaje ensamblador que guarda los registros importantes y dicha rutina manda llamar al SO.

3

´ ´ es El SO se da cuenta que hay un fallo de pagina y averigua cual ´ la pagina que necesita. Esto puede ser con ayuda de uno de los registros almacenados en hardware o bien el SO debe recuperar el PC del programa y ´ es la pagina ´ trata de deducir cual necesaria.

4

´ requerida es valida ´ Si la direccion entonces el SO busca un ´ marco libre o bien ejecuta el algoritmo de reemplazo de paginas, de lo contrario el SO mata el proceso.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

53 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion VII 5

Si el marco escogido esta´ modificado el SO calendariza su ´ de que cambia de contexto eligiendo escritura a disco ademas otro proceso a ejecutar (en lo que se mueve el marco a disco).

6

´ Una vez que el marco de pagina esta listo el SO calendariza una ´ de disco para traer la pagina ´ operacion que requiere. Mientras esto se realiza otro proceso puede ser calendarizado.

7

´ de disco indica que llego la pagina ´ Cuando la interrupcion ´ entonces se actualiza la tabla de paginas.

8

´ que causo´ el fallo se regresa a su estado inicial. La instruccion

9

El proceso que causo´ el fallo se calendariza.

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

54 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion VIII

10

El SO regresa a la rutina de lenguaje ensamblador que lo invoco.

11

´ informacion ´ de Esta rutina vuelve a cargar los registros y demas ´ del proceso original. estado para continuar con la ejecucion

´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

55 / 56

´ y fallos de pagina ´ Aspectos de paginacion

´ y fallos de pagina ´ Aspectos de paginacion IX ´ ¿Como funciona el retroceso de instrucciones? ´ el SO debe determinar donde ´ Para reiniciar una instruccion ´ esta´ el primer byte de la instruccion. ´ que hace 2 referencias a memoria contempla 3 Ej. una instruccion direcciones diferentes donde podr´ıa haber ocurrido el fallo. ´ ´ donde ocurrio´ el fallo De este modo el SO no sabra´ si la direccion ´ de memoria asociada a este. ´ es un cod. de oper. o una direccion ´ hardware es un registro interno oculto que ofrecen Una solucion ´ algunas maquinas donde copian el valor del PC antes de que se ´ ejecuta cada instruccion. Sin dicho dato el SO se las debe arreglar para resolver el problema. ´ Sergio Luis Perez (UAM C UAJIMALPA)

Curso de Sistemas Operativos

56 / 56