Soluciones de práctica

Índice
IPC 2
Semáforos: Barrera BID 2
Semáforos: Parque de diversiones 3
Semáforos: Desarrolle el pseudocódigo de las primitivas de semáforos de eventos utilizando
primitivas de exclusión (up() y down()) 5
Semáforos: Mensajes con buzones 6
Semáforos: Rotonda 8
Semáforos: Pseudocódigo de las primitivas para semáforos binarios (mutexes) 9
Semáforos: Pseudocódigo de las primitivas para semáforos generales 10
Semáforos: Problema 1 de la Guía de Práctica 11
Semáforos: Problema 2 de la Guía de Práctica 12
Semáforos: Problema 3 de la Guía de Práctica 13
Semáforos: Problema 4 de la Guía de Práctica 14
Semáforos: Problema 5 de la Guía de Práctica 16
Semáforos: Problema 6 de la Guía de Práctica 18
Ejemplo de código PRODUCTOR – CONSUMIDOR con Semáforos 19
Ejemplo de código PRODUCTOR – CONSUMIDOR con Semáforos y buffer circular 20
Semáforos: Problema 7 de la Guía de Práctica 21
Semáforos: Problema de excursión 23
Semáforos: Problema de excursión (Resolución Faus) 26
Semáforos: Problema de ferry (Resolución Faus) 27

Administración de Memoria 28
Problema con tabla de descriptores de segmento 28
Problema con tabla de página 30
Problema con matriz 100x100 31
Problema de fallos de página con una cadena de referencias 32
Problema con matriz 512x512 33
Ejercicio N°1 de la Guía 33
Ejercicio N°2 de la Guía 34
Ejercicio N°3 de la Guía 35
Ejercicio N°5 de la Guía 35
Ejercicio N°6 de la Guía 36

Archivos 37
Ejercicio N°1 de la Guía 37
Ejercicio N°2 de la Guía 38
Ejercicio N°3 de la Guía 41
Ejercicio N°4 de la Guía 44
Ejercicio de final 45
IPC
Semáforos: Barrera BID

sem mutex = 1;
sem waiting = 0;
int count[N] = 0;

barrera(BID, N){
down(mutex[BID]);
count[BID]++; /* incrementa contador de proc */
if(count[BID] == N){ /* si llegó a N, despierta a todos */
for (int i=0; i<N; i++){
up(waiting[BID]);
}
count[BID] = 0; /* reinicia el contador */
up(mutex[BID]);
}
else{ /* sino, pone en espera a ese BID */
up(mutex[BID]);
down(waiting[BID]);
}
}
Semáforos: Parque de diversiones
En un parque de diversiones n niños desean divertirse en un tren con d lugares disponibles (d < n). Los niños
repetidamente esperan poder subirse al tren para divertirse en el paseo. Para subir y bajar ejecutan subir() y
bajar(), respectivamente. El tren posee las operaciones abordar(), darPaseo(), descargar(). Los niños no
pueden subir al tren hasta que este no ejecute abordar(). El tren no da el paseo hasta que no esté lleno (d
pasajeros en el tren). Los niños para bajarse del tren (bajar() deben esperar que el tren ejecute descargar()).
Realice el pseudocódigo de niños() y tren() empleando semáforos.

#define N 10
sem mutex = 1;
sem abordar = 0;
sem niños = 0;
sem subir = 0;
sem pasear = 0;
int cantidadNiños = 0;

niños(){
while(true){
subir();
divertirse();
bajar();
}
}

tren(){
while(true){
abordar();
darPaseo();
descargar();
}
}

abordar(){
up(subir); /* al ejecutarse, desbloquea subir */
}
subir(){
down(subir); /* pide subir para ejecutarse */
down(mutex);
cantidadNiños++; /* incrementa contador de niños */
if (cantidadNiños == N){ /* si llego a N, desbloquea pasear*/
up(pasear);
up(mutex);
up(subir); /* libera subir */
}
else{ /* si no llego a N, pone en espera niños */
up(mutex);
up(subir); /* libera subir */
down(niños);
}
}

darPaseo(){
down(pasear); /* pide pasear para ejecutarse */
pasear();
}

descargar(){
up(bajar); /* al ejecutarse, desbloquea bajar */
}

bajar(){
down(bajar); /* pide bajar para ejecutarse */
down(mutex);
for(int i=0; i<N; i++){ /* desbloquea todos los niños */
up(niños);
}
cantidadNiños = 0; /* resetea contador */
up(mutex);
up(bajar); /* libera bajar */
}
Semáforos: Desarrolle el pseudocódigo de las primitivas de semáforos de eventos
utilizando primitivas de exclusión (up() y down())
int count [N] = 0;
typedef int sem;
sem mutex = 1;
sem waiting[N] = 0;

waitSem(semID){
down(mutex);
count[semID]++;
up(mutex);
down(waiting[semID]);
}

postSem(semID){
down(mutex);
for (int i=0; i<count[semID]; i++){
up(waiting[semID]);
}
count[semID] = 0;
up(mutex);
}
Semáforos: Mensajes con buzones

typedef int sem;

sem mutex = 1;
sem lleno = 0;
sem vacio = N;

send(buzon, &msg){
down(&vacio);
down(&mutex);
copiarAMsgBox(buzon, &msg);
up(&mutex);
up(&lleno);
}

receive(buzon, &msg){
down(&lleno);
down(&mutex);
copiarDesdeMsgBox(buzon, &msg);
up(&mutex);
up(&vacio);
}
Semáforos: Rotonda

#define N 0; /* se puede definir de antemano por el sentido */

#define O 1;
#define S 2;
#define E 3;

typedef int sem;

sem rotonda = 8; /* capacidad de la rotonda */
sem entrada[4] = {1,1,1,1} /* capacidades de las 4 entradas */
sem salida[4] = {1,1,1,1} /* capacidades de las 4 salidas */

vehiculo(acceso_entrada, acceso_salida){
down(entrada[acceso_entrada]);
down(rotonda);
entrarARotonda();
up(entrada[acceso_entrada]);
down(salida[acceso_salida]);
salirDeRotonda();
up(rotonda);
up(salida[acceso_salida]);
}
Semáforos: Pseudocódigo de las primitivas para semáforos binarios (mutexes)

struct semaforoBinario {
int valor;
lista listaProcesos;
} semaforoBinario;

var semaforoBinario s;

void downBinario(){
deshabilitarInterrupciones();
if ([Link] == 1){
[Link] = [Link] - 1;
}
else {
situar procesoX en [Link];
sleep(procesoX);
}
habilitarInterrupciones();
}

void upBinario(){
deshabilitarInterrupciones();
if([Link] == 0){
[Link] = [Link] + 1;
}

if([Link] != null){
seleccionar un proceso de [Link]
wakeup(procesoSeleccionado);
eliminar procesoSeleccioando de [Link];
ubicar procesoSeleccionado en lista de procesos listos;
}
habilitarInterrupciones();
}
Semáforos: Pseudocódigo de las primitivas para semáforos generales

down(s){
deshabilitarInterrupciones;

[Link] = [Link] - 1;

si ([Link] < 0){

situar proceso en [Link];
sleep(proceso);
}

habilitarInterrupciones;

up(s){
deshabilitarInterrupciones;

[Link] = [Link] + 1;

si ([Link] <= 0){

si ([Link] != nulo){
seleccionar un proceso de [Link];
wakeup(proceso_seleccionado);
eliminar proceso_seleccionado de [Link];
ubicar proceso_seleccionado en lista de proc_listos;
}
}

habilitarInterrupciones;

}
Semáforos: Problema 1 de la Guía de Práctica

struct sem {
int valor;
mutex mtx;
mutex waiting;
} sem;

var sem s;

[Link] = 0;
[Link] = 1;
[Link] = 0;

down(s){
lock([Link]);
[Link] = [Link] - 1;
if([Link] < 0){
unlock([Link]);
lock([Link]);
}
else {
unlock([Link]);
}
}

up(s){
lock([Link]);
[Link] = [Link] + 1;
if([Link] <= 0){
unlock([Link]);
unlock([Link]);
}
}
Semáforos: Problema 2 de la Guía de Práctica

[Link] = 0;

wait(semaforo){
deshabilitarInterrupciones;
[Link] = [Link] - 1;
if([Link] < 0){
situar procesoX en [Link];
sleep(procesoX);
}
habilitarInterrupciones;
}

up(semaforo){
deshabilitarInterrupciones;
[Link] = [Link] + 1;
if([Link] <= 0){
if([Link] != null){
while([Link] != null){
seleccionar proceso de [Link];
wakeup(proceso_seleccionado);
eliminar proceso_seleccionado de [Link];
ubicar proceso_seleccionado en lista de procesos listos;
}
}
}
habilitarInterrupciones;
}
Semáforos: Problema 3 de la Guía de Práctica

typedef int sem;

sem X = 1;
sem Y = 1;
sem puente = 2;

tren(origen, destino){
down(puente);
down(origen);
cruzar(origen);
up(origen);

pasar_puente();

down(destino);
cruzar(destino);
up(destino);
up(puente);
}
Semáforos: Problema 4 de la Guía de Práctica

#define RUTA1 +1;

#define RUTA2 -1;

typedef int sem;

sem mutex = 1;
sem waiting[RUTA1] = 0;
sem waiting[RUTA2] = 0;

int autosInteresados[RUTA1] = 0;
int autosInteresados[RUTA2] = 0;
int puente = 0;

auto(sentido){
llegar(sentido);
cruzar(sentido);
salir(sentido);
}

llegar(sentido){
while(TRUE){
down(mutex);
if(puente == 0){
puente += sentido;
up(mutex);
break;
}
else if( signo(puente) != signo(sentido)){
autosInteresados[sentido]++;
up(mutex);
 down(waiting[sentido]);
}
else {
puente += sentido;
up(mutex);
break;
}
}
}

salir(sentido){
while(TRUE){
down(mutex);
puente -= sentido;
if(puente == 0){
while(autosInteresados[-sentido] > 0){
up(waiting[-sentido]);
autosInteresados[-sentido]--;
}
}
up(mutex);
}
Semáforos: Problema 5 de la Guía de Práctica

typedef int sem;

sem finP1, finP2, finP3;

inicializa(finP1, 0);
inicializa(finP2, 1);
inicializa(finP3, 0);

cobegin
P1;P2;P3;
coend;

P1 {
loop
down(finP2);
accionesP1();
up(finP1);
end
}

P2 {
loop
down(finP3);
accionesP2();
up(finP2);
end
}

P3 {
loop
down(finP1);
accionesP3();
up(finP3);
end
}
Se puede modificar la forma de inicializar:

inicializa(finP1, 1);
inicializa(finP2, 0);
inicializa(finP3, 0);

inicializa(finP1, 0);
inicializa(finP2, 0);
inicializa(finP3, 1);

P1 {
loop
down(finP3);
accionesP1();
up(finP1);
end
}

P2 {
loop
down(finP1);
accionesP2();
up(finP2);
end
}

P3 {
loop
down(finP2);
accionesP3();
up(finP3);
end
}
Semáforos: Problema 6 de la Guía de Práctica

typedef int sem;

sem autobomba = 3;
sem tobogan = 1;

niños(){
loop
down(tobogan);
subir_tobogan();
up(tobogan);
down(autobomba);
subir_autobomba();
up(autobomba);
end
}
Ejemplo de código PRODUCTOR – CONSUMIDOR con Semáforos

#define N 100
typedef int semaforo;
semaforo mutex = 1;
semaforo lleno = 0;
semaforo vacio = N;

void productor(void){
int item;
while(TRUE){
producir_item(&item);
down(&vacio);
down(&mutex);
entrar_item(item);
up(&mutex);
up(&lleno);
}
}

void consumidor(void){
int item;
while(TRUE){
down(&lleno);
down(&mutex);
retirar_item(item);
up(&mutex);
up(&vacio);
consumir_item(item);
}
}
Ejemplo de código PRODUCTOR – CONSUMIDOR con Semáforos y buffer circular

#define MAX 100

typedef int semaforo;
semaforo mutex = 1;
semaforo lleno = 0;
semaforo vacio = MAX;
variableCompartida item buffer[MAX];
variableCompartida int in, out, count;

void productor(void){
item elem;
while(TRUE){
producir_item(&elem);
down(&vacio);
down(&mutex);
buffer[in] = elem;
in = in + 1 mod MAX
count = count + 1;
up(&mutex);
up(&lleno);
}
}

void consumidor(void){
item elem;
while(TRUE){
down(&lleno);
down(&mutex);
elem = buffer[out];
out = out + 1 mod MAX;
count = count - 1;
up(&mutex);
up(&vacio);
consumir_item(elem);
}
}
Semáforos: Problema 7 de la Guía de Práctica

#define X 4;

typedef int sem;

sem mutex = 1;
sem totalPedidos = 0;
sem pedidos = X;

void despachante(void){
int cafe;

while(TRUE){
servir_cafe(cafe);
down(&pedidos);
down(&mutex);
despachar_cafe(cafe);
up(&mutex);
up(&totalPedidos);
}
}

void mozo(void){
int cafe;

while(TRUE){
down(&totalPedidos);
down(&mutex);
retira_cafe(cafe);
up(&mutex);
up(&pedidos);
sirve_cafe(cafe);
}
}
void despachante(void){
int cafe;
message m;

while(TRUE){
servir_cafe(&cafe);
receive(mozo, &m);
crearMensaje(&m, cafe);
send(mozo, &m);
}
}

void mozo(void){
int cafe, i;
message m;

for(i=0, i<X, i++){

send(despachante, m);
}

while(TRUE){
receive(despachante, &m);
retira_cafe(&m, cafe);
send(despachante, &m);
sirve_cafe(cafe);
}
}
Semáforos: Problema de excursión
Para una excursión se contrataron varias combis con capacidad de pasaje para 500 Kgs. Todo viaje debe salir
con la carga exacta. Las mujeres pesan 50 kilos y los varones 75 kilos. Desarrollar el pseudocódigo de
varones() y mujeres() para salir de viaje. Nota: si lo piensa resolver con transferencia de mensajes puede
utilizar un Administrador, si lo piensa resolver con semáforos piense cómo funciona una barrera.

#define capacidadKg 500;

typedef int sem;

sem esperarProxCombie = 0;
sem esperarASalirDeViaje = 0;
sem esperarCargaMaxima = 0;
sem mutex = 1;
int capacidadDisponible = capacidadKg;
int combies = 5;
int enEsperaCombi = 0;
int enEsperaViaje = 0;

varones(){
subirCombieVaron();
salirDeViaje();
}

mujeres(){
subirCombieMujer();
salirDeViaje();
}

chofer(){
esperarCargaMaxima();
salirDeViaje();
}

subirCombieVaron(){
while(true){
down(mutex);
if(capacidadDisponible < 75){
 enEsperaCombi++;
up(mutex);
down(esperarProxCombi);
}
else{
capacidadDisponible = capacidadDisponible - 75;
enEsperaViaje++;
up(mutex);
up(esperarCargaMaxima);
down(esperarAsalirDeViaje);
break;
}
}

subirCombieMujer(){
while(true){
down(mutex);
if(capacidadDisponible < 50){
enEsperaCombi++;
up(mutex);
down(esperarProxCombi);
}
else{
capacidadDisponible = capacidadDisponible - 50;
enEsperaViaje++;
up(mutex);
up(esperarCargaMaxima);
down(esperarAsalirDeViaje);
break;
}
}

esperarCargaMaxima(){
while(true){
down(mutex);
if(capacidadDisponible == 0){
 while(enEsperaViaje != 0){
enEsperaViaje--;
up(esperarAsalirDeViaje);
}

if(combies > 1){

capacidadDisponible = capacidadKg;
combies--;
while(enEsperaCombie != 0){
enEsperaCombie--;
up(esperarProximaCombie);
}
}
up(mutex);
break;
}
else
down(esperarCargaMaxima);
}
}
Semáforos: Problema de excursión (Resolución Faus)
Para una excursión se contrataron varias combis con capacidad de pasaje para 500 Kgs. Todo viaje
debe salir con la carga exacta. Las mujeres pesan 50 kilos y los varones 75 kilos. Desarrollar el
pseudocódigo de varones() y mujeres() para salir de viaje. Nota: si lo piensa resolver con
transferencia de mensajes puede utilizar un Administrador, si lo piensa resolver con semáforos
piense cómo funciona una barrera.

#define capacidad 500

typedef int sem;

sem mutex = 1;
sem viajar = 0;
sem espera_mujeres = 0;
sem espera_varones = 0;

int capacidadActual = 0;

combi(){
while(TRUE){
varones();
mujeres();
down(viajar);
acciones_viajar();
up(viajar);
}
}

varones(){
down(mutex);
capacidadActual += 75;
if(capacidadActual == capacidad){
up(viajar);
up(mutex);
}
else {
up(mutex);
down(espera_varones);
}
}

mujeres(){
down(mutex);
capacidadActual += 50;
if(capacidadActual == capacidad){
up(viajar);
up(mutex);
}
else {
up(mutex);
down(espera_mujeres);
}
}
Semáforos: Problema de ferry (Resolución Faus)
Para cruzar un río solo existe un ferry con capacidad para transportar N automóviles. El ferry
cruzará el río cuando sea la hora de hacerlo o ni bien esté colmada de autos.
Desarrollar el pseudocódigo con semáforos los autos() y para el ferry() disponiendo además de un
3er tipo de proceso del administrador del ferry que establece el horario reglamentario para partir.

#define N 10
typedef int sem;
sem mutex = 1;
sem esperaAutos = 0;
sem cruzar = 0;

int cantidadAutos = 0;
int autosBloqueados = 0;

autos(){
down(mutex);
cantidadAutos++;
if(cantidadAutos == N){
up(cruzar);
up(mutex);
}
else{
autosBloqueados++;
up(mutex);
down(esperaAutos);
}
}

ferry(){
while(TRUE){
administradorFerry();
autos();
cruzar();
}
}

cruzar(){
down(cruzar);
down(mutex);
for (int i=0; i hasta autosBloqueados; i++){
up(esperaAutos);
}
cantidadAutos=0;
autosBloqueados=0;
up(mutex);
up(cruzar);
}
Administración de Memoria
Problema con tabla de descriptores de segmento

SEG BASE LÍMITE BASE+LÍMITE TIPO PERM

0 136 16 152 COD --X

1 128 12 140 STK RW-

2 32 16 48 DAT R-X

3 ? ? ? ?

4 240 7 247 DAT RW-

5 224 24 248 DAT R--

6 ? ? ? ?

7 4 27 31 STK RW-

a) Se solapan los segmentos 0 y 1 y 4 y 5.

b)

Acceso 1)
Nro. de segmento: 111 = 7
Dirección real: BASE + DESPL = 4 + 16 = 20 = 00010100
Fallo de protección de protección de segmento:
¿16 es mayor a 32? No, no hay fallo de segmento.
¿Tiene permiso de ejecución? Si, no hay fallo de protección de acceso.

Acceso 2)
Nro. de segmento: 010 = 2
Dirección real: BASE + DESPL = 32 + 17 = 49 = 00110001
Fallo de protección de protección de segmento:
¿17 es mayor a 16? Si, hay fallo de segmento.
¿Tiene permiso de lectura? Si, no hay fallo de protección de acceso.

Acceso 3)
Nro. de segmento: 001 = 1
Dirección real: BASE + DESPL = 128 + 4 = 132 = 10000100
Fallo de protección de protección de segmento:
¿4 es mayor a 12? No, no hay fallo de segmento.
¿Tiene permiso de escritura? Si, no hay fallo de protección de acceso.

Acceso 4)
Nro. de segmento: 000 = 0
Dirección real: BASE + DESPL = 136 + 1 = 137 = 10001001
Fallo de protección de protección de segmento:
¿1 es mayor a 16? No, no hay fallo de segmento.
¿Tiene permiso de ejecución? Si, no hay fallo de protección de acceso.

Acceso 5)
Nro. de segmento: 101 = 5
Dirección real: BASE + DESPL = 224 + 24 = 248 = 11111000
Fallo de protección de protección de segmento:
¿24 es mayor a 24? No, no hay fallo de segmento.
¿Tiene permiso de escritura? No, hay fallo de protección de acceso.

Acceso 6)
Nro. de segmento: 011 = 3
Dirección real: No se puede determinar.
Fallo de protección de protección de segmento:
¿16 es mayor a 32? No se puede determinar.
¿Tiene permiso de ejecución? No se puede determinar.
Problema con tabla de página
Problema con matriz 100x100

tamañoElemento = 2 bytes
tamañoPagina = 256 bytes
tamañoTotalArreglo = 100 * 100 * 2 bytes = 20000 bytes
cantidadPaginasAlojamiento = 20000 / 256 = 78.125
cantidadElementosPagina = 256 / 2 = 128 elementos

a) Con el fragmento indicado en dicho inciso, se produce un fallo cada 128 elementos,
por lo que dará un total de:

cantidadFallosFila = tamañoArreglo / cantidadElementosPagina .

= 100*100/128 = 10000/128 = 78.125 → 79 fallos

b) Para el fragmento por columnas, se produce un fallo por cada actualización, es decir,
que la cantidad de fallos será:
cantidadFallosColumna = i * j

Pero, como la cantidad de páginas alojadas no es un número “redondo” esto quiere

decir que no todos los elementos serán referenciados aunque se recorra toda la
matriz, luego:

elementosReferenciados = 128 * 0,125 = 16 elementos

cantidadFallosColumna = 79 * 100 - (100 - 16) = 7816 fallos

Problema de fallos de página con una cadena de referencias
Problema con matriz 512x512

Ejercicio N°1 de la Guía

a) NRU: Página 1 (Por primer clase no vacia R,M)

b) FIFO: Página 3 (Por tiempo de carga)
c) LRU: Página 1 (Por último acceso)
d) Segunda oportunidad: Página 1. Se le da segunda oportunidad a Página 3.
Ejercicio N°2 de la Guía

Paginación

1 2 7 8 1 7 6 3 8 5 7 3 7 2 1 3 4 2 5 7 2 3 4 5 7 7 8 7 2 1
1 2 7 8 1 7 6 3 8 5 7 3 7 2 1 3 4 2 5 7 2 3 4 5 7 7 8 7 2 1
1 2 7 8 1 7 6 3 8 5 7 3 7 2 1 3 4 2 5 7 2 3 4 5 5 7 8 7 2
1 2 7 8 1 7 6 3 8 5 5 3 7 2 1 3 4 2 5 7 2 3 4 4 5 5 8 7
1 2 2 8 1 7 6 3 8 8 5 3 7 2 1 3 4 4 5 7 2 3 3 4 4 5 8
2 8 1 7 6 6 6 8 5 5 7 7 1 3 3 4 5 7 2 2 3 3 4 5
2 2 1 1 1 1 6 8 8 5 5 7 1 1 1 1 1 1 1 2 2 3 4
2 2 2 2 1 6 6 8 8 8 8 8 8 8 8 8 8 1 1 1 3
6 6 6 6 6 6 6 6 6 6 6 6 6 6
F FF F - - F F F F F - - F F - F - F F - F F F F - F - F F
∞ ∞∞∞ 4 3 ∞∞ 5 ∞ 5 4 2 7 7 4 ∞ 4 6 6 3 5 5 5 5 1 7 2 6 7

21 fallos de página

Aplicando la fórmula de la distancia de la cadena:

C_∞ = 8
C_1 = 1
C_2 = 2
C_3 = 2
C_4 = 4
C_5 = 6
C_6 = 3
C_7 = 4

Para 4 marcos:
m=4, k=5, n=9
F_4 = C_5 + C_6 + C_7 + C_8 = 6 + 3 + 4 + 8 = 21

Para 5 marcos:
m=5, k=6, n=9
F_5 = C_6 + C_7 + C_8 = 3 + 4 + 8 = 15
Ejercicio N°3 de la Guía

C_1: 7
C_2: 2
C_3: 5
C_4: 2
C_5: 1
C_6: 2
C_7: 5
C_8: 3
C_9: 1

Para 4 marcos:
m=4, k=5, n=9
F_4 = C_5 + C_6 + C_7 + C_8 + C_9 = 1 + 2 + 5 + 3 + 1 = 12 fallos

Para 5 marcos:
m=5, k=6, n=9
F_5 = C_6 + C_7+ C_8 + C_9 = 2 + 5 + 3 + 1 = 11 fallos

Para 6 marcos:
m=6, k=7, n=9
F_6 = C_7+ C_8 + C_9 = 5 + 3 + 1 = 9 fallos

Ejercicio N°5 de la Guía

Ejercicio N°6 de la Guía

tamañoElemento = 2 bytes
tamañoPagina = 256 bytes
tamañoTotalArreglo = 128 * 128 * 2 bytes = 32768 bytes
cantidadPaginasAlojamiento = 32768 / 256 bytes = 128 páginas
cantidadElementosPagina = 256 / 2 = 128 elementos

a) Por filas
Dado que el arreglo está almacenado por filas, la cantidad de fallos será:
cantidadFallos = 32768 bytes / 256 bytes = 128 fallos
Es decir, ocurre 1 fallo por cada página

b) Por columnas
En este caso, si se recorre por columnas y sabemos que está almacenado por
filas, ocurrirá 1 fallo por cada actualización.
cantidadFallos = 128 * 128 = 16384 fallos
Archivos

Ejercicio N°1 de la Guía

Datos
tamañoBloque = 4 KB
direccionesADisco = 16 bits → tamañoDireccion = 16/8 = 2 bytes

TMA = tamañoBloque * nrosPunteros

nrosPunteros = min {punterosDireccionamiento, punterosEstructuraInodo}

punterosPorBloque = tamañoBloque / tamañoDireccion = 4096 bytes / 2 bytes = 2048

punterosDireccionamiento = 2^16 = 65536

punterosEstructuraInodo = 7 + 2 * punterosPorBloque + punterosPorBloque^2 = 7 + 2 * 2048+ 2048^2 =

4198407

nrosPunteros = min {2^16, 4198407} = min {65536, 4198407} = 65536

TMA = 4KB * 65536 = 262144 KB = 256 MB

Ejercicio N°2 de la Guía

tamañoDisco = 40 GB
tamañoBloque = 4 KB
direccionesADisco = 32 bits → 28 utilizables
tamañoEntrada = direccionesADisco / 8 = 32 / 8 = 4 bytes

a) entradasFAT = min {cantidadBloquesDisco, cantidadMaxDireccionable}

cantidadBloquesDisco = tamañoDisco / tamañoBloque = 41934040 KB / 4 KB = 10485760 bloques
cantidadMaxDireccionable = 2^nFAT = 2^28 = 268435456 bloques

entradasFAT = min {10485760 , 268435456 } = 10485760 entradas

tamañoFAT = entradasFAT * tamañoEntrada = 10485760 * 4 bytes = 41943040 bytes = 40 MB

b) desperdicioEsperadoDisco = cantidadArchivos * ½ * tamañoBloque = 12522 * ½ * 4 KB = 25044 KB

c) desperdicioEsperadoArchivo = espacioAsignadoArchivo - espacioRealArchivo

espacioAsignadoArchivo = bloquesArchivo * tamañoBloque

espacioRealArchivo = 12357222 bytes

entradasArchivo = tamañoArchivo / tamañoBloque = 12357222 / 4096 bytes = 3016,899902

= 3017 entradas → 3017 bloques (Por cada bloque hay una entrada en la FAT)

espacioAsignadoArchivo = 3017 * 4 KB = 12068 KB = 12357632 bytes

desperdicioEsperadoArchivo = 12357632 - 12357222 = 410 bytes

accesosFAT = entradasFAT - 1 = 3017 - 1 = 3016

d) Datos

nFAT = 16, 32
tamañoParticion = 16 MB, 256 MB
cantidadMaximaEntradas = 2^nFAT

Buscando X2
tamañoParticion = 2^nFAT * tamañoBloque
256 MB = 2^16 * X2
256 MB / 2^16 = X2
256 * 1024 * 1024 / 65536 = X2
4096 bytes = X2
4 KB = X2

Buscando X1
tamañoParticion = 2^nFAT * tamañoBloque
16 MB = 2^X1 * 4 KB
16384 KB / 4 KB = 2^X1
4096 = 2^X1
log_2(4096) = X1
12 = X1

Buscando X3
tamañoParticion = 2^nFAT * tamañoBloque
X3= 2^28 * 4KB
X3 = 1073741824 KB = 1048576 MB = 1024 GB = 1 TB
e) FAT-12
cantidadMaximaEntradas = 2^12 = 4096
tamañoFAT = 2^12 * 1.5 bytes = 6144 bytes = 6 KB

FAT-16
cantidadMaximaEntradas = 2^16 = 65536
tamañoFAT = 2^16 * 2 bytes = 131072 bytes = 128 KB

FAT-32
cantidadMaximaEntradas = 2^28 = 268435456
tamañoFAT = 2^28 * 4 bytes = 1073741824 bytes = 1048576 KB = 1024 MB = 1 GB
Ejercicio N°3 de la Guía

Archivo A
Estado: CORRECTO
Consecuencia: -
Corrección: -

Archivo B
Estado: segunInode > segunEntradas
Consecuencia: El estado no es grave, pero se está desperdiciando espacio en disco si el archivo no se
encuentra en ningún directorio.
Corrección: Para corregirlo, el valor en “Según el Inode” será 1.

Archivo C
Estado: segunEntradas > segunInode
Consecuencia: La situación es grave ya que 3 entradas de directorio están enlazadas al archivo pero el inodo
solo indica 2. Cuando se borren 2 entradas, el inodo va a decir 0 y será marcado como no usado, liberando
todos sus bloques. Por lo que una de las entradas de directorio apuntará a un nodo-i que no se usa y
probablemente sus bloques se asignen a otras entradas.
Corrección: Para corregirlo, el valor en “Según el Inode” será 3.

Archivo D
Estado: segunInode > segunEntradas
Consecuencia: La situación no es grave pero se está desperdiciando espacio en disco si el archivo no se
encuentra en ningún directorio.
Corrección: Para corregirlo, el valor en “Según el Inode” será 0.

Archivo E
Estado: segunEntradas > segunInode
Consecuencia: Idem situación archivo C. La entrada al directorio está enlazada a un archivo pero el nodo-i no
tiene ningún enlace.
Corrección: Para corregirlo, el valor en “Según el Inode” será 1.
100
Estado: entradasDirectorios == 0 && bitmapInodesLibres == 0 → Inode faltante
Consecuencia: Como no hay ninguna entrada de directorio, reduce la capacidad de disco ya que ese inode no
está marcado como libre.
Corrección: El valor en “Bitmap inodes libres” será 1.

200
Estado: entradasDirectorios == 1 && bitmapInodesLibres == 1 → Presente en ambas listas
Consecuencia: La entrada de directorio está apuntando a un inodo marcado como libre. Podría generar que
dicho inodo sea reasignado a otra entrada y esto sería erróneo.
Corrección: El valor en “Bitmap inodes libres” será 0.

300
Estado: entradasDirectorios == 2 && bitmapInodesLibres == 0 → Correcto. Esto se debe a un hard link, donde
dos entradas referencian al mismo inode.
Consecuencia: -
Corrección: -

400
Estado: entradasDirectorios == 1 && bitmapInodesLibres == 0 → Correcto. Hay una entrada referenciando al
inodo, por lo que se debe marcar como libre.
Consecuencia: -
Corrección: -

500
Estado: entradasDirectorios == 0 && bitmapInodesLibres == 1 → Correcto. Como no hay ninguna entrada
referenciando al inodo, el mismo está marcado como libre.
Consecuencia: -
Corrección: -
1000
Estado: segunInodes == 0 && bitmapBloquesLibres == 0 → Bloque faltante
Consecuencia: No es perjudicial pero desperdicia espacio y reduce la capacidad del disco
Corrección: Agregarlo a la lista de bloques libres. El valor de “Bitmap bloques libres” será 1.

2000
Estado: segunInodes == 1 && bitmapBloquesLibres == 1 → Presente en ambas listas
Consecuencia: No se puede asegurar si está ocupado o si está libre.
Corrección: Eliminarlo de la lista de bloques libres. El valor de “Bitmap bloques libres” será 0.

3000
Estado: segunInodes == 2 && bitmapBloquesLibres == 0 → Bloque presente en dos archivos
Consecuencia: Si se borra uno de los dos archivos, el bloque se marcará como libre y eso no es correcto. Se
debe referenciar uno de los dos archivos en otro bloque.
Corrección: Suponiendo que el bloque 6000 está libre, se crea una columna para dicho bloque con “Según los
Inodes” en 1 y “Bitmap bloques libres” en 0. En este bloque, se debe corregir “Según los Inodes” y su valor
será 1.

4000
Estado: segunInodes == 1 && bitmapBloquesLibres == 0 → Correcto
Consecuencia: -
Corrección: -

5000
Estado: segunInodes == 0 && bitmapBloquesLibres == 1 → Correcto
Consecuencia: -
Corrección: -
Ejercicio N°4 de la Guía

Datos
tamañoDisco = 64 GB
tamañoBloque = 4 KB
tamañoMapaDeBits = 4 KB
direccionamiento = 32 bits
tamañoInodo = 128 bytes
estructuraInodo = 10 + 2*cantidadBloques + cantidadBloques^2 + cantidadBloques^3

a) TMFS = min {tamañoDisco, tamañoSegunEstructuraFS}

tamañoSegunEstructuraFS = 2^direccionamiento * tamañoBloque = 2^32 * 4 KB

TMFS = min {64 GB, 2^32 * 4 KB} = 64 GB

b) cantidadArchivosDisco = min {tamañoMapaDeBits, cantidadDeBloques}

tamañoMapaDeBits = 4096 * 8 = 32768

cantidadDeBloques = 64 GB / 4 KB = 65536 MB / 4 KB = 67108864 KB / 4 KB = 16777216

cantidadArchivosDisco = min {32768 , 16777216} = 32768

c) espacioInodes = tamañoInodo * cantidadArchivosDisco = 128 bytes * 32768 = 4194304 bytes = 4096

KB = 4 MB
Ejercicio de final
Se desea montar un sistema de archivos del estilo de UNIX sobre un disco de 120GB, con sectores
de 512 bytes. Este sistema de archivos, tendrá las siguientes características:

1) El primer sector (sector 0) es el bloque de carga.

2) El segundo sector es el superbloque.
3) X sectores conteniendo el mapa de bits de inodes.
4) Y sectores contienen el mapa de bits de bloques.
5) Los siguientes 100 sectores serán inodes. El primer inode corresponde al directorio raíz.
6) El resto de los sectores serán bloques de datos o índices. El tamaño de bloque es igual al de
un sector.

Estructura de un inode
Cada inode ocupa 64 bytes, y las direcciones a bloques son de 32 bits.
Tipo de archivo (2 bytes)
Número de links (2 bytes)
Lista de punteros a los bloques de datos
Consta de 10 punteros directos, dos punteros simplemente indirectos, 1 puntero doblemente
indirecto y un puntero triplemente indirecto.
Estructura de una entrada de directorio
Nombre del archivo (14 letras)
Número de inode (2 bytes)

Responder:
a) ¿Cuántos sectores Y son necesarios para contener el mapa de bits de bloques?
b) ¿Cuántos sectores X son necesarios para contener el mapa de bits de inodes?
c) ¿Cuántos archivos puede tener como máximo este sistema de archivos? Justificar
d) ¿Cuál es el tamaño máximo del sistema de archivos? Justificar
e) ¿Cuál es el tamaño máximo de un archivo en este sistema de archivos? Justificar
f) Comprobando el sistema de archivos se ve que el inodo 37 tiene 2 referencias pero hay 3
entradas de directorio que hacen referencia a él. ¿Cual es la consecuencia que puede traer
este tipo de inconsistencias de archivo? ¿Cómo se resuelve?

tamañoDisco = 120GB
tamañoBloque = tamañoSector = 512 bytes
tamañoInode = 64 bytes
direccion = 32 bits
tamañoDireccion = 32/8 = 4 bytes
punterosPorBloque = 512 bytes / 4 bytes = 128 punteros
punterosEstructuraInodo = 10 + 128*2 + 128^2 + 128^3 = 2113802 punteros
cantidadInodesDisco = 100 inodes
mapaDeBitsDeBloques = 512 bytes * 8 bytes = 4096 bloques
tamañoSegunEstructuraFS = 2^32 * 512 bytes = 2048 GB
a) Sectores Y necesarios para contener el mapa de bits de bloques
cantidadBloquesDisco = tamañoDisco / tamañoBloque
= 120 GB / 512 bytes = 125829120 KB / 0.5 KB = 251658240 bloques
En el mapa de bits de bloques, cada bloque tiene 1 bit por bloque, luego:
sectoresY = cantidadBloquesDisco / mapaDeBitsDeBloques
251658240 bloques / 4096 bloques = 61440 sectores

b) Sectores X necesarios para contener el mapa de bits de inodes

cantidadInodesSector = tamañoSector / tamañoInode
= 512 bytes / 64 bytes = 8 inodes

Como sabemos que hay 100 sectores de inodes en el FS:

sectoresX = cantidadInodesFS / cantidadInodesSector
sectoresX = 8*100 / 8 = 100 sectores
Luego, como hay 100 sectores de inodes en el FS, solo se necesita 1 sector X para contener
el mapa de bits de inodes.

c) cantidadMaximaArchivos = cantidadInodesFS = 800 archivos

d) tamañoMaximoFS = min {tamañoDisco, tamañoSegunEstructuraFS}

tamañoMaximoFS = min {120 GB, 2048 GB} = 120 GB

e) tamañoMaximoArchivo = tamañoBloque * nrosPunteros

nrosPunteros = min {punterosDireccionamiento, punterosEstructuraInodo}
nrosPunteros = min {2^32, 2113802} = 2113802
tamañoMaximoArchivo = 512 bytes * 2113802 ≌ 1032, 13 MB

f) segunEntradas (3) mayor a segunInode (2). La situación es grave ya que 3 entradas están
enlazadas a un archivo pero el inodo dice 2 por lo que cuando se borren 2 entradas, la
cuenta del inodo será 0 y será marcado como no usado, liberando todos sus bloques y
probablemente sean asignados a otras entradas. Para corregir la situación, se debe poner
en 3 el valor del inode.