Sistemas Operativos I - Tema 4

Gestión de la memoria |1

4. GESTIÓN DE LA MEMORIA Si se pretende que los procesos estén preparados para su ejecución es necesario cargarlos en la memoria principal, ya que ningún proceso se puede activar antes de que se le asigne el espacio de memoria que requiere. La utilización de los recursos del sistema, y en general, del rendimiento del sistema va a estar condicionado por la eficacia en la gestión de la memoria. Uno de los factores más importantes es la organización y gestión de la memoria principal. El ciclo típico de ejecución de una instrucción incluye las acciones siguientes: · Búsqueda de la instrucción en la memoria · Decodificación de la instrucción · Posible búsqueda de operandos en la memoria · Almacenamiento del resultado de la operación realizada

4.1 Sistemas elementales de gestión de la memoria El esquema de gestión más simple que se puede considerar es aquel que no tiene ningún gestor. El usuario tiene un control completo sobre el espacio total de memoria. Ventajas: 1) Máxima flexibilidad para el usuario 2) Máxima simplicidad y coste mínimo 3) No es necesario disponer de un computador específico ni tan siquiera del SO Este sistema tiene sus limitaciones, ya que no da ningún servicio. El usuario tiene acceso a todos los recursos del computador, pero el SO no tiene control sobre las interrupciones, no hay un monitor residente para procesar las llamadas al sistema o para el tratamiento de errores. El siguiente esquema se obtiene al dividir la memoria en dos secciones: una para el proceso del usuario y otra para la parte del sistema operativo que debe de estar residente en memoria (monitor). En el MS-DOS para el PC de IBM, la memoria está dividida en tres zonas: la parte inferior, que está destinada al SO; la parte central, dedicada al único programa de usuario y la parte superior, en ROM, para los controladores de dispositivos (más conocido como BIOS). A partir de ahí se ha utilizado la multiprogramación, por varias razones: 1) Facilitar la programación de una aplicación al dividirla en varios procesos 2) Poder dar servicio interactivo a varios usuarios al mismo tiempo u optimizar el tiempo del procesador cuando un proceso está a la espera de una operación de E/S.

4.2 Gestión de la memoria con particiones fijas El tamaño de las particiones se puede fijar o bien con anterioridad a la ejecución de los programas de usuario o efectuarse dinámicamente en la fase de ejecución. La asignación de memoria con particiones fijas se denominó MFT (Multiprograming with a Fixed number of Tasks). La división de ésta se ha realizado con anterioridad a la ejecución de los programas de usuario, pudiendo hacerla el operador o administrador del sistema de forma manual, al iniciar una sesión con la máquina. El número y tamaño de las particiones se determinan teniendo en cuenta: 1) Capacidad de la memoria física disponible y el grado de multiprogramación (nº máximo de procesos activos en el sistema) 2) Tamaños típicos de los procesos ejecutados más frecuentemente

Gestión de la memoria |2 4.2.1 Principio de operación a) Cuando llega una tarea, ésta se pone en una cola de tareas b) El planificador de tareas tiene en cuenta los requerimientos de memoria de cada una de ellas y las particiones de memoria disponible c) Si una tarea tiene espacio disponible en memoria, se ubica en una partición, y puede competir por el uso de la CPU d) Cuando se termina una tarea, se libera la partición de memoria que ocupa, pudiendo el planificador de tareas asignar esta partición a otra tarea de la cola de tareas Hay diferentes tipos de organizaciones posibles para la asignación de memoria a las tareas, por ejemplo, clasificarlas todas según sus requerimientos de espacio. Así cada partición tendrá una cola de tareas y cada tarea se incluye en la cola de partición de memoria que mejor se adapta. La planificación de cada cola se hace por separado y, como cada cola tiene su propia partición, no hay competencia entre las colas por la memoria. Otro tipo de organización consiste en mantener todas las tareas en una sola cola. El planificador selecciona la próxima tarea para ser ejecutada y espera hasta que se disponga de una región de memoria del tamaño requerido.

4.2.2 Intercambio Otro esquema en el uso de la memoria. Hace referencia a las operaciones de eliminar de la memoria principal procesos suspendidos, llevarlos al disco y cargar del disco a la memoria principal procesos para su ejecución. Responsabilidades del intercambiador: - Selección de los procesos que hay que eliminar de la memoria principal - Selección de los procesos que hay que cargar en la memoria principal - Asignación y gestión del espacio de intercambio La selección de los procesos en la memoria principal que hay que intercambiar se hace entre aquellos que ocupan particiones suficientemente grandes para los procesos que se les debe asignar espacio en memoria, considerando: a) Prioridad. Son más aptos aquellos con baja prioridad. b) Estado de espera. Procesos que esperan sucesos lentos tienen mayor probabilidad de ser suspendidos durante un tiempo suficientemente grande. c) Tiempo de permanencia en memoria. Y si se ha ejecutado mientras ha estado en memoria. La elección de los procesos que hay sin cargar en la memoria se basan en: 1) Tiempo que ha permanecido en memoria secundaria 2) Prioridad 3) Satisfacción del tiempo mínimo de residencia en disco desde la descarga

4.2.3Archivo de intercambio Un proceso se prepara para su ejecución y se envía al SO en la forma de un archivo que contiene un programa en versión ejecutable y sus correspondientes datos. Este archivo puede contener atributos del proceso. Un proceso ejecutado parcialmente tiene una imagen en tiempo de ejecución diferente de la inicial almacenada en el disco. En general, la parte modificable del estado del proceso consiste en los contenidos de sus datos y posiciones de la pila, así como de los registros del procesador. El contenido de una porción considerable (o el espacio de direcciones entero) se debe copiar a disco durante el intercambio. Como la imagen del proceso estático se utiliza para la activación inicial, la imagen modificada en tiempo de ejecución no debe sobrescribir a la imagen del proceso estático sobre el disco. Hay dos opciones básicas para diseñar el archivo de intercambio: 1) Un único archivo de intercambio para el sistema completo 2) Diferentes archivos de intercambio dedicados a cada uno de los procesos

Gestión de la memoria |3 El espacio de intercambio para cada proceso susceptible de poderse transferir está generalmente reservado, y asignado estáticamente en el momento de creación del proceso. Para un único archivo de intercambio, se crea un solo archivo, generalmente en el curso de la inicialización del sistema, para tratar los requerimientos de intercambio de todos los procesos. El archivo se suele situar en un disco rápido (para reducir tiempos de intercambio). El tamaño del archivo de intercambio afecta al número de procesos que están activos en el sistema. Un proceso se activa si se le puede reservar suficiente espacio de intercambio. Los fallos que se producen al reservar el espacio de intercambio en el tiempo de creación del proceso pueden llevar a graves errores en tiempo de ejecución. La alternativa es tener archivos de intercambio dedicados a cada uno de los procesos intercambiables del sistema. Pueden ser creados dinámicamente en el tiempo de generación del proceso o estáticamente en el tiempo de preparación del programa. Ventajas: se elimina el problema de dimensionamiento del archivo de intercambio y los errores de sobrepasar la capacidad, no se impone restricción sobre el número de procesos activos. Desventajas: necesidad de más espacio de disco para intercambio, acceso más lento y direccionamiento más complicado. Los algoritmos para la gestión del espacio disponible en el archivo de intercambio son los mismos que los usados para la gestión de la memoria principal.

4.2.4 Reubicación y protección Al mantener diversas tareas activas aparecen dos problemas: la reubicación y la protección. Reubicable: Posibilidad de cargar y ejecutar un programa dado en un lugar arbitrario de memoria. La solución al problema de la reubicación pasa por considerar dos tipos de reubicaciones: a) Reubicación estática: Implica que ésta se realiza antes o durante la carga del programa en memoria, mediante un enlazador o cargador reubicable. b) Reubicación dinámica: Implica que la asignación del espacio de direcciones virtuales al espacio de direcciones físicas se realiza en tiempo de ejecución, con ayuda de dispositivos físicos específicos destinados a tal fin. Cuando el proceso se está ejecutando, todas sus referencias a direcciones de memoria se recalculan durante la ejecución de la instrucción antes de acceder a la memoria física. Esto se realiza mediante registros base especializados. Ventaja: Un programa se puede trasladar de una partición de memoria a otra mientras se encuentra en ejecución. En ambos esquemas queda por resolver el problema de la protección, ya que un programa de forma mal intencionada, puede construir una dirección física que se salga fuera de la partición asignada. Una solución es considerar un registro límite que se cargaría con la longitud de la partición. Otro esquema de protección hardware es considerar registros bordes para cada partición, los cuales se cargan con las direcciones físicas de comienzo y final de la partición.

4.2.5 Selección del tamaño de la partición: fragmentación de la memoria La decisión inicial generalmente se basa en una suposición razonable de los requerimientos de los programas de entrada. Cuando el sistema está operando, se puede considerar la información sobre el número y tamaño de las tareas que se están ejecutando, para optimizar el tamaño de las particiones. La mayor dificultad con las particiones fijas es encontrar un buen compromiso entre los tamaños de las particiones y la memoria requerida por los trabajos.

Gestión de la memoria |4 Hay dos tipos de desaprovechamiento de la memoria: 1) Fragmentación interna. Parte de la memoria que no se está usando pero que es interna a una partición y no se puede aprovechar. 2) Fragmentación externa. Cuando una partición disponible no se emplea porque es muy pequeña para cualquiera de las tareas que esperan. La selección de los tamaños de las particiones es un compromiso entre estos dos casos de fragmentación.

4.3 Gestión de la memoria con particiones variables 4.3.1 Principio de operación El SO mantiene una tabla que indica qué partes de la memoria están disponibles y cuales están ocupadas. Cuando llega una tarea que requiere memoria, se busca un bloque disponible suficientemente grande. Si se encuentra, se asigna sólo la cantidad que se necesita. En general, en cualquier instante de tiempo hay libres un conjunto de bloques de memoria, de varios tamaños, repartidos a lo largo de la memoria. Mientras se puedan mover todos los procesos hacia la parte superior es posible combinar todos los bloques libres en uno solo. Esta técnica se conoce como compactación de la memoria. Generalmente no se realiza porque consume mucho tiempo de CPU. Un punto importante, es la cantidad de memoria que se le asigna a un proceso recién creado o intercambiado. Si los procesos se crean con un tamaño fijo invariante, se les asigna exactamente la memoria que necesitan. El problema aparece cuando los segmentos de datos de algunos procesos pueden crecer. Si hay una partición libre adyacente al proceso, ésta se le puede asignar. Pero si el proceso que crece es adyacente a otro proceso, debe ser desplazado a una partición libre lo suficientemente grande, o se tendrán que intercambiar uno o más procesos para crear una partición libre adyacente.

4.3.2 Sistemas de registro del uso de la memoria El registro de las particiones libres y ocupadas debe ser eficiente, tanto en tiempo para la asignación, como en aprovechamiento de la memoria. Hay varias formas: Mapa de bits. La memoria se divide en unidades de asignación. A cada unidad le corresponde un bit en el mapa de bits (0=libre y 1=ocupado). Ventaja: Ocupa poco espacio en memoria. Inconveniente: Sistema de gestión de memoria lento. Listas enlazadas. De las particiones libres y asignadas. Cada proceso tiene dos vecinos: dos procesos, un proceso y una partición libre y dos particiones libres. En este caso las estrategias más comunes para la asignación de memoria son: 1) Primero en ajustarse: estrategia más simple y rápida. El bloque encontrado se divide en dos partes, una se asigna al proceso y la otra se introduce en la lista como libre. Se produce fragmentación externa. 2) Mejor en ajustarse: busca en toda la lista y asigna el bloque más pequeño que es suficientemente grande. Produce restos más pequeños y es más lento. Produce mayor desperdicio de memoria que los otros dos algoritmos. 3) Peor en ajustarse: Suprime el efecto de particiones muy pequeñas. Produce restos más grandes, pero se ha demostrado que no tiene mejor rendimiento que los otros dos algoritmos. 4) Sistema de los asociados: Aprovecha el hecho de trabajar con direcciones binarias para hacer más rápida la fusión entre particiones libres adyacentes. El bloque de

Gestión de la memoria |5 memoria se va dividiendo en mitades según el requerimiento de los procesos. Un procedimiento ocupa la potencia de 2 (128Kb, 256Kb…) que está más cerca del redondeo de la memoria que necesita el proceso. Las fusiones se producen entre los bloques adyacentes previamente divididos cuando están libres.

4.4 Paginación Uno de los principales inconvenientes de los anteriores sistemas de gestión es la fragmentación externa. Este problema tiene dos soluciones generales: 1) Compactación de memoria. No se suele usar por su coste en tiempo. 2) Paginación. Permite que la memoria de un programa no sea contigua, de forma que siempre que se disponga de espacio, aunque éste no sea adyacente, se pueda asignar a un programa.

4.4.1 Principio de operación La memoria se divide conceptualmente en un número de bloques de tamaños fijos, los marcos de página. El espacio de direcciones virtuales de un proceso también se divide en bloques de tamaño fijo, páginas, del mismo tamaño que los marcos de página. La asignación de memoria consiste en encontrar un número suficiente de marcos de página sin usar para cargar las páginas de los procesos solicitadas. La dirección lógica se descompone en dos campos: el número de página y el desplazamiento relativo dentro de esta página.

4.4.2 Implementación de las tablas de páginas El objetivo de las tablas de páginas es asociar a las páginas un marco de página. Plantean dos cuestiones importantes: 1) El tamaño de la tabla de páginas, que puede ser demasiado grande. 2) El tiempo de asignación, que debe ser rápido. El acceso y búsqueda en estas tablas tiene que ser lo suficiente rápido para no ser un cuello de botella en funcionamiento del computador. La realización más sencilla es tener una sola tabla de páginas estructurada como un conjunto de registros dedicados. La CPU cargará estos registros cada vez que cargue los otros registros del programa. Es un método directo, sólo usa una referencia a memoria durante la asociación. Su desventaja es el coste de la circuitería asociada cuando las tablas de páginas son grandes. La utilización de registros específicos para la tabla de páginas es adecuada si la tabla de páginas es razonablemente pequeña. En sistemas con tablas de páginas grandes el sistema no es rentable. Se requiere más de una referencia a memoria para leer las entradas de la tabla de páginas durante la ejecución de cada instrucción. La solución es disponer de un pequeño dispositivo especial, la memoria asociativa. La mayoría de los programas tienden a hacer un gran número de referencias a un número pequeño de páginas y no al revés. Cada entrada tiene: 1) Número de página 2) Marco físico donde se localiza la página 3) Código de protección 4) Bit de modificación Se suele añadir un bit más que indica si la entrada se está utilizando o no. Cuando se presenta una dirección lógica, se verifica que el número de página lógica se encuentra en la memoria asociativa. Si el acceso no viola los bits de protección, el marco de

Gestión de la memoria |6 página se toma directamente de la memoria asociativa, si se viola la protección se genera un fallo de página. El porcentaje de veces que un número de página se encuentra en memoria asociativa (razón de encuentros) está relacionado con el número de registros de la memoria asociativa. Con una memoria de 16 registros se puede tener una razón de encuentros del 80% o 90%. Hay que tener en cuenta si el sistema es multiprogramado. Cada proceso tiene su propia tabla de páginas y es necesario dar mecanismos para que al ejecutarse un nuevo proceso no utilice los marcos de página de otro proceso. Dos soluciones: a) Proporcionar una instrucción máquina que invalide la memoria asociativa b) Realiza la memoria asociativa con un campo id_proceso

4.4.3 Compartición de páginas y protección Una de las ventajas de la paginación es la posibilidad de compartir código. Para ser compartible, el código debe ser reentrante (no automodificable, no cambia nunca durante la ejecución). Dos o más procesos pueden ejecutar el mismo código a la vez, manteniendo copia de sus registros y de sus datos, ya que estos varían de un proceso a otro. La protección de la memoria se realiza mediante bits de protección asociados a cada una de las páginas. Estos bits se encuentran en la tabla de página y definen la página como de lectura/escritura o de sólo lectura.

4.5 Segmentación El usuario prefiere ver a la memoria como un conjunto de diferentes tamaños, sin una ordenación específica entre ellos. Segmentación: Sistema de gestión de la memoria que soporta esta visión. El espacio de direcciones lógicas es un conjunto de segmentos, con diferentes nombres y tamaños. Las direcciones especifican el nombre del segmento y el desplazamiento dentro del segmento. Este esquema es muy diferente al de la paginación. Un segmento puede tener una determinada estructura de datos, o un procedimiento o módulo, pero normalmente no va a contener una mezcla de varios.

4.5.1 Principio de operación El programa de usuario se compila y el compilador construye automáticamente los segmentos de acuerdo a la estructura del programa. El cargador tomará todos estos segmentos y le asignará números de segmento. Cada uno de los segmentos se compila comenzando por su propia dirección lógica 0. Es necesario disponer de un mecanismo que convierta las direcciones lógicas bidimensionales en su dirección física equivalente. Esta asignación se efectúa mediante una tabla de segmentos. En la tabla se mantienen registrados los descriptores de cada segmento: la base, correspondiente a la dirección física en que comienza el segmento y el tamaño del mismo. El número de segmento se emplea como un índice dentro de la tabla de segmentos. La dirección física se obtiene añadiendo el desplazamiento a la base del segmento. El desplazamiento no debe sobrepasar el tamaño máximo del segmento.

Gestión de la memoria |7

Una tabla de segmentos que se mantiene en registros especiales puede ser referenciada muy rápidamente; la suma a la base y la comparación con el tamaño se puede hacer simultáneamente. Cuando el número de segmentos crece, la tabla de segmentos se deja en memoria; un registro base de la tabla de segmentos apunta a la tabla de segmentos. Modo de proceder: 1) Se comprueba que el número de segmento es correcto 2) Se suma el número de segmento al valor del registro base de la tabla de segmentos para obtener la dirección de memoria para la entrada de la tabla de segmentos 3) Esta entrada se lee de memoria y se procede como antes (se comprueba que el desplazamiento no rebasa la longitud del segmento y se calcula la dirección física). Esto requiere dos referencias a memoria por dirección lógica, provocando una disminución en la velocidad del computador. Solución: disponer también de una memoria asociativa para retener las entradas de la tabla de segmentos usadas más recientemente. La segmentación no produce fragmentación interna, pero sí externa, cuando todos los bloques de memoria libres son muy pequeños para acomodar un segmento.

4.5.2 Protección y compartición Como todas las entradas al segmento se usan de la misma manera, los segmentos de código se pueden definir de sólo lectura, mientras que un segmento de datos se puede definir de lectura/escritura. También facilita la compartición de código o datos entre varios procesos. Ejemplo: las librerías compartidas.

4.5.3 Sistemas combinados de paginación-segmentación Características: a) El programador no necesita saber que se está utilizando la paginación; pero si se dispone de segmentación sí necesita saberlo. b) La paginación sigue un sistema lineal, la segmentación proporciona un espacio bidimensional con muchos espacios de direcciones. c) La paginación no distingue el código de los datos. La segmentación sí. d) La segmentación facilita la compartición de código y datos, así como el uso de estructuras de datos de tamaños fluctuantes. e) El espacio total de direcciones de ambas puede exceder el tamaño de la memoria física. Esto permite desarrollar el concepto de memoria virtual. No se puede decir que una técnica sea mejor a la otra, por ello hay muchos sistemas que combinan los dos métodos. Una técnica muy extendida consiste en usar la segmentación desde el punto de vista usuario, pero dividiendo cada segmento en páginas de tamaño fijo. Es adecuada en el caso de que los

Gestión de la memoria |8 segmentos sean muy grandes. Así se elimina la fragmentación externa y hace más fácil el problema de la ubicación.

Cada segmento tiene su propia tabla de páginas. El tamaño de la tabla de páginas no tiene que ser el máximo, sino un tamaño en función de la longitud del segmento. Se ha eliminado la fragmentación externa, pero introduciendo fragmentación interna y aumentando el espacio de tablas.

4.6 Memoria virtual Memoria virtual: Permite que el espacio de direcciones virtuales de un proceso activo sea mayor que la memoria física disponible.

4.6.1 Principio de operación Demanda de página: sistemas más comunes. Similar a un sistema de paginación con intercambio. Los procesos se inician sin ninguna página en memoria; cuando se intenta ejecutar la primera instrucción se produce un fallo de página que provocará que el SO tenga que cargar en la memoria principal la página que contiene esta instrucción. Un fallo de página se produce cuando en la tabla de páginas del proceso no hay asociado un marco de página a la página a la que se quiere acceder. Cuando se produce un fallo: 1) Se verifica si la dirección es válida. 2) Si es una referencia válida, pero no se ha traído la página a la memoria principal, el SO detecta un fallo de página y determina la página virtual requerida para traerla. La instrucción queda interrumpida y se guarda el estado. 3) Se selecciona un marco libre. Si no existe uno, se tendría que ejecutar un algoritmo de sustitución de página. 4) Si el marco de página está ocupado, el planificador transfiere la página al disco y se produce un cambio de contexto; se suspende el proceso causante del fallo y se permite la ejecución de otro. El marco queda marcado como ocupado. 5) Cuando el marco queda limpio, el SO examina la dirección en el disco donde se encuentra la página necesaria y planifica una operación de lectura de la misma. Mientras se carga la página, el proceso que produjo el fallo continúa suspendido y se permite ejecutar otro proceso. 6) Cuando se completa la lectura del disco, la tabla de páginas se actualiza para indicar que ya se dispone de la página en la memoria.

Gestión de la memoria |9 7) La instrucción que produjo el fallo regresa al estado de comienzo y se planifica su ejecución. La circuitería para soportar demanda de página es la misma que para la paginación e intercambio. También se tiene que imponer algunas restricciones sobre la arquitectura, siendo esencial la posibilidad de continuar cualquier instrucción después de un fallo de página.

4.6.2 Conceptos de memoria virtual Una gestión de la memoria basada en el mecanismo de demanda de página tiene un considerable efecto sobre el rendimiento del computador. La probabilidad de que ocurra un fallo de página debe de ser menor al 0,001%, evidentemente, hay que mantener la razón de fallos de página muy baja para que la ejecución de un programa no se haga extremadamente lenta. Muchos procesos no usan todas sus páginas (páginas de dato o código que no se usan, de tratamiento de errores…), por tanto no hay que traerlas todas, pudiéndose ejecutar más procesos. En esta situación puede ocurrir el efecto de la sobreasignación de la memoria. Se necesita un sistema de sustitución de páginas que permita mantener un alto nivel de multiprogramación. El SO debe elegir una página para retirarla de memoria y dejar espacio para la página que se solicita. La memoria virtual mediante paginación supone mantener una tabla de páginas por cada uno de los procesos activos. Estas tablas pueden ser mucho más grandes en un sistema virtual que en uno de paginación real, ya que el espacio de direcciones virtuales de un proceso puede exceder la capacidad de la memoria real. Se deben tener políticas de: a) Asignación de memoria real a cada uno de los procesos activos. b) Búsqueda y lectura del disco de los correspondientes elementos. c) Sustitución de elementos en memoria principal por los nuevos elementos que se traen del disco. d) Ubicación de los nuevos elementos.

4.7 Políticas de sustitución de páginas 4.7.1 Algoritmo de sustitución FIFO: First In, First Out A cada página se le asocia el tiempo que ha permanecido en la memoria y al sustituir una página, se elige la que más tiempo lleva en la memoria. No es necesario guardar el tiempo de entrada, ya que se puede crear una cola con todas las páginas de memoria que van entrando. Su funcionamiento no es siempre el adecuado y no es el que se suele usar. A pesar de que una página se usa muy frecuentemente, según este algoritmo se seleccionaría para ser sustituida, aunque se acabara de usar. Sufre la “anomalía de Belady” (aumentan los fallos de páginas al aumentar el número de marcos de páginas para asignación).

4.7.2 Algoritmo de sustitución óptimo Tiene que producir menos fallos de páginas que cualquier otro algoritmo. Además, no debe de presentar la anomalía de Belady.

G e s t i ó n d e l a m e m o r i a | 10 El algoritmo óptimo se puede enunciar así: “Sustituir aquella página que tardará más en volverse a utilizar”. El problema de este algoritmo es que es irrealizable, ya que el SO no sabe a priori que páginas se referenciarán en el futuro. Sirve como medida para los demás algoritmos.

4.7.3 Algoritmo de sustitución LRU: Least Recently Used Es una buena aproximación al algoritmo óptimo. Se considera que las páginas usadas más frecuentemente en las últimas instrucciones son las que con más probabilidad se usarán próximamente. Este algoritmo asocia a cada página el tiempo de la última vez que se utilizó. Cuando una página debe ser sustituida, se elige aquella que no ha sido utilizada durante un mayor periodo de tiempo. Necesita un considerable apoyo de recursos de la máquina. Hay dos posibles realizaciones: 1) Mediante una pila que mantiene los números de página. Cada vez que una página se referencia, su número se elimina de la pila y se coloca en la cumbre. La eliminación de una página y su colocación en la cumbre supone tener que modificar un número x de punteros, lo que puede consumir mucho tiempo. 2) Mediante registros contadores. En la CPU hay un contador que se incrementa cada vez que se hace una referencia a la memoria. Cada vez que se hace referencia a una página, se copia el contador en el registro con el tiempo en el que se usó la página. Cuando hay que hacer una sustitución se busca el registro con el valor más pequeño. Los dos métodos necesitan de una circuitería especial de la que no siempre se dispone. Así, muchos sistemas proporcionan un bit de referencia por cada una de las páginas. El SO pone a 0 estos bits y, cuando se referencia una página, el bit se pone a 1. Se sabe qué páginas se han referenciado, pero no el orden en el que se ha hecho. Se puede tener más información registrando regularmente estos bits (por ejemplo, una tabla con registros de ocho bits por cada página). Periódicamente el SO desplazará a la derecha los bits de estor registros y situará en el bit de orden superior el bit de referencia. En el caso extremo se puede mantener sólo el bit de referencia, sin ningún bit de historia. Esto da lugar al algoritmo de la segunda oportunidad.

4.7.4 Algoritmo de sustitución de la segunda oportunidad Es una modificación del algoritmo FIFO. La modificación consiste en examinar el bit de referencia de las páginas que se seleccionan para sustituir. Si es 0, la página no se ha utilizado además de ser antigua. Si es 1, entonces se pone a 0 y la página se coloca al final de la cola. La segunda oportunidad busca una página antigua que NO se haya referenciado.

4.7.5 Otros algoritmos de sustitución A muchos de ellos se les puede considerar aproximaciones del LRU. Si además del bit de referencia se considera un bit de modificación, que se activa cuando se escribe una palabra en la página. El SO asigna un valor 0 a los dos bits, de forma periódica, el bit de referencia se pone a 0 para distinguir las páginas que no tienen referencias recientes de las que sí. Cuando hay un fallo de página, el SO se encontrará cuatro categorías de páginas, según los bits: 0= (0,0) no ha sido referenciada ni modificada 1= (0,1) no ha sido referenciada, pero sí modificada 2= (1,0) ha sido referenciada, pero no modificada 3= (1,1) ha sido referenciada y modificada El algoritmo sustituye una página de la clase más baja que no esté vacía.

G e s t i ó n d e l a m e m o r i a | 11

Se puede construir el algoritmo LRU mediante un programa. Se conoce como el algoritmo de uso no frecuente (NFU). Necesita una variable tipo contador asociada a cada página, con valor inicial 0. Cuando ocurre un fallo de página, se elige la página con el valor mínimo del contador. El problema es que este algoritmo no olvida, así que páginas que fueron utilizadas con mucha frecuencia hace tiempo, mantienen el valor del contador alto y no son sustituidas. Hay una clase de algoritmos que nunca presentan la anomalía de Belady, los algoritmos de pila. Es un algoritmo para el que se puede demostrar que el conjunto de páginas en memoria para n marcos es un subconjunto del conjunto de páginas que se tendrían con n+1 marcos.

4.8 Políticas de asignación Las políticas de asignación intentar ser un compromiso entre distintos requerimientos conflictivos. El número mínimo de marcos por proceso viene fijado por la propia arquitectura del computador, mientras que el número máximo es definido por la cantidad de memoria física disponible. La elección del número de marcos para cada proceso se hará entre estos dos límites. Para sistemas con capacidad de multiproceso, la sustitución de páginas se pueden clasificar en dos categorías: local y global. Las globales permiten que para un proceso se seleccione un marco para sustitución del conjunto de todos los marcos. En las locales para cada proceso se seleccionan sólo marcos asignados a él. Con políticas de sustituciones locales, el número de marcos de un proceso no cambia, mientras que con sustituciones globales puede ocurrir que un proceso seleccione sólo marcos asignados a otros procesos. El problema para la sustitución global es que los programas no pueden controlar su propia razón de fallos de páginas, depende también de los fallos de páginas de los demás procesos. En cambio, para políticas locales, el conjunto de páginas de un proceso depende sólo del comportamiento del mismo.

4.8.1 El modelo del conjunto de trabajo Al aumentar el grado de multiprogramación se podría esperar que la utilización del procesador también aumentase. Generalmente éste es el caso mientras el grado de multiprogramación se mantenga por debajo de un cierto nivel, que depende del tamaño de la memoria disponible. Si el grado de multiprogramación excede ese límite, entonces se provoca un marcado aumento en el intercambio de páginas entre la memoria principal y el disco, acompañado por una inesperada disminución en la utilización del procesador. La explicación es que con el alto de multiprogramación es imposible que todos los procesos mantengan suficientes páginas en memoria para que no se generen un gran número de fallos de página. Se satura el canal de transferencia con el disco, se bloquean muchos procesos esperando un intercambio de páginas y el procesador está infrautilizado. Esto se conoce como catástrofe (thrashing). La catástrofe se puede limitar mediante el empleo de algoritmos de sustitución locales, ya que si un proceso comienza un fenómeno de catástrofe, no puede coger marcos de otro proceso y extender la catástrofe a los otros procesos. Para prevenir la catástrofe se debe suministrar a los procesos tantas páginas como necesiten. El conjunto de páginas utilizadas en un determinado momento por el proceso se denomina conjunto de trabajo. Para evitar la catástrofe, el grado de multiprogramación no debe ser mayor que el que permite que los conjuntos de trabajo de todos los procesos se puedan tener simultáneamente en la memoria.

G e s t i ó n d e l a m e m o r i a | 12 El problema se reduce a determinar que páginas constituyen el conjunto de trabajo de un proceso. Para ello se hace uso del principio de localidad: “Las referencias de los programas tienden a agruparse en pequeñas zonas del espacio de direcciones, y estas localizaciones tienden a cambiar solo intermitentemente” En las políticas de sustitución y asignación se debe seguir la siguiente regla genérica: Ejecutar un proceso solamente si el conjunto de trabajo está por completo en memoria principal, y no eliminar una páginas que es parte del conjunto de trabajo de un proceso.

4.9 Aspectos de diseño para los sistemas de paginación Cuestiones que un diseñador de SO debe tener en cuenta al efectuar la gestión de la memoria.

4.9.1 Tamaño de página En general, las páginas se eligen de tamaños que son potencias de 2. Un tamaño pequeño supone un menor desperdicio de la memoria. Si las páginas son pequeñas las tablas de páginas tienen que ser grandes, y como cada proceso tiene su propia copia de la tabla de páginas sería recomendable tablas pequeñas, lo que supone páginas grandes. Otro problema es el tiempo necesario para leer y escribir una página. Este tiempo está compuesto por un periodo de latencia y por el propio tiempo de transferencia. El tiempo de transferencia depende del tamaño de la página, es proporcional a la cantidad de información transferida. Hay otros factores, como la relación entre el tamaño de página y el tamaño de los sectores del disco; pero no hay una respuesta satisfactoria global.

4.9.2 Prepaginación Cuando un proceso se arranca inicialmento o despés de haber sido suspendido, tiene que traer a memoria todas las páginas que necesita para su ejecución. Se pueden traer de una sola vez a memoria todas las páginas que se precisan (técnica de prepaginación). El problema es saber si el coste de la paginación es menor que el coste de servir fallos de páginas.

4.9.3 Frecuencia de fallos de páginas El modelo del conjunto de trabajo es útil para realizar la prepaginación, pero no es el más adecuado para manejar el control de la catástrofe. Se pueden establecer límites entre los cuales se desea mantener el porcentaje de fallos de páginas. La política a seguir será mantener el número de fallos de páginas entre estos límites. Si en algún momento existe un número elevado de procesos en memoria, que no permiten mantener la razón de fallos de páginas por debajo del límite superior, entonces se retira un proceso y se reparten sus marcos de páginas entre los otros.