Diseño de Sistemas Operativos

Junio de 2002

Sistema de Ficheros

 

Se desea dimensionar un Sistema de Ficheros UNIX para un Servidor de audio Streaming. Este Servidor envía por la red, al Cliente que se lo pide, audio comprimido (1 minuto de música por Megabyte de datos), para que el Cliente lo reproduzca en tiempo real, esto es, según lo descarga y sin almacenarlo primero en un fichero local.

Este Sistema de Ficheros irá sobre un disco duro cuyas características simplificadas son las siguientes:

 

a)      En función de los siguientes parámetros:

            TP:            Logaritmo en base 2 del tiempo de posicionamiento.
                        (Ej. Para el caso medio del disco valdría –11)

            TB:            Logaritmo en base 2 del tamaño de bloque.
                        (Ej. Para un bloque de 1Kilobyte valdría 10)

Formule el tiempo de acceso a un bloque [segundos].

Formule el ancho de banda del Sistema de Ficheros [Bloques / segundo].

Formule el ratio de compresión [segundos de audio / Bloque].

Formule el grado de concurrencia [segundos de audio / segundo].

 

El grado de concurrencia indicará el número de ficheros de audio comprimido que es posible servir concurrentemente.

 

b)      Calcule qué tamaño de bloque aseguraría un grado de concurrencia de 60 sin que se viole la restricción de tiempo real.

 

Considere un fichero de 10 minutos de audio que está totalmente fragmentado. ¿Cuánto tiempo se tardaría en leer de forma secuencial todo el fichero? Calcule los casos medio y peor.

 

c)      Dibuje el formato de este Sistema de Ficheros indicando las dimensiones de cada una de sus partes. Haga las suposiciones que considere razonables.

 

d)      ¿Indique qué estrategias de planificación de accesos a disco serían adecuadas en un sistema como el presentado y cuáles no?


SOLUCIÓN

 

a)

 

Acceso = Posicionamiento + Latencia + Transferencia

Posicionamiento            =            2TP (segundos)

                                                =            2-11 (segundos)                         (caso medio)

                                                =            2-8 (segundos)                         (caso peor)

Latencia          =            ½ Rotación            =            2-8 (segundos) (caso medio)

                                    =            1 Rotación            =            2-7 (segundos) (caso peor)

Transferencia: Un disco transfiere datos según los sobrevuela.

Si se transfiere una pista completa en una rotación, un bloque en:

                        211*29 (bytes)            ___________  2-7 (segundos)

                        2TB (bytes)            ___________            Transferencia 1 bloque = 2TB-27 (segundos)

 

TA: Tiempo de Acceso a 1 bloque (segundos)

                        =            2-11 + 2-8 + 2TB-27 (segundos)                              (caso medio)

                        =            2-8 + 2-7 + 2TB-27 (segundos)                         (caso peor)

 

AB: Ancho de Banda (bloques / segundo)

                        =            1 / TA

 

RC: Ratio de Compresión (seg. audio / bloque)

            Si 1 Megabyte son 60 segundos de audio, 1 bloque serán:

            220 (bytes)            __________    60 (seg.audio)

            2TB (bytes)            __________    RC = 60 * 2TB-20 (seg.audio / bloque)

 

GC: Grado de Concurrencia (seg.audio / segundo)

            =            RC * AB

            =            (60 * 2TB-20) / (2-11 + 2-8 + 2TB-27) (seg.audio / segundo)                (caso medio)

            =            (60 * 2TB-20) / (2-8 + 2-7 + 2TB-27) (seg.audio / segundo)            (caso peor)

 

b)

Para que no se viole la restricción de tiempo real, debemos aplicar las fórmulas correspondientes al caso peor.

GC = 60 = (60 * 2TB-20) / (2-8 + 2-7 + 2TB-27)

Despejamos 2TB...

            2TB            =            232 * (28 + 27) / (227 - 220)    =            ~ 12384.7

            213            =            8192                                        <

            214            =            16384                                      >

Luego el tamaño de bloque adecuado será:            2TB = 214 = 16 Kilobytes

 

En número de bloques del disco son:

            213 (cilindros) * 23 (pistas / cilindro) * 211 (sectores / pista) * 29 (bytes / sector) / 2TB (bytes / bloque) = .

            213+3+11+9-14 (bloques) = 222 (bloques)

Luego para direccionar los bloques necesitaremos direcciones de 32 bits.

Y el número de direcciones que caben en un bloque de indirección serán:

            2TB (bytes / bloque) / 24 (bytes / dirección) = 210 = 1024 (direcciones / bloque)

 

Un fichero de 10 Minutos de audio necesita:

            10 * 60 (seg.audio) / RC (seg.audio / bloque) = 10 / 2TB-20 = 10 * 26 = 640 (bloques (de datos))

Para acceder a estos 640 bloques de datos, considerando inodos de 10 direcciones directas y bloques de indirección con 1024 entradas será necesario hacer uso del simple indirecto, luego habrá que acceder también al un bloque de indirección. Realmente podríamos considerar este bloque extra como despreciable en nuestros cálculos.

 

En acceder a estos 641 bloques, tardaríamos

            641 (bloques) * TA (segundos / bloque)            =

                        = 641 * (2-11 + 2-8 + 214-27)   = ~2.895 (segundos)            (caso medio)

                        = 641 * (2-8 + 2-7 + 214-27)   = ~7.589 (segundos)            (caso peor)

 

c)

En el apartado anterior hemos deducido un tamaño de bloque de 214 (bytes), y que el dispositivo tiene 222 bloques luego necesitaremos usar direcciones a bloque de 32 bits.

 

                        [BB][SB][MBB][MBI][__VI__][____DATOS____]

 

[BB] Bloque de Boot. Ocupa un bloque.

[SB] Super Bloque. Ocupa un bloque.

[MBB] Mapa de Bits de Bloque. Precisa un bit por bloque, luego ocupa:

            222 (bloques) * 1 (bit / bloque) / 23 (bits / byte) / 214 (bytes / bloque) = 222-3-14 = 25 (bloques)

[MBI] Mapa de Bits de I-nodos. Precisa un bit por i-nodo.

Debemos decidir el número de i-nodos necesario. Normalmente, para un sistema de ficheros de propósito general, asumimos un i-nodo por cada bloque, pero para un uso especializado como el planteado, y dado que los ficheros van a ser de tamaño mediano/grande, podríamos usar una cantidad menor. Por ejemplo un i-nodo por cada 32 bloques. Con lo que nos queda:

            222-5 (inodos) * 1 (bit / inodo) / 23 (bits / byte) / 214 (bytes / bloque) = 222-5-3-14 = 1 (bloque)

[VI] Vector de I-nodos. Suponiendo i-nodos de 128 bytes:

            217 (inodos) * 27 (bytes / inodo) / 214 (bytes / bloque) = 217+7-14 = 210 (bloques)

[DATOS] Espacio para datos, sería el resto.

            222 – 1 – 1 – 25 – 1 – 210 (bloques)                     ~0,025% de metadatos

 

d)

Casi todas las estrategias de planificación de accesos a disco disponibles (SCAN, C-SCAN, LOOK, etc.) mejoran las prestaciones medias del dispositivo al que se aplican, pero tienen el inconveniente de que lo consiguen cambiando el orden original de dichas peticiones. Luego la aplicación de estas estrategias hace que el sistema no sea determinista, esto es, impide asegurar un tiempo máximo por petición, ya que se nos pueden "colar" un número indeterminado de otras peticiones.

Por esta razón la única estrategia de planificación que cabe ser aplicada en un sistema con restricciones de tiempo real, es la que mantiene el orden original de las peticiones, esto es, la planificación FIFO.