Esercizio - Allocazione contigua con first fit, best fit, worst fit e next fit (eserciziario, esercizi 35, 36, 54, 55, 102 e 115)

---

Come si ragiona

Ogni istante in cui succede qualcosa si fa in due passi: prima terminano i processi (la loro area si libera e si fonde con le aree libere vicine), poi si prova a caricare i processi arrivati. L'elenco delle aree libere va tenuto in ordine di indirizzo.

• first fit: la prima area (per indirizzo) abbastanza grande;
• best fit: la più piccola abbastanza grande (resto minimo);
• worst fit: la più grande (resto massimo);
• next fit: come first fit ma si riparte dall'ultima area usata.

Un processo va nella parte iniziale dell'area scelta: l'area si riduce dal basso.

Esercizio 35 (first fit)

Memoria $0\ldots4095$. Gli intervalli sono indirizzi di byte.

Punti da notare:

• a $t=4$, alla terminazione di $P_1$, sono libere due aree (2000 e 586 byte);
• a $t=6$, $P_4$ (580 byte) va nella prima delle due, perché entrambe bastano;
• a $t=7$, $P_5$ (1500 byte) non entra: la memoria libera totale è $1420+586=2006\ge1500$, ma è divisa in due buchi, nessuno dei quali basta: è frammentazione esterna. $P_5$ aspetta. A $t=8$ i buchi sono 1420 e 1086 byte, ancora insufficienti; entra a $t=9$, quando $P_2$ termina e i buchi si fondono in uno solo (la soluzione del corso si ferma a $t=7$: il resto è la continuazione dello stesso procedimento).

Esercizio 36 (worst fit)

Stato a $t=13$: $P_3$ (0-1999), $P_2$ (2048-4017), $P_4$ (4018-4047) occupati.

• Frammentazione esterna: la memoria libera è $48+48=96$ byte in due buchi da 48. Un processo che chiedesse da 49 a 96 byte non potrebbe essere caricato, pur essendoci abbastanza memoria in totale.
• Frammentazione interna: nessuna, perché a ogni processo si assegna esattamente lo spazio che richiede (partizioni variabili).

Esercizio 54 (best fit, celle da 16 bit)

La memoria è di $4\text{ KB}=4096$ byte; con celle da 2 byte sono $4096/2=2048$ celle, numerate $0\ldots2047$. Si convertono i processi in celle (arrotondando per eccesso):

Errore nella soluzione del corso. La soluzione riporta che $P_2$ occupa le celle da 1024 a 1549, e di conseguenza $P_3$ da 1550 a 1799 e $P_4$ da 1800 a 1949. Ma $P_2$ occupa 525 celle: da 1024 a $1024+525-1=\mathbf{1548}$. Tutti gli intervalli successivi sono quindi spostati di uno (una nota sulla slide corregge 1549 in 1548). Il resto del ragionamento (best fit sceglie $L_1$ sia a $t=11$ sia a $t=13$) è corretto.

Esercizio 55

La dimensione massima di un processo che può partire è quella della zona libera più grande.

• A $t=10$: le aree libere sono $L_2$ (celle 0-1023, cioè 1024 celle $=2$ KB) e $L_1$ (499 celle): il massimo è 2 KB.
• A $t=13$: la zona più grande è ancora $L_2$ (1024 celle): 2 KB. Lo scontro tra $P_3$ e $P_4$ ha consumato solo $L_1$.

Esercizio 102 (next fit)

Aree: 8, 4, 14, 18, 17, 9, 12, 15 KB.

1. Carico 12 KB. Si parte dall'inizio: 8 non basta, 4 no, 14 sì: si usa l'area da 14 (resto 2 KB).
2. Poi 3 KB con next fit: si riparte dall'ultima area usata, cioè dal resto di 2 KB (non basta), poi 18: 18 KB.

Risposta: l'area da 18 KB. Per confronto: first fit avrebbe scelto 8 KB (il primo che basta), best fit 4 KB, worst fit 18 KB (o la più grande rimasta).

Esercizio 115 (best fit e worst fit)

Aree: $[8, 15, 3, 11, 5, 7, 20, 25]$.

Verifica del worst fit a 13 KB: dopo le prime due richieste le aree sono 8, 15, 3, 11, 5, 7, 16, 14: la più grande è 16, e basta per 13. Il worst fit ha lasciato 3 KB nell'area da 16 e ha consumato in tutto 3 grandi aree.

---

Errori tipici

• Dimenticare che a un istante prima terminano i processi e poi arrivano i nuovi (è la regola che dà l'ordine giusto).
• Non fondere le aree libere adiacenti dopo una terminazione.
• Dire che c'è frammentazione interna con partizioni variabili: c'è solo quella esterna.
• Convertire male celle e byte (con celle da 16 bit un'area da 4 KB ha 2048 celle) o dimenticare l'arrotondamento per eccesso.
• Scrivere come fine di un intervallo $\text{inizio}+\text{dimensione}$ invece di $\text{inizio}+\text{dimensione}-1$.