Sistemas Operativos

Temas:

Multiprogramación con particiones variables.Multiprogramación con intercambio de almacenamiento.Organización de Memoria Virtual.Administración de Memoria Virtual.

Multiprogramación con particiones variables

Este esquema fue originalmente usado por el sistema operativo IBM OS/360 (llamado MFT), el cual ya no está en uso.

El sistema operativo lleva una tabla indicando cuáles partes de la memoria están disponibles y cuáles están ocupadas.

Inicialmente, toda la memoria está disponible para los procesos de usuario y es considerado como un gran bloque o hueco único de memoria.

Cuando llega un proceso que necesita memoria, buscamos un hueco lo suficientemente grande para el proceso. Si encontramos uno, se asigna únicamente el espacio requerido, manteniendo el resto disponible para futuros procesos que requieran de espacio. Cuando a un proceso se le asigna un espacio y es cargado a la memoria principal, puede entonces competir para el uso del CPU.

No hay limites 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 mas numerosos pero mas pequeños, por lo que se genera un desperdicio de memoria principal.

Aparecen condensación y compactación

Multiprogramación particiones variables

Condensación Unir o fusionar espacios o huecos continuos

adyacentes para formar uno mas grande.

Compactación Técnica que consiste en trasladar todas las áreas

ocupadas del almacenamiento hacia algún extremo de la memoria.

Multiprogramación por intercambio de

almacenamientoEn 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 periodo 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 numero 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).

Organización Memoria VirtualMediante este esquema se ejecutan programas que no se encuentran totalmente en memoria principal. Por lo tanto, un programa puede tener un tamaño mayor a la memoria física disponible.

Los Métodos más comunes para poner en práctica el almacenamiento virtual son:

** Paginación* * Segmentación

Conceptos BásicosLas direcciones referidas por un proceso se denominan Direcciones Virtuales o Lógicas (L). Por otra parte, las direcciones disponibles en memoria principal se denominan Direcciones Físicas (F).

En el momento de ejecución de los programas, las direcciones lógicas deben hacerse corresponder con las direcciones físicas, mediante una aplicación, la cual se denomina Mapeo de Memoria (Mapping).

Esta actividad realizada por los mecanismos de conversión de direcciones lógicas a direcciones reales se llama Mecanismo de Traducción Dinámica de Direcciones (MTDD).

Las direcciones contiguas en el espacio de direcciones virtuales de un proceso no son necesariamente contiguas en el almacenamiento real. Esto se llama Contigüidad Artificial.

Los MTDD mantiene Mapas de Correspondencia para la traducción de direcciones que muestran cuáles localidades del almacenamiento virtual están en el almacenamiento real en un momento dado y en dónde se encuentran. Para ello, se agrupa en bloques.

Cuando los bloques son del mismo tamaño se llaman Páginas y la organización de la memoria se llama Paginación.

Cuando los bloques pueden tener tamaños diferentes se llaman Segmentos y la organización de la memoria se llama Segmentación.

Las direcciones en un sistema de bloques son Bidimensionales. Para hacer referencia a un elemento en particular, el programa especifica el bloque en el que se encuentra y su desplazamiento a partir del inicio del bloque.

Paginación

Correspondencia de bloques de tamaño fijo

• Las páginas se transfieren de almacenamiento secundario al primario y se colocan dentro de bloques llamados marcos de página, que tienen el mismo tamaño que las páginas entrantes.

• Una página entrante puede colocarse en cualquier marco de página disponible.

Correspondencia entre direcciones de almacenamiento virtual y direcciones de almacenamiento real en un sistema de paginación.

Fallos de Página Un fallo de página es la secuencia de eventos que ocurren cuando

un programa intenta acceder a datos (o código) que está en su espacio de direcciones, pero que no está actualmente ubicado en la RAM del sistema. El sistema operativo debe manejar los fallos de página haciendo residentes en memoria los datos accedidos, permitiendo de esta manera que el programa continúe la operación como que si el fallo de página nunca ocurrió.

La secuencia de lo que ocurre durante un fallo de página es lo siguiente:

El HW hace un señalamiento al núcleo y resguarda el contador del programa en pila. En muchas maquinas, se resguarda cierta información acerca del estado de la instrucción activa en algunos registros especiales del CPU.

Inicia una rutina en código ensamblador con el fin de resguardar los registros generales y la demás información volátil y evitar que el sistema operativo los destruya. Esta rutina llama al S.O como un proceso.

El S.O descubre la ocurrencia de un fallo de página e intenta determinar la pagina virtual requerida. Con frecuencia uno de los registros de HW contiene esa información. Si no, el S.O debe recuperar el contador del programa, buscar la instrucción y analizarla en SW para hacerse una idea de lo que realizaba al ocurrir el fallo.

Una vez determinada la dirección virtual que provocó el fallo, el S.O verifica si la dirección es válida y si la protección es consistente con el acceso. Si no, se envía una señal al proceso o se elimina. Si la dirección es válida y no ocurrió un fallo de protección, el sistema intenta obtener un marco de la lista de marcos libres. Si no existen marcos libres, se ejecuta el algoritmo de remplazo para seleccionar una victima.

Si la página seleccionada esta sucia, el planificador transfiere la página al disco y ocurre un cambio de contexto; se suspende el proceso que provocó el fallo y se permite la ejecución de otro, hasta que termina la transferencia al disco. En cualquier caso, el marco queda señalado como ocupado, para evitar que se le use con otros fines.

Tan pronto el marco este limpio, el S.O examina la dirección en disco donde se encuentra la página necesaria y planifica una operación en disco para recuperarla. Mientras se carga la página, el proceso que produjo el fallo continua suspendido y se ejecuta otro proceso de usuario, si es disponible.

Cuando el interruptor del disco indica la llegada de la página, las tablas de página se actualizan para reflejar su posición y el marco queda en estado normal.

La instrucción que produjo el fallo regresa al estado donde inició y el contador del programa se modifica para que apunte a esa instrucción.

El proceso que provocó el fallo se planifica y el sistema operativo regresa a la rutina del lenguaje ensamblador que lo llamó.

Esta rutina restaura los registros y la demás información volátil; por último regresa al espacio de usuario para continuar la ejecución, como si no hubiera ocurrido un fallo de página.

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

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. 

Al no necesitarse cargar un programa completo en memoria para su ejecución, se puede aumentar el número de programas multiprogramándose. 

Se elimina el problema de fragmentación externa.

Desventajas 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 más 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

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 páginas (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 páginas, 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.

SegmentaciónEn este método se divide los espacios en memoria y los procesos o programas en segmentos de longitud variable.

Un programa y sus datos pueden ocupar varios bloques. Estos pueden estar separados (no contiguos) en almacenamiento real.

Los segmentos se transfieren del almacenamiento primario al secundario como unidades completas.

Un segmento entrante puede colocarse en cualquier área disponible dealmacenamiento primario cuyo tamaño sea suficiente para contenerlo.

Los objetivos alcanzados por la segmentación son:

Modularidad de Programa Estructuras de datos de largo variable Protección Comparación Enlace dinámico entre segmentos

Las estrategias de colocación para la segmentación son similares a las empleadas en la multiprogramación con particiones variables :

Mejor ajuste. Peor ajuste. Primer ajuste.

Ventajas Conocimiento de unidades lógicas facilita el tratamiento para el

programador.

Compilación separada de módulos ( como segmentos) hasta tanto se haga referencia entre segmentos.

Cambios a un modulo no afecta al resto

Fácil de compartir segmentos

Los segmentos pueden crecer dinámicamente, según las necesidades del proceso.

Se pueden definir segmentos que no existan, como una pila sin elementos, así no se asigna espacio hasta ser necesario.

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

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 compartición de segmentos permite ahorrar memoria, pero requiere de mecanismos adicionales da hardware y software.

Sistemas de Paginación-Segmentación

Objetivo: Combinar las ventajas de ambos esquemas.

Los segmentos tienen un tamaño múltiplo de páginas.

No es necesario que todas las páginas de un segmento estén en alma- cenamiento primario a la vez.

Las páginas que son contíguas en almacenamiento virtual no son por fuerza contíguas en almacenamiento real.

Las direcciones son tridimensionales

V = ( S, P, D )

Segmento Página Desplazamiento

VENTAJAS DE LA SEGMENTACIÓN PAGINADA

Debido a que los espacios de memorias son segmentados, se garantiza la facilidad de implantar la compartición 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. 

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.

Administración de Memoria Virtual

Estrategias de Administración de le Memoria Virtual.

Estrategias del mejor ajuste

Estrategias del primer ajuste

Estrategias del peor ajuste

Estrategias de obtención

Estrategias de colocación.

Estrategias de reemplazo

Técnicas de Remplazo de Páginas

Principio de Optimidad Remplazo de Paginas Aleatorio Remplazo de paginas del reloj Remplazo de paginas primeras entradas primeras salidas (PEPS) Remplazo de Paginas de la menos frecuentemente utilizada.(LFU) Remplazo de Paginas de la no utilizada recientemente.(NUR)

Bit de Referencia  = 0 si no se ha hecho referencia a la página

                                   = 1 se ha hecho referencia a la página.

Bit de Modificación = 0 si la página no ha sido modificada                                   = 1 si la página ha sido modificada.

Paginación Por Demanda

Los procesos residen en memoria secundaria (en el disco). Cuando queremos ejecutar un proceso, lo metemos en memoria. Sin embargo, en vez de intercambiar todo el proceso hacia la memoria, utilizamos un intercambiador perezoso.

Un intercambiador perezoso nunca reincorpora una página a memoria a menos que se necesite. Como ahora consideramos un proceso como una secuencia de páginas, en vez de un gran espacio contiguo de direcciones, el término intercambio es técnicamente incorrecto. Un intercambiador manipula procesos enteros, mientras que un paginador trata con las páginas individualmente de un proceso.

Este esquema requiere apoyo del hardware. Generalmente se añade un bit más a cada entrada de la tabla de páginas: un bit válido-inválido. Cuando este bit está asignado como válido, indica que la página asociada se encuentra en memoria. Si el bit está como inválido, este valor indica que la página está en disco. Una página marcada como inválida no tendrá ningún efecto si el proceso nunca intenta acceder a esa página.

Paginación Anticipada  En la paginación anticipada, el sistema operativo intenta

predecir las paginas que necesitara un proceso y entonces carga dichas cuando hay espacio disponible.

Mientras el proceso se ejecuta con sus paginas actuales, el sistema carga las demás paginas que estarán disponibles cuando las requiera el proceso.

El S. O. intenta predecir las paginas que un proceso va a necesitar y a continuación precarga estas paginas cuando hay espacio disponible Mientras el proceso ejecuta sus paginas actuales, el sistema carga paginas nuevas que estarán disponibles cuando el proceso las pida, debido a ello, el tiempo de ejecución de un proceso se puede reducir.

Liberación de PáginaUn proceso usuario puede emitir una “liberación voluntaria de página” para liberar el marco de página cuando ya no necesitara esa página. Se puede eliminar el “desperdicio” y acelerar la ejecución.

El inconveniente es que la incorporación de mandatos de liberación de páginas dentro de los programas de usuarios puede ser peligroso y retrasar el desarrollo de aplicaciones.

“Los compiladores y S. O. deberían detectar automáticamente situaciones de liberación de página mucho antes de lo que es posible con estrategias de conjuntos de trabajo”.

Estrategias de reemplazo de páginas.

Menos frecuentemente utilizada (LFU).Se reemplaza la página a la que se ha hecho referencia con menos frecuencia.

No utilizada recientemente (NUR).Las páginas no utilizadas recientemente, es poco probable que sean referenciadas en un futuro cercano. Por ello se las elige para el reemplazo.

Tamaño de PáginaGeneralmente el almacenamiento real se divide en marcos o celdas de página de tamaño fijo.

Los interrogantes tienen que ver con el tamaño de las páginas, si todas las páginas tendrán igual tamaño, si en caso de utilizar páginas de diferente tamaño las páginas mayores deben ser o no múltiplos enteros de las menores, etc.

Algunas consideraciones para determinar el tamaño de página son las siguientes:

Cuanto más pequeño sea el tamaño de una página, más páginas y marcos de páginas habrá y mayores serán las tablas de páginas:

El desperdicio de almacenamiento debido al tamaño excesivo de las tablas de página se llama“fragmentación de tablas”.

Esto indica la necesidad de páginas más grandes.

Con páginas grandes, grandes cantidades de información que nunca llegaría a ser referenciada, se paginarán hacia el almacenamiento primario:

Esto indica la necesidad de páginas más pequeñas.

Debido a que las transferencias de e / s del disco (paginación) consumen bastante tiempo, se debe minimizar la paginación que un proceso requiera:

Esto indica la necesidad de páginas grandes.

Los programas tienden a mostrar la propiedad de localidad de referencia y esta localidad tiende a ser pequeña:

Esto indica la necesidad de páginas pequeñas.

Los procedimientos y datos rara vez comprenden un número entero de páginas, por lo que los sistemas de paginación experimentan una “fragmentación interna”:

El desperdicio promedio es de 1 / 2 página no usada por segmento (grupo) de páginas, que estará en la última página del segmento.

Esto indica la necesidad de páginas pequeñas.

Los tamaños de pagina mas utilizados son: 512 b, 1 kb, 2 kb, 4 kb.