Esercizio - Tempo di accesso effettivo con TLB e page fault (eserciziario, esercizi 32, 70 e 118)

In questa pagina 6

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, e slide delle lezioni).

Esercizio 118. Sistema con tabella delle pagine in memoria centrale e TLB. Ogni riferimento alla memoria (anche alla tabella) richiede 200 ns; il reperimento nel TLB richiede 20 ns. Quale deve essere l'hit ratio del TLB per avere un tempo di accesso effettivo medio di 240 ns?
Esercizio 32. Memoria virtuale paginata; CPU con ciclo di 1 $\mu$ s; accedere a una pagina diversa da quella corrente costa 1 $\mu$ s in più; pagine da 1000 parole; il dispositivo di paginazione è un tamburo che ruota a 3000 giri al minuto e trasferisce 1 milione di parole al secondo. Misure: l'1% delle istruzioni accede a una pagina diversa da quella corrente; di queste, l'80% accede a una pagina già in memoria; quando serve una pagina nuova, la pagina sostituita risulta modificata il 50% delle volte. Tempo medio effettivo di un'istruzione, con un solo processo e CPU inattiva durante i trasferimenti dal tamburo.
Esercizio 70. Stringa di riferimenti 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 3, 2, 7, 6, 3, 2, 1, 2, 3, 6; tempo di accesso effettivo con LRU e 5 frame. Un page fault senza salvataggio della pagina sostituita costa 80 ms, uno con salvataggio 140 ms; un accesso alla memoria 80 $\mu$ s; gli accessi alle pagine 1, 2, 3 sono sempre in scrittura. Inizialmente i 5 frame sono vuoti.
Slide. (a) Memoria 10 ns, hit ratio 80% e 99%: slowdown? (b) Accesso 200 ns, fault da 8 ms: $p$ massimo per un degrado del 10%.

Teoria: Memoria centrale - allocazione contigua, paginazione e segmentazione, Memoria virtuale - paginazione su richiesta e sostituzione delle pagine.

Le formule

Con il TLB (tempo del TLB $\tau$ , accesso alla memoria $t$ , hit ratio $h$ ): hit: $\tau+t$ ; miss: $\tau+t$ (tabella) $+\,t$ (dato) $=\tau+2t$ . $\text{EAT}=h(\tau+t)+(1-h)(\tau+2t)$ . Se si trascura $\tau$ : $\text{EAT}=ht+(1-h)2t$ .
Con i page fault: $\text{EAT}=(1-p)\,t+p\,t_{\text{fault}}$ ; in generale, la media pesata dei costi di ogni caso, ognuno con la sua frequenza.

Esercizio 118

Con $\tau=20$ , $t=200$ ns:

$h\,(20+200)+(1-h)(20+200+200)=240\ \Rightarrow\ 220h+420-420h=240\ \Rightarrow\ -200h=-180\ \Rightarrow\ h=\mathbf{0{,}9}.$

Verifica: $0{,}9\cdot220+0{,}1\cdot420=198+42=240$ ns.

Esercizio 32

Tempo di un trasferimento dal tamburo. Il tamburo gira a 3000 giri/min, cioè $50$ giri/s: una rotazione completa dura $20$ ms e la latenza media è mezza rotazione, $30/3000=10$ ms $=10\,000\ \mu$ s. Trasferire 1000 parole (una pagina) a $10^6$ parole/s costa $1$ ms $=1000\ \mu$ s. Quindi leggere una pagina costa $10\,000+1000=11\,000\ \mu$ s; scrivere una pagina costa lo stesso.

Casi e frequenze (su 1 istruzione):

caso	probabilità	costo
stessa pagina	$0{,}99$	$1\ \mu$ s
altra pagina, già in memoria	$0{,}01\cdot0{,}8=0{,}008$	$2\ \mu$ s (1 di ciclo + 1 in più)
altra pagina non in memoria (page fault)	$0{,}01\cdot0{,}2=0{,}002$	lettura della pagina nuova: $11\,000\ \mu$ s
fault con vittima modificata	$0{,}002\cdot0{,}5=0{,}001$	scrittura della vittima: altri $11\,000\ \mu$ s

$\text{EAT}=0{,}99\cdot1+0{,}008\cdot2+0{,}002\cdot11\,000+0{,}001\cdot11\,000=0{,}99+0{,}016+22+11=\mathbf{34{,}0\ \mu s}.$

Ogni fault costa una lettura (probabilità $0{,}002$ ), e in più una scrittura nella metà dei casi ( $0{,}001$ ). Per essere precisi si dovrebbe aggiungere a ogni fault anche il microsecondo del ciclo (variazione di $0{,}002\ \mu$ s: trascurabile); il risultato è $34{,}006\ \mu$ s.

Esercizio 70

Numero di fault e di hit con LRU, 5 frame. Si segnano i fault (F):

rif.	1	2	3	4	2	1	5	6	2	1	3	2	7	6	3	2	1	2	3	6
esito	F	F	F	F	hit	hit	F	F	hit	hit	F	hit	F	hit	hit	hit	hit	hit	hit	hit
vittima								3			4		5

I primi 4 fault e il quinto (pagina 5) riempiono i frame vuoti: nessuna vittima.
$t=8$ (pagina 6): la meno recente è la 3 (ultimo uso a $t=3$ ). La 3 è stata scritta (le pagine 1, 2, 3 sono sempre in scrittura): va salvata su disco prima di essere sostituita: fault con salvataggio.
$t=11$ (pagina 3): la meno recente è la 4 (mai scritta): sostituzione senza salvataggio.
$t=13$ (pagina 7): la meno recente è la 5 (mai scritta): senza salvataggio.

Totale: 8 fault, di cui 1 con salvataggio e 7 senza; gli altri $20-8=12$ riferimenti sono hit, costano l'accesso diretto di 80 $\mu$ s.

$\text{EAT}=\frac{12\cdot80\ \mu\text{s}+7\cdot80\,000\ \mu\text{s}+1\cdot140\,000\ \mu\text{s}}{20}=\frac{960+560\,000+140\,000}{20}\ \mu\text{s}=35\,048\ \mu\text{s}\approx\mathbf{35{,}048\ ms}.$

(Il tempo effettivo è dominato dai fault: le $12$ hit pesano meno di 1 ms su 701 ms.)

Esempi dalle slide

(a) Slowdown del TLB. $t=10$ ns: con $h=0{,}80$ : $0{,}8\cdot10+0{,}2\cdot20=12$ ns, cioè il 20% in più. Con $h=0{,}99$ : $0{,}99\cdot10+0{,}01\cdot20=10{,}1$ ns, solo l'1% in più.

(b) Page fault. Accesso 200 ns, fault 8 ms $=8\,000\,000$ ns: $\text{EAT}=200+7\,999\,800\,p$ . Per un degrado minore del 10%: $220>200+7\,999\,800\,p$ , quindi $p<20/7\,999\,800=2{,}5\cdot10^{-6}$ : meno di un fault ogni 400 000 accessi. Con $p=0{,}001$ il tempo è $8{,}2\ \mu$ s, 40 volte maggiore.

Errori tipici

Dimenticare che un TLB miss costa due accessi alla memoria (tabella più dato).
Nell'esercizio 32, sommare per ogni fault la lettura e la scrittura anche quando la vittima non è modificata: la scrittura si paga solo nel 50% dei fault.
Usare come probabilità di fault $0{,}01$ invece di $0{,}01\cdot0{,}2=0{,}002$ .
Nell'esercizio 70, non fare il salvataggio quando la vittima è una pagina scritta (la 3 alla sostituzione a $t=8$ ).
Convertire male le unità (3000 giri/min $\to$ latenza media 10 ms, non 20 ms).

Versione ripasso

Formule. TLB: $\text{EAT}=h(\tau+t)+(1-h)(\tau+2t)$ . Fault: $\text{EAT}=(1-p)t+p\,t_{\text{fault}}$ , o media pesata dei casi.

118. $220h+420(1-h)=240\Rightarrow h=0{,}9$ .

32. Latenza $30/3000=10$ ms, trasferimento $1000/10^6=1$ ms $\to$ pagina $11\,000\ \mu$ s. Casi: 0,99 $\cdot$ 1; 0,008 $\cdot$ 2; fault 0,002 $\cdot$ 11 000; vittima modificata 0,001 $\cdot$ 11 000 $\to0{,}99+0{,}016+22+11=34{,}0\ \mu$ s.

70. LRU con 5 frame: 8 fault (5 su frame vuoti, poi 6 sostituisce la 3 con salvataggio, 3 sostituisce la 4, 7 sostituisce la 5), 12 hit. $\text{EAT}=\dfrac{12\cdot80+7\cdot80\,000+140\,000}{20}\ \mu\text{s}=35{,}048$ ms.

Slide. $h=0{,}8\to12$ ns (+20%); $h=0{,}99\to10{,}1$ ns (+1%). $p<2{,}5\cdot10^{-6}$ per degrado $<10\%$ con 200 ns e 8 ms.

Passaggi. 118: $h(20+200)+(1-h)(20+200+200)=240$ . 32: pagina $=10\,000+1000=11\,000\ \mu$ s; probabilità: 0,99 (1 $\mu$ s), 0,008 (2 $\mu$ s), 0,002 (fault: lettura 11 000), 0,001 (vittima modificata: scrittura 11 000) $\to34{,}0\ \mu$ s. 70: LRU 5 frame, fault sulle pagine 1, 2, 3, 4, 5 (frame vuoti), poi 6 (toglie la 3, dirty, 140 ms), 3 (toglie la 4), 7 (toglie la 5): 7 fault a 80 ms, 1 a 140 ms, 12 hit da 80 $\mu$ s: $35{,}048$ ms. Slide: $0{,}8\cdot10+0{,}2\cdot20=12$ ns; $p<2{,}5\cdot10^{-6}$ .

Errori tipici: TLB miss con un solo accesso; scrittura della vittima sempre pagata; $p=0{,}01$ al posto di $0{,}002$ ; vittima dirty non salvata; latenza di un giro intero.

Teoria: Memoria centrale - allocazione contigua, paginazione e segmentazione.