En sistemas operativos de computadoras, los sistemas de paginación de memoria dividen los programas en pequeñas partes o páginas. Del mismo modo, la memoria es dividida en trozos del mismo tamaño que las páginas llamados marcos de página. De esta forma, la cantidad de memoria desperdiciada por un proceso es el final de su última página, lo que minimiza la fragmentación interna y evita la externa.
En un momento cualquiera, la memoria se encuentra ocupada con páginas de diferentes procesos, mientras que algunos marcos están disponibles para su uso. El sistema operativo mantiene una lista de estos últimos marcos, y una tabla por cada proceso, donde consta en qué marco se encuentra cada página del proceso. De esta forma, las páginas de un proceso pueden no estar contiguamente ubicadas en memoria, y pueden intercalarse con las páginas de otros procesos.
En la tabla de páginas de un proceso, se encuentra la ubicación del marco que contiene a cada una de sus páginas. Las direcciones lógicas ahora se forman como un número de página y de un desplazamiento dentro de esa página. El número de página es usado como un índice dentro de la tabla de páginas, y una vez obtenida la dirección real del marco de memoria, se utiliza el desplazamiento para componer la dirección real. Este proceso es realizado en el hardware del computador.
De esta forma, cuando un proceso es cargado en memoria, se cargan todas sus páginas en marcos libres y se completa su tabla de páginas.
Paginación en memoria virtual
El único inconveniente del sistema de paginación pura es que todas las páginas de un proceso deben estar en memoria para que pueda ejecutar. Esto hace que si los programas son de tamaño considerable, no puedan cargarse muchos a la vez, disminuyendo el grado de multiprogramación del sistema. Para evitar esto, y aprovechando el principio de cercanía de referencias donde se puede esperar que un programa trabaje con un conjunto cercano de referencias a memoria (es decir con un conjunto residente más pequeño que el total de sus páginas), se permitirá que algunas páginas del proceso sean guardadas en un espacio de intercambio (en memoria secundaria) mientras no se necesiten.
Cuando la paginación se utiliza junto con memoria virtual, el sistema operativo mantiene además el conocimiento sobre qué páginas están en memoria principal y cuáles no, usando la tabla de paginación. Si una página buscada está marcada como no disponible (tal vez porque no está presente en la memoria física, pero sí en el área de intercambio), cuando la CPU intenta referenciar una dirección de memoria en esa página, la MMU responde levantando una excepción (comúnmente llamada fallo de página). Si la página se encuentra en el área de intercambio, se salta a una rutina que invoca una operación llamada un intercambio de página, para traer a memoria principal la página requerida. La operación lleva varios pasos. Primero se selecciona una página en memoria, por ejemplo una que no haya sido usada recientemente (para más detalles ver algoritmos de reemplazo de páginas). Si la página fue modificada, se escribe la misma en el espacio de intercambio. El siguiente paso en el proceso es leer la información en la página necesitada desde el espacio de intercambio). Cuando esto sucede, las tablas para traducción de direcciones virtuales a reales son actualizadas para reflejar los contenidos de la memoria física. Entonces el intercambio de página sale, y el programa que usó la dirección que causó la excepción es vuelto a ejecutar desde el punto en que se dio la misma y continúa como si nada hubiera pasado. También es posible que: una dirección virtual es marcada como no disponible, porque no fue localizada previamente. En estos casos, una página de memoria es localizada y llenada con ceros, la tabla de paginación es modificada para mostrar los cambios y el programa se reinicia como en el otro caso.
viernes, 20 de noviembre de 2009
4.3.1 Paginación de memoria virtual
En sistemas operativos de computadoras, los sistemas de paginación de memoria dividen los programas en pequeñas partes o páginas. Del mismo modo, la memoria es dividida en trozos del mismo tamaño que las páginas llamados marcos de página. De esta forma, la cantidad de memoria desperdiciada por un proceso es el final de su última página, lo que minimiza la fragmentación interna y evita la externa.
En un momento cualquiera, la memoria se encuentra ocupada con páginas de diferentes procesos, mientras que algunos marcos están disponibles para su uso. El sistema operativo mantiene una lista de estos últimos marcos, y una tabla por cada proceso, donde consta en qué marco se encuentra cada página del proceso. De esta forma, las páginas de un proceso pueden no estar contiguamente ubicadas en memoria, y pueden intercalarse con las páginas de otros procesos.
En la tabla de páginas de un proceso, se encuentra la ubicación del marco que contiene a cada una de sus páginas. Las direcciones lógicas ahora se forman como un número de página y de un desplazamiento dentro de esa página. El número de página es usado como un índice dentro de la tabla de páginas, y una vez obtenida la dirección real del marco de memoria, se utiliza el desplazamiento para componer la dirección real. Este proceso es realizado en el hardware del computador.
De esta forma, cuando un proceso es cargado en memoria, se cargan todas sus páginas en marcos libres y se completa su tabla de páginas.
Paginación en memoria virtual
El único inconveniente del sistema de paginación pura es que todas las páginas de un proceso deben estar en memoria para que pueda ejecutar. Esto hace que si los programas son de tamaño considerable, no puedan cargarse muchos a la vez, disminuyendo el grado de multiprogramación del sistema. Para evitar esto, y aprovechando el principio de cercanía de referencias donde se puede esperar que un programa trabaje con un conjunto cercano de referencias a memoria (es decir con un conjunto residente más pequeño que el total de sus páginas), se permitirá que algunas páginas del proceso sean guardadas en un espacio de intercambio (en memoria secundaria) mientras no se necesiten.
Cuando la paginación se utiliza junto con memoria virtual, el sistema operativo mantiene además el conocimiento sobre qué páginas están en memoria principal y cuáles no, usando la tabla de paginación. Si una página buscada está marcada como no disponible (tal vez porque no está presente en la memoria física, pero sí en el área de intercambio), cuando la CPU intenta referenciar una dirección de memoria en esa página, la MMU responde levantando una excepción (comúnmente llamada fallo de página). Si la página se encuentra en el área de intercambio, se salta a una rutina que invoca una operación llamada un intercambio de página, para traer a memoria principal la página requerida. La operación lleva varios pasos. Primero se selecciona una página en memoria, por ejemplo una que no haya sido usada recientemente (para más detalles ver algoritmos de reemplazo de páginas). Si la página fue modificada, se escribe la misma en el espacio de intercambio. El siguiente paso en el proceso es leer la información en la página necesitada desde el espacio de intercambio). Cuando esto sucede, las tablas para traducción de direcciones virtuales a reales son actualizadas para reflejar los contenidos de la memoria física. Entonces el intercambio de página sale, y el programa que usó la dirección que causó la excepción es vuelto a ejecutar desde el punto en que se dio la misma y continúa como si nada hubiera pasado. También es posible que: una dirección virtual es marcada como no disponible, porque no fue localizada previamente. En estos casos, una página de memoria es localizada y llenada con ceros, la tabla de paginación es modificada para mostrar los cambios y el programa se reinicia como en el otro caso.
En un momento cualquiera, la memoria se encuentra ocupada con páginas de diferentes procesos, mientras que algunos marcos están disponibles para su uso. El sistema operativo mantiene una lista de estos últimos marcos, y una tabla por cada proceso, donde consta en qué marco se encuentra cada página del proceso. De esta forma, las páginas de un proceso pueden no estar contiguamente ubicadas en memoria, y pueden intercalarse con las páginas de otros procesos.
En la tabla de páginas de un proceso, se encuentra la ubicación del marco que contiene a cada una de sus páginas. Las direcciones lógicas ahora se forman como un número de página y de un desplazamiento dentro de esa página. El número de página es usado como un índice dentro de la tabla de páginas, y una vez obtenida la dirección real del marco de memoria, se utiliza el desplazamiento para componer la dirección real. Este proceso es realizado en el hardware del computador.
De esta forma, cuando un proceso es cargado en memoria, se cargan todas sus páginas en marcos libres y se completa su tabla de páginas.
Paginación en memoria virtual
El único inconveniente del sistema de paginación pura es que todas las páginas de un proceso deben estar en memoria para que pueda ejecutar. Esto hace que si los programas son de tamaño considerable, no puedan cargarse muchos a la vez, disminuyendo el grado de multiprogramación del sistema. Para evitar esto, y aprovechando el principio de cercanía de referencias donde se puede esperar que un programa trabaje con un conjunto cercano de referencias a memoria (es decir con un conjunto residente más pequeño que el total de sus páginas), se permitirá que algunas páginas del proceso sean guardadas en un espacio de intercambio (en memoria secundaria) mientras no se necesiten.
Cuando la paginación se utiliza junto con memoria virtual, el sistema operativo mantiene además el conocimiento sobre qué páginas están en memoria principal y cuáles no, usando la tabla de paginación. Si una página buscada está marcada como no disponible (tal vez porque no está presente en la memoria física, pero sí en el área de intercambio), cuando la CPU intenta referenciar una dirección de memoria en esa página, la MMU responde levantando una excepción (comúnmente llamada fallo de página). Si la página se encuentra en el área de intercambio, se salta a una rutina que invoca una operación llamada un intercambio de página, para traer a memoria principal la página requerida. La operación lleva varios pasos. Primero se selecciona una página en memoria, por ejemplo una que no haya sido usada recientemente (para más detalles ver algoritmos de reemplazo de páginas). Si la página fue modificada, se escribe la misma en el espacio de intercambio. El siguiente paso en el proceso es leer la información en la página necesitada desde el espacio de intercambio). Cuando esto sucede, las tablas para traducción de direcciones virtuales a reales son actualizadas para reflejar los contenidos de la memoria física. Entonces el intercambio de página sale, y el programa que usó la dirección que causó la excepción es vuelto a ejecutar desde el punto en que se dio la misma y continúa como si nada hubiera pasado. También es posible que: una dirección virtual es marcada como no disponible, porque no fue localizada previamente. En estos casos, una página de memoria es localizada y llenada con ceros, la tabla de paginación es modificada para mostrar los cambios y el programa se reinicia como en el otro caso.
4.3.2 Segmentación de memoria virtual
Desventajas de la segmentación
* Hay un incremento en los costos de hardware y de software para llevar a cabo la implantación, así como un mayor consumo de recursos: memoria, tiempo de CPU, etc.
* Debido a que los segmentos tienen un tamaño variable se pueden presentar problemas de fragmentación externas, lo que puede ameritar un plan de reubicación de segmentos en memoria principal.
* Se complica el manejo de memoria virtual, ya que los discos almacenan la información en bloques de tamaños fijos, mientras los segmentos son de tamaño variable. Esto hace necesaria la existencia de mecanismos más costosos que los existentes para paginación.
* Al permitir que los segmentos varíen de tamaño, puede ser necesarios planes de reubicación a nivel de los discos, si los segmentos son devueltos a dicho dispositivo; lo que conlleva a nuevos costos.
* No se puede garantizar, que al salir un segmento de la memoria, este pueda ser traído fácilmente de nuevo, ya que será necesario encontrar nuevamente un área de memoria libre ajustada a su tamaño.
* La comparticion de segmentos permite ahorrar memoria, pero requiere de mecanismos adicionales da hardware y software
4.3.3 ALGORITMOS DE SUSTITUCIÓN DE PÁGINAS
ALGORITMOS DE SUSTITUCIÓN DE PÁGINAS
Cuando ocurre una falla de página, el sistema operativo tiene que escoger la página que sacará de la memoria para que pueda entrar la nueva página. Si la página que se eliminará fue modificada mientras estaba en la memoria, se debe reescribir en el disco a fin de actualizar la copia del disco, pero si no fue así (p. ej., si la página contenía texto de programa), la copia en disco ya estará actualizada y no será necesario reescribirla. La nueva página simplemente sobre escribe la que está siendo desalojada.
Si bien sería posible escoger una página al azar para ser desalojada cuando ocurre una falla de página, el rendimiento del sistema es mucho mejor si se escoge una página que no se usa mucho. Si se elimina una página de mucho uso, probablemente tendrá que traerse pronto a la memoria otra vez, aumentando el gasto extra. Se ha trabajado mucho sobre el tema de los algoritmos de reemplazo de páginas, tanto teórica como experimentalmente. A continuación describimos algunos de los algoritmos más importantes.
El algoritmo de sustitución de páginas óptimo
El mejor algoritmo de reemplazo de páginas posible es fácil de describir pero imposible de implementar. En el momento en que ocurre una falla de páginas, algún conjunto de páginas está en la memoria. A una de estas páginas se hará referencia en la siguiente instrucción (la página que contiene esa instrucción). Otras páginas podrían no necesitarse sino hasta 10, 100 o tal vez 1000 instrucciones después. Cada página puede rotularse con el número de instrucciones que se ejecutarán antes de que se haga referencia a esa página.
El algoritmo de reemplazo de páginas óptimo simplemente dice que se debe eliminar la página que tenga el rótulo más alto. Si una página no se va a usar sino hasta después de 8 millones de instrucciones y otra página no se usará sino hasta después de 6 millones de instrucciones, el desalojo de la primera postergará la falla de página que la traerá de nuevo a la memoria lo más lejos hacia el futuro que es posible. Las computadoras, al igual que las personas, tratan de aplazar los sucesos desagradables el mayor tiempo que se puede.
El único problema con este algoritmo es que no se puede poner en práctica. En el momento en que ocurre la falla de página, el sistema operativo no tiene manera de saber cuándo se hará referencia a cada una de las páginas. (Vimos una situación similar antes con el algoritmo de planificación del primer trabajo más corto; ¿cómo puede el sistema saber cuál trabajo es el más corto?) No obstante, si se ejecuta un programa en un simulador y se toma nota de todas las referencias a páginas, es posible implementar el reemplazo de páginas óptimo en la segunda ejecución utilizando la información recabada durante la primera.
De este modo, es posible comparar el rendimiento de los algoritmos realizables con el mejor posible. Si un sistema operativo logra un rendimiento, digamos, sólo 1 % peor que el algoritmo óptimo, los esfuerzos dedicados a buscar un mejor algoritmo redundarán cuando más en una mejora del 1%. Para evitar confusiones, debemos dejar sentado que esta bitácora de referencias a páginas sólo es válido para el programa que acaba de medirse. El algoritmo de reemplazo de páginas derivado de él es específico para ése y sólo ese programa. Aunque este método es útil para evaluar los algoritmos de reemplazo de páginas, no sirve de nada en los sistemas prácticos. A continuación estudiaremos algoritmos que sí son útiles en los sistemas reales.
El algoritmo de sustitución de páginas no usadas recientemente
Cuando ocurre una falla de página, el sistema operativo examina todas las páginas y las divide en cuatro categorías con base en los valores actuales de sus bits R y M:
Clase 0: no referida, no modificada.
Clase 1: no referida, modificada.
Clase 2: referida, no modificada.
Clase 3: referida, modificada.
Cuando ocurre una falla de página, el sistema operativo tiene que escoger la página que sacará de la memoria para que pueda entrar la nueva página. Si la página que se eliminará fue modificada mientras estaba en la memoria, se debe reescribir en el disco a fin de actualizar la copia del disco, pero si no fue así (p. ej., si la página contenía texto de programa), la copia en disco ya estará actualizada y no será necesario reescribirla. La nueva página simplemente sobre escribe la que está siendo desalojada.
Si bien sería posible escoger una página al azar para ser desalojada cuando ocurre una falla de página, el rendimiento del sistema es mucho mejor si se escoge una página que no se usa mucho. Si se elimina una página de mucho uso, probablemente tendrá que traerse pronto a la memoria otra vez, aumentando el gasto extra. Se ha trabajado mucho sobre el tema de los algoritmos de reemplazo de páginas, tanto teórica como experimentalmente. A continuación describimos algunos de los algoritmos más importantes.
El algoritmo de sustitución de páginas óptimo
El mejor algoritmo de reemplazo de páginas posible es fácil de describir pero imposible de implementar. En el momento en que ocurre una falla de páginas, algún conjunto de páginas está en la memoria. A una de estas páginas se hará referencia en la siguiente instrucción (la página que contiene esa instrucción). Otras páginas podrían no necesitarse sino hasta 10, 100 o tal vez 1000 instrucciones después. Cada página puede rotularse con el número de instrucciones que se ejecutarán antes de que se haga referencia a esa página.
El algoritmo de reemplazo de páginas óptimo simplemente dice que se debe eliminar la página que tenga el rótulo más alto. Si una página no se va a usar sino hasta después de 8 millones de instrucciones y otra página no se usará sino hasta después de 6 millones de instrucciones, el desalojo de la primera postergará la falla de página que la traerá de nuevo a la memoria lo más lejos hacia el futuro que es posible. Las computadoras, al igual que las personas, tratan de aplazar los sucesos desagradables el mayor tiempo que se puede.
El único problema con este algoritmo es que no se puede poner en práctica. En el momento en que ocurre la falla de página, el sistema operativo no tiene manera de saber cuándo se hará referencia a cada una de las páginas. (Vimos una situación similar antes con el algoritmo de planificación del primer trabajo más corto; ¿cómo puede el sistema saber cuál trabajo es el más corto?) No obstante, si se ejecuta un programa en un simulador y se toma nota de todas las referencias a páginas, es posible implementar el reemplazo de páginas óptimo en la segunda ejecución utilizando la información recabada durante la primera.
De este modo, es posible comparar el rendimiento de los algoritmos realizables con el mejor posible. Si un sistema operativo logra un rendimiento, digamos, sólo 1 % peor que el algoritmo óptimo, los esfuerzos dedicados a buscar un mejor algoritmo redundarán cuando más en una mejora del 1%. Para evitar confusiones, debemos dejar sentado que esta bitácora de referencias a páginas sólo es válido para el programa que acaba de medirse. El algoritmo de reemplazo de páginas derivado de él es específico para ése y sólo ese programa. Aunque este método es útil para evaluar los algoritmos de reemplazo de páginas, no sirve de nada en los sistemas prácticos. A continuación estudiaremos algoritmos que sí son útiles en los sistemas reales.
El algoritmo de sustitución de páginas no usadas recientemente
Cuando ocurre una falla de página, el sistema operativo examina todas las páginas y las divide en cuatro categorías con base en los valores actuales de sus bits R y M:
Clase 0: no referida, no modificada.
Clase 1: no referida, modificada.
Clase 2: referida, no modificada.
Clase 3: referida, modificada.
4.3.4 ASPECTOS DE DISEÑO DE LOS SISTEMAS CON PAGINACIÓN
El modelo de conjunto de trabajo
En la forma más pura de paginación, los procesos se inician con ninguna de sus páginas en la memoria. Tan pronto como la CPU trata de obtener la primera instrucción, detecta una falla página que hace que el sistema operativo traiga a la memoria la página que contiene dicha instrucción. Por lo regular, pronto ocurren otras fallas de página al necesitarse variables globales y la pila. Después de un tiempo, el proceso tiene la mayor parte de las páginas que necesita y se dedica a ejecutarse con relativamente pocas fallas de página. Tal estrategia se denomina paginación por demanda porque las páginas se cargan sólo cuando se piden, no por adelantado.
Desde luego, es fácil escribir un programa de prueba que lea sistemáticamente todas páginas de un espacio de direcciones grande, causando tantas fallas de página que no habrá suficiente memoria para contenerlas todas. Por fortuna, la mayor parte de los procesos no funcionan así; exhiben una localidad de referencia, lo que significa que durante cualquier fase de ejecución, el proceso sólo hace referencia a una fracción relativamente pequeña de sus páginas. Cada pasada de un compilador de múltiples pasadas, por ejemplo, sólo hace referencia a fracción de todas las páginas, que es diferente en cada pasada. El conjunto de páginas que un proceso está usando actualmente es su conjunto de trabajo (Denning, 1968a; Denning, 1980). Si todo el conjunto de trabajo está en la memoria, el proceso ejecutará sin causar muchas fallas hasta que pase a otra fase de su ejecución (p. ej., la siguiente pasada de un compilador). Si la memoria disponible es demasiado pequeña para contener todo conjunto de trabajo, el proceso causará muchas fallas de página y se ejecutará lentamente, ya que la ejecución de una instrucción normalmente toma unos cuantos nanosegundos, y la lectura; una página de disco suele tomar decenas de milisegundos. Si ejecuta sólo una o dos instrucción cada 20 milisegundos, el proceso tardará muchísimo en terminar. Se dice que un programa q causa fallas de página repetidamente después de unas cuantas instrucciones se está “sacudiendo (en inglés, thrashing, que es el término que utilizaremos) (Denning, 1968b). ‘¡
En un sistema de tiempo compartido, los procesos a menudo se transfieren al disco (esto es, todas sus páginas se eliminan de la memoria) para que otro proceso tenga oportunidad de usar la CPU. Surge la pregunta de qué hacer cuando se vuelve a traer un proceso a la memoria. Técnicamente, no hay que hacer nada. El proceso simplemente causará fallas de página hasta que haya cargado su conjunto de trabajo. El problema es que tener 20, 50 o incluso 100 fallas de página cada vez que se carga un proceso hace lento el funcionamiento y además desperdicia mucho tiempo de CPU, pues el sistema operativo requiere unos cuantos milisegundos de tiempo de CPU para procesar una falla de página. Por ello, muchos sistemas de paginación tratan de seguir la pista al conjunto de trabajo de cada proceso y se aseguran de que esté en la memoria antes de dejar que el proceso se ejecute. Este enfoque se denomina modelo de conjunto de trabajo (Denning, 1970) y está diseñado para reducir considerablemente la tasa de fallas de página. La carga de las páginas antes de dejar que los procesos se ejecuten también se denomina prepaginación. A fin de implementar el modelo de conjunto de trabajo, el sistema operativo tiene que saber cuáles páginas están en el conjunto de trabajo. Una forma de seguir la pista a esta información es usar el algoritmo de maduración que acabamos de explicar. Cualquier página que contenga un bit 1 entre los n bits de orden alto del contador se considera miembro del conjunto de trabajo. Si no se ha hecho referencia a una página en n tics de reloj consecutivos, se omite del conjunto de trabajo. El parámetro n se debe determinar experimentalmente para cada sistema, pero por lo regular el rendimiento del sistema no es muy sensible al valor exacto. La información relativa al conjunto de trabajo puede servir para mejorar el rendimiento del algoritmo del reloj. Normalmente, cuando la manecilla apunta a una página cuyo bit R es O, esa página se desaloja. La mejora consiste en verificar si esa página forma parte del conjunto de trabajo del proceso en curso. Si lo es, se le perdona la vida. Este algoritmo se conoce como wsclock.
Tamaño de página
En muchos casos, el tamaño de página es un parámetro que el sistema operativo puede escoger. Incluso si el hardware se diseñó con páginas de, por ejemplo, 512 bytes, el sistema operativo fácilmente puede considerar las páginas O y l, 2 y 3, 4 y 5,etc., como páginas de 1K asignando siempre dos marcos de página de 512 bytes consecutivos a ellas. La determinación del tamaño de página óptimo requiere balancear varios factores opuestos. Por principio, un segmento de texto, datos o pila escogido al azar no llena un número entero de 342 ADMINISTRACIÓN DE MEMORIA CAP.4 páginas. En promedio, la mitad de la página final estará vacía. El espacio extra de esa página se desperdicia, y este desperdicio se denomina fragmentación interna. Con n segmentos en memoria y un tamaño de página de p bytes, se desperdiciarán np/2 bytes por fragmentación interna. Este razonamiento es un argumento a favor de las páginas pequeñas. Otro argumento a favor de un tamaño de página pequeño se hace evidente si pensamos en un programa que consiste en ocho fases secuenciales de 4K cada una. Con un tamaño de página 32K, habría que asignar al programa 32K todo el tiempo. Con un tamaño de página de 16K programa sólo necesitaría 16K. Con un tamaño de página de 4K o menor, el programa se requeriría 4K en un momento dado. En general, un tamaño de página grande hará que haya proporción mayor de programa no utilizado en la memoria que si se usan páginas pequeñas. Por otro lado, el empleo de páginas pequeñas implica que los programas necesitarán muchas páginas, y la tabla de páginas será grande. Un programa de 32K sólo necesita cuatro páginas 8K, pero 64 páginas de 512 bytes. Las transferencias entre la memoria y el disco generalmente son de páginas completas, y la mayor parte del tiempo se invierte en la búsqueda y el retardo rotacional, de modo que la transferencia de una página pequeña toma casi tanto tiempo como en una página grande. Podrían requerirse 64 x 15 ms para cargar 64 páginas de 512 bytes, pero sólo 4 x 25 ms para cargar cuatro páginas de 8K. En algunas máquinas, la tabla de páginas debe cargarse en registros de hardware cada que la CPU conmuta de un proceso a otro. En estas máquinas, tener un tamaño de página pequeña implica que el tiempo requerido para cargar los registros de páginas aumenta conforme el tamaño de página disminuye. Además, el espacio ocupado por la tabla de páginas aumenta al disminuir el tamaño de página. Este último punto puede analizarse matemáticamente. Sea s el tamaño de proceso promedio en bytes y p el tamaño de página en bytes. Además, suponga que cada entrada de página requiere bytes. El número apropiado de páginas requeridas por proceso es entonces s/p, que ocupan p bytes en la tabla de páginas. La memoria desperdiciada en la última página del proceso debido a la fragmentación interna es p/2. Por tanto, el gasto extra total debido a la tabla de páginas y a la pérdida por fragmentación interna está dada por gasto extra = selp + p/2 El primer término (tamaño de la tabla de páginas) es grande cuando el tamaño de página pequeño. El segundo término (fragmentación interna) es grande cuando el tamaño de página es grande. El tamaño óptimo debe estar en algún punto intermedio. Si obtenemos la primera derivada respecto a p y la igualamos a cero, tenemos la ecuación -selp2 +1/2=0 De esta ecuación podemos deducir una fórmula que da el tamaño de página óptimo (considerando sólo la memoria desperdiciada por fragmentación y el tamaño de la tabla de páginas). El resultado p = ^ 2se SEC. 4.6 SEGMENTACIÓN 343 Para s = 128K y e = 8 bytes por entrada de tabla de páginas, el tamaño de página óptimo es de 1448 bytes. En la práctica se usaría 1K o 2K, dependiendo de los demás factores (p. ej., rapidez del disco). La mayor parte de las computadoras comerciales emplean tamaños de página que van desde 512 bytes hasta 64K. 4.5.4 Interfaz de memoria virtual Hasta ahora, hemos supuesto que la memoria virtual es transparente para los procesos y los programadores. Esto es, todo lo que ellos ven es un espacio de direcciones virtual grande en una computadora con una memoria física (más) pequeña. En muchos sistemas, esto es cierto, pero en algunos sistemas avanzados los programadores tienen cierto control sobre el mapa de memoria y lo pueden utilizar de formas no tradicionales. En esta sección veremos brevemente algunas de ellas. Una razón para dar a los programadores control sobre su mapa de memoria es permitir que dos o más procesos compartan la misma memoria. Si los programadores pueden nombrar regiones de su memoria, un proceso puede darle a otro el nombre de una región de memoria para que pueda incluirla en su mapa. Cuando dos (o más) procesos comparten las mismas páginas, se hace posible la compartición de alto ancho de banda: un proceso escribe en la memoria compartida y el otro la lee. La compartición de páginas también puede servir para implementar un sistema de transferencia de páginas de alto rendimiento. Normalmente, cuando se transfieren mensajes, los datos se copian de un espacio de direcciones a otro, pagando un precio considerable. Si los procesos pueden controlar su mapa de páginas, se puede transferir un mensaje haciendo que el proceso transmisor excluya de su mapa la página o páginas que contienen el mensaje, y que el proceso receptor las incluya en su mapa. Aquí sólo tendrían que copiarse los nombres de página, no todos los datos. Otra técnica de administración avanzada de memoria es la memoria compartida distribuida (Feeley et al., 1995; Li y Hudak, 1989; Zekauskas et al., 1994). De lo que se trata aquí es de permitir que múltiples procesos en una red compartan un conjunto de páginas, posiblemente, aunque no necesariamente, como un solo espacio de direcciones lineal compartido. Cuando un proceso hace referencia a una página que actualmente no está en su mapa, genera una falla de página. El manejador de fallas de página, que puede estar en el kernel o en el espacio de usuario, localiza entonces la máquina que tiene la página y le envía un mensaje pidiéndole que la excluya de su mapa y la envíe por la red. Cuando llega la página, se incluye en el mapa y se reinicia la instrucción que falló
En la forma más pura de paginación, los procesos se inician con ninguna de sus páginas en la memoria. Tan pronto como la CPU trata de obtener la primera instrucción, detecta una falla página que hace que el sistema operativo traiga a la memoria la página que contiene dicha instrucción. Por lo regular, pronto ocurren otras fallas de página al necesitarse variables globales y la pila. Después de un tiempo, el proceso tiene la mayor parte de las páginas que necesita y se dedica a ejecutarse con relativamente pocas fallas de página. Tal estrategia se denomina paginación por demanda porque las páginas se cargan sólo cuando se piden, no por adelantado.
Desde luego, es fácil escribir un programa de prueba que lea sistemáticamente todas páginas de un espacio de direcciones grande, causando tantas fallas de página que no habrá suficiente memoria para contenerlas todas. Por fortuna, la mayor parte de los procesos no funcionan así; exhiben una localidad de referencia, lo que significa que durante cualquier fase de ejecución, el proceso sólo hace referencia a una fracción relativamente pequeña de sus páginas. Cada pasada de un compilador de múltiples pasadas, por ejemplo, sólo hace referencia a fracción de todas las páginas, que es diferente en cada pasada. El conjunto de páginas que un proceso está usando actualmente es su conjunto de trabajo (Denning, 1968a; Denning, 1980). Si todo el conjunto de trabajo está en la memoria, el proceso ejecutará sin causar muchas fallas hasta que pase a otra fase de su ejecución (p. ej., la siguiente pasada de un compilador). Si la memoria disponible es demasiado pequeña para contener todo conjunto de trabajo, el proceso causará muchas fallas de página y se ejecutará lentamente, ya que la ejecución de una instrucción normalmente toma unos cuantos nanosegundos, y la lectura; una página de disco suele tomar decenas de milisegundos. Si ejecuta sólo una o dos instrucción cada 20 milisegundos, el proceso tardará muchísimo en terminar. Se dice que un programa q causa fallas de página repetidamente después de unas cuantas instrucciones se está “sacudiendo (en inglés, thrashing, que es el término que utilizaremos) (Denning, 1968b). ‘¡
En un sistema de tiempo compartido, los procesos a menudo se transfieren al disco (esto es, todas sus páginas se eliminan de la memoria) para que otro proceso tenga oportunidad de usar la CPU. Surge la pregunta de qué hacer cuando se vuelve a traer un proceso a la memoria. Técnicamente, no hay que hacer nada. El proceso simplemente causará fallas de página hasta que haya cargado su conjunto de trabajo. El problema es que tener 20, 50 o incluso 100 fallas de página cada vez que se carga un proceso hace lento el funcionamiento y además desperdicia mucho tiempo de CPU, pues el sistema operativo requiere unos cuantos milisegundos de tiempo de CPU para procesar una falla de página. Por ello, muchos sistemas de paginación tratan de seguir la pista al conjunto de trabajo de cada proceso y se aseguran de que esté en la memoria antes de dejar que el proceso se ejecute. Este enfoque se denomina modelo de conjunto de trabajo (Denning, 1970) y está diseñado para reducir considerablemente la tasa de fallas de página. La carga de las páginas antes de dejar que los procesos se ejecuten también se denomina prepaginación. A fin de implementar el modelo de conjunto de trabajo, el sistema operativo tiene que saber cuáles páginas están en el conjunto de trabajo. Una forma de seguir la pista a esta información es usar el algoritmo de maduración que acabamos de explicar. Cualquier página que contenga un bit 1 entre los n bits de orden alto del contador se considera miembro del conjunto de trabajo. Si no se ha hecho referencia a una página en n tics de reloj consecutivos, se omite del conjunto de trabajo. El parámetro n se debe determinar experimentalmente para cada sistema, pero por lo regular el rendimiento del sistema no es muy sensible al valor exacto. La información relativa al conjunto de trabajo puede servir para mejorar el rendimiento del algoritmo del reloj. Normalmente, cuando la manecilla apunta a una página cuyo bit R es O, esa página se desaloja. La mejora consiste en verificar si esa página forma parte del conjunto de trabajo del proceso en curso. Si lo es, se le perdona la vida. Este algoritmo se conoce como wsclock.
Tamaño de página
En muchos casos, el tamaño de página es un parámetro que el sistema operativo puede escoger. Incluso si el hardware se diseñó con páginas de, por ejemplo, 512 bytes, el sistema operativo fácilmente puede considerar las páginas O y l, 2 y 3, 4 y 5,etc., como páginas de 1K asignando siempre dos marcos de página de 512 bytes consecutivos a ellas. La determinación del tamaño de página óptimo requiere balancear varios factores opuestos. Por principio, un segmento de texto, datos o pila escogido al azar no llena un número entero de 342 ADMINISTRACIÓN DE MEMORIA CAP.4 páginas. En promedio, la mitad de la página final estará vacía. El espacio extra de esa página se desperdicia, y este desperdicio se denomina fragmentación interna. Con n segmentos en memoria y un tamaño de página de p bytes, se desperdiciarán np/2 bytes por fragmentación interna. Este razonamiento es un argumento a favor de las páginas pequeñas. Otro argumento a favor de un tamaño de página pequeño se hace evidente si pensamos en un programa que consiste en ocho fases secuenciales de 4K cada una. Con un tamaño de página 32K, habría que asignar al programa 32K todo el tiempo. Con un tamaño de página de 16K programa sólo necesitaría 16K. Con un tamaño de página de 4K o menor, el programa se requeriría 4K en un momento dado. En general, un tamaño de página grande hará que haya proporción mayor de programa no utilizado en la memoria que si se usan páginas pequeñas. Por otro lado, el empleo de páginas pequeñas implica que los programas necesitarán muchas páginas, y la tabla de páginas será grande. Un programa de 32K sólo necesita cuatro páginas 8K, pero 64 páginas de 512 bytes. Las transferencias entre la memoria y el disco generalmente son de páginas completas, y la mayor parte del tiempo se invierte en la búsqueda y el retardo rotacional, de modo que la transferencia de una página pequeña toma casi tanto tiempo como en una página grande. Podrían requerirse 64 x 15 ms para cargar 64 páginas de 512 bytes, pero sólo 4 x 25 ms para cargar cuatro páginas de 8K. En algunas máquinas, la tabla de páginas debe cargarse en registros de hardware cada que la CPU conmuta de un proceso a otro. En estas máquinas, tener un tamaño de página pequeña implica que el tiempo requerido para cargar los registros de páginas aumenta conforme el tamaño de página disminuye. Además, el espacio ocupado por la tabla de páginas aumenta al disminuir el tamaño de página. Este último punto puede analizarse matemáticamente. Sea s el tamaño de proceso promedio en bytes y p el tamaño de página en bytes. Además, suponga que cada entrada de página requiere bytes. El número apropiado de páginas requeridas por proceso es entonces s/p, que ocupan p bytes en la tabla de páginas. La memoria desperdiciada en la última página del proceso debido a la fragmentación interna es p/2. Por tanto, el gasto extra total debido a la tabla de páginas y a la pérdida por fragmentación interna está dada por gasto extra = selp + p/2 El primer término (tamaño de la tabla de páginas) es grande cuando el tamaño de página pequeño. El segundo término (fragmentación interna) es grande cuando el tamaño de página es grande. El tamaño óptimo debe estar en algún punto intermedio. Si obtenemos la primera derivada respecto a p y la igualamos a cero, tenemos la ecuación -selp2 +1/2=0 De esta ecuación podemos deducir una fórmula que da el tamaño de página óptimo (considerando sólo la memoria desperdiciada por fragmentación y el tamaño de la tabla de páginas). El resultado p = ^ 2se SEC. 4.6 SEGMENTACIÓN 343 Para s = 128K y e = 8 bytes por entrada de tabla de páginas, el tamaño de página óptimo es de 1448 bytes. En la práctica se usaría 1K o 2K, dependiendo de los demás factores (p. ej., rapidez del disco). La mayor parte de las computadoras comerciales emplean tamaños de página que van desde 512 bytes hasta 64K. 4.5.4 Interfaz de memoria virtual Hasta ahora, hemos supuesto que la memoria virtual es transparente para los procesos y los programadores. Esto es, todo lo que ellos ven es un espacio de direcciones virtual grande en una computadora con una memoria física (más) pequeña. En muchos sistemas, esto es cierto, pero en algunos sistemas avanzados los programadores tienen cierto control sobre el mapa de memoria y lo pueden utilizar de formas no tradicionales. En esta sección veremos brevemente algunas de ellas. Una razón para dar a los programadores control sobre su mapa de memoria es permitir que dos o más procesos compartan la misma memoria. Si los programadores pueden nombrar regiones de su memoria, un proceso puede darle a otro el nombre de una región de memoria para que pueda incluirla en su mapa. Cuando dos (o más) procesos comparten las mismas páginas, se hace posible la compartición de alto ancho de banda: un proceso escribe en la memoria compartida y el otro la lee. La compartición de páginas también puede servir para implementar un sistema de transferencia de páginas de alto rendimiento. Normalmente, cuando se transfieren mensajes, los datos se copian de un espacio de direcciones a otro, pagando un precio considerable. Si los procesos pueden controlar su mapa de páginas, se puede transferir un mensaje haciendo que el proceso transmisor excluya de su mapa la página o páginas que contienen el mensaje, y que el proceso receptor las incluya en su mapa. Aquí sólo tendrían que copiarse los nombres de página, no todos los datos. Otra técnica de administración avanzada de memoria es la memoria compartida distribuida (Feeley et al., 1995; Li y Hudak, 1989; Zekauskas et al., 1994). De lo que se trata aquí es de permitir que múltiples procesos en una red compartan un conjunto de páginas, posiblemente, aunque no necesariamente, como un solo espacio de direcciones lineal compartido. Cuando un proceso hace referencia a una página que actualmente no está en su mapa, genera una falla de página. El manejador de fallas de página, que puede estar en el kernel o en el espacio de usuario, localiza entonces la máquina que tiene la página y le envía un mensaje pidiéndole que la excluya de su mapa y la envíe por la red. Cuando llega la página, se incluye en el mapa y se reinicia la instrucción que falló
4.3.5 Liberación de páginas
Un proceso usuario puede emitir una “liberación voluntaria de página” para liberar el marco de página cuando ya no necesitara esa página.
Se puede eliminar el “desperdicio” y acelerar la ejecución.
El inconveniente es que la incorporación de mandatos de liberación de páginas dentro de los programas de usuarios puede ser peligroso y retrasar el desarrollo de aplicaciones.
“Los compiladores y S. O. deberían detectar automáticamente situaciones de liberación de página mucho antes de lo que es posible con estrategias de conjuntos de trabajo”.
Se puede eliminar el “desperdicio” y acelerar la ejecución.
El inconveniente es que la incorporación de mandatos de liberación de páginas dentro de los programas de usuarios puede ser peligroso y retrasar el desarrollo de aplicaciones.
“Los compiladores y S. O. deberían detectar automáticamente situaciones de liberación de página mucho antes de lo que es posible con estrategias de conjuntos de trabajo”.
viernes, 6 de noviembre de 2009
Suscribirse a:
Entradas (Atom)