miércoles, 28 de noviembre de 2012

3.3.4 Sistemas de paginación segmentación.

Sistemas de Paginación / Segmentación

Ofrecen las ventajas de las dos técnicas de organización del almacenamiento virtual
El tamaño de los segmentos es múltiplo del de las páginas.
No es necesario que todas las páginas de un segmento se encuentren al mismo tiempo en el almacenamiento primario.
Las páginas de almacenamiento virtual, que son contiguas en este almacenamiento, no necesitan ser contiguas en el almacenamiento real.
El direccionamiento es tridimensional con una dirección de almacenamiento virtual “v = (s,p,d)”:
  • “s” es el número del segmento.
  • “p” es el número de página.
  • “d” es el desplazamiento en la página donde se encuentra asignado el elemento deseado.
Inicio:    Fin:
Traducción Dinámica de Direcciones en Sistemas de Paginación / Segmentación
Se considera la traducción dinámica de direcciones de virtuales a reales en un sistema de paginación / segmentación utilizando la combinación de transformación asociativa / directa

El proceso en ejecución hace referencia a la dirección virtual v = (s,p,d)

Las páginas de referencia más reciente tienen entradas en un almacenamiento asociativo.
Se realiza una búsqueda asociativa para intentar localizar (s,p) en el almacenamiento asociativo:
  • Si se encuentra (s,p), entonces el marco de página “p ’ ” en el cual reside dicha página en la memoria real, se concatena al desplazamiento “d” para formar la dirección de memoria real “r” correspondiente a la dirección virtual v= (s,p,d).
  • Si no se encuentra (s,p), entonces:
    • La dirección base “b” de la tabla de segmentos se añade al número de segmento “s” formando la dirección “b + s” de la entrada de la tabla de mapa de segmentos para el segmento “s” de la memoria real.
    • La entrada de la tabla de mapa de segmentos indica la dirección base “s ’ ” de la tabla de páginas para el segmento “s”.
    • El número de página “p” se añade a “s ’ ” formando la dirección “p + s ’ ” de la entrada en la tabla de páginas para la página “p” del segmento “s”:
      • Indica que “p ’ ” es el número del marco correspondiente a la página virtual “p”.
      • “p ’ ” se concatena con el desplazamiento “d” formando la dirección real “r ” que corresponde a la dirección virtual v = (s,p,d).
Si el segmento “s” no se encuentra en el almacenamiento primario se produce un “fallo de pérdida de segmento”, cuyo caso el S. O. localiza el segmento en el almacenamiento secundario, crea una tabla de páginas para el segmento y carga la página apropiada en el almacenamiento primario, pudiendo producir reemplazos de páginas.
Si el segmento “s” está en el almacenamiento primario y si la referencia a la tabla de mapa de páginas indica que la página deseada no se encuentra en el almacenamiento primario, se produce un “fallo de pérdida de página”, en tal caso el S. O. obtiene el control, localiza la página en el almacenamiento secundario y la carga, pudiendo reemplazar otra página.
Si una dirección de almacenamiento virtual está más allá del final del segmento se genera un “fallo de desbordamiento de segmento”, el que debe ser atendido por el S. O.
Si los bits de protección indican que la operación que se va a ejecutar en la dirección virtual referida no se permite, se genera un “fallo de protección de segmento”, el que también debe ser atendido por el S. O.
Si se utiliza un mecanismo de transformación directa pura, manteniendo el mapa completo dentro del almacenamiento primario, la referencia promedio de almacenamiento virtual requeriría:
  • Un ciclo de almacenamiento para acceder a la tabla de mapa de segmentos.
  • Un segundo ciclo de almacenamiento para hacer referencia a la tabla de mapa de páginas.
  • Un tercer ciclo de almacenamiento para referenciar al elemento deseado del almacenamiento real.
Cada referencia a un elemento comprende tres ciclos de almacenamiento:
  • El sistema correría casi a 1 / 3 de su velocidad nominal.
  • La traducción de direcciones insumiría 2 / 3 del tiempo.
Con la utilización de registros asociativos (por ej. 16 registros), se logran velocidades de ejecución del 90 % o más de la velocidad total de procesamiento de sus procesadores de control.
La estructura de tablas de procesos, de mapas de segmentos y de mapas de páginas puede consumir un porcentaje importante del almacenamiento primario cuando se ejecutan un gran número de procesos.
La traducción procede mucho más rápido si todas las tablas están en el almacenamiento primario, lo que resta espacio para los procesos.
Inicio:    Fin:
Compartimiento en un Sistema de Paginación / Segmentación
Se implementa disponiendo entradas en tablas de mapa de segmentos para diferentes procesos que apunten a la misma tabla de mapa de páginas .
El compartimiento requiere una administración cuidadosa por parte del S. O., ya sea en sistemas de paginación, segmentación o paginación / segmentación, pues se debe considerar qué sucedería si una nueva página reemplazara a otra página compartida por muchos procesos.



Sistemas combinados

La paginación y la segmentación puras son métodos de manejo de memoria bastante efectivos, aunque la mayoría de los sistemas operativos modernos implantan esquemas combinados, es decir, combinan la paginación y la segmentación. La idea de combinar estos esquemas se debe a que de esta forma se aprovechan los conceptos de la división lógica de los programas (segmentos) con la granularidad de las páginas. De esta forma, un proceso estará repartido en la memoria real en pequeñas unidades (páginas) cuya liga son los segmentos. También es factible así el compartir segmentos a medida que las partes necesitadas de los mismos se van referenciando (páginas). Para comprender este esquema, nuevamente se verá cómo se traduce una dirección virtual en una localidad de memoria real. Para la paginación y segmentacíon puras se puede decir que el direccionamiento es `bidimensional' porque se necesitan dos valores para hallar la dirección real. Para el caso combinado, se puede decir que se tiene un direccionamiento `tridimensional'. En la figura 4.8 [ Deitel93] se muestran las partes relevantes para lograr la traducción de direcciones. El sistema debe contar con una tabla de procesos (TP). Por cada renglón de esa tabla se tiene un número de proceso y una dirección a una tabla de segmentos. Es decir, cada proceso tiene una tabla de segmentos. Cuando un proceso hace alguna referencia a memoria, se consulta TP para encontrar la tabla de segmentos de ese proceso. En cada tabla de segmentos de proceso (TSP) se tienen los números de los segmentos que componen a ese proceso. Por cada segmento se tiene una dirección a una tabla de páginas. Cada tabla de páginas tiene las direcciones de las páginas que componen a un solo segmento. Por ejemplo, el segmento `A' puede estar formado por las páginas reales `a','b','c','p' y `x'. El segmento `B' puede estar compuesto de las páginas `f','g','j','w' y `z'.

Para traducir una dirección virtual v=(s,p,d) donde `s' es el segmento, `p' es la página y `d' el desplazamiento en la página se hace lo siguiente. Primero se ubica de qué proceso es el segmento y se localiza la tabla de segmentos de ese proceso en la TP. Con `s' como índice se encuentra un renglón ( registro) en la tabla de segmentos de ese proceso y en ese renglón está la dirección de la tabla de páginas que componen al segmento. Una vez en la tabla de páginas se usa el valor `p' como índice para encontrar la dirección de la página en memoria real. Una vez en esa dirección de memoria real se encuentra el byte (o palabra) requerido por medio del valor de `d'.
Ahora, en este esquema pueden haber dos tipos de fallos: por fallo de página y por fallo de segmento. Cuando se hace referencia a una dirección y el segmento que la contiene no está en RAM ( aunque sea parcialmente ), se provoca un fallo por falta de segmento y lo que se hace es traerlo del medio de almacenamiento secundario y crearle una tabla de páginas. Una vez caragado el segmento se necesita localizar la página correspondiente, pero ésta no existe en RAM, por lo cual se provoca un fallo de página y se carga de disco y finalmente se puede ya traer la dirección deseada por medio del desplazamiento de la dirección virtual.
La eficiencia de la traducción de direcciones tanto en paginación pura, segmentación pura y esquemas combinados se mejora usando memorias asociativas para las tablas de páginas y segmentos, así como memorias cache para guardar los mapeos más solicitados.
Otro aspecto importante es la estrategia para cargar páginas ( o segmentos ) a la memoria RAM. Se usan más comunmente dos estrategias: cargado de páginas por demanda y cargado de páginas anticipada. La estrategia de caragdo por demanda consiste en que las páginas solamente son llevadas a RAM si fueron solicitadas, es decir, si se hizo referencia a una dirección que cae dentro de ellas. La carga anticipada consiste en tratar de adivinar qué páginas serán solicitadas en el futuro inmediato y cargarlas de antemano, para que cuando se pidan ya no ocurran fallos de página. Ese `adivinar' puede ser que se aproveche el fenómeno de localidad y que las páginas que se cargan por anticipado sean aquellas que contienen direcciones contiguas a la dirección que se acaba de refenciar. De hecho, el sistema operativo VMS usa un esquema combinado para cargar páginas: cuando se hace referencia a una dirección cuya página no está en RAM, se provoca un fallo de página y se carga esa página junto con algunas páginas adyacentes. En este caso la página solicitada se cargó por demanda y las adyacentes se cargaron por anticipación.

3.3.3 Segmentación.

Segmentación
En los sistemas de “segmentación” un programa y sus datos pueden ocupar varios bloques separados de almacenamiento real
Los bloques:
  • No necesitan ser de igual tamaño.
  • Los bloques separados no necesitan ser adyacentes.
  • Deben estar compuestos de posiciones contiguas de almacenamiento.
Se complica la protección de bloques de memoria de un proceso de usuario.
Es más difícil limitar el rango de acceso de cualquier programa .
Un esquema posible de protección es el uso de claves de protección del almacenamiento
  • Las claves están bajo el control estricto del S. O.
  • Un programa de usuario, a quien corresponde una cierta clave en la cpu, solo puede hacer referencia a los otros bloques del almacenamiento con igual clave de protección.

Una dirección virtual es un par ordenado v=(s,d)
  • “s” es el número del segmento del almacenamiento virtual en el cual residen los elementos referidos.
  • “d” es el desplazamiento en el segmento “s” en el cual se encuentra el elemento referido.

Un proceso solo puede ejecutarse si su segmento actual (como mínimo) está en el almacenamiento primario.
Los segmentos se transfieren del almacenamiento secundario al primario como unidades completas.
Un nuevo segmento puede ser colocado en una serie disponible de posiciones contiguas del almacenamiento primario de tamaño suficiente para alojar al segmento.
La traducción dinámica de direcciones utiliza una “tabla de mapa de segmentos”.
Inicio:    Fin:
Control de Acceso en Sistemas de Segmentación
Se le otorga a cada proceso ciertos derechos de acceso a todos los segmentos y se le niega completamente el acceso a muchos otros.
Si un proceso tiene “acceso de lectura” a un segmento, puede obtener cualquier elemento de información contenido en ese segmento.
Si un proceso tiene “acceso de escritura” a un segmento, puede modificar cualquier contenido del segmento y puede introducirle información adicional, incluso destruir toda la información del segmento.
Un proceso con “acceso de ejecución” de un segmento puede ejecutarlo como si fuera un programa.
Un proceso con “acceso de adición” puede escribir información adicional al final del segmento, pero no puede modificar la información existente.
En base a los “tipos de control de acceso” indicados pueden crearse distintos “modos de control de acceso”.
Ejemplos de combinación de los accesos de lectura, escritura y ejecución para producir modos de protección útiles se dan en la Tabla 3.1 y en la Tabla 3.2 [7, Deitel].
 

Modo
Lectura
Escritura
Ejecución
Explicación
0
N
N
N
No hay permiso de acceso
1
N
N
S
Solo ejecución
2
S
N
N
Solo lectura
3
S
N
S
Lectura / ejecución
4
S
S
N
Lectura / escritura pero no ejecución
5
S
S
S
Acceso no limitado
Tabla 3.1: Ejemplo de combinación de accesos.

 
Modo
Aplicación
0
Seguridad
1
Un programa disponible a los usuarios, que no pueden copiarlo ni modificarlo, pero sí ejecutarlo
2
Recuperación de información
3
Un programa puede ser copiado o ejecutado, pero no puede ser modificado
4
Protege los datos contra un intento erróneo de ejecutarlos
5
Este acceso se concede a los usuarios de confianza
Tabla 3.2: Ejemplo de aplicaciones de la combinación de accesos.
Inicio:    Fin:
Traducción de Direcciones de Segmentación por Transformación Directa
Existen varias estrategias para la implementación de la traducción de direcciones de segmentación:
  • Por transformación directa, asociativa o combinación de asociativa / directa.
  • Con caché suficiente para alojar la tabla completa de mapa de segmentos o caché parciales que contengan solo las entradas de los segmentos de referencia más reciente

Se considerará la traducción de direcciones de segmentación con la tabla completa de mapa de segmentos en la caché.
Un proceso en ejecución hace referencia a la dirección virtual v = (s,d):
  • El segmento número “s” se añade a la dirección base “b” en el registro origen de la tabla de mapa de segmentos formando la dirección de memoria real “b + s”, de la entrada para el segmento “s” de la tabla de mapa de segmentos, que contiene la dirección del almacenamiento primario “s ’ ”, donde comienza el segmento.
  • El desplazamiento “d” se añade a “s ’ ” formando la dirección real “r = d + s ’ ”, correspondiente a la dirección virtual “v = (s,d)”.
Un “bit de residencia”, “r”, indica si en la actualidad el segmento se encuentra o no en el almacenamiento primario.
Si el segmento se encuentra en el almacenamiento primario “s ’ ” es la dirección en este almacenamiento donde comienza el segmento.
Si el segmento no se encuentra en el almacenamiento primario “a” es la dirección en el almacenamiento secundario de donde debe recuperarse antes que el proceso pueda continuar.
Se compara cada referencia a un segmento con los bits de protección para determinar si se permite la operación que se está intentando.
Si el segmento buscado no está en el almacenamiento primario se genera un “fallo de pérdida de segmento”:
  • El S. O. obtiene el control y carga el segmento referido desde la dirección “a” del almacenamiento secundario.
  • Se comprueba si el desplazamiento “d” es menor o igual a la longitud del segmento “l ”:
    • Si no es así se genera un “fallo de desbordamiento de segmento” y el S. O. obtiene el control y termina la ejecución del proceso.
    • Si el desplazamiento está en el rango del segmento se comprueban los bits de protección para asegurarse si se permite la operación que se está intentando:
      • Si es así entonces la dirección base del segmento, “s ’ ”, en el almacenamiento primario se añade al desplazamiento “d” formando la dirección de memoria real “r = s ’ + d”, que corresponde a la dirección del almacenamiento virtual “v = (s,d)”.
      • Si la operación intentada no se permite se genera un “fallo de protección de segmento” y el S. O. obtiene el control y termina la ejecución del proceso.
Inicio:    Fin:
Compartimiento en un Sistema de Segmentación
Una de las ventajas de la segmentación sobre la paginación es que se trata más de un hecho lógico que físico:
  • En un sistema de segmentación, una vez que un segmento ha sido declarado como compartido, entonces las estructuras que lo integran pueden cambiar de tamaño.
  • Lo anterior no cambia el hecho lógico de que residen en un segmento compartido.
Dos procesos pueden compartir un segmento con solo tener entradas en sus tablas generales que apunten al mismo segmento del almacenamiento primario .



Segmentación pura

La segmentación se aprovecha del hecho de que los programas se dividen en partes lógicas, como son las partes de datos, de código y de pila (stack). La segmentación asigna particiones de memoria a cada segmento de un programa y busca como objetivos el hacer fácil el compartir segmentos ( por ejemplo librerías compartidas ) y el intercambio entre memoria y los medios de almacenamiento secundario.

Por ejemplo, en la versión de UNIX SunOS 3.5, no existían librerías compartidas para algunas herramientas, por ejemplo, para los editores de texto orientados al ratón y menús. Cada vez que un usuario invocaba a un editor, se tenía que reservar 1 megabyte de memoria. Como los editores son una herramienta muy solicitada y frecuentemente usada, se dividió en segmentos para le versión 4.x ( que a su vez se dividen en páginas ), pero lo importante es que la mayor parte del editor es común para todos los usuarios, de manera que la primera vez que cualquier usuario lo invocaba, se reservaba un megabyte de memoria como antes, pero para el segundo, tercero y resto de usuarios, cada editor extra sólo consumía 20 kilobytes de memoria. El ahorro es impresionante. Obsérvese que en la segmentación pura las particiones de memoria son de tamaño variable, en contraste con páginas de tamaño fijo en la paginación pura. También se puede decir que la segmentación pura tiene una granularidad menor que la paginación por el tamanó de segmentos versus tamaño de páginas. Nuevamente, para comprender mejor la segmentación, se debe dar un repaso a la forma en que las direcciones virtuales son traducidas a direcciones reales, y para ellos se usa la figura 4.4. Prácticamente la traducción es igual que la llevada a cabo en la paginación pura, tomando en consideracióñ que el tamaño de los bloques a controlar por la tabla de traducción son variables, por lo cual, cada entrada en dicha tabla debe contener la longitud de cada segmento a controlar. Otra vez se cuenta con un registro base que contiene la dirección del comienzo de la tabla de segmentos. La dirección virtual se compone de un número de segmento (s) y un desplazamiento ( d ) para ubicar un byte (o palabra ) dentro de dicho segmento. Es importante que el desplazamiento no sea mayor que el tamaño del segmento, lo cual se controla simplemente checando que ese valor sea mayor que la dirección del inicio del segmento y menor que el inicio sumado al tamaño.
Una ves dada una dirección virtual v=( s,d ), se realiza la operación b + s para hallar el registro (o entrada de la tabla de segmentos ) que contiene la dirección de inicio del segmento en la memoria real, denotado por s'. Ya conociendo la dirección de inicio en memoria real s' sólo resta encontrar el byte o palabra deseada, lo cual se hace sumándole a s' el valor del desplazamiento, de modo que la dirección real ® r = s'+ d.
Cada entrada en la tabla de segmentos tiene un formato similar al mostrado en la figura 4.5. Se tienen campos que indican la longitud, los permisos, la presencia o ausencia y dirección de inicio en memoria real del segmento.
Según amplios experimentos [Deitel93] sugieren que un tamaño de páginas de 1024 bytes generalmente ofrece un desempeño muy aceptable. Intuitivamente parecería que el tener páginas del mayor tamaño posible haría que el desempeño fuera óptimo pero no es así, a menos que la página fuera del tamaño del proceso total. No es así con tamaños grandes de página menores que el proceso, ya que cuando se trae a memoria principal una página por motivo de un solo byte o palabra, se están trayendo muchísimos más bytes de los deseados. La dependencia entre el número de fallas respecto al tamaño de las páginas se muestra en la figura 4.6.
Un hecho notable en los sistemas que manejan paginación es que cuando el proceso comienza a ejecutarse ocurren un gran número de fallos de página, porque es cuando está referenciando muchas direcciones nuevas por vez primera, después el sistema se estabiliza, conforme el número de marcos asignados se acerca al tamaño del conjunto de trabajo.
El la figura 4.7 se muestra la relación entre el tiempo promedio entre fallas de página y el número de marcos de página asignados a un proceso. Allí se ve que el tiempo entre fallas decrece conforme se le asignan más páginas al proceso. La gráfica se curva en un punto, el cual corresponde a que el proceso tiene un número de páginas asignado igual al que necesita para almacenar su conjunto de trabajo. Después de eso, el asignarle a un proceso más páginas que las de su conjunto de trabajo ya no conviene, ya que el tiempo promedio entre fallas permanece sin mucha mejora. Un aspecto curioso de aumentar el número de páginas a un proceso cuando el algoritmo de selección de páginas candidatas a irse a disco es la primera en entrar primera en salir es la llamada `anomalía FIFO' a `anomalía de Belady'. Belady encontró ejemplos en los que un sistema con un número de páginas igual a tres tenía menos fallas de páginas que un sistema con cuatro páginas. El ejemplo descrito en [Tanxx] es injusto. Si se mira con cuidado, obviamente si se compara un sistema con 10 páginas contra otro de 5, ya de inicio el primer sistema tendrá 5 fallos de página más que el de 5, porque se necesitan diez fallos para cargarlo. A esto debería llamársele `anomalía de Belady con corrección.

3.3.2 Paginación.


Conceptos Básicos de Paginación

Frecuentemente se diferencia entre la “paginación pura” y la “combinación de paginación y segmentación.

Las páginas se transfieren del almacenamiento secundario al primario en bloques llamados “marcos de páginas”:
  • Tienen el mismo tamaño que las páginas.
  • Comienzan en direcciones del almacenamiento real que son múltiplos enteros del tamaño fijo de la página.
  • Podrá colocarse una nueva página dentro de cualquier “marco de página” o “celda de página” disponible.
La “traducción dinámica de direcciones” incluye:
  • Un proceso en ejecución hace referencia a una dirección virtual “v = (p,d)”
  • Un mecanismo de transformación de páginas busca la página “p” en la “tabla de páginas” y determina si la página “p” se encuentra en el marco de página “p ’ ”.
  • La dirección de almacenamiento real se forma por la concatenación de “p ’ ” y “d”.

La tabla de “mapa de páginas” debe indicar si se encuentra o no en el almacenamiento primario la página referenciada:
  • En caso afirmativo dónde está en la memoria real.
  • En caso negativo dónde puede estar en el almacenamiento secundario.
La dirección de almacenamiento primario “a”, donde comienza el marco de pagina “p ’ ” (suponiendo un tamaño de página “p”), está dada por: “a = (p) (p ’)”; se supone marcos de página numerados 0, 1, 2, etc.
Traducción de Direcciones de Paginación por Transformación Directa
Un proceso en ejecución hace referencia a la dirección virtual v = (p,d).
Antes que un proceso comience su ejecución, el S. O. carga la dirección de almacenamiento primario de la “tabla de mapa de páginas” en el “registro origen de la tabla de mapa de páginas”

La dirección base de la tabla de mapa de páginas es “b”.
El número de página es “p”.
La dirección en el almacenamiento primario de la entrada en la tabla de mapa de páginas para la página “p” es “b + p”:
  • Indica que el marco de página “p ’ ” corresponde a la página virtual.
  • “p ’ ” se concatena con el desplazamiento “d” par formar la dirección real “r”.
“Esto es un ejemplo de transformación directa debido a que la tabla de mapa de páginas contiene una entrada por cada una de las páginas del almacenamiento virtual de este proceso”.
La dirección virtual que se está traduciendo y la dirección base de la tabla de mapa de páginas son mantenidas en un registro de alta velocidad del control del procesador.
La tabla de mapa de páginas transformada directamente suele mantenerse en el almacenamiento primario:
  • Las referencias a esta tabla requieren un ciclo completo de almacenamiento primario, que generalmente es la parte más larga de un ciclo de ejecución de instrucciones.
  • Se requiere otro ciclo de ejecución de almacenamiento primario para la transformación de páginas, lo que puede ocasionar degradación equivalente a un 50%, para lo cual una solución sería tener la tabla completa de mapa de páginas de transformación directa en la “caché” de muy alta velocidad.
Traducción de Direcciones de Paginación por Transformación Asociativa
Una forma de acelerar la traducción dinámica de páginas consiste en colocar la tabla completa de mapa de páginas en un “almacenamiento asociativo” que tenga un tiempo de ciclo mucho más rápido que el almacenamiento primario.
Una variante es la “transformación asociativa pura”

Un programa en ejecución hace referencia a la dirección virtual v = (p,d).
Cada entrada en el almacenamiento asociativo se busca de forma simultánea para la página “p”:
  • Se obtiene “p ’ ” como el marco de página correspondiente a la página “p”.
  • Se concatena “p ’ ” con “d” formando la dirección real “r”.
Cada una de las células del almacenamiento asociativo se registra de manera simultánea:
  • Hace costoso el almacenamiento asociativo.
  • Implementar la transformación asociativa pura resulta demasiado costoso, tal lo ocurrido con la implementación de la transformación directa pura utilizando “caché”.
Traducción de Direcciones de Paginación por Combinación de Transformación Asociativa / Directa
Se utiliza un almacenamiento asociativo capaz de mantener solo un pequeño porcentaje del mapa completo de páginas para un proceso .

Las entradas de página contenidas en este mapa reducido corresponden solo a las páginas referenciadas recientemente:
  • Se presupone que una página recientemente referenciada tendrá posibilidades de serlo de nuevo próximamente.
  • Los rendimientos obtenidos con este esquema de mapa asociativo parcial superan aproximadamente en un 100 % a los rendimientos obtenidos con esquemas de mapa asociativo de página completo.
Un programa hace referencia a la dirección virtual v = (p,d).
El mecanismo de traducción de direcciones intenta encontrar la página “p” en el mapa de página asociativo parcial:
  • Si “p” se encuentra allí:
    • El mapa asociativo devuelve “p ’ ” como el número de marco de página correspondiente a la página virtual “p”.
    • “p ’ ” se concatena con el desplazamiento “d” para formar la dirección real “r” que corresponde a la dirección virtual v = (p,d).
  • Si “p” no se encuentra en el mapa de pagina parcial:
    • Se utiliza un mapa directo convencional.
    • La dirección “b” del registro de origen de la tabla de páginas se añade a “p” para localizar la entrada apropiada a la página “p” en la tabla de mapa de páginas de transformación directa del almacenamiento primario.
    • La tabla indica que “p ’ ” es el marco de página correspondiente a la página virtual “p”.
    • “p ’ ” se concatena con el desplazamiento “d” para formar la dirección real “r” correspondiente a la dirección virtual v = (p,d).
Compartimiento de Recursos en un Sistema de Paginación
En sistemas multiprogramados, especialmente en los de tiempo compartido, es común que más de un usuario estén ejecutando los mismos programas:
  • Para optimizar el uso de la memoria real se comparten las páginas que pueden ser compartidas:
    • El compartimiento debe ser cuidadosamente controlado para evitar que un proceso modifique datos que otro proceso esta leyendo.
    • Los programas se encuentran divididos en áreas separadas de “procedimiento” y “datos”.
    • Los procedimientos no modificables se llaman “procedimientos puros reentrantes”.
    • Los datos y procedimientos modificables no pueden ser compartidos.
    • Los datos no modificables (ej.: tablas fijas) son compartibles.
  • Se debe identificar cada página como compartible o no.
  • Habrá marcos (celdas) de páginas compartidos por varios procesos.

El compartimiento:
  • Reduce la cantidad de almacenamiento primario necesario para la ejecución eficaz de un grupo de procesos.
  • Puede hacer posible que un sistema determinado mantenga una cantidad mayor de usuarios (procesos).


Paginación pura

La paginación pura en el majejo de memoria consiste en que el sistema operativo divide dinámicamente los programas en unidades de tamaño fijo ( generalmente múltiplos de 1 kilobyte ) los cuales va a manipular de RAM a disco y viceversa. Al proceso de intercambiar páginas, segmentos o programas completos entre RAM y disco se le conoce como `intercambio' o `swapping'. En la paginación, se debe cuidar el tamño de las páginas, ya que si éstas son muy pequeñas el control por parte del sistema operativo para saber cuáles están en RAM y cuales en disco, sus direcciones reales, etc; crece y provoca mucha `sobrecarga' (overhead). Por otro lado, si las páginas son muy grandes, el overhead disminuye pero entonces puede ocurrir que se desperdicie memoria en procesos pequeños. Debe haber un equilibrio.

Uno de los aspectos más importantes de la paginación, asi como de cualquier esquema de memoria virtual, es la forma de traducir una dirección virtual a dirección real. Para explicarlo, obsérvese la figura
Como se observa, una dirección virtual `v' = ( b,d) está formada por un número de página virtual `b' y un desplazamiento `d'. Por ejemplo, si el sistema ofrece un espacio de direcciones virtuales de 64 kilobytes, con páginas de 4 kilobytes y la RAM sólo es de 32 kilobytes, entonces tenemos 16 páginas virtuales y 8 reales. La tabla de direcciones virtuales contiene 16 entradas, una por cada página virtual. En cada entrada, o registro de la tabla de direcciones virtuales se almacenan varios datos: si la página está en disco o en memoria, quién es el dueño de la página, si la página ha sido modificada o es de lectura nada mas, etc. Pero el dato que nos interesa ahora es el número de página real que le corresponde a la página virtual. Obviamente, de las 16 virtuales, sólo ocho tendrán un valor de control que dice que la página está cargada en RAM, así como la dirección real de la página, denotada en la figura 4.3 como b' . Por ejemplo, supóngase que para la página virtual número 14 la tabla dice que, efectivamente está cargada y es la página real 2 ( dirección de memoria 8192 ). Una vez encontrada la página real, se le suma el desplazamiento, que es la dirección que deseamos dentro de la página buscada ( b' + d ).
La tabla de direcciones virtuales a veces está ubicada en la misma meoria RAM, por lo cual se necesita saber en qué dirección comienza, en este caso, existe un registro con la dirección base denotada por la letra `a' en la figura 4.3.
Cuando se está buscando una página cualquiera y ésta no está cargada, surge lo que se llama un `fallo de página' (page fault ). Esto es caro para el manejador de memoria, ya que tiene que realizar una serie de pasos extra para poder resolver la dirección deseada y darle su contenido a quien lo pide. Primero, se detecta que la página no está presente y entonces se busca en la tabla la dirección de esta página en disco. Una vez localizada en disco se intenta cargar en alguna página libre de RAM. Si no hay páginas libres se tiene que escoger alguna para enviarla hacia el disco. Una vez escogida y enviada a disco, se marca su valor de control en la tabla de direcciones virtuales para indicar que ya no está en RAM, mientras que la página deseada se carga en RAM y se marca su valor para indicar que ahora ya está en RAM. Todo este procedimiento es caro, ya que se sabe que los accesos a disco duro son del orden de decenas de veces más lentos que en RAM. En el ejemplo anterior se mencionó que cuando se necesita descargar una página de RAM hacia disco se debe de hacer una elección. Para realizar esta elección existen varios algoritmos, los cuales se describen enseguida. _ La primera en entrar, primera en salir: Se escoge la página que haya entrado primero y esté cargada en RAM. Se necesita que en los valores de control se guarde un dato de tiempo. No es eficiente porque no aprovecha ninguna característica de ningún sistema. Es justa e imparcial. _ La no usada recientemente: Se escoge la página que no haya sido usada (referenciada) en el ciclo anterior. Pretende aprovechar el hecho de la localidad en el conjunto de trabajo.
·         La usada menos recientemente: Es parecida a la anterior, pero escoge la página que se usó hace más tiempo, pretendiendo que como ya tiene mucho sin usarse es muy probable que siga sin usarse en los próximos ciclos. Necesita de una búsqueda exhaustiva.
·         La no usada frecuentemente: Este algoritmo toma en cuenta no tanto el tiempo, sino el número de referencias. En este caso cualquier página que se use muy poco, menos veces que alguna otra.
·         La menos frecuentemente usada: Es parecida a la anterior, pero aquí se busca en forma exhaustiva aquella página que se ha usado menos que todas las demás.
·         En forma aleatoria: Elige cualquier página sin aprovechar nada. Es justa e imparcial, pero ineficiente.
Otro dato interesante de la paginación es que ya no se requiere que los programas estén ubicados en zonas de memoria adyacente, ya que las páginas pueden estar ubicadas en cualquier lugar de la memoria RAM.

3.3.1 Evaluación de las organizaciones de almacenamiento.


Introducción a la Organización del Almacenamiento Virtual

“Almacenamiento virtual ” significa la capacidad de direccionar un espacio de almacenamiento mucho mayor que el disponible en el almacenamiento primario de determinado sistema de computación .
Esta tecnología apareció en 1960 en la Universidad de Manchester (Inglaterra), en el sistema “Atlas”.
Los métodos más comunes de implementación son mediante:
  • Técnicas de “paginación”.
  • Técnicas de “segmentación”.
  • Una combinación de ambas técnicas.
Las direcciones generadas por los programas en su ejecución no son, necesariamente, aquellas contenidas en el almacenamiento primario (memoria real), ya que las direcciones virtuales suelen seleccionarse dentro de un número mucho mayor de direcciones que las disponibles dentro del almacenamiento primario.
La evolución en las organizaciones de almacenamiento puede resumirse como sigue:
  • Real:
    • Sistemas dedicados a un solo usuario.
  • Real:
    • Sistemas de multiprogramación en memoria real:
      • Multiprogramación en partición fija:
        • Absoluta.
        • Relocalizable (reubicable).
      • Multiprogramación en partición variable.
  • Virtual:
    • Multiprogramación en almacenamiento virtual:
      • Paginación pura.
      • Segmentación pura.
      • Combinación paginación / segmentación.
Conceptos Básicos de Almacenamiento Virtual

La clave del concepto de memoria (almacenamiento) virtual esta en la disociación:
  • De las direcciones a las que hace referencia un programa.
  • De las direcciones disponibles en la memoria real (almacenamiento primario).
Los principales conceptos son los siguientes:
  • “Direcciones virtuales”:
    • Son las referidas por un proceso en ejecución.
  • “Direcciones reales”:
    • Son las disponibles dentro del almacenamiento primario.
  • “Espacio de direcciones virtuales (v)” de un proceso:
    • Es el número de direcciones virtuales a que puede hacer referencia el proceso.
  • “Espacio de direcciones reales (r)” de un computador:
    • Es el número de direcciones reales disponibles en el ordenador.
Los procesos hacen referencia a direcciones virtuales pero éstas deben ejecutarse en el almacenamiento real:
  • Las direcciones virtuales deben ser transformadas dentro de las direcciones reales, mientras el proceso está en ejecución.
  • La traducción de direcciones deberá hacerse rápidamente para no degradar al sistema.
Existen varios medios para asociar las direcciones virtuales con las reales .
Los mecanismos de “traducción dinámica de direcciones” (dat) convierten las direcciones virtuales en reales al ejecutarse el proceso.
Las direcciones contiguas dentro del espacio de direcciones virtuales de un proceso no tienen por qué ser contiguas dentro del almacenamiento real, a esto se denomina “contigüidad artificial ” .

Organización del Almacenamiento de Niveles Múltiples

Se deben proporcionar los medios para retener programas y datos en un gran almacenamiento auxiliar para:
  • Permitir que el espacio de direcciones virtuales de un usuario sea mayor que el espacio de direcciones reales.
  • Soportar multiprogramación de forma efectiva en un sistema con muchos usuarios que compartan el almacenamiento real.
Se utiliza un esquema de almacenamiento de dos niveles .
  • Primer nivel: “almacenamiento real ”:
    • En él se ejecutan los procesos y en él deben estar los datos para que un proceso pueda referirse a ellos.

  • Segundo nivel: “almacenamiento auxiliar, secundario o adicional ”:
    • Generalmente consta de discos de gran capacidad que pueden mantener los programas y datos que no caben al mismo tiempo en el más limitado almacenamiento real.
Cuando se va a ejecutar un proceso su código y datos se pasan al almacenamiento principal.
El almacenamiento real es compartido por varios procesos:
  • Cada proceso puede tener un espacio de direcciones virtuales mucho mayor que el almacenamiento real.
  • Solo se mantiene al mismo tiempo una pequeña parte de los programas y datos de cada proceso en el almacenamiento real.
Transformación de Bloques
Los mecanismos de traducción dinámica de direcciones deben mantener “mapas” que ilustren qué direcciones del almacenamiento virtual se encuentran en el almacenamiento real y dónde se encuentran .
La información se agrupa en “bloques”:
  • El sistema está informado del lugar del almacenamiento real donde han sido colocados los bloques de almacenamiento virtual.
  • Cuanto mayor sea el bloque menor será la fracción del almacenamiento real que debe dedicarse a contener la información del mapa.
  • Con bloques grandes:
    • Se reduce la sobrecarga de almacenamiento del mecanismo de transformación.
    • Se incrementa el tiempo de transferencia entre los almacenamientos secundario y primario.
    • Consumen más almacenamiento real pudiendo limitar el número de procesos que pueden compartirlo.
  • Los bloques pueden ser de tamaño:
    • Igual : se denominan “páginas” y la organización de almacenamiento virtual asociada se denomina “paginación”.
    • Diferente: se denominan “segmentos” y la organización de almacenamiento virtual asociada se denomina “segmentación”.
  • Se pueden combinar ambas técnicas: segmentos de tamaño variable compuestos de páginas de tamaño fijo.
Las direcciones son “bidimensionales”, es decir que una dirección virtual “v” se indica por un par ordenado “(b,d)”, donde:
  • “b”: número del bloque donde reside.
  • “d”: desplazamiento a partir del inicio del bloque.
La traducción de una dirección virtual “v = (b,d)” a la dirección real “r” considera lo siguiente
  • Cada proceso tiene su “tabla de mapa de bloques” mantenida por el sistema en el almacenamiento real.
  • Un registro especial del procesador llamado “registro origen de la tabla de bloques” se carga con la dirección real “a” de la “tabla de mapa de bloques”:
    • Contiene una entrada para cada bloque del proceso.
    • Las entradas se mantienen en orden secuencial para el bloque 0, bloque 1, etc.
    • Se añade el bloque número “b” a la dirección base “a” de la “tabla de bloques” para formar la dirección real de la entrada de la “tabla de mapa de bloques” para el bloque “b”:
      • Contiene la dirección real “b ’ ” para el bloque “b”.
      • El desplazamiento “d” se añade a la dirección de inicio del bloque, “b ’ ”, para formar la “dirección real” deseada: “r = b ’ + d”.
La transformación de bloques se efectúa en forma dinámica mientras se ejecuta un proceso, por lo cual, si la implementación no es eficiente, su sobrecarga puede causar una degradación del rendimiento que podría eliminar en parte las ventajas de la utilización del almacenamiento virtual.