Salta al contenuto
Note per Studenti Esercizio - Buddy system per la memoria del kernel (slide di memoria virtuale)

Esercizio - Buddy system per la memoria del kernel (slide di memoria virtuale)

In questa pagina 5

Testo.

  1. (Slide.) Il kernel dispone di un segmento di 256 KB gestito con il buddy system e chiede 21 KB: come viene diviso il segmento e quanto spazio si spreca?
  2. Segmento da 256 KB, tutto libero. Arrivano nell'ordine le richieste A=21A=21 KB, B=35B=35 KB, C=14C=14 KB, D=70D=70 KB. Mostrare i blocchi assegnati, la frammentazione interna totale, e le fusioni quando si liberano nell'ordine AA, CC, BB, DD.
  3. Cosa cambia con la slab allocation?

Teoria: Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine →.

Il buddy system

Il segmento è formato da pagine fisicamente contigue. Ogni richiesta è arrotondata alla potenza di 2 superiore. Se il blocco libero più piccolo che basta è più grande del necessario, lo si divide in due compagni (buddies) di dimensione metà, e si ripete fino alla dimensione giusta; un compagno si usa, l'altro resta libero. Quando un blocco viene liberato e anche il suo compagno è libero, i due si fondono in un blocco doppio, e si ripete.

Il compagno di un blocco di dimensione ss che parte all'indirizzo aa (multiplo di ss) è il blocco che parte da a⊕sa\oplus s (cioè a+sa+s se a/sa/s è pari, a−sa-s se è dispari).

Parte 1: 21 KB su 256 KB

21→3221\to32 KB (potenza di 2 superiore). Si divide:

256→128+128,128→64+64,64→32+32.256\to128+128,\qquad128\to64+64,\qquad64\to32+32.

Un blocco da 32 KB serve la richiesta; restano liberi un blocco da 32 KB, uno da 64 KB e uno da 128 KB. Lo spreco (frammentazione interna) è 32−21=1132-21=11 KB.

Parte 2: quattro richieste

Rappresentiamo la memoria come un segmento [0,256)[0,256) in KB.

passo richiesta blocco richiesto operazione blocchi liberi dopo
0 [0,256)[0,256) (256)
1 A=21A=21 32 divisioni fino a 32: AA in [0,32)[0,32) [32,64)[32,64), [64,128)[64,128), [128,256)[128,256)
2 B=35B=35 64 si usa il blocco libero da 64: BB in [64,128)[64,128) [32,64)[32,64), [128,256)[128,256)
3 C=14C=14 16 si divide il 32 libero: [32,48)+[48,64)[32,48)+[48,64); CC in [32,48)[32,48) [48,64)[48,64), [128,256)[128,256)
4 D=70D=70 128 si usa il blocco libero da 128: DD in [128,256)[128,256) [48,64)[48,64) (16)

Frammentazione interna. AA: 32−21=1132-21=11; BB: 64−35=2964-35=29; CC: 16−14=216-14=2; DD: 128−70=58128-70=58. Totale: 11+29+2+58=10011+29+2+58=100 KB sprecati su 240 KB assegnati (41,7%41{,}7\%). Rimangono liberi 16 KB nel blocco [48,64)[48,64), ma una nuova richiesta da 17 KB o più non sarebbe soddisfatta.

Liberazioni (ordine AA, CC, BB, DD):

  1. Si libera AA [0,32)[0,32): il suo compagno [32,64)[32,64) è diviso (contiene CC): niente fusione. Liberi: [0,32)[0,32), [48,64)[48,64).
  2. Si libera CC [32,48)[32,48): il compagno [48,64)[48,64) è libero: si fondono in [32,64)[32,64) (32 KB); il compagno di questo è [0,32)[0,32), libero: si fondono in [0,64)[0,64) (64 KB); il compagno di [0,64)[0,64) è [64,128)[64,128) (BB, occupato): si ferma. Libero: [0,64)[0,64).
  3. Si libera BB [64,128)[64,128): il compagno [0,64)[0,64) è libero: fusione in [0,128)[0,128); il compagno di questo, [128,256)[128,256), è DD (occupato): si ferma. Libero: [0,128)[0,128).
  4. Si libera DD [128,256)[128,256): il compagno [0,128)[0,128) è libero: fusione in [0,256)[0,256). La memoria è di nuovo un unico blocco da 256 KB.

La fusione è veloce perché basta controllare il compagno (indirizzo a⊕sa\oplus s); lo svantaggio è la frammentazione interna dovuta all'arrotondamento.

Parte 3: slab

Con la slab allocation una slab è una o più pagine contigue; ogni cache contiene una o più slab per una struttura dati del kernel ed è riempita di oggetti di quella struttura, all'inizio tutti marcati liberi. Un'allocazione prende un oggetto libero (lo marca usato); se la slab è piena si passa a una vuota, e se non ce n'è si crea una nuova slab. Poiché ogni cache è fatta di oggetti della dimensione esatta della struttura, non c'è frammentazione dovuta all'arrotondamento a potenze di 2 e le richieste sono servite rapidamente, senza dividere e fondere blocchi.

Errori tipici

  • Dimenticare di arrotondare alla potenza di 2 superiore (21 KB →\to 32 KB, non 16 né 21).
  • Fondere due blocchi vicini che non sono compagni (per esempio [32,64)[32,64) con [64,128)[64,128)): la fusione vale solo per i compagni, che hanno la stessa dimensione e provengono dalla stessa divisione.
  • Fermarsi alla prima fusione senza controllare il compagno del blocco risultante.
  • Contare come spreco anche la memoria libera: la frammentazione interna è solo la differenza fra blocco assegnato e richiesta.

Versione ripasso

Regole. Richiesta arrotondata alla potenza di 2 superiore; si divide un blocco libero in due compagni di metà dimensione finché serve; al rilascio, se il compagno (indirizzo a⊕sa\oplus s) è libero ci si fonde, e si ripete.

1. 21 KB →32\to32 KB: 256→128+128→64+64→32+32256\to128+128\to64+64\to32+32; restano liberi 32, 64, 128; spreco 32−21=1132-21=11 KB.

2. A=21→32A=21\to32 in [0,32)[0,32); B=35→64B=35\to64 in [64,128)[64,128); C=14→16C=14\to16 in [32,48)[32,48) (si divide il 32 in 16+16); D=70→128D=70\to128 in [128,256)[128,256). Interna: 11+29+2+58=10011+29+2+58=100 KB (su 240 assegnati); restano liberi 16 KB in [48,64)[48,64). Liberazioni: AA (compagno [32,64)[32,64) diviso: nessuna fusione); CC (si fonde con [48,64)[48,64), poi con [0,32)[0,32), poi si ferma davanti a BB): libero [0,64)[0,64); BB →\to libero [0,128)[0,128); DD →\to libero [0,256)[0,256).

3. Slab. Cache per ogni struttura del kernel, riempita di oggetti della misura esatta (liberi o usati); se la slab è piena si usa una vuota o se ne crea una; niente arrotondamenti a potenze di 2, richieste rapide.

Errori tipici: niente arrotondamento; fusione tra blocchi non compagni; fermarsi alla prima fusione; spreco contato sulla memoria libera.

Teoria: Memoria virtuale - paginazione su richiesta e sostituzione delle pagineLa memoria virtuale separa la memoria logica da quella fisica: basta che alcune pagine siano in RAM; con la paginazione su richiesta (demand paging) una pagina si carica solo al primo riferimento, e un riferimento a una pagina non residente (bit di validità = i) genera un page fault gestito dal sistema operativo in sei passi; EAT = (1 - p) * accesso + p * servizio del fault, con p minuscolo; copy-on-write rende economica la fork; se non ci sono frame liberi si sceglie una vittima con FIFO (anomalia di Belady), OPT (ottimo, irrealizzabile), LRU (algoritmo a stack), second chance (bit di riferimento, orologio) o la versione con bit di modifica; i frame si assegnano in modo uguale o proporzionale, con sostituzione globale o locale; se un processo non ha abbastanza frame va in thrashing; il modello del working set e la frequenza dei page fault lo evitano; considerazioni su prepaging, dimensione della pagina, TLB reach e struttura dei programmi; memoria del kernel con buddy system e slab.Memoria virtuale - paginazione su richiesta e sostituzione delle pagine →.

Teoria collegata