Salta al contenuto
Note per Studenti Esercizio - Second chance globale con bit di riferimento (eserciziario, esercizio 51)

Esercizio - Second chance globale con bit di riferimento (eserciziario, esercizio 51)

In questa pagina 5

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Sistema con memoria virtuale, memoria fisica di 8 frame condivisa da 4 processi attivi A, B, C, D. All'istante 100 lo stato della memoria è (campo R: 1 = riferita, 0 = no):

processo pagina logica pagina fisica istante di caricamento R
A 0 7 50 1
A 1 6 37 0
B 5 5 30 1
B 3 4 97 0
C 2 0 15 1
C 5 2 70 0
C 9 1 92 0
D 8 3 27 0

Il sistema usa la sostituzione second chance globale. Mostrare come cambia lo stato della memoria dopo le operazioni: all'istante 101 C riferisce la pagina logica 5; all'istante 105 A riferisce la pagina logica 9.

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

Come funziona l'algoritmo

La second chance è una FIFO con il bit di riferimento. Le pagine in memoria formano una coda ordinata per istante di caricamento (la più vecchia in testa). Il sistema è globale: la vittima si cerca fra tutte le pagine di tutti i processi, non solo fra quelle del processo che ha avuto il fault. Per scegliere la vittima si guarda la testa della coda:

  • se R=1R=1: la pagina ha una seconda opportunità: si pone R=0R=0 e la si sposta in coda (come se fosse appena arrivata), poi si guarda la nuova testa;
  • se R=0R=0: è la vittima.

Quando una pagina in memoria è riferita, si pone R=1R=1 e basta (non cambia posizione).

Ordine di partenza (per istante di caricamento): C2(15,1) - D8(27,0) - B5(30,1) - A1(37,0) - A0(50,1) - C5(70,0) - C9(92,0) - B3(97,0), dove la scrittura X p (t, R) indica la pagina pp del processo XX, caricata all'istante tt, con bit RR.

Istante 101: C riferisce la pagina 5

La pagina C5 è già in memoria (frame 2): non c'è nessun fault. Si pone solo R=1R=1. La coda resta nello stesso ordine:

C2(15,1) - D8(27,0) - B5(30,1) - A1(37,0) - A0(50,1) - C5(70,1) - C9(92,0) - B3(97,0)

Istante 105: A riferisce la pagina 9

La pagina A9 non è in memoria: page fault, e i frame sono tutti occupati (8 su 8). Serve una vittima.

  1. Si guarda la testa: C2, con R=1R=1. Ha la seconda opportunità: RR passa a 0 e la pagina va in coda.
  2. Nuova testa: D8, con R=0R=0: è la vittima. La pagina D8 esce dal frame 3.
  3. A9 si carica nel frame 3, all'istante di caricamento 105 e con R=1R=1 (è stata appena riferita).

Coda risultante:

B5(30,1) - A1(37,0) - A0(50,1) - C5(70,1) - C9(92,0) - B3(97,0) - C2(15,0) - A9(105,1)

Si nota che C2 è finita in coda mantenendo l'istante di caricamento 15 nell'etichetta ma occupando la posizione di "appena arrivata". La soluzione del corso riporta esattamente questa lista.

Una nota sul significato di "globale"

Nel testo dell'esercizio il sistema è detto "second chance globale". Un'annotazione sulle slide dice che, se "globale" si intende riferito all'intero processo (si considera riferito un processo che ha almeno una pagina con R=1R=1 e poi si azzerano le RR di tutte le sue pagine prima di passare al processo successivo), anche C5 dovrebbe tornare a 0 dopo l'esame di C2, e la lista finale avrebbe C5(70,0). La soluzione del corso lascia invece C5(70,1), cioè applica la second chance per pagina. Quest'ultima è la definizione dell'algoritmo data a lezione (bit di riferimento di ciascuna pagina) ed è quella usata sopra; in ogni caso la vittima (D8) e la pagina caricata (A9 nel frame 3) non cambiano.

Errori tipici

  • Spostare in coda una pagina con R=0R=0 invece di sostituirla.
  • Dimenticare di azzerare RR della pagina che ha avuto la seconda opportunità.
  • Mettere R=0R=0 alla pagina appena caricata: il riferimento che l'ha causata la rende R=1R=1.
  • Sostituire una pagina del solo processo A: la sostituzione è globale, la vittima può essere di qualunque processo (qui D8).
  • Contare un fault al riferimento C5: la pagina è già in memoria.

Versione ripasso

Regola. Coda per istante di caricamento. Testa con R=1R=1: si azzera RR e la pagina va in coda; testa con R=0R=0: vittima. Un riferimento a una pagina in memoria pone R=1R=1, nessun fault. Sostituzione globale: la vittima può essere di qualunque processo.

Partenza. C2(15,1) D8(27,0) B5(30,1) A1(37,0) A0(50,1) C5(70,0) C9(92,0) B3(97,0).

Istante 101. C5 è già in memoria →\to solo R=1R=1: … C5(70,1) …, stesso ordine.

Istante 105. A9 non c'è: fault. Testa C2 (R=1R=1) →\to R=0R=0, in coda; testa D8 (R=0R=0) →\to vittima; A9 nel frame 3 con R=1R=1. Lista finale: B5(30,1) A1(37,0) A0(50,1) C5(70,1) C9(92,0) B3(97,0) C2(15,0) A9(105,1). (Se "globale" significasse azzerare tutte le pagine del processo C, sarebbe C5(70,0); la soluzione del corso la lascia a 1.)

Errori tipici: sostituire la pagina con R=0R=0 spostandola; non azzerare RR alla seconda opportunità; pagina nuova con R=0R=0; vittima solo del processo che ha il 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 →.

Teoria collegata