Unidad 3.2 Memoria real.

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.
http://www.monografias.com/trabajos13/gesme/gesme.shtml

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 [7, Deitel].
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:
o ¿ se concede a cada uno la misma cantidad de espacio o se divide el almacenamiento en porciones o “particiones” de diferente tamaño ?.
o ¿ se utilizará un esquema rígido de número y tamaño de particiones o un esquema dinámico y adaptable ?.
o ¿ 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 ?.
o ¿ 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 ?:
o ¿ 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 ?:
o ¿ se prioriza el tiempo de carga o la optimización en el uso del almacenamiento ?.
• ¿ con qué criterio se desplazarán programas ?.
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA


3.6.2 Jerarquía.
Jerarquía de Almacenamiento
Los programas y datos tienen que estar en la memoria principal para poder ejecutarse o ser referenciados [7, Deitel].
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 (ver Figura 3.1 [7, Deitel]).

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:
o 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:
o 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.6.3 Estrategia de administración de memoria.
Estrategias de Administración del Almacenamiento
Están dirigidas a la obtención del mejor uso posible del recurso del almacenamiento principal [7, Deitel].
Se dividen en las siguientes categorías:
• Estrategias de búsqueda:
o Estrategias de búsqueda por demanda.
o 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:
a. Particiones asignadas
b. 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 memoria diná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.
4. 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.
5. Paginació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:
1. La tabla de páginas puede ser demasiado grande.
2. 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
1. Es posible comenzar a ejecutar un programa, cargando solo una parte del mismo en memoria, y el resto se cargara bajo la solicitud.
2. 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.
3. Es fácil controlar todas las páginas, ya que tienen el mismo tamaño.
4. 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.
5. 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.
6. Al no necesitarse cargar un programa completo en memoria para su ejecución, se puede aumentar el numero de programas multiprogramándose.
7. Se elimina el problema de fragmentación externa.
Desventajas de la paginación
1. 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.
2. 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).
3. 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:
6. Segmentació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:
1. Modularidad de programas: cada rutina del programa puede ser un bloque sujeto a cambios y recopilaciones, sin afectar por ello al resto del programa.
2. Estructuras de datos de largo variable: ejm. Stack, donde cada estructura tiene su propio tamaño y este puede variar.
3. Protección: se puede proteger los módulos del segmento contra accesos no autorizados.
4. Comparición: dos o más procesos pueden ser un mismo segmento, bajo reglas de protección; aunque no sean propietarios de los mismos.
5. 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.
7. 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.
http://www.monografias.com/trabajos13/gesme/gesme.shtml


3.6.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 (ver Figura 3.2 [7, Deitel]).

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 (ver Figura 3.3 [7, Deitel]):
• 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:
o Detener el sistema.
o Producir salidas erróneas.
• El S. O. debe estar protegido contra el proceso usuario:
o 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.
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm#OAA

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. Por ejemplo:
 
 

 
 
 
VENTAJAS DESVENTAJAS
- La cabeza de lectura no se mueve demasiado en la lectura de un archivo. - Produce fragmentación externa.
ASIGNACIÓN LIGADA
En este método, cada archivo es una lista ligada de bloques de disco. En el directorio hay un apuntador al bloque de inicio y un apuntador al bloque final para cada archivo. En cada uno de los bloques donde se encuentra un archivo hay un apuntador al siguiente bloque de la lista. Por ejemplo:

 
 
VENTAJAS DESVENTAJAS
- No produce fragmentación externa.
  • La cabeza de lectura se puede mover demasiado en la lectura de un archivo. 
• - Si una liga se pierde, se perderá el archivo completo. 
• Es ineficiente para la implementación de archivos directos. 
• Se necesita un campo extra para el apuntador.
ASIGNACIÓN INDEXADA
Como ya se vio, la asignación ligada resuelve problemas de fragmentación externa, sin embargo, la asignación ligada no soporta eficientemente el acceso directo a los archivos. La asignación indexada resuelve este problema poniendo todos los apuntadores en una sola localidad: El bloque índice.
Cada archivo tiene su bloque índice, El cual es un arreglo de direcciones de bloques de disco.
La i-ésima entrada en el bloque índice apunta al i-ésimo bloque que conforma el archivo. En el directorio se controla la dirección del bloque índice de cada archivo, por ejemplo:
 
 

 
VENTAJAS DESVENTAJAS
• No produce fragmentación externa. 
• Eficiente para la implementación de archivos directos.
  • Existe desperdicio cuando hay archivos muy chicos. 
• Desbordamiento de bloque índice. (Solución: creación de un esquema ligado; el ultimo bloque índice apunta a otro índice)

http://www.itlp.edu.mx/publica/tutoriales/sistemasoperativos2/unidad4.htm#ASIGNACIÓN%20CONTIGUA.

3.6.5 Multiprogramación de partición fija, partición variable, con intercambio de almacenamiento.
Multiprogramación de partición fija.-
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).
Multiprogramación de partición variable.-
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
Los sistemas de un solo usuario desperdician gran cantidad de recursos computacionales debido a que [7, Deitel] (ver Figura 3.4 [7, Deitel]):
• 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 (ver Figura 3.5 [7, Deitel]).

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 (ver Figura 3.6 [7, Deitel]).
• 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” (ver Figura 3.7 y Figura 3.8 [7, Deitel]).
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 [7, Deitel] (ver Figura 3.9 [7, Deitel]).

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 (ver Figura 3.10 [7, Deitel]).


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” (ver Figura 3.11 [7, Deitel]).


Principales desventajas de la compresión
Consume recursos del sistema (ver Figura 3.12 [7, Deitel]).

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”:
o 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”:
o Un trabajo nuevo es colocado en el primer agujero disponible con tamaño suficiente para alojarlo.
• “Estrategia de peor ajuste”:
o 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 [7, Deitel].
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).