Recuperación de datos es el proceso de restablecer la información contenida en dispositivos de almacenamiento secundarios dañados, defectuosos, corruptos, inaccesibles o que no se pueden acceder de forma normal. A menudo la información es recuperada de dispositivos de almacenamiento tales como discos duros, cintas, CD, DVD, RAID y otros dispositivos electrónicos. La recuperación puede ser debida a un daño físico en el dispositivo de almacenamiento o por un daño lógico en el sistema de archivos que evita que el dispositivo sea accedido desde el sistema operativo. Ya sea utilizado en otro sistema o en otro lugar del original.

El escenario más común de “recuperación de datos” involucra una falla en el sistema operativo (típicamente de un solo disco, una sola partición, un solo sistema operativo), en este caso el objetivo es simplemente copiar todos los archivos requeridos en otro disco. Esto se puede conseguir fácilmente con un Live CD, la mayoría de los cuales provéen un medio para acceder al sistema de archivos, obtener una copia de respaldo de los discos o dispositivos removibles, y luego mover los archivos desde el disco hacia el respaldo con un administrador de archivos o un programa para creación de discos ópticos. Estos casos pueden ser mitigados realizando particiones del disco y continuamente almacenando los archivos de información importante (o copias de ellos) en una partición diferente del de la de los archivos de sistema en el sistema operativo, los cuales son reemplazables.

Otro escenario involucra una falla a nivel de disco, tal como un sistema de archivos o partición de disco que esté comprometido, o una falla en el disco duro. En cualquiera de estos casos, los datos no pueden ser fácilmente leidos. Dependiendo de la situación, las soluciones pueden estar entre reparar el sistema de archivos, la tabla de particiones o el registro maestro de cargado (MBR), o técnicas de recuperación del disco duro que van desde la recuperación basada en software de los datos corruptos a el reemplazo del hardware de un disco dañado físicamente. Si la recuperación del disco duro es necesaria, el disco de por sí típicamente ha fallado de manera permanente, y el propósito en vez de una recuperación de una sola vez, es el de rescatar cualquier dato que pueda ser leido.

En un tercer escenario, los archivos han sido “borrados” de un medio de almacenamiento. Típicamente, los archivos borrados no son realmente eliminados de inmediato; en vez de ello, las referencias a ellos en la estructura de directorios ha sido removida, y el espacio que éstos ocupan se hace disponible para su posterior sobre-escritura. En el transcurso de esto, el archivo original puede ser recuperado. Aunque hay cierta confusión acerca del término, la “recuperación de datos” puede también ser usada en el contexto de aplicaciones de informática forense o de espionaje.

mas información sobre recuperación  de datos: http://es.wikipedia.org/wiki/Recuperaci%C3%B3n_de_datos

Métodos de Recuperación

 RAID (“Redundant Array of Inexpensive Disks”)

En palabras simples es: un conjunto de 2 o más “Discos Duros” que operan como grupo y logran ofrecer una forma más avanzada de respaldo ya que:

Es posible mantener copias en linea (“Redundancy”).

Agiliza las operaciones del Sistema (sobre todo en bases de datos .)

El sistema es capaz de recuperar información sin intervención de un Administrador.

Existen varias configuraciones de Tipo RAID, sin embargo, existen 4 tipos que prevalecen en muchas Arquitecturas:

RAID-0 : En esta configuración cada archivo es dividido (“Striped”) y sus fracciones son colocadas en diferentes discos. Este tipo de implementación sólo agiliza el proceso de lectura de archivos, pero en ningún momento proporciona algún tipo de respaldo (“redundancy”).

RAID-1 : En orden ascendente, este es el primer tipo de RAID que otorga cierto nivel de respaldo; cada vez que se vaya a guardar un archivo en el sistema éste se copiara integro a DOS discos (en línea), es por esto que RAID-1 también es llamado “Mirroring”.

Además de proporcionar un respaldo en caliente (“hot”) en dado caso de fallar algún disco del grupo , RAID-1 también agiliza la lectura de archivos (si se encuentran ocupadas las cabezas de un disco “I/O”) ya que otro archivo puede ser leído del otro disco y no requiere esperar a finalizar el “I/O” del primer disco.

RAID-2: “Acceso paralelo con discos especializados. Redundancia a través del código Hamming”: El RAID nivel 2 adapta la técnica comúnmente usada para detectar y corregir errores en memorias de estado sólido. En un RAID de nivel 2, el código ECC (Error Correction Code) se intercala a través de varios discos a nivel de bit. El método empleado es el Hamming. Puesto que el código Hamming se usa tanto para detección como para corrección de errores. No tiene ninguna ventaja sobre el RAID-3. Así, todos los discos de la matriz están siendo “monitorizados” por el mecanismo. Actualmente, el RAID 2 es poco usado, ya que prácticamente todos los discos rígidos nuevos salen de fábrica con mecanismos de detección de fallas implantados.

RAID-3 : Esta configuración al igual que RAID-0 divide la información de todos los archivos (“Striping”) en varios discos, pero ofrece un nivel de respaldo que RAID-0 no ofrece. En RAID-0 si falla un disco del grupo, la Información no puede ser recuperada fácilmente, ya que cada disco del grupo contiene una fracción del archivo, sin embargo RAID-3 opera con un disco llamado “de paridad” (“parity disk”). Este “disco de paridad” guarda fracciones de los archivos necesarias para recuperar toda su Información, con esto, es posible reproducir el archivo que se perdió a partir de esta información de paridad.

RAID 4: distribuye los datos a nivel de bloque (la principal diferencia con el nivel 3), a través de varios discos, con la pariedad almacenada en un disco. La información de pariedad permite la recuperación de cualquier disco en caso de falla. El rendimiento de un arreglo nivel 4 es muy bueno para lecturas (similar al nivel 0). Sin embargo, la escritura requiere que los datos de pariedad sean actualizados cada vez. Esto retarda particularmente las escrituras aleatorias pequeñas, aunque las escrituras grandes o secuenciales son razonablemente rápidas. Debido a que solamente un disco es del arreglo es utilizado para datos redundantes, el costo por megabyte de un arreglo nivel 4 es relativamente bajo.

RAID-5 : es la alternativa más popular. El Nivel 5 crea datos de pariedad, distribuyéndolos a través de todos los discos (excepto en aquel disco en que se almacena la información original), obviando la necesidad de un disco de pariedad dedicado. El Nivel 5 es el más completo de todos los niveles de redundancia por distribución, por que si un disco falla, la información de pariedad en los otros permite la reconstrucción de toda su información. Aún más, el Nivel 5 escribe datos en los discos al nivel de bloques (en lugar de trabajar al nivel de bytes), volviéndolo más apropiado para múltiples transacciones pequeñas como e-mail, procesadores de palabras, hojas electrónicas, y aplicaciones de bases de datos. Los niveles 3 y 5 requieren al menos de 3 discos para su implementación.

 RAID 6: Similar al RAID 5, pero incluye un segundo esquema de paridad distribuido por los distintos discos y por tanto ofrece tolerancia extremadamente alta a los fallos y a las caídas de disco, ofreciendo dos niveles de redundancia. Hay pocos ejemplos comerciales en la actualidad, ya que su coste de implementación es mayor al de otros niveles RAID, ya que las controladoras requeridas que soporten esta doble paridad son más complejas y caras que las de otros niveles RAID. Así pues, comercialmente no se implementa.

RAID 0+1/ RAID 0/1 ó RAID 10: “Ambos mundos”: El RAID 0 + 1 es una combinación de los niveles 0 (Striping) y 1 (Mirroring), este que proporciona velocidad y tolerancia al fallo simultáneamente donde los datos son divididos entre los discos para mejorar el ingreso, pero también utilizan otros discos para duplicar la información. Así, es posible utilizar el buen ingreso del nivel 0 con la redundancia del nivel 1. Sin embargo, es necesario por lo menos 4 discos para montar un RAID de este tipo.. El nivel de RAID 0+1 fracciona los datos para mejorar el rendimiento, pero también utiliza un conjunto de discos duplicados para conseguir redundancia de datos. Al ser una variedad de RAID híbrida, RAID 0+1 combina las ventajas de rendimiento de RAID 0 con la redundancia que aporta RAID 1

Sistemas De Archivos

Sistema operativo Tipos de sistemas de archivos admitidos
Dos FAT16
Windows 95 FAT16
Windows 95 OSR2 FAT16, FAT32
Windows 98 FAT16, FAT32
Windows NT4 FAT, NTFS (versión 4)
Windows 2000/XP FAT, FAT16, FAT32, NTFS (versiones 4 y 5)
Linux Ext2, Ext3, ReiserFS, Linux Swap (FAT16, FAT32, NTFS)
MacOS HFS (Sistema de Archivos Jerárquico), MFS (Sistemas de Archivos Macintosh)
OS/2 HPFS (Sistema de Archivos de Alto Rendimiento)
SGI IRIX XFS
FreeBSD, OpenBSD UFS (Sistema de Archivos Unix)
Sun Solaris UFS (Sistema de Archivos Unix)
IBM AIX JFS (Sistema Diario de Archivos)
Anuncios

1.-Nombre

El nombre simbólico del archivo es la única información que se mantiene en forma legible para los humanos.

2.-Tipo:

Esta información es necesaria para aquellos sistemas que soportan diferentes tipos.

3.-Ubicación:

Esta información es un apuntador a un dispositivo y ala ubicación del archivo en dicho dispositivo.

4.-Tamaño:

En este atributo se incluyen el tamaño actual del archivo (en bytes, palabras o bloques) y, posiblemente, el tamaño máximo permitido.

5.-protección.

Información de control de acceso que determina quien puede leer, escribir, ejecutar, etc. El archivo.

6.-Hora, fecha e identificación del usuario:

Esta información puede mantenerse para

1.-La creación

2.-La ultima modificación

3.-El ultimo uso.

Directorios

Todo sistema de archivo posee un como parte de su organización, una estructura de datos denominada directorio que sirve para localizar los archivos.

En él están contenidos los datos acerca de los archivos almacenados sobre el soporte que reside.

El acceso a los directorios se hace siempre a través de llamadas al sistema (una invocación al kernel del SO).

Los directorios son una estructura que contiene diversos campos para especificar datos acerca de los archivos referidos desde el directorio.

Directorios de un solo nivel

La figura anterior representa un mismo directorio para todos los usuarios. De ahi la razón de nombrarlos directorios de un solo nivel, pues todos los usuarios comparten un mismo directorio. Esto trae problemas de nombramiento (varios usuarios pueden tener el mismo nombre para diferentes archivos o un mismo archivo puede tener varios nombres diferentes) y problemas de agrupamiento (diferentes tipos de archivos, por ejemplo, Programas en Pascal, Juegos, documento de un mismo tipo, etc)

Directorios de dos niveles

En la figura anterior cada usuario puede tener sus propios directorios, incluso se puede tener el mismo nombre de archivo para diferentes usuarios (ejemplo directorio A).

Directorios con estructura de Árbol

Con esta imagen se representan directorios con estructura de árbol y es en esta estructura donde cada usuario puede tener varios directorios y dentro de estos, tantos subdiretorios o archivos como se quiera. Al incrementarse la cantidad de niveles, brinda capacidad de agrupamiento y búsqueda eficiente.

Directorios de Grafos o Ciclicos.

Una estructura de árbol prohíbe el compartimiento de archivos o directorios. Una grafica acíclica (grafica sin ciclos) permite que los directorios tengan subdirectorios y archivos compartidos. El mismo archivo o subdirectorio puede estar en dos directorios diferentes. Una grafica  a cíclica es una generalización natural del esquema de directorios con estructura de árbol. Cuando varias personas están trabajando  como equipo, todos los archivos que se van a compartir pueden colocarse juntos en un directorio. Cada uno de los directorios de archivos de usuario de todos los miembros del equipo contiene este directorio de archivos compartidos como un subdirectorio.

Una estructura de directorios de grafica aciclica es más flexible que una estructura sencilla de árbol, pero también es más compleja.

http://eosnaya.wordpress.com/1-conceptos-basicos-de-archivos/

METODOS DE ASIGNACION

Asignación Contigua:

  • Cada archivo ocupa un conjunto de bloques contiguos en el disco.
  • Se asigna un unico conjunto contiguo de bloques en tiempo de creación.
  • Simple-Solo se requiere la ubicación inicial (nro de bloque) y la longitud (nro de bloques)
  • Existirá fragmentación externa
  • Desperdicio de espacio (problema con la asignación dinámica del espacio)
  • Los archivos pueden crecer.

Asignación enlazada, encadenada.

  • Cada archivo es una lista enlazada de bloques de disco: los bloques pueden estar dispersos en cualquier parte del disco.
  • En lo que respecta a la administración del espacio libre, no hay desperdicio de espacio.
  • No hay acceso aleatorio.
  • No hay fragmentación externa.
  • se adapta mejor a archivos secuenciales.

Asignación indexada

  • Tiene todos los punteros juntos en el bloque de índices
  • Vista lógica

Ubicación indexada m.

  • Requiere de tabla índice
  • Acceso aleatorio
  • Acceso dinámico sin fragmentación externa, pero hay sobre costo en el bloque de índice

Que tan grande debe ser el bloque índice

  • Lo suficiente para contener los distintos índices:

-Esquema enlazado. Dentro del bloque las últimas direcciones indican otros bloques de dirección

-Índice multinivel. Bloque índice de primer nivel y de segundo nivel, el tercero es el de datos. Con 4096 de tamaño de bloque se tiene 1024 punteros de 4 bytes que apuntarían a 1.048.576 bloques de datos o 4 GB de datos.

-Esquema combinado. Ej 17 punteros de bloque en el bloque índice o I-nodo. Los primeros 12 son directos, 3 a bloques indirectos, luego un indirecto doble, e indirecto triple.

Información de un Nodo- i Unix residente en disco.

C= Almacenamiento archivo.

Tb= Tamaño del bloque.

Db= Direcciones en bytes

R= Directas

S= Indirecto simples.

D=  Indirecto dobles

T= Indirecto triple.

A= Numero de Direcciones

Ejercicio.

10 directos y un indirect tendrian una  capácidad de almacenamiento de :

4k*10+1*1024*4kb

1 directo + 1 indirecto simple + 1 indirecto doble.

4kb+1024*4kb+1*1024*1024*4kb.

 

Formula general=

C= R*Tb*S*(Tb/A)*Tb+D*(Tb/A)^2*Tb+T*(Tb/A)^3 *Tb+Q*(Tb/A)^4*Tb….

 

Tamaño del archivo= 10*tb+(1*1024*tb)+1*1024* tb+1*1024*1024*tb

TA= 10*tb+1*1024*tb+1*1024^2*tb+1*1024^3*tb.

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 1: no referenciada, no modificada
  • Categoría 2: no referenciada, modificada ( Categoria sin logica alguna)
  • Categoría 3: referenciada, no modificada
  • Categoría 4: 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.

Primera en entrar, primera en salir (FIFO, First In, First Out)

En este método el sistema operativo sólo tiene que guardar en qué orden las páginas fueron cargadas, de modo que al necesitar hacer espacio pueda fácilmente elegir la primera página cargada. Se usa una cola, al cargar una página nueva se ingresa en el último lugar. Aunque las colas FIFO son simples e intuitivas, no se comportan de manera aceptable en la aplicación práctica, por lo que es raro su uso en su forma simple. Uno de los problemas que presentan es la llamada Anomalía FIFO o Anomalía de Belady. Belady encontró ejemplos en los que un sistema con un número de marcos de páginas igual a tres tenía menos fallos de páginas que un sistema con cuatro marcos de páginas. El problema consiste en que podemos quitar de memoria una página de memoria muy usada, sólo porque es la más antigua.

FIFO Y ANOMALÍA DE BELADY M

TRES PAGINAS
PAGINAS
SOLICITUD RESIDENTES FALLA
A A F
B A,B F
C A,B,C F
D B,C,D F
A C,D,A F
B D,B,A F
E B,A,E F
A B,A,E
B B,A,E

 

CUATRO PAGINAS
PAGINAS
SOLICITUD RESIDENTES FALLA
A A F
B A,B F
C A,B,C F
D A,B,C,D F
A A,B,C,D
B A,B,C,D
E B,C,D,E F
A C,D,E,A F
B D,E,A,B F

Reloj, Segunda oportunidad

Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor 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 bit de referencia. En caso de estar fijado (en 1) se cambia el bit a 0 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 bit se encuentra sin fijar(en 0), la página se saca de memoria. Cada vez que la MMU accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware.

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.

Menos usada recientemente (Least Recently UsedLRU)

Este algoritmo difiere del de ‘No usada recientemente’ en el hecho de que aquel sólo se fija en el intervalo de tiempo desde que se pusieron en 0 los bits de referencia de las páginas, mientras que el algoritmo de ‘Menos usada recientemente’ intenta proveer un comportamiento casi óptimo mediante la observación de las páginas que menos fueron usadas recientemente. Este tipo de páginas, estadísticamente son las que tienen menor probabilidad de ser usadas nuevamente.

Aunque este algoritmo provee un buen comportamiento en teoría, es caro de implementar, en cuanto a recursos consumidos. Hay varias implementaciones que intentan mantener bajo el costo y lograr un rendimiento considerable. Un método consiste en tener una lista enlazada y ordenada de todas las páginas en memoria. En el final de la lista está la página menos usada recientemente, y al principio la más usada recientemente. El costo alto de este método es porque cada vez que se referencia una página debe ser movida en la lista, algo que consume mucho tiempo. Otra forma, que requiere soporte de hardware, consiste en tener un contador que es incrementado en cada instrucción del CPU. Cada vez que una página es accedida, gana el número del contador en ese momento. Cuando una página debe ser retirada de memoria, simplemente hay que buscar cuál es la que tiene el menor número, que es la que fue usada hace más tiempo. En el presente no existen contadores tan grandes para permitir esto. Debido al alto costo del LRU, se proponen algoritmos similares, pero que permiten implementaciones menos costosas, como los que siguen.

TRES PAGINAS
PAGINAS
SOLICITUD RESIDENTES FALLA
A A F
B A,B F
C A,B,C F
D B,C,D F
A C,D,A F
B D,B,A F
E B,A,E F
A B,E,A
B E,A,B

Algoritmo del conjunto de trabajo 

  • Conjunto de trabajo (working set) es el numero de paginas mínimo que un programa necesita para ejecutarse
  • El algoritmo debe garantizar en un espacio de tiempo el conjunto de páginas requeridas este presente.
  • Se utiliza un bit de referencia y una estampa de tiempo
    • Se mira en todas las páginas el bit de referencia
    • Coloco en el tiempo actual el último tiempo
    • Se saca a la pagina que no está referenciada

Reloj mejorado

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.

windows XP

  • utiliza paginacion por demanda por clustering. el agrupamiento trae las paginas alrededor de la pagina fallada.
  • a los proceso se les asigna un working set minimum y un working set maximum
  • el conjunto de trabajo minimo es el numero de paginas que se le garantiza a un proceso tener en memoria
  • a un proceso se le pueden asignar tantas paginas

solaris

  • mantiene una lista de paginas libres para asignarle a los procesos con faltas de pagina.
  • lostfree parámetro umbral (cantidad de memoria) para empezar a paginar.
  • desfree parámetro umbral para incrementar la paginacion
  • minfree parámetro umbral para empezar el intercambio
  • la paginacion es realizada por el proceso pageout
  • pageout busca las paginas utilizando el algoritmo del reloj modificado
  • scanrate es la velocidad con la cual las paginas son buscadas. Varia de solwscan.

reemplazo de paginas en linux

  • linux utiliza una variante del algoritmo del reloj para aproximarse a la estrategia de reemplazo de paginas LRU.
  • el administrador de memoria utiliza dos listas enlazadas.
    • la lista activa
      • contiene las paginas activas

 

ALMACENAMIENTO SECUNDARIO

 

Planificación del Disco

  • El SO es responsable por el uso eficiente del HW para los discos duros, esto significa tener un tiempo de acceso más rápido y un mayor ancho de banda para el disco
  • El tiempo de acceso tiene dos componentes principales:
    • El tiempo de búsqueda es el tiempo en el que el disco debe mover las cabezas hasta el cilindro que contiene el sector deseado
    • Latencia rotacional es el tiempo adicional de espera para que el disco rote sus cabezas hasta el sector deseado.
  • Minimizando el tiempo de búsqueda
  • El ancho de banda del disco es el número total de bytes transferidos dividido por el tiempo total entre la primera solicitud del servicio y el completado de la transferencia.
  • Existen diversos algoritmos para planificar el servicio de las solicitudes de entrada y salida del disco

FCFS( first come first serve)

cola de solicitudes= 98, 183, 37, 122, 14, 124, 65, 67 la cabeza inicia en 53.

la ilustración muestra el movimiento total de la cabeza de 640 cilindros

SSTF (Shortest seek time first)

  • elige la solicitud con el mínimo de tiempo de búsqueda desde la actual posición de la cabeza
  • la planificación SSTF es una forma de la planificación SJF

la ilustración muestra el movimiento total de la cabeza de 236 cilindros

SCAN – N PASOS

el brazo del disco empieza en uno de los extremos del disco, y se mueve hacia el otro extremo, sirviendo las solicitudas hasta que llega al otro extremo, donde el movimiento se invierte el servicio continua.

C-Scan

C-look

  • versión de C-scan
  • el brazo solo va tan lejos como este la ultima solicitud en cada dirección, entonces se devuelve sin ir al extreselección de algoritmos de planificacion de disco

RESUMEN

 

 

Segmentación

La gestión de la memoria física y virtual incluye varios procesos, entre los cuales se encuentran la paginación, la segmentación y la segmentación paginada.
La segmentación de memoria 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.
Con el uso de segmentación se pretende alcanzar varios objetivos, alguno de ellos son:

  • 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: 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.
  • Compartición: los procesos pueden compartir 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.
sistsegmentacion.gif

Traducción de direcciones en un sistema con segmentación

Ventajas de un sistema con segmentacion

Algunas de las ventajas que ofrece el esquema de segmentación son:

  • La segmentación es normalmente visible al programador y se proporciona como una utilidad para organizar programas y datos.
  • Es posible compilar módulos separados como segmentos; el enlace entre los segmentos puede suponer hasta tanto se haga una referencia entre segmentos. Como consecuencia de esto, se hace más fácil la modificación de los mismos. Los cambios dentro de un módulo no afecta al resto de los módulos.
  • Facilidad para compartir segmentos
  • Es posible que los segmentos crezcan dinámicamente según las necesidades del programa en ejecución.

Desventajas de un sistema con segmentacion

Por otro lado, existen varias desventajas que presenta este esquema, entre ellas se encuentran las siguientes:

  • Incremento en los costos de hardware y de software para llevar a cabo la implementació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, en consecuencia se debería implementar algún algoritmo de reubicación de segmentos en memoria principal.
  • Dificulta el manejo de memoria virtual, ya que este tipo de memoria almacena la información en bloques de tamaños fijos, mientras que los segmentos son de tamaño variable. Esto hace necesaria la existencia de mecanismos más costosos que los existentes para paginación.
  • Debido a la variación de tamaño de los segmentos, puede ser necesarios planes de reubicación a nivel de disco, 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.

Segmentacion paginada

Esta técnica permite minimizar las desventajas mencionadas anteriormente. Combinando los esquemas de paginación y segmentación.
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 página implica solo encontrar un marco de pagina disponible.
A nivel de paginación, si se desea referenciar en forma cíclicas n páginas , estas deberán ser cargadas una a una generándose varias interrupciones por fallas de páginas ; bajo segmentación, esta página podría conformar un solo segmento, generando una sola interrupción, por falla de segmento. No obstante, si bajo segmentación, se desea acceder a 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 cargará 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:
s =número del segmento,
p = número de la página dentro del segmento
d = desplazamiento dentro de la pagina.

Este esquema utiliza varias tablas, entre estas se encuentran:

  • SMT(tabla de mapas de segmentos): una para cada proceso. En cada entrada de la tabla se almacena la información descrita bajo segmentación pura, pero en el campo de dirección se indicará 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 describe una página de un segmento; en la forma que se presento la pagina pura.
  • TBM(tabla de bloques de memoria): se utiliza para controlar asignación de páginas por parte del sistema operativo.
  • JT(tabla de Jobs): 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 página, 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.

sistsegmentacionpaginacion.gif
Traducción de direcciones en un sistema con segmentación y paginación

Ventajas de un sistema con segmentacion paginada

El esquema de segmentación paginada tiene todas las ventajas de la segmentación y la paginación:

  • Se garantiza la facilidad de implantar la compartición y enlaces.
  • Se simplifican las estrategias de almacenamiento.
  • Se elimina el problema de la fragmentación externa y la necesidad de compactación.

Desventajas de un sistema con segmentacion paginada

Por otro lado, este esquema tiene sus desventajas, las cuales son:

  • Las tres componentes de la dirección y el proceso de formación de direcciones hace que se incremente el costo de su implementació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.

Buffer de traducción anticipada o TLB

De nuevo el principio de localidad: Si las referencias tienen localidad entonces la traducción de direcciones también debe tener localidad

  • El buffer de traducción anticipada (translation-lookaside buffer) o TLB es una cache, habitualmente totalmente asociativa o asociativa por conjuntos, cuyas entradas contienen: en la parte de la etiqueta, el número de página virtual (o parte) y en la parte del dato, el número de página física y los bits de control
  • Un tamaño de página mayor hace que más memoria pueda estar mapeada con una entrada, por lo que se reduce el numero de fallos en la TLB
  • Hay TLBs unificadas y separadas (datos e instrucciones)
  • Cuando se combinan caches y memoria virtual, la dirección virtual debe ser traducida a una dirección física mediante la TLB antes de que pueda acceder a la cache (elevado tiempo de acierto)
  • Una forma de reducir el tiempo de acierto es:
    • acceder a la cache únicamente con el desplazamiento de página (no necesita ser traducido) y mientras se están leyendo las etiquetas de dirección de la cache, el número de página virtual es enviado a la TLB para ser traducido
    • como la TLB es habitualmente más pequeña y rápida que la memoria de etiquetas de la cache, la lectura de la TLB puede hacerse de forma simultánea a la lectura de la memoria de etiquetas sin ralentizar los tiempos de acierto de la cache después la comparación de direcciones se realiza entre la dirección física de la TLB y la etiqueta de la cache
  • Inconveniente: una cache de correspondencia directa no puede ser mayor que una página
  • Otra alternativa es utilizar caches virtuales

Esquema de tabla de páginas de dos niveles.

Establecer el EAT para un procesador con 4 niveles de paginacion (ej. Motorola 68030) con tiempo de acceso a memoria de 100ms, tiempo de busqueda es 20ms y una tasa de aciertos en cache de 98%.

No tenga en cuenta el intercambio.

Comparelo con el tiempo de acceso a memoria.

Rendimiento en paginacion por demanda con intercambio

Tasa de fallo de pagina 0<= p<= 1.0
si p=0 no hay fallo de pagina
si p=1 cada referencia es un fallo de pagina

Tiempo de acceso efectivo con intercambio= EATS

EATS= (1-p)* acceso a memoria+p*(sobrecarga de fallo de pagina+ [descarga]+carga+reinicio)

EATS= (1-p)*t+p*f

  • El tiempo que importa es el de carga de memoria de intercambio a memoria real.

ejemplo rendimiento en paginacion por demanda con intercambio

EATS=(1-p)*t+p*f

si suponemos un t=100ns y un disco con latencia = 8ms, t.busqueda = 15ms y t.transferencia=1ms, tendramos un tiempo promedio de fallo f= ms

EATS=(1-p)*100+p*(25.000.000)

100+24.999,900*p (en ns)

lo cual significa que el tiempo de acceso esta muy relacionado con la tasa de fallos de paginacion.(en general t<<f)

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 memoriaRAM 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

image

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 paginas.
  • Para cargar un programa de tamaño n paginas, se requiere encontrar n marcos libres y cargar el programa.
  • Se puede presentar fragmentación interna.

Planificación

Publicado: octubre 4, 2012 en Uncategorized

En Solaris
El manejo de procesos en Solaris es por prioridad y round robin. En algunas versiones se maneja también un ajuste dinámico de la prioridad de acuerdo al tiempo que los procesos han esperado y al tiempo que ya han usado el CPU. El sistema provee facilidades para crear ‘pipes’ entre procesos, contabilizar el uso de CPU por proceso y una pila común para todos los procesos cuando necesitan estarse ejecutando en modo privilegiado (cuando hicieron una llamada al sistema). Solaris permite que un proceso haga una copia de sí mismo por medio de la llamada ‘fork’, lo cual es muy útil cuando se realizan trabajos paralelos o concurrentes; también se proveen facilidades para el envío de mensajes entre procesos. Recientemente Sun Microsystems, AT&T, IBM, Hewlett Packard y otros fabricantes de computadoras llegaron a un acuerdo para usar un paquete llamado ToolTalk para crear aplicaciones que usen un mismo método de intercambio de mensajes.

 Planificación en POSIX

cada política de planificación tiene asociada al menos 32 niveles de prioridad

el planificador elige el proceso con la mayor prioridad

En Linux

Puede haber a la vez en el sistema procesos con distinta política de planificación establecida. En realidad cada proceso se puede planificar de varias maneras, las políticas de planificación de un proceso se pueden cambiar en tiempo de ejecución.

Linux está basado en la planificación tradicional de Unix  añadiendo 2 clases de prioridad para procesos de tiempo real flexibles. Las clases de planificación de Linux son las siguientes:

SCHED_OTHER : Es la planificación clásica de UNIX. No es aplicable a tiempo real. Examina las prioridades dinámicas (calculadas como combinación de las especificadas por el usuario y las calculadas por el sistema). Los procesos que llevan más tiempo en el sistema van perdiendo prioridad.

SCHED_FIFO : El sistema FIFO o FCFS (First to Come is First Served).Los procesos esperan en cola y se ejecutan secuencialmente. Se sigue calculando un cuantum de tiempo para el proceso, generalmente no se usa porque con esta planificación no se fuerza al proceso a abandonar la CPU. Se usa en procesos de tiempo real.

Windows 

Por lo general en Windows se utiliza una política de planificación: Round Robin. La desventaja principal es que cambia los procesos en ejecución con demasiada frecuencia. Lo que supone una pequeña pérdida de tiempo.

Además Las prioridades en W2K se organizan en dos bandas o clases: tiempo real y variable. Cada una de estas bandas consta de 16  niveles de PRIORIDAD. Los hilos que requieren atención inmediata están en clase de tiempo real, que incluye funciones como comunicaciones tareas de tiempo real.  En general, puesto que W2K utiliza un planificador preferente con prioridades, los hilos con prioridades de tiempo real tienen preferencia sobre los otros hilos. En un monoprocesador, cuando un hilo cuya prioridad es mayor que la del que se ejecuta en ese momento pasa a estar Listo, el hilo de menor prioridad es expulsado y se asigna el procesador al de mayor prioridad. En la clase de prioridad de tiempo real, todos los tienen una prioridad fija que no cambia nunca.

Hay una cola FIFO en cada nivel de prioridad, pero un proceso puede emigrar a una de las otras colas dentro de la clase de prioridad variable. Sin embargo un hilo de prioridad no puede promocionarse a ningún otro nivel de la clase de tiempo real.

Planificacion Multiples  procesadores

  • La planificación es más compleja cuando se tienen varios procesadores.
  • Escenarios: Asignación de procesos a procesadores, uso de la multiprogramación en cada procesador individual, activación del proceso, propiamente dicho.
  • La carga se comparte (una cola por procesador?)
  • Una cola para todos los procesadores?.
  • Multiprocesamiento simetrico (SMP)- cada procesador tiene sus propias decisiones de planificación y consulta la cola de listos.
  • Multiprocesamiento Asimétrico (ASMP) – Solo un procesador accede a las estructuras de datos del sistema, obviando la necesidad de compartir datos.

Planificación de tiempo real estática:

No se ajustan las prioridades con el tiempo, poca recarga en el sistema, para procesos donde las condiciones eventualmente cambian

  • Estática dirigida por tabla(plan): determina en tiempo de ejecución, cuándo debe comenzar a ejecutarse cada tarea. Se aplica a tareas periódicas
  • Estática con expropiación dirigida por prioridad(sin plan): Se utiliza un planificador expropiativo tradicional basado en prioridades. Usado en los sistemas miltiprogramados que no son de tiempo real. En tiempo real la prioridad se ajusta con base a las restricciones de tiempo de la tarea, Ej, planificación monótona en frecuencia(RMS)

Planificación de tiempo real dinámica:

Ajusta las prioridades en respuesta a condiciones cambiantes, puede tener una significativa sobrecarga, pero debe asegurar que ella no genere incumplimiento en los tiempos.

  • Dinámica basada en un plan: La factibilidad se determina en tiempo de ejecución.
  • Dinámica basada en el mejor esfuerzo: No se realiza análisis de factibilidad. El sistema trata de cumplir con todos los plazos y abandona cualquier proceso ya iniciado y cuyo plazo no se haya cumplido.

PLANIFICACIÓN POR PLAZOS

 

Las aplicaciones de tiempo real no se preocupan tanto de la velocidad de ejecución como de completar sus tareas.

El proceso debe completarse en un tiempo específico

  • Se utiliza cuando los resultados serían inútiles si no se realiza el proceso a tiempo.
  • Difícil de implementar
    • Debe prever un plan de requerimientos de recursos
    • Genera significativamente sobrecarga
    • El servicio proporcionado a los otros procesos se puede degradar

Algoritmos de Planifiicacion

Publicado: septiembre 29, 2012 en Uncategorized

PLANIFICACIÓN POR PRIORIDAD

  • Se asocia un número entero a cada proceso.
  • La CPU es asignada al proceso con mayor prioridad (por ej. El número más pequeño significa mayor prioridad en Unix o prioridad ascendente como Windows a mayor número mayor prioridad).
    • Expropiativo.
    • No expropiativo.
  • SJF es un esquema de planificación por prioridad, donde la prioridad es el tiempo de ráfaga de CPU que se calcula.
  • Problema= La inanición- los procesos de baja prioridad puede ser que nunca se ejecuten.
  • Solución= Envejecimiento – a medida que transcurre el tiempo aumenta la prioridad.

TURNO CIRCULAR (ROUND ROBIN)

  • Cada proceso toma una pequeña unidad de tiempo de CPU (quantum de tiempo), por lo general  de 10-100 ms. Después de transcurrido de este lapso de tiempo, el proceso es expropiado y ubicado en la cola de listos.
  • Si hay n procesos en la cola de listos y el quantum es q, entonces cada proceso toma 1/n de tiempo de CPU en bloques de a lo más q  unidades de tiempo a la vez. Ningún proceso espera más que (n-1)*q unidades de tiempo.
  • Rendimiento.
    • Si q >> entonces FIFO.
    • Si q << q debe ser mayor que la conmutación de contexto, de otra forma la sobrecarga es grande.

 

FAIR SHARE SCHEDULLING – PORCIÓN JUSTA

Porción justa/reparto equitativo: Divide la capacidad de recursos del sistema en porciones, que son asignadas a planificadores asignados a varios grupos.

  • Las aplicaciones o trabajos de usuario se pueden organizar como un conjunto de procesos (hilos), algunos grupos son más importantes que otros.
  • Desde el punto de vista del usuario, la preocupación es cómo se ejecutan su aplicación.
  • Es necesario tomar decisiones de planificación basadas en estos conjuntos de procesos, los grupos menos importantes no pueden monopolizar los recursos.

Loteria

se da a cada proceso un tiquete para varios recursos del sistema, tal como cpu. Cuando se requiere planificarse

un ejemplo es un servidor de video: supongamos que los procesos necesitan velocidades de 10, 20, 25 f/s.