Ejercicios de parcial 2014 V.1.

UTN FRBA

Sistemas Operativos

Ejercicios de planificacin
1) Peter desarroll un Sistema Operativo, donde las operaciones de semforos duran 3 ms y cuya
atomicidad est lograda mediante la deshabilitacin de las interrupciones. Decidi ponerle un planificador
Round Robin, con Q = 5 ms.
Leandro, quien es amigo de Peter, al analizar el sistema desde Pittsburgh (donde reside actualmente) le
consulta si tiene sentido dicho diseo, dado que la mayor parte del tiempo se tendrn corriendo un
programa formado por tres procesos, como se muestra a continuacin:
Proceso A (llegada = 0)

Proceso B (llegada = 1)

Proceso C (llegada = 5)

wait(A);
wait(B);
calculos();
signal(A);
signal(B);

wait(A);
calculos();
wait(C);
signal(A);
signal(C);

wait(C);
wait(A);
calculos();
signal(C);
signal(A);

Peter decide entonces realizar el diagrama de GANTT, e indicar como y cuando finalizaron los
procesos.
Nota: los semforos se encuentran inicializados de la siguiente forma: A = 2, B = 0, C = 1, y la funcin
clculos() dura 3 ms

2) La oficina de la Junta Electoral est preparando el software necesario para dar los resultados de las
elecciones PASO, anunciando los candidatos electos lo antes posible, por lo que decide probar
diferentes algoritmos de planificacin para su sistema operativo. Los KLTs a utilizar estn definidos de la
siguiente forma:
1) Recuento: CPU(1) E/S (10) CPU(8) -> Realiza el recuento de votos y define los candidatos electos
2) Estadsticas: CPU(2) E/S(3) CPU(5) -> Realiza estadsticas generales
3) Votantes: CPU(5) E/S(2) CPU (2) -> Revisa los padrones y enva e-multas a quienes no votaron
Los algoritmos para ser evaluados son SJF (con desalojo) y RR (con Q=2). Todos los KLTs estn en la
cola de listos, ordenados como se muestra ms arriba, y deben finalizar para mostrar los resultados.
Cul debe ser elegido? Justifique realizando diagramas de Gantt.

3) El siguiente diagrama representa la ejecucin de 4 procesos planificados segn un algoritmo. Observe

detenidamente el grfico e indique.

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

a) Qu algoritmos se pueden estar utilizando si consideramos el Gantt hasta el instante 6 (antes de

elegir a D)?
b) Cul fue el algoritmo utilizado considerando toda la ejecucin de los procesos?
Justifique en ambos casos.

Nota: inicialmente los procesos llegan a una cola en el orden ABCD.

4) Un sistema utiliza un algoritmo Feedback de planificacin de procesos. El mismo cuenta de 3 colas,

preemptive entre ellas. Las reglas que sigue el algoritmo son las siguientes:

Cola mayor prioridad RR Q = 2.

Cola prioridad media RR Q = 3.

Cola menor prioridad FIFO.

Procesos nuevos van a la cola de mayor prioridad.

Un proceso, al ser desalojado por fin de quantum, es penalizado y llevado a la cola

inmediatamente inferior.

Luego de una e/s los procesos son promovidos a la cola de mayor prioridad (RR Q = 2).
Considerando que inicialmente en la cola de listos de mayor prioridad se encuentran : A-B-C y que en el
instante 13 llega el proceso D, encuentre los errores en la siguiente planificacin:

5) En un Sistema Operativo que utiliza el algoritmo HRRN se estn corriendo los siguientes ULTs, que
pertenecen al KLT Pregunta DOS (que corre un juego de preguntas sobre comandos de consola):
ULT Buscador de participantes: CPU 4, E/S 4, CPU 4 -> Tiempo de llegada 0
ULT Buscador de preguntas: CPU 3, E/S 5, CPU 2 -> Tiempo de llegada 1
ULT Contador de monedas: CPU 1, E/S 5, CPU 1 -> Tiempo de llegada 5

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

Se sabe que todas las funciones de E/S utilizadas son propias de la biblioteca de hilos, y que sta
planifica usando el algoritmo SJF sin desalojo.
a) Realice el diagrama de Gantt correspondiente a esta ejecucin.
b) El programador que realiz el juego decide utilizar la tcnica de Jacketing para todas las E/S
(convirtindolas en no-bloqueantes). Mejorar esto la situacin? Realice el nuevo diagrama de Gantt

6) Dada la siguiente traza de ejecucin:

CPU

I/O

CPU

Proceso A

10

Proceso B

Proceso C

a) Realice el diagrama de gant para los algoritmos SJF sin desalojo y SJF con desalojo.
b) Calcule para el proceso A el tiempo de ejecucin y el tiempo de espera en ambos algoritmos.
Notas:
- Todos los procesos se encuentran en Ready
- Cada vez que se produce un cambio de proceso, el SO consume 2 unidades de tiempo
- Si el SO interviene pero eso no se traduce en un cambio de proceso, el SO consume 1 unidad de
tiempo

7) Suponga que para un TP de la materia Tcnicas de Grficos por Computadora, usted grafica un
Gaucho en 3D que anda lento (lo cual es raro porque su pc tiene dos procesadores). Para agilizar el
proceso, al indagar descubre que este programa consta de un proceso, el cual tiene dos hilos de kernel
(A y B) y que cada uno tiene dos hilos de usuario. Al ser un sistema operativo UbUTNu, su planificador
es FIFO, y la biblioteca usa RR con Q=2.
Dada la siguiente traza de ejecucin:

UTL-A1
UTL-A2
UTL-B1
UTL-B2

Llegada
0
1
4
3

CPU
3
4
2
1

I/O
1
3

CPU
1
1

a) Realice un diagrama de GANTT para tener ms informacin sobre la lentitud del Gaucho, sabiendo
que toda peticin de E/S pasa por la biblioteca de ULTs.
b) Calcule los tiempos de respuesta y ejecucin, e indique cual debera merecer mayor importancia y
porqu.

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

8) Un da cualquiera, Peter decide comprarse un iPhone 5S. Sin embargo, al experimentar la lentitud del
sistema, decide sacarle iOS e instalarle Ubuntu Satanic. En una charla de ascensor, el vecino de su
edificio le consulta si considera que realiz una buena eleccin. Para saberlo, decide ejecutar un par de
procesos, registrar su ejecucin y luego imprimir el GANTT para enviarle al vecino.
Sabiendo que el planificador es RR con Q=3, que existe una sola CPU y un solo dispositivo de E/S,
grafique dicho diagrama de GANTT, sabiendo que la traza de los procesos PA y PB es la siguiente:
Llegada

CPU

I/O

CPU

PA - KLT1

12

PA - KLT2

13

PB - KLT3

PB - KLT4

Nota: Cada vez que interviene el SO para un cambio de hilo, se consume 1 ms si se mantiene en el
mismo proceso, y 2 ms en caso contrario.

9) Suponga la siguiente traza de ejecucin de los procesos A y B, con un sistema operativo que planifica
bajo RR con Q=4:
Llegada

CPU

I/O

CPU

PA - UTL1

PA - UTL2

10

PB - UTL3

PB - UTL4

Se pide:
a) Realice el diagrama de GANTT de la ejecucin de los mismos
b) Indicar en cuales instantes de tiempo se produjo un cambio de modo de ejecucin
c) Indicar en cuales instantes de tiempo el procesador recibe una interrupcin
Nota: La biblioteca de usuario planifica bajo el algoritmo FIFO. Todo pedido de E/S pasa por la biblioteca.

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

Ejercicios de sincronizacin
1) Peter necesita sincronizar los procesos que ocurren cuando se toman finales. Por cada mesa de
examen hay un jefe de mesa que se encarga de recibir las libretas, pasar las notas a ellas y luego
entregarlas.
La mesa cuenta con tres profesores que se ocupan de corregir los finales. La mesa de examen tiene que
llegar a los treinta alumnos. Dado el siguiente pseudo-cdigo:
Proceso jefe de mesa
(1 instancias)
entregar_examenes();
entregar_notas();

Proceso profesor
(3 instancias)
corregir_final();

Proceso alumno
(n instancias)
entregar_libreta();
hacer_final();
recibir_libreta();

Coloque adecuadamente en los tres procesos semforos para que el jefe de mesa no entregue el
examen a los alumnos hasta que los treinta no hayan entregado su libreta y adems, para que las libretas
se entreguen todas juntas, una vez que se corrigieron todos los finales.
Nota: indicar para cada semforo utilizado, su tipo y su valor inicial.

2) Suponga que lo contrata Peter Rial, para sincronizar su sistema de gestin de chismes. Al parecer
Peter Ventura lo program, pero como no sabe nada de sincronizacin, se le pide a usted que lo ayude (a
cambio de que luego salga en intrusos como el gran sincronizador). Dado el siguiente pseudo-cdigo:
Proceso Meditica (n instancias)

Proceso Rial (1 instancia)

registrar_escndalo();
enviar_a_rial();
difundir_video();
asistir_a_instrusos();

procesar_escndalo_nuevo();
invitar_al_programa();

Sincronice la ejecucin de ambos programas mediante el uso de semforos exclusivamente, para

garantizar que el proceso Rial solamente procesa escndalos cuando los mismos hayan sido enviados, y
que el personaje meditico solo difunde su video cuando Rial ya lo invit a su programa. Tenga en cuenta
que si bien Rial invita a todos los mediticos, solo dos de ellos puede asistir a la vez en un programa.
Nota: indicar para cada semforo utilizado, su tipo y su valor inicial.
3) La AFIP atienden a contribuyentes todos los das hbiles, pero adems realiza operativos anti-lavado
constantemente. Dicha actividad ha sido modelada utilizando cuatro procesos, dos que simbolizan el
actuar de la oficina, y dos que simbolizan a los contribuyentes y a los evasores (entre parntesis figuran

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

las instancias de cada uno).

AFIP-Atencion (1)
while (true) {
AtenderTramite();
}

AFIP-Operativos (1)
while (true) {
RealizarOperativo();
}

Contribuyente (N)
while (true) {
HacerTramite();
}

Evasor (N)
while (true) {
Lavar($1000);
}

La oficina de atencin est ociosa hasta que alguien se acerca a realizar un trmite. Por otro lado, los
contribuyentes deben esperar a que la oficina de atencin se desocupe, para ser atendidos. Si la AFIP
detecta una operacin de lavado, realiza un operativo. Por otro lado los evasores prefieren no lavar ms
de $100.000 de manera continua, para evitar sospechas. Por ltimo, dada la baja cantidad de personal
que trabaja aqu, las oficinas de atencin no reciben trmites durante los operativos, dejando que estos
se acumulen infinitamente.
Sincronice estos procesos utilizando slo semforos y sin que sufran deadlock.

4) Suponga que Peter program en Objective C para iPhone un cdigo para salir a competir con la
aplicacin del momento: Pregunta2. En esta parte del mismo, existen muchos hilos que validan preguntas
y las que son apropiadas las dejan listas para que un hilo servidor, del cual existen muchas instancias, la
enve a algun usuario vido de contestar alguna pregunta.
El pseudo-cdigo, que cada tanto falla por razones desconocidas, es el siguiente:
S1.valor = 1; S2.valor = 100; S3.valor = 0
Validador de Preguntas Nuevas (n instancias)

Servidor de preguntas (n instancias)

while (true){
wait(S1)
wait(S2)
pregunta = obtener_pregunta_validada()
depositar(cola, pregunta)
signal(S1)
signal(S3)
}

while (true){
wait(S1)
wait(S3)
pregunta2 = retirar(cola)
enviar(pregunta2, )
signal(S1)
signal(S2)
}

a) Indique paso a paso la secuencia de ejecucin de ambos hilos que generara un problema, y explique
qu problema es.
b) Implemente en pseudo-cdigo la funcin signal(), sabiendo que la estructura semforo tiene el
siguiente formato:

struct semforo {
int valor;
LISTA* bloqueados;
// Otros atributos
};

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

Nota: para el punto b) se disponen de las funciones syscall_bloquear(proceso) y

syscall_despertar(proceso), y se debe garantizar la atomicidad de la funcin a travs de alguna solucin
provista por el hardware (se pueden agregar campos a la estructura si lo considera necesario)
5) Peter, quien es una persona que suele tener mala suerte, se esguinz corriendo el colectivo. Por lo
tanto, necesita ir a la guardia del Hospital OSD, donde deber seguir el siguiente procedimiento:
En primer lugar, indicar la especialidad deseada en una mquina, dnde obtendr un ticket con un
nmero correspondiente al turno. Dicho valor es de 0-99, luego se reinicia.
El ticket generado por la mquina ingresa en forma virtual en una cola de tickets consultada por los
recepcionistas. Para evitar que haya mucha espera en la sala, el sistema permite que haya slo 60 tickets
pendientes.
Cuando un recepcionista obtiene un ticket atender a la persona segn el nmero que se indique en el
mismo. Segn lo que le explique el paciente, lo derivar con un especialista especfico.
Peter (u otro paciente) (N)

Recepcionista ( 5 )

Notas

turno= solicitarTicket()
sentarse();
explicarSituacin()
atenderseConEspecialista()

While(1) {
turno= obtenerTicket()
escucharPaciente()
asignarEspecialista()
}

Nota 1: El paciente se levanta de la silla

recin cuando el recepcionista lo llama.
Nota 2: Hay 20 sillas

6) Peter est a punto de rendir el ltimo final de su carrera. Sus amigos organizan los festejos en la
puerta de la facultad, y para ello compran un maple con 96 huevos. Dadas las dimensiones del maple, los
amigos tomarn los huevos de a uno a la vez. Peter recibir el homenaje, para luego lavarse y secarse
con la toalla que le ofrecer su madre. Por ltimo, se tomar una foto con todos sus amigos.
Peter

Amigo (4 instancias)

Madre de Peter

salir_de_la_facultad();
recibir_huevos();
lavarse();
secarse();
sacarse_foto();

esperar();
while(huevos > 0) {
tomar_huevo(maple);
huevos--;
arrojar_huevo();
}
sacarse_foto();

esperar();
emocionarse();
alcanzar_toalla();

Sincronice los siguientes procesos utilizando nicamente semforos, sin caer en deadlock o inanicin.
7) Peter decidi festejar su cumpleaos e invitar a muchos amigos, por lo que debe elaborar muchas
pizzas. Como peter quiere terminar lo antes posible, consigue ayuda para poder paralelizar el trabajo
mientras llegan los invitados. Sincronice (utilizando slo semforos) el trabajo de Peter y su equipo
(amigos, abuelos, primos) para que la fiesta sea un xito.

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

Para esto tenga en cuenta que: hay 3 bowls, 5 pizzeras y un horno. Los abuelos van colocando los bollos
en una nica bandeja que tiene una capacidad mxima de 10 bollos (ya que si no se comienzan a pegar).
Peter podr colocar pizzas en el mismo momento en el que los invitados agarren porciones (aunque se
pelee con Bernstein). Tenga en cuenta que Peter corta las pizzas en 4, pero que de cada una se come
una porcin. Nota: en el proceso de elaboracin de una pizza se la coloca dos veces en el horno, la
primera, para preparar la prepizza, la segunda para que se derrita el queso.
8) Peter est por hacer su primer salto en paracadas. Como no quiere dejar ningn detalle librado al
azar, decide simular su cada, incluyendo al fotgrafo que lo va a retratar y a su esposa. El salto se har a
5000 pies, saltando primero l y despus el fotgrafo. Antes de pasar los 3000 pies, se le sacar una foto
desde arriba, y luego de pasar los 3000 pies una desde abajo (para esto, el fotgrafo primero desafiar
las leyes de la gravedad, descendiendo ms rpido que l). Luego abrirn el paracadas y aterrizarn (no
importa en qu orden).
En tierra lo esperar su esposa, quien se preocupar cuando Peter pase los 3000 pies, y lo abrazar
luego de aterrizar.
Sincronice los siguientes procesos utilizando nicamente semforos, sin provocar deadlock o
starvation.
Peter

Fotgrafo

Esposa

while(1) {
tirarseA5000Pies();
pasarLos3000Pies();
abrirParacaidas();
aterrizar();
}

while(1) {
tirarseA5000Pies();
sacarFotoDesdeArriba();
desafiarLeyesDeGravedad();
sacarFotoDesdeAbajo();
abrirParacaidas();
aterrizar();
}

while(1) {
preocuparse();
abrazarParacaidista();
}

9) Los creadores de koopa decidieron que su implementacin fuese multi-thread. Peter, quin program
la libmemoria.so entre otras cosas, va a realizar la modificacin. La especificacin de koopa dice: Ahora
koopa realiza hasta tres operaciones de asignacin de particiones en paralelo y a la hora de liberar
particiones, hasta cinco operaciones.

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

a) Ayudemos a Peter a modificar su implementacin de memoria utilizando semforos donde fuese

necesario, indicando sus valores iniciales.
b) Implemente las primitivas de semforos con espera activa, en caso que presenten seccin crtica,
sincronice (con un color diferente) dichas primitivas utilizando alguna tcnica hardware de su eleccin.
Aclaracin: Solo utilizar semforos. No puede agregar o quitar cdigo.
Las funciones particion_libre(...) y particion_ocupada(...) en caso de hallar una particin, la marcan para
que no est disponible. Mientras que asignar_particion(...) y liberar_particion(...) actualiza el listado de
particiones.
t_list *particiones //Variable global con particiones de la memoria.
int almacenar_particion(...) {

int eliminar_particion() {

if(datos_invalidos( id, tamanio, contenido)) {

return -1 ;
}
particion_libre = particion_libre(particiones, tamanio);
if(particion_libre) {
asignar_particin(particiones, particion_libre, id,
tamanio, contenido);
return 1;
} else {
return 0;
}

particion = particion_ocupada(particiones, id);

if(particion) {
liberar_particion(particiones, particion);
return 1;
}
return 0;
}

10) Implemente las funciones wait() y signal(), utilizando la instruccin test_and_set para garantizar la
concurrencia.
Suponga que tiene los procesos A, B y C. Sincroncelos con semforos para que ejecuten siguiendo la
secuencia BACABACA (Utilice la menor cantidad de semforos posible)

11) Sincronice el siguiente cdigo, correspondiente a un proceso que genera procesos hijos, para evitar
inconsistencias, deadlocks e inanicin. Adems debe tener en cuenta lo siguiente:

El archivo donde se escriben los logs es nico.

No debe haber ms de 50 procesos en ejecucin

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

El padre debe escribir en el log antes que el hijo recin creado.

int main () {
while (true) {
pid = fork();
if (pid < 0) {
log(Error);
} else if (pid == 0) {
log(Y yo soy el hijo);
realizarTarea();
exit(0); // Finaliza el proceso hijo
} else { // Padre
log(pid + soy tu padre);
}
}
}

10

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

Ejercicios de deadlock

1) Dadas las matrices, defina: qu enfoque utilizar para tratar el Deadlock?

Qu procesos estn en deadlock y cmo lo solucionara? Tenga en cuenta que el proceso 3 debe
finalizar correctamente. Indique en un grafo de asignacin de recursos dnde podra existir deadlock si
slo grafica los procesos 2 y 4.

2) En un sistema cuyo estado se encuentra representado por las siguientes matrices se tienen como
recursos mximos R1= 7, R2=4, R3=2,R4=3. Resuelva:
a) Qu algoritmo de tratamiento de deadlocks se puede
utilizar con los datos presentes? Explique en qu se basa
dicho mecanismo.
b) Indique si se satisfacen inmediatamente cada uno de los
siguientes pedidos, utilizando el mecanismo indicado en b):

P1 2 R1 1 R3

P2 1 R1 2 R3

P3 1 R1

P4
1R1
1 R3
3) Dadas las siguientes matrices de asignacin y
necesidad de recursos, determine si el sistema se
encuentra actualmente en estado de interbloqueo
(deadlock). En caso de que hubiese interbloqueo,
determine qu proceso/s se podra/n escoger como
vctimas/s para solucionarlo. Si no hubiese deadlock,
muestre una secuencia de ejecucin en la cual todos
los procesos terminen correctamente. Justifique.

11

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

4) Dadas las siguientes matrices de un sistema operativo que utiliza como poltica evadir el Deadlock:

a) Halle la matriz de recursos disponibles requeridos para que pueda otorgarse 2 instancias del Recurso
3 al Proceso 2. La cantidad de recursos debe ser la menor posible.
b) Indique la secuencia de finalizacin de los procesos.

5) Un grupo de vedettes intenta promocionar su nueva obra de teatro yendo a diferentes programas.
Podemos diferenciarlas entre principal (hay una sola), vedettes secundarias (hay cinco) y mellizas griegas
(hay dos). Aprovechando sus conocimientos de Sistemas Operativos, deciden simular esta situacin
utilizando procesos, para poder asistir a los programas sin descuidar la obra de teatro. El pseudo-cdigo
es el siguiente:

Programa de Chimentos() {

Programa de Cable() {

Entrevistar(melliza, 1)

if(bajo_rating) {
Entrevistar(secundaria, 1)
}

Obra de Teatro() {

Entrevistar(secundaria, 3)
Entrevistar(melliza, 1)

if(aparece_sponsor) {
Entrevistar(principal, 1)
}

}
}

Bailar(secundaria, 2)
Monologo(principal, 1)

if(el_publico_no_se_rie) {
Bailar(melliza, 2)
}
}

Habitualmente el programa de chimentos tiene un rating muy alto. Por otro lado, el programa de cable no
suele tener ningn sponsor. Y un 90% de las veces, el pblico que va al teatro se re con el monlogo de
la vedette principal.
a) En este instante los procesos estn donde indica la flecha Podrn promocionarse sin descuidar la
obra de teatro? Justifique
b) Si la respuesta es afirmativa, indique en qu orden deberan finalizar los procesos para que esto
ocurra. Si es negativa, indique qu sucedera si se contrata una vedette secundaria ms.

6) Sobre un sistema operativo que emplea el algoritmo de deteccin de deadlock se ejecutar los
siguientes programas: Valores de las variables globales: sem_t A=5, B=7, C=3;

12

Ejercicios de parcial 2014 V.1.0

Proceso X | PID 2345

wait(A, 2);
injectarSQL();
wait(B, 1);
wait(B, 6);

T1
informarVulnerabilidad()
;
signal(B, 6);
wait(B, 1);

T2
siguienteVictima();
...

Sistemas Operativos

Proceso Z | PID 3001

wait(C,2);
wait(A,1);
sleep(200);
T1
signal(A,1);
kill(2398, SIGKILL);
wait(A,1);
T2
...

Proceso Y | PID 2352

wait(C,1);
wait(B,1);
enviarMail();
wait(A,1);
wait(B, 1);
T1
wait(A, 1);
spamearAlVecino();
signal(B,1);
wait(C,1);
T2
...

UTN FRBA

Proceso W | PID 2398

recibirCorreo();
wait(A,1);
wait(B,5);
wait(C,2);
T1
signal(C,1);
signal(B,1);
listarCorreo();
wait(B,1);
T2
exit();
...

Notas:
* wait(sem,n) Toma en forma atmica n instancias del semforo sem. Se bloquea si no estn
disponibles.
* signal(sem, n) Libera n instancias del semforo sem.
* Indica el instante donde el proceso se encuentra ejecutando. En caso de tratarse de un wait()
significa que la funcin solicito un recurso al SO y este aun no lo entreg.
Se ejecutan los programas y despus de un tiempo, el administrador de sistema activa el mdulo de
deteccin de deadlock. Indique el resultado que vera para los instantes T1 y T2, as como el estado de
cada proceso. En T2 se sabe que W finaliz.

7) En un sistema que utiliza el algoritmo del banquero como mtodo para evitar los deadlocks, indique
cules de los siguientes pedidos seran satisfechos inmediatamente, suponiendo que cada uno se
efectuar sobre el estado presentado inicialmente:
1) P1: una instancia de R1
2) P1: una instancia de R4
3) P3: 2 R2
4) P3: 2R1 y 3 R4

13

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

8) Un sistema que evade el deadlock se encuentra en el siguiente estado:

Halle el vector de recursos totales que tenga la menor cantidad posible de instancias de recursos y que
adems pueda aceptar la solicitud de una instancia de R1 por parte de P4.

14

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

Ejercicios de Memoria
1) Un sistema utiliza un esquema de paginacin bajo demanda, con una poltica de sustitucin global que
utiliza el algoritmo LRU. En el mismo se dedican nicamente 4 frames para alojar pginas de procesos de
usuario (frames: 1-2-3-4).
Dicho sistema posee en un momento dado nicamente dos procesos, A y B, que se encuentran
ejecutando. El proceso A necesita ejecutar una instruccin la cual referencia a sus pginas 0, 1 y 2. A su
vez, el proceso B necesita ejecutar otra instruccin para la cual necesita tener cargadas en memoria
fsica a las pginas 0, 1, 2, 3 y 4.
Luego de cargar ciertas pginas el estado de los procesos es el siguiente:
TP Proceso A

TP Proceso B

P
g

Fram
e

T ltima
referencia

Pg

Frame

T ltima
referencia

10

12

11

Por lo tanto, con el fin de poder ejecutar las instrucciones, los procesos referencian a las siguientes
pginas en el orden indicado: 1B 3B 2A 2B
a) Indique:
La cantidad de PFs (page faults) que se generan.
Las pginas que se leen de disco y las que se escriben de memoria a disco.
El estado de las tablas de pginas luego de la ltima referencia.
b) Podrn los procesos ejecutar cada uno su instruccin deseada? Podra responder la pregunta
anterior antes de resolver el punto 1? Podra ejecutar algn proceso su instruccin si se modifica el
orden de las referencias? Justifique en todos los casos.

2) Un sistema utiliza un esquema de paginacin bajo demanda con un tamao de frame de 2 KiB,
direcciones lgicas de 16 bits y una poltica de asignacin fija de 3 frames. En un momento se sabe que
la tabla de pginas de un proceso es la siguiente (siendo la pgina 2 la pgina que hace ms tiempo est
cargada en memoria):

15

Ejercicios de parcial 2014 V.1.0

Pg

Frame

Sistemas Operativos

UTN FRBA

Posteriormente se referencian las direcciones lgicas: 0843h(R) - 2122h(R) - 027Ah(W) y aplicando un

algoritmo de sustitucin de pginas se llega al siguiente estado:
Fr

Cul/es algoritmos se puede/n haber utilizado? Justifique

3) Un Sistema Operativo tiene 64KB de memoria y utiliza paginacin por demanda, con pginas de 1 KB
y direcciones de 20 bits. El proceso P, de 10KB, est cargado en memoria y quiere realizar la operacion
int suma = a + b.
a) Indique cul es el tamao mximo que un proceso podra direccionar en este esquema.
b) Indique el estado final de la memoria, si P tiene asignados 3 frames (inicialmente vacos) y el cdigo
ocupa la pgina 0 del proceso, suma est en la pgina 3, a en la pgina 6 y b en la pgina 6.
c) Qu sucedera si b estuviese en la pgina 8?
d) Qu sucedera si a y b estuviesen en la pgina 12?

4) Un sistema que trabaja con paginacin bajo demanda utiliza 32 bits para el direccionamiento y divide
toda su memoria en frames de 1KiB. En l se ejecuta un proceso que realiza las siguientes referencias a
memoria: 3500, 2100, 1200, 500, 3501, 2101, 4500, 3508, 2101, 1050, 50, 4200. El proceso tiene
asignados 3 frames (inicialmente vacos).
a) Calcule la cantidad de fallos de pginas producidos por los algoritmos Clock y Fifo
b) Si se otorgara un frame ms al proceso, ocurrira la anomala de Bldy?

16

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

5) Un esquema de memoria virtual tiene un tamao de pgina de 1024 bytes y la memoria fsica tiene 4
marcos de pgina. La Tabla de pginas de un proceso es:
Pgina
Virtual

Marco

---

---

---

---

---

---

a) Indique detalladamente Cules son las direcciones fsicas de las siguientes direcciones virtuales
(expresadas en decimal): 1024, 0, 3728, 1025, 1240?
b) Suponiendo que en vez de tablas de pginas, se utilizar una tabla de pginas invertida, indique qu
valores tendra la misma.

6) Una computadora que est ejecutando solamente dos procesos, utiliza un SO experimental que tiene
una memoria de 256 KiB y utiliza tabla de pginas invertida con tamao de pgina de 1024 bytes y
direcciones de 20 bits. Se conocen las siguientes direcciones lgicas:
Proceso 1: (36;125) (35;256) (39;716)
Proceso 2: (40;26) (37;456) (32;951)
a) Grafique la tabla de pginas y complete las entradas que corresponda.
b) Indique cuntas entradas tiene la tabla de pginas invertida y cuntos frames tiene la memoria.
c) Cules son las direcciones fsicas de las direcciones (39;716) y (32;951)?
Notas:

Asuma que el resto de las pginas de los procesos no estn en Memoria Principal.

Utilice como funcin de hash: f(x) = (x-36)2 (donde x es el nmero de pgina)

7) Un Sistema Operativo administra sus procesos utilizando Segmentacin simple, con direcciones de 18
bits y 64 KiB de memoria. El Sistema Operativo utiliza una lista de particiones para administrar la
memoria disponible, con poltica FIFO, y est alojado en la segunda mitad de la memoria. La tabla de
segmentos del nico proceso corriendo en un instante determinado es la siguiente:

Segmento

Base

Lmite /
Tamao

1000h

0111h

1200h

00FFh

1300h

0BEEh

a) Calcule qu direccin fsica producira la

direccin lgica 200EEh
b) Calcule qu direccin fsica producira la
direccin lgica 00211h
c) Si el proceso necesitara otro segmento de
tamao 15FFh En qu lugar de la memoria lo
ubicara?
d) Si agregado al punto c), el proceso
necesitara otro segmento de tamao 4B00.
Habra espacio libre suficiente en la memoria
para ubicarlo?

17

Ejercicios de parcial 2014 V.1.0

UTN FRBA

Sistemas Operativos

8) Lolo posee un sistema que utiliza paginacin bajo demanda, con una asignacin fija de 3 frames por
proceso y una poltica de sustitucin de frames local.
Al ejecutar un programa, en un momento determinado, el puntero a prxima instruccin es 123.

123 OPLOCA , OP1 , OP2 , OP3 , RES

Dicha instruccin, con los operandos OP1, OP2 y OP3, realiza una operacin y guarda el resultado en
RES.
Recordando que el ciclo de instruccin bsico consta de: Bsqueda de instruccin ->Decodificacin
Instruccin -> Bsqueda de operandos -> ejecucin de instruccin -> Guardar resultados. Y sabiendo
que:
Ubicacin de datos y cdigo en la
imagen Proceso
OPLOCA

PG 2

OP1

PG 6

OP2

PG 6

OP3

PG 10

RES

PG 5

Estado Frames asignados

PT
R

->

Fra
me

P
g

11

10

a) Identifique la secuencia de referencias a pginas necesarias para poder completar el ciclo de dicha
instruccin. Utilizando el algoritmo de sustitucin de pginas Clock modificado mostrar el estado de la
tabla de pginas luego de cada referencia.
b) En cada caso indicar (luego de cada referencia): si hay page fault, cules son las pginas ledas y
escritas de/a disco (si corresponde).
c) Se puede finalmente completar el ciclo de instruccin correctamente? En caso afirmativo justifique y
en caso negativo relacione el problema a un concepto de memoria (explicando el mismo).

9) Se tiene una PC con procesador de 8 bits. La misma tiene instalado un SO que emplea paginacin
bajo demanda, que asigna 3 frames fijos por proceso y utiliza sustitucin local basada en clock
modificado.
Actualmente se est ejecutando un proceso del cual se sabe que la nica pgina
que tiene en memoria es la pgina 0 (cero) y reside en el frame 1. Dicha pgina
tiene sus bits de modificado y uso ambos en 1.
Se sabe adems que el proceso realizar una serie de lecturas en memoria, de
las cuales slo se conoce el nmero de pgina y la direccin fsica con la que se
acceder a la misma:

18

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

Se pide:
1. Indicar qu frames le asignar el sistema operativo al proceso. Justifique
2. Indicar las direcciones lgicas (en hexadecimal) para cada una de las referencias a memoria
Nota: Para el punto 1 se deber justificar realizando la traza de pginas con dicho algoritmo.

10) Un esquema de memoria virtual que utiliza paginacin bajo demanda con poltica de asignacin de
frames fija y con alcance local, tiene un tamao de pgina de 1024 bytes y la memoria fsica tiene 4
marcos de pgina por proceso. Un proceso de 12 KiB inicia su ejecucin realizando las siguientes
referencias a memoria:
En decimal: 1024 - 0 - 7000 - 6500 - 45 - 2999 - 2035 - 4018 - 4019 - 12800 - 11000 - 9500
Indique detalladamente el estado de los marcos luego de cada referencia utilizando:
a) Poltica de reemplazo LRU.
b) Poltica de reemplazo FIFO.

11) Se tiene un proceso de 10 Kb ejecutando en el sistema, realizando las siguientes referencias a

memoria (en forma de pgina,desplazamiento): (1,20), (3,0), (5,200), (4,30), (3,20), (4,11), (7,20) (8,88)
(3,10)
a) Indique el estado de la memoria en cada instante de tiempo para los algoritmos de reemplazo LRU y
CLOCK
b) Indique qu algoritmo tuvo una mejor performance, justificando el criterio elegido
c) Suponga que la referencia a la pgina 5 era de escritura, cambiara en algo la solucin del punto a)?
d) Cuantas referencias a memoria hubieran existido para el punto a, en el algoritmo LRU, si se contaba
con una TLB de 10 entradas?
Nota: el esquema de memoria tiene una asignacin fija de 3 frames por proceso, con alcance local

19

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

Ejercicios de entrada/salida
1) Un disco est formado por 100 cilindros, 4 platos y 20 sectores por pista. El tiempo entre pistas es de
1ms. En el instante 0ms la cabeza se encuentra en la pista 50 y llegan los pedidos de pistas 60, 90, 25,
45 y 15. En el instante 20ms llega el pedido de pista 85 y en el instante 25 ms llega el pedido de pista 70.
Calcule el tiempo de atencin e indique en qu orden sern atendidos los pedidos utilizando:
a) Algoritmo F-SCAN y la cabeza se encuentra subiendo.
b) Algoritmo C-SCAN y la cabeza se encuentra subiendo..

2) Peter desea planificar los pedidos que llegan a sus dos discos rgidos (D1 y D2) utilizando el mismo
algoritmo (sin inanicin y sin usar N-STEP, ya que no le agrada). Ambos discos tienen 50 pistas, pero el
disco D1 tiene mayor capacidad y gira un poco ms rpido. El tiempo entre pistas es de 1ms, y las
cabezas de ambos discos estn en la pista 0. Los siguientes pedidos (n de pista) llegan en los instantes
sealados:
D1: Tiempo 0ms: 40, 2. Tiempo 10ms: 49, 40
D2: Tiempo 0ms: 35, 5, 35, 5. Tiempo 20 ms: 10
a) Indique qu algoritmo se debera elegir para que el tiempo usado para recorrer las pistas sea el menor
posible.
b) Si se deseara agregar un disco D3 de caractersticas similares a D1 para formar un RAID Qu
esquema sugerira utilizar? Justifique

3) Peter tiene un disco rgido algo viejo, con capacidad total de 4 GB, sectores de 4KB (usando Advanced
Format), 8 caras, 1024 sectores por pista y un tiempo entre pistas de 1ms. Su curiosidad lo lleva a
investigar cmo se comportaran algunos algoritmos de planificacin ante una cierta cantidad de pedidos.
Dentro de su investigacin, cuando el brazo est en la pista 0, al disco llegan los siguientes pedidos (n
de pista):
Tiempo 0: 100, 15, 90
Tiempo 20: 110, 30, 35, 40
Calcule los tiempos que tomara atenderlos utilizando FSCAN y NSTEP SCAN (N=2). Justifique sus
respuestas.

4) Un disco que posee 100 pistas (0-99) tiene su cabezal en la pista 16 ascendiendo. Se requiere saber
cundo terminara de atender los pedidos: 6-16-24-2-10, comenzando desde el instante 0, utilizando los
algoritmos C-LOOK y FSCAN si el tiempo entre pistas es 2ms y si:

20

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

a) En el instante 15ms llega un pedido en la pista 27

b) En el instante 17ms llega un pedido en la pista 27
Nota 1: Slo tenga en cuenta el tiempo de bsqueda (tiempo entre pistas).
Nota 2: Realice los puntos a) y b) como ejercicios separados.

5) Se tiene un disco de 100 cilindros 4 platos y 20 sectores por pista. El tiempo de bsqueda (seek time)
es de 2 ms. El brazo se desplaza en forma descendente en este instante y acaba de leer el bloque 177.
Tiene los siguientes pedidos encolados: 186, 2226, 1470, 7000, 154.
Ordene la cola y determine el tiempo necesario para atender todos los pedidos segn: SSTF y N-STEPSCAN( colas de 3 pedidos ).

6) Peter necesita leer un conjunto de archivos lo ms rpido posible, muchas veces al da. Como su
presupuesto no es tan alto y conoce las limitaciones de escritura de los SSD decide dividir los archivos en
dos discos independientes, cada uno de 1000 pistas, 10 caras y 10 sectores por pista.
En un momento dado se tienen los siguientes pedidos lgicos (D1: disco 1, D2: disco 2): 1000 D1, 1500
D2, 1800 D1, 5000 D1, 3300 D2, 1700 D2, 3200 D2.
a) Calcule el tiempo necesario para atenderlos a todos sabiendo que el algoritmo a utilizar es FIFO y que
el tiempo entre pistas es de 1 ms. La pista inicial es la 0 en ambos discos.
b) Mejorara la situacin si se atendieran todos los pedidos desde un nico disco usando el algoritmo
SCAN?

7) Un archivo comprimido con WinRawr est dividido en dos partes, guardadas en dos discos rgidos
distintos. La primera parte se encuentra en un disco de 100 pistas (que el S.O. planifica utilizando el
algoritmo SCAN), y para leerla necesita atender los siguientes pedidos de pistas: 88, 60, 89, 1, 20 (que
llegan a la cola en el instante 0 ms), y 60, 20 (que llegan a la cola en el instante 50 ms). La segunda parte
del archivo se encuentra en un disco de 50 pistas (que el S.O. planifica utilizando el algoritmo FSCAN), y
para leerla necesita atender los siguientes pedidos de pistas: 40, 20, 1 (que llegan a la cola en el instante
0 ms), y 40, 20 (que llegan a la cola en el instante 20 ms). En ambos casos, el tiempo entre pistas es de
1ms, y el brazo se encuentra en la pista 0.
a) Qu tiempo lleva abrir el archivo completo, si las partes se deben leer en simultneo?
b) WinRawr escribe en un pequeo archivo de log, siempre en el instante 30 ms, en la pista 25 del primer
disco. Sera conveniente mover el archivo a la pista 35 del segundo disco?.

21

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

Ejercicios de file system

1) Peter se cans de tener Windows en su PC y decide instalar Kubuntu. Al empezar a usarlo, descubre
lo maravilloso que es, y decide desafiar a un amigo que tiene Windows a que su sistema es ms rpido.
Para ello, deciden competir en la velocidad a la hora de jugar al Angry Penguins, que como se la pasa
operando con archivos, implica la necesidad de tener un desempeo muy bueno en su filesystem.
Luego de instalarse el programa Linus Toolvars, descubre que su filesystem maneja inodos, con
bloques de 4 KiB y punteros de 8 bytes. El inodo est conformado con 12 punteros directos, 1 indirecto, 1
indirecto doble y 1 indirecto triple.
Analice, suponiendo que el inodo de un archivo /trash/pagefile.sys se encuentra en memoria, la cantidad
de accesos a disco para leer:
a) El byte nro 20000112 del archivo
b) Desde el byte 0 hasta el 191233 del archivo
c) El byte nro 20000112 de un hard link al mismo archivo
d) El byte nro 60001 de un symbolic link al mismo archivo
Nota: Tenga en cuenta que su disco es un HDD (Hard Disk Drive) de 3 Gb que al parecer posee 512
cilindros, 7200 rpm, 24 cabezas y 128 sectores por pista.

2) Un File System de tipo EXT2 maneja punteros de 32 bits, bloques de 4KiB y la conformacin de su
inodo es de 10 punteros directos, 1 indirecto simple, 1 indirecto doble y 1 indirecto triple. En dicho File
System se aloja el archivo Resumen.pdf, de 4 MiB, el cual se lee y comprime a la mitad de su tamao
(sin borrar el original), y luego se guarda en el mismo directorio como Resumen.tar.gz.
a) Indique cuntos accesos a disco fueron necesarios para realizar la operacin.
b) Indique cuntos accesos a disco seran necesarios para leer el primer bloque de Resumen.pdf si
accediramos desde un Symbolic Link ubicado en el Escritorio

3) Un volumen se encuentra formateado con FAT 12. El disco posee un tamao de 1GiB. Si se sabe que
con el FS actual se logra referenciar todo el disco:
a) Qu tan bien se utilizara el espacio bajo este esquema si la mayora de los archivos son de 2KiB?
b) Encuentre el formato de FS tipo FAT que permita direccionar todo el disco y que mejor se adapte a
archivos de 2KiB.
c) Suponiendo que la tabla FAT se cargue en su totalidad a memoria principal, compare dicho sistema en
performance con EXT2, para casos de accesos concurrentes a distintos archivos.
4) Peter posee un disco de de 500 GiB formateado con un FS Unix que posee la siguiente estructura de
inodos: 15 punteros directos , 2 punteros indirectos simples , 1 puntero indirecto doble
Los bloques de datos tienen un tamao de 8 KiB y las direcciones son de 64 bits.

22

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

En su disco posee un directorio dedicado a series y pelculas. En esta oportunidad, Peter se quera bajar
(legalmente) la 3er temporada de Game of Thrones en HD, la cual tiene un tamao de 13,67 GiB. Sin
embargo, en el proceso de escritura del archivo a su disco se encontr con un problema por lo que el
archivo no se pudo guardar, sin importar que posee ms de la mitad del disco vaco. Finalmente opt por
una versin de menor calidad con un tamao de 3,9 GiB.
a) Indique y justifique qu problema tuvo Peter. Proponga dos posibles soluciones para que pueda tener
la versin HD.
b) Cuntas operaciones de disco se realizarn para escribir el archivo de 3,9 GiB a disco? (considere
escrituras de bloques de datos y de punteros).
Nota 1: Indique claramente de qu nivel son los punteros escritos.
Nota 2: Considere que toda la temporada se encuentra en un nico archivo.

5) Se deben formatear 4 discos de 32 GiB cada uno, utilizando una configuracin RAID 1. Las opciones
de FS a elegir son:

FAT16, con clusters de 1MiB.

UFS con punteros de 4 bytes, bloques de 4KiB e inodos con el siguiente formato: 2 ptrs directos, 1
ptr indirecto simple, 1 ptr indirecto doble y 1 ptr indirecto triple.
a) Seleccione una de las opciones y justifique su eleccin teniendo en cuenta que: se quiere minimizar la
cantidad de accesos a disco para leer un archivo, sin importar el tamao del mismo; se quiere poder
aprovechar todo el tamao del volumen.
b) Luego de utilizar el sistema por un tiempo, uno de los discos falla. Por lo tanto, se decide eliminar el
RAID 1 y reconfigurar los discos. Indique en cada caso la solucin a proponer (especificando la opcin de
FS a utilizar en cada caso):
b1- Proveer seguridad de los datos y permitir escrituras eficientes
b2- Obtener el mayor volumen posible, sin importar la seguridad de los datos

6) Peter tiene dos volmenes en su disco rgido; el primero se encuentra formateado con FAT16, con
clusters de 8KiB, y el segundo con UFS, con inodos que poseen: 10 ptrs directos, 2 ptrs indirectos
simples, 1 ptr indirecto doble y 1 ptr indirecto triple (el tamao puntero es de 8bytes) y bloques de 2 KiB.
Luego de tener problemas de espacio en su primera particin comenz a pasar sus archivos a la particin
con UFS. El primer archivo a mover, se encuentra comprimido y su tamao es de 1MiB. Una vez que el
archivo se encuentra en la segunda particin, el mismo se descomprime (alcanzando el doble del tamao
inicial).
Considerando que la tabla FAT y la tabla de inodos se encuentran en memoria:
a) Calcule la cantidad de accesos a clusters, a bloques de datos y bloques de punteros (segn
corresponda) necesarios para realizar las operaciones.

23

Ejercicios de parcial 2014 V.1.0

Sistemas Operativos

UTN FRBA

b) Indique, en cada uno de los filesystems, qu modificaciones sufrieron las estructuras administrativas al
realizar dichas operaciones.

7) Dado un disco con FAT32 y clusters de 12 Kb

a) Indique el tamao mximo terico del filesystem
b) Indique el tamao mximo real si se formatea sobre un pendrive de 4 TB
c) Cunto espacio en disco ocupara la FAT?
d) Cul es el mximo de fragmentacin interna que podra tener el filesystem?
Nota: Recuerde que dicho fs utiliza solamente 28 bits para direccionar clusters.

8) Un filesystem de tipo Unix maneja bloques de 4KiB, punteros de 32 bits. Adems se sabe que el inodo
cuenta con 10 punteros directos, un puntero indirecto simple, un puntero indirecto doble y un puntero
indirecto triple. Se utiliza un disco que tiene 256 GiB con sectores de 1024 bytes.
a) Calcule el tamao mximo terico de un archivo.
b) Cuntos accesos a disco se requieren para leer los primeros 10 MiB de un archivo.
c) Calcule el tamao mximo terico y real del filesystem.

9) En la VM de Ubuntu que Peter usa para el trabajo prctico, tiene un sistema de archivos ext2 con
bloques de 2 KiB y tamao de punteros de 16 Bytes. Dentro de la VM tiene la cancin Lessons.mp3 (de
la banda Rush) que se encuentra direccionada de la siguiente forma: 12 bloques directos, 1 bloque
indirecto completo y un bloque indirecto doble con solo 62 bloques indirectos completos.
Como quiere escuchar esa cancin en mi equipo iPod, que usa FAT16 con clusters de 256 bytes,
aprovecha que tiene un pendrive vaco formateado en ese sistema de archivos con clusters de 256 Bytes
para pasar la cancin all.
a) Podr pasar la cancin al pendrive?
b) Independientemente del punto anterior, suponga que la cancin se pudo pasar. Si luego ese pendrive
se monta en otra PC, indique cuntos accesos al pendrive se necesitarn para leer el byte 875424
(asuma que la FAT est en memoria, y que los sectores son de 128 bytes)
Nota: El manual del iPod dice Tamao disponible: todo lo que direccione el filesystem menos lo que
ocupen la tabla FAT y su copia.

24