Particiones, buddy y placement

🎯 Al terminar podrás

1. Nombrar los 5 requisitos de la gestión de memoria con un ejemplo de cada uno.
2. Clasificar un desperdicio como fragmentación interna o externa y decir qué esquema la produce.
3. Aplicar first-fit, best-fit y next-fit a una lista de huecos.
4. Simular el buddy system: partir, asignar, liberar y fusionar.
5. Explicar cómo base y límite resuelven a la vez la relocalización y la protección.

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Simulador predice el estado antes de pulsar el paso siguiente
• Laboratorio sube la escalera: resuelto → completa → solo → variante

Requisitos de la gestión de memoria (Stallings cap. 7)

💡 En simple: el problema

La RAM es como un estacionamiento y los procesos son autos que llegan y se van. El SO es el encargado del estacionamiento y tiene que resolver:

• dónde estaciona cada auto (y que pueda volver a otro lugar mañana: relocalización);
• que ningún auto choque al de al lado (protección);
• que dos autos puedan compartir algo, como un remolque, sin romper lo anterior (compartición);
• que el auto venga por partes con reglas distintas (cabina, maletero) (organización lógica);
• que, si no caben todos, algunos esperen en la calle (el disco) y entren cuando haya sitio (organización física).

Requisito	Por qué
Relocalización	El programador no sabe dónde quedará su programa, y al hacer swap puede volver a otra dirección.
Protección	Las referencias a memoria deben revisarse en tiempo de ejecución, porque la ubicación es impredecible. Los mecanismos de relocalización también dan protección.
Compartición	Permitir que varios procesos usen la misma copia del código sin romper la protección.
Organización lógica	Los programas son módulos con distintos permisos (solo lectura, solo ejecución), compilados por separado.
Organización física	Jerarquía de dos niveles (principal y secundaria). El SO debe mover los datos porque el overlaying es costoso de programar y el programador no sabe cuánta memoria habrá.

Particionamiento (sin memoria virtual)

Particiones fijas

💡 En simple: casilleros de tamaño fijo

Imagina casilleros de un gimnasio, ya construidos. Si tu mochila es chica y te toca un casillero grande, el espacio sobrante no lo puede usar nadie.

Ejemplo trivial: partición de 8 MB, proceso de 3 MB → se pierden 5 MB dentro de la partición. Eso es la fragmentación interna (el desperdicio queda dentro de lo asignado).

Y si hay 7 casilleros, como mucho hay 7 procesos a la vez, aunque sean diminutos.

• De igual tamaño: da igual cuál usar. Si todas están ocupadas por procesos no listos, se hace swap out.
• De distinto tamaño: se asigna la partición más pequeña que alcance, con una cola por partición o una cola única.
• ✘ El número de particiones limita el grado de multiprogramación. ✘ Los trabajos pequeños desperdician espacio: fragmentación interna. ✘ Un programa demasiado grande necesita overlays.

Particiones fijas: detalles

• Por ejemplo, 64 MB con 8 MB para el SO y 7 particiones de 8 MB (iguales), o particiones de 2, 4, 6, 8, 8, 12 y 16 MB (desiguales).
• Una cola por partición: cada proceso va a la partición más chica en que cabe. Es óptimo para esa partición, pero la de 16 MB puede quedar vacía mientras procesos chicos esperan en otra cola.
• Una cola única: se usa la partición libre más chica que alcance. Aprovecha mejor el sistema.
• IBM OS/MFT (Multiprogramming with a Fixed number of Tasks). Hoy está prácticamente en desuso.

Particiones dinámicas (OS/MVT de IBM)

💡 En simple: estacionamiento sin líneas pintadas

Ahora no hay casilleros: cada auto ocupa exactamente lo que mide. No se desperdicia nada al entrar… pero cuando los autos se van, quedan huecos de tamaños raros entre los que siguen estacionados.

Ejemplo trivial: quedan dos huecos libres, uno de 4 MB y otro de 6 MB. Llega un proceso de 8 MB. En total hay 10 MB libres, pero no cabe, porque ningún hueco por sí solo mide 8. Eso es la fragmentación externa (el desperdicio está fuera, entre los procesos).

La compactación es pedir a todos los autos que se corran hacia un lado para juntar los huecos. Funciona, pero mientras tanto nadie trabaja (cuesta CPU).

• Cada proceso recibe exactamente lo que pide.
• Con el tiempo aparecen huecos pequeños entre procesos: fragmentación externa.
• Paso a paso (fig. 7.4), con 56 MB libres: entra P1 (20 MB) y quedan 36; entra P2 (14) y quedan 22; entra P3 (18) y queda un hueco de 4. Todos quedan bloqueados, así que se hace swap out de P2 (se liberan 14). Entra P4 (8) y queda un hueco de 6. La memoria termina salpicada de huecos inútiles (4 MB, 6 MB): fragmentación externa.
• Algoritmo de reemplazo: si todos los procesos en memoria están bloqueados y no hay espacio ni compactando, ¿a quién se saca? El tema continúa en memoria virtual.
• Compactación: mover los procesos para juntar el espacio libre. Solo es posible con relocalización dinámica (en tiempo de ejecución) y cuesta CPU. Durante la E/S hay que fijar el proceso en memoria o hacer E/S solo a buffers del SO.

Interna vs externa

• Interna: el espacio se desperdicia dentro del bloque asignado (el bloque es más grande que lo pedido). Ocurre en particiones fijas, buddy y paginación (última página).
• Externa: hay memoria libre total suficiente, pero no contigua. Ocurre en particiones dinámicas y segmentación.

Algoritmos de placement

💡 En simple: ¿en qué hueco lo pongo?

Hay varios huecos libres y llega un proceso. Ejemplo trivial: huecos, en orden desde el inicio de la memoria, de 5, 12 y 8 MB. Llega un proceso de 7 MB.

• First-fit (el primero que sirva): el de 5 no alcanza, así que usa el de 12 y sobra un hueco de 5.
• Best-fit (el más justo): usa el de 8 y sobra un hueco de 1 MB, una «astilla» que casi nunca le sirve a nadie. Por eso best-fit suele ser peor de lo que su nombre promete.
• Next-fit (el primero que sirva, pero empezando desde donde quedó la última vez): depende de dónde quedó el puntero.

Algoritmo	Elige	Comentario
Best-fit	el hueco más ajustado	deja astillas diminutas e inútiles; en la práctica suele ser el peor
First-fit	el primero desde el inicio que alcance	simple, rápido y generalmente el mejor
Next-fit	el primero desde la última asignación	tiende a romper el bloque grande del final

Regla del 50 % (análisis de first-fit): con N bloques asignados se pierden ≈ 0.5 N por fragmentación, es decir, un tercio de la memoria puede quedar inutilizable.

Algoritmos de placement (particiones dinámicas)

Cada marcador muestra el hueco que elegiría cada algoritmo. Asigna varias veces y mira cómo crece la fragmentación externa. Haz clic en un proceso para liberarlo; los huecos adyacentes se combinan.

Solicitud: 16 MB

OS8

8

P16

12

P24

22

P32

18

P44

8

P56

6

P64

14

P710

36

First-fitBest-fitNext-fitWorst-fit

Asignar con First-fitAsignar con Best-fitAsignar con Next-fitAsignar con Worst-fitReiniciar

Memoria libre total124 MB

Hueco más grande36 MB

Huecos8

Peldaño 1 · Resueltolee cada paso y su porqué

Resuelto: huecos de 5, 12 y 8 MB; llega un proceso de 7 MB

Es el ejemplo del recuadro «En simple» de arriba. First-fit usa el de 12 y deja 5. Best-fit usa el de 8 y deja una astilla de 1. Next-fit depende de dónde quedó el puntero.

Peldaño 3 · Solosin ayuda; luego compara

Solo: huecos (en orden) de 10, 4, 20, 18, 7, 9, 12 y 15 KB; llegan, en orden, pedidos de 12, 10 y 9 KB

¿Dónde va cada pedido con first-fit, best-fit y next-fit? (Next-fit empieza al inicio de la memoria.)

Comparar

Pedido	First-fit	Best-fit	Next-fit
12	20 (quedan 8)	12 (exacto)	20 (quedan 8)
10	10	10	18: el puntero sigue desde el hueco de 20, donde quedan 8
9	18	9	9

Best-fit da tres ajustes exactos y next-fit «se come» los huecos grandes del medio. Es la tabla clásica de Silberschatz: con otra secuencia de pedidos, el ranking puede cambiar.

Buddy system

💡 En simple: partir una barra de chocolate

Tienes una barra de chocolate y solo puedes partirla por la mitad, y cada mitad otra vez por la mitad. Das a cada persona el trozo más chico que le alcance. Cuando dos mitades «hermanas» (buddies) quedan libres, se vuelven a pegar.

Ejemplo trivial: memoria de 64 KB y alguien pide 10 KB.

1. 64 es demasiado grande → se parte en dos de 32.
2. 32 sigue siendo grande → uno de los 32 se parte en dos de 16.
3. 16 alcanza (la mitad, 8, ya no alcanza) → se entrega un bloque de 16 KB.

Se pierden 16 − 10 = 6 KB dentro del bloque (fragmentación interna), pero liberar y juntar bloques es muy rápido.

Es un compromiso entre particiones fijas y dinámicas. Los bloques tienen tamaño $2^K$ con $L \le K \le U$: $2^L$ es el bloque mínimo y $2^U$ es toda la memoria.

1. Al inicio hay un único bloque de $2^U$.
2. Para una solicitud $s$ con $2^{U-1} < s \le 2^U$ se asigna el bloque completo.
3. Si no, se divide en dos buddies de $2^{U-1}$, y así sucesivamente hasta obtener el menor bloque $\ge s$.
4. Se mantiene una lista de huecos por cada tamaño $2^i$.
5. Al liberar, si el buddy también está libre, se fusionan en un bloque de $2^{i+1}$, y eso se repite hacia arriba.

En el árbol binario, si dos buddies son hojas, al menos uno está asignado; si no, ya se habrían fusionado. Linux usa buddy para asignar páginas físicas (__get_free_pages).

Buddy system (1 MiB)

Bloques de tamaño 2^k. Pedir: redondear a potencia de 2 y dividir a la mitad hasta ajustar. Liberar: fusionar con el buddy mientras esté libre. Empieza con la secuencia de la diapositiva 19.

1024K

Asignado0K

Frag. interna0K

Bloques libres1024K

Pedir A = 100KDeshacerReiniciar

NombreTamaño: 90KPedir

Peldaño 2 · Complétalofaltan pasos clave: llénalos tú

Complétalo: el ejemplo de Stallings (fig. 7.6) con 1 MB

Ya se asignaron A = 100K (recibe un bloque de 128K en 0) y B = 240K (recibe 256K en 256K). Quedan libres 128K en 128K y 512K en 512K. Completa: ¿dónde van C = 64K y D = 256K?

Comparar

• C = 64K: el menor bloque libre que alcanza es el de 128K en 128K. Se parte en dos de 64K: C va en 128K y queda libre el de 64K en 192K.
• D = 256K: el único bloque que alcanza es el de 512K. Se parte en dos: D va en 512K y queda libre el de 256K en 768K.
• Mapa: A 128 | C 64 | libre 64 | B 256 | D 256 | libre 256.

Peldaño 3 · Solosin ayuda; luego compara

Solo: sigue el mismo ejemplo. Libera B, libera A y pide E = 75K

Comparar

• Libera B (256K en 256K): su buddy es el bloque de 256K en 0, que no está libre (tiene A y C), así que no se fusiona.
• Libera A (128K en 0): su buddy es el de 128K en 128K, que está partido (C está ahí), así que no se fusiona.
• E = 75K necesita 128K: usa el de 0.
• Mapa: E 128 | C 64 | libre 64 | libre 256 | D 256 | libre 256. Es el mismo que en la fig. 7.6.

Peldaño 4 · Variantecambia una condición: ¿sigue valiendo lo anterior?

Variante: ahora libera C, después E y después D. ¿Cuántas fusiones hay en cada paso?

Comparar

• C: se fusiona con su buddy de 64K en 192K y forma 128K en 128K. Su buddy (E, en 0) está ocupado: 1 fusión.
• E: con 128K en 128K forma 256K en 0, y con el 256K libre en 256K forma 512K en 0: 2 fusiones.
• D: con 256K en 768K forma 512K en 512K, y con 512K en 0 vuelve a ser 1 MB: 2 fusiones.

Para encontrar el buddy de un bloque se calcula inicio XOR tamaño. Por ejemplo, 512K XOR 512K = 0.

Relocalización (diapositiva «Important about relocation»)

💡 En simple: «tercera puerta desde la entrada»

El programa no sabe en qué parte de la RAM va a quedar. Por eso sus direcciones son relativas, como decir «tercera puerta desde la entrada del pasillo», y no «puerta 5203».

Ejemplo trivial: el proceso quedó en la partición que empieza en 5000 (registro base = 5000, y mide 1000, así que el límite es 1000).

• El programa pide la dirección 200 → 200 es menor que el límite, así que se accede a 5000 + 200 = 5200.
• Pide la 1500 → 1500 supera el límite → error: intenta salirse de su partición.
• Si mañana el SO lo mueve a la partición que empieza en 9000, la misma dirección 200 apunta a 9200. El programa no cambió nada: solo cambió la base.

1. Particiones fijas con una cola por partición: el proceso vuelve siempre a la misma partición, así que basta un cargador relocalizador simple que reemplaza las referencias relativas por absolutas al cargar.
2. Particiones iguales, o desiguales con cola única, y particiones dinámicas: un proceso puede volver a otra partición tras un swap, así que las direcciones no pueden fijarse al cargar.
3. Con compactación, los procesos se mueven mientras están en memoria, así que las referencias cambian cada vez.

En los casos 2 y 3 hace falta traducir en tiempo de ejecución:

Tipo de dirección	Qué es
Lógica	referencia independiente de la ubicación; hay que traducirla
Relativa	caso particular de la lógica: el desplazamiento desde un punto conocido (el inicio del programa)
Física o absoluta	la ubicación real en la RAM

Hardware (fig. 7.8): al pasar a Running se cargan los registros base y límite (bounds). Cada dirección relativa se suma a la base y la dirección absoluta se compara con el límite; si se pasa, hay una interrupción al SO. Esto resuelve relocalización (mover un proceso es solo cambiar la base) y protección a la vez, con el costo mínimo de hacerlo en hardware.

De programa a proceso: carga y enlace (apéndice 7A)

💡 En simple: armar un mueble

• Compilar es fabricar cada pieza (cada .c produce un .o).
• Enlazar es atornillar las piezas entre sí: tu main llama a printf, y el enlazador conecta esa llamada con donde de verdad está printf.
• Cargar es llevar el mueble armado a la casa y ponerlo en un lugar concreto de la RAM.

La pregunta de fondo es cuándo se decide la dirección real: si se decide temprano (al compilar), el programa solo puede ir en un lugar; si se decide tarde (al ejecutar, con base y límite), se puede mover cuando haga falta.

Carga (loading):

• Absoluta: siempre en la misma dirección, y las direcciones se resuelven al compilar. No se puede mover.
• Relocalizable: las direcciones son relativas al inicio del módulo; el cargador suma la base x usando un diccionario de relocalización que dice qué referencias ajustar. Ejemplo: «saltar a 1424» cargado en 1024 se convierte en 2448.
• Dinámica en ejecución: la dirección absoluta se calcula al ejecutar cada instrucción (con base y límite). Permite mover y hacer swap del proceso libremente.

Enlace (linking): el linker une módulos objeto en un módulo de carga, resolviendo las referencias externas. Si A mide L y hace CALL B, eso se convierte en JSR "L"; si B hace CALL C, en JSR "L+M".

• Linkage editor: produce un módulo de carga relocalizable completo.
• Enlace dinámico en la carga (load-time): las referencias a bibliotecas se resuelven al cargar.
• Enlace dinámico en ejecución (run-time): se resuelve cuando se ejecuta la llamada, y los módulos se comparten entre procesos (las DLL de Windows y las .so de Linux).
  • ✔ Se puede actualizar una biblioteca sin reenlazar las aplicaciones, se comparte código automáticamente y terceros pueden extender el sistema.
  • ✘ DLL hell: dos aplicaciones necesitan versiones distintas de la misma DLL.
  • Junto con la segmentación, permite no reservar memoria para módulos que nunca se usan en una ejecución (por ejemplo, en un sistema de reservas).

⚠️ Errores que cuestan puntos

• Llamar «interna» a los huecos entre procesos.Los huecos entre procesos son fragmentación externa. La interna es el sobrante dentro del bloque asignado.
• Creer que best-fit es el mejor por su nombre.Deja astillas diminutas. En la práctica, first-fit suele ganar.
• Decir que en buddy se asigna exactamente lo pedido.Se asigna la menor potencia de 2 ≥ lo pedido: 100K recibe 128K.
• Afirmar que la compactación sirve con cualquier tipo de carga.Necesita relocalización dinámica (en ejecución), porque los procesos se mueven mientras están en memoria.

Autoevaluación

0/5 correctas · 0 respondidas Reiniciar

1. Buddy system con 1 MiB. Se pide 100 KiB. ¿Qué bloque se asigna y cuánta fragmentación interna genera?

a) 100 KiB, 0b) 128 KiB, 28 KiBc) 256 KiB, 156 KiBd) 64 KiB, 0

2. Hay 30 MB libres en huecos de 10 MB y llega un proceso de 25 MB que no cabe. Eso es…

a) Fragmentación internab) Fragmentación externac) Thrashingd) Overlaying

3. ¿Qué algoritmo de placement tiende a dejar huecos diminutos inutilizables?

a) First-fitb) Best-fitc) Next-fitd) Ninguno

4. La compactación requiere…

a) Particiones fijasb) Relocalización dinámica (en tiempo de ejecución)c) Buddy systemd) Un TLB

5. En buddy, el buddy del bloque de 64K que empieza en 128K es…

a) el de 64K en 192Kb) el de 64K en 64Kc) el de 128K en 0d) el de 64K en 0

🗣️ Explícalo tú (Feynman)

Explica con un ejemplo de números por qué las particiones fijas tienen fragmentación interna y las dinámicas externa, y cómo el buddy system queda en el medio.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

• Fijas: el bloque viene predefinido, así que lo que sobra del bloque se pierde dentro (8 MB para un proceso de 3 MB pierde 5).
• Dinámicas: se da exactamente lo pedido, pero al salir procesos quedan huecos entre ellos (4 + 6 MB libres no sirven para 8 MB).
• Buddy: los bloques son potencias de 2, así que hay algo de interna, pero liberar y fusionar con el buddy es rápido y limita la externa.
• La compactación arregla la externa, pero cuesta CPU y exige relocalización dinámica.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·for_partial/pending_themes/Sem06_06-OST-Memory.pdf (diap. 4–23) · sem_6/resumen-capitulo-7-memory-management.md · Stallings cap. 7