Final de práctica — Sistemas Operativos

Temas: todo el curso, con énfasis en las semanas 9 a 16 · Tiempo de trabajo estimado: 120 minutos

Este es un examen de práctica con el formato del final. Sirve para medir cuánto les toma cada tipo de pregunta: resuélvanlo en papel, de corrido y con el reloj en marcha, y recién después comprueben sus respuestas con los programas de cada semana. Cada pregunta trae su tiempo estimado.

Indicaciones

• Muestren el procedimiento: el número solo no basta. Si un inciso usa el resultado de otro, usen el que obtuvieron, aunque duden de él.
• Los errores menores de sintaxis en C no importan si la idea es correcta.
• Salvo que la pregunta diga otra cosa, se pide el modelo de OSTEP y de los apuntes. Las preguntas sobre xv6 se refieren a xv6-riscv, el kernel del curso.

Convenciones del curso

• Planificación. Como en sched.c (semana 3): el tiempo avanza en ticks enteros. STCF elige el menor tiempo restante y, si empatan, sigue el que ya corría. En Round Robin, los trabajos que llegan en el instante t entran a la cola antes que el trabajo desalojado en t. Retorno = fin − llegada; respuesta = primera vez que corre − llegada.
• Reemplazo de páginas. Como en paging.c (semana 8). Los marcos libres se llenan en orden (0, 1, 2). En el reloj, la manecilla empieza en el marco 0; una página que entra o que se usa tiene el bit en 1; después de llenar un marco o de reemplazar una víctima, la manecilla queda en el marco siguiente.
• Banquero. Como en banker.c (semana 12): en cada vuelta se elige el primer proceso, en el orden de la tabla, cuya necesidad cabe en Trabajo.
• Unidades. En tasas y capacidades de discos, como los fabricantes: 1 MB = 1000 KB, 1 TB = 10⁶ MB. En bloques, páginas, offsets y tablas, potencias de 2: 1 KB = 1024 bytes, 1 GB = 2³⁰ bytes, y la pregunta lo repite cuando hace falta.
• RAID 5. La distribución de raid5.c (la de OSTEP): con N discos, la franja s guarda su paridad en el disco N − 1 − (s mod N), y sus bloques de datos van a la derecha de la paridad, en orden y dando la vuelta.

Parte A — Repaso de las semanas 1 a 8

Pregunta 1 — Planificación con llegadas

Tiempo estimado: 10 min

Cuatro trabajos que solo usan la CPU:

a) Dibujen el diagrama de Gantt con STCF y calculen el tiempo de retorno y el de respuesta de cada trabajo, y sus promedios.

b) Lo mismo con Round Robin de quantum 2. Expliquen qué pasa en t = 6, cuando llega D y a la vez se acaba el quantum de un trabajo.

c) ¿Cuál de las dos políticas da mejor retorno promedio y cuál mejor respuesta promedio? ¿Por qué STCF no se puede implementar tal cual en un sistema de propósito general, y qué ofrece RR aunque aquí pierda en las dos métricas?

Pregunta 2 — Traducción, TLB y reemplazo

Tiempo estimado: 11 min

a) Una máquina de 32 bits con páginas de 4 KB y PTE de 4 bytes usa una tabla de dos niveles como la de x86: la VA se parte en 10 + 10 + 12 bits. El registro de la tabla apunta al directorio en 0x00200000. Esta es parte de la memoria; cada palabra es una PDE o una PTE, y “V” significa válida:

Para cada VA, digan qué índices tiene, qué direcciones de la tabla se leen, la dirección física o el fallo, y cuántos accesos a memoria hace la MMU (contando el del dato, si lo hay): 0x00405C38, 0x00802010, 0x00407FFC y 0x00C05010. La TLB está vacía.

b) Un acceso a memoria cuesta 100 ns y la TLB acierta el 95 % de las veces. ¿Cuál es el tiempo promedio de un acceso con esta tabla de dos niveles? ¿Y con la de tres niveles de Sv39?

c) Un proceso tiene 3 marcos y hace estas referencias: 2 3 2 1 5 2 4 5 3 2 5 2. ¿Cuántos fallos tiene con OPT, FIFO, LRU y el reloj? Para el reloj, escriban qué página expulsa cada fallo que ocurre con los tres marcos ocupados.

Parte B — Concurrencia

Pregunta 3 — Carreras y locks

Tiempo estimado: 8 min

La variable compartida x vale 3. Dos hilos corren a la vez; el compilador traduce cada sentencia a tres instrucciones de RISC-V:

// Hilo 1: x = x + 1          // Hilo 2: x = x * 2
ld   a5,0(a4)                 ld   a5,0(a4)
addi a5,a5,1                  slli a5,a5,1
sd   a5,0(a4)                 sd   a5,0(a4)

a) ¿Qué valores finales puede tener x? Para cada uno, den una intercalación que lo produzca. ¿Cuál es la sección crítica?

b) Si cada sentencia va entre pthread_mutex_lock(&m) y pthread_mutex_unlock(&m), ¿qué valores quedan? ¿El programa es determinista?

c) En xv6, acquire() empieza con push_off(), que apaga las interrupciones de la CPU. sys_sleep toma tickslock y el manejador del reloj, clockintr, toma el mismo lock. ¿Qué pasaría si acquire no apagara las interrupciones?

Pregunta 4 — Una cola de trabajos

Tiempo estimado: 12 min

Un grupo de 3 trabajadores saca trabajos de una cola. La cola nunca se llena. El programa principal encola 6 trabajos con submit y después llama a pool_shutdown:

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  c = PTHREAD_COND_INITIALIZER;
int queue[N], head = 0, tail = 0;      // vacía si head == tail
int shutdown_flag = 0;

void submit(int job) {
    pthread_mutex_lock(&m);
    queue[tail % N] = job;
    tail++;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

void *worker(void *arg) {
    for (;;) {
        pthread_mutex_lock(&m);
        while (head == tail && !shutdown_flag)
            pthread_cond_wait(&c, &m);
        if (head == tail) {            // vacía y cerrando: salir
            pthread_mutex_unlock(&m);
            return NULL;
        }
        int job = queue[head % N];
        head++;
        pthread_mutex_unlock(&m);
        run(job);
    }
}

void pool_shutdown(void) {
    shutdown_flag = 1;                 // (S1)
    pthread_cond_signal(&c);           // (S2)
    for (int i = 0; i < NWORKERS; i++)
        pthread_join(tid[i], NULL);
}

En las pruebas, pool_shutdown a veces no retorna.

a) ¿Por qué en submit basta un signal, si todos los trabajadores duermen en la misma CV?

b) Supongan que cuando se llama a pool_shutdown los 6 trabajos ya terminaron y los 3 trabajadores duermen en c. ¿Qué pasa? ¿Cuántos trabajadores salen?

c) Cambien (S2) por pthread_cond_broadcast(&c). Todavía hay una intercalación en la que un trabajador no sale nunca. Descríbanla paso a paso. ¿Qué regla del uso de variables de condición rompe (S1)?

d) Escriban pool_shutdown corregida.

Pregunta 5 — Deadlock: evitar y detectar

Tiempo estimado: 12 min

Un sistema tiene tres tipos de recurso, A, B y C, y Disponible = (1 1 1):

a) ¿Cuántas instancias hay de cada tipo? Calculen la matriz Necesidad.

b) ¿Es seguro el estado? Si lo es, den la secuencia segura que encuentra el algoritmo con la convención del curso.

c) Evalúen, cada una desde el estado de la tabla, estas solicitudes: P4 pide (1 0 0), P2 pide (0 0 2) y P5 pide (0 1 1). ¿Se concede, se niega o es un error? ¿Por qué se niega la más pequeña?

d) Otro sistema, con dos tipos de recurso de dos instancias cada uno, X e Y, y Disponible = (0 0):

¿Hay un ciclo en el grafo de asignación de recursos? ¿Hay deadlock? Justifiquen con el algoritmo de detección.

Parte C — Persistencia

Pregunta 6 — Discos

Tiempo estimado: 9 min

a) Un disco de laptop gira a 5 400 RPM, tiene una búsqueda promedio de 12 ms y transfiere a 120 MB/s. Calculen el tiempo de una lectura aleatoria de 4 KB, cuántas hace por segundo y su tasa en MB/s. Luego, el tiempo y la tasa de una lectura secuencial de 100 MB.

b) Hay ocho pedidos pendientes, en este orden de llegada, sobre las pistas 0 a 99: 72 15 55 90 33 8 47 64. El cabezal está en la pista 39 y va subiendo. Den el orden de atención y el total de pistas recorridas con FCFS, SSTF, SCAN (llega hasta la pista 99 y regresa), LOOK y C-SCAN (llega hasta la 99, vuelve a la 0 sin atender, y ese regreso cuenta).

c) ¿Por qué ninguna de las cinco garantiza el menor tiempo total? ¿Quién puede hacerlo mejor, el sistema operativo o el disco?

Pregunta 7 — RAID

Tiempo estimado: 9 min

a) Un RAID 5 tiene 4 discos. Dibujen las franjas 0 a 3 con la convención del curso. ¿En qué disco y franja está el bloque lógico 7, y dónde está su paridad?

b) Dos escrituras pequeñas llegan a la vez. ¿Pueden ir en paralelo las de los bloques 1 y 4? ¿Y las de los bloques 5 y 10?

c) En la franja 0 los primeros bytes de los tres bloques de datos son 0x5A, 0x3C y 0xF0. ¿Cuánto vale la paridad? Se reemplaza 0x3C por 0x0F: calculen la paridad nueva con el método sustractivo y comprueben el resultado. ¿Cuántas E/S cuesta esa escritura?

d) Con 4 discos de 8 TB y el disco de la pregunta 6 (usen S = 117,5 MB/s y R = 57 E/S por segundo), completen capacidad, tasa secuencial, lectura aleatoria y escritura aleatoria para RAID 0, RAID 1 (RAID 10) y RAID 5. Si falla un disco, ¿cuánto tarda, como mínimo, reconstruirlo escribiendo el reemplazo a la tasa S?

Pregunta 8 — Sistemas de archivos y xv6

Tiempo estimado: 12 min

a) En VSFS (64 bloques de 4 KB; tabla de inodos desde el bloque 3; inodos de 256 bytes), ¿en qué bloque y en qué byte de ese bloque está el inodo 53? ¿En qué sector, si los sectores son de 512 bytes?

b) Sin caché, ¿cuántas lecturas hacen open("/a/b/c", O_RDONLY) y luego leer los dos bloques de c? ¿Cuántas veces se lee un bitmap?

c) En xv6 (bloques de 1 KB = 1024 bytes, 12 punteros directos y uno indirecto de 256 entradas), ¿en qué bloque lógico y en qué byte de ese bloque están los offsets 5 000, 13 000 y 200 000? Para cada uno, ¿se usa un puntero directo o el bloque indirecto (y qué entrada), y cuántas lecturas hacen falta sin caché, contando la del bloque con el inodo?

d) El proyecto P5 cambia un puntero directo por uno doblemente indirecto, sin cambiar el tamaño de struct dinode: quedan 11 directos, un indirecto y un doble indirecto. ¿Cuál es el tamaño máximo de un archivo? Con P5 hecho, ¿qué índices usa bmap() para el offset 300 000, y cuántas lecturas hacen falta sin caché?

Pregunta 9 — Consistencia ante fallos

Tiempo estimado: 8 min

Agregar un bloque a un archivo cambia el inodo I, el bitmap de datos B y el bloque de datos Db.

a) En journaling de metadatos (modo ordered), escriban el orden de las escrituras al disco. Si el sistema se cae justo después de escribir en el journal TxB, I’ y B’, pero antes de TxE, ¿qué estado queda después de la recuperación? ¿Y si se cae después de TxE, a mitad del checkpoint?

b) ¿Qué puede pasar si Db se escribe después de TxE (el modo writeback) y el sistema se cae entre los dos? ¿Lo detecta fsck?

c) En xv6, begin_op() duerme si log.lh.n + (log.outstanding + 1) * MAXOPBLOCKS > LOGBLOCKS, con MAXOPBLOCKS = 10 y LOGBLOCKS = 30. La transacción en curso ya anotó 4 bloques. ¿Puede entrar una llamada nueva si hay 1 en curso? ¿Y si hay 2? ¿Por qué el commit de xv6 es escribir la cabecera del log?

Pregunta 10 — LFS y SSDs

Tiempo estimado: 9 min

a) En LFS, cada escritura paga un posicionamiento de 8 ms y transfiere a 200 MB/s. ¿Qué tamaño de segmento hace falta para alcanzar el 80 % de la tasa pico? ¿Y el 95 %?

b) Una SSD de juguete tiene 3 bloques de 4 páginas (páginas físicas 0 a 11). El FTL es log-structured: cada escritura va a la siguiente página libre, empezando en la 0. El sistema escribe las páginas lógicas 10 11 12 13 10 12 14 11 15, en ese orden. Luego el recolector limpia, entre los bloques llenos, el que tiene menos páginas vivas: copia sus páginas vivas a las siguientes páginas libres y lo borra. ¿Qué bloque elige, qué copia y adónde? ¿Cómo queda la tabla de mapeo? ¿Cuánto vale la amplificación de escritura, contando como escrituras del sistema las 9 de la secuencia?

c) Con mapeo por página, ¿cuánta DRAM ocupa la tabla de una SSD de 2 TB (aquí, 2 × 2⁴⁰ bytes) con páginas de 4 KB y entradas de 4 bytes? ¿Por qué TRIM reduce la amplificación de escritura?

Parte D — Sistemas distribuidos y seguridad

Pregunta 11 — NFS y AFS

Tiempo estimado: 6 min

a) Un cliente NFS envía un pedido, vence el timeout y lo reenvía. ¿Para cuáles de estas operaciones es inofensivo el reenvío, y por qué: READ(fh, 0, 4096), WRITE(fh, 8192, 4096, datos), REMOVE(dir, "f") y una operación APPEND(fh, datos) que escribiera al final del archivo? ¿Qué tiene que ver esto con que el servidor no guarde estado?

b) En AFSv2, el archivo F tiene la versión v1 en el servidor. Pasa esto, en orden:

1. C1 abre F.
2. C2 abre F.
3. C2 escribe v2 en su copia.
4. C1 lee F.
5. C2 cierra F.
6. C1 lee F (todavía lo tiene abierto).
7. C1 cierra F y lo vuelve a abrir.
8. C1 lee F.

¿Qué versión lee C1 en los pasos 4, 6 y 8? ¿Qué hace el servidor en el paso 5? Si C1 hubiera escrito v3 y cerrado F después del paso 5, ¿qué versión quedaría en el servidor?

Pregunta 12 — Permisos de Unix

Tiempo estimado: 8 min

Ana y Beto están en el grupo curso; Carla no. No hay ACLs ni bit sticky:

-r--rw----  ana   curso  informe.txt
-rwxr-x--x  beto  curso  prog
drwx-wx---  ana   curso  proyecto/
-rw-r--r--  ana   curso  proyecto/plan.txt

a) Digan si se permite cada acceso y qué clase de permisos decide: Ana lee informe.txt; Ana escribe informe.txt; Beto escribe informe.txt; Carla lee informe.txt; Carla ejecuta prog; Carla lee prog.

b) Beto quiere listar proyecto/, leer proyecto/plan.txt, crear proyecto/nuevo.txt y borrar proyecto/plan.txt. ¿Qué puede hacer y qué no? Carla quiere leer proyecto/nuevo.txt: ¿puede?

c) Con umask 027, ¿qué permisos tiene un archivo creado con open(..., O_CREAT, 0666)? ¿Y un directorio creado con mkdir(..., 0777)?

d) passwd es de root y tiene modo 4755. Ana lo ejecuta: ¿qué uid real y qué uid efectivo tiene el proceso? ¿Por qué un programa así debe soltar los privilegios apenas termina lo que necesita de root?

Pregunta 13 — Preguntas cortas

Tiempo estimado: 6 min

a) Un kernel invitado ejecuta csrw satp, a0 en una máquina virtual con trap-and-emulate. ¿Qué pasa, paso a paso? ¿Por qué el x86 de 32 bits no se podía virtualizar así?

b) Un programa setuid root hace esto antes de mostrarle un archivo al usuario:

if (access(ruta, R_OK) != 0)
    return -1;
int fd = open(ruta, O_RDONLY);

¿Qué ataque permite? ¿Cómo se corrige?

c) Para cada defensa, digan qué paso de un ataque por buffer overflow en la pila rompe: canario de pila, NX (W^X), ASLR y PIE.

Después del examen: lo que ya pueden hacer

Al corregir su intento, marquen cada resultado de aprendizaje del programa que ya dominan. Si una pregunta les costó, vuelvan a las semanas indicadas: la Ruta de lectura de cada capítulo dice qué secciones repasar, y las Preguntas de repaso de la guía semanal y los Ejercicios del capítulo sirven de práctica.

• Puedo explicar cómo el OS virtualiza la CPU con procesos, ejecución directa limitada y planificación, y comparar FIFO, SJF, STCF, RR, MLFQ, lotería, stride y CFS calculando tiempos de retorno y de respuesta. Semanas 1–4 · pregunta 1 · P1 y P2. Este final no trae MLFQ, lotería ni stride: practíquenlos con mlfq.c, lottery.c y stride.c y con los ejercicios de las semanas 3 y 4.
• Puedo traducir direcciones a mano con base y límite, segmentación, paginación, TLB y tablas multinivel, y simular el reemplazo de páginas con OPT, FIFO, LRU y el reloj. Semanas 5–8 · pregunta 2 · P3. Base y límite y segmentación no tienen pregunta aquí: repasen los ejemplos resueltos de la semana 5.
• Puedo escribir programas concurrentes correctos en C con pthreads, encontrar una condición de carrera o un deadlock en código dado y elegir entre lock, variable de condición y semáforo. Semanas 9–12 · preguntas 3, 4 y 5 · P4.
• Puedo describir cómo funcionan los discos, RAID, los SSDs y los sistemas de archivos, calcular tiempos de disco y capacidades de RAID, y explicar cómo el journaling recupera la consistencia después de un fallo. Semanas 12–15 · preguntas 6, 7, 8, 9 y 10 · P5.
• Puedo explicar los principios de NFS y AFS (protocolo sin estado, idempotencia, callbacks) y los mecanismos de seguridad de un OS (autenticación, permisos, ACLs, defensas contra la explotación de software). Semanas 15–16 · preguntas 11, 12 y 13 b) y c). La autenticación y las ACLs POSIX no tienen pregunta aquí: repasen la semana 16 y sus ejercicios.
• Puedo modificar xv6-riscv: agregar una llamada al sistema y cambiar su planificador, su memoria virtual y su sistema de archivos. Semanas 4–8, 10, 11 y 14 (secciones «En xv6» de los capítulos) · preguntas 3 c), 8 c) y d), 9 c) y 13 a). En papel solo se puede razonar sobre el código; la práctica de verdad son P2, P3, P5 y el bono.