Algoritmo FIFO

El algoritmo FIFO reemplaza las páginas de la forma que el primero que entra es el primero que sale. Asocia a cada página el instante en el que se trajo a la memoria, así cuando se tenga que reemplazar una página, se elige la más antigua.

En la imagen vemos 19 páginas entrando en una memoria de tres frames. El resultado obtenido fueron 15 fallos de página.
A pesar de que es un algoritmo fácil de comprender y programar, su rendimiento no siempre es bueno. Un ejemplo claro es cuando la página puede contener una variable cuyo valor inicial se asignó hace tiempo pero que se utiliza constantemente por lo que puede prescindir de páginas que accede con frecuencia.

Algoritmo FIFO

1. FIFO

Se sustituye la página residente que lleve más tiempo en

memoria

Fácil de implementar (cola FIFO de páginas)

Problema: al no tener en cuenta la historia del uso de una

página dada, FIFO puede prescindir de páginas a las que se

accede con frecuencia

Padece la anomalía de

Belady

(fenómeno paradójico

consistente en que aumenta el número de fallos de páginas

cuando se asignan más páginas reales al proceso)

Propiedad de pila

: para cualquier punto en la cadena de

referencia, el conjunto de páginas en N marcos de página es

un subconjunto del que se formaría en N+1 marcos de página

Algoritmo Óptimo

El Algoritmo Óptimo, también conocido como OPT se originó luego del descubrimiento de la Anomalía de Belady en la búsqueda de un algoritmo mucho más óptimo. El algoritmo elige la página de la memoria que vaya a ser referenciada más tarde, las páginas se rotulan con el número de instrucciones que se ejecutarán antes de que se haga la primera referencia a ella y, cuando se presenta un fallo de página, se reemplaza la que más instrucciones falten para referenciarla para así ir aplazando lo más que se pueda los fallos de página. Por desgracia, este algoritmo es irrealizable, ya que no hay una forma de predecir qué páginas referenciará un proceso en el futuro.

En la imagen vemos la cadena de referencias para una página y cómo se usa la memoria (en este caso de 3 frames o marcos). Se comienza tal como el algoritmo FIFO ingresando las páginas a la memoria; el primer caso de memoria llena sucede cuando entra la página 1 y quiere entrar la página 2. La víctima debe ser decidida de tal forma que la página no sea referenciada mas o sea referenciada mucho después. En este caso la página 5 no es referenciada más, por lo que es reemplazada por la página 2. El algoritmo genera finalmente 7 fallos de página, versus por ejemplo los 10 fallos que FIFO genera.
Como es un algoritmo que no se puede poner en práctica, se ejecuta en simuladores en los cuales se demuestra que es un muy buen algoritmo que reduce mucho las fallas y que se encuentra entre los algoritmos con mejor eficiencia por lo que es el algoritmo utilizado para estudios comparativos.

Algunos algoritmos de

reemplazo

Básicos

FIFO

OPTIMO

LRU – least recently used

Aproximaciones LRU

LRU con bits de referencia adicionales

LRU de segunda oportunidad o del reloj

LRU de segunda oportunidad mejorado

De conteo

LFU – less frequently used

MFU – most frequently used

25

Algoritmo FIFO

1. FIFO

Se sustituye la página residente que lleve más tiempo en

memoria

Fácil de implementar (cola FIFO de páginas)

Problema: al no tener en cuenta la historia del uso de una

página dada, FIFO puede prescindir de páginas a las que se

accede con frecuencia

Padece la anomalía de

Belady

(fenómeno paradójico

consistente en que aumenta el número de fallos de páginas

cuando se asignan más páginas reales al proceso)

Propiedad de pila

: para cualquier punto en la cadena de

referencia, el conjunto de páginas en N marcos de página es

un subconjunto del que se formaría en N+1 marcos de página

ejercicios de FIFo
https://www.youtube.com/watch?v=4HIXcs-tscI

Algoritmo de reemplazo óptimo

2. Óptimo

Escoger como víctima la página que más tarde en

volver a ser accedida

Es el algoritmo que presenta la frecuencia de

fallos de página más baja de todos

No implementable (requiere presciencia)

Útil como referencia de comparación

 

Vista

Compactación de Memoria

Compactación de Memoria

El proceso de compactación son unas instancias particulares del problema de asignación de memoria dinámica, y esta se  refiere a  satisfacer  una necesidad de tamaño (N) en una lista de huecos libres. Entre tantas posibilidades existe una que determina el hueco más indicado en el momento de asignar. A continuación estrategias  comunes para la asignación de algún hueco en la tabla.

·         PRIMER  AJUSTE: Consiste en  asignar el proceso en el primer  hueco que se  halle y se ajuste sin importar  que el hueco  sea más  grande  que el  tamaño del proceso  a insertar.

·         MEJOR  AJUSTE: Consiste en ubicar  el proceso según su tamaño en el hueco  más apropiado, esto con el fin de evitar desperdicio de memoria.

·         PEOR AJUSTE: En este algoritmo se busca que el tamaño del hueco concuerde con el tamaño del proceso. Es decir que sea el tamaño del hueco sea igual o mayor que el del proceso, sin importar que se pueda perder gran cantidad de espacio en la memoria.

Almacenamiento Virtual

La memoria virtual es una técnica de gestión de la memoria que permite que el sistema operativo disponga, tanto para el software de usuario como para sí mismo, de mayor cantidad de memoria que la disponible físicamente.

La mayoría de los ordenadores tienen cuatro tipos de memoria: registros en la CPU, la memoria caché (tanto dentro como fuera del CPU), la memoria RAM y el disco duro. En ese orden, van de menor capacidad y mayor velocidad a mayor capacidad y menor velocidad.

Muchas aplicaciones requieren acceso a más información (código y datos) que la que se puede mantener en memoria física. Esto es así sobre todo cuando el sistema operativo permite múltiples procesos y aplicaciones ejecutándose simultáneamente. Una solución al problema de necesitar mayor cantidad de memoria de la que se posee consiste en que las aplicaciones mantengan parte de su información en disco, moviéndola a la memoria principal cuando sea necesario

En este caso es cuando es útil el espacio de intercambio

El sistema operativo puede buscar un proceso poco activo, y moverlo al área de intercambio (el disco duro) y de esa forma liberar la memoria principal para cargar otros procesos. Mientras no haga falta, el proceso extraído de memoria puede quedarse en el disco, ya que ahí no utiliza memoria física. Cuando sea necesario, el sistema vuelve a hacer un intercambio, pasándolo del disco a memoria RAM. Es un proceso lento (comparado con usar sólo la memoria RAM), pero permite dar la impresión de que hay más memoria disponible.

Paginación

·         El espacio de direcciones lógicas de un proceso no necesariamente es contiguo; los procesos se ubican en memoria física donde luego quedan disponibles.

·         Se divide la memoria física en bloques de tamaño fijo llamados marcos (los tamaños son potencias de 2, entre 512 y 8192 bytes)

·         Se divide la memoria lógica en bloques del mismo tamaño llamados páginas.

·         Para cargar un programa de tamaño páginas, se requiere encontrar n marcos libres y cargar el programa.

·         Se puede presentar fragmentación interna

Enlaces de los PDF de la unidad 4

https://drive.google.com/open?id=0B6tmhVjC_V93MGwwTVU1NkVpQzA

https://drive.google.com/open?id=0B6tmhVjC_V93LXJkMW92OGllblU


https://drive.google.com/open?id=0B6tmhVjC_V93VVBoYXlSUFZZRFU

administración de memoria: 

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 esta sólo es posible si la localización es dinámica y se hace en tiempo de ejecución.

 

administración de memoria con o sin intercambio:

Los sistemas de administración de la memoria se pueden clasificar en dos tipos:   Los que
desplazan los procesos de la memoria principal al disco y viceversa durante la ejecución, y aquellos
que no los desplazan.
 

El esquema más sencillo de administración de la memoria es aquel en el que  sólo se tiene un
proceso en memoria en cada instante. El usuario carga toda la memoria con un programa del disco y
utiliza la máquina.       

administración de memoria fija o variables computación:

 

 Técnicas de condensación de huecos y de compactación del almacenamiento

 En los sistemas operativos actuales, debido al uso de varios programas (multiprogramación) se produce en memoria una fragmentación de la misma, producida porque a cada proceso se le asigna una cantidad de memoria (variable) y quedan “huecos” entre particiones. Estos huecos son memoria desperdiciada en cierto modo, ya que si la cantidad es inferior a la necesitada por otro proceso no se llega a usar.

Esta fragmentación puede ser de dos tipos:

– Fragmentación externa: esta se debe a que la cantidad de memoria satisface a la que necesita un proceso, pero al no ser contigua no se le puede asignar como una partición.

– Fragmentación interna: en este tipo, la partición es algo mayor a la que necesita un proceso, por tanto un porcentaje de la partición queda sin usar pero no se puede asignar a otra tarea.

Para evitar estas fragmentaciones existen dos técnicas:

Condensación de huecos

Esta técnica consiste en fusionar dos huecos de memoria libre adyacentes en uno sólo que tendrá como capacidad la suma de los dos originales. Cuando un trabajo termina, el sistema operativo trata de unir todos los espacios libres en uno solo, para tener un espacio suficiente para que pueda entrar otro programa en memoria. Mediante la condensación de huecos se pueden recuperar los bloques contiguos de almacenamiento más grande que sea posible. Gracias a esto, la velocidad de acceso es mayor. Por ejemplo, necesitamos 4K de nuestra memoria, pero tenemos dos huecos, cada uno de 2K. Unimos los dos huecos y tenemos uno de 4K que nos sirve para almacenar este proceso.

Compactación del almacenamiento

Una forma de solucionar la fragmentación externa es usando compactación. Consiste en desplazar todas las localizaciones de memoria ocupada a un extremo de la misma, así quedan dos partes bien diferenciadas, la memoria ocupada y la memoria libre.

La compactación no siempre es posible, ya que es necesario que la localización

sea dinámica y se efectúa en el momento de la ejecución. Además, otro inconveniente que presenta es que es una técnica costosa, ya que requiere recursos del sistema y puede provocar que el tiempo de respuesta aumente. El sistema debe detener todo mientras efectúa la compresión, lo que puede afectar los tiempos de respuesta.

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 esta sólo es posible si la relocalización es dinámica y se hace en tiempo de ejecución.

Condensación

Unir o fusionar espacios o “huecos” adyacentes para formar uno más grande.

Por ejemplo, si hay una solicitud de usuario de  5k y en la memoria hay disponibles 2 “huecos” contíguos pero uno es de 2k y el otro es 3k, entonces, para poder atender ésa solicitud de usuario, se “unen” los 2 “huecos” que formarían un sólo “hueco” de 5k, por tanto ahora si cabría la solicitud en el “hueco” que hay disponible.

 

Compactación;

Una solución para el problema de la fragmentación externa es la compactación. El objetivo consiste en desplazar el contenido de la memoria para colocar junta toda la memoria libre en un solo bloque de gran tamaño.

        Técnica que consiste en trasladar todas las áreas ocupadas del almacenamiento hacia

algún extremo de la memoria.

•    Es una solución de la fragmentación externa.

•   El objetivo consiste en desplazar el contenido de la   memoria libre en un sólo bloque de gran tamaño.

•     La compactación no siempre es posible, sólo es posible si la   relocalización es dinámica y se efectúa en el momento de la ejecución.

•                      Este esquema puede ser bastante costoso.

Estrategias de colocación

Permiten determinar en qué lugar de la memoria  principal se deben colocar  los programas y datos entrantes.

  

Tipos:

      Mejor Ajuste: Colocar el trabajo en el menor bloque en el que quepa.

¨ Primer Ajuste. Colocar el trabajo en el primer hueco de la lista de almacenamiento libre en el que quepa.

 

Peor Ajuste: Colocar el trabajo en el menor bloque en el que quepa.

 

- Administracion de memoria virtual

   espacio de direcciones lógicas vs fisicas

   paginación

   segmentación

   paginacion por demanda

   fallo de pagina

   segmentacion paginada

   paginacion segmentada.

TÉCNICAS DE CONDENSACIÓN DE HUECOS Y COMPACTACIÓN DE ALMACENAMIENTO

           Los trabajos ocupan tanto espacio como necesiten (pero no todo el almacenamiento real). No se

imponen límites fijos, sino que se da a los trabajos todo el almacenamiento que necesiten.

          En la multiprogramación con particiones variables hay fragmentación de tipo externa. Las técnicas de este tipo de fragmentación son:

CONDENSACIÓN DE HUECOS

          Se denomina combinación o condensación de huecos. Es un proceso que consiste en fusionar huecos adyacentes para formar un solo hueco más grande.

          Cuando un trabajo termina, el sistema operativo trata de unir todos los espacios libres en uno solo, para tener un espacio suficiente para que pueda entrar otro programa en memoria.

          Mediante la condensación de huecos se pueden recuperar los bloques contiguos de almacenamiento más grande que sea posible. Gracias a esto, la velocidad de acceso es mayor.

COMPACTACIÓN DEL ALMACENAMIENTO

          Se denomina compresión o compactación de almacenamiento. Esta técnica consiste en trasladar todas las áreas ocupadas del almacenamiento hacia algún extremo de la memoria. Este Proceso es utilizado cuando se tiene una memoria con partición variable en el que se tiene 5 procesos y digamos que el 3 termino su trabajo lo que hace el sistema operativo es coger el proceso 4 y el 5 hacia arriba para ocupar el lugar del 3 y así no tener huecos entre ellos, aunque es tedioso para el sistema operativo porque a cada momento tiene que mover los procesos. Su objetivo consiste en desplazar el contenido de la Memoria libre en un sólo bloque de gran tamaño.

          La compactación no siempre es posible, sólo es posible si la relocalización es dinámica y se efectúa en el momento de la ejecución.

Este esquema puede ser bastante costoso.

          Algunas desventajas de esta técnica de compresión:

               1) Consume recursos del sistema.             

               2) El sistema debe detener todo mientras efectúa la compresión, lo que puede afectar los tiempos de respuesta.

               3) Implica la relocalización (reubicación) de los procesos que se encuentran en la memoria.