Salta al contenuto
Note per Studenti Esercizio - Working set, thrashing e frequenza dei page fault (eserciziario, esercizio 87)

Esercizio - Working set, thrashing e frequenza dei page fault (eserciziario, esercizio 87)

In questa pagina 5

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Si consideri la stringa di riferimenti (partendo con t=0t=0)

2 6 5 7 7 7 7 5 1 6 4

e il working set WS(t,Δ)WS(t,\Delta) all'istante tt con intervallo Δ\Delta.

  1. Cos'è WS(10,8)WS(10,8), cioè dopo l'ultimo accesso?
  2. Nel caso precedente, quanti page fault ci sono complessivamente con Δ=4\Delta=4 (supponendo che in ogni istante si mantenga in memoria esattamente il solo working set)?

Inoltre (dalle slide): come si usa D=∑iWSSiD=\sum_iWSS_i per riconoscere il thrashing e come interviene la frequenza dei page fault.

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 →.

Definizione usata

WS(t,Δ)WS(t,\Delta) è l'insieme delle pagine riferite negli ultimi Δ\Delta riferimenti che terminano all'istante tt (compreso). La sua dimensione è WSS(t)WSS(t).

Numeriamo i riferimenti a partire da t=0t=0:

tt 0 1 2 3 4 5 6 7 8 9 10
pagina 2 6 5 7 7 7 7 5 1 6 4

Punto 1: WS(10,8)WS(10,8)

Gli ultimi 8 riferimenti fino a t=10t=10 sono quelli da t=3t=3 a t=10t=10: 7 7 7 7 5 1 6 4. Le pagine distinte sono

WS(10,8)={1,4,5,6,7}(dimensione 5).WS(10,8)=\{1,4,5,6,7\}\qquad(\text{dimensione }5).

La pagina 2 (t=0t=0) e il primo riferimento alla 6 (t=1t=1) sono fuori finestra; la 6 è comunque nell'insieme perché è riferita di nuovo a t=9t=9.

Punto 2: page fault con Δ=4\Delta=4

Si tiene in memoria solo il working set: a ogni istante si trovano in memoria le pagine riferite negli ultimi 4 riferimenti, e le altre vengono tolte. Un riferimento causa un page fault se la pagina non era nel working set dell'istante precedente (cioè non è stata riferita nei 4 riferimenti precedenti).

tt pagina riferimenti precedenti (ultimi 4) in memoria? WS(t,4)WS(t,4) WSSWSS
0 2 – no {2}\{2\} 1
1 6 2 no {2,6}\{2,6\} 2
2 5 2 6 no {2,5,6}\{2,5,6\} 3
3 7 2 6 5 no {2,5,6,7}\{2,5,6,7\} 4
4 7 2 6 5 7 sì {5,6,7}\{5,6,7\} 3
5 7 6 5 7 7 sì {5,7}\{5,7\} 2
6 7 5 7 7 7 sì {7}\{7\} 1
7 5 7 7 7 7 no (uscita dalla finestra) {5,7}\{5,7\} 2
8 1 7 7 7 5 no {1,5,7}\{1,5,7\} 3
9 6 7 7 5 1 no {1,5,6,7}\{1,5,6,7\} 4
10 4 7 5 1 6 no {1,4,5,6}\{1,4,5,6\} 4

I fault sono a t=0,1,2,3t=0,1,2,3 (4 fault di primo accesso), t=7t=7 (la 5, uscita dalla finestra: era stata riferita a t=2t=2, ben oltre 4 riferimenti prima), t=8,9,10t=8,9,10 (pagine 1, 6, 4): in totale

4+1+3=8 page fault.4+1+3=\mathbf{8\ page\ fault}.

Il working set varia nel tempo: WSSWSS passa da 4 a 1 e poi risale a 4 (picchi di fault quando la località cambia, valli quando il working set è caricato). Con Δ\Delta troppo piccola si hanno più fault; con Δ\Delta grande il working set copre più "località" insieme.

Thrashing e frequenza dei fault (dalle slide)

  • Si stima la richiesta totale di frame D=∑iWSSiD=\sum_iWSS_i. Se D>mD>m (i frame disponibili) c'è thrashing: i processi non hanno i frame per il proprio working set e il sistema passa il tempo a caricare e scaricare pagine. Il sistema operativo deve sospendere o scaricare un processo (diminuire il grado di multiprogrammazione).
  • Con la frequenza dei page fault (PFF) si fissa un intervallo accettabile: se il tasso di un processo è sotto la soglia inferiore gli si toglie un frame, se supera la soglia superiore gli se ne assegna uno; se non ci sono frame liberi, si sospende un processo.

Esempio. m=20m=20 frame; tre processi hanno WSS=9, 7, 6WSS=9,\ 7,\ 6: D=22>20D=22>20, thrashing: si sospende (per esempio) il processo da 6, poi D=16≤20D=16\le20.

Errori tipici

  • Includere nel working set i riferimenti prima della finestra.
  • Contare come fault i riferimenti a pagine ancora nel working set (per esempio t=4,5,6t=4,5,6).
  • Dimenticare il fault a t=7t=7: la 5, riferita a t=2t=2, è uscita dalla finestra di 4 riferimenti.
  • Confondere WSWS (insieme di pagine) con WSSWSS (numero di pagine).

Versione ripasso

Definizione. WS(t,Δ)WS(t,\Delta) = pagine distinte degli ultimi Δ\Delta riferimenti fino a tt compreso; WSS=∣WS∣WSS=|WS|; D=∑WSSi>m⇒D=\sum WSS_i>m\Rightarrow thrashing ⇒\Rightarrow sospendere un processo. PFF: tasso basso →\to togliere un frame; alto →\to darne uno.

Stringa 2 6 5 7 7 7 7 5 1 6 4 (t=0..10t=0..10). WS(10,8)WS(10,8): riferimenti da t=3t=3 a 1010 (7 7 7 7 5 1 6 4) →{1,4,5,6,7}\to\{1,4,5,6,7\}.

Fault con Δ=4\Delta=4 (si tiene solo il working set; fault se la pagina non è tra gli ultimi 4 riferimenti precedenti): t=0,1,2,3t=0,1,2,3 (primi accessi), t=7t=7 (la 5, uscita dalla finestra), t=8,9,10t=8,9,10 (1, 6, 4) →\to 8. WSSWSS: 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 4.

Tabella WSS(t,4)WSS(t,4) per 2 6 5 7 7 7 7 5 1 6 4: 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 4. Fault a t=0,1,2,3,7,8,9,10t=0,1,2,3,7,8,9,10 (8); WS(10,8)={1,4,5,6,7}WS(10,8)=\{1,4,5,6,7\}.

Errori tipici: includere riferimenti fuori finestra; contare fault sulle pagine ancora nel working set; dimenticare il fault a t=7t=7; WS≠WSSWS\ne WSS.

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