Risolto Working set model.

Stato
Discussione chiusa ad ulteriori risposte.

mattstack

Utente Bronze
1 Aprile 2021
44
13
12
27
Salve, mi sto cimentando nello studio della teoria dei sistemi operativi e attualmente sto studiando gli algoritmi di sostituzione delle pagine basati sul working set dei processi, avendo da prima studiando l'algoritmo di aging, come evoluzione del NFU, mi chiedo se sia utilizzabile anche come algoritmo working set oriented; il numero di bit che compone il contatore di ogni pagina è pari al numero di cicli di clock che definiscono il working set dei processi stessi.
Definendo quindi il working set come le pagine indirizzate da un processo negli ultimi k cicli di clock.
Una pagina cui contatore e a 0 sarà una pagina non appartenente al working set, in caso di assenza di pagine non appartenenti allora verrà presa la pagina con il contatore più piccolo ovvero quella meno utilizzata o cui accesso da parte del processo non è recente; Prendendo a prescindere quindi la pagina cui contatore è più piccolo (identico all'aging)
Se per esempio k, ovvero il numero del cicli di clock che definisce il working, è pari a 4 data la seguente configurazione:
Codice:
       1°           2°           3°          4°          5°          6°
    A, B, C       A,C           D, A           C, D           E
 |------------|------------|------------|------------|------------|------------|  
               |--------------------------------------------------|  ^page fault
                         working set
 
Contatore a 4 bit;

          A  |  B  |  C  |  D  |  E 
 1°     8h   8h   8h   0h   0h
 2°     Ch   4h   Ch  0h   0h
 3°     Eh   2h   6h   8h   0h
 4°     7h   1h   Bh   Ch   0h
 5°     3h   0h   5h   6h    8h

Risulta quindi che la pagina B è da sfrattare in quanto non appartiene al working set del processo, ed è così.
La mia domanda quindi è la seguente:
È possibile utilizzare l'aging come algoritmo working set oriented, c'è qualcosa che mi sfugge in caso negativo?
 

St3ve

Utente Jade
12 Ottobre 2011
2,313
5
1,648
680
Ultima modifica:
Penso di sì, da quanto ho capito il working set swapping e le politiche di admission control si possono applicare sopra ad ogni altro algoritmo di page replacement.

Visto che ti stai guardando l'argomento, poterbbe interessarti qualche news. Con Linux 5.19 dovrebbero cambiare l'algoritmo di page replacement dalla doppia LRU (1) ad una multigenerational LRU (2, 3, 4). In parole povere l'algoritmo attuale funziona con due liste (in realtà credo che siano ad orologio) LRU-like, una per il working set e una per i candidati allo swap out, mentre quello nuovo funzionerà con una gerarchia di liste basata sull'ageing. Non ne so un granché a riguardo, ma era giusto per menzionarti che quello che leggi sul libro non è proprio quello che avviene nella pratica. I problemi di trashing ormai non ci sono più perché il il page out intensivo è proibitivo: la RAM è molto più veloce del disco quindi piuttosto che ritrovarti in situazioni di trashing installi un OOM killer (prendi un processo che sta consumando tanta RAM e lo ammazzi), senza complicare l'algoritmo di page replacement.
 
  • Mi piace
Reazioni: mattstack

mattstack

Utente Bronze
1 Aprile 2021
44
13
12
27
Ultima modifica:
Penso di sì, da quanto ho capito il working set swapping e le politiche di admission control si possono applicare sopra ad ogni altro algoritmo di page replacement.

Visto che ti stai guardando l'argomento, poterbbe interessarti qualche news. Con Linux 5.19 dovrebbero cambiare l'algoritmo di page replacement dalla doppia LRU (1) ad una multigenerational LRU (2, 3, 4). In parole povere l'algoritmo attuale funziona con due liste (in realtà credo che siano ad orologio) LRU-like, una per il working set e una per i candidati allo swap out, mentre quello nuovo funzionerà con una gerarchia di liste basata sull'ageing. Non ne so un granché a riguardo, ma era giusto per menzionarti che quello che leggi sul libro non è proprio quello che avviene nella pratica. I problemi di trashing ormai non ci sono più perché il il page out intensivo è proibitivo: la RAM è molto più veloce del disco quindi piuttosto che ritrovarti in situazioni di trashing installi un OOM killer (prendi un processo che sta consumando tanta RAM e lo ammazzi), senza complicare l'algoritmo di page replacement.
Grazie mille :)
Messaggio unito automaticamente:

Penso di sì, da quanto ho capito il working set swapping e le politiche di admission control si possono applicare sopra ad ogni altro algoritmo di page replacement.

Visto che ti stai guardando l'argomento, poterbbe interessarti qualche news. Con Linux 5.19 dovrebbero cambiare l'algoritmo di page replacement dalla doppia LRU (1) ad una multigenerational LRU (2, 3, 4). In parole povere l'algoritmo attuale funziona con due liste (in realtà credo che siano ad orologio) LRU-like, una per il working set e una per i candidati allo swap out, mentre quello nuovo funzionerà con una gerarchia di liste basata sull'ageing. Non ne so un granché a riguardo, ma era giusto per menzionarti che quello che leggi sul libro non è proprio quello che avviene nella pratica. I problemi di trashing ormai non ci sono più perché il il page out intensivo è proibitivo: la RAM è molto più veloce del disco quindi piuttosto che ritrovarti in situazioni di trashing installi un OOM killer (prendi un processo che sta consumando tanta RAM e lo ammazzi), senza complicare l'algoritmo di page replacement.
Un ulteriore domanda: nel libro che sto utilizzando (I moderni sistemi operativi di Tenenbaum 3^a edizione) spiega che l'algoritmo PFF(page fault frequency) per l'allocazione dei frame ai processi viene utilizzato con un algoritmo di sostituzione delle pagine globale. Non dovrebbe essere il contrario?
Se l'algoritmo utilizzato è globale in questo modo non si limitano i frame utilizzati da parte del processo a quelli assegnati diventando di fatto un algoritmo locale?
Penso che ci sia stata una svista da parte dell'autore, anche perchè sarebbe il secondo errore che trovo, il primo era: sull'aging piuttosto di spiegare che viene effettuato uno shift a destra c'è scritto a sinistra.
 

St3ve

Utente Jade
12 Ottobre 2011
2,313
5
1,648
680
Ultima modifica:
Penso che ci sia stata una svista da parte dell'autore, anche perchè sarebbe il secondo errore che trovo, il primo era sull'aging piuttosto di spiegare che veniva effettuato uno shift a destra c'era scritto a sinistra.
Sul pdf italiano che ho trovato in rete dice: "Fortunatamente una piccola modifica all'algoritmo NFU lo rende capace di simulare piuttosto bene l'algoritmo LRU. La modifica avviene in due fasi. Primo, ognuno dei contatori viene shiftato a destra di un bit prima di somarvi il bit R; secondo, il bit R viene sommato al bit più a sinistra invece che a quello più a destra". (sezione 4.4.7, La simulazione della LRU via software, pag. 203). Quello che leggo qui è corretto, ma non ho idea se sia la tua stessa edizione.

nel libro che sto utilizzando (I moderni sistemi operativi di Tenenbaum 3^a edizione) spiega che l'algoritmo PFF(page fault frequency) per l'allocazione dei frame ai processi viene utilizzato con un algoritmo di sostituzione delle pagine globale. Non dovrebbe essere il contrario?
Se l'algoritmo utilizzato è globale in questo modo non si limitano i frame utilizzati da parte del processo a quelli assegnati diventando di fatto un algoritmo locale?
Continuo a citare il pdf che ho trovato: "Gli algoritmi locali sono quelli che assegnano ad ogni processo una quantità fissata di memoria; gli algoritmi globali allocano dinamicamente le pagine fisiche fra tutti i processi eseguibili; in questo modo, il numero delle pagine fisiche allocate ad un processo varia nel tempo. (...). Se viene usato un algoritmo globale, si potrebbe cominciare ogni processo con un numero di pagina proporzionale alla dimensione del processo, ma l'allocazione deve essere aggiornata dinamicamente mentre il processo gira. Un modo per gestire l'allocazione è di utilizzare l'algoritmo PFF (Page Fault Frequency, frequenza dei fault di pagina). Esso indica quanto incrementare o decrementare l'allocazione di una pagina del processo, ma non dice niente riguardo a quale pagina rimpiazzare quando si verifica un fault di pagina: controlla soltanto la dimensione allocata". (sezione 4.6.1, Confronto delle politiche di allocazione globali e locali, pag. 217).

Non mi sembra sbagliato, nel senso che il libro è consistente con le definizioni che fornisce, ma capisco la tua perplessità. Io l'avrei spiegato in un altro modo. Molti algoritmi di page replacement possono essere applicati sia localmente che globalmente; ad esempio, puoi cercare la last recently used page di un singolo processo (locale) o in tutta la memoria (globale). Se scegli di applicarli localmente devi prima capire quanta memoria vuoi assegnare ad ogni processo: devi inventarti un algoritmo di space reservation (i.e., quante pagine riservare per ogni processo) da applicare sopra all'algoritmo di page replacement applicato locale. Questo algoritmo può essere statico o dinamico. Una policy statica potrebbe essere una banale fairness dove tutti i processi si spartiscono equamente la memoria, oppure una fairness pesata sulla dimensione del processo dove il web browser di 1GB prende 1000 volte lo spazio riservato all'hello world di 1kB. Una policy dinamica potrebbe basarsi sulla frequenza dei page fault (PFF), aumentando lo spazio ai processi che iniziano ad annaspare (tanti page faults) e togliendolo a quelli che sono rilassati e comodi (pochi page faults).

Io userei local e global per indicare la politica di page replacement e fixed e dynamic per indicare la politica di space reservation. La politica di space reservation è sempre globale e serve solo quando la politica di page replacement è locale. Il libro non fa queste distinzioni ed è forse un po' confusionario, ma io non lo leggo come un errore perché è comunque consistente con le sue definizioni: se dici "Gli algoritmi locali sono quelli che assegnano ad ogni processo una quantità fissata di memoria; gli algoritmi globali allocano dinamicamente le pagine fisiche fra tutti i processi eseguibili" allora sono d'accordo che PFF è globale, però io l'avrei spiegato diversamente.
 

mattstack

Utente Bronze
1 Aprile 2021
44
13
12
27
Ultima modifica:
Cio che mi ha manda in totale confusione è quel "Se viene usato un algoritmo globale, si potrebbe cominciare ogni processo con un numero di pagina proporzionale alla dimensione del processo, ma l'allocazione deve essere aggiornata dinamicamente mentre il processo gira. Un modo per gestire l'allocazione è di utilizzare l'algoritmo PFF (Page Fault Frequency, frequenza dei fault di pagina).". Perché con un algoritmo globale, non dovrebbe essere locale, che senso ha assegnare un numero di pagine dinamiche o statiche a un processo quando si usa un algoritmo di page replacement globale?
La politica di space reservation è sempre globale e serve solo quando la politica di page replacement è locale
Bene proprio come pensavo, fatto sta che nel libro è chiaramente detto: "Se viene usato un algoritmo globale, si potrebbe cominciare ogni processo con un numero di pagina proporzionale alla dimensione del processo, ma l'allocazione deve essere aggiornata dinamicamente mentre il processo gira. Un modo per gestire l'allocazione è di utilizzare l'algoritmo PFF (Page Fault Frequency, frequenza dei fault di pagina)."

Aggiornamento: sono un idiota non avevo capito che "algoritmo globale" si riferisse alla politica di space reservation :oddio:

(Comunque nella mia versione lo shift del contatore è a sinistra, ma vabè sviste del traduttore).
 

St3ve

Utente Jade
12 Ottobre 2011
2,313
5
1,648
680
Perchè con un algoritmo globale, non dovrebbe essere locale, che senso ha assegnare un numero di pagine dinamiche o statiche a un processo quando si usa un algoritmo di page replacement globale?
Dinamico e statico è un termine che ho usato io per spiegarti il concetto in modo diverso, ma il libro non usa questi termini. Il libro dice: "Gli algoritmi locali sono quelli che assegnano ad ogni processo una quantità fissata di memoria; gli algoritmi globali allocano dinamicamente le pagine fisiche fra tutti i processi eseguibili". Il libro chiama page replacement algorithm sia cose tipo LDR che cose tipo il working set model che cose come il PFF. Non è sbagliato chiamarli page replacement algorithms perché effettivamente definiscono politiche su come rimpiazzare le pagine, però può essere confusionario perché lavorano su piani diversi: LDR è page replacement puro perché ti spiega come selezionare la pagina da rimpiazzare, il working set model fa delle considerazioni su un insieme di pagine che può essere caricato/scaricato in un'unica botta nel momento in cui un processo entra/esce nella fase di running e il PFF io l'ho definito algoritmo di space reservation perché sceglie come distribuire le pagine in un sistema time-sharing.

Considerando la definizione di statico/dinamico presente sul libro, la frase che ti manda in confusione la possiamo riscrivere come: "Se vogliamo che ogni processo usi una quantità non-fissata di memoria (a.k.a., se non vogliamo suddividere la memoria equamente per ogni processo né vogliamo dividerla proporzionalmente alla loro dimensione, ma vogliamo che la quantità di memoria distribuita ad ogni processo sia variabile in base a ciò che succede a runtime), si potrebbe cominciare ogni processo con un numero di pagine proporzionale alla dimensione del processo, ma l'allocazione deve essere aggiornata dinamicamente mentre il processo gira. Un modo per gestire l'allocazione è di utilizzare l'algoritmo PFF (Page Fault Frequency, frequenza dei fault di pagina)".

Oppure, usando la terminologia (fixed vs. dynamic e page replacement vs. space reservation) che ho introdotto nel post precedente: "Se viene usato un algoritmo di space reservation dinamico (i.e., il numero di pagine disponibili per ogni processo varia a runtime [vedi nota]), si potrebbe cominciare ogni processo con un numero di pagine proporzionale alla dimensione del processo, ma l'allocazione deve essere aggiornata dinamicamente mentre il processo gira. Un modo per gestire l'allocazione è di utilizzare l'algoritmo PFF (Page Fault Frequency, frequenza dei fault di pagina)".
[nota]: In realtà non è proprio corretto dire "varia a runtime" perché anche se con una policy fixed-space il numero di pagine riservato per ogni processo può cambiare a runtime: basta che si aggiunge/rimuove un processo.
 
  • Mi piace
Reazioni: mattstack
Stato
Discussione chiusa ad ulteriori risposte.