Salta al contenuto
Note per Studenti Esercizio - Segmentazione e traduzione degli indirizzi (eserciziario, esercizi 49, 78 e 90)

Esercizio - Segmentazione e traduzione degli indirizzi (eserciziario, esercizi 49, 78 e 90)

In questa pagina 5

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD).

  • Esercizio 90. Tabella dei segmenti: segmento 0 base 219 lunghezza 600; segmento 1 base 2300 lunghezza 14; segmento 2 base 90 lunghezza 100; segmento 3 base 1327 lunghezza 580; segmento 4 base 1952 lunghezza 96. Indirizzi fisici corrispondenti ai logici ⟨0,430⟩\langle0,430\rangle, ⟨1,10⟩\langle1,10\rangle, ⟨2,500⟩\langle2,500\rangle, ⟨3,400⟩\langle3,400\rangle, ⟨4,112⟩\langle4,112\rangle.
  • Esercizio 78. Memoria virtuale con segmentazione, parola da un byte, indirizzi logici di 10 bit di cui i 4 più significativi indicano il segmento. (a) Dimensione massima di un segmento? (b) Quanti segmenti al massimo per un processo? Il processo ha 5 segmenti S0…S4S_0\ldots S_4 con tabella: S0S_0 (lunghezza 10, base 200), S1S_1 (20, 100), S2S_2 (6, 252), S3S_3 (32, 720), S4S_4 (32, 683). Tradurre gli indirizzi logici 9, 132, 79, 64, 259, 135, 320.
  • Esercizio 49. Data l'allocazione in memoria dei segmenti 0-4 (figura dell'eserciziario), determinare gli indirizzi fisici degli indirizzi virtuali ⟨0,1984⟩\langle0,1984\rangle, ⟨1,18⟩\langle1,18\rangle, ⟨2,250⟩\langle2,250\rangle, ⟨3,1400⟩\langle3,1400\rangle, ⟨4,112⟩\langle4,112\rangle.

Teoria: Memoria centrale - allocazione contigua, paginazione e segmentazioneUn programma deve stare in memoria centrale per girare; la MMU traduce a ogni accesso l'indirizzo logico (virtuale) in indirizzo fisico, sommando un registro di rilocazione e controllando il limite; con l'allocazione contigua (partizioni fisse o variabili, first/best/worst fit) si hanno frammentazione interna ed esterna e serve la compattazione; la paginazione divide memoria logica in pagine e memoria fisica in frame della stessa dimensione (potenza di 2), elimina la frammentazione esterna, traduce (p, d) con la tabella delle pagine (PTBR, PTLR) e riduce il costo dei due accessi con il TLB (EAT = h * t + (1 - h) * 2t); le tabelle grandi si dividono in gerarchiche, hash o invertite; lo swapping sposta intere pagine o processi su disco; la segmentazione usa blocchi di lunghezza variabile con coppia (base, limite), eventualmente paginati; Intel IA-32 usa segmentazione con paginazione a due livelli (10+10+12 bit) e IA-64 quattro livelli su 48 bit.Memoria centrale - allocazione contigua, paginazione e segmentazione →.

Il metodo

L'indirizzo logico è la coppia ⟨s,d⟩\langle s,d\rangle (segmento, scostamento). Per ognuno:

  1. si cerca la riga ss della tabella (base BsB_s, lunghezza LsL_s); se il segmento non esiste, l'indirizzo non è valido;
  2. si controlla d<Lsd<L_s: se d≥Lsd\ge L_s c'è un errore di segmentazione (trap);
  3. se è valido, l'indirizzo fisico è Bs+dB_s+d.

A differenza della paginazione il limite del controllo cambia a ogni segmento.

Esercizio 90

logico base lunghezza controllo fisico
⟨0,430⟩\langle0,430\rangle 219 600 430<600430<600 valido 219+430=649219+430=\mathbf{649}
⟨1,10⟩\langle1,10\rangle 2300 14 10<1410<14 valido 2300+10=23102300+10=\mathbf{2310}
⟨2,500⟩\langle2,500\rangle 90 100 500≥100500\ge100 illegale (trap)
⟨3,400⟩\langle3,400\rangle 1327 580 400<580400<580 valido 1327+400=17271327+400=\mathbf{1727}
⟨4,112⟩\langle4,112\rangle 1952 96 112≥96112\ge96 illegale (trap)

Esercizio 78

(a) Con 10 bit logici e 4 per il segmento, restano 10−4=610-4=6 bit di scostamento: un segmento è lungo al massimo 26=642^6=\mathbf{64} byte.

(b) I 4 bit del segmento dànno 24=162^4=\mathbf{16} segmenti al massimo.

Traduzione. Il segmento è ⌊a/64⌋\lfloor a/64\rfloor e lo scostamento a mod 64a\bmod64:

logico binario (10 bit) ⟨s,d⟩\langle s,d\rangle controllo fisico
9 0000 001001 ⟨0,9⟩\langle0,9\rangle 9<109<10 200+9=209200+9=\mathbf{209}
132 0010 000100 ⟨2,4⟩\langle2,4\rangle 4<64<6 252+4=256252+4=\mathbf{256}
79 0001 001111 ⟨1,15⟩\langle1,15\rangle 15<2015<20 100+15=115100+15=\mathbf{115}
64 0001 000000 ⟨1,0⟩\langle1,0\rangle 0<200<20 100+0=100100+0=\mathbf{100}
259 0100 000011 ⟨4,3⟩\langle4,3\rangle 3<323<32 683+3=686683+3=\mathbf{686}
135 0010 000111 ⟨2,7⟩\langle2,7\rangle 7≥67\ge6 errore di segmentazione
320 0101 000000 ⟨5,0⟩\langle5,0\rangle il processo ha solo 5 segmenti (0-4) segmento non valido

Ogni segmento ha dimensione massima 64 byte (punto a), ma la lunghezza reale è quella della tabella: per questo l'indirizzo 135 cade nel segmento 2 (lunghezza 6) e non è valido.

Esercizio 49

La figura dell'eserciziario mostra i segmenti in memoria; dalla soluzione si ricavano base e lunghezza dei segmenti usati:

segmento base lunghezza
0 (non serve) 1536
1 8960 20
2 144 256
3 4903 1408
4 6482 150
logico controllo fisico
⟨0,1984⟩\langle0,1984\rangle 1984≥15361984\ge1536 errore: indirizzo illegale
⟨1,18⟩\langle1,18\rangle 18<2018<20 8960+18=89788960+18=\mathbf{8978}
⟨2,250⟩\langle2,250\rangle 250<256250<256 144+250=394144+250=\mathbf{394}
⟨3,1400⟩\langle3,1400\rangle 1400<14081400<1408 4903+1400=63034903+1400=\mathbf{6303}
⟨4,112⟩\langle4,112\rangle 112<150112<150 6482+112=65946482+112=\mathbf{6594}

Errori tipici

  • Dimenticare il controllo d<Lsd<L_s e tradurre comunque.
  • Confrontare con ≤\le invece che con << (se la lunghezza è LL, i byte validi sono 0…L−10\ldots L-1).
  • Confondere la dimensione massima di un segmento (2bit di offset2^{\text{bit di offset}}) con la sua lunghezza reale nella tabella.
  • Non controllare che il numero di segmento esista nel processo.
  • Sommare la lunghezza invece della base.

Versione ripasso

Metodo. ⟨s,d⟩\langle s,d\rangle: segmento esistente? d<Lsd<L_s? Allora fisico =Bs+d=B_s+d; altrimenti trap (errore di segmentazione o segmento non valido).

Ex. 90. ⟨0,430⟩→219+430=649\langle0,430\rangle\to219+430=649; ⟨1,10⟩→2310\langle1,10\rangle\to2310; ⟨2,500⟩\langle2,500\rangle illegale (500≥100500\ge100); ⟨3,400⟩→1327+400=1727\langle3,400\rangle\to1327+400=1727; ⟨4,112⟩\langle4,112\rangle illegale (112≥96112\ge96).

Ex. 78. 10 bit, 4 di segmento →\to 6 di offset: segmenti da 64 byte al massimo, 16 segmenti. s=⌊a/64⌋s=\lfloor a/64\rfloor, d=a mod 64d=a\bmod64: 9 →⟨0,9⟩→209\to\langle0,9\rangle\to209; 132 →⟨2,4⟩→256\to\langle2,4\rangle\to256; 79 →⟨1,15⟩→115\to\langle1,15\rangle\to115; 64 →⟨1,0⟩→100\to\langle1,0\rangle\to100; 259 →⟨4,3⟩→686\to\langle4,3\rangle\to686; 135 →⟨2,7⟩\to\langle2,7\rangle, 7≥67\ge6: errore di segmentazione; 320 →⟨5,0⟩\to\langle5,0\rangle: segmento non valido.

Ex. 49. Limiti: segmento 0 lungo 1536, 1 base 8960 (20), 2 base 144 (256), 3 base 4903 (1408), 4 base 6482 (150). ⟨0,1984⟩\langle0,1984\rangle illegale; ⟨1,18⟩→8978\langle1,18\rangle\to8978; ⟨2,250⟩→394\langle2,250\rangle\to394; ⟨3,1400⟩→6303\langle3,1400\rangle\to6303; ⟨4,112⟩→6594\langle4,112\rangle\to6594.

Errori tipici: niente controllo del limite; ≤\le al posto di <<; dimensione massima ≠\ne lunghezza reale; segmento inesistente.

Teoria: Memoria centrale - allocazione contigua, paginazione e segmentazioneUn programma deve stare in memoria centrale per girare; la MMU traduce a ogni accesso l'indirizzo logico (virtuale) in indirizzo fisico, sommando un registro di rilocazione e controllando il limite; con l'allocazione contigua (partizioni fisse o variabili, first/best/worst fit) si hanno frammentazione interna ed esterna e serve la compattazione; la paginazione divide memoria logica in pagine e memoria fisica in frame della stessa dimensione (potenza di 2), elimina la frammentazione esterna, traduce (p, d) con la tabella delle pagine (PTBR, PTLR) e riduce il costo dei due accessi con il TLB (EAT = h * t + (1 - h) * 2t); le tabelle grandi si dividono in gerarchiche, hash o invertite; lo swapping sposta intere pagine o processi su disco; la segmentazione usa blocchi di lunghezza variabile con coppia (base, limite), eventualmente paginati; Intel IA-32 usa segmentazione con paginazione a due livelli (10+10+12 bit) e IA-64 quattro livelli su 48 bit.Memoria centrale - allocazione contigua, paginazione e segmentazione →.

Teoria collegata