algoritmos planeacion bueno

5/10/2018 algoritmos planeacion bueno - slidepdf.com

http://slidepdf.com/reader/full/algoritmos-planeacion-bueno 1/26

Problemas de Sistemas de Archivo

SO2

Abril 2.000

PROBLEMAS RESUELTOS

Cuestion 1

Dado un disco de cabeza movil con 200 cilindros, numerados de 0 a 199 se considera que:

Actualmente sirve una solicitud en el cilindro 143.

Previamente se solicito el acceso al cilindro 125.

La cola de solicitudes se mantiene en orden FIFO: 86, 147, 91, 177, 94, 150, 102, 175, 130.

Se pide:

Determinar el movimiento total de la cabeza necesario para satisfacer estas solicitudes con los siguientes algoritmos

de planificacion de disco:

– FCFS.

– SSTF.

– SCAN.

– LOOK.

– C-SCAN.

Cuestion 2

Dado un disco de cabeza movil con 200 cilindros, numerados de 0 a 199 y con un tiempo promedio de acceso (rotacion

+ transferencia) de 20 unidades de tiempo se trata de determinar el tiempo total de servicio que se requiere para atender

las siguientes peticiones:

(0,30), (40,10), (45,40), (60, 60), (100,50), (120, 5), (140, 100), (160, 120)

donde la primera componente de cada peticion se refiere al instante de tiempo en el que se efectua dicha peticion y la

segunda componente indica el cilindro al que se pretende acceder. Se considera que el tiempo de posicionamiento entre

cilindros contiguos es igual a 1 unidad de tiempo.

Aplicar para el calculo del tiempo total de servicio los siguientes algoritmos:

FCFS.

SSTF.

SCAN.

LOOK.

1



C-SCAN.

Nota: El cabezal del disco se encuentra inicialmente posicionado en el cilindro 0 y el servicio de las peticiones se

realiza en el sentido de numeros de cilindro crecientes.

Cuestion 3

Dada una estructura de disco de doble cara con 80 cilindros y 18 sectores por pista y un tama no de sector de 512 bytes,

se pide:

Determinar la capacidad del disco.

Dada la correspondencia entre sectores fısicos y logicos, se trata de determinar la direccion fısica (cilindro, cabeza,

sector) del numero de sector logico 1234.

De forma analoga se desea determinar cual es el numero de sector logico asociado a la direccion f ısica (47, 1, 15).

Cilindro Cabeza Sector Sector logico

0 0 0 0

........ ........ ........ .............

0 0 17 17

0 1 0 18

........ ........ ........ .............

0 1 17 35

1 0 0 36

........ ........ ........ .............

........ ........ ........ .............

79 1 17 2879

Cuestion 4

Dado un disco de 20 Mb de capacidad total con los siguientes parametros:

Clusters (bloques) de tamano 1K. Sectores de 512 bytes.

Numeros de bloque de 16 bits.

Se pide:

Calcular el numero de bloques necesarios para la gestion de bloques libres mediante:

– Lista enlazada.

– Mapa de bits.

Determinar la estructura del disco si lo utilizamos enteramente para MS-DOS:

– Calcular el numero de sectores reservados a la FAT y su copia.

– Calcular el numero de sectores reservados para el directorio raız (considerar un maximo de 512 entradas).– Determinar el numero de clusters de datos disponibles.

Calcular el mejor y peor caso en el numero de accesos a bloques de disco para leer el 33¡£ ¢

cluster de un fichero

MS-DOS situado en el directorio raız en el siguiente caso:

– Suponiendo que la cache de la FAT en memoria es 1K.

2



Realizar el mismo calculo si el fichero se encuentra en el directorio \PRUEBA que contiene 33 entradas en total.

NOTA: En los dos ultimos apartados de esta cuestion 4 se asumira que las lecturas en la FAT y en el directorio raız

obtienen un bloque entero, en lugar de un solo sector.

Cuestion 5

Determinar el tamano maximo teorico (sin tener en cuenta el tamano real que tendra el dispositivo sobre el que deba

residir el fichero) de un fichero UNIX, especificando los bloques direccionados con cada tipo de puntero. Los parametros

corresponden a los siguientes valores:

Punteros a zonas de datos de 32 bits.

Tamano de bloque 1K (1 zona = 1 bloque).

Estructura de nodo-i:

– 10 punteros directos.

– 1 puntero indirecto.

– 1 puntero indirecto doble.

– 1 puntero indirecto triple.

Realizar el mismo calculo para un fichero en MINIX con los siguientes parametros:



Estructura de nodo-i:

– 7 punteros directos.

– 1 puntero indirecto.

– 1 puntero indirecto doble.

Cuestion 6

Determinar la estructura de un disco de 20 Mb en MINIX con los siguientes par ametros:



Tamano de nodo-i de 32 bytes.

Numero maximo de nodos-i: 512.

Se pide:

Especifique claramente todas las estructuras de datos que forman el sistema de archivos y los bloques que ocupan.

En caso de resultar danada la estructura del mapa de bits de zonas, piense la forma de reconstruirla con la infor-

macion de la que se dispone en el resto de estructuras del sistema de archivos (se supone que estas se conservan

inalteradas).

3



Cuestion 7

Suponga que se ha desarrollado una version de MINIX en la cual el tamano del bloque se ha cambiado a 128 bytes (1

bloque = 1 zona).

Suponga tambien que se dispone de un disco duro (/dev/hd5) formateado con bloques de 128 bytes, con capacidad

para almacenar 10240 bloques con un numero maximo de ficheros posibles igual a 127.

En este disco existen tres directorios:

Directorio / Con 10 entradas (todas las entradas incluidas)

Directorio /bin Con 16 entradas (ıdem)

Directorio /lib Con 20 entradas (ıdem)

La longitud de todos los ficheros es de 768 bytes, salvo dos ficheros, /bin/mediano y /bin/grande cuyas

longitudes respectivas son 1024 bytes y 10240 bytes.

SE PIDE:

1. Como esta estructurado el disco.

2. Numero de bloques para el mapa de nodos-i.

3. Numero de bloques para el mapa de zonas.

4. Numero de bloques de nodos-i.

5. Numero total de zonas de datos.

6. Numero de nodos-i utilizados.

7. Numero de zonas utilizadas para:

(a) Contener datos convencionales de ficheros regulares.

(b) Contener entradas de directorios.

(c) Contener referencias a otros bloques.

Justifique adecuadamente sus respuestas.

Cuestion 8

En el sistema operativo MINIX se introducen los siguientes cambios en el diseno del sistema de ficheros:

El tamano de bloque se reduce a 32 bytes.

El tamano de una entrada de directorio se reduce a 8 bytes (2 bytes para el numero de nodo-i y 6 para el nombre del

fichero).

El tamano del nodo-i se reduce a 16 bytes. Los primeros 8 bytes se emplean para almacenar informacion general

(atributos de fichero), representada en la figura por XX, y los 8 bytes restantes para almacenar los punteros a las

zonas pertenecientes al fichero: dos punteros directos, un indirecto simple y un indirecto doble, tal y como muestra

la figura:

XX

numero de zona 0

numero de zona 1

indirecto

indirecto doble

4





SE PIDE:

1. ¿ Cual podra ser el tamano mınimo de un puntero a zona ?

2. ¿ Cuantos punteros podran ubicarse en una misma zona ?

3. Si se necesita 32 bytes por cada nodo-i y de ellos 16 pueden destinarse a punteros a zona, ¿ que esquema de los

siguientes es preferible y por que ?

(a) Que todos los punteros sean directos.

(b) Todos los punteros directos, excepto un puntero indirecto simple.(c) Todos los punteros directos, excepto dos punteros indirectos simples.

(d) Todos los punteros directos, excepto un puntero indirecto simple y otro indirecto doble.

Cuestion 10Se tiene un dispositivo de almacenamiento de 32 Kb, con bloques de 512 bytes (1 zona = 1 bloque). Este dispositivo

va a ser inicializado para poder utilizar un sistema de archivo similar al de MINIX con entradas de directorio de 16 bytes,

un maximo de 31 archivos y nodos-i de 16 bytes de los cuales 60 bits pueden dedicarse a punteros directos a zona. Se

supone que el tamano de los punteros a zona es el mınimo posible.

SE PIDE:

1. Decidir como quedara estructurado el disco. Es decir, cuantos bloques se dedican a cada una de las estructuras que

mantiene el sistema de archivo.

2. ¿ Cual sera el tamano maximo de un archivo ?

3. Asumiendo que no se permite crear enlaces fısicos, ¿ cuantas entradas podra tener como maximo un directorio ?

¿ Cuantos bloques podra llegar a ocupar ?

4. ¿ Cuantos bloques pueden llegar a quedar libres si se crea el maximo numero de archivos posible, pero todos ellos

con tamano mınimo ?

5. Determinar como quedaran los mapas de bits de nodos-i y de zonas despues de realizar las acciones que se citan

a continuacion (y en ese orden). Se supone que un 1 en el mapa de bits indica que el elemento representado estalibre. Ademas, se supone que siempre se utiliza el nodo-i o zona libre con numero mas bajo.

Comentar tambien que bloques tiene asignados cada archivo.

Las acciones son las siguientes:

Inicializar el disco.

Crear un directorio /dir1.

Crear un directorio /dir2.

Crear y escribir un archivo /dir1/a de 2.000 bytes.

Borrar el directorio /dir2.

Crear y escribir un archivo /dir1/b de 4.900 bytes. Crear y escribir un archivo /dir1/c de 3.500 bytes.

Borrar el archivo /dir1/a.

Anadir datos al archivo /dir1/c. Se anade 1 Kb al final del archivo.

6. Determinar el contenido de los archivos de tipo directorio que hayan quedado tras realizar las acciones citadas en

el punto anterior.

6











2. Direccion f ısica del bloque logico 1234. Suponemos un solo sector por bloque.

Las direcciones fısicas tienen la siguiente estructura:

(num. cilindro, num. cara, num. sector)

Ademas, la numeracion se sigue del siguiente modo: hasta que no se han numerado todos los sectores de una cara

no se pasa a la siguiente cara del mismo cilindro y hasta que no se hayan numerado todas las caras de un cilindro

no se pasa al siguiente.

Por tanto, para obtener la direccion fısica efectuaremos lo siguiente:

(a) Dividiremos la direccion logica por el numero de sectores por pista. O sea:

1234 div 18 = 68

1234 mod 18 = 10

Esto quiere decir que con la direccion logica 1234 se han podido “llenar” 68 caras y se esta referenciando el

undecimo sector (ya que empezamos a numerarlos a partir de cero) de la sexagesima novena cara.

(b) Dividiremos el numero de caras “completas” obtenido en el punto anterior por el numero de caras por cilindro

que admite el disco. Ası:

68 div 2 = 34

68 mod 2 = 0

Esto se interpreta como que hemos podido “completar” 34 cilindros y estamos en la primera cara del trig esimo

quinto.

Por tanto, la direccion fısica pedida es: ( 34, 0, 10 )

Es decir, cilindro 34, cara 0, sector 10.

3. Direccion logica para la direccion fısica ( 47, 1, 15 ).

Suponiendo direcciones fısicas de la forma ( i, j, k ), basta con aplicar la formula:

PR Q

¨ S

(E $T "T UT V3 &X WY $a Y bc § df eg (h Ui bq pB br $% V% Ui Wt su W

Pw v

p% xy � W£ �

El resultado obtenido es:

PR Q

¨� 9T �

(

9a �

§ d

9

(h D� � �r �G �

¨� 9T �

(

9T �

! �

�� 9B �

(

9

�

9

F

¨@ 9

�G D

�

Con lo que el numero de bloque logico es el 1725.

Cuestion 4

1. Bloques necesarios si se utiliza lista enlazada. La lista enlazada propiamente dicha utiliza un puntero al final

de cada bloque para enlazarlo con el siguiente bloque libre. O sea, se utilizan los propios bloques libres para

mantenerlos en la lista. Por tanto, no es necesario ningun bloque adicional para mantener el control sobre que

bloques tenemos libres.

En algunos casos, para compactar la lista, se utilizan unos pocos bloques libres para guardar (de manera similar a un

ındice enlazado) todos los numeros de los bloques disponibles. Esto no aporta ninguna variacion al caso comentado

en el parrafo anterior, pues estos bloques se van liberando a medida que se van asignando bloques disponibles. Al

final, si se asignan todos los bloques a ficheros, no queda ningun bloque dedicado a mantener la lista enlazada.

11



2. Bloques necesarios si se utiliza mapa de bits.

El tamano de bloque es de 1.024 bytes, con lo que en cada bloque tendremos 8.192 bits para mantener el mapa.

Nuestro disco tiene 20 Mb. Eso representa 20 * 1.024 bloques, o sea, 20.480 bloques.

Por tanto, utilizando mapa de bits necesitamos:

PR Q

¨

DG F�

9

Fq D% �

�

9

Fq D% �

¨

D6 F

�

¨

D� �

�

H� �

Q

su x% �B �� "% $

3. Estructura del disco.

(a) Tamano de la FAT (en sectores):

Como utilizamos numeros de cluster de 16 bits, en un sector de 512 bytes se podran mantener 256 numeros

de cluster. Por tanto, tendremos 256 entradas de la FAT en cada sector.

El numero de clusters en nuestro disco ha sido calculado previamente y es igual a 20480. (En la practica es

ligeramente inferior, puesto que la informacion mantenida en la cabecera no se organiza en clusters, sino en

sectores, y no puede utilizarse para mantener ficheros. Sin embargo, esto no afecta demasiado a la hora de

efectuar los calculos: el numero correcto de clusters es 20383 como veremos dentro de un momento, pero al

dividirlo entre 256 y redondearlo hacia arriba dara el mismo resultado.)

Por tanto:

¥

bq � �w

¨

� �© � Ui s � $a Y "a pG $

"

P

`£ pB b

v

br $B V6 $T "T Ui Y xB p

¨

D6 FG �

�

F

D

�6 j

¨ �

F

(b) Directorio raız (en sectores):

Una entrada de directorio MS-DOS ocupa 32 bytes. Por tanto, en un sector tendremos:

"

P

`£ p% b

v

br $% VG $T "B U5 Y xB p

¨

¥

bq �k Y ¡Y

0

¤' ¢

¥

bq � ¡Y 4

0

¢ 2 m l5 2

¨

�r 9

D

�

D

¨� 9a j

Si el directorio raız mantiene un maximo de 512 entradas, deberemos asignarle:

P

� �© �n $a "B U5 Y xB p% "% $

¨

�r 9

D

9a j

¨

�

D

(c) Clusters de datos:

Del total de 20480 bloques que posee el disco, tenemos reservados los siguientes:

Por el sector de arranque primario o MBR (Master Boot Record): 1 sector (medio bloque).

Por el sector de arranque de la particion DOS: 1 sector (medio bloque).

Por la FAT y su copia: 80 + 80 = 160 sectores (80 bloques).

Por el directorio raız: 32 sectores (16 bloques).

O sea, en total 97 bloques. Por tanto, para clusters de datos tendremos 20480 - 97 = 20383 clusters.

4. Mejor y peor caso para leer el cluster 33¤

de un archivo del directorio raız.

Mejor caso

Tarea Accesos Acumul.

Lectura y busqueda del archivo en el primer bloque del 1 1

directorio raız. Encontramos la entrada de directorio de

ese archivo en este primer bloque del raız. Obtenemos, portanto, el numero del primer cluster del archivo.

Recorrido de la FAT para buscar el trigesimo tercer cluster 0 1

del archivo. Todos los numeros de cluster explorados se

encuentran en la cache para la FAT.

Acceso al cluster pedido. 1 2

12





Cuestion 5Para determinar el tamano maximo de un archivo en un sistema UNIX debemos tener en cuenta dos cifras:

El numero maximo de bloques que puede llegarse a mantener. Esto se determina a partir del tamano de los punteros

a zona, ya que no podremos tener una particion de disco mayor que este lımite y un archivo no puede extenderse

por mas de una particion.

Cuantos punteros a zona pueden llegarse a guardar a partir de un nodo-i, teniendo en cuenta los niveles de indirec-

cion que pueden mantenerse.

El tamano maximo del archivo sera el menor de estos dos valores.Veamos los dos casos presentados:

UNIX.

Segun el lımite debido al tamano de puntero, tenemos que el tamano maximo serıa:

tam. particion = 2 o bloques = 4 Gbloques

¨w

4 Tbytes

Segun el numero de punteros tendremos:

En una misma zona podra llegar a haber 1024 / 4 = 256 punteros a zona, ya que una zona tiene 1024 bytes y cada

puntero ocupa 4.

Por tanto, el numero de punteros a zona sera:

Tipo de puntero Punteros directos

Directos en nodo-i. 10

Indirecto simple. 256

Indirecto doble. 256 = 65.536

Indirecto triple. 256o = 16.777.216

TOTAL: 16.843.018

Por tanto, esta cifra obtenida es menor que la anterior y el tamano maximo del archivo sera de:

16.843.018 bloques = 16.842.018 Kb¨w

16’064 Gbytes

MINIX.

Debido al tamano de puntero, el tamano maximo es en este caso:

tam. particion = 2 8 bloques = 64 Kbloques

¨R

64 Mbytes

Segun el numero de punteros tendremos:

En una zona podra haber 1024 / 2 = 512 punteros a zona, ya que una zona tiene 1024 bytes y cada puntero ocupa 2.

Tipo de puntero Punteros directos

Directos en nodo-i. 7

Indirecto simple. 512

Indirecto doble. 512 = 262.144

TOTAL: 262.663

Esto hace un total de 262.663 bloques¨R

256’5 Mbytes.

En este caso, el lımite lo proporciona el tamano de la particion. Con esto el tamano maximo queda en 64 Mbytes.

14



Cuestion 6


Un disco MINIX tiene las siguientes partes:

(a) Bloque de arranque: 1.

(b) Superbloque: 1.

(c) Mapa de bits para nodos-i: 1.

Necesitamos un bit por archivo. Como el disco unicamente va a permitir 512 archivos, basta con 512 bits. Enla practica, el autor de MINIX anadio una entrada mas en el mapa de bits, correspondiente al nodo-i 0. Por

tanto, en el mapa existirıan realmente 513 bits, aunque en disco solo se necesitarıa espacio para guardar 512

nodos-i.

En este sistema un bloque tiene 1024 bytes (8192 bits), con lo que el mapa cabe en un solo bloque.

(d) Mapa de bits para zonas: 3.

Un disco de 20 Mb tiene 20480 bloques de 1 Kb. En cada bloque caben 8 * 1024 bits. Por tanto, se tendr a:

PR Q

¨

DG F�

9

F D% �

�

9

Fq D% �

¨

DG F

�

¨

D� �

�

H �

(e) Bloques para nodos-i: 16.

Como cada nodo-i ocupa 32 bytes, en un bloque cabran 1024 / 32 = 32 nodos-i.Si vamos a tener 512 nodos-i, necesitaremos:

PR Q

¨

�r 9

D

�

D

¨@ 9a j

(f) Bloques para datos: 20458.

Unicamente hay que descontar los bloques vistos en los puntos anteriores de la capacidad total del disco.

PR Q

¨

DG F6 �

�

F{ z| d

9

(

9

(

9

(

�

(

9T j

�

¨

DG FG �

�

F{ z} D D

¨

D6 FG �

�6 �

2. Reconstruccion del mapa de bits de zonas.

Suponiendo que el resto del disco no ha resultado danado, se podrıa realizar lo siguiente:

(a) Reinicializar todo el mapa de bits de zonas de manera que todos las zonas de disco aparezcan como libres.

(b) Siguiendo el mapa de bits para nodos-i, recorrer todos los nodos-i utilizados. Para cada uno de ellos habra que

consultar sus punteros directos a zona y marcar tales zonas como ocupadas en el mapa de bits que se dano.

Lo mismo para los punteros indirecto simple e indirecto doble, bajando hasta el nivel de zona de punteros

directos. De esta manera todas las zonas utilizadas por todos los archivos son marcadas en el mapa de bits

como “en uso”.

Una vez terminados estos dos pasos, el mapa de bits para zonas estara recuperado.

Cuestion 7Dado que ha cambiado el tamano del bloque, es necesario en primer lugar calcular la cantidad de elementos que puede

contener un bloque en funcion de su tipo:

tipo de bloque tamano del elemento numero de elementos

mapas de bits 1 bit 1024

nodos-i 32 bytes 4

entradas de directorios 16 bytes 8

referencias a zonas 2 bytes 64

datos 1 byte 128

15



1. Como esta estructurado el disco

Bloque de arranque- Superbloque- Mapa de nodos-i- Mapa de zonas- Nodos-i- Datos

2. Numero de bloques del mapa de nodos-i. 1

El numero maximo de nodos-i necesarios es igual a 127. Por lo tanto, basta un solo bloque para contener el mapa

de nodos-i, puesto que tiene capacidad para 1024 bits.

3. Numero de bloques del mapa de zonas. 10

El numero total de zonas (bloques) es igual a 10.240. Como cada bloque tiene capacidad para 1024 bits, son

necesarios 10 bloques para albergar todo el mapa de zonas.

4. Numero de bloques de nodos-i. 32

El numero maximo de nodos-i necesarios es igual a 127. Puesto que un bloque tiene capacidad para 4 nodos-i, son

necesarios 32 para contener todos los nodos-i.

5. Numero total de bloques de datos. 10.195

Se han consumido en los apartados anteriores 1, 10 y 32 bloques. Junto con los bloques de arranque y superbloque,

dan un total de 45 bloques consumidos. Siendo el total de bloques igual a 10.240, quedan 10.195 bloques de

datos, los cuales se pueden utilizar para albergar datos convencionales, entradas de directorios o referencias a otros

bloques.

6. Numero de nodos-i utilizados. 41

Un nodo-i por cada directorio o fichero regular.Directorio raız (/) 1

Directorio /bin 1

Directorio /lib 1

Ficheros regulares de / 10 - 2 (. y ..) -2 (/bin y /lib) 6

Ficheros regulares de /bin 16 - 2 (. y ..) 14

Ficheros regulares de /lib 20 - 2 (. y ..) 18

TOTAL 41

7. Numero de bloques utilizados para:

(a) Contener datos convencionales de ficheros regulares. 304

El numero de ficheros regulares es igual a 38. (41 menos 3 directorios). La ocupacion en disco de los datos

de estos ficheros es la siguiente:36 ficheros regulares de 768 bytes (6 bloques) 216

1 fichero regular de 1024 bytes (8 bloques) 8

1 fichero regular de 10240 bytes (80 bloques) 80

TOTAL 304

(b) Contener entradas de directorios. 7Directorio raız (/) 10 entradas 2

Directorio /bin 16 entradas 2

Directorio /lib 20 entradas 3

TOTAL 7

(c) Contener referencias a otros bloques. 4

Los ficheros regulares de 768 bytes no utilizan los punteros indirectos del nodo-i, puesto que ocupan 6 zonas

y en el nodo-i en MINIX existen 7 referencias directas.

El fichero /bin/mediano necesita 8 zonas de datos.

Las primeras 7 zonas son referenciados directamente en el nodo-i.

El bloque numero 7 necesita la referencia simple indirecta del nodo-i. Esta referencia necesita una zona de

datos, cuyos primeros dos bytes apuntan a la zona numero 7 del fichero, y el resto del bloque no se utiliza.

El fichero /bin/grande necesita 80 zonas de datos.

16



Las primeras 7 zonas son referenciadas directamente en el nodo-i.

Las 64 zonas siguientes necesitan la referencia simple indirecta del nodo-i. Esta referencia necesita una zona

de datos, que se utiliza completamente.

Las ultimas 9 zonas necesitan la referencia doble indirecta del nodo-i. Esta referencia necesita una zona de

datos, cuyos primeros dos bytes apuntan a otra zona de datos, que contiene las ultimas 9 referencias del

fichero.

Cuestion 8El primer paso para resolver el problema consistira en determinar que bloques son utilizados para mantener los nodos-i

y otras estructuras al principio del disco.

Veamos:

Supondremos que el bloque de arranque sigue siendo unico: 1.

Necesitamos tambien un bloque para el superbloque: 1.

Mapa de bits para nodos-i: 1.

Como unicamente necesitamos 100 nodos-i y un bloque tiene 32 * 8 = 256 bits, basta con un bloque para mantener

esta informacion.

Mapa de bits para zonas de datos: 4.

Si el dispositivo tiene 32 Kb y el tamano de bloque es de 32 bytes, tendra 1024 bloques. Si cada bloque puede

mantener 256 bits, el mapa necesita 1024 / 256 = 4 bloques.

Bloques para nodos-i: 50.

Si hay 100 nodos-i y en cada bloque caben 2, necesitaremos 100 / 2 = 50 bloques.

Bloques para datos: 967.

Los bloques ya citados contabilizan un total de 57. Si el dispositivo tiene 1024, la diferencia 1024 - 57 = 967 ser a

la cantidad de bloques para datos (zonas) que tendra el dispositivo.

Con esto sabemos que:

Los bloques del 0 al 6 se utilizan para mantener el bloque de arranque, el superbloque y los mapas de bits.

El bloque 7 sera el primero que mantenga nodos-i. En concreto mantendra los nodos-i 0 y 1. En general, el bloque

i entre 7 y 56, mantiene los nodos-i: (2*i - 14) y (2*i - 13).

El bloque 57 sera el primero que mantenga zonas para datos, directorios y zonas de punteros a zona.

1. Arbol de directorios.

Veamos sobre que archivos mantenemos informacion. Segun lo dicho anteriormente los bloques 7, 8, 15 y 17

mantienen los nodos-i (0, 1), (2, 3), (16, 17) y (20, 21).

Contrastando esta informacion con los bloques 57 a 60, 62 a 64 y 88, puede decirse que:

El bloque 57 mantiene el directorio raız, puesto que utiliza el nodo-i 1 y sus entradas . y .. apuntan a dicho

nodo-i. Tiene unicamente dos subdirectorios: bin (nodo-i 2) y users (nodo-i 3).

Consultando el nodo-i 2, vemos que el directorio /bin esta guardado en la zona 58 y que solo tiene esa

zona. Mantiene dos entradas: cc (nodo-i 4) y mined (nodo-i 5), pero no podemos decir nada mas sobre ellas

porque no sabemos nada de sus nodos-i.

17



Consultando el nodo-i 3 vemos que el directorio /users esta guardado en las zonas 59, 60, 62 y 63 (en este

orden), ya que el numero 61 se utiliza como puntero indirecto a zona.

Por tanto, este directorio tiene 16 entradas que corresponden a ., .., y 14 archivos cuyo nombre va de dso00

a dso13.

El bloque 15 nos proporciona los nodos-i 16 y 17, correspondientes a los directorios /users/dso10 y

/users/dso11 respectivamente. Ambos ocupan una zona unicamente. En ambos casos encontramos un

unico archivo msh.c dentro de cada directorio.

El bloque 17 mantiene los nodos-i de estos dos archivos. Deberemos usarlo para tener una idea del tamano de

ambos archivos.

Por lo dicho hasta ahora, la estructura de directorios debe ser la siguiente (se adjunta el numero de nodo-i corres-

pondiente a cada archivo):

/

1

... ...

bin

2

users

3

cc

4

mined

5

dso00

6

dso10

16

dso11

17

dso13

19

msh.c

20

msh.c

21

2. Ejecucion de open( "/users/dso11/msh.c", O RDONLY ).Veamos que accesos deben realizarse:

Bloque Explicacion

57 Lectura del directorio raız. Encontramos entrada users.

8 Lectura del nodo-i 3. Encontramos numeros de zona donde leer

el directorio users.

59 Buscamos en las primeras dos entradas el archivo dso11.

No lo encontramos.

60 Buscamos en las siguientes cuatro entradas. Tampoco tenemos suerte.

61 Leemos la zona que mantiene los siguientes punteros directos.

62 Buscamos en las siguientes cuatro entradas. No lo encontramos.

63 Buscamos en las siguientes cuatro entradas. Encontramos entrada.

Sabemos que el numero de nodo-i es 17 y que estara en el bloque 15.15 Encontramos que la zona para el directorio dso11 es el 88.

88 Buscamos entrada msh.c en el directorio y la encontramos.

El nodo-i a cargar para realizar la apertura es el 21.

17 Leemos el nodo-i 21 en el bloque 17. Con esto terminamos.

3. Tama ˜ no en zonas de /users/dso10/msh.c.

18



Sabemos que cada zona de disco puede mantener 16 punteros a otras zonas.

Partiendo de la informacion del nodo-i 20, en el bloque 17, podemos saber:

Las zonas 65 y 66 son las dos primeras del archivo.

El numero 67 es un puntero indirecto. En el se mantienen los siguientes 16 numeros de zona. El numero 68 es un puntero doble indirecto. Su contenido nos da los numeros de tres zonas mas que contienen

ya punteros directos. Por tanto, sabemos que el archivo tendra 32 zonas mas (cuyos numeros estan guardados

en las zonas 85 y 86).

El numero 87 es un puntero indirecto. No sabemos nada de su contenido. Sin embargo, como mınimo tendra

un puntero directo valido y como maximo 16.

Acumulando lo dicho anteriormente tendremos:

Que el fichero utiliza las zonas 67, 68, 85, 86 y 87 como zonas con punteros a zona. Por tanto, 5 zonas se

necesitan para esto. Que el fichero utiliza 2 + 16 + 2*16 = 50 zonas de datos, referenciados por el nodo-i o por las zonas de

punteros 67, 85 y 86, mientras que la zona 87 aportara entre 1 y 16 zonas mas. O sea se emplean entre 51 y

66 zonas de datos.

Esto hace que el total oscile entre 56 y 71 zonas.

Cuestion 9

1. Tama ˜ no mınimo del puntero a zona.

En el disco tendremos 320 bloques, ya que su capacidad total es de 320 Kb y el tamano de bloque (y de zona) es de

1Kb.

Para mantener 320 bloques necesitamos al menos 9 bits, ya que 2 ~ = 256 (con 8 bits unicamente se pueden

referenciar 256 bloques diferentes) mientras que 2 = 512 (con 9 bits se podrıan referenciar 512 bloques).

2. Punteros por zona.

En una zona podremos mantener:

P

&

¨

¥

bq � � x

P

b

¥

bq � � &X �

P

`Y "T pB x

¨

�

9

F D% �

�

¨

�

9

FX � D

H

�

9

F & �

P

`Y "T p% xG $

3. Tipo de punteros en el nodo-i.

Si tenemos 16 bytes para punteros, podremos llegar a mantener en un mismo nodo-i:

P

&

¨

9T j

�

�

¨

9

D

�

�

¨@ 9

�X �n D

H

9

� & �

P

`Y "T p% xG $

Las alternativas presentadas se convierten ası en las siguientes:

(a) 14 punteros directos.

Permite un tamano maximo del archivo de 14 Kb, pero los numeros de bloque estan todos accesibles una vez

se carga el nodo-i en memoria.

El unico problema es que el tamano maximo del archivo es excesivamente pequeno.

(b) 13 punteros directos y uno indirecto simple.

Esta opcion es la mas adecuada, puesto que si el tamano del archivo no supera los 13 Kb, todos sus punteros se

mantienen en el nodo-i. En caso de que el archivo sea mayor basta con mantener un puntero indirecto simple

ya que esto admitirıa 910 punteros directos mas. Obviamente, como la capacidad del disco es de 320 bloques,

nunca se llegarıa a requerir mas bloques de punteros.

19



(c) 12 punteros directos y 2 indirectos simples.

No es conveniente, puesto que el segundo puntero indirecto nunca se usarıa y se obligarıa a usar un bloque

de punteros para los archivos con mas de 12 Kb, mientras con la opcion anterior esto no era necesario hasta

sobrepasar los 13 Kb.

(d) 12 punteros directos, 1 indirecto simple y 1 indirecto doble.

Ocurre lo mismo que en el caso anterior.

Cuestion 10


El disco tendra: o 5 Y 3 8

8

= 64 bloques.

Estos se descomponen del siguiente modo:

1 bloque de arranque.

1 superbloque.

1 bloque para el mapa de nodos-i.

Tendremos 31 nodos-i, por tanto necesitamos 31 bits para “mapearlos”. Ademas, en MINIX el nodo-i numero

cero, a pesar de no existir, ocupaba espacio en el mapa. Por tanto, habra 32 bits en el mapa. Con un bloque

tenemos suficiente. 1 bloque para mapa de zonas de datos.

Como maximo tendrıamos 64 bits (algunos no hacen falta puesto que estan ocupados por el bloque de arran-

que, el superbloque, los mapas, etc.). Con un bloque volvemos a tener bastante.

1 bloque para nodos-i.

Tendremos 31 nodos-i y cada uno de ellos necesita 16 bytes. Por tanto, se necesitan 496 bytes para almace-

narlos, con lo que se usara un bloque.

59 bloques para datos.

Del total de 64 bloques del disco, 5 ya estan ocupados. Por tanto, quedan 59 para datos.

2. Tama ˜ no maximo de archivo.

Necesitamos conocer cuantos bloques podremos referenciar mediante los 60 bits que mantiene un nodo-i parapunteros directos.

El tamano de un puntero a bloque sera:

64 bloques H 2 bloques H punteros de 6 bits

Tenemos 60 bits disponibles. Ası tendremos: 60 / 6 = 10 punteros directos.

Como cada bloque es de 512 bytes, el archivo podra llegar a 5 Kb.

3. Maximo numero de entradas en un directorio.

En principio este valor no esta limitado. Unicamente depende del numero de archivos que se puedan crear.

En nuestro caso, solo podremos crear 31 archivos. Si todos los archivos se encontraran en el directorio raız

tendrıamos:

Las entradas . y .. que se referirıan al propio archivo del directorio raız. 30 entradas mas que acogerıan al resto de archivos.

Esto supone un total de 32 entradas. Como cada entrada necesita 16 bytes, esto supondrıa 512 bytes; o lo que

es lo mismo, 1 bloque.

20





Cil. actual Cilindros pendientes Desplaz. (cil.)

50 23. 48, *, 70, 81, 95 50 - 48 = 2

48 23, *, 70, 81, 95 70 - 48 = 22

70 23, *, 81, 95 81 - 70 = 9

81 23, *, 95 95 - 81 = 14

95 23, * 95 - 23 = 72

TOTAL: 121

LOOK

Direc. servicio Cil. servidos Desplaz. (cil.)

Ascendente 70, 81 y 95 95 - 50 = 45

Descendente 48 y 23 95 - 23 = 72

TOTAL: 117

2. Algoritmo “optimo”

Ni el LOOK ni el SSTF dan el mejor resultado posible para las peticiones que nos plantea el problema. Si el sentido

inicial de servicio fuera descendente el LOOK proporcionarıa un resultado optimo.

Dado un conjunto estatico de peticiones, el recorrido optimo serıa el siguiente:

Conocido el conjunto de peticiones y el cilindro donde est a actualmente la cabeza, servirlas en el sentido hacia

aquel extremo que quede m ´ as cerca del cilindro actual. Una vez llegado al cilindro de la ´ ultima petici´ on en tal

sentido, invertir el sentido de servicio y pasar a servir las peticiones restantes.

En nuestro caso, las peticiones en los extremos (la de menor y mayor cilindro, respectivamente) son sobre los

cilindros 23 y 95. El cilindro actual es el 50. Por tanto, el “extremo” mas cercano es el cilindro 23, con lo que

primero serviremos en orden descendente y despues en ascendente. Ası,

Direc. servicio Cil. servidos Desplaz. (cil.)

Descendente 48 y 23 50 - 23 = 27

Ascendente 70, 81 y 95 95 - 23 = 72

TOTAL: 99

No obstante, este algoritmo no funcionarıa bien a medida que fueran llegando nuevas peticiones ya que deberıan

recalcularse los “extremos” con cada nueva peticion y raramente se atenderıan peticiones alejadas del cilindro

actual.

Cuestion 12

1. Estructura de directorios

22





CUESTIONES Y PROBLEMAS PROPUESTOS

Cuestion 1Decidir si las siguientes afirmaciones sobre el sistema de archivos UNIX son verdaderas o falsas:

La creacion de un enlace fısico mediante el mandato ln implica la utilizacion de un nuevo nodo-i.

La creacion de un enlace simbolico mediante el mandatoln -s

no requiere el uso de un nuevo nodo-i. El mandato mv nunca implica el uso de nodos-i libres ni la liberacion de nodos-i en uso.

Para que un nodo-i pueda liberarse, deben eliminarse todos los enlaces fısicos y simbolicos sobre ese nodo-i.

Dado un archivo /dir1/a, la ejecucion del mandato rm /dir1/a siempre implica la liberacion de su nodo-i.

Se supone que el usuario tiene suficientes derechos de acceso a dicho archivo.

Cuestion 2¿ Que problemas plantearıa en UNIX la posibilidad de crear enlaces f ısicos sobre archivos de tipo directorio ?

Cuestion 3Explicar como podrıan darse multiples nombres a un mismo archivo en sistemas de archivo Windows 95 / 98 (FAT16 /

FAT32).

Cuestion 4Decidir si las siguientes afirmaciones sobre algoritmos de planificacion de peticiones a disco son verdaderas o falsas:

Si un manejador de disco no suele tener mas de una o dos peticiones pendientes, en la practica se planifica con

estrategia FCFS.

Con una estrategia FCFS el tiempo de espera de una peticion en la cola del manejador es el mınimo posible.

La estrategia SSTF es injusta porque puede marginar las peticiones sobre los cilindros mas internos o externos del

disco.

En un sistema multiprogramado se podra tener mas de una peticion pendiente del mismo hilo de ejecucion.

En un sistema multiprogramado no se podra tener dos peticiones pendientes sobre el mismo cilindro.

Cuestion 5

Decidir si las siguientes afirmaciones sobre estructuras de directorios son verdaderas o falsas:

El sistema de archivos de MS-DOS es un ejemplo de estructura de directorios de dos niveles.

El sistema de archivos de UNIX es un ejemplo de estructura de directorios en grafo acıclico.

Una estructura de directorios en grafo general no permite que diferentes usuarios protejan sus archivos.

24





1. Dibujar la estructura de directorios.

2. Utilizando las entradas que se conocen de la FAT, decir que clusters pertenecen a cada archivo. ¿ Puede detectarse

alguna inconsistencia ?

3. Comentar que salida darıa el mandato DIR (sin argumentos) si nos encontramos en el directorio mantenido en el

cluster 2.

4. Si se supone que el directorio que se encuentra en el cluster 2 funciona como directorio raız, comentar como

quedarıa la FAT y los directorios tras haber realizado las siguientes acciones:

C:> DEL \DOS\CONFIG.SYS

C:> COPY \ARCHIVOS\A.DAT \A.BAK

suponiendo que la asignacion de clusters libres se intenta realizar con aquellos que tengan menor numero de cluster.

5. ¿ Que pasarıa si la entrada 35 de la FAT apuntara al bloque 35 e intentaramos ejecutar el mandato DELTREE ?

¿ Que pasa en general si una entrada de la FAT apunta a ella misma ?

6. Suponiendo que el disco estudiado tiene una capacidad de 40 Mb, guarda FAT original y una copia (punteros de

16 bits) y el directorio raız puede mantener 512 entradas, dar la estructura del disco y mencionar cuantos clusters o

sectores tendra cada parte.

7. Comentar cuanto espacio se desperdicia debido a fragmentacion interna en cada uno de los archivos que aparecen

en el enunciado (Sin tener en cuenta el apartado 4).

8. Suponiendo bloques (y zonas) de 4 Kb y un disco de igual capacidad, con punteros a zona de 16 bits, entradas

de directorio de 16 bytes, un maximo de 1024 archivos, nodos-i de 32 bytes con 7 punteros directos, un indirecto

simple y uno doble:

Indicar como se estructurarıa este mismo disco bajo MINIX.

Suponiendo que contiene unicamente estos mismos archivos y directorios, dar el contenido de los archivos de

tipo directorio suponiendo que:

– Los archivos se crearon por niveles (primero todos los que aparecen en el directorio raız y despues los

archivos que cuelgan de sus dos subdirectorios). Dentro de un mismo nivel se siguio orden alfabetico.

– Siempre se uso el nodo-i mas bajo disponible.

– El disco no contenıa ningun archivo previamente y no se han borrado ni creado mas archivos.

Comparar las cifras de fragmentacion interna en este sistema con las del anterior. ¿ En que archivos difiere ?

26

Documents

algoritmos planeacion bueno