Se plantean tres
cuestiones independientes sobre el sistema de ficheros de UNIX:
a) Para realizar su
labor, el código del sistema de ficheros debe llevar a cabo numerosos cálculos
aplicando diversas fórmulas. Suponiendo los siguientes parámetros genéricos:
·
TB: tamaño del bloque en bytes; TI:
tamaño del inodo en bytes (divisor exacto de TB).
·
Inodo con D punteros directos, un indirecto simple
y uno doble (por simplicidad, no hay indirecto triple). Un puntero a un bloque
ocupa P bytes.
·
El mapa de bloques libres está almacenado a partir del
bloque MB (recuerde que este mapa sólo guarda el estado de bloques de
datos) y el de inodos libres a partir de MI (recuerde que no existe el
inodo 0).
·
Los inodos están almacenados en el disco a partir del
bloque BI y los datos a partir del bloque BD.
A partir de dichos
parámetros, se pide especificar las siguientes fórmulas (NOTA: sólo se
tendrá en cuenta una respuesta si incluye la fórmula solicitada, no siendo
considerada si aparece únicamente una descripción textual):
a.1) Dado un número de
inodo (I), desarrolle las fórmulas que calculan en qué bloque de disco (B)
se encuentra y a partir de qué byte (b) dentro de dicho bloque se
almacena el inodo.
a.2) Dado un número de
bloque de datos (X), calcule en qué bloque del disco (B) se
encuentra su información de estado (libre/ocupado) y, además, de qué bit (b)
dentro de ese bloque se trata.
a.3) Igual que el
apartado anterior pero siendo X el número de un inodo.
a.4) Dado un determinado
byte (b) de un fichero, calcule, en primer lugar, a qué número de bloque
(BF) del fichero pertenece. A continuación, especifique la fórmula que,
dado un número de bloque dentro del fichero (BF) y su inodo asociado (I),
determina en qué bloque de disco (BD) está almacenado. Esta fórmula se
descompondrá en varias subfórmulas dependiendo de a qué intervalo pertenezca el
bloque del fichero. Se deben especificar los rangos de los distintos intervalos
basándose en los parámetros del sistema de ficheros y detallar la subfórmula
aplicable a cada uno. Para ello, se utilizará la siguiente notación:
·
I[X]: Corresponde con el puntero a bloque
almacenado en la posición X del vector de punteros incluido en el inodo.
·
B(X): Bloque X del disco.
·
B(X)[Y]: Dentro del bloque X del disco (que
será un bloque de índices), corresponde con el puntero almacenado en la
posición Y.
¿Encuentra alguna
similitud entre este proceso de traducción y el usado en alguna otra parte del
sistema operativo?
a.5) Dada la petición
general read(d,buf,tam) y tomando como base
las fórmulas anteriores, explique cómo se determina, a partir de los parámetros
de la llamada, la lista de bloques del fichero involucrados y, a continuación,
la lista de bloques de discos implicados. Se deberá explicar qué estructuras en
memoria del sistema operativo se consultan, cómo se tiene acceso a ellas y qué
datos se extraen de las mismas.
b) Supóngase que el
tamaño del bloque es de 4096 bytes, que el número de enlaces directos es 12 y
que existe un fichero de 81.940 (4096 * 20 + 20) bytes. Se plantean dos formas
de leer completamente el fichero:
1) 20 lecturas de 4096
bytes y una final de 20 bytes.
2) 1 primera lectura de
20 bytes y 20 de 4096 bytes.
Suponiendo que en la
cache de bloques no hay ninguna información sobre ese fichero, calcule para
cada caso cuántos accesos a la cache del sistema de ficheros se producen y cuál
es el porcentaje de aciertos, así como cuántos accesos al disco se realizan.
Compare la eficiencia de estas estrategias.
c) En un sistema con tamaño de bloques de 4096 bytes existe un
fichero de tamaño 8192. Suponiendo que en la cache de bloques no hay ninguna
información sobre ese fichero, analice qué operaciones sobre la cache y sobre
el disco produciría una petición de escritura sobre ese fichero que involucrase
desde el byte 1.000 hasta el 10.000 (recuerde que la cache de bloques de UNIX
no usa write-through).
a) En este apartado se utilizarán los operadores / y % sobre enteros con el mismo significado que tienen en C, o sea,
división entera con truncamiento y resto de la división, respectivamente.
a.1) Dado un número de
inodo I y teniendo en cuenta que el primer inodo es el 1, las fórmulas
que calculan el bloque de disco B donde se encuentra y el byte (b)
dentro de dicho bloque son:
·
B= BI + ((I-1) x TI) / TB
·
b=
((I-1) x TI) % TB
a.2) A partir del número
de bloque de datos X, las fórmulas que calculan el bloque de disco B
donde se encuentra su información de estado y el bit b dentro de dicho
bloque son:
·
B= MB + X / (TB x 8)
·
b= X
% (TB x 8)
a.3) A partir del número
de inodo X, las fórmulas que calculan el bloque de disco B donde
se encuentra su información de estado y el bit b dentro de dicho bloque
son:
·
B= MI + (X-1)
/ (TB x 8)
·
b=
(X-1) % (TB x 8)
a.4) En primer lugar, se presenta la fórmula que calcula el bloque del
fichero BF a partir de un determinado byte (b) del mismo:
·
BF= b / TB
A
continuación, se plantea la fórmula que, dado un número de bloque dentro del
fichero BF y su inodo asociado I, determina el bloque de disco (BD)
donde está almacenado. Esta fórmula se descompone en tres subfórmulas
dependiendo de si el bloque dentro del fichero corresponde con un bloque
directo, un indirecto simple o un indirecto doble, respectivamente.
·
Si BF < D -> I[BF]
·
Si D £ BF <
(D + TB/P) -> B(I[D])[BF-D]
·
Si (D + TB/P) £ BF < (D + TB/P + (TB/P)2)
->
o B(B(I[D+1])[(BF-D-TB/P)/(TB/P)])[(BF-D-TB/P)%(TB/P)]
Nótese en
la última subfórmula, que corresponde con el caso donde el bloque BF
está referenciado a través del puntero indirecto doble (D+1), que la expresión subrayada se usa para
indexar dentro del bloque de primer nivel, mientras que la expresión en cursiva
se usa para acceder al segundo.
Este
proceso de traducción presenta una apreciable similitud con el proceso de
traducción utilizado en un sistema con paginación. Para ello, hay que resaltar
la siguiente equivalencia matemática:
·
Si X es un número de N bits tal que X=2K ->
o Y%X
= K bits de menor peso
de X
o Y/X
= N-K bits de mayor peso de X
Para ver la similitud, nótese, en primer
lugar, que generalmente el valor de TB será una potencia de 2 (TB
= 2t) y, por tanto, suponiendo
que la dirección de un byte del fichero b usa n bits, la primera
fórmula de este apartado sería equivalente a:
·
BF= b/TB ->
n-t bits de mayor peso de b
o Los t bits de menor peso corresponden con el
desplazamiento dentro del bloque
Como se puede observar, es el mismo proceso
que se realiza en un sistema de paginación.
En un sistema de paginación con un solo
nivel, los bits de mayor peso (el equivalente a nuestro BF) se usan para
indexar la tabla de páginas del proceso. En el caso del sistema de ficheros de
UNIX, si BF se corresponde con un bloque directo o indirecto simple,
este valor se usa para acceder a la tabla de punteros directos en el inodo o al
bloque indirecto simple.
El acceso a bloques asociados al indirecto
doble es similar a un sistema de paginación con dos niveles. En este caso, a
partir del valor de BF, una vez ajustado (hay que restarle D+TB/P
bloques que quedan cubiertos por los punteros directos y el indirecto simple),
se calcula cómo acceder a los dos niveles de índices. Para ello, se usa el
valor TB/P que representa cuántas entradas caben en el bloque de índices de
segundo nivel. Dado que TB es potencia de 2 (2t) y, normalmente, también P (2k), el valor de la división también lo será (TB/P=2t-k=2e).
El cálculo es el siguiente:
·
Para acceder al primer nivel se divide el valor de BF
ajustado, que ocupa n-t bits, entre TB/P -> (n-t)-e bits de mayor peso de dicho valor ajustado.
·
Para acceder al segundo nivel se calcula el resto entre
el valor de BF ajustado y TB/P -> e bits de menor peso de dicho valor ajustado.
Nótese que cuando BF corresponde con
el puntero indirecto doble es muy similar al proceso de traducción en un
sistema con 2 niveles: La dirección del byte b dentro del fichero,
después del ajuste debido a la existencia de punteros directos y el indirecto
simple, se descompone en tres partes:
·
Los t bits de
menor peso corresponden con el desplazamiento dentro del bloque.
·
Los e bits
intermedios con el desplazamiento dentro del bloque de punteros de segundo nivel.
·
Los (n-t)-e
bits de mayor peso con el desplazamiento dentro del bloque de punteros de
primer nivel.
Si se hubiera planteado un inodo más realista
con un indirecto triple, se mantendría la analogía correspondiendo con un
sistema de paginación de tres niveles.
Resumiendo, la traducción usando el inodo es
similar a la usada en los sistemas de paginación, pero resultando un híbrido de
sistemas con distintos niveles. En cualquier caso, es importante resaltar que
una diferencia significativa es que el proceso de traducción de un sistema de
memoria se realiza por hardware, ya que se debe aplicar a cada referencia a
memoria, mientras que la traducción de ficheros la hace el sistema operativo,
dado que sólo se aplica en los accesos a ficheros.
Hay que hacer notar, por último, que, gracias
a que los tamaños de distintos elementos del sistema de ficheros son potencias
de 2, el sistema operativo puede realizar más eficientemente las operaciones de
división y resto requeridas por la traducción.
a.5) A partir de la petición read(d,buf,tam),
la lista de bloques de disco implicados se determina de la siguiente forma:
1)
Se accede al BCP del proceso y
dentro de éste a la tabla de descriptores abiertos, concretamente, a la
posición d de esa tabla.
2)
En esa posición se almacena qué
entrada de la tabla intermedia de ficheros (tabla filp) corresponde con
ese descriptor. En dicha entrada se almacena, entre otras cosas, la posición
actual (offset) dentro del fichero y una referencia al inodo I,
que estará almacenado en la tabla de inodos en memoria, puesto que el fichero
se abrió previamente.
3)
El rango de bytes que hay que leer
correponden con el intervalo [offset, offset+tam-1].
Aplicando a los valores extremos de ese rango la primera fórmula del apartado
anterior, se obtendrá el primer (BFini) y último bloque (BFfin)
del fichero que hay que leer, con lo que el intervalo resultante será: [BFini,
BFfin].
4)
Por último, usando el inodo I,
habrá que aplicar a cada uno de los bloques de esa lista la segunda fórmula del
apartado anterior (la que relaciona bloques de fichero y bloques de disco),
obteniendo la lista de bloques de disco.
b) Dado que se pretenden comparar dos formas de acceso a un fichero,
nos vamos a centrar en la lectura propiamente dicha, puesto que la parte de
apertura y cierre del fichero será común en ambas estrategias.
b.1) Hay que leer 21 bloques que producirán los siguientes accesos a
la cache:
Nótese que la última lectura, aunque sea de sólo 20 bytes, implica los mismos accesos a la cache que las lecturas anteriores.
En resumen:
b.2) Hay que leer 21 bloques que producirán los siguientes accesos a
la cache:
En resumen:
c) Aplicando la primera fórmula del apartado a.4, el rango
del fichero afectado por la lectura corresponde con los tres primeros bloques
del mismo, generando, por tanto, tres accesos a la cache:
Hay que
resaltar que, dado que no se usa write-through, las escrituras en los
tres bloques no causan escrituras inmediatas en el disco, sino que éstas se
diferirán hasta que el bloque sea expulsado o se cumpla el plazo de volcado
periódico. Asimismo, nótese que en cualquiera de los tres accesos, a la hora de
reservar un buffer libre en la cache, podría haberse requerido una expulsión de
otro bloque que estuviese modificado, produciéndose, en ese caso, una escritura
en disco.