martes, 19 de noviembre de 2013

Unidad 3. Administración de memoria.

3.1 Política y filosofía.
POLITICAS Y FILOSOFIA DE LA ADMINISTRACION DE LA MEMORIA.
La memoria principal es el lugar donde el CPU lee las instrucciones a ejecutar, asi como algunos datos a emplear.
Una de las funciones basicas que debe implementar un SO es la Administracion de la Memoria para tener un control sobre los lugares donde estan almacenados los procesos y datos que actualmente se estan utilizando.
EL retiro del administrador de la memoria del kernel es un ejemplo de la separación de política y mecanismo. Las decisiones acercá de que proceso se colocará en que sitio de la memoria (política) son tomadas por el administrador de la mempria. La colocación real de mapa de memoria para los procesos (mecanismo) es realizado por la tarea contenida en kernel. Esta división facilita en forma relativa el cambio de la política de administración de la memoria (algoritmos,ect) sin tener que modificar los estratos inferiores del sistema operativo.
3.2 Memoria real.
Memoria real

La memoria real o principal es en donde son ejecutados los programas y procesos de una computadora y es el espacio real que existe en memoria para que se ejecuten los procesos. Por lo general esta memoria es de mayor costo que la memoria secundaria, pero el acceso a la información contenida en ella es de más rápido acceso. Solo la memoria cache es más rápida que la principal, pero su costo es a su vez mayor.

3.2.1 Administración de almacenamiento.
Asignación del espacio de almacenamiento
El subsistema de archivos se debe encargar de localizar espacio libre en los medios de almacenamiento para guardar archivos y para después borrarlos, renombrarlos o agrandarlos. Para ello se vale de localidades especiales que contienen la lista de archivos creados y por cada archivo una serie de direcciones que contienen los datos de los mismos. Esas localidades especiales se llaman directorios.


Organización y Administración del Almacenamiento 
Organización del Almacenamiento 

Históricamente el almacenamiento principal se ha considerado como un recurso costoso, por lo cual su utilización debía optimizarse. 
Por organización del almacenamiento se entiende la manera de considerar este almacenamiento: 

¿ se coloca un solo programa de usuario o varios ?.
Si se encuentran varios programas de usuario:
¿ se concede a cada uno la misma cantidad de espacio o se divide el almacenamiento en porciones o “particiones” de diferente tamaño ?.
¿ se utilizará un esquema rígido de número y tamaño de particiones o un esquema dinámico y adaptable ?.
¿ se requerirá que los trabajos de los usuarios sean diseñados para funcionar en una partición específica o se permitirá que se ejecuten en cualquiera donde quepan ?.
¿ se requerirá o no que cada trabajo sea colocado en un bloque contiguo de memoria ?.
Administración del Almacenamiento 
Independientemente del esquema de organización hay que decidir las estrategias que se utilizarán para optimizar el rendimiento. 
Las “estrategias de administración” deben considerar: 

¿ cuándo se consigue un nuevo programa para colocar en la memoria ?:
¿ cuando el sistema lo pide específicamente o se intenta anticiparse a las peticiones ?.
¿ dónde se colocará el programa que se ejecutará a continuación ?:
¿ se prioriza el tiempo de carga o la optimización en el uso del almacenamiento ?.
¿ con qué criterio se desplazarán programas ?.
3.2.2 Jerarquía.

Jerarquía de Almacenamiento 

Los programas y datos tienen que estar en la memoria principal para poder ejecutarse o ser referenciados  
Los programas y datos que no son necesarios de inmediato pueden mantenerse en el almacenamiento secundario. 
El almacenamiento principal es más costoso y menor que el secundario pero de acceso más rápido. 
Los sistemas con varios niveles de almacenamiento requieren destinar recursos para administrar el movimiento de programas y datos entre niveles . 

Un nivel adicional es el “caché” o memoria de alta velocidad, que posee las siguientes características: 
Es más rápida y costosa que la memoria principal.
Impone al sistema un nivel más de traspaso:
Los programas son traspasados de la memoria principal al caché antes de su ejecución.
Los programas en la memoria caché ejecutan mucho más rápido que en la memoria principal.
Al utilizar memoria caché se espera que:
La sobrecarga que supone el traspaso de programas de un nivel de memoria a otro sea mucho menor que la mejora en el rendimiento obtenida por la posibilidad de una ejecución mucho más rápida en la caché.
3.2.3 Estrategia de administración de memoria.


Están dirigidas a la obtención del mejor uso posible del recurso del almacenamiento principal . 
Se dividen en las siguientes categorías: 

Estrategias de búsqueda:
Estrategias de búsqueda por demanda.
Estrategias de búsqueda anticipada.
Estrategias de colocación.
Estrategias de reposición.
Las “estrategias de búsqueda” están relacionadas con el hecho de cuándo obtener el siguiente fragmento de programa o de datos para su inserción en la memoria principal.
En la “búsqueda por demanda” el siguiente fragmento de programa o de datos se carga al almacenamiento principal cuando algún programa en ejecución lo referencia. 
Se considera que la “búsqueda anticipada” puede producir un mejor rendimiento del sistema. 
Las “estrategias de colocación” están relacionadas con la determinación del lugar de la memoria donde se colocará (cargará) un programa nuevo. 
Las “estrategias de reposición” están relacionadas con la determinación de qué fragmento de programa o de datos desplazar para dar lugar a los programas nuevos. 

Intercambio
El objetivo del intercambio es dar cabida a la ejecución de mas aplicaciones de las que pueden residir simultáneamente en la memoria del sistema:
Consiste en trasladar el código y los datos de un proceso completo de memoria al sistema de almacenamiento secundario , para cargar otro previamente almacenado, no permite a un proceso utilizar mas memoria RAM de la que realmente existe en el sistema. Esta técnica puede ser ineficiente ya que se tiene que hacer el intercambio completo del proceso, aunque éste solo vaya a ejecutar una pequeña porción del código.
Durante el intercambio un proceso puede ser sacado temporalmente de memoria y llevado a un lugar especial del disco y posteriormente vuelto a memoria y continuada su ejecución..
El lugar de almacenamiento temporal suele ser un espacio suficientemente grande como para acomodar copias de las imágenes de meoria de todos los usuarios.
Asignacion Contigua
La memoria principal normalmente se divide en dos particiones:

         Sistema operativo residente, normalmente en la parte baja de memoria con los vectores de interrupción.
         Procesos de usuario en la parte alta.
Asignación de partición simple:
Puede utilizarse un esquema de registro de relocalización y limite para proteger un proceso de usuario de otro y de cambios del código y datos del sistema operativo .
El registro de relocalización contiene la dirección contiene la dirección física mas pequeña; el registro limite contiene el rango de las direcciones lógicas cada dirección lógica debe ser menor al registro limite
Asignación de particiones múltiples:
Bloques de distintos tamaños están distribuidos en memoria , cuando llega un proceso se le asigna un hueco suficientemente grande para acomodarle.
El sistema operativo debe tener información sobre:

Particiones asignadas
Particiones libres (huecos)
Asignación de partición dinámica
El proceso de compactación es una instancia particular del problema de asignación de memoriadinámica, el cual es el cómo satisfacer una necesidad de tamaño n con una lista de huecos libres. Existen muchas soluciones para el problema. El conjunto de huecos es analizado para determinar cuál hueco es el más indicado para asignarse. Las estrategias más comunes para asignar algún hueco de la tabla son:

         Primer ajuste: Consiste en asignar el primer hueco con capacidad suficiente. La búsqueda puede iniciar ya sea al inicio o al final del conjunto de huecos o en donde terminó la última búsqueda. La búsqueda termina al encontrar un hueco lo suficientemente grande.
         Mejor ajuste: Busca asignar el espacio más pequeño de los espacios con capacidad suficiente. La búsqueda se debe de realizar en toda la tabla, a menos que la tabla esté ordenada por tamaño. Esta estrategia produce el menor desperdicio de memoria posible.
         Peor ajuste: Asigna el hueco más grande. Una vez más, se debe de buscar en toda la tabla de huecos a menos que esté organizada por tamaño. Esta estrategia produce los huecos de sobra más grandes, los cuales pudieran ser de más uso si llegan procesos de tamaño mediano que quepan en ellos.
Se ha demostrado mediante simulacros que tanto el primer y el mejor ajuste son mejores que el peor ajuste en cuanto a minimizar tanto el tiempo del almacenamiento. Ni el primer o el mejor ajuste es claramente el mejor en términos de uso de espacio, pero por lo general el primer ajuste es más rápido.
Problema: La fragmentación.
La fragmentación es la memoria que queda desperdiciada al usar los métodos de gestión de memoria que se vieron en los métodos anteriores. Tanto el primer ajuste, como el mejor y el peor producen fragmentación externa.
La fragmentación es generada cuando durante el reemplazo de procesos quedan huecos entre dos o más procesos de manera no contigua y cada hueco no es capaz de soportar ningún proceso de la lista de espera.
La fragmentación puede ser:

         Fragmentación Externa: existe el espacio total de memoria para satisfacer un requerimiento, pero no es contigua.
         Fragmentación Interna: la memoria asignada puede ser ligeramente mayor que la requerida; esta referencia es interna a la partición, pero no se utiliza.
La fragmentación externa se puede reducir mediante la compactación para colocar toda la memoria libre en un solo gran bloque, pero est a solo es posible si la relocalización es dinámica y se hace en tiempo de ejecución.
Es una técnica de manejo de memoria, en la cual el espacio de memoria se divide en secciones físicas de igual tamaño, denominadas marcos de página. Los programas se dividen en unidades lógicas, denominadas páginas, que tienen el mismo tamaño que los marcos de páginas. De esta forma, se puede cargar una página de información en cualquier marco de página.
Las páginas sirven como unidad de almacenamiento de información y de transferencia entre memoria principal y memoria auxiliar o secundaria. Cada marco se identifica por la dirección de marco, que esta en la posición física de la primera palabra en el marco de página.
Las páginas de un programa necesitan estar contiguamente en memoria, aunque el programador lo observe de esta forma. Los mecanismos de paginación permiten la correspondencia correcta entre las direcciones virtuales (dadas por los programas) y las direcciones reales de la memoria que se reverencien.
Cada pagina consiste en z palabras contiguas; un espacio de direcciones N de un programa consiste de n paginas (0,1,2,3…n-1) (n*z direcciones virtuales) y el espacio de memoria consiste de m marcos de paginas (0,z,2z,…,(m-1)z)(m*z posiciones). Una dirección virtual a es equivalente a una dirección dada como una dupla (p, d), en la cual p es el número de la página y d el número de la palabra dentro de la página, de acuerdo con la relación:
a=p*z+d (0<=d<z)
p=(a/z) (parte entera de la division)
d=a mod z (resto de divisor a/z)
En las maquinas que usan aritmética binaria, el calculo de (p, d) es trivial, si z es potencia de 2. Por ejemplo, si el campo de direcciones de la instrucción es de m bits (m>6), los cuatro bits mas significativos indican el numero de la pagina y los m-4 bits restantes, el desplazamiento.
Para tener el control de las páginas, debe mantenerse una tabla en memoria que se denomina tabla de Mapas de Pagina (PMT) para cada uno de los procesos.
Hasta ahora, los métodos que hemos visto de la administración de la memoria principal, nos han dejado con un problema: fragmentación, (huecos en la memoria que no pueden usarse debido a lo pequeño de su espacio) lo que nos provoca un desperdicio de memoria principal.
Una posible solución para la fragmentación externa es permitir que espacio de direcciones lógicas lleve a cabo un proceso en direcciones no contiguas, así permitiendo al proceso ubicarse en cualquier espacio de memoria física que esté disponible, aunque esté dividida. Una forma de implementar esta solución es a través del uso de un esquema de paginación. La paginación evita el considerable problema de ajustar los pedazos de memoria de tamaños variables que han sufrido los esquemas de manejo de memoria anteriores. Dado a sus ventajas sobre los métodos previos, la paginación, en sus diversas formas, es usada en muchos sistemas operativos.
Al utilizar la memoria virtual, las direcciones no pasan en forma directa al bus de memoria, sino que van a una unidad administradora de la memoria (MMU –Memory Management Unit). Estas direcciones generadas por los programas se llaman direcciones virtuales y conforman el hueco de direcciones virtuales. Este hueco se divide en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página o frames. Las páginas y los frames tienen siempre el mismo tamaño.
Tablas de páginas
Cada página tiene un número que se utiliza como índice en la tabla de páginas, lo que da por resultado el número del marco correspondiente a esa página virtual. Si el bit presente / ausente es 0, se provoca un señalamiento (trap) hacia el sistema operativo. Si el bit es 1, el número de marco que aparece en la tabla de páginas se copia en los bits de mayor orden del registro de salida, junto con el ajuste (offset) de 12 bits, el cual se copia sin modificaciones de la dirección virtual de entrada. Juntos forman una dirección física de 15 bits. El registro de salida se coloca entonces en el bus de la memoria como la dirección en la memoria física.
En teoría, la asociación de las direcciones virtuales con las físicas se efectúa según lo descrito. El número de página virtual se divide en un número de página virtual (los bits superiores)y un ajuste (los bits inferiores). El número de página virtual se utiliza como un índice en la tabla de páginas para encontrar la entrada de esa página virtual. El número de marco (si existe) se determina a partir de la tabla de páginas. El número de marco se asocia al extremo superior del ajuste y reemplaza al número de página virtual para formar una dirección física que se puede enviar a la memoria.
La finalidad de la tabla de páginas es asociar las páginas virtuales con los marcos. En términos matemáticos, la tabla de páginas es una función, cuyo argumento es el número de página virtual y como resultado el número del marco físico. Mediante el resultado de esta función, se puede reemplazar el campo de la página virtual de una dirección virtual por un campo de marco, lo que produce una dirección en la memoria física. Sin embargo hay que enfrentar dos aspectos fundamentales:

La tabla de páginas puede ser demasiado grande.
La asociación debe ser rápida.
El primer punto proviene del hecho de que las computadoras modernas utilizan direcciones virtuales de al menos 32 bits. Por ejemplo, si el tamaño de página es de 4K, un hueco de direcciones de 32 bits tiene un millón de páginas; en el caso de un hueco de direcciones de 64 bits, se tendría más información de la que uno quisiera contemplar.
El segundo punto es consecuencia del hecho de que la asociación virtual – física debe hacerse en cada referencia a la memoria. Una instrucción común tiene una palabra de instrucción y también un operando de memoria. Entonces es necesario hacer una, dos o más referencias a la tabla de páginas por cada instrucción.
Características de la paginación:

         El espacio de direcciones lógico de un proceso puede ser no contiguo.
         Se divide la memoria física en bloques de tamaño fijo llamados marcos (frames).
         Se divide la memoria en bloques de tamaño llamados paginas.
         Se mantiene información en los marcos libres.
         Para correr un programa de n paginas de tamaño, se necesitan encontrara n marcos y cargar el programa.
         Se establece una tabla de paginas para trasladar las direcciones lógicas a físicas.
         Se produce fragmentación interna.
Ventajas de la paginación
Es posible comenzar a ejecutar un programa, cargando solo una parte del mismo en memoria, y el resto se cargara bajo la solicitud.
No es necesario que las paginas estén contiguas en memoria, por lo que no se necesitan procesos de compactación cuando existen marcos de paginas libres dispersos en la memoria.
Es fácil controlar todas las páginas, ya que tienen el mismo tamaño.
El mecanismo de traducción de direcciones (DAT) permite separar los conceptos de espacio de direcciones y espacios de memoria. Todo el mecanismo es transparente al usuario.
Se libera al programador de la restricción de programar para un tamaño físico de memoria, con lo que s e aumenta su productividad. Se puede programar en función de una memoria mucho más grande a la existente.
Al no necesitarse cargar un programa completo en memoria para su ejecución, se puede aumentar el numero de programas multiprogramándose.
Se elimina el problema de fragmentación externa.
Desventajas de la paginación
El costo de hardware y software se incrementa, por la nueva información que debe manejarse y el mecanismo de traducción de direcciones necesario. Se consume mucho mas recursos de memoria, tiempo en el CPU para su implantación.
Se deben reservar áreas de memoria para las PMT de los procesos. Al no ser fija el tamaño de estas, se crea un problema semejante al de los programas (como asignar un tamaño óptimo sin desperdicio de memoria, u "ovearhead" del procesador).
Aparece el problema de fragmentación interna. Así, si se requieren 5K para un programa, pero las paginas son de 4K, deberán asignárseles 2 paginas (8k), con lo que quedan 3K sin utilizar. La suma de los espacios libres dejados de esta forma puede ser mayor que el de varias paginas, pero no podrá ser utilizados. Debe asignarse un tamaño promedio a las páginas, evitando que si son muy pequeñas, se necesiten TABLAS BMT y PMT muy grandes, y si son muy grandes, se incremente el grado de fragmentación interna.
Traducción de Direcciones
La dirección generada por la CPU se divide en:

         Numero de pagina (p): utilizado como indice en la tabla de pagins que contiene la dirección base de cada pagina en la memoria fisica.
         Offset de la pagina (d): combinado con la dirección base dfine la direccion fisica que será enviada a la unidad de memoria.
Ejemplo de paginación:
Es un esquema de manejo de memoria mediante el cual la estructura del programa refleja su división lógica; llevándose a cabo una agrupación lógica de la información en bloques de tamaño variable denominados segmentos. Cada uno de ellos tienen información lógica del programa: subrutina, arreglo, etc. Luego, cada espacio de direcciones de programa consiste de una colección de segmentos, que generalmente reflejan la división lógica del programa.
La segmentación permite alcanzar los siguientes objetivos:

Modularidad de programas: cada rutina del programa puede ser un bloque sujeto a cambios y recopilaciones, sin afectar por ello al resto del programa.
Estructuras de datos de largo variable: ejm. Stack, donde cada estructura tiene su propio tamaño y este puede variar.
Protección: se puede proteger los módulos del segmento contra accesos no autorizados.
Comparición: dos o más procesos pueden ser un mismo segmento, bajo reglas de protección; aunque no sean propietarios de los mismos.
Enlace dinámico entre segmentos: puede evitarse realizar todo el proceso de enlace antes de comenzar a ejecutar un programa. Los enlaces se establecerán solo cuando sea necesario.
Ventajas de la segmentación
El esquema de segmentación ofrece las siguientes ventajas:

         El programador puede conocer las unidades lógicas de su programa, dándoles un tratamiento particular.
         Es posible compilar módulos separados como segmentos el enlace entre los segmentos puede suponer hasta tanto se haga una referencia entre segmentos.
         Debido a que es posible separar los módulos se hace más fácil la modificación de los mismos. Cambios dentro de un modulo no afecta al resto de los módulos.
         Es fácil el compartir segmentos.
         Es posible que los segmentos crezcan dinámicamente según las necesidades del programa en ejecución.
         Existe la posibilidad de definir segmentos que aun no existan. Así, no se asignara memoria, sino a partir del momento que sea necesario hacer usos del segmento. Un ejemplo de esto, serian los arreglos cuya dimensión no se conoce hasta tanto no se comienza a ejecutar el programa. En algunos casos, incluso podría retardar la asignación de memoria hasta el momento en el cual se referencia el arreglo u otra estructura de dato por primera vez.
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.
Estas desventajas tratan de ser minimizadas, bajo la técnica conocida como Segmentación paginada.
Paginación y segmentación son técnicas diferentes, cada una de las cuales busca brindar las ventajas enunciadas anteriormente.
Para la segmentación se necesita que estén cargadas en memoria, áreas de tamaños variables. Si se requiere cargar un segmento en memoria; que antes estuvo en ella y fue removido a memoria secundaria; se necesita encontrar una región de la memoria lo suficientemente grande para contenerlo, lo cual no es siempre factible; en cambio "recargar" una pagina implica solo encontrar un merco de pagina disponible.
A nivel de paginación, si quiere referenciar en forma cíclicas n paginas, estas deberán ser cargadas una a una generándose varias interrupciones por fallas de paginas; bajo segmentación, esta pagina podría conformar un solo segmento, ocurriendo una sola interrupción, por falla de segmento. No obstante, si bajo segmentación, se desea acceder un área muy pequeña dentro de un segmento muy grande, este deberá cargarse completamente en memoria, desperdiciándose memoria; bajo paginación solo se cargara la página que contiene los ítems referenciados.
Puede hacerse una combinación de segmentación y paginación para obtener las ventajas de ambas. En lugar de tratar un segmento como una unidad contigua, este puede dividirse en páginas. Cada segmento puede ser descrito por su propia tabla de páginas.
Los segmentos son usualmente múltiplos de páginas en tamaño, y no es necesario que todas las páginas se encuentren en memoria principal a la vez; además las páginas de un mismo segmento, aunque se encuentren contiguas en memoria virtual; no necesitan estarlo en memoria real.
Las direcciones tienen tres componentes: (s, p,d), donde la primera indica el numero del segmento, la segunda el numero de la pagina dentro del segmento y la tercera el desplazamiento dentro de la pagina. Se deberán usar varias tablas:

         SMT (tabla de mapas de segmentos): una para cada proceso. En cada entrada de la SMT se almacena la información descrita bajo segmentación pura, pero en el campo de dirección se indicara la dirección de la PMT (tabla de mapas de páginas) que describe a las diferentes páginas de cada segmento.
         PMT (tabla de mapas de páginas): una por segmento; cada entrada de la PMT describe una página de un segmento; en la forma que se presento la pagina pura.
         TBM (tabla de bloques de memoria): para controlar asignación de páginas por parte del sistema operativo.
         JT (tabla de Jobs): que contiene las direcciones de comienzo de cada una de las SMT de los procesos que se ejecutan en memoria.
En el caso, de que un segmento sea de tamaño inferior o igual al de una pagina, no se necesita tener la correspondiente PMT, actuándose en igual forma que bajo segmentación pura; puede arreglarse un bit adicional (S) a cada entrada de la SMT, que indicara si el segmento esta paginado o no.
Ventajas de la segmentación paginada
El esquema de segmentación paginada tiene todas las ventajas de la segmentación y la paginación:

         Debido a que los espacios de memorias son segmentados, se garantiza la facilidad de implantar la comparticion y enlace.
         Como los espacios de memoria son paginados, se simplifican las estrategias de almacenamiento.
         Se elimina el problema de la fragmentación externa y la necesidad de compactación.
Desventajas de la segmentación paginada
         Las tres componentes de la dirección y el proceso de formación de direcciones hace que se incremente el costo de su implantación. El costo es mayor que en el caso de de segmentación pura o paginación pura.
         Se hace necesario mantener un número mayor de tablas en memoria, lo que implica un mayor costo de almacenamiento.
Sigue existiendo el problema de fragmentación interna de todas- o casi- todas las páginas finales de cada uno de los segmentos. Bajo paginación pura se desperdician solo la última página asignada, mientras que bajo segmentación – paginada el desperdicio puede ocurrir en todos los segmentos asignados.
3.2.4 Asignación contigua v.s. no contigua.

Para asignarle espacio a los archivos existen tres criterios generales que se describen enseguida.

         Asignación contigua: Cada directorio contiene la los nombres de archivos y la dirección del bloque inicial de cada archivo, así como el tamaño total de los mismos. Por ejemplo, si un archivo comienza en el sector 17 y mide 10 bloques, cuando el archivo sea accesado, el brazo se moverá inicialmente al bloque 17 y de ahí hasta el 27. Si el archivo es borrado y luego creado otro más pequeño, quedarán huecos inútiles entre archivos útiles, lo cual se llama fragmentación externa.
         Asignación encadenada: Con este criterio los directorios contienen los nombres de archivos y por cada uno de ellos la dirección del bloque inicial que compone al archivo. Cuando un archivo es leído, el brazo va a esa dirección inicial y encuentra los datos iniciales junto con la dirección del siguiente bloque y así sucesivamente. Con este criterio no es necesario que los bloques estén contiguos y no existe la fragmentación externa, pero en cada "eslabón" de la cadena se desperdicia espacio con las direcciones mismas. En otras palabras, lo que se crea en el disco es una lista ligada.
         Asignación con índices ( indexada ): En este esquema se guarda en el directorio un bloque de índices para cada archivo, con apuntadores hacia todos sus bloques constituyentes, de mabnera que el acceso directo se agiliza notablemente, a cambio de sacrificar varios bloques para almacenar dichos apuntadores. Cuando se quiere leer un archivo o cualquiera de sus partes, se hacen dos accesos: uno al bloque de índices y otro a la dirección deseada. Este es un esquema excelente para archivos grandes pero no para pequeños, porque la relación entre bloques destinados para índices respecto a los asignados para datos es incosteable.
Asignación Contigua de Almacenamiento Versus No Contigua 
En la “asignación contigua” cada programa ocupa un bloque contiguo y sencillo de localizaciones de almacenamiento. 
En la “asignación no contigua” un programa se divide en varios bloques o “segmentos” que pueden almacenarse en direcciones que no tienen que ser necesariamente adyacentes, por lo que es más compleja pero más eficiente que la asignación continua. 
Asignación Contigua de Almacenamiento de Un Solo Usuario 
Se consideran S. O. que ya poseen desarrollado el “sistema de control de entrada / salida”: IOCS: input / output control system 


El tamaño de los programas está limitado por la cantidad de memoria principal, pero se puede superar este límite con técnicas de “recubrimientos”, con las siguientes características 

Si una sección particular del programa ya no es necesaria, se carga otra sección desde el almacenamiento secundario ocupando las áreas de memoria liberadas por la sección que ya no se necesita.
La administración manual por programa del recubrimiento es complicada y dificulta el desarrollo y el mantenimiento.

Protección en los sistemas de un solo usuario 
El usuario tiene un completo control sobre la totalidad del almacenamiento principal: 

El almacenamiento se divide en porciones que contienen el S. O., el programa del usuario y una porción sin usar.
El programa del usuario podría destruir áreas del S. O. que podrían:
Detener el sistema.
Producir salidas erróneas.
El S. O. debe estar protegido contra el proceso usuario:
La protección se instrumenta mediante un “registro de límites” incorporado a la cpu:
Contiene la dirección de la instrucción más alta utilizada por el S. O.
Si se intenta ingresar al S. O. la instrucción es interceptada y el proceso finaliza.
Procesamiento por lotes de flujo único
Los sistemas de un solo usuario se dedican a un trabajo durante más tiempo del que toma su ejecución. 
Los trabajos requieren de: 

“tiempo de instalación”: el necesario para preparar el entorno operativo requerido.
“tiempo de descarga”: el necesario para desmontar el entorno operativo que fue requerido.
Durante la instalación y descarga de los trabajos la cpu no está ejecutando dichos trabajos requeridos, por lo cual:
Automatizar la “transición de trabajo a trabajo” reduce la cantidad de tiempo perdido entre trabajos.
Surgieron los sistemas de “procesamiento por lotes”.
En el “procesamiento por lotes de flujo único” los trabajos se agrupan en “lotes” encolándose para su ejecución.
El “procesador de flujos de trabajos”: 
Lee las instrucciones del “lenguaje de control de trabajos”.
Facilita la preparación del trabajo siguiente.
Emite instrucciones al operador del sistema.
Automatiza funciones anteriormente manuales.
Cuando finaliza un trabajo efectúa las “operaciones de mantenimiento” apropiadas para facilitar la transición del siguiente trabajo.


MÉTODOS DE ASIGNACIÓN DE ESPACIO EN DISCO.
    Un método de asignación de espacio en disco determina la manera en que un Sistema Operativo controla los lugares del disco ocupados por cada archivo de datos. Se debe controlar básicamente la identificación del archivo, sector de inicio y sector final. 
    Para el control del espacio ocupado en disco se puede utilizar como base alguno de los métodos teóricos: Asignación Contigua, Asignación Ligada, Asignación Indexada. 
  
ASIGNACIÓN CONTIGUA. 
Este método consiste en asignar el espacio en disco de tal manera que las direcciones de todos los bloques correspondientes a un archivo definen un orden lineal.

3.2.5 Multiprogramación de partición fija, partición variable, con intercambio de almacenamiento


La memoria se divide en particiones de tamaño fijo (puede ser distinto el tamaño de cada partición).
Originalmente los programas se compilaban y link editaban para ejecutar en una partición en particular (direcciones absolutas). Posteriormente los compiladores y link editores generan código reubicable para que un programa pudiera ejecutar en cualquier partición de memoria suficientemente grande.
Con esta estructura de administración de memoria se desperdicia memoria y tiempo de CPU (si hay un programa corriendo los demás quedan encolados aunque haya otra partición libre).
Cada programa o usuario utiliza tanta memoria como sea necesaria siempre que quepa en el almacenamiento real. Cuando los programas van terminando su ejecución se van generando agujeros en memoria.
Particiones fijas o particiones variables
En el esquema de la multiprogramación en memroia real se manejan dos alternativas para asignarle a cada programa su partición correspondiente: particiones de tamaño fijo o particiones de tamaño variable. La alternativa más simple son las particiones fijas. Dichas particiones se crean cuando se enciende el equipo y permanecerán con los tamaños iniciales hasta que el equipo se apague. Es una alternativa muy vieja, quien hacía la división de particiones era el operador analizando los tamaños estimados de los trabajos de todo el día. Por ejemplo, si el sistema tenía 512 kilobytes de RAM, podia asignar 64 k para el sistema operativo, una partición más de 64 k, otra de 128k y una mayor de 256 k. Esto era muy simple, pero inflexible, ya que si surgían trabajos urgentes, por ejemplo, de 400k, tenían que esperar a otro día o reparticionar, inicializando el equipo desde cero. La otra alternativa, que surgió después y como necesidad de mejorar la alternativa anterior, era crear particiones contiguas de tamaño variable. Para esto, el sistema tenía que mantener ya una estructura de datos suficiente para saber en dónde habían huecos disponibles de RAM y de dónde a dónde habían particiones ocupadas por programas en ejecución. Así, cuando un programa requería ser cargado a RAM, el sistema analizaba los huecos para saber si había alguno de tamaño suficiente para el programa que queria entrar, si era así, le asignaba el espacio. Si no, intentaba relocalizar los programas existentes con el propósito de hacer contiguo todo el espacio ocupado, así como todo el espacio libre y así obtener un hueco de tamaño suficiente. Si aún así el programa no cabía, entonces lo bloqueaba y tomaba otro. El proceso con el cual se juntan los huecos o los espacios ocupados se le llama `compactación'. El lector se habrá dado cuenta ya de que surgen varios problemas con los esquemas de particiones fijas y particiones variables: ø En base a qué criterio se elige el mejor tamaño de partición para un programa ? Por ejemplo, si el sistema tiene dos huecos, uno de 18k y otro de 24 k para un proceso que desea 20 k, ø Cual se le asigna ? Existen varios algoritmos para darle respuesta a la pregunta anterior, los cuales se ennumeran y describen enseguida.

         Primer Ajuste: Se asigna el primer hueco que sea mayor al tamaño deseado.
         Mejor Ajuste: Se asigna el hueco cuyo tamaño exceda en la menor cantidad al tamaño deseado. Requiere de una búsqueda exhaustiva.
         Peor Ajuste: Se asigna el hueco cuyo tamaño exceda en la mayor cantidad al tamaño deseado. Requiere también de una búsqueda exhaustiva.
         El Siguiente Ajuste: Es igual que el `primer ajuste' con la diferencia que se deja un apuntador al lugar en donde se asignó el último hueco para realizar la siguiente búsqueda a partir de él.
         Ajuste Rápido: Se mantienen listas ligadas separadas de acuerdo a los tamaños de los huecos, para así buscarle a los procesos un hueco más rápido en la cola correspondiente.
Otro problema que se vislumbra desde aquí es que, una vez asignado un hueco, por ejemplo, con "el peor ajuste", puede ser que el proceso requiriera 12 kilobytes y que el hueco asignado fuera de 64 kilobytes, por lo cual el proceso va a desperdiciar una gran cantidad de memoria dentro de su partición, lo cual se le llama `fragmentación interna'.
Por otro lado, conforme el sistema va avanzando en el día, finalizando procesos y comenzando otros, la memoria se va configurando como una secuencia contigua de huecos y de lugares asignados, provocando que existan huecos, por ejemplo, de 12 k, 28k y 30 k, que sumados dan 70k, pero que si en ese momento llega un proceso pidiéndolos, no se le pueden asignar ya que no son localidades contiguas de memoria ( a menos que se realice la compactación ). Al hecho de que aparezcan huecos no contiguos de memoria se le llama `fragmentación externa'.
De cualquier manera, la multiprogramación fue un avance significativo para el mejor aprovechamiento de la unidad central de procesamiento y de la memoria misma, así como dio pie para que surgieran los problemas de asignación de memoria, protección y relocalización, entre otros.
Los overlays 
Una vez que surgió la multiprogramación, los usuarios comenzaron a explorar la forma de ejecutar grandes cantidades de código en áreas de memoria muy pequeñas, auxiliados por algunas llamadas al sistema operativo. Es así como nacen los `overlays'.
Esta técnica consiste en que el programador divide lógicamente un programa muy grande en secciones que puedan almacenarse el las particiones de RAM. Al final de cada sección del programa ( o en otros lugares necesarios ) el programador insertaba una o varias llamadas al sistema con el fin de descargar la sección presente de RAM y cargar otra, que en ese momento residía en disco duro u otro medio de almacenamiento secundario. Aunque esta técnica era eficaz ( porque resolvía el problema ) no era eficiente ( ya que no lo resolvía de la mejor manera ). Esta solución requería que el programador tuviera un conocimiento muy profundo del equipo de cómputo y de las llamadas al sistema operativo. Otra desventaja era la portabilidad de un sistema a otro: las llamadas cambiaban, los tamaños de particiones también. Resumiendo, con esta técnica se podían ejecutar programas más grandes que las particiones de RAM, donde la división del código corría a cuenta del programador y el control a cuenta del sistema operativo.

Multiprogramación de Partición Fija 

Cuando ocurre una petición de e / s la cpu normalmente no puede continuar el proceso hasta que concluya la operación de e / s requerida.
Los periféricos de e / s frenan la ejecución de los procesos ya que comparativamente la cpu es varios órdenes de magnitud más rápida que los dispositivos de e / s.
Los sistemas de “multiprogramación” permiten que varios procesos usuarios compitan al mismo tiempo por los recursos del sistema: 
Un trabajo en espera de e / s cederá la cpu a otro trabajo que esté listo para efectuar cómputos.
Existe paralelismo entre el procesamiento y la e / s.
Se incrementa la utilización de la cpu y la capacidad global de ejecución del sistema.
Es necesario que varios trabajos residan a la vez en la memoria principal.
Multiprogramación de Partición Fija: Traducción y Carga Absolutas 
Las “particiones” del almacenamiento principal: 

Son de tamaño fijo.
Alojan un proceso cada una.
La cpu se cambia rápidamente entre los procesos creando la ilusión de simultaneidad.
Los trabajos se traducían con ensambladores y compiladores absolutos para ser ejecutados solo dentro de una partición específica
El S. O. resulta de implementación relativamente sencilla pero no se optimiza la utilización de la memoria. 
Multiprogramación de Partición Fija: Traducción y Carga Relocalizables 
Los compiladores, ensambladores y cargadores de relocalización: 

Se usan para producir programas relocalizables que puedan ser ejecutados en cualquier partición disponible de tamaño suficiente para aceptarlos
Son más complejos que los absolutos.
Mejoran la utilización del almacenamiento.
Confieren más flexibilidad en el armado de la carga de procesos.

Protección en los Sistemas de Multiprogramación 
Si se utiliza asignación contigua de memoria la protección suele implementarse con varios“registros de límites”
Los extremos superior e inferior de una partición pueden ser: 

Delineados con dos registros.
Indicados el límite inferior o superior y el tamaño de la partición o región.

Fragmentación en la Multiprogramación de Partición Fija 
La “fragmentación de almacenamiento” ocurre en todos los sistemas independientemente de su organización de memoria. 
En los S. O. de multiprogramación de partición fija la fragmentación se produce cuando: 

Los trabajos del usuario no llenan completamente sus particiones designadas.
Una partición permanece sin usar porque es demasiado pequeña para alojar un trabajo que está en espera.
Multiprogramación de Partición Variable 
Los procesos ocupan tanto espacio como necesitan, pero obviamente no deben superar el espacio disponible de memoria.

No hay límites fijos de memoria, es decir que la partición de un trabajo es su propio tamaño. 
Se consideran “esquemas de asignación contigua”, dado que un programa debe ocupar posiciones adyacentes de almacenamiento. 
Los procesos que terminan dejan disponibles espacios de memoria principal llamados “agujeros”: 

Pueden ser usados por otros trabajos que cuando finalizan dejan otros “agujeros”menores.
En sucesivos pasos los “agujeros” son cada vez más numerosos pero más pequeños, por lo que se genera un desperdicio de memoria principal.
Combinación de agujeros (áreas libres)
Consiste en fusionar agujeros adyacentes para formar uno sencillo más grande. 
Se puede hacer cuando un trabajo termina y el almacenamiento que libera tiene límites con otros agujeros. 
Compresión o Compactación de Almacenamiento 
Puede ocurrir que los agujeros (áreas libres) separados distribuidos por todo el almacenamiento principal constituyan una cantidad importante de memoria: 

Podría ser suficiente (el total global disponible) para alojar a procesos encolados en espera de memoria.
Podría no ser suficiente ningún área libre individual .

La técnica de compresión de memoria implica pasar todas las áreas ocupadas del almacenamiento a uno de los extremos de la memoria principal: 
Deja un solo agujero grande de memoria libre contigua.
Esta técnica se denomina “recogida de residuos”

Principales desventajas de la compresión 
Consume recursos del sistema

El sistema debe detener todo mientras efectúa la compresión, lo que puede afectar los tiempos de respuesta. 
Implica la relocalización (reubicación) de los procesos que se encuentran en la memoria: 

La información de relocalización debe ser de accesibilidad inmediata.
Una alta carga de trabajo significa mayor frecuencia de compresión que incrementa el uso de recursos.

Estrategias de Colocación del Almacenamiento 
Se utilizan para determinar el lugar de la memoria donde serán colocados los programas y datos que van llegando y se las clasifica de la siguiente manera: 

“Estrategia de mejor ajuste”:
Un trabajo nuevo es colocado en el agujero en el cual quepa de forma más ajustada:
Debe dejarse el menor espacio sin usar.
“Estrategia de primer ajuste”:
Un trabajo nuevo es colocado en el primer agujero disponible con tamaño suficiente para alojarlo.
“Estrategia de peor ajuste”:
Consiste en colocar un programa en el agujero en el que quepa de la peor manera, es decir en el más grande posible:
El agujero restante es también grande para poder alojar a un nuevo programa relativamente grande.
Multiprogramación con Intercambio de Almacenamiento 
En el esquema de “intercambio” los programas del usuario no requieren permanecer en la memoria principal hasta su terminación. 
Una variante consiste en que un trabajo se ejecuta hasta que ya no puede continuar: 

Cede el almacenamiento y la cpu al siguiente trabajo.
La totalidad del almacenamiento se dedica a un trabajo durante un breve período de tiempo.
Los trabajos son “intercambiados”, dándose que un trabajo puede ser intercambiado varias veces antes de llegar a su terminación.
Es un esquema razonable y eficiente para un número relativamente reducido de procesos de usuarios.
Los sistemas de intercambio fueron los predecesores de los sistemas de paginación. 
El rendimiento de los sistemas de intercambio mejora al reducir el tiempo de intercambio: 

Manteniendo al mismo tiempo varias “imágenes de usuario o imágenes de memoria” en la memoria principal.
Retirando una imagen de usuario de la memoria principal solo cuando es necesario su almacenamiento para una nueva imagen.
Incrementando la cantidad de memoria principal disponible en el sistema.
Las imágenes de usuario (imágenes de memoria) retiradas del almacenamiento principal se graban en el almacenamiento secundario (discos).
3.3 Organización de memoria virtual.
Multiprogramación en memoria virtual

La necesidad cada vez más imperiosa de ejecutar programas grandes y el crecimiento en poder de las unidades centrales de procesamiento empujaron a los diseñadores de los sistemas operativos a implantar un mecanismo para ejecutar automáticamente programas más grandes que la memoria real disponible, esto es, de ofrecer `memoria virtual'.
La memoria virtual se llama así porque el programador ve una cantidad de memoria mucho mayor que la real, y en realidad se trata de la suma de la memoria de almacenamiento primario y una cantidad determinada de almacenamiento secundario. El sistema operativo, en su módulo de manejo de memoria, se encarga de intercambiar programas enteros, segmentos o páginas entre la memoria real y el medio de almacenamiento secundario. Si lo que se intercambia son procesos enteros, se habla entonces de multiprogramación en memoria real, pero si lo que se intercambian son segmentos o páginas, se puede hablar de multiprogramación con memoria virtual.
La memoria virtual se apoya en varias técnicas interesantes para lograr su objetivo. Una de las teorias más fuertes es la del `conjunto de trabajo', la cual se refiere a que un programa o proceso no está usando todo su espacio de direcciones en todo momento, sino que existen un conjunto de localidades activas que conforman el `conjunto de trabajo'. Si se logra que las páginas o segmentos que contienen al conjunto de trabajo estén siempre en RAM, entonces el programa se desempeñará muy bien.
Otro factor importante es si los programas exhiben un fenómeno llamado `localidad', lo cual quiere decir que algunos programas tienden a usar mucho las instrucciones que están cercanas a la localidad de la instrucción que se está ejecutando actualmente.

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 ” 

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).
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ónpara 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.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. 

No hay comentarios:

Publicar un comentario