Sistemas Operativos: Memoria y Archivos PDF

176 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 En este capítulo investigaremos varios esquemas distintos de administración de memoria, que varían desde muy simples hasta muy sofisticados. Como generalmente el hardware es el que se en- carga de administrar el nivel más bajo de memoria caché, en este capítulo nos concentraremos en el modelo del programador de la memoria principal y en cómo se puede administrar bien. Las abs- tracciones y la administración del almacenamiento permanente, el disco, son el tema del siguiente capítulo. Analizaremos primero los esquemas más simples posibles y después progresaremos de manera gradual hacia esquemas cada vez más elaborados. 3.1 SIN ABSTRACCIÓN DE MEMORIA La abstracción más simple de memoria es ninguna abstracción. Las primeras computadoras main- frame (antes de 1960), las primeras minicomputadoras (antes de 1970) y las primeras computado- ras personales (antes de 1980) no tenían abstracción de memoria. Cada programa veía simplemente la memoria física. Cuando un programa ejecutaba una instrucción como MOV REGISTRO1, 1000 la computadora sólo movía el contenido de la ubicación de memoria física 1000 a REGISTRO1. Así, el modelo de programación que se presentaba al programador era simplemente la memoria física, un conjunto de direcciones desde 0 hasta cierto valor máximo, en donde cada dirección correspon- día a una celda que contenía cierto número de bits, comúnmente ocho. Bajo estas condiciones, no era posible tener dos programas ejecutándose en memoria al mismo tiempo. Si el primer programa escribía un nuevo valor en, por ejemplo, la ubicación 2000, esto bo- rraría cualquier valor que el segundo programa estuviera almacenando ahí. Ambos programas falla- rían de inmediato. Incluso cuando el modelo de memoria consiste en sólo la memoria física hay varias opciones posibles. En la figura 3-1 se muestran tres variaciones. El sistema operativo puede estar en la parte inferior de la memoria en la RAM (Random Access Memory, Memoria de acceso aleatorio), como se muestra en la figura 3-1(a), puede estar en la ROM (Read Only Memory, Memoria de sólo lec- tura) en la parte superior de la memoria, como se muestra en la figura 3-1(b), o los controladores de dispositivos pueden estar en la parte superior de la memoria en una ROM y el resto del sistema en RAM más abajo, como se muestra en la figura 3-1(c). El primer modelo se utilizó antes en las mainframes y minicomputadoras, pero actualmente casi no se emplea. El segundo modelo se utili- za en algunas computadoras de bolsillo y sistemas integrados. El tercer modelo fue utilizado por las primeras computadoras personales (por ejemplo, las que ejecutaban MS-DOS), donde la porción del sistema en la ROM se conoce como BIOS (Basic Input Output System, Sistema básico de en- trada y salida). Los modelos (a) y (c) tienen la desventaja de que un error en el programa de usua- rio puede borrar el sistema operativo, posiblemente con resultados desastrosos (la información del disco podría quedar ininteligible). Cuando el sistema se organiza de esta forma, por lo general se puede ejecutar sólo un proceso a la vez. Tan pronto como el usuario teclea un comando, el sistema operativo copia el programa so- licitado del disco a la memoria y lo ejecuta. Cuando termina el proceso, el sistema operativo mues- SECCIÓN 3.1 SIN ABSTRACCIÓN DE MEMORIA 177 0xFFF … Drivers de Sistema dispositivos operativo en ROM en ROM Programa de usuario Programa de usuario Programa de usuario Sistema Sistema operativo operativo en RAM en RAM 0 0 0 (a) (b) (c) Figura 3-1. Tres formas simples de organizar la memoria con un sistema operativo y un proceso de usuario. También existen otras posibilidades. tra un carácter indicador de comando y espera un nuevo comando. Cuando recibe el comando, car- ga un nuevo programa en memoria, sobrescribiendo el primero. Una forma de obtener cierto grado de paralelismo en un sistema, sin abstracción de memoria, es programar con múltiples hilos. Como se supone que todos los hilos en un proceso ven la misma imagen de memoria, el hecho de que se vean obligados a hacerlo no es un problema. Aunque esta idea funciona, es de uso limitado ya que lo que las personas desean a menudo es que los programas no relacionados se ejecuten al mismo tiempo, algo que la abstracción de los hilos no provee. Ade- más, es muy poco probable que un sistema tan primitivo como para no proporcionar una abstrac- ción de memoria proporcione una abstracción de hilos. Ejecución de múltiple programas sin una abstracción de memoria No obstante, aun sin abstracción de memoria es posible ejecutar varios programas al mismo tiem- po. Lo que el sistema operativo debe hacer es guardar todo el contenido de la memoria en un archi- vo en disco, para después traer y ejecutar el siguiente programa. Mientras sólo haya un programa a la vez en la memoria no hay conflictos. Este concepto, el intercambio, se analiza a continuación. Con la adición de cierto hardware especial es posible ejecutar múltiples programas concurren- temente, aun sin intercambio. Los primeros modelos de la IBM 360 resolvieron el problema de la siguiente manera: la memoria estaba dividida en bloques de 2 KB y a cada uno se le asignaba una llave de protección de 4 bits, guardada en registros especiales dentro de la CPU. Un equipo con una memoria de 1 MB sólo necesitaba 512 de estos registros de 4 bits para totalizar 256 bytes de almacenamiento de la llave. El registro PSW (Program Status Word, Palabra de estado del progra- ma) también contenía una llave de 4 bits. El hardware de la 360 controlaba mediante un trap cual- quier intento por parte de un proceso en ejecución de acceder a la memoria con un código de protección distinto del de la llave del PSW. Como sólo el sistema operativo podía modificar las lla- ves de protección, los procesos de usuario fueron controlados para que no interfirieran unos con otros, ni con el mismo sistema operativo. 178 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 Sin embargo, esta solución tenía una gran desventaja, que se ilustra en la figura 3-2. Como muestran las figuras 3-2(a) y (b), se tienen dos programas, cada uno con un tamaño de 16 KB. El primero está sombreado para indicar que tiene una llave de memoria diferente a la del segundo y empieza saltando a la dirección 24, que contiene una instrucción MOV; el segundo, saltando a la dirección 28, que contiene una instrucción CMP. Las instrucciones que no son relevantes para este análisis no se muestran. Cuando los dos programas se cargan consecutivamente en la memoria, em- pezando en la dirección 0, tenemos la situación de la figura 3-2(c). Para este ejemplo, suponemos que el sistema operativo está en la parte alta de la memoria y no se muestra. 0 32764... CMP 16412 16408 16404 16400 16396 16392 16388 JMP 28 16384 0 16380 0 16380 0 16380......... ADD 28 CMP 28 ADD 28 MOV 24 24 MOV 24 20 20 20 16 16 16 12 12 12 8 8 8 4 4 4 JMP 24 0 JMP 28 0 JMP 24 0 (a) (b) (c) Figura 3-2. Ilustración del problema de reubicación. (a) Un programa de 16 KB. (b) Otro programa de 16 KB. (c) Los dos programas cargados consecutivamente en la me- moria. Una vez que los programas se cargan se pueden ejecutar. Como tienen distintas llaves de me- moria, ninguno de los dos puede dañar al otro. Pero el problema es de una naturaleza distinta. Cuan- do se inicia el primer programa, ejecuta la instrucción JMP 24, que salta a la instrucción, como se espera. Este programa funciona de manera normal. Sin embargo, después de que el primer programa se ha ejecutado el tiempo suficiente, el siste- ma operativo tal vez decida ejecutar el segundo programa, que se carga encima del primero, en la dirección 16,384. La primera instrucción ejecutada es JMP 28, que salta a la instrucción ADD en el pri- mer programa, y no a la instrucción CMP a la que se supone debe saltar. Es muy probable que el programa falle en menos de 1 segundo. SECCIÓN 3.2 UNA ABSTRACCIÓN DE MEMORIA: ESPACIOS DE DIRECCIONES 179 El problema central aquí es que los dos programas hacen referencia a la memoria física absolu- ta. Eso, definitivamente, no es lo que queremos; deseamos que cada programa haga referencia a un conjunto privado de direcciones locales para él. En breve le mostraremos cómo se logra esto. Lo que la IBM 360 hacía como solución para salir del paso era modificar el segundo programa al instante, a medida que se cargaba en la memoria, usando una técnica conocida como reubicación estática. Esta técnica funcionaba así: cuando se cargaba un programa en la dirección 16,384, se sumaba el va- lor constante 16,384 a todas las direcciones del programa durante el proceso de carga. Aunque este mecanismo funciona si se lleva a cabo en la forma correcta, no es una solución muy general y redu- ce la velocidad de la carga. Lo que es más, se requiere información adicional en todos los programas ejecutables para indicar cuáles palabras contienen direcciones (reubicables) y cuáles no. Después de todo, el “28” en la figura 3-2(b) tiene que reubicarse, pero una instrucción como MOV REGISTRO1, 28 que mueve el número 28 a REGISTRO1 no se debe reubicar. El cargador necesita cierta forma de saber qué es una dirección y qué es una constante. Por último, como recalcamos en el capítulo 1, la historia tiende a repetirse en el mundo de las computadoras. Mientras que el direccionamiento directo de la memoria física está muy lejos de po- der aplicarse en las mainframes, minicomputadoras, computadoras de escritorio y notebooks, la fal- ta de una abstracción de memoria sigue siendo común en los sistemas integrados y de tarjeta inteligente. En la actualidad, los dispositivos como las radios, las lavadoras y los hornos de mi- croondas están llenos de software (en ROM), y en la mayoría de los casos el software direcciona memoria absoluta. Esto funciona debido a que todos los programas se conocen de antemano, y los usuarios no tienen la libertad de ejecutar su propio software en su tostador. Mientras que los sistemas integrados de alta tecnología (como los teléfonos celulares) tienen sistemas operativos elaborados, los más simples no. En algunos casos hay un sistema operativo, pe- ro es sólo una biblioteca ligada con el programa de aplicación y proporciona llamadas al sistema para realizar operaciones de E/S y otras tareas comunes. El popular sistema operativo e-cos es un ejemplo común de un sistema operativo como biblioteca. 3.2 UNA ABSTRACCIÓN DE MEMORIA: ESPACIOS DE DIRECCIONES Con todo, exponer la memoria física a los procesos tiene varias desventajas. En primer lugar, si los programas de usuario pueden direccionar cada byte de memoria, pueden estropear el sistema operati- vo con facilidad, ya sea intencional o accidentalmente, con lo cual el sistema se detendría en forma súbita (a menos que haya hardware especial como el esquema de bloqueo y llaves de la IBM 360). Es- te problema existe aun cuando sólo haya un programa de usuario (aplicación) en ejecución. En segun- do lugar, con este modelo es difícil tener varios programas en ejecución a la vez (tomando turnos, si sólo hay una CPU). En las computadoras personales es común tener varios programas abiertos a la vez (un procesador de palabras, un programa de correo electrónico y un navegador Web, donde uno de ellos tiene el enfoque actual, pero los demás se reactivan con el clic de un ratón). Como esta situa- ción es difícil de lograr cuando no hay una abstracción de la memoria física, se tuvo que hacer algo. 180 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 3.2.1 La noción de un espacio de direcciones Hay que resolver dos problemas para permitir que haya varias aplicaciones en memoria al mismo tiempo sin que interfieran entre sí: protección y reubicación. Ya analizamos una solución primiti- va al primer problema en la IBM 360: etiquetar trozos de memoria con una llave de protección y comparar la llave del proceso en ejecución con la de cada palabra de memoria obtenida por la CPU. Sin embargo, este método por sí solo no resuelve el segundo problema, aunque se puede resolver mediante la reubicación de los programas al momento de cargarlos, pero ésta es una solución lenta y complicada. Una mejor solución es inventar una nueva abstracción para la memoria: el espacio de direccio- nes. Así como el concepto del proceso crea un tipo de CPU abstracta para ejecutar programas, el espacio de direcciones crea un tipo de memoria abstracta para que los programas vivan ahí. Un es- pacio de direcciones (address space) es el conjunto de direcciones que puede utilizar un proceso para direccionar la memoria. Cada proceso tiene su propio espacio de direcciones, independiente de los que pertenecen a otros procesos (excepto en ciertas circunstancias especiales en donde los pro- cesos desean compartir sus espacios de direcciones). El concepto de un espacio de direcciones es muy general y ocurre en muchos contextos. Con- sidere los números telefónicos. En los Estados Unidos y en muchos otros países, un número de te- léfono local es comúnmente un número de 7 dígitos. En consecuencia, el espacio de direcciones para los números telefónicos varía desde 0,000,000 hasta 9,999,999, aunque algunos números, co- mo los que empiezan con 000, no se utilizan. Con el crecimiento de los teléfonos celulares, módems y máquinas de fax, este espacio se está volviendo demasiado pequeño, en cuyo caso habrá qué uti- lizar más dígitos. El espacio de direcciones para los puertos de E/S en el Pentium varía desde 0 has- ta 16383. Las direcciones IPv4 son números de 32 bits, por lo que su espacio de direcciones varía desde 0 hasta 232 – 1 (de nuevo, con ciertos números reservados). Los espacios de direcciones no tienen que ser numéricos. El conjunto de dominios.com de In- ternet es también un espacio de direcciones. Este espacio de direcciones consiste de todas las cade- nas de longitud de 2 a 63 caracteres que se puedan formar utilizando letras, números y guiones cortos, seguidas de.com. Para estos momentos usted debe de hacerse hecho ya la idea. Es bastante simple. Algo un poco más difícil es proporcionar a cada programa su propio espacio de direcciones, de manera que la dirección 28 en un programa indique una ubicación física distinta de la dirección 28 en otro programa. A continuación analizaremos una forma simple que solía ser común, pero ha caí- do en desuso debido a la habilidad de poner esquemas mucho más complicados (y mejores) en los chips de CPU modernos. Registros base y límite La solución sencilla utiliza una versión muy simple de la reubicación dinámica. Lo que hace es asociar el espacio de direcciones de cada proceso sobre una parte distinta de la memoria física, de una manera simple. La solución clásica, que se utilizaba en máquinas desde la CDC 6600 (la pri- mera supercomputadora del mundo) hasta el Intel 8088 (el corazón de la IBM PC original), es equi- par cada CPU con dos registros de hardware especiales, conocidos comúnmente como los registros SECCIÓN 3.2 UNA ABSTRACCIÓN DE MEMORIA: ESPACIOS DE DIRECCIONES 181 base y límite. Cuando se utilizan estos registros, los programas se cargan en ubicaciones consecuti- vas de memoria en donde haya espacio y sin reubicación durante la carga, como se muestra en la fi- gura 3-2(c). Cuando se ejecuta un proceso, el registro base se carga con la dirección física donde empieza el programa en memoria y el registro límite se carga con la longitud del programa. En la fi- gura 3-2(c), los valores base y límite que se cargarían en estos registros de hardware al ejecutar el pri- mer programa son 0 y 16,384, respectivamente. Los valores utilizados cuando se ejecuta el segundo programa son 16,384 y 16,384, respectivamente. Si se cargara un tercer programa de 16 KB directa- mente por encima del segundo y se ejecutara, los registros base y límite serían 32,768 y 16,384. Cada vez que un proceso hace referencia a la memoria, ya sea para obtener una instrucción de memoria, para leer o escribir una palabra de datos, el hardware de la CPU suma de manera automá- tica el valor base a la dirección generada por el proceso antes de enviar la dirección al bus de me- moria. Al mismo tiempo comprueba si la dirección ofrecida es igual o mayor que el valor resultante de sumar los valores de los registros límite y base, en cuyo caso se genera un fallo y se aborta el ac- ceso. Por ende, en el caso de la primera instrucción del segundo programa en la figura 3-2(c), el proceso ejecuta una instrucción JMP 28 pero el hardware la trata como si fuera JMP 16412 por lo que llega a la instrucción CMP, como se esperaba. Los valores de los registros base y límite durante la ejecución del segundo programa de la figura 3-2(c) se muestran en la figura 3-3. El uso de registros base y límite es una manera fácil de proporcionar a cada proceso su propio espacio de direcciones privado, ya que a cada dirección de memoria que se genera en forma auto- mática se le suma el contenido del registro base antes de enviarla a memoria. En muchas implemen- taciones, los registros base y límite están protegidos de tal forma que sólo el sistema operativo puede modificarlos. Éste fue el caso en la CDC 6600, pero no el del Intel 8088, que ni siquiera te- nía el registro límite. Sin embargo, tenía varios registros base, lo cual permitía que se reubicaran texto y datos de manera independiente, pero no ofrecía una protección contra las referencias a me- moria fuera de rango. Una desventaja de la reubicación usando los registros base y límite es la necesidad de realizar una suma y una comparación en cada referencia a memoria. Las comparaciones se pueden hacer con rapidez, pero las sumas son lentas debido al tiempo de propagación del acarreo, a menos que se utilicen circuitos especiales de suma. 3.2.2 Intercambio Si la memoria física de la computadora es lo bastante grande como para contener todos los proce- sos, los esquemas descritos hasta ahora funcionarán en forma más o menos correcta. Pero en la práctica, la cantidad total de RAM que requieren todos los procesos es a menudo mucho mayor de lo que puede acomodarse en memoria. En un sistema Windows o Linux común, se pueden iniciar 182 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 16384 0 32764.. Registro límite. CMP 16412 16408 16404 16400 16396 16392 16388 16384 JMP 28 16384 0 16380.. Registro base. ADD 28 MOV 24 20 16 12 8 4 JMP 24 0 (c) Figura 3-3. Se pueden utilizar registros base y límite para dar a cada proceso un espa- cio de direcciones separado. entre 40 y 60 procesos o más cada vez que se inicia la computadora. Por ejemplo, cuando se insta- la una aplicación Windows, a menudo emite comandos de manera que en los inicios subsiguientes del sistema se inicie un proceso que no haga nada, excepto buscar actualizaciones para la aplica- ción. Dicho proceso puede ocupar fácilmente de 5 a 10 MB de memoria. Otros procesos en segun- do plano comprueban el correo entrante, las conexiones de red entrantes y muchas otras cosas. Y todo esto se hace antes de que se inicie el primer programa de usuario. Hoy en día, los programas de aplicaciones de usuario serios pueden ejecutarse ocupando fácilmente desde 50 a 200 MB y más. En consecuencia, para mantener todos los procesos en memoria todo el tiempo se requiere una gran cantidad de memoria y no puede hacerse si no hay memoria suficiente. A través de los años se han desarrollado dos esquemas generales para lidiar con la sobrecar- ga de memoria. La estrategia más simple, conocida como intercambio, consiste en llevar ca- da proceso completo a memoria, ejecutarlo durante cierto tiempo y después regresarlo al disco. Los procesos inactivos mayormente son almacenados en disco, de tal manera que no ocupan memoria cuando no se están ejecutando (aunque algunos de ellos se despiertan periódicamente pa- ra realizar su trabajo y después vuelven a quedar inactivos). La otra estrategia, conocida como me- moria virtual, permite que los programas se ejecuten incluso cuando sólo se encuentran en forma parcial en la memoria. A continuación estudiaremos el intercambio; en la sección 3.3 examinare- mos la memoria virtual. SECCIÓN 3.2 UNA ABSTRACCIÓN DE MEMORIA: ESPACIOS DE DIRECCIONES 183 La operación de un sistema de intercambio se ilustra en la figura 3-4. Al principio, sólo el pro- ceso A está en la memoria. Después los procesos B y C se crean o se intercambian desde disco. En la figura 3-4(d), A se intercambia al disco. Después llega D y sale B. Por último, A entra de nuevo. Como A está ahora en una ubicación distinta, las direcciones que contiene se deben reubicar, ya sea mediante software cuando se intercambia o (más probablemente) mediante hardware durante la eje- cución del programa. Por ejemplo, los registros base y límite funcionarían bien en este caso. Tiempo C C C C C B B B B A A A A D D D Sistema Sistema Sistema Sistema Sistema Sistema Sistema operativo operativo operativo operativo operativo operativo operativo (a) (b) (c) (d) (e) (f) (g) Figura 3-4. La asignación de la memoria cambia a medida que llegan procesos a la memoria y salen de ésta. Las regiones sombreadas son la memoria sin usar. Cuando el intercambio crea varios huecos en la memoria, es posible combinarlos todos en uno grande desplazando los procesos lo más hacia abajo que sea posible. Esta técnica se conoce como compactación de memoria. Por lo general no se realiza debido a que requiere mucho tiempo de la CPU. Por ejemplo, en una máquina con 1 GB que pueda copiar 4 bytes en 20 nseg, se requerirían aproximadamente 5 segundos para compactar toda la memoria. Un aspecto que vale la pena mencionar es la cantidad de memoria que debe asignarse a un pro- ceso cuando éste se crea o se intercambia. Si los procesos se crean con un tamaño fijo que nunca cambia, entonces la asignación es sencilla: el sistema operativo asigna exactamente lo necesario, ni más ni menos. No obstante, si los segmentos de datos de los procesos pueden crecer, por ejemplo mediante la asignación dinámica de memoria proveniente de un heap, como en muchos lenguajes de programa- ción, ocurre un problema cuando un proceso trata de crecer. Si hay un hueco adyacente al proceso, puede asignarse y se permite al proceso crecer en el hueco; si el proceso está adyacente a otro pro- ceso, el proceso en crecimiento tendrá que moverse a un hueco en memoria que sea lo bastante grande como para alojarlo, o habrá que intercambiar uno o más procesos para crear un hueco con el tamaño suficiente. Si un proceso no puede crecer en memoria y el área de intercambio en el dis- co está llena, el proceso tendrá que suspenderse hasta que se libere algo de espacio (o se puede eli- minar). 184 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 Si se espera que la mayoría de los procesos crezcan a medida que se ejecuten, probablemente sea conveniente asignar un poco de memoria adicional cada vez que se intercambia o se mueve un proceso, para reducir la sobrecarga asociada con la acción de mover o intercambiar procesos que ya no caben en su memoria asignada. No obstante, al intercambiar procesos al disco, se debe intercam- biar sólo la memoria que se encuentre en uso; es un desperdicio intercambiar también la memoria adicional. En la figura 3-5(a) podemos ver una configuración de memoria en la cual se ha asigna- do espacio para que crezcan dos procesos. Pila de B Espacio para crecer Espacio para crecer Datos de B B Realmente en uso Programa de B Pila de A Espacio para crecer Espacio para crecer Datos de A A Realmente en uso Programa de A Sistema Sistema operativo operativo (a) (b) Figura 3-5. (a) Asignación de espacio para un segmento de datos en crecimiento. (b) Asignación de espacio para una pila en crecimiento y un segmento de datos en cre- cimiento. Si los procesos pueden tener dos segmentos en crecimiento, por ejemplo, cuando el segmento de datos se utiliza como heap para las variables que se asignan y liberan en forma dinámica y un segmento de pila para las variables locales normales y las direcciones de retorno, un arreglo alter- nativo se sugiere por sí mismo, a saber, el de la figura 3-5(b). En esta figura podemos ver que cada proceso ilustrado tiene una pila en la parte superior de su memoria asignada, la cual está creciendo hacia abajo, y un segmento de datos justo debajo del texto del programa, que está creciendo hacia arriba. La memoria entre estos segmentos se puede utilizar para cualquiera de los dos. Si se agota, el proceso tendrá que moverse a un hueco con suficiente espacio, intercambiarse fuera de la memo- ria hasta que se pueda crear un hueco lo suficientemente grande, o eliminarse. 3.2.3 Administración de memoria libre Cuando la memoria se asigna en forma dinámica, el sistema operativo debe administrarla. En tér- minos generales, hay dos formas de llevar el registro del uso de la memoria: mapas de bits y listas libres. En esta sección y en la siguiente analizaremos estos dos métodos. SECCIÓN 3.2 UNA ABSTRACCIÓN DE MEMORIA: ESPACIOS DE DIRECCIONES 185 Administración de memoria con mapas de bits Con un mapa de bits, la memoria se divide en unidades de asignación tan pequeñas como unas cuan- tas palabras y tan grandes como varios kilobytes. Para cada unidad de asignación hay un bit corres- pondiente en el mapa de bits, que es 0 si la unidad está libre y 1 si está ocupada (o viceversa). La figura 3-6 muestra parte de la memoria y el mapa de bits correspondiente. A B C D E 8 16 24 (a) 11111000 P 0 5 H 5 3 P 8 6 P 14 4 11111111 11001111 H 18 2 P 20 6 P 26 3 H 29 3 X 11111000 Hueco Empieza Longitud Proceso en la 18 2 (b) (c) Figura 3-6. (a) Una parte de la memoria con cinco procesos y tres huecos. Las mar- cas de graduación muestran las unidades de asignación de memoria. Las regiones som- breadas (0 en el mapa de bits) están libres. (b) El mapa de bits correspondiente. (c) La misma información en forma de lista. El tamaño de la unidad de asignación es una importante cuestión de diseño. Entre más peque- ña sea la unidad de asignación, mayor será el mapa de bits. Sin embargo, aun con una unidad de asignación tan pequeña como 4 bytes, 32 bits de memoria sólo requerirán 1 bit del mapa. Una me- moria de 32n bits utilizará n bits del mapa, por lo que el mapa de bits ocupará sólo 1/33 de la memo- ria. Si la unidad de asignación se elige de manera que sea grande, el mapa de bits será más pequeño pero se puede desperdiciar una cantidad considerable de memoria en la última unidad del proceso si su tamaño no es un múltiplo exacto de la unidad de asignación. Un mapa de bits proporciona una manera simple de llevar el registro de las palabras de memoria en una cantidad fija de memoria, debido a que el tamaño del mapa de bits sólo depende del tamaño de la memoria y el tamaño de la unidad de asignación. El problema principal es que, cuando se ha de- cidido llevar un proceso de k unidades a la memoria, el administrador de memoria debe buscar en el mapa para encontrar una serie de k bits consecutivos con el valor 0 en el mapa de bits. El proceso de buscar en un mapa de bits una serie de cierta longitud es una operación lenta (debido a que la serie puede cruzar los límites entre las palabras en el mapa); éste es un argumento contra los mapas de bits. Administración de memoria con listas ligadas Otra manera de llevar el registro de la memoria es mantener una lista ligada de segmentos de me- moria asignados y libres, en donde un segmento contiene un proceso o es un hueco vacío entre dos 186 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 procesos. La memoria de la figura 3-6(a) se representa en la figura 3-6(c) como una lista ligada de segmentos. Cada entrada en la lista especifica un hueco (H) o un proceso (P), la dirección en la que inicia, la longitud y un apuntador a la siguiente entrada. En este ejemplo, la lista de segmentos se mantiene ordenada por dirección. Al ordenarla de es- ta manera, tenemos la ventaja de que cuando termina un proceso o se intercambia, el proceso de ac- tualizar la lista es simple. Un proceso en terminación por lo general tiene dos vecinos (excepto cuando se encuentra en la parte superior o inferior de la memoria). Éstos pueden ser procesos o hue- cos, lo cual conduce a las cuatro combinaciones de la figura 3-7. En la figura 3-7(a), para actuali- zar la lista se requiere reemplazar una P por una H. En las figuras 3-7(b) y 3-7(c) dos entradas se fusionan en una sola y la lista se reduce en una entrada. En la figura 3-7(d), se fusionan las tres en- tradas y dos elementos son eliminados de la lista. Como la ranura de la tabla de procesos para el proceso en terminación en general apuntará a la entrada en la lista para el mismo proceso, puede ser más conveniente tener la lista como una lista doblemente ligada, en vez de la lista simplemente ligada de la figura 3-6(c). Esta estructura facili- ta encontrar la entrada anterior y ver si es posible una combinación. Antes de que termine X Después de que termina X (a) A X B se convierte en A B (b) A X se convierte en A (c) X B se convierte en B (d) X se convierte en Figura 3-7. Cuatro combinaciones de los vecinos para el proceso en terminación, X. Cuando los procesos y huecos se mantienen en una lista ordenada por dirección, se pueden utili- zar varios algoritmos para asignar memoria a un proceso creado (o a un proceso existente que se in- tercambie del disco). Suponemos que el administrador de memoria sabe cuánta debe asignar. El algoritmo más simple es el de primer ajuste: el administrador de memoria explora la lista de segmen- tos hasta encontrar un hueco que sea lo bastante grande. Después el hueco se divide en dos partes, una para el proceso y otra para la memoria sin utilizar, excepto en el estadísticamente improbable caso de un ajuste exacto. El algoritmo del primer ajuste es rápido debido a que busca lo menos posible. Una pequeña variación del algoritmo del primer ajuste es el algoritmo del siguiente ajuste. Funciona de la misma manera que el primer ajuste, excepto porque lleva un registro de dónde se encuentra cada vez que descubre un hueco adecuado. La siguiente vez que es llamado para buscar un hueco, empieza a buscar en la lista desde el lugar en el que se quedó la última vez, en vez de empezar siempre desde el principio, como el algoritmo del primer ajuste. Las simulaciones realiza- das por Bays (1977) muestran que el algoritmo del siguiente ajuste tiene un rendimiento ligeramen- te peor que el del primer ajuste. Otro algoritmo muy conocido y ampliamente utilizado es el del mejor ajuste. Este algoritmo busca en toda la lista, de principio a fin y toma el hueco más pequeño que sea adecuado. En vez de dividir un gran hueco que podría necesitarse después, el algoritmo del mejor ajuste trata de buscar SECCIÓN 3.2 UNA ABSTRACCIÓN DE MEMORIA: ESPACIOS DE DIRECCIONES 187 un hueco que esté cerca del tamaño actual necesario, que coincida mejor con la solicitud y los hue- cos disponibles. Como ejemplo de los algoritmos de primer ajuste y de mejor ajuste, considere de nuevo la fi- gura 3-6. Si se necesita un bloque de tamaño 2, el algoritmo del primer ajuste asignará el hueco en la 5, pero el del mejor ajuste asignará el hueco en la 18. El algoritmo del mejor ajuste es más lento que el del primer ajuste, ya que debe buscar en to- da la lista cada vez que se le llama. De manera sorprendente, también provoca más desperdicio de memoria que los algoritmos del primer ajuste o del siguiente ajuste, debido a que tiende a llenar la memoria con huecos pequeños e inutilizables. El algoritmo del primer ajuste genera huecos más grandes en promedio. Para resolver el problema de dividir las coincidencias casi exactas en un proceso y en un pe- queño hueco, podríamos considerar el algoritmo del peor ajuste, es decir, tomar siempre el hueco más grande disponible, de manera que el nuevo hueco sea lo bastante grande como para ser útil. La simulación ha demostrado que el algoritmo del peor ajuste no es muy buena idea tampoco. Los cuatro algoritmos pueden ser acelerados manteniendo listas separadas para los procesos y los huecos. De esta forma, todos ellos dedican toda su energía a inspeccionar los huecos, no los pro- cesos. El precio inevitable que se paga por esta aceleración en la asignación es la complejidad adi- cional y la lentitud al desasignar la memoria, ya que un segmento liberado tiene que eliminarse de la lista de procesos e insertarse en la lista de huecos. Si se mantienen distintas listas para los procesos y los huecos, la lista de huecos se puede man- tener ordenada por el tamaño, para que el algoritmo del mejor ajuste sea más rápido. Cuando el al- goritmo del mejor ajuste busca en una lista de huecos, del más pequeño al más grande, tan pronto como encuentre un hueco que ajuste, sabrá que el hueco es el más pequeño que se puede utilizar, de aquí que se le denomine el mejor ajuste. No es necesario buscar más, como con el esquema de una sola lista. Con una lista de huecos ordenada por tamaño, los algoritmos del primer ajuste y del mejor ajuste son igual de rápidos, y hace innecesario usar el del siguiente ajuste. Cuando los huecos se mantienen en listas separadas de los procesos, una pequeña optimización es posible. En vez de tener un conjunto separado de estructuras de datos para mantener la lista de huecos, como se hizo en la figura 3-6(c), la información se puede almacenar en los huecos. La pri- mera palabra de cada hueco podría ser el tamaño del mismo y la segunda palabra un apuntador a la siguiente entrada. Los nodos de la lista de la figura 3-6(c), que requieren tres palabras y un bit (P/H), ya no son necesarios. Un algoritmo de asignación más es el denominado de ajuste rápido, el cual mantiene listas se- paradas para algunos de los tamaños más comunes solicitados. Por ejemplo, podría tener una tabla con n entradas, en donde la primera entrada es un apuntador a la cabeza de una lista de huecos de 4 KB, la segunda entrada es un apuntador a una lista de huecos de 8 KB, la tercera entrada un apun- tador a huecos de 12 KB y así sucesivamente. Por ejemplo, los huecos de 21 KB podrían colocar- se en la lista de 20 KB o en una lista especial de huecos de tamaño inusual. Con el algoritmo del ajuste rápido, buscar un hueco del tamaño requerido es extremadamente rápido, pero tiene la misma desventaja que todos los esquemas que se ordenan por el tamaño del hueco: cuando un proceso termina o es intercambiado, buscar en sus vecinos para ver si es posible una fusión es un proceso costoso. Si no se realiza la fusión, la memoria se fragmentará rápidamen- te en un gran número de pequeños huecos en los que no cabrá ningún proceso. 188 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 3.3 MEMORIA VIRTUAL Mientras que los registros base y límite se pueden utilizar para crear la abstracción de los espacios de direcciones, hay otro problema que se tiene que resolver: la administración del agrandamiento del soft- ware (bloatware). Aunque el tamaño de las memorias se incrementa con cierta rapidez, el del softwa- re aumenta con una mucha mayor. En la década de 1980, muchas universidades operaban un sistema de tiempo compartido con docenas de usuarios (más o menos satisfechos) trabajando simultáneamen- te en una VAX de 4 MB. Ahora Microsoft recomienda tener por lo menos 512 MB para que un siste- ma Vista de un solo usuario ejecute aplicaciones simples y 1 GB si el usuario va a realizar algún trabajo serio. La tendencia hacia la multimedia impone aún mayores exigencias sobre la memoria. Como consecuencia de estos desarrollos, existe la necesidad de ejecutar programas que son de- masiado grandes como para caber en la memoria y sin duda existe también la necesidad de tener sistemas que puedan soportar varios programas ejecutándose al mismo tiempo, cada uno de los cua- les cabe en memoria, pero que en forma colectiva exceden el tamaño de la misma. El intercambio no es una opción atractiva, ya que un disco SATA ordinario tiene una velocidad de transferencia pi- co de 100 MB/segundo a lo más, lo cual significa que requiere por lo menos 10 segundos para in- tercambiar un programa de 1 GB de memoria a disco y otros 10 segundos para intercambiar un programa de 1 GB del disco a memoria. El problema de que los programas sean más grandes que la memoria ha estado presente desde los inicios de la computación, en áreas limitadas como la ciencia y la ingeniería (para simular la creación del universo o, incluso, para simular una nueva aeronave, se requiere mucha memoria). Una solución que se adoptó en la década de 1960 fue dividir los programas en pequeñas partes, co- nocidas como sobrepuestos (overlays). Cuando empezaba un programa, todo lo que se cargaba en memoria era el administrador de sobrepuestos, que de inmediato cargaba y ejecutaba el sobrepues- to 0; cuando éste terminaba, indicaba al administrador de sobrepuestos que cargara el 1 encima del sobrepuesto 0 en la memoria (si había espacio) o encima del mismo (si no había espacio). Algunos sistemas de sobrepuestos eran muy complejos, ya que permitían varios sobrepuestos en memoria a la vez. Los sobrepuestos se mantenían en el disco, intercambiándolos primero hacia adentro de la memoria y después hacia afuera de la memoria mediante el administrador de sobrepuestos. Aunque el trabajo real de intercambiar sobrepuestos hacia adentro y hacia afuera de la memo- ria lo realizaba el sistema operativo, el de dividir el programa en partes tenía que realizarlo el pro- gramador en forma manual. El proceso de dividir programas grandes en partes modulares más pequeñas consumía mucho tiempo, y era aburrido y propenso a errores. Pocos programadores eran buenos para esto. No pasó mucho tiempo antes de que alguien ideara una forma de pasar todo el trabajo a la computadora. El método ideado (Fotheringham, 1961) se conoce actualmente como memoria virtual. La idea básica detrás de la memoria virtual es que cada programa tiene su propio espacio de direcciones, el cual se divide en trozos llamados páginas. Cada página es un rango contiguo de direcciones. Estas páginas se asocian a la memoria física, pero no todas tienen que estar en la memoria física para poder ejecutar el programa. Cuando el programa hace referencia a una parte de su espacio de direcciones que está en la memoria física, el hardware realiza la asociación necesaria al instante. Cuando el programa hace refe- rencia a una parte de su espacio de direcciones que no está en la memoria física, el sistema operativo recibe una alerta para buscar la parte faltante y volver a ejecutar la instrucción que falló. SECCIÓN 3.3 MEMORIA VIRTUAL 189 En cierto sentido, la memoria virtual es una generalización de la idea de los registros base y lí- mite. El procesador 8088 tenía registros base separados (pero no tenía registros límite) para texto y datos. Con la memoria virtual, en vez de tener una reubicación por separado para los segmentos de texto y de datos, todo el espacio de direcciones se puede asociar a la memoria física en unidades pequeñas equitativas. A continuación le mostraremos cómo se implementa la memoria virtual. La memoria virtual funciona muy bien en un sistema de multiprogramación, con bits y partes de muchos programas en memoria a la vez. Mientras un programa espera a que una parte del mis- mo se lea y coloque en la memoria, la CPU puede otorgarse a otro proceso. 3.3.1 Paginación La mayor parte de los sistemas de memoria virtual utilizan una técnica llamada paginación, que describiremos a continuación. En cualquier computadora, los programas hacen referencia a un con- junto de direcciones de memoria. Cuando un programa ejecuta una instrucción como MOV REG, 1000 lo hace para copiar el contenido de la dirección de memoria 1000 a REG (o viceversa, dependiendo de la computadora). Las direcciones se pueden generar usando indexado, registros base, registros de segmentos y otras formas más. La CPU envía direcciones Paquete virtuales a la MMU de la CPU CPU Unidad de Controlador administración Memoria de disco de memoria Bus La MMU envía direcciones físicas a la memoria Figura 3-8. La posición y función de la MMU. Aquí la MMU se muestra como parte del chip de CPU, debido a que es común esta configuración en la actualidad. Sin em- bargo, lógicamente podría ser un chip separado y lo era hace años. Estas direcciones generadas por el programa se conocen como direcciones virtuales y forman el espacio de direcciones virtuales. En las computadoras sin memoria virtual, la dirección física se coloca directamente en el bus de memoria y hace que se lea o escriba la palabra de memoria fí- sica con la misma dirección. Cuando se utiliza memoria virtual, las direcciones virtuales no van di- rectamente al bus de memoria. En vez de ello, van a una MMU (Memory Managemente Unit, 190 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 Unidad de administración de memoria) que asocia las direcciones virtuales a las direcciones de memoria físicas, como se ilustra en la figura 3-8. En la figura 3-9 se muestra un ejemplo muy simple de cómo funciona esta asociación. En este ejemplo, tenemos una computadora que genera direcciones de 16 bits, desde 0 hasta 64 K. Éstas son las direcciones virtuales. Sin embargo, esta computadora sólo tiene 32 KB de memoria física. Así, aunque se pueden escribir programas de 64 KB, no se pueden cargar completos en memoria y ejecu- tarse. No obstante, una copia completa de la imagen básica de un programa, de hasta 64 KB, debe estar presente en el disco para que las partes se puedan traer a la memoria según sea necesario. El espacio de direcciones virtuales se divide en unidades de tamaño fijo llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos de página. Las páginas y los mar- cos de página por lo general son del mismo tamaño. En este ejemplo son de 4 KB, pero en sistemas reales se han utilizado tamaños de página desde 512 bytes hasta 64 KB. Con 64 KB de espacio de direcciones virtuales y 32 KB de memoria física obtenemos 16 páginas virtuales y 8 marcos de pá- gina. Las transferencias entre la RAM y el disco siempre son en páginas completas. Espacio de direcciones virtuales 60Kñ64K X 56Kñ60K X Página virtual 52Kñ56K X 48Kñ52K X 44Kñ48K 7 40Kñ44K X Dirección de 36Kñ40K 5 memoria 32Kñ36K X física 28Kñ32K X 28Kñ32K 24Kñ28K X 24Kñ28K 20Kñ24K 3 20Kñ24K 16Kñ20K 4 16Kñ20K 12Kñ16K 0 12Kñ16K 8Kñ12K 6 8Kñ12K 4Kñ8K 1 4Kñ8K 0Kñ4K 2 0Kñ4K Marco de página Figura 3-9. La relación entre las direcciones virtuales y las direcciones de memoria fí- sica está dada por la tabla de páginas. Cada página empieza en un múltiplo de 4096 y termina 4095 direcciones más arriba, por lo que de 4 K a 8 K en realidad significa de 4096 a 8191 y de 8 K a 12 K significa de 8192 a 12287. La notación en la figura 3-9 es la siguiente. El rango marcado de 0K a 4 K significa que las di- recciones virtuales o físicas en esa página son de 0 a 4095. El rango de 4 K a 8 K se refiere a las SECCIÓN 3.3 MEMORIA VIRTUAL 191 direcciones de 4096 a 8191 y así en lo sucesivo. Cada página contiene exactamente 4096 direccio- nes que empiezan en un múltiplo de 4096 y terminan uno antes del múltiplo de 4096. Por ejemplo, cuando el programa trata de acceder a la dirección 0 usando la instrucción MOV REG,0 la dirección virtual 0 se envía a la MMU. La MMU ve que esta dirección virtual está en la página 0 (0 a 4095), que de acuerdo con su asociación es el marco de página 2 (8192 a 12287). Así, trans- forma la dirección en 8192 y envía la dirección 8192 al bus. La memoria no sabe nada acerca de la MMU y sólo ve una petición para leer o escribir en la dirección 8192, la cual cumple. De esta ma- nera, la MMU ha asociado efectivamente todas las direcciones virtuales entre 0 y 4095 sobre las di- recciones físicas de 8192 a 12287. De manera similar, la instrucción MOV REG,8192 se transforma efectivamente en MOV REG,24576 debido a que la dirección virtual 8192 (en la página virtual 2) se asocia con la dirección 24576 (en el marco de página físico 6). Como tercer ejemplo, la dirección virtual 20500 está a 20 bytes del inicio de la página virtual 5 (direcciones virtuales 20480 a 24575) y la asocia con la dirección físi- ca 12288 20 12308. Por sí sola, la habilidad de asociar 16 páginas virtuales a cualquiera de los ocho marcos de pá- gina mediante la configuración de la apropiada asociación de la MMU no resuelve el problema de que el espacio de direcciones virtuales sea más grande que la memoria física. Como sólo tenemos ocho marcos de página físicos, sólo ocho de las páginas virtuales en la figura 3-9 se asocian a la memoria física. Las demás, que se muestran con una cruz en la figura, no están asociadas. En el hardware real, un bit de presente/ausente lleva el registro de cuáles páginas están físicamente pre- sentes en la memoria. ¿Qué ocurre si el programa hace referencia a direcciones no asociadas, por ejemplo, mediante el uso de la instrucción MOV REG,32780 que es el byte 12 dentro de la página virtual 8 (empezando en 32768)? La MMU detecta que la pá- gina no está asociada (lo cual se indica mediante una cruz en la figura) y hace que la CPU haga un trap al sistema operativo. A este trap se le llama fallo de página. El sistema operativo selecciona un marco de página que se utilice poco y escribe su contenido de vuelta al disco (si no es que ya es- tá ahí). Después obtiene la página que se acaba de referenciar en el marco de página que se acaba de liberar, cambia la asociación y reinicia la instrucción que originó el trap. Por ejemplo, si el sistema operativo decidiera desalojar el marco de página 1, cargaría la pági- na virtual 8 en la dirección física 8192 y realizaría dos cambios en la asociación de la MMU. Pri- mero, marcaría la entrada de la página virtual 1 como no asociada, para hacer un trap por cualquier acceso a las direcciones virtuales entre 4096 y 8191. Después reemplazaría la cruz en la entrada de 192 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 la página virtual 8 con un 1, de manera que al ejecutar la instrucción que originó el trap, asocie la dirección virtual 32780 a la dirección física 4108 (4096 12). Ahora veamos dentro de la MMU para analizar su funcionamiento y por qué hemos optado por utilizar un tamaño de página que sea una potencia de 2. En la figura 3-10 vemos un ejemplo de una dirección virtual, 8196 (0010000000000100 en binario), que se va a asociar usando la asociación de la MMU en la figura 3-9. La dirección virtual entrante de 16 bits se divide en un número de pá- gina de 4 bits y en un desplazamiento de 12 bits. Con 4 bits para el número de página, podemos te- ner 16 páginas y con los 12 bits para el desplazamiento, podemos direccionar todos los 4096 bytes dentro de una página. Dirección 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 física saliente (24580) 15 000 0 14 000 0 13 000 0 12 000 0 11 111 1 10 000 0 9 101 1 El desplazamiento Tabla de 8 000 0 de 12 bits copiado páginas 7 000 0 directamente de la 6 000 0 entrada a la salida 5 011 1 4 100 1 3 000 1 2 110 1 110 1 001 1 Bit de 0 010 1 presente/ ausente La página virtual = 2 se utiliza como índice en la tabla de páginas Dirección virtual entrante (8196) 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 Figura 3-10. La operación interna de la MMU con 16 páginas de 4 KB. El número de página se utiliza como índice en la tabla de páginas, conduciendo al número del marco de página que corresponde a esa página virtual. Si el bit de presente/ausente es 0, se provo- ca un trap al sistema operativo. Si el bit es 1, el número del marco de página encontrado en la tabla de páginas se copia a los 3 bits de mayor orden del registro de salida, junto con el desplazamien- to de 12 bits, que se copia sin modificación de la dirección virtual entrante. En conjunto forman una dirección física de 15 bits. Después, el registro de salida se coloca en el bus de memoria como la dirección de memoria física. SECCIÓN 3.3 MEMORIA VIRTUAL 193 3.3.2 Tablas de páginas En una implementación simple, la asociación de direcciones virtuales a direcciones físicas se pue- de resumir de la siguiente manera: la dirección virtual se divide en un número de página virtual (bits de mayor orden) y en un desplazamiento (bits de menor orden). Por ejemplo, con una direc- ción de 16 bits y un tamaño de página de 4 KB, los 4 bits superiores podrían especificar una de las 16 páginas virtuales y los 12 bits inferiores podrían entonces especificar el desplazamiento de by- tes (0 a 4095) dentro de la página seleccionada. Sin embargo, también es posible una división con 3, 5 u otro número de bits para la página. Las distintas divisiones implican diferentes tamaños de página. El número de página virtual se utiliza como índice en la tabla de páginas para buscar la entra- da para esa página virtual. En la entrada en la tabla de páginas, se encuentra el número de marco de página (si lo hay). El número del marco de página se adjunta al extremo de mayor orden del des- plazamiento, reemplazando el número de página virtual, para formar una dirección física que se pueda enviar a la memoria. Por ende, el propósito de la tabla de páginas es asociar páginas virtuales a los marcos de pági- na. Hablando en sentido matemático, la tabla de páginas es una función donde el número de página virtual es un argumento y el número de marco físico es un resultado. Utilizando el resultado de esta función, el campo de la página virtual en una dirección virtual se puede reemplazar por un campo de marco de página, formando así una dirección de memoria física. Estructura de una entrada en la tabla de páginas Ahora vamos a pasar de la estructura de las tablas de páginas en general a los detalles de una sola entrada en la tabla de páginas. La distribución exacta de una entrada depende en gran parte de la máquina, pero el tipo de información presente es aproximadamente el mismo de una máquina a otra. En la figura 3-11 proporcionamos un ejemplo de una entrada en la tabla de páginas. El tamaño va- ría de una computadora a otra, pero 32 bits es un tamaño común. El campo más importante es el número de marco de página. Después de todo, el objetivo de la asociación de páginas es mostrar este valor. Enseguida de este campo tenemos el bit de presente/ausente. Si este bit es 1, la entrada es válida y se puede utilizar. Si es 0, la página virtual a la que pertenece la entrada no se encuentra actualmente en la memoria. Al acceder a una entrada en la tabla de página con este bit puesto en 0 se produce un fallo de página. Uso de caché deshabilitado Modificada Presente/ausente Número de marco de página Referenciada Protección Figura 3-11. Una típica entrada en la tabla de páginas. 194 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 Los bits de protección indican qué tipo de acceso está permitido. En su forma más simple, es- te campo contiene 1 bit, con 0 para lectura/escritura y 1 para sólo lectura. Un arreglo más sofistica- do es tener 3 bits: uno para habilitar la lectura, otro para la escritura y el tercero para ejecutar la página. Los bits de modificada y referenciada llevan el registro del uso de páginas. Cuando se escri- be en una página, el hardware establece de manera automática el bit de modificada. Este bit es valioso cuando el sistema operativo decide reclamar un marco de página. Si la página en él ha sido modificada (es decir, está “sucia”), debe escribirse de vuelta en el disco. Si no se ha mo- dificado (es decir, está “limpia”) sólo se puede abandonar, debido a que la copia del disco es aun válida. A este bit se le conoce algunas veces como bit sucio, ya que refleja el estado de la página. El bit de referenciada se establece cada vez que una página es referenciada, ya sea para leer o escribir. Su función es ayudar al sistema operativo a elegir una página para desalojarla cuando ocu- rre un fallo de página. Las páginas que no se estén utilizando son mejores candidatos que las pági- nas que se están utilizando y este bit desempeña un importante papel en varios de los algoritmos de reemplazo de páginas que estudiaremos más adelante en este capítulo. Finalmente, el último bit permite deshabilitar el uso de caché para la página. Esta característi- ca es importante para las páginas que se asocian con los registros de dispositivos en vez de la me- moria. Si el sistema operativo está esperando en un ciclo de espera hermético a que cierto dispositivo de E/S responda a un comando que acaba de recibir, es esencial que el hardware siga obteniendo la palabra del dispositivo y no utilice una copia antigua en la caché. Con este bit, el uso de la caché se puede desactivar. Las máquinas que tienen un espacio de E/S separado y no utilizan E/S asociada a la memoria no necesitan este bit. Observe que la dirección del disco utilizado para guardar la página cuando no está en memo- ria no forma parte de la tabla de páginas. La razón es simple: la tabla de páginas sólo guarda la in- formación que el hardware necesita para traducir una dirección virtual en una dirección física. La información que necesita el sistema operativo para manejar los fallos de página se mantiene en ta- blas de software dentro del sistema operativo. El hardware no la necesita. Antes de analizar más aspectos de la implementación, vale la pena recalcar de nuevo que lo que la memoria virtual hace es crear una abstracción —el espacio de direcciones— que es una abstrac- ción de la memoria física, al igual que un proceso es una abstracción del procesador físico (CPU). Para implementar la memoria virtual, hay que descomponer el espacio de direcciones virtuales en páginas y asociar cada una a cierto marco de página de memoria física o dejarla (temporalmente) sin asociar. Por ende, este capítulo trata fundamentalmente de una abstracción creada por el siste- ma operativo y la forma en que se administra esa abstracción. 3.3.3 Aceleración de la paginación Acabamos de ver los fundamentos de la memoria virtual y la paginación. Ahora es tiempo de en- trar en más detalle acerca de las posibles implementaciones. En cualquier sistema de paginación hay que abordar dos cuestiones principales: SECCIÓN 3.3 MEMORIA VIRTUAL 195 1. La asociación de una dirección virtual a una dirección física debe ser rápida. 2. Si el espacio de direcciones virtuales es grande, la tabla de páginas será grande. El primer punto es una consecuencia del hecho de que la asociación virtual-a-física debe reali- zarse en cada referencia de memoria. Todas las instrucciones deben provenir finalmente de la me- moria y muchas de ellas hacen referencias a operandos en memoria también. En consecuencia, es necesario hacer una, dos o algunas veces más referencias a la tabla de páginas por instrucción. Si la ejecución de una instrucción tarda, por ejemplo 1 nseg, la búsqueda en la tabla de páginas debe realizarse en menos de 0.2 nseg para evitar que la asociación se convierta en un cuello de botella importante. El segundo punto se deriva del hecho de que todas las computadoras modernas utilizan direc- ciones virtuales de por lo menos 32 bits, donde 64 bits se vuelven cada vez más comunes. Por de- cir, con un tamaño de página de 4 KB, un espacio de direcciones de 32 bits tiene 1 millón de páginas y un espacio de direcciones de 64 bits tiene más de las que desearíamos contemplar. Con 1 millón de páginas en el espacio de direcciones virtual, la tabla de páginas debe tener 1 millón de entradas. Y recuerde que cada proceso necesita su propia tabla de páginas (debido a que tiene su propio es- pacio de direcciones virtuales). La necesidad de una asociación de páginas extensa y rápida es una restricción considerable en cuanto a la manera en que se construyen las computadoras. El diseño más simple (por lo menos en concepto) es tener una sola tabla de páginas que consista en un arreglo de registros de hardwa- re veloces, con una entrada para cada página virtual, indexada por número de página virtual, como se muestra en la figura 3-10. Cuando se inicia un proceso, el sistema operativo carga los registros con la tabla de páginas del proceso, tomada de una copia que se mantiene en la memoria principal. Durante la ejecución del proceso no se necesitan más referencias a memoria para la tabla de pági- nas. Las ventajas de este método son que es simple y no requiere referencias a memoria durante la asociación. Una desventaja es que es extremadamente costoso que la tabla de páginas sea extensa; otra es que tener que cargar la tabla de páginas completa en cada conmutación de contexto ve afec- tado el rendimiento. En el otro extremo, toda la tabla de páginas puede estar en la memoria principal. Así, todo lo que el hardware necesita es un solo registro que apunte al inicio de la tabla de páginas. Este diseño permite cambiar la asociación de direcciones virtuales a direcciones físicas al momento de una con- mutación de contexto con sólo recargar un registro. Desde luego, tiene la desventaja de requerir una o más referencias a memoria para leer las entradas en la tabla de páginas durante la ejecución de cada instrucción, con lo cual se hace muy lenta. Búferes de traducción adelantada Ahora veamos esquemas implementados ampliamente para acelerar la paginación y manejar espa- cios de direcciones virtuales extensos, empezando con la aceleración de la paginación. El punto ini- cial de la mayor parte de las técnicas de optimización es que la tabla de páginas está en la memoria. Potencialmente, este diseño tiene un enorme impacto sobre el rendimiento. Por ejemplo, considere una instrucción de 1 byte que copia un registro a otro. A falta de paginación, esta instrucción hace 196 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 sólo una referencia a memoria para obtener la instrucción. Con la paginación se requiere al menos una referencia adicional a memoria para acceder a la tabla de páginas. Como la velocidad de ejecu- ción está comúnmente limitada por la proporción a la que la CPU puede obtener instrucciones y da- tos de la memoria, al tener que hacer dos referencias a memoria por cada una de ellas se reduce el rendimiento a la mitad. Bajo estas condiciones, nadie utilizaría la paginación. Los diseñadores de computadoras han sabido acerca de este problema durante años y han idea- do una solución que está basada en la observación de que la mayor parte de los programas tienden a hacer un gran número de referencias a un pequeño número de páginas y no viceversa. Por ende, sólo se lee con mucha frecuencia una pequeña fracción de las entradas en la tabla de páginas; el res- to se utiliza muy pocas veces. La solución que se ha ideado es equipar a las computadoras con un pequeño dispositivo de hard- ware para asociar direcciones virtuales a direcciones físicas sin pasar por la tabla de páginas. El dis- positivo, llamado TLB (Translation Lookaside Buffer, Búfer de traducción adelantada) o algunas veces memoria asociativa, se ilustra en la figura 3-12. Por lo general se encuentra dentro de la MMU y consiste en un pequeño número de entradas, ocho en este ejemplo, pero raras veces más de 64. Ca- da entrada contiene información acerca de una página, incluyendo el número de página virtual, un bit que se establece cuando se modifica la página, el código de protección (permisos de lectura/es- critura/ejecución) y el marco de página físico en el que se encuentra la página. Estos campos tienen una correspondencia de uno a uno con los campos en la tabla de páginas, excepto por el número de página virtual, que no se necesita en la tabla de páginas. Otro bit indica si la entrada es válida (es decir, si está en uso) o no. Marco de Válida Página virtual Modificada Protección página Figura 3-12. Un TLB para acelerar la paginación. Un ejemplo que podría generar el TLB de la figura 3-12 es un proceso en un ciclo que abarque las páginas virtuales 19, 20 y 21, de manera que estas entradas en el TLB tengan códigos de pro- tección para lectura y ejecución. Los datos principales que se están utilizando (por decir, un arreglo que se esté procesando) se encuentran en las páginas 129 y 130. La página 140 contiene los índices utilizados en los cálculos del arreglo. Al final, la pila está en las páginas 860 y 861. Ahora veamos cómo funciona el TLB. Cuando se presenta una dirección virtual a la MMU pa- ra que la traduzca, el hardware primero comprueba si su número de página virtual está presente en SECCIÓN 3.3 MEMORIA VIRTUAL 197 el TLB al compararla con todas las entradas en forma simultánea (es decir, en paralelo). Si se en- cuentra una coincidencia válida y el acceso no viola los bits de protección, el marco de página se toma directamente del TLB, sin pasar por la tabla de páginas. Si el número de página virtual está presente en el TLB, pero la instrucción está tratando de escribir en una página de sólo lectura, se genera un fallo por protección. El caso interesante es lo que ocurre cuando el número de página virtual no está en el TLB. La MMU detecta que no está y realiza una búsqueda ordinaria en la tabla de páginas. Después desalo- ja una de las entradas del TLB y la reemplaza con la entrada en la tabla de páginas que acaba de buscar. De esta forma, si esa página se utiliza pronto otra vez, la segunda vez se producirá un acier- to en el TLB en vez de un fracaso. Cuando se purga una entrada del TLB, el bit modificado se co- pia de vuelta a la entrada en la tabla de páginas en memoria. Los otros valores ya están ahí, excepto el bit de referencia. Cuando el TLB se carga de la tabla de páginas, todos los campos se toman de la memoria. Administración del TLB mediante software Hasta ahora hemos supuesto que toda máquina con memoria virtual paginada tiene tablas de pági- nas reconocidas por el hardware, más un TLB. En este diseño, la administración y el manejo de fa- llas del TLB se realiza por completo mediante el hardware de la MMU. Las traps, o trampas, para el sistema operativo ocurren sólo cuando una página no se encuentra en memoria. En el pasado, esta suposición era correcta. Sin embargo, muchas máquinas RISC modernas (in- cluyendo SPARC, MIPS y HP PA) hacen casi toda esta administración de páginas mediante softwa- re. En estas máquinas, las entradas del TLB se cargan de manera explícita mediante el sistema operativo. Cuando no se encuentra una coincidencia en el TLB, en vez de que la MMU vaya a las tablas de páginas para buscar y obtener la referencia a la página que se necesita, sólo genera un fa- llo del TLB y pasa el problema al sistema operativo. El sistema debe buscar la página, eliminar una entrada del TLB, introducir la nueva página y reiniciar la instrucción que originó el fallo. Y, desde luego, todo esto se debe realizar en unas cuantas instrucciones, ya que los fallos del TLB ocurren con mucha mayor frecuencia que los fallos de página. De manera sorprendente, si el TLB es razonablemente grande (por ejemplo, de 64 entradas) para reducir la proporción de fallos, la administración del TLB mediante software resulta tener una eficien- cia aceptable. El beneficio principal aquí es una MMU mucho más simple, lo cual libera una cantidad considerable de área en el chip de CPU para cachés y otras características que pueden mejorar el ren- dimiento. Uhlig y colaboradores (1994) describen la administración del TLB mediante software. Se han desarrollado varias estrategias para mejorar el rendimiento en equipos que realizan la ad- ministración del TLB mediante software. Un método se enfoca en reducir los fallos del TLB y el cos- to de un fallo del TLB cuando llega a ocurrir (Bala y colaboradores, 1994). Para reducir los fallos del TLB, algunas veces el sistema operativo averigua de modo “intuitivo” cuáles páginas tienen más pro- babilidad de ser utilizadas a continuación y precarga entradas para ellas en el TLB. Por ejemplo, cuan- do un proceso cliente envía un mensaje a un proceso servidor en el mismo equipo, es muy probable que el servidor tenga que ejecutarse pronto. Sabiendo esto al tiempo que procesa el trap para realizar la ope- ración send, el sistema también puede comprobar en dónde están las páginas de código, datos y pila del servidor, asociándolas antes de que tengan la oportunidad de producir fallos del TLB. 198 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 La forma normal de procesar un fallo del TLB, ya sea en hardware o en software, es ir a la ta- bla de páginas y realizar las operaciones de indexado para localizar la página referenciada. El pro- blema al realizar esta búsqueda en software es que las páginas que contienen la tabla de páginas tal vez no estén en el TLB, lo cual producirá fallos adicionales en el TLB durante el procesamiento. Estos fallos se pueden reducir al mantener una caché grande en software (por ejemplo, de 4 KB) de entradas en el TLB en una ubicación fija, cuya página siempre se mantenga en el TLB. Al compro- bar primero la caché de software, el sistema operativo puede reducir de manera substancial los fa- llos del TLB. Cuando se utiliza la administración del TLB mediante software, es esencial comprender la di- ferencia entre los dos tipos de fallos. Un fallo suave ocurre cuando la página referenciada no está en el TLB, sino en memoria. Todo lo que se necesita aquí es que el TLB se actualice. No se nece- sita E/S de disco. Por lo general, un fallo suave requiere de 10 a 20 instrucciones de máquina y se puede completar en unos cuantos nanosegundos. Por el contrario, un fallo duro ocurre cuando la misma página no está en memoria (y desde luego, tampoco en el TLB). Se requiere un acceso al disco para traer la página, lo cual tarda varios milisegundos. Un fallo duro es en definitiva un mi- llón de veces más lento que un fallo suave. 3.3.4 Tablas de páginas para memorias extensas Los TLBs se pueden utilizar para acelerar las traducciones de direcciones virtuales a direcciones fí- sicas sobre el esquema original de la tabla de páginas en memoria. Pero ése no es el único proble- ma que debemos combatir. Otro problema es cómo lidiar con espacios de direcciones virtuales muy extensos. A continuación veremos dos maneras de hacerlo. Tablas de páginas multinivel Como primer método, considere el uso de una tabla de páginas multinivel. En la figura 3-13 se muestra un ejemplo simple. En la figura 3-13(a) tenemos una dirección virtual de 32 bits que se par- ticiona en un campo TP1 de 10 bits, un campo TP2 de 10 bits y un campo Desplazamiento de 12 bits. Como los desplazamientos son de 12 bits, las páginas son de 4 KB y hay un total de 220. El secreto del método de la tabla de páginas multinivel es evitar mantenerlas en memoria todo el tiempo, y en especial, aquellas que no se necesitan. Por ejemplo, suponga que un proceso nece- sita 12 megabytes: los 4 megabytes inferiores de memoria para el texto del programa, lo siguientes 4 megabytes para datos y los 4 megabytes superiores para la pila. Entre la parte superior de los da- tos y la parte inferior de la pila hay un hueco gigantesco que no se utiliza. En la figura 3-13(b) podemos ver cómo funciona la tabla de página de dos niveles en este ejem- plo. A la izquierda tenemos la tabla de páginas de nivel superior, con 1024 entradas, que correspon- den al campo TP1 de 10 bits. Cuando se presenta una dirección virtual a la MMU, primero extrae el campo TP1 y utiliza este valor como índice en la tabla de páginas de nivel superior. Cada una de estas 1024 entradas representa 4 M, debido a que todo el espacio de direcciones virtuales de 4 gi- gabytes (es decir, de 32 bits) se ha dividido en trozos de 4096 bytes. SECCIÓN 3.3 MEMORIA VIRTUAL 199 Tablas de páginas de segundo nivel Tabla de páginas para los 4M superiores de la memoria Tabla de páginas de nivel superior 1023 6 Bits 10 10 12 5 TP1 TP2 Desplaza- miento 4 3 (a) 2 1 0 1023 6 5 4 3 A las páginas 2 1 0 (b) Figura 3-13. (a) Una dirección de 32 bits con dos campos de tablas de páginas. (b) Tablas de páginas de dos niveles. La entrada que se localiza al indexar en la tabla de páginas de nivel superior produce la dirección (o número de marco de página) de una tabla de páginas de segundo nivel. La entrada 0 de la tabla de páginas de nivel superior apunta a la tabla de páginas para el texto del programa, la entrada 1 apunta a la tabla de páginas para los datos y la entrada 1023 apunta a la tabla de páginas para la pila. Las otras entradas (sombreadas) no se utilizan. Ahora el campo TP2 se utiliza como índice en la tabla de pági- nas de segundo nivel seleccionada para buscar el número de marco de página para esta página en sí. Como ejemplo, considere la dirección virtual de 32 bits 0x00403004 (4,206,596 decimal), que se encuentra 12,292 bytes dentro de los datos. Esta dirección virtual corresponde a TP1 1, 200 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 TP2 2 y Desplazamiento 4. La MMU utiliza primero a TP1 para indexar en la tabla de pági- nas de nivel superior y obtener la entrada 1, que corresponde a las direcciones de 4M a 8M. Des- pués utiliza PT2 para indexar en la tabla de páginas de segundo nivel que acaba de encontrar y extrae la entrada 3, que corresponde a las direcciones de 12288 a 16383 dentro de su trozo de 4M (es decir, las direcciones absolutas de 4,206,592 a 4,210,687). Esta entrada contiene el número de marco de la página que contiene la dirección virtual 0x00403004. Si esa página no está en la me- moria, el bit de presente/ausente en la entrada de la tabla de páginas será cero, con lo cual se pro- ducirá un fallo de página. Si la página está en la memoria, el número del marco de página que se obtiene de la tabla de páginas de segundo nivel se combina con el desplazamiento (4) para construir la dirección física. Esta dirección se coloca en el bus y se envía a la memoria. Lo interesante acerca de la figura 3-13 es que, aunque el espacio de direcciones contiene más de un millón de páginas, en realidad sólo cuatro tablas de páginas son requeridas: la tabla de nivel superior y las tablas de segundo nivel de 0 a 4M (para el texto del programa), de 4M a 8M (para los datos) y los 4M superiores (para la pila). Los bits de presente/ausente en 1021 entradas de la tabla de páginas de nivel superior están en 0 y obligan a que se produzca un fallo de página si se tratan de utilizar alguna vez. En caso de que esto ocurra, el sistema operativo observará que el proceso es- tá tratando de referenciar memoria que no debe y tomará la acción apropiada, como enviar una se- ñal o eliminarlo. En este ejemplo hemos elegido números redondos para los diversos tamaños y que TP1 sea igual a TP2, pero en la práctica también es posible elegir otros valores. El sistema de tablas de páginas de dos niveles de la figura 3-13 se puede expandir a tres, cua- tro o más niveles. Entre más niveles se obtiene una mayor flexibilidad, pero es improbable que la complejidad adicional sea de utilidad por encima de tres niveles. Tablas de páginas invertidas Para los espacios de direcciones virtuales de 32 bits, la tabla de páginas multinivel funciona bastan- te bien. Sin embargo, a medida que las computadoras de 64 bits se hacen más comunes, la situación cambia de manera drástica. Si el espacio de direcciones es de 264 bytes, con páginas de 4 KB, nece- sitamos una tabla de páginas con 252 entradas. Si cada entrada es de 8 bytes, la tabla es de más de 30 millones de gigabyes (30 PB). Ocupar 30 millones de gigabytes sólo para la tabla de páginas no es una buena idea por ahora y probablemente tampoco lo sea para el próximo año. En consecuencia, se necesita una solución diferente para los espacios de direcciones virtuales paginados de 64 bits. Una de esas soluciones es la tabla de páginas invertida. En este diseño hay una entrada por cada marco de página en la memoria real, en vez de tener una entrada por página de espacio de di- recciones virtuales. Por ejemplo, con direcciones virtuales de 64 bits, una página de 4 KB y 1 GB de RAM, una tabla de páginas invertida sólo requiere 262,144 entradas. La entrada lleva el regis- tro de quién (proceso, página virtual) se encuentra en el marco de página. Aunque las tablas de página invertidas ahorran grandes cantidades de espacio, al menos cuan- do el espacio de direcciones virtuales es mucho mayor que la memoria física, tienen una seria des- ventaja: la traducción de dirección virtual a dirección física se hace mucho más difícil. Cuando el proceso n hace referencia a la página virtual p, el hardware ya no puede buscar la página física usan- do p como índice en la tabla de páginas. En vez de ello, debe buscar una entrada (n, p) en toda la SECCIÓN 3.4 ALGORITMOS DE REEMPLAZO DE PÁGINAS 201 tabla de páginas invertida. Lo que es peor: esta búsqueda se debe realizar en cada referencia a me- moria, no sólo en los fallos de página. Buscar en una tabla de 256 K en cada referencia a memoria no es la manera de hacer que la máquina sea deslumbrantemente rápida. La forma de salir de este dilema es utilizar el TLB. Si el TLB puede contener todas las páginas de uso frecuente, la traducción puede ocurrir con igual rapidez que con las tablas de páginas regu- lares. Sin embargo, en un fallo de TLB la tabla de páginas invertida tiene que buscarse mediante software. Una manera factible de realizar esta búsqueda es tener una tabla de hash arreglada según el hash de la dirección virtual. Todas las páginas virtuales que se encuentren en memoria y tengan el mismo valor de hash se encadenan en conjunto, como se muestra en la figura 3-14. Si la tabla de hash tiene tantas ranuras como las páginas físicas de la máquina, la cadena promedio tendrá sólo una entrada, con lo cual se acelera de manera considerable la asociación. Una vez que se ha encon- trado el número de marco de página, se introduce el nuevo par (virtual, física) en el TLB. Tabla de páginas tradicional con una entrada para cada una de las 252 páginas 252 -1 La memoria física de 1 GB tiene 218 marcos de página de 4 KB Tabla de hash 218 -1 218 -1 0 0 0 Indexada por Indexada por página virtual hash en página Página Marco virtual virtual de página Figura 3-14. Comparación de una tabla de páginas tradicional con una tabla de pági- nas invertida. Las tablas de páginas invertidas son comunes en las máquinas de 64 bits ya que incluso con un tamaño de página muy grande, el número de entradas en la tabla de páginas es enorme. Por ejem- plo, con páginas de 4 MB y direcciones virtuales de 64 bits, se necesitan 242 entradas en la tabla de páginas. Otros métodos para manejar memorias virtuales extensas se pueden encontrar en Talluri y colaboradores (1995). 3.4 ALGORITMOS DE REEMPLAZO DE PÁGINAS Cuando ocurre un fallo de página, el sistema operativo tiene que elegir una página para desalojarla (eliminarla de memoria) y hacer espacio para la página entrante. Si la página a eliminar se modificó 202 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 mientras estaba en memoria, debe volver a escribirse en el disco para actualizar la copia del mismo. No obstante, si la página no se ha modificado (por ejemplo, si contiene el texto del programa), la copia ya está actualizada y no se necesita rescribir. La página que se va a leer sólo sobrescribe en la página que se va a desalojar. Aunque sería posible elegir una página al azar para desalojarla en cada fallo de página, el ren- dimiento del sistema es mucho mayor si se selecciona una página que no sea de uso frecuente. Si se elimina una página de uso frecuente, tal vez tenga que traerse de vuelta rápidamente, lo cual pro- duce una sobrecarga adicional. Se ha realizado mucho trabajo, tanto teórico como experimental en el tema de los algoritmos de reemplazo de páginas. A continuación describiremos algunos de los al- goritmos más importantes. Vale la pena observar que el problema del “reemplazo de páginas” ocurre también en otras áreas del diseño computacional. Por ejemplo, la mayoría de las computadoras tienen una o más me- morias cachés que consisten en bloques de memoria de 32 bytes o 64 bytes de uso reciente. Cuan- do la caché está llena, hay que elegir cierto bloque para eliminarlo. Este problema es precisamente el mismo que la reemplazo de páginas, sólo que en una escala de tiempo menor (tiene que realizar- se en unos cuantos nanosegundos, no milisegundos como en el reemplazo de páginas). La razón de tener una menor escala de tiempo es que los fallos de bloques de caché se satisfacen desde la me- moria principal, que no tiene tiempo de búsqueda ni latencia rotacional. Un segundo ejemplo es en un servidor Web. El servidor puede mantener cierto número de páginas Web de uso muy frecuente en su memoria caché. Sin embargo, cuando la memoria caché está llena y se hace referencia a una nueva página, hay que decidir cuál página Web se debe desalojar. Las consi- deraciones son similares a las de las páginas de memoria virtual, excepto por el hecho de que las pági- nas Web nunca se modifican en la caché, por lo cual siempre hay una copia fresca “en el disco”. En un sistema de memoria virtual, las páginas en memoria principal pueden estar sucias o limpias. En todos los algoritmos de reemplazo de páginas que analizaremos a continuación, surge cier- ta cuestión: al desalojar una página de la memoria, ¿tiene que ser una de las propias páginas del pro- ceso fallido o puede ser una página que pertenezca a otro proceso? En el primer caso, estamos limitando en efecto cada proceso a un número fijo de páginas; en el segundo caso no. Ambas son posibilidades. En la sección 3-5.1 volveremos a ver este punto. 3.4.1 El algoritmo de reemplazo de páginas óptimo El mejor algoritmo de reemplazo de páginas posible es fácil de describir, pero imposible de imple- mentar: al momento en que ocurre un fallo de página, hay cierto conjunto de páginas en memoria y una de éstas se referenciará en la siguiente instrucción (la página que contiene la instrucción); otras páginas tal vez no se referencien sino hasta 10, 100 o tal vez 1000 instrucciones después. Ca- da página se puede etiquetar con el número de instrucciones que se ejecutarán antes de que se ha- ga referencia por primera vez a esa página. El algoritmo óptimo de reemplazo de páginas establece que la página con la etiqueta más alta debe eliminarse. Si una página no se va a utilizar durante 8 millones de instrucciones y otra no se va a utilizar durante 6 millones de instrucciones, al eliminar la primera se enviará el fallo de pági- na que la obtendrá de vuelta lo más lejos posible en el futuro. Al igual que las personas, las com- putadoras tratan de posponer los eventos indeseables el mayor tiempo posible. SECCIÓN 3.4 ALGORITMOS DE REEMPLAZO DE PÁGINAS 203 El único problema con este algoritmo es que no se puede realizar. Al momento del fallo de pá- gina, el sistema operativo no tiene forma de saber cuándo será la próxima referencia a cada una de las páginas (vimos una situación similar antes, con el algoritmo de planificación del trabajo más corto primero: ¿cómo puede saber el sistema cuál trabajo es más corto?). Aún así, al ejecutar un pro- grama en un simulador y llevar la cuenta de todas las referencias a páginas, es posible implemen- tar un algoritmo óptimo de reemplazo de página en la segunda corrida, al utilizar la información de referencia de páginas recolectada durante la primera corrida. De esta manera, se puede comparar el rendimiento de los algoritmos realizables con el mejor posible. Si un sistema operativo logra un rendimiento de, por ejemplo, sólo 1 por ciento peor que el algoritmo óptimo, el esfuerzo invertido en buscar un mejor algoritmo producirá cuando mucho una mejora del 1 por ciento. Para evitar cualquier posible confusión, hay que aclarar que este registro de referencias de pá- ginas se refiere sólo al programa que se acaba de medir y sólo con una entrada específica. Por lo tanto, el algoritmo de reemplazo de páginas que se derive de esto es específico para ese programa y esos datos de entrada. Aunque este método es útil para evaluar los algoritmos de reemplazo de pá- ginas, no es útil en sistemas prácticos. A continuación estudiaremos algoritmos que son útiles en sistemas reales. 3.4.2 El algoritmo de reemplazo de páginas: no usadas recientemente Para permitir que el sistema operativo recolecte estadísticas útiles sobre el uso de páginas, la ma- yor parte de las computadoras con memoria virtual tienen dos bits de estado asociados a cada pági- na. R se establece cada vez que se hace referencia a la página (lectura o escritura); M se establece cuando se escribe en la página (es decir, se modifica). Los bits están contenidos en cada entrada de la tabla de páginas, como se muestra en la figura 3-11. Es importante tener en cuenta que estos bits se deben actualizar en cada referencia a la memoria, por lo que es imprescindible que se establez- can mediante el hardware. Una vez que se establece un bit en 1, permanece así hasta que el siste- ma operativo lo restablece. Si el hardware no tiene estos bits, pueden simularse de la siguiente forma. Cuando se inicia un proceso, todas sus entradas en la tabla de páginas se marcan como que no están en memoria. Tan pronto como se haga referencia a una página, ocurrirá un fallo de página. Entonces, el sistema ope- rativo establece el bit R (en sus tablas internas), cambia la entrada en la tabla de páginas para que apunte a la página correcta, con modo de SÓLO LECTURA, y reinicia la instrucción. Si la página se modifica después, ocurrirá otro fallo de página que permite al sistema operativo establecer el bit M y cambiar el modo de la página a LECTURA/ESCRITURA. Los bits R y M se pueden utilizar para construir un algoritmo simple de paginación de la si- guiente manera. Cuando se inicia un proceso, ambos bits de página para todas sus páginas se esta- blecen en 0 mediante el sistema operativo. El bit R se borra en forma periódica (en cada interrupción de reloj) para diferenciar las páginas a las que no se ha hecho referencia recientemente de las que si se han referenciado. Cuando ocurre un fallo de página, el sistema operativo inspecciona todas las páginas y las di- vide en 4 categorías con base en los valores actuales de sus bits R y M: 204 ADMINISTRACIÓN DE MEMORIA CAPÍTULO 3 Clase 0: no ha sido referenciada, no ha sido modificada. Clase 1: no ha sido referenciada, ha sido modificada. Clase 2: ha sido referenciada, no ha sido modificada. Clase 3: ha sido referenciada, ha sido modificada. Aunque las páginas de la clase 1 parecen a primera instancia imposibles, ocurren cuando una interrup- ción de reloj borra el bit R de una página de la clase 3. Las interrupciones de reloj no borran el bit M debido a que esta información se necesita para saber si la página se ha vuelto a escribir en el disco o no. Al borrar R pero no M se obtiene una página de clase 1. El algoritmo NRU (Not Recently Used, No usada recientemente) elimina una página al azar de la clase de menor numeración que no esté vacía. En este algoritmo está implícita la idea de que es mejor eliminar una página modificada a la que no se haya hecho referencia en al menos un pul- so de reloj (por lo general, unos 20 mseg) que una página limpia de uso frecuente. La principal atracción del NRU es que es fácil de comprender, moderadamente eficiente de implementar y pro- porciona un rendimiento que, aunque no es óptimo, puede ser adecuado. 3.4.3 El algoritmo de reemplazo de páginas: Primera en entrar, primera en salir (FIFO) Otro algoritmo de paginación con baja sobrecarga es el de Primera en entrar, primera en salir (First-In, First-Out, FIFO). Para ilustrar cómo funciona, considere un supermercado con suficien- tes repisas como para mostrar exactamente k productos distintos. Un día, cierta empresa introduce un nuevo alimento de conveniencia: yogurt orgánico instantáneo liofilizado que se puede reconsti- tuir en un horno de microondas. Es un éxito inmediato, por lo que nuestro supermercado finito se tiene que deshacer de un producto antiguo para tenerlo en existencia. Una posibilidad es buscar el producto que el supermercado haya tenido en existencia por más tiempo (por ejemplo, algo que se empezó a vender hace 120 años) y deshacerse de él por la razón de que nadie está interesado ya. En efecto, el supermercado mantiene una lista ligada de todos los productos que vende actualmente en el orden en el que se introdujeron. El nuevo pasa a la parte fi- nal de la lista; el que está al frente de la lista se elimina. Como un algoritmo de reemplazo de páginas, se aplica la misma idea. El sistema operativo mantiene una lista de todas las páginas actualmente en memoria, en donde la llegada más reciente está en la parte final y la menos reciente en la parte frontal. En un fallo de página, se elimina la pá- gina que está en la parte frontal y la nueva página se agrega a la parte final de la lista. Cuando se aplica en las tiendas, FIFO podría eliminar la gomina para el bigote, pero también podría eliminar harina, sal o mantequilla. Cuando se aplica a las computadoras, surge el mismo problema. Por esta razón es raro que se utilice FIFO en su forma pura. 3.4.4 El algoritmo de reemplazo de páginas: segunda oportunidad Una modificación simple al algoritmo FIFO que evita el problema de descartar una página de uso frecuente es inspeccionar el bit R de la página más antigua. Si es 0, la página es antigua y no se ha SECCIÓN 3.4 ALGORITMOS DE REEMPLAZO DE PÁGINAS 205 utilizado, por lo que se sustituye de inmediato. Si el bit R es 1, el bit se borra

Sistemas Operativos: Memoria y Archivos PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue