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.
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”.
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.
|
|
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.
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.
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