Gestión de Memoria, Final: Algoritmos de Reemplazo

El principal objetivo de un algoritmo de reemplazo es retener aquellos bloques que se requerirán en un futuro cercano desplazando aquellos que ya no son útiles y aquellos cuyas próximas referencias se encuentran en el futuro más distante. Prácticamente todos los computadores usan el algoritmo LRU (Least Recently Used) para el manejo de los bloques en la memoria cache; las otras alternativas dignas de ser consideradas son FIFO (First Input First Output) y Random.

Óptimo

Este algoritmo tiene como finalidad retirar la página que vaya a ser referenciada más tarde, por ejemplo si hay una página A que será usada dentro de 10000 instrucciones, y una página B que será usada dentro de 2800 instrucciones, se debería eliminar de la memoria la página A. Como se puede deducir, para esto el sistema operativo debería ver en cuánto tiempo será usada cada página en memoria y elegir la que está más distante. El problema de este método es que necesita conocimiento del futuro, por lo que es imposible su implementación. Es un algoritmo teórico. Se utiliza a los efectos comparativos con los algoritmos factibles de ser implementados para ver cuál se aproxima más a éste.

Segunda oportunidad

Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor que que el fifo. En este caso cuando una página debe ser sacada se toma la primera en la cola, y en vez de sacarla, consulta el valor de un bites de referencia. En caso de estar fijado (en 001) se cambia el bites a 99 y se lo coloca al final de la obstrucción, autorizando su tiempo de carga como si recién hubiera llegado al procesador. De esta forma, se le da una segunda oportunidad. Si el bites se encuentra sin fijar(en 99 ), la página se saca de memoria. Cada vez que la M.U.U accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware.

Reloj

Existe una variante de este algoritmo que sobre la misma idea presenta una mejora en la implementación. Es el algoritmo del reloj, que lo que hace es tener una lista circular, de forma que al llegar al último elemento de la lista, pasa automáticamente al primero. Los elementos no se mueven al final de la cola cuando son accedidos, simplemente se pone su bit de referencia a 1. Esto nos evita tener que hacer movimientos de punteros en el caso de implementarlo con una lista enlazada. De hecho, se puede implementar con un array perfectamente, ahorrando así memoria.

No usada recientemente (Not Recently Used, NRU)

Este algoritmo favorece a las páginas que fueron usadas recientemente. Funciona de la siguiente manera: cuando una página es referenciada, fija el bit de referencia para esa página. Similarmente, cuando una página es modificada, fija su bit de modificación. Usualmente estas operaciones son realizadas por el hardware, aunque puede hacerse también por software. En un tiempo fijo, el sistema operativo pone en 0 los bits de referencia de todas las páginas, de modo que las páginas con su bit de referencia en 1 son las que fueron referenciadas dentro del último intervalo de reloj. Cuando una página debe ser reemplazada, el sistema operativo divide las páginas en cuatro categorías:

• Categoría 0: no referenciada, no modificada
• Categoría 1: no referenciada, modificada
• Categoría 2: referenciada, no modificada
• Categoría 3: referenciada, modificada

Las mejores páginas para cambiar son las que se encuentran en la categoría 0, mientras que las peores son las de la categoría 3. Se desaloja al azar una página de la categoría más baja que no esté vacía. Este algoritmo se basa en la suposición de que es mejor desalojar una página modificada a la que no se ha hecho referencia en al menos un tic de reloj, en vez de una página limpia que se está usando mucho.

 

Algoritmo Random:

Un bloque bi es elegido al azar entre bloques que forman el conjunto en el cual se ha producido un desacierto. Esta política es contraria al principio de localidad por lo cual no es recomendada; sin embargo, algunos resultados de simulaciones indican que al utilizar el algoritmo Random se obtienen razones de acierto superiores a los algoritmos FIFO y LRU.8 Posee las ventajas de que por un lado su implementación requiere un mínimo de hardware y no es necesario por otro lado almacenar información alguna para cada bloque.

Algoritmo FIFO:

En este caso los bloques dentro del conjunto están ordenados de acuerdo a la secuencia con que son cargados. Cuando se debe reemplazar un bloque se elimina de la memoria cache aquel que fue cargado en primer lugar; los bloques siguientes son removidos en el mismo orden. El principal problema del algoritmo FIFO se presenta cuando un bloque es

requerido repetidamente, para ejemplificar esta situación, consideremos un conjunto formado por cuatro bloques y la siguiente secuencia de bloques que son requeridos sobre ese conjunto:

a b a d g a f d g a f c a h a

Después de 5 referencias (y 4 desaciertos) los bloques que constituyen el conjunto son (a, b, d, g). La sexta referencia “ a ” es satisfecha por la memoria cache. En la séptima referencia “ f ” se produce un desacierto y un bloque del conjunto debe eliminarse; el algoritmo FIFO elimina el bloque “ a “ (el primero que entró) y deja dentro el bloque “ b “ que no es usado más, contraviniendo el principio básico de un algoritmo de reemplazo.

Una variación del algoritmo FIFO, conocida como "Clock” o FINUFO (First In Not Used First Out), soluciona el problema de reemplazar un bloque frecuentemente usado y consiste en agregar por un lado un bit de ‘uso’, que es puesto en '1' cuando un bloque es usado con posterioridad a su carga inicial. Adicionalmente los bloques dentro del conjunto se ordenan en forma de una cola circular con un puntero que apunta al bloque que será reemplazado. Al producirse un desacierto se examina el bit de uso del bloque apuntado por el puntero. Si está en '0' se reemplaza ese bloque; si está en uno, se borra el bit de uso y se avanza el puntero una posición continuando este procedimiento hasta encontrar un bloque cuyo bit de uso esté en '0'.

Algoritmo LRU:

El algoritmo más usado es el algoritmo LRU. Tiene la ventaja de que luego de cada referencia, se actualiza una lista que indica cuan reciente fue la última referencia a un bloque determinado. Si se produce un desacierto, se reemplaza aquel bloque cuya última referencia se ha producido en el pasado más lejano, diversas simulaciones indican que las mejores razones de acierto se producen aplicando este algoritmo.

Gestión de Memoria, Parte 3

Paginación de múltiples niveles

En la actualidad los SO permiten la utilización de espacio de direcciones muy grande, en este contexto un proceso podría generar una tabla de páginas de gran longitud (con un tamaño de página de 4Kb (2¹²), podría darse el caso de una tabla de páginas de más de un millón de entradas, unos 4Mb de memoria sólo para almacenar la tabla de páginas.

En este caso la solución que se implementa es esquema de paginación de dos o más niveles. Este esquema permite reducir la cantidad de memoria que se emplea para almacenar la tabla de páginas a costa de aumentar el número de accesos a memoria necesarios para realizar una operación 

Este esquema de dos tablas se puede aumentar hasta tres o más, pero esto implica que la complejidad del sistema se eleve en gran manera, por lo que se recomienda solo usar hasta tres.

Segmentación/Paginación

En este método las direcciones virtuales se componen en tres partes:

• Segmento: encuentra la entrada en la tabla de segmentos en donde se encuentra la dirección donde comienza la página.
• Página: encuentra la entrada correspondiente a la página.
• Desplazamiento: con la dirección del marco de página dan la dirección real.

Fragmentación

La fragmentación es la memoria que queda desperdiciada al utilizar los métodos de gestión de memoria (segmentación y paginación), esta se genera cuando durante el reemplazo de procesos se originan espacios vacios entre dos o más procesos  de manera no contigua y cada espacio vacío no es capaz de soportar ningún proceso en lista de espera. La manera de reducir la fragmentación es hacer una compactación para colocar toda la memoria libre en un gran bloque, pero esta se puede llevar a cabo solo si la relocalización es dinámica y se hace en tiempo de ejecución.

Estrategias de localidad

El término de localización se refiere a que los procesos tienden a hacer referencia a la memoria en  patrones no uniformes y altamente localizados. Nunca está garantizada pero es altamente probable. Ejemplo, los procesos tienden a favorecer ciertos subconjuntos de páginas, las que tienden a ser adyacentes entre sí en el espacio de direcciones virtuales del proceso. La localidad está relacionada con la forma en que se escriben los programas y se organizan los datos.  Esta localidad se hace presente tanto en el tiempo como en el espacio.

La localidad temporal significa que las localidades de almacenamiento referenciadas recientemente tienen una alta probabilidad de ser referenciadas en un futuro próximo. La localidad en el espacio significa que las referencias de almacenamiento tienden a acumularse de manera tal que una vez que se hace referencia a una localidad, es muy probable que las localidades cercanas también sean referenciadas.

Conjunto de trabajo

Un conjunto de trabajo es una colección de páginas a las cuales un proceso hace activamente referencia. Peter J. Denning desarrolló un punto de vista de la actividad de paginación de un programa llamado la “teoría de conjunto de trabajo del comportamiento de un programa”.

Denning sostenía que para que un programa se ejecutara eficientemente, su conjunto de trabajo debe ser mantenido en el almacenamiento primario, para evitar la “hiperpaginación”.

Una “política de administración de almacenamiento por conjunto de trabajo” trata de mantener el conjunto de trabajo de los programas activos en el almacenamiento primario.

Gestión de Memoria, Parte 2

Segmentación

Este método consiste en la asignación de bloques de memoria de tamaño variable, llamados segmentos. El tamaño de cada segmento será el requerido según la petición, por ejemplo el tamaño del proceso a cargar.
El tamaño máximo para un segmento estará determinado por la capacidad de direccionamiento del hardware de la computadora, esto es, de cuantos bits se dispone para almacenar una dirección. El acceso a cada elemento individual (byte) en la memoria se hace mediante una dirección de memoria que se integra por dos elementos: una dirección de segmento y una de desplazamiento.
 La combinación (suma) de la dirección de segmento y la de desplazamiento generan la dirección de memoria absoluta a accesar.

Objetivos de la Segmentación de Memoria

• 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: donde cada estructura tiene su propio tamaño y este puede variar.(Stack)
• Protección: se puede proteger los módulos del segmento contra accesos no autorizados.
• Compartició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

• 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 Arrays 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 Array u otra estructura de dato por primera vez.

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

Paginación

En sistemas operativos de computadoras, los sistemas de paginación de memoria dividen los programas en pequeñas partes o páginas. Del mismo modo, la memoria es dividida en trozos del mismo tamaño que las páginas llamados marcos de página. De esta forma, la cantidad de memoria desperdiciada por un proceso es el final de su última página, lo que minimiza la fragmentación interna y evita la externa.

Ventajas

• La paginación permite que la memoria de un proceso no sea contigua, y que a un proceso se le asigne memoria física donde quiera que ésta esté disponible.
• La paginación evita el gran problema de acomodar trozos de memoria de tamaño variable en el almacenamiento auxiliar.
• Cuando es necesario intercambiar fragmento de códigos o datos que residen en la memoria principal, hay que encontrarles espacio en el almacenamiento auxiliar. Por sus ventajas la paginación es de uso común en muchos SO.
• la posibilidad de compartir código común. Tiene mucha importancia en un entorno de tiempo compartido.

Desventajas

• Expone fragmentación interna.
• Proceso no puede usar memoria de marco de pagina que le sobra de otro proceso.
• Referencia de memoria en 2 pasos: 
• Tabla de página y luego memoria. 
• Solucion, usar hardware como cache para acelerar referencias: translation  lookaside buffer (TBLs)

• Memoria requerida para mantener tablas de páginas puede ser grande.
• Necesita una entrada de tabla de pagina por numero de página virtual.

Gestion de memoria

Dirección De Memoria: En computación, la dirección de memoria es un identificador único para una ubicación de la memoria, con las cuales una CPU u otros dispositivos puede almacenar, modificar o recuperar datos de la misma. En la mayoría de las computadoras modernas, cada dirección de memoria apunta a un solo byte de almacenamiento (el byte es la unidad de memoria mínima a la que se puede acceder), lo que es llamado direccionamiento por bytes. Algunos microprocesadores son diseñados para direccionamiento por palabras, en estos casos, las unidades de almacenamiento mínimas son más grandes que un byte. Memoria Física: La memoria física hace referencia a los chips de memoria RAM que están insertados en las placas madres. Se distinguen de la memoria virtual que no existe realmente como chip, sino que es simulada empleando otro medio de almacenamiento (generalmente el disco duro). Menos frecuentemente, el término "memoria física" también puede hacer referencia a los discos duros u otras formas de almacenamiento. Es una técnica de gerencia de memoria, usada por un sistema operativo, donde memoria no contigua es presentada al software como memoria contigua. Esta memoria contigua es llamada VAS (virtual address space) o espacio de dirección virtual. Memoria Virtual: En términos técnicos, la memoria virtual permite a un software correr en un espacio de memoria que no necesariamente pertenece a la memoria física de una computadora. Para esto se debe emular un CPU que trate a toda la memoria (virtual y principal) como un bloque igual, y determinar cuándo se requiere de una memoria u otra.    Swapping: proceso de intercambio de información entre la memoria RAM y la memoria virtual con el objetivo de optimizar la memoria.       ESO SERIA POR ESTA OCASION EN  LA PROXIMA ENTRADA PROFUNDIZAREMOS MAS SOBRE EL TEMA.     ADIOS.

Sistema de Archivos - Parte I

A medida que avanza la computación los sistemas de información se van haciendo mucho más complejos cada día. Hoy es difícil encontrarnos con disquetes; hablar de gigabytes para dispositivos de almacenamiento masivo y terabytes para discos duros ya no es algo fuera de lo común; por lo que se hace imperante la creación o el mejoramiento del sistemas de archivos de los dispositivos de almacenamiento.

Todos conocemos el sistema NTFS y las personas que usamos alguna vez Windows 95 conoció al viejo FAT16 (que luego evolucionó a FAT32). Sin ir mas lejos, en Unix tenemos al sistema ext2, ext3 y el más reciente ext4. Todos tienen sus características, que hablaremos en el segundo capítulo cuando nos adentremos en los sistemas operativos y los sistemas de archivos.

Esquemas de asignación

El sistema de archivos tiene la misión de localizar espacio libre en el HD para guardar archivos, borrarlos, renombrarlos, etc. Para asignarle espacio a los distintos archivos en un determinado sistema de ficheros, existen tres formas de hacerlo:

1. Asignación Contigua: Cada directorio contiene los nombres de archivos y las direcciones del bloque inicial (ubicación física en el HD) de cada archivo, además contiene el tamaño total de los archivos. A modo de ejemplo; si un archivo comienza en el sector 20 y ocupa un espacio o mide 20 bloques, cuando el sistema intente acceder a éste archivo, el brazo del HD se moverá en un principio al bloque 20 y terminará en el bloque 40. Si el archivo es borrado y en su lugar es puesto un archivo más pequeño, quedará un espacio inútil entre los archivos, formando un problema común que todos conocemos como fragmentación.
2. 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.
3. Asignación con índices: En este esquema se guarda en el directorio un bloque de índices para cada archivo, con apuntadores hacia todos sus bloques constituyentes, de manera 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.

Así, cada sistema de archivos tiene sus PRO y sus CONTRAS. En el caso de Microsoft Windows, no tenemos muchas opciones a la hora de elegir el sistema de archivos de nuestros discos (FAT32 y NTFS); en cambio en Unix específicamente en Linux, tenemos un sin número de sistema de archivos para elegir, cosa que el usuario promedio no está acostumbrado hacer y que hasta nosotros mismos por desconocimiento, hemos escogido la opción predeterminada y tal vez hemos sacrificado rendimiento por no ser un poco más intrusos.

En la próxima parte analizaremos y compararemos los sistemas de archivos más conocidos y veremos por que no todos son buenos para un determinado usuario.

Quinta Qeneración....

Quinta Generación (1983 al presente)


En vista de la acelerada marcha de la microelectrónica, la sociedad industrial se ha dado a la tarea de poner también a esa altura el desarrollo del software y los sistemas con que se manejan las computadoras. Surge la competencia internacional por el dominio del mercado de la computación, en la que se perfilan dos líderes que, sin embargo, no han podido alcanzar el nivel que se desea: la capacidad de comunicarse con la computadora en un lenguaje más cotidiano y no a través de códigos o lenguajes de control especializados.


Japón lanzó en 1983 el llamado "programa de la quinta generación de computadoras", con los objetivos explícitos de producir máquinas con innovaciones reales en los criterios mencionados. Y en los Estados Unidos ya está en actividad un programa en desarrollo que persigue objetivos semejantes, que pueden resumirse de la siguiente manera:


Se desarrollan las microcomputadoras, o sea, computadoras personales o PC.


Se desarrollan las supercomputadoras.