Diseño de Sistemas Operativos

Febrero de 2002

Problema de Sistema de Ficheros

 

ENUNCIADO

Los dispositivos "Disk On Chip" (DOC) son físicamente un chip (sin partes móviles) que presentan un interfaz equivalente al de un pequeño disco (de 8 Megabytes). El almacenamiento interno de los datos se realiza sobre memoria no volátil de tecnología flash.

 

La geometría interna de un DOC distingue dos unidades distintas:

·         El sector (de 0,5 Kilobytes). Un DOC puede ser considerado como un vector de sectores.

·         La región (de 32 Kilobytes). Un DOC puede ser considerado como un vector de regiones.

 

Las operaciones que se pueden realizar sobre un DOC son:

 

Un Sistema de Ficheros para un DOC, ha de tener en cuenta las siguientes consideraciones de diseño:

 

De cara a adaptar un Sistema de Ficheros tipo UNIX (UFS) convencional a un DOC, conteste razonablemente a las siguientes cuestiones:

 

1)       Con los datos mencionados, calcule: número de regiones del DOC, número de sectores por región, número de sectores en el DOC, y número de bits por sector.

 

2)       ¿Cuál sería el tamaño de bloque adecuado para este sistema? Razone pros y contras para los casos extremos:                   1 bloque = 1 sector            ó             1 bloque = 1 región.

 

3)       Justifique la conveniencia de usar la cache de bloques para un dispositivo de tipo DOC. ¿Cuáles serían las políticas más adecuadas?

 

4)       Indique qué estructuras de datos de un UFS convencional están dispuestas en posiciones fijas del dispositivo, y dónde se indica dicha posición, es decir, qué otra estructura de datos la referencia.

 

5)       Suponiendo un UFS convencional, indique qué accesos de lectura y/o escritura son necesarios para crear un subdirectorio del directorio raíz.

 

6)       Dadas las particularidades del DOC y la lógica del Sistema de Ficheros, ¿en qué estados puede encontrarse un bloque? ¿Cómo determinaría el estado de un bloque?

 

7)       Describa en qué circunstancias podría ser borrada una región sin que se comprometa la consistencia del Sistema de Ficheros.

 

8)       Enumere las características de un UFS convencional que hacen que no sean aptos para este tipo de dispositivos. Para cada una, esboce una solución.


SOLUCIÓN

 

1)        

Datos:

1 DOC

=

8 Mbytes

=

2^23 bytes

 

 

 

 

1 Sector

=

0,5 Kbytes

=

2^9 bytes

=

2^10 / 2

=

512 bytes

1 Región

=

32 Kbytes

=

2^15 bytes

 

 

 

 

 

Cálculos:

Regiones / DOC

=

2^23 / 2^15

=

2^(23-15)

=

2^8

=

256

Sectores / DOC

=

2^23 / 2^9

=

2^(23-9)

=

2^14

=

16 K

Sectores / Región

=

2^15 / 2^9

=

2^(15-9)

=

2^6

=

64

Bits / Sector

=

2^9 * 2^3

=

2^(9+3)

=

2^12

=

4 K

 

2)        

Consideraciones iniciales:

·         Sobre la eficiencia de las transferencias de datos.

El tamaño del bloque no afecta a la eficiencia. Las operaciones de lectura y escritura se realizan sobre sectores individuales. Dado que el dispositivo no tiene partes móviles, el tiempo de acceso al medio es uniforme, esto es, se tardaría exactamente lo mismo en leer n sectores dispersos que consecutivos.

Dada la naturaleza del DOC, sólo se puede escribir sobre sectores que estén "borrados". Esto hace imposible la re-escritura in-situ de un sector. Es preciso encontrar sectores borrados dónde poder escribir. Esto obliga a localizar Regiones (conjuntos de sectores) que puedan ser borradas. Esto puede condicionar la complejidad del Sistema de Ficheros.

 

Considerando 1 Bloque = 1 Sector:

Pros:

Contras:

 

Considerando 1 Bloque = 1 Región. Es el caso diametralmente opuesto al anterior.

Pros:

Contras:

 

Por lo tanto, en ningún caso se justifica la opción 1 boque = 1 región. Todo apunta a escoger el tamaño de bloque menor posible, un sector. Ahora bien, ¿es ésta la solución óptima?

 

De cara a aprovechar al máximo la capacidad de almacenamiento del DOC, hemos de reducir al mínimo el espacio necesario para los metadatos, información imprescindible para su correcta gestión. Luego la pregunta es:

 

¿Cuánto espacio ocuparán los metadatos?

Para responder numéricamente haremos las siguientes suposiciones:

 

Para 1 Bloque = 1 Sector.

Bloques / DOC

=

2^14

 

 

 

 

 

 

Bloques / Bitmap

=

2^14 / (2^9 * 2^3)

=

2^(14-9-3)

=

2^2

=

4

Bloques / V. Inodos

=

2^14 / (2^9 / 2^5)

=

2^(14-9+5)

=

2^10

=

1024

Bloques / Metadatos

=

1 + 1 + 4 + 4 + 2^10

=

x

=

1034

~=

2^10

Los Metadatos son

=

2^10 / 2^14

=

2^(10-14)

=

1/2^4

=

1/16

 

Para 1 Bloque = 2 Sectores = 1 Kbyte

Bloques / DOC

=

2^13

 

 

 

 

 

 

Bloques / Bitmap

=

2^13 / (2^10 * 2^3)

=

2^(13-10-3)

=

2^0

=

1

Bloques / V. Inodos

=

2^13 / (2^10 / 2^5)

=

2^(13-10+5)

=

2^8

=

256

Bloques / Metadatos

=

1 + 1 + 1 + 1 + 2^8

=

x

=

260

~=

2^8

Los Metadatos son

=

2^8 / 2^13

=

2^(8-13)

=

1/2^5

=

1/32

 

Para 1 Bloque = 4 Sectores = 2 Kbytes.

Bloques / DOC

=

2^12

 

 

 

 

 

 

Bloques / Bitmap

=

2^12 / (2^11 * 2^3)

=

2^(12-11-3)

=

1/2^2

~=

1

Bloques / V. Inodos

=

2^12 / (2^11 / 2^5)

=

2^(12-11+5)

=

2^6

=

64

Bloques / Metadatos

=

1 + 1 + 1 + 1 + 2^6

=

x

=

70

~=

2^6

Los Metadatos son

=

2^6 / 2^12

=

2^(6-12)

=

1/2^6

=

1/64

 

Como se puede apreciar, a medida que el tamaño del bloque se dobla, el número de ellos se reduce a la mitad, y el espacio destinado a inodos también. Dado que esta es la parte más voluminosa de los metadatos, estos también se reducen aproximadamente a la mirad.

Así mismo se puede observar que a partir del tamaño de 2 Kbytes empezamos a tener que utilizar todo un bloque para almacenar un bitmap que sólo ocupa una parte de él.

 

La elección más prudente estaría alrededor de estas cantidades, pero para decidir habría que conocer un dato que no se da, el tamaño medio de los ficheros. Ante la ausencia de éste cabría optar por 1 Bloque = 1 Kbyte.

 

3)        

Cuando hablamos de la "Cache de Bloques" no nos estamos refiriendo a una memoria cache (asociativa), sino a la estructura de datos, gestionada por el Servidor de Ficheros y construida sobre memoria principal (convencional), que permite aumentar las prestaciones del sistema de Entrada / Salida.

 

De cara a las operaciones de lectura, y dado que la velocidad de acceso al DOC es alta (aunque no la de la memoria principal), podría pensarse que resulta poco útil. No obstante siempre resultará eficaz.

 

La principal utilidad de la Cache de bloques está en las operaciones de escritura.  Dada la característica de no re-escribible in-situ del DOC, cada escritura consume un bloque en estado “borrado”. Tarde o temprano, estos se agotan y habrá que empezar a borrar regiones no en uso para obtener espacio.

 

Es por lo tanto, imprescindible reducir al máximo las operaciones de escritura (y consecuentemente los borrados) sobre el DOC. Para ello utilizaremos la Cache de bloques (cuanto mayor mejor) con una política de escritura write-back o delayed-write, de manera que se amortigüen al máximo el número de escrituras reales sobre el DOC.


 

4)       La estructura de un UFS convencional es:

 

[BB][SB][MBB___][MBI___][VI____][Bloque de datos__________________________________________]

 

 

Así pues, como hemos visto, las dos primeras estructuras (BB y SB) se hayan dispuestas en posición fija conocida de forma implícita. Las tres siguientes (MBB, MBI y VI) se encuentran ubicadas de forma contigua en una posición y tamaño indicadas en el Superbloque.

 

Ahora bien, estas no son las únicas referencias (direcciones de otras estructuras) que contiene un UFS. Cada vez que se indica un número de bloque o un número de inodo (aunque esta última referencia siempre es relativa y se usa para indexar el Vector de inodos), se está refiriendo a otra estructura dispuesta en posición fija.

 

Así, la estructura lógica de la información contenida en el Sistema de Ficheros está establecida como un árbol con su raíz en el inodo raíz (indicado como tal en el SB), y de las entradas de éste directorio, al resto de directorios y ficheros del sistema. Cada entrada de directorio indica a un inodo concreto y cada inodo, a través de sus campos de localización, indica las posiciones fijas de los bloques que ocupa dicho fichero o directorio.


 

5)        

Tomando como punto de partida que el UFS está montado y su Superbloque está en memoria, los accesos necesarios para crear un subdirectorio del directorio raíz será:

1.        1 acceso de lectura del inodo del directorio raíz (normalmente el número 2). También es posible que la operación de montado lo haya traído a memoria y bloqueado allí.

2.        n accesos de lectura del contenido completo del directorio raíz, accediendo a través de los campos directos, indirectos, etc. del inodo, buscando una entrada de directorio libre, así como comprobando que la que queremos crear no existe ya. Si existiese se aborta la operación.

3.        n accesos de lectura del mapa de bits de inodos, buscando uno libre para el nuevo subdirectorio. Si no se encuentra uno libre, la operación se aborta.

4.        1 acceso de escritura del bloque del mapa de bits de inodos donde hemos marcado el bit correspondiente como ocupado.

5.        n acceso de lecturas del mapa de bits de bloques, buscando uno libre para el nuevo subdirectorio. Si no se encuentra uno libre, la operación se aborta.

6.        1 acceso de escritura del bloque del mapa de bits de bloques donde hemos marcado el bit correspondiente como ocupado.

7.        1 acceso de escritura del bloque ubicado, una vez introducidas en él las entradas de directorio “.” y “..” apuntando a sí mismo y al raíz respectivamente.

8.        1 acceso de escritura del inodo ubicado (del bloque que lo contiene), una vez asignado a él el nuevo bloque de datos con sus entradas de directorio.

9.        1 acceso de escritura del bloque del directorio raíz, una vez introducida en él la nueva entrada apuntando al nuevo subdirectorio.

10.     1 acceso de escritura del inodo raíz (del bloque que lo contiene) una vez actualizado en él el campo número de enlaces, así como el tiempo de última modificación.

11.     1 posible acceso de escritura del SB, si en él se refleja información sobre el número de bloque o inodos disponibles en cada momento, una vez actualizado en él dicha información.

 

6)        

Se pregunta por los posibles estados de un bloque. Es preciso hacer notar, que el bloque es la unidad de acceso (y de ubicación, ya que no lo hemos distinguido del concepto de zona) del Sistema de Ficheros, y por tanto, todos los sectores que lo compongan tendrán siempre el mismo estado. Este estado será el del bloque.

 

Dadas las particularidades del DOC, y basándonos en la operación de “Estado de un sector” un bloque puede estar:

 

Según la lógica habitual del Sistema de Ficheros, y consultando el correspondiente bit del MBB, un bloque puede estar:

 

De la combinación de ambas visiones surge el siguiente diagrama de los estados en los que puede estar un bloque:

 



Los estados resultantes son 4:

  1. Virgen = Borrado + Libre. Es un bloque que puede ser reservado (bit = 1) o vuelto a borrar (aunque ya lo está).
  2. Reservado = Borrado + Ocupado. Es un estado transitorio previo a la escritura del mismo.
  3. En Uso = Escrito + Ocupado. Hay en él información útil y actual. Cuando dejemos de usarlo los liberaremos (bit = 0).
  4. Gastado = Escrito + Libre. Es un estado transitorio previo al borrado de la región que lo contiene.

 

Las transiciones entre estados suceden con las acciones indicadas:

 

Las transiciones no indicadas en el diagrama de estados darían lugar a errores (Ej. Re-escritura en el estado Gastado) o a inconsistencias en el Sistema de Ficheros (Ej. Borrar un bloque En Uso o Reservado).

 

7)        

Del diagrama anterior se deduce claramente que sólo se debe borrar una región tal que todos sus bloques estén en los estados Gastado o Virgen, y que estos estados se distinguen de los otros dos posibles porque en el mapa de bits los bloques están marcados como libres.

 

8)        

De todas las consideraciones hechas hasta el momento, podemos resumir en los principales inconvenientes que dificultan la adaptación de un Sistema de Ficheros UFS a un dispositivo tipo DOC en:

 

Para plantear una solución factible, hay que darse cuenta de que re-ubicar un bloque de un fichero no plantea problemas. Dado que la disposición física de los bloques de los ficheros nunca trasciende más allá del propio Sistema de Ficheros, esto es, para referirnos a ellos siempre utilizamos su numeración lógica, si deseamos reubicar (disponer en otra posición física) un bloque de un fichero, no tendríamos más que indicar la nueva posición en el correspondiente campo de su inodo.

 

El problema está las estructuras de datos de Mapas de bits y en el Vector de inodos, que se hayan dispuestas en posición fija y ubicadas de forma contigua. Para poder reubicar estas estructuras y que su disposición física no sea siempre la misma, hay que introducir un nivel más de indirección en el camino de acceso a las mismas, al estilo de lo que inodo supone para los bloques de los ficheros.

 

Para el caso del Vector de Inodos, se utilizaría una especie de Super-Inodo, que referenciado desde el Superbloque nos permitiría el acceso a los inodos, así como su ubicación en cualquier posición física, esto es, en cualquier bloque. De manera equivalente podría hacerse para cada uno de los Mapas de bits, si es que estos efectivamente ocupan un número elevado de bloques. Si ocupasen un número reducido de bloques, podríamos indicar en el mismo Superbloque la dirección de cada uno de los bloques ocupados por estos Mapas de Bits.

 

De esta manera, desplazamos el problema a la disposición fija que normalmente ocupa el propio Superbloque. La disposición física de éste podría escogerse, de forma circular, de entre un conjunto de posiciones prefijadas acompañándolo de un de un número de secuencia que al montar el Sistema de Ficheros nos permita localizar la última versión del mismo.

 

Respecto al problema de obtener espacio ubicable borrando regiones. La solución pasa por realizar esta tarea de forma asíncrona. Normalmente usaríamos un proceso de fondo (daemon o thread del kernel) que trabajaría como un recolector de espacio. Leyendo los ficheros que ocupan bloques en uso, para luego volver a escribirlos en espacio vacío, y así conseguir regiones completas susceptibles de ser borradas.

 

-----Fin.