Repaso final: chuleta, flashcards y simulacro del LC3

💡 En simple

Usa esta página al final, después de las páginas de cada tema:

1. Lee la chuleta y pregúntate «¿sabría explicar esto?».
2. Pasa las flashcards (tu progreso se guarda en el navegador).
3. Haz el simulacro con un cronómetro, en el mismo orden que el LC3: primero el código y después el quiz.

Chuleta

Memoria virtual

• Partes de una dirección: offset = $\log_2(\text{página})$; VPN = bits virtuales − offset; PFN = bits físicos − offset.
• Tabla: entradas = $2^{VPN}$ (o memoria virtual / página); tamaño = entradas × bytes por PTE.
• Multinivel con tablas de una página: bits por nivel = $\log_2(\text{página}/\text{PTE})$; niveles = ⌈VPN / bits por nivel⌉.
• Accesos por referencia: sin TLB, k niveles + 1. Con TLB: 1 si acierta, k + 1 si falla.
• Tiempo efectivo de acceso: $\text{EAT} = t_{TLB} + t_m + (1-h)\,k\,t_m$ si siempre se consulta la TLB. Despejar h: $(1-h) = (\text{EAT} - t_{TLB} - t_m)/(k\,t_m)$.
• PTE: P/V (presente), M (dirty), R/U (uso), protección, frame. Invertida: una entrada por frame, con hash de (página, PID).
• Page fault: trap → validar → frame libre o víctima (escribirla si M = 1) → leer del disco (el proceso se bloquea) → actualizar la PTE → reiniciar la instrucción.
• Reemplazo:
  • OPT: la que se usa más tarde;
  • LRU: la usada hace más tiempo;
  • FIFO: la más vieja en memoria;
  • Clock: pone u = 0 al pasar y saca la primera con u = 0;
  • Clock mejorado: prefiere (u, m) = (0, 0) > (0, 1) > (1, 0) > (1, 1).
  • Belady: FIFO y Clock pueden tener más fallos con más frames; LRU y OPT (algoritmos de pila) no.
• Conjunto residente:
  • fija + local, variable + local o variable + global; fija + global es imposible;
  • working set $W(t,\Delta)$ = las páginas de las últimas Δ referencias;
  • PFF: crecer si los fallos están muy seguidos, encogerse si no.
• Limpieza: por demanda (2 E/S) vs precleaning (E/S desperdiciada) → page buffering.
• Thrashing: la CPU cae y el disco se satura. Hay que bajar el nivel de multiprogramación (criterio L = S o 50 %).
• UNIX/Linux: reloj de dos manecillas (scanrate, handspread), lazy buddy, COW; en Linux, split LRU (activa/inactiva, kswapd), buddy de frames y slab/SLUB/SLOB.

Deadlock y sincronización

• Coffman: exclusión mutua + hold and wait + no expropiación + espera circular.
• Filósofos:
  • semáforo central (1) → sin deadlock, come uno a la vez;
  • k ≤ N − 1 sillas → sin deadlock;
  • asimétrica → sin deadlock, con paralelismo ⌊N/2⌋;
  • Tanenbaum → sin deadlock, pero puede haber starvation (tanen-5-1, tanen-4-2).
• trylock: rompe hold and wait, pero puede haber livelock. La solución robusta es el orden global de los locks.
• Barbero:
  • sem_trywait(seats) (no bloquea);
  • barber_chair, client_seat y hair_cut (el barbero decide cuándo termina);
  • con N barberos, un panel (write_panel = 1, read_panel = 0), y barber_chair sobra.
• Valgrind:
  • Invalid write/read (fuera del bloque o ya liberado), Invalid free (doble o no-heap), definitely lost (fuga), Conditional jump … uninitialised (en el if, no en la declaración);
  • no ve desbordes del stack;
  • helgrind encuentra races aunque el resultado haya salido bien.

Flashcards

Flashcards

dominadas 0/40

TodosMemoria virtualReemplazoConjunto residenteUNIX/LinuxDeadlockBarberoUNIXLinuxValgrind solo pendientesBarajarReiniciar progreso

Memoria virtual · pregunta · 1/40¿Qué dos características permiten la memoria virtual?clic para voltear

← AnteriorRepasarLa séSiguiente →

Simulacro del LC3

¿Quieres algo más duro? Pasa después a LC3 · peor escenario. Para las 4 teóricas (las del libro), repasa antes Stallings para el LC3.

Instrucciones (como el LC3 real)

• Primero el código (2 preguntas, 6 pts, máximo 60 min), resuelto en papel o en tu editor y probado.
• Después el quiz: 4 teóricas (5 pts) y 3 de análisis (9 pts).
• Abre las soluciones solo al terminar.

Código 1 (3 pts) · Barbero con sem_trywait

Completa los huecos para 1 barbero y 5 sillas de espera. Un cliente que no encuentra silla se va sin bloquearse, el barbero duerme si no hay clientes, y el cliente no se levanta hasta que el barbero termina.

sem_t seats, barber_chair, client_seat, hair_cut;

void *cliente(void *a) {                     void *barbero(void *a) {
    if (/* [1] */) {                              while (1) {
        /* [2] */;                                    /* [5] */;
        sem_post(&seats);                             cut_shave();
        /* [3] */;                                    /* [6] */;
        /* [4] */;                                }
        sem_post(&barber_chair);              }
    } else leaves();
}
/* main: sem_init(&seats,0,[7]); sem_init(&barber_chair,0,[8]);
         sem_init(&client_seat,0,[9]); sem_init(&hair_cut,0,[10]); */

Solución y pauta (probada en una ejecución de prueba)

Hueco	Código
[1]	sem_trywait(&seats) == 0
[2]	sem_wait(&barber_chair)
[3]	sem_post(&client_seat)
[4]	sem_wait(&hair_cut)
[5]	sem_wait(&client_seat)
[6]	sem_post(&hair_cut)
[7]–[10]	5, 1, 0, 0

Es la solución de la diap. 41, probada con 300 clientes: 237 atendidos y 63 que se fueron, nunca más de 5 esperando (barbero).

Pauta: 0.3 por hueco. [1] con sem_wait en lugar de sem_trywait vale 0, porque el cliente se bloquearía en vez de irse.

Código 2 (3 pts) · Errores de memoria

 4  char *duplicar(const char *s) {
 5      char *d = malloc(strlen(s));
 6      strcpy(d, s);
 7      return d;
 8  }
 9
10  int main(void) {
11      int *v = malloc(5 * sizeof(int));
12
13      for (int i = 0; i <= 5; i++)
14          v[i] = i * i;
15      char *nombre = duplicar("utec");
16      printf("%s %d\n", nombre, v[2]);
17      free(v);
18      printf("%d\n", v[0]);
19      return 0;
20  }

Indica cada error que reportaría memcheck (tipo y línea) y corrige el programa.

Solución (salida real de memcheck)

Invalid write of size 4     at main (lc3_mem.c:14)   0 bytes after a block of size 20 alloc'd
Invalid write of size 1     (strcpy, línea 6)          0 bytes after a block of size 4 alloc'd
Invalid read of size 1      (printf, línea 16)         0 bytes after a block of size 4 alloc'd
Invalid read of size 4      at main (lc3_mem.c:18)   0 bytes inside a block of size 20 free'd
4 bytes in 1 blocks are definitely lost
ERROR SUMMARY: 5 errors from 5 contexts

#	Línea	Error	Corrección
1	14	i <= 5 escribe v[5], fuera de un bloque de 5 enteros	i < 5
2	6 (por la 5)	malloc(strlen(s)) no deja espacio para el '\0': strcpy escribe 1 byte de más	malloc(strlen(s) + 1)
3	16	printf("%s") lee ese mismo byte fuera del bloque (consecuencia del error 2)	se arregla con el error 2
4	18	lee v[0] después del free(v) (uso tras liberar)	mover free(v) al final
5	—	nombre nunca se libera: 4 bytes definitely lost	free(nombre) antes de return

La versión corregida da 0 errores. Ojo: el programa original imprimió bien (utec 4, 0). Por eso hay que usar Valgrind: los bugs de memoria muchas veces no se notan.

Pauta: 0.5 por error bien ubicado y 0.5 por un programa corregido que compile.

Quiz: teóricas (5 pts) y análisis (9 pts)

Teóricas (1.25 c/u)

0/4 correctas · 0 respondidas Reiniciar

1. ¿Cuál de las condiciones de Coffman normalmente NO se puede eliminar?

a) Hold and waitb) No expropiaciónc) Exclusión mutua: hay recursos que por naturaleza no se compartend) Espera circular

2. La paginación sufre fragmentación…

a) externab) interna (la última página del proceso queda a medias)c) ningunad) ambas

3. Si el nivel de multiprogramación sube demasiado…

a) la CPU llega al 100 %b) aparece el thrashing: los procesos no tienen su working set y el uso de la CPU caec) baja la tasa de fallosd) se activa el buddy

4. En una tabla de páginas invertida, la búsqueda se hace…

a) indexando por número de páginab) con un hash de (página, PID) sobre una tabla de una entrada por framec) secuencialmente en discod) en la TLB solamente

Análisis (3 c/u)

0/3 correctas · 0 respondidas Reiniciar

1. Cadena 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 con 3 frames vacíos. Fallos de FIFO, OPT y LRU:

a) 15, 9, 12b) 12, 9, 15c) 15, 12, 9d) 10, 7, 8

2. Paginación de 2 niveles 10|10|12 y PTE de 4 B. La dirección virtual 0x00C03A7C y la PTE final dice frame 0x1F2. ¿Índices y dirección física?

a) directorio 3, tabla 3, física 0x1F2A7Cb) directorio 0xC0, tabla 0x3A, física 0x1F27Cc) directorio 3, tabla 0x3A7, física 0x1F2Cd) directorio 12, tabla 3, física 0x1F2000

3. Filósofos (N = 5) donde cada uno toma primero el tenedor de MENOR número y luego el de mayor. ¿Qué pasa?

a) Deadlock como la versión ingenuab) Sin deadlock (orden global de los recursos rompe la espera circular) y pueden comer hasta 2c) Sin deadlock pero come de a unod) Livelock

Después del simulacro: corrige como tutor

Un simulacro sirve el doble si diagnosticas cada error en vez de solo contarlo. Por cada pregunta que perdiste puntos:

1. Busca el primer paso que hiciste mal, no solo la respuesta final.
2. Clasifícalo y haz lo que dice la tabla:

Tipo de error	Señal	Qué hacer
Conceptual	no sabías la regla, o tenías una idea equivocada («inseguro = deadlock»)	vuelve a la página del tema: «En simple», «Predice» y «Errores que cuestan puntos»
Procedimental	sabías la regla, pero te saltaste o desordenaste un paso (olvidaste el bit de validez)	rehaz los peldaños 2 y 3 de la escalera de ese tema
De cálculo	potencias de 2, binario o hexadecimal, sumas	un ejercicio corto solo de esa operación, y vuelve al problema
De interpretación	leíste mal el enunciado o no declaraste la convención	vuelve a leer el enunciado y subraya los supuestos (marcos, convención de Clock, niveles)

3. Marca tu nivel en esa página (📈) para que el panel de repaso te la vuelva a mostrar en el momento justo.
4. Escribe tu hoja de errores: 5 a 8 líneas con lo que no puedes volver a hacer. Léela la mañana del LC3.

Fuente ·Todo el material de sem_9 y las páginas de esta sección · Simulacro propio; respuestas verificadas con el simulador de reemplazo, un recorrido exhaustivo de estados y ejecuciones de prueba (barber.c, lc3_mem.c)