Apuntes · Capítulo 8Memoria

Más allá de la memoria física: swapping y sistemas de memoria virtual completos

Más allá de la memoria física: swapping y sistemas de memoria virtual completos

En las semanas 5 a 7 construimos la memoria virtual pieza por pieza: el espacio de direcciones, la paginación, la TLB y las tablas multinivel. En todas ellas hicimos una suposición cómoda: todas las páginas de todos los procesos tienen un marco de página (page frame) en la memoria física. Esta semana la quitamos. ¿Qué pasa cuando la suma de lo que piden los procesos es mayor que la RAM?

La respuesta es usar el disco como un nivel más de la jerarquía de memoria. Las páginas que no se están usando esperan en el disco, en el espacio de swap, y vuelven a la RAM cuando alguien las necesita. Para que esto funcione hacen falta un mecanismo (el bit presente y el manejo del fallo de página) y una política (qué página sacar cuando no hay espacio). Al final veremos cómo combinan todas estas ideas dos sistemas reales, VAX/VMS y Linux, y qué hace xv6-riscv con los fallos de página.

Ruta de lectura.

  • Antes de clase (15–20 min): «Espacio de swap», «El bit presente» y «Qué pasa en un fallo de página», de «El mecanismo: el bit presente y el fallo de página».
  • En clase: sesión A (la sesión B es el examen parcial), «Cuánto cuesta un fallo», «La política: qué página expulsar», «Aproximar LRU: el algoritmo del reloj», «Thrashing y conjunto de trabajo» y «Sistemas reales»; laboratorio, «Experimento: presión de memoria en el contenedor» y «Fallos de página en xv6-riscv».
  • Después de clase: repasar el «Resumen» y el «Repaso para el examen parcial», y resolver los «Ejercicios». Para ampliar: OSTEP cap. 21 a 23.

Lectura. Este capítulo acompaña a OSTEP cap. 21 Beyond Physical Memory: Mechanisms, cap. 22 Beyond Physical Memory: Policies, cap. 23 Complete Virtual Memory Systems y el diálogo del cap. 24. El código está en code/week-08 y se compila con make dentro del contenedor del curso. La sesión B de esta semana es el examen parcial; al final del capítulo hay una sección de repaso.

El mecanismo: el bit presente y el fallo de página

Espacio de swap

El kernel reserva una zona del disco (una partición o un archivo) dividida en bloques del tamaño de una página: el espacio de swap (swap space). Cuando una página sale de la RAM, se escribe en un bloque libre y el kernel anota cuál. El código no necesita swap: si se expulsa, se vuelve a leer del ejecutable. El swap es para el heap, la pila y todo lo que no tiene otra copia en el disco.

El bit presente

Con swap, cada entrada de la tabla de páginas (page table entry, PTE) debe decir además si la página está en memoria o en disco. Para eso está el bit presente (present bit):

  • Presente en 1: la MMU traduce como siempre.
  • Presente en 0: la MMU no puede traducir. Lanza una excepción, un fallo de página (page fault), y le pasa el problema al kernel.

Con la página fuera, el número de marco no sirve, y el kernel usa esos bits para guardar el bloque de swap donde quedó.

Tabla de páginas del proceso A con cuatro entradas: las páginas 0 y 2 tienen el bit presente en 1 y apuntan a los marcos 0 y 3 de la RAM; las páginas 1 y 3 tienen el bit en 0 y apuntan a los bloques 0 y 1 del swap. La RAM y el swap también guardan páginas de los procesos B y CTabla de páginas del proceso A con cuatro entradas: las páginas 0 y 2 tienen el bit presente en 1 y apuntan a los marcos 0 y 3 de la RAM; las páginas 1 y 3 tienen el bit en 0 y apuntan a los bloques 0 y 1 del swap. La RAM y el swap también guardan páginas de los procesos B y C
Con P = 1 la PTE dice en qué marco está la página; con P = 0, en qué bloque del swap la dejó el kernel.

En xv6. RISC-V no tiene un bit “presente” separado. La PTE de Sv39 tiene los bits V, R, W, X, U, G, A, D y dos bits RSW reservados para el software (ver kernel/riscv.h). Si V es 0, la MMU lanza un fallo de página, así que V cumple el papel del bit presente. Un kernel con swap sobre RISC-V guardaría el bloque de swap en los bits restantes de una PTE con V = 0. xv6 no tiene swap, pero sí atiende fallos de página: lo vemos al final.

Qué pasa en un fallo de página

Sigamos un acceso a memoria de principio a fin:

  1. La MMU busca la traducción en la TLB; si no está, recorre la tabla de páginas. Si la PTE es válida y presente, todo lo resuelve el hardware.
  2. Si la página es válida pero no presente, la MMU lanza un fallo de página: un trap al kernel.
  3. El kernel busca un marco libre. Si no hay, elige una víctima con la política de reemplazo (y la escribe al swap si está modificada).
  4. El kernel lee la página del swap. Esto toma milisegundos: el proceso se bloquea y la CPU pasa a otro.
  5. Al terminar la E/S, el kernel actualiza la PTE (marco y presente en 1) y la instrucción que falló se reintenta.
Animación: un acceso pasa por la TLB y la tabla de páginas, encuentra la PTE con presente en 0 y salta al kernel, que busca un marco, lee la página del disco mientras el proceso está bloqueado, actualiza la PTE y reintenta; la segunda vez el acceso llega a la RAMAnimación: un acceso pasa por la TLB y la tabla de páginas, encuentra la PTE con presente en 0 y salta al kernel, que busca un marco, lee la página del disco mientras el proceso está bloqueado, actualiza la PTE y reintenta; la segunda vez el acceso llega a la RAM
El camino de un fallo de página. Arriba trabaja el hardware; abajo, el kernel. El acceso al disco es lo único caro.

Si la dirección ni siquiera es válida, no hay nada que traer: el kernel termina al proceso (Segmentation fault). El fallo lo atiende el kernel y no el hardware porque, al lado de los milisegundos del disco, el trap y la lógica en software no cuestan nada, y el kernel sabe dónde está cada bloque y qué conviene expulsar.

Cuánto cuesta un fallo

Sea p la probabilidad de que un acceso cause un fallo de página. El tiempo efectivo de acceso es

T_efectivo = (1 - p) * T_RAM + p * T_fallo

Con T_RAM = 100 ns y T_fallo = 10 ms (un disco duro):

  • Si p = 1/1000: 0.999 * 100 + 0.001 * 10 000 000 ≈ 10 100 ns. La memoria se vuelve 100 veces más lenta.
  • Para perder solo un 10 %: p * 10 000 000 ≤ 10, es decir p ≤ 10^-6. Un fallo cada millón de accesos.

Con un SSD es más barato, pero no tanto: más abajo medimos unos 41 µs de pasada por cada fallo mayor.

Idea clave. El swap solo funciona si los fallos de página son rarísimos. Por eso la política de reemplazo importa tanto: un pequeño cambio en la tasa de fallos es un cambio enorme en el rendimiento.

Marcas de agua y el demonio de swap

Los sistemas reales no esperan a quedarse sin marcos: expulsan por adelantado. Hay dos marcas de agua, una baja (low watermark, LW) y una alta (high watermark, HW). Cuando quedan menos de LW páginas libres, despierta el demonio de swap (swap daemon), un hilo del kernel que expulsa páginas hasta tener HW libres. Como expulsa muchas a la vez, puede agrupar (clustering) las escrituras en pocas operaciones grandes, que el disco atiende mucho mejor. En Linux el demonio es kswapd; en el contenedor del curso, /proc/zoneinfo muestra low 13232 y high 16755 páginas: despierta bajo 52 MB libres y para en 65 MB.

La política: qué página expulsar

La memoria como caché

La RAM es una caché de las páginas que viven en el disco. Una caché se mide por su tasa de aciertos (hits) y de fallos (misses), y el tiempo medio de acceso es

AMAT = T_M + P_fallo * T_D

donde T_M es el tiempo de un acceso a memoria y T_D el de un acceso a disco. Los fallos de una caché se clasifican en las 3 C:

  • Compulsivos (cold-start): la primera vez que se usa una página. Ninguna política los evita.
  • De capacidad: la página estuvo en memoria, pero se expulsó porque no cabía todo.
  • De conflicto: en las cachés de hardware, una dirección solo puede ir a ciertas posiciones. La memoria del sistema operativo es totalmente asociativa: una página puede ir a cualquier marco, así que no hay fallos de conflicto.

Para comparar políticas usaremos una misma secuencia de 12 referencias a páginas y una memoria de 3 marcos:

0 1 0 2 3 0 1 4 0 3 4 0

Hay 5 páginas distintas y la 0 es la más popular. Todo se verificó con paging.c.

OPT: la política óptima

La política óptima (Belady, 1966) expulsa la página que se usará más lejos en el futuro. Los cuatro primeros accesos cargan 0, 1 y 2. Cuando llega 3, los próximos usos son: 0 en la posición 6, 1 en la 7 y 2 nunca. Se expulsa 2. Cuando llega 4: 0 en 9, 1 nunca y 3 en 10. Se expulsa 1.

Resultado: 5 fallos, todos compulsivos: no se puede hacer mejor. Pero OPT necesita conocer el futuro; solo sirve como referencia.

FIFO

FIFO expulsa la página que entró primero; solo necesita una cola. Cuando llega 3, la más antigua es 0, justo la más usada. Al siguiente acceso 0 falla, expulsa a 1, que falla enseguida, y así. Resultado: 9 fallos, 4 de capacidad más que OPT. FIFO no mira cuánto se usa una página, solo cuándo llegó.

RAND

La política aleatoria expulsa una página cualquiera. Su resultado depende de la suerte; en 10 000 corridas:

Fallos 5 6 7 8 9 10 11
Corridas 1066 1493 2391 2721 1657 599 73

Promedio: 7.45 fallos, a veces como OPT y a veces peor que FIFO.

LRU

LRU (least recently used) expulsa la página que se usó hace más tiempo. Se apoya en la localidad: lo que no se usó hace rato probablemente no se use pronto.

Ref. Resultado Expulsa Marcos
0 fallo (frío) 0 - -
1 fallo (frío) 0 1 -
0 acierto 0 1 -
2 fallo (frío) 0 1 2
3 fallo (frío) 1 0 3 2
0 acierto 0 3 2
1 fallo 2 0 3 1
4 fallo (frío) 3 0 4 1
0 acierto 0 4 1
3 fallo 1 0 4 3
4 acierto 0 4 3
0 acierto 0 4 3

Cuando llega 3, LRU expulsa 1 (usada en la posición 2) y salva a 0. Resultado: 7 fallos, mejor que FIFO y que RAND, peor que OPT. ./paging -p all 0 1 0 2 3 0 1 4 0 3 4 0 imprime la comparación completa.

Animación: tres tablas, OPT, FIFO y LRU, se llenan columna a columna con la secuencia 0 1 0 2 3 0 1 4 0 3 4 0 y 3 marcos, marcando fallos fríos, fallos de capacidad y aciertos; terminan con 5, 9 y 7 fallosAnimación: tres tablas, OPT, FIFO y LRU, se llenan columna a columna con la secuencia 0 1 0 2 3 0 1 4 0 3 4 0 y 3 marcos, marcando fallos fríos, fallos de capacidad y aciertos; terminan con 5, 9 y 7 fallos
Las tres políticas sobre la misma secuencia. Los cinco fallos fríos son iguales en todas; la diferencia está en los de capacidad.

Depende de la carga de trabajo

Sin localidad (accesos al azar), todas las políticas realistas dan casi lo mismo. Con una carga 80-20 (el 20 % de las páginas recibe el 80 % de los accesos), LRU gana porque guarda las páginas calientes. Con un ciclo de N+1 páginas y N marcos, LRU y FIFO siempre expulsan la página que viene después: con 0 1 2 3 tres veces y 3 marcos fallan las 12 veces, y RAND solo 7.83 en promedio.

La anomalía de Belady

Con FIFO, más memoria puede dar más fallos. Con 0 1 2 3 0 1 4 0 1 2 3 4:

Marcos FIFO LRU
3 9 10
4 10 8

Con 4 marcos, FIFO acierta en 0 y 1, pero luego 4 expulsa a 0 y empieza una cadena de fallos. LRU y OPT no sufren esta anomalía de Belady porque tienen la propiedad de pila (stack property): lo que está en N marcos también está en N+1. Se verifica con ./paging -p fifo -c 5 ....

Aproximar LRU: el algoritmo del reloj

LRU exacto exige actualizar una marca de tiempo en cada acceso y buscar la mínima entre millones de páginas: demasiado caro. El hardware ofrece algo más barato, un bit de referencia (use bit): la MMU lo pone en 1 al usar la página y solo el OS lo vuelve a 0. En RISC-V es el bit A de la PTE.

El algoritmo del reloj (clock) imagina las páginas en un círculo con una manecilla. Al buscar una víctima:

  • Si la página apuntada tiene el bit en 1, se le da una segunda oportunidad: el bit pasa a 0 y la manecilla avanza.
  • Si tiene el bit en 0, no se usó desde la última vuelta: se expulsa.
Animación: seis páginas, de A a F, en un círculo con su bit de referencia. Falla G: la manecilla pone en 0 los bits de A y B, expulsa a C, que tenía el bit en 0, y G entra en su lugar con el bit en 1Animación: seis páginas, de A a F, en un círculo con su bit de referencia. Falla G: la manecilla pone en 0 los bits de A y B, expulsa a C, que tenía el bit en 0, y G entra en su lugar con el bit en 1
El reloj busca una víctima: cada página con bit 1 recibe una segunda oportunidad; la primera con bit 0 sale.

Con nuestra secuencia, cuando llega 3 los tres marcos tienen el bit en 1: la manecilla da una vuelta completa poniéndolos en 0 y expulsa a 0, igual que FIFO. Pero más adelante, cuando 0 ya tiene su bit en 1 por un acierto reciente, la manecilla lo salta y expulsa a 1. El resultado es 8 fallos: entre FIFO (9) y LRU (7), con solo un bit por página.

Páginas sucias

Expulsar una página modificada obliga a escribirla al disco; una página limpia simplemente se olvida. El hardware marca las páginas modificadas con el bit sucio (dirty bit; en RISC-V, el bit D). El reloj modificado busca primero páginas no usadas y limpias, después no usadas y sucias:

Usada Sucia Al expulsar
0 0 primera opción: gratis
0 1 hay que escribirla al disco
1 0 se usó hace poco
1 1 la peor opción

Las páginas se traen casi siempre por demanda (demand paging), a veces con precarga (prefetching) de la siguiente.

Thrashing y conjunto de trabajo

Si la memoria que los procesos usan activamente no cabe en la RAM, cada acceso expulsa una página que se va a necesitar enseguida. Los procesos pasan la vida esperando al disco, la CPU queda casi ociosa aunque hay mucho trabajo pendiente, y el sistema parece congelado. Es el thrashing.

Denning (1968) propuso medirlo con el conjunto de trabajo (working set): W(t, Δ) son las páginas distintas usadas en las últimas Δ referencias. Con Δ = 4 y nuestra secuencia:

t 1 2 3 4 5 6 7 8 9 10 11 12
Ref. 0 1 0 2 3 0 1 4 0 3 4 0
|W| 1 2 2 3 4 3 4 4 3 4 3 3

El conjunto de trabajo llega a 4 páginas con solo 3 marcos: de ahí salen los fallos de capacidad de FIFO, LRU y el reloj. Según Denning, un proceso solo debería correr si su conjunto de trabajo cabe entero; si no caben todos, hay que sacar procesos completos (control de admisión). Linux, más drástico, tiene el OOM killer: mata a un proceso que usa mucha memoria.

Idea clave. Una política de reemplazo no puede arreglar una memoria demasiado pequeña. Si el conjunto de trabajo no cabe, cualquier política hace thrashing; la única salida es correr menos cosas a la vez o comprar más RAM.

Experimento: presión de memoria en el contenedor

memtouch.c reserva N MB con mmap y los recorre varias veces, escribiendo un byte en cada página. Por cada pasada mide el tiempo y, con getrusage, cuántos fallos menores (se resuelven sin disco: una página nueva en ceros, o una que todavía está en RAM) y fallos mayores (hubo que leer del disco) hubo:

for (int p = 1; p <= passes; p++) {
    getrusage(RUSAGE_SELF, &before);
    double t0 = now_s();
    for (size_t i = 0; i < size; i += page)
        buf[i] = (char)p; // queda sucia
    double dt = now_s() - t0;
    getrusage(RUSAGE_SELF, &after);
    // imprime dt, MB/s, ru_minflt, ru_majflt
}

En un contenedor limitado a 256 MB (Docker agrega por defecto otros 256 MB de swap: --memory-swap, memoria más swap, vale el doble de --memory):

docker run --rm -it --memory=256m -v "$PWD":/work -w /work sistemas-operativos bash
make
./memtouch 200 2
./memtouch 400
PID 13: 200 MB, páginas de 4096 bytes, 51200 páginas
 pasada  segundos      MB/s  f.menores  f.mayores
      1     0.029      6856      51204          1
      2     0.001    209662          0          0
PID 18: 400 MB, páginas de 4096 bytes, 102400 páginas
 pasada  segundos      MB/s  f.menores  f.mayores
      1     0.117      3424     102406          3
      2     1.068       375      76768      25646
      3     1.074       373      76667      25744
      4     1.086       368      76377      26038

Con 200 MB, la primera pasada tiene un fallo menor por página (es el demand zeroing, más abajo) y después ninguno. Con 400 MB, desde la segunda pasada todo es unas 500 veces más lento y mayores más menores suman el número de páginas: cada página falla. Hay más menores que mayores porque Linux, al leer del swap, trae también páginas vecinas (readahead). Es el ciclo que vimos arriba, el peor caso de LRU, ejecutándose de verdad: unos 41 µs de pasada por cada fallo mayor (incluye escribir las víctimas). Mientras tanto, vmstat 1 en otra terminal muestra unos 380 000 KB/s en las columnas si y so (lo que entra desde el swap y sale hacia él).

Si se quita el swap con --memory-swap=256m, el kernel no tiene dónde poner las páginas y el OOM killer mata al proceso: memtouch 400 termina con Killed y código 137 (128 + 9, SIGKILL), y /sys/fs/cgroup/memory.events cuenta oom_kill 1. Con el swap por defecto pasa lo mismo con memtouch 600, que supera los 512 MB de memoria más swap.

Ojo al medir en Docker Desktop: el contenedor corre en una máquina virtual Linux (en nuestras pruebas, 16 GB de RAM y 3 GB de swap) y vmstat y free muestran toda esa máquina, no el límite del contenedor, que está en /sys/fs/cgroup/memory.current. Si free muestra Swap: 0, no habrá swap y verán directamente el OOM killer.

Sistemas reales

VAX/VMS

El VAX-11 (1978) tenía direcciones de 32 bits y páginas de 512 bytes (VPN de 23 bits, offset de 9). Los 2 bits altos eligen el segmento: un híbrido de segmentación y paginación. La mitad baja es del proceso, P0 (código y heap) y P1 (pila); la alta es el sistema S, compartido. Para que las tablas no fueran enormes, hay una por segmento con base y límite (el hueco entre heap y pila no ocupa PTEs), y las de P0 y P1 viven en la memoria virtual del kernel, así que también pueden ir al swap. La página 0 es inválida, para atrapar los punteros NULL.

Un VAX-11/780 en un museo: tres gabinetes grandes de color crema con una franja azul y el rótulo VAX 11/780, junto a un rack con unidades de disco
Un VAX-11/780 de DEC. Esta máquina, del tamaño de varios armarios, fue el hogar de VMS y también de BSD Unix. Foto: Joe Mabel, CC BY-SA 3.0, Wikimedia Commons.

La PTE del VAX no tiene bit de referencia. VMS usó un FIFO segmentado: cada proceso tiene un tope de páginas, su RSS (resident set size), y al pasarlo su página más antigua va a una lista global de segunda oportunidad, de limpias o de sucias. Otros procesos toman marcos de la de limpias, pero si el owner vuelve a pedir la página antes, la recupera sin disco. Con listas grandes se acerca a LRU. Las sucias se escriben agrupadas.

VMS popularizó además dos trucos que hoy usa todo sistema operativo:

  • Demand zeroing: una página nueva no se llena de ceros al pedirla; queda no presente. En el primer acceso hay un fallo y recién ahí se busca un marco y se pone en cero. Si nunca se usa, no costó nada (la primera pasada de memtouch).
  • Copy-on-write (COW): “copiar” una página es mapearla en ambos espacios como solo lectura. Cuando alguien escribe, hay un fallo; el kernel copia la página, le da al que escribió su copia escribible y reintenta. Con fork() seguido de exec() casi nada se copia.
Animación: el padre tiene las páginas a, b y c en los marcos A, B y C con permiso de escritura. Tras fork(), el hijo apunta a los mismos marcos y ambos quedan de solo lectura. El hijo escribe en a y hay un fallo de página; el kernel copia A en un marco nuevo A' y lo mapea en el hijo con permiso de escritura, mientras b y c siguen compartidasAnimación: el padre tiene las páginas a, b y c en los marcos A, B y C con permiso de escritura. Tras fork(), el hijo apunta a los mismos marcos y ambos quedan de solo lectura. El hijo escribe en a y hay un fallo de página; el kernel copia A en un marco nuevo A' y lo mapea en el hijo con permiso de escritura, mientras b y c siguen compartidas
Copy-on-write con fork(): solo se copia la página que alguien escribe, y recién cuando la escribe.

Linux

En Linux el kernel está mapeado en la parte alta de todos los procesos (en x86 de 32 bits, el último GB; en x86-64, la mitad alta de 48 bits). Tiene direcciones lógicas (kmalloc), que son la memoria física con un desplazamiento fijo, contiguas y fuera del swap (sirven para DMA), y direcciones virtuales (vmalloc), páginas sueltas que solo parecen contiguas.

Páginas enormes (huge pages). Una TLB de 64 entradas cubre 256 KB con páginas de 4 KB y 128 MB con páginas de 2 MB. Linux las usa solo, con las transparent huge pages (THP), activadas en el contenedor: con el argumento huge, la primera pasada de memtouch 200 da 102 fallos en vez de 51 202 y es 9 veces más rápida. El costo: fragmentación interna y swap más caro.

Page cache. La RAM que sobra guarda páginas de archivos. Con LRU puro, un cat de un archivo gigante expulsaría todo lo útil; Linux usa una variante de 2Q: la página entra a la lista inactiva y solo sube a la activa si se vuelve a usar. Las víctimas salen de la inactiva, con un algoritmo tipo reloj:

$ grep '(file)' /proc/meminfo
Active(file):     620384 kB
Inactive(file):  4426808 kB

Seguridad. Además de ASLR (semana 5) y KASLR para el kernel, en 2018 se publicó Meltdown: en algunas CPU, la ejecución especulativa permitía leer memoria del kernel desde modo usuario, porque estaba mapeada en cada proceso. La defensa es KPTI (kernel page-table isolation): dos tablas por proceso, y en modo usuario casi nada del kernel está mapeado, a costa de cambiar de tabla en cada trap. La CPU ARM del contenedor no es vulnerable.

En xv6. xv6-riscv siempre funcionó como Linux con KPTI: el kernel tiene su propia tabla de páginas y cada proceso la suya, sin el kernel. La única página mapeada en ambas es trampoline: el código de kernel/trampoline.S cambia el registro satp (la tabla activa) al entrar y al salir de cada trap.

Fallos de página en xv6-riscv

xv6 no tiene swap: si se acaba la memoria, kalloc() retorna 0. Pero atiende fallos de página para reservar memoria de forma perezosa (lazy allocation). En usertrap() (kernel/trap.c), scause da la causa del trap (8 llamada al sistema, 13 fallo al leer, 15 fallo al escribir) y stval la dirección que falló:

  } else if ((r_scause() == 15 || r_scause() == 13) &&
             vmfault(p->pagetable, p->sz, r_stval(),
                     (r_scause() == 13) ? 1 : 0) != 0) {
    // page fault on lazily-allocated page
  } else {
    // ... imprime scause, sepc y stval
    setkilled(p);
  }

Si vmfault() no resuelve el fallo, el proceso muere; un fallo al ejecutar (scause 12) muere directo. La reserva perezosa empieza en sys_sbrk() (kernel/sysproc.c): sbrklazy(n) pasa SBRK_LAZY y solo suma n a p->sz. (sbrk(n) usa SBRK_EAGER y reserva de inmediato, así que el malloc de xv6 no es perezoso.) Al tocar esa memoria, vmfault() en kernel/vm.c hace el resto:

  if (va >= psz)
    return 0;
  va = PGROUNDDOWN(va);
  if (ismapped(pagetable, va)) {
    return 0;
  }
  mem = (uint64)kalloc();
  if (mem == 0)
    return 0;
  memset((void *)mem, 0, PGSIZE);
  if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
    kfree((void *)mem);
    return 0;
  }
  return mem;

Bajo sz y sin mapear: reserva un marco, lo llena de ceros (demand zeroing), lo mapea y la instrucción se reintenta. El argumento read no se usa en este commit, y copyin()/copyout() también llaman a vmfault(), porque el kernel puede tocar memoria perezosa (por ejemplo, en un read()) sin pasar por usertrap.

En xv6. El bono del curso es el lab cow del MIT: fork con copy-on-write. Hoy kfork() (kernel/proc.c) llama a uvmcopy(), que hace kalloc y memmove de cada página del padre. Y una escritura en una página mapeada sin PTE_W llega a vmfault(), que retorna 0 porque la página ya está mapeada: el proceso muere. El lab cambia exactamente esos dos puntos: uvmcopy() comparte los marcos, quita PTE_W y marca las PTE con un bit RSW; y el manejo de scause 15 copia la página al primer intento de escritura. Además hay que contar referencias por marco en kernel/kalloc.c para liberar un marco solo cuando nadie lo usa.

Repaso para el examen parcial

El parcial cubre las semanas 1 a 8: procesos, ejecución directa limitada, planificación, espacio de direcciones, segmentación, paginación, TLB, tablas multinivel y swapping. Abundan los problemas de cálculo, como en los simuladores de OSTEP. Un ejemplo de cada tipo:

  • Planificación. A, B y C llegan en t = 0 y duran 6, 2 y 4. Con FIFO (A, B, C) terminan en 6, 8 y 12: tiempo de retorno promedio 26/3 ≈ 8.67. Con SJF (B, C, A) terminan en 2, 6 y 12: 20/3 ≈ 6.67.
  • Base y límite. Base 32 KB, límite 4 KB. La dirección virtual 1000 es menor que 4096: va a 32 768 + 1000 = 33 768. La 5000 supera el límite: excepción.
  • Paginación. Espacio de 16 KB, páginas de 1 KB: 14 bits, 4 de VPN y 10 de offset. 0x0A4C = 0010 1001001100: VPN 2, offset 0x24C. Si la VPN 2 está en el marco 7, la física es 7 · 1024 + 0x24C = 0x1E4C.
  • TLB. 98 % de aciertos, tabla de 2 niveles, 100 ns por acceso a memoria: 0.98 · 100 + 0.02 · 300 = 104 ns.
  • Reemplazo. Simular a mano OPT, FIFO, LRU y reloj, como en este capítulo.

Estudien con las preguntas de repaso de cada guía y con los simuladores usando semillas nuevas (primero a mano, después -c). Escriban siempre el procedimiento y las unidades.

Resumen

  • El swap usa el disco para dar más memoria de la que hay. Si el bit presente (en RISC-V, V) está en 0, el acceso causa un fallo de página que atiende el kernel. Los fallos cuestan miles de accesos a RAM.
  • El demonio de swap mantiene páginas libres entre las marcas LW y HW y agrupa las escrituras.
  • Con 0 1 0 2 3 0 1 4 0 3 4 0 y 3 marcos: OPT 5 fallos, LRU 7, reloj 8, FIFO 9, RAND 7.45 en promedio. FIFO sufre la anomalía de Belady; LRU y OPT no.
  • El reloj aproxima LRU con un bit por página. Si los conjuntos de trabajo no caben, hay thrashing.
  • VMS: FIFO segmentado, demand zeroing y copy-on-write. Linux: huge pages, page cache con 2Q y KPTI.
  • xv6 no tiene swap, pero atiende fallos (scause 13 y 15) para la reserva perezosa con vmfault().

Ejercicios

  1. Simulen a mano OPT, FIFO y LRU para la secuencia 0 1 2 0 1 3 0 3 1 2 1 con 3 marcos. Clasifiquen cada fallo como compulsivo o de capacidad y verifiquen con ./paging -p opt 0 1 2 0 1 3 0 3 1 2 1 (y lo mismo con fifo y lru).
  2. Simulen el reloj con la misma secuencia del ejercicio 1. ¿En qué referencia se separa de FIFO? Verifiquen con -p clock.
  3. Con T_RAM = 100 ns y T_fallo = 100 µs (un SSD), ¿qué tasa de fallos de página haría que la memoria efectiva fuera el doble de lenta?
  4. Encuentren otra secuencia, distinta de la del capítulo, que muestre la anomalía de Belady con FIFO. Pista: usen ./paging -p fifo -c 5 para probar candidatas. Verifiquen que LRU no la sufre.
  5. Ejecuten memtouch en un contenedor con --memory=128m y tamaños de 64, 120, 140 y 200 MB. ¿Desde qué tamaño aparecen fallos mayores? ¿Por qué no es exactamente 128 MB?
  6. Calculen el conjunto de trabajo W(t, 3) de la secuencia del capítulo. ¿Cuál es su tamaño máximo? ¿Cuántos marcos necesitaría LRU para no tener fallos de capacidad?
  7. En xv6, escriban un programa de usuario que llame a sbrklazy(4096 * 10) y toque solo la primera y la última página. ¿Cuántas veces se llama a vmfault()? Verifíquenlo con un printf temporal en el kernel.